ARTS打卡—第10周

今天是父亲节，祝老爸节日快乐，身体健康，也祝天下所有父亲节日快乐。上周由于带端午节回家没打卡拖延了一周。本周打卡内容主要是二叉树、RxJava 以及 adb 命令相关的内容。

• Algorithm
  • 题目一
    • 运行结果
  • 题目二
    • 运行结果
• Review
  *
  • 数学相关的操作：
  • 常用不同类型的 Observable
• Tips
• Share

Algorithm

这周主要作了二叉树相关的题目，第二个题目是第一个题目的延伸。

题目一

654. Maximum Binary Tree

Given an integer array with no duplicates. A maximum tree building on this array is defined as follow:

1. The root is the maximum number in the array.
2. The left subtree is the maximum tree constructed from left part subarray divided by the maximum number.
3. The right subtree is the maximum tree constructed from right part subarray divided by the maximum number.

Construct the maximum tree by the given array and output the root node of this tree.

Example:

> Input: [3,2,1,6,0,5] > Output: return the tree root node representing the following tree: > > 6 > / \ > 3 5 > \ / > 2 0 > \ > 1 >

题目要求将一数组转化成二叉树，而且操作是很规律的，因此用递归是最好不过了。

public TreeNode constructMaximumBinaryTree(int[] nums) {
  return constructMaximumBinaryTree(nums, 0, nums.length - 1);
}

private TreeNode constructMaximumBinaryTree(int[] nums, int start, int end) {
  int maxValPosition = findMaxValueBetweenPosition(nums, start, end);
  if (maxValPosition == -1) {
    return null;
  }
  TreeNode head = new TreeNode(nums[maxValPosition]);
  head.left = constructMaximumBinaryTree(nums, start, maxValPosition - 1);
  head.right = constructMaximumBinaryTree(nums, maxValPosition + 1, end);
  return head;
}

private int findMaxValueBetweenPosition(int[] nums, int start, int end) {
  if (start > end) {
    return -1;
  } else if (start == end) {
    return start;
  }
  int maxValPos = start;
  for (int i = start + 1; i <= end; i++) {
    if (nums[i] > nums[maxValPos]) {
      maxValPos = i;
    }
  }
  return maxValPos;
}

运行结果

题目二

998. Maximum Binary Tree II

We are given the root node of a maximum tree: a tree where every node has a value greater than any other value in its subtree.

Just as in the previous problem, the given tree was constructed from an list A (root = Construct(A)) recursively with the following Construct(A) routine:

• If A is empty, return null.
• Otherwise, let A[i] be the largest element of A. Create a root node with value A[i].
• The left child of root will be Construct([A[0], A[1], ..., A[i-1]])
• The right child of root will be Construct([A[i+1], A[i+2], ..., A[A.length - 1]])
• Return root.

Note that we were not given A directly, only a root node root = Construct(A).

Suppose B is a copy of A with the value val appended to it. It is guaranteed that B has unique values.

Return Construct(B).

Example1

>Input: root = [4,1,3,null,null,2], val = 5 >Output: [5,4,null,1,3,null,null,2] >Explanation: A = [1,4,2,3], B = [1,4,2,3,5] >

Example2

>Input: root = [5,2,4,null,1], val = 3 >Output: [5,2,4,null,1,null,3] >Explanation: A = [2,1,5,4], B = [2,1,5,4,3] >

Example3

>Input: root = [5,2,3,null,1], val = 4 >Output: [5,2,4,null,1,3] >Explanation: A = [2,1,5,3], B = [2,1,5,3,4] >

public TreeNode insertIntoMaxTree(TreeNode root, int val) {
  TreeNode tmp = new TreeNode(val);
  if (root == null) {
    return tmp;
  }
  if (val > root.val) {
    tmp.left = root;
    return tmp;
  }
  TreeNode head = root;
  while (head.right != null && val < head.right.val) {
    head = head.right;
  }
  if (head.right == null) {
    head.right = tmp;
  } else {
    TreeNode tmp1 = head.right;
    head.right = tmp;
    tmp.left = tmp1; 
  }

  return root;
}

运行结果

Review

本周阅读学习 RxJava 系列的中的两篇文章：

数学相关的操作：

使用这些接口时需要新引入一个 jar 包，如下：

implementation 'com.github.akarnokd:rxjava2-extensions:0.20.0'

• Average： 求出传递所有元素的平均值，将该平均值传递给 Observer；
• Count：统计所传数据的个数，即原始 Obserable 发送了多少次数据；
• Max：将所有传递的数据中的最大值当最终结果进行传递；
• Min: 和 Max 类似；
• Reduce：将所有的原始发送数据进行累积乘积，将最终结果传递给 Observer；
• Sum: 将所有数据求和；

Mathematical and Aggregate Operators

常用不同类型的 Observable

• Single：该 Observable 每次只传递一个元素或者抛出一个异常，常用的有网络连接等。

  Single.create(new SingleOnSubscribe<User>() { @Override public void subscribe(SingleEmitter<User> emitter) throws Exception { User user = new User("Anitaa"); emitter.onSuccess(user); } }) .observeOn(Schedulers.io()) .subscribe(new SingleObserver<User>() { @Override public void onSubscribe(Disposable d) { } @Override public void onSuccess(User user) { System.out.println(String.format("User with name %s successfully created: ", user.getName())); } @Override public void onError(Throwable e) { } });

• Maybe：该 Observable 可能发送元素也可能不发送元素；

  Maybe.create(new MaybeOnSubscribe<User>() { @Override public void subscribe(MaybeEmitter<User> emitter) { User user = new User("Anitaa"); emitter.onSuccess(user); } }) .observeOn(Schedulers.io()) .subscribe(new MaybeObserver<User>() { @Override public void onSubscribe(Disposable d) { } @Override public void onSuccess(User user) { System.out.println(String.format("User with name '%s' successfully created ", user.getName())); } @Override public void onError(Throwable e) { System.out.println("onError is called: " + e.getMessage()); } @Override public void onComplete() { System.out.println("onComplete is called"); } });

• Completeable：该 Observable 不会发送数据，但是会关注事件是否成功执行，onComplete或者onFail之一会被调用；

• Flowable：当 Observable 发送大量数据，但是 Observer 不能及时处理这些数据时需要使用此 Observable；

Different Types of Observables

Tips

1. git log —grep key-word命令可以过滤包含 key-word的 git log 信息；
2. EditText设置边框需要使用 background 属性 ；

Share

ADB 常用命令整理