Fork me on GitHub

ARTS(2)

Posted on | Edited on | In | Views:

ARTS 第二周分享

每周完成一个ARTS（也就是 Algorithm、Review、Tip、Share 简称ARTS）：

  1. 每周至少做一个 leetcode 的算法题
  2. 阅读并点评至少一篇英文技术文章
  3. 学习至少一个技术技巧
  4. 分享一篇有观点和思考的技术文章。

Algorithm

LeetCode 905. Sort Array By Parity

Given an array A of non-negative integers, return an array consisting of all the even elements of A, followed by all the odd elements of A.

You may return any answer array that satisfies this condition.

Input: [3,1,2,4]
Output: [2,4,3,1]
The outputs [4,2,3,1], [2,4,1,3], and [4,2,1,3] would also be accepted.

题意：偶数放在数组前部，奇数放在数组后部。
思路：双指针法：两个指针分别指向奇、偶数，适时移动即可。
易错点：注意数组下标越界问题。
以下解法：时间复杂度O(n2)（最差），空间复杂度O(1)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
    public int[] sortArrayByParity(int[] A) {
        if(A == null){
            return null;
        }
        int i = 0,j = 0;
        while(i<A.length && j<A.length){
            while(A[j] % 2 == 1){
                ++j;
                if(j>=A.length){
                    break;
                }
            }
            while(A[i]%2 == 0){
                ++i;
                if(i>=A.length){
                    break;
                }
            }
            if(j>i && i<A.length && j<A.length){
                move(A,i,j);
                ++i;
                ++j;
            }else{
                ++j;
            }
        }
        return A;
    }
    public void move(int[] A,int i,int j){
        int temp = A[j];
        for(int k = j;k>i;--k){
            A[k] = A[k-1];
        }
        A[i] = temp;
    }
}

扩展：可以尝试模仿快排的方式解题，应该会更容易，不过同时容易造成不稳定的情况。

LeetCode 129. Sum Root to Leaf Numbers

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.

An example is the root-to-leaf path 1->2->3 which represents the number 123.

Find the total sum of all root-to-leaf numbers.

Input: [1,2,3]
1
/
2 3
Output: 25

题意：从根节点到叶子节点数字组成一个 number，所有 number 的和输出。
思路：DFS 的思路，如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
	List<Integer> list = new ArrayList<>();
	int result = 0;

	public int sumNumbers(TreeNode root) {
		sums(root);
		return result;
	}

	public void sums(TreeNode root) {
        if(root == null){
            return;
        }
		if (root.left == null && root.right == null) {
			list.add(root.val);
			int temp = getNum(list);
			result += temp;
			list.remove(list.size() - 1);
			return;
		}
		list.add(root.val);
		sums(root.left);
		sums(root.right);
		list.remove(list.size() - 1);
	}

	public int getNum(List<Integer> list) {
		int ans = 0;
		for (int i = 0; i < list.size(); ++i) {
			ans = ans * 10 + list.get(i);
		}
		return ans;
	}
}

Review

本周阅读英文文章来自 javaworld ，名为：Thread behavior in the JVM

  1. 首先提到“new、runnable、running、suspended、blocked、terminated”Java 线程的六种状态。
  2. 然后重点提及了继承 thread 类和实现 Runnable 接口两种实现多线程的方式。
  3. 将线程分为：守护线程与非守护线程：
    1. 非守护线程：会一直执行到任务结束，除非出现System.exit()的情况。
    2. 守护线程：无需执行到任务最后。如果其他非守护线程都已经结束了，那么此守护线程也会立即结束。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
*  守护线程与非守护线程举例
*  执行规律为：main 线程首先 start，然后 daemon 线程开始打印
*  main 线程 sleep 后也很快结束任务，此时 daemon 线程还没彻底打印完成
*
* /

import java.util.stream.IntStream;

public class NonDaemonAndDaemonThread {

	public static void main(String... nonDaemonAndDaemon) throws InterruptedException {
		System.out.println("线程开始执行： " + Thread.currentThread().getName());

		// 遍历打印数字
		Thread daemonThread = new Thread(() -> IntStream.rangeClosed(1, 100000)
				.forEach(System.out::println));

		daemonThread.setDaemon(true);
		daemonThread.start();

		Thread.sleep(10);

		System.out.println("线程执行结束： " +
				Thread.currentThread().getName());
	}
}

笔者本机模拟截图如下：

main 线程 end 后，daemon 线程最终到470左右也发生 end，并未完成打印到 100000 的任务。

  1. 线程有 1~10 的优先级的说法，从低到高，但是并不能保证完全依据优先级先后执行。

    Remember, we can’t rely on program logic (order of threads or thread priority) to predict the JVM’s order of execution.

  2. Java threads 容易出现的错误：

    1. 在 run 方法中开启新线程；
    2. 同一个线程 start 两次；
    3. 多的线程同时改变一个对象的状态；
    4. 依赖线程优先级来实现逻辑；
    5. 依赖线程 start 的先后顺序来实现逻辑。

Tip

  1. 中英文混写的文章中，为了美观考虑，可以尽量在中英文中间加上空格，这里采用搜狗输入法的相关设置，默认为中文间加上空间，省心省事。
  2. idea 编辑器中，双击 SHIFT 键，可以调出全局搜索，可以搜索 JDK 中的相关类。
  3. lombok 插件尤其有用，可以节省很多 setter/getter 的格外设置。

Share

本周分享我用 Java 代码完成的：七种内部排序的代码实现

That’s all,thank you!

-------------The End-------------