发表于 | 分类于

Description:

Given a binary tree, return the postorder traversal of its nodes’ values.

解法：

递归解题，具体代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> output = new ArrayList();
        helper(root,output);
        return output;
    }
    void helper(TreeNode root,List<Integer> output){
        if(root == null){
            return;
        }
        helper(root.left,output);
        helper(root.right,output);
        output.add(root.val);
    }
}

发表于 | 分类于

Description:

Given a binary tree, return the preorder traversal of its nodes’ values.

解法：

递归解题，具体代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> output = new ArrayList();
        helper(root,output);
        return output;
    }
    void helper(TreeNode root,List<Integer> output){
        if(root == null){
            return;
        }
        output.add(root.val);
        helper(root.left,output);
        helper(root.right,output);
    }
}

发表于 | 分类于

Description:

Given a binary tree, return the inorder traversal of its nodes’ values. Example:

Input: [1,null,2,3]

1
2
3
4
5
1
 \
  2
 /
3

Output: [1,3,2]

Follow up: Recursive solution is trivial, could you do it iteratively?

解法：

直接递归的方法解题，具体代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> output = new ArrayList();
        helper(root,output);
        return output;
    }
    void helper(TreeNode root,List<Integer> output){
        if(root == null){
            return;
        }
        helper(root.left,output);
        output.add(root.val);
        helper(root.right,output);
    }
}

发表于 | 更新于 | 分类于

Description:

Given a binary tree, find the length of the longest path where each node in the path has the same value. This path may or may not pass through the root. Note: The length of path between two nodes is represented by the number of edges between them. Example 1: Input:

    5
   / \
  4   5
 / \   \
1   1   5

Output:

2

Example 2: Input:

    1
   / \
  4   5
 / \   \
4   4   5

Output:

2

Note: The given binary tree has not more than 10000 nodes. The height of the tree is not more than 1000.

解法：

这道题让我们求最长的相同值路径，对于这种树的路径问题，递归是不二之选。在递归函数中，我们首先对其左右子结点调用递归函数，得到其左右子树的最大相同值路径，下面就要来看当前结点和其左右子结点之间的关系了，如果其左子结点存在且和当前节点值相同，则left自增1，否则left重置0；同理，如果其右子结点存在且和当前节点值相同，则right自增1，否则right重置0。然后用left+right来更新结果res。而调用当前节点值的函数只能返回left和right中的较大值，因为如果还要跟父节点组path，就只能在左右子节点中选一条path，当然选值大的那个了，具体代码如下：

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 {
    int res;

    public int longestUnivaluePath(TreeNode root) {
        res = 0;
        helper(root);
        return res;
    }

    public int helper(TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            return 0;
        }
        int left = helper(root.left);
        int right = helper(root.right);
        if (root.left != null && root.val == root.left.val) {
            left++;
        } else {
            left = 0;
        }
        if (root.right != null && root.val == root.right.val) {
            right++;
        } else {
            right = 0;
        }
        if (left + right > res) {
            res = left + right;
        }
        if (left > right) {
            return left;
        }
        return right;
    }
}

发表于 | 更新于 | 分类于

Description:

The set [1,2,3,...,_n_] contains a total of _n_! unique permutations. By listing and labeling all of the permutations in order, we get the following sequence for _n_ = 3:

  1. "123"
  2. "132"
  3. "213"
  4. "231"
  5. "312"
  6. "321"

Given _n_ and _k_, return the _k_th permutation sequence. Note:

  • Given _n_ will be between 1 and 9 inclusive.
  • Given _k_ will be between 1 and _n_! inclusive.

Example 1:

Input: n = 3, k = 3
Output: “213”

Example 2:

Input: n = 4, k = 9
Output: “2314”

解法：

这道题主要是找规律，因为不必要把所有的排列都列出来，所以以 n = 4 k = 17为例：

首先我们要知道当n = 3时，其排列组合共有3! = 6种，当n = 4时，其排列组合共有4! = 24种，所有排列组合情况如下：

1234
1243
1324
1342
1423
1432
2134
2143
2314
2341
2413
2431
3124
3142
3214
3241
3412 <— k = 17
3421
4123
4132
4213
4231
4312
4321

我们可以发现，每一位上1,2,3,4分别都出现了6次，当最高位上的数字确定了，第二高位每个数字都出现了2次，当第二高位也确定了，第三高位上的数字都只出现了1次，当第三高位确定了，那么第四高位上的数字也只能出现一次，下面我们来看k = 17这种情况的每位数字如何确定，由于k = 17是转化为数组下标为16：

最高位可取1,2,3,4中的一个，每个数字出现3！= 6次，所以k = 16的第一位数字的下标为16 / 6 = 2，在 “1234” 中即3被取出。这里我们的k是要求的坐标为k的全排列序列，我们定义 k’ 为当最高位确定后，要求的全排序列在新范围中的位置，同理，k” 为当第二高为确定后，所要求的全排列序列在新范围中的位置，以此类推，下面来具体看看：

第二位此时从1,2,4中取一个，k = 16，则此时的 k’ = 16 % (3!) = 4，如下所示，而剩下的每个数字出现2！= 2次，所以第二数字的下标为4 / 2 = 2，在 “124” 中即4被取出。

3124
3142
3214
3241
3412 <— k’ = 4
3421

第三位此时从1,2中去一个，k’ = 4，则此时的k” = 4 % (2!) = 0，如下所示，而剩下的每个数字出现1！= 1次，所以第三个数字的下标为 0 / 1 = 0，在 “12” 中即1被取出。

3412 <— k” = 0
3421

第四位是从2中取一个，k” = 0，则此时的k”’ = 0 % (1!) = 0，如下所示，而剩下的每个数字出现0！= 1次，所以第四个数字的下标为0 / 1= 0，在 “2” 中即2被取出。

3412 <— k”’ = 0

那么我们就可以找出规律了
a1 = k / (n – 1)!
k1 = k

a2 = k1 / (n – 2)!
k2 = k1 % (n – 2)!
…

an-1 = kn-2 / 1!
kn-1 = kn-2 % 1!

an = kn-1 / 0!
kn = kn-1 % 0!

实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public String getPermutation(int n, int k) {
        StringBuilder nums = new StringBuilder("123456789");
        StringBuilder res = new StringBuilder();
        int[] array = new int[n + 1];
        array[0] = 1;
        for (int i = 1; i <= n; i++) {
            array[i] = array[i - 1] * i;
        }
        k -= 1;
        n -= 1;
        while (n >= 1) {
            int s = k / array[n];
            res.append(nums.charAt(s));
            nums.deleteCharAt(s);
            k = k % array[n];
            n--;
        }
        res.append(nums.charAt(0));
        return res.toString();
    }
}

发表于 | 更新于 | 分类于

Description:

Given a collection of numbers that might contain duplicates, return all possible unique permutations. Example:

Input: [1,1,2]
Output:
[
[1,1,2],
[1,2,1],
[2,1,1]
]

解法：

同样是排列问题，这道题去掉了一个限制条件，即可以有重复的元素。考虑例子{1,2,2}，在某次结果得到1，2，2后，在选择第二个元素时，由于2已经被选过，所以第三个2不用放在第二个位置上了，此时的条件为第三个二与第二个二相等，而第二个二还没有被选中，所以，为了避免重复，有限制条件即：

nums[i] == nums[i - 1] && used[i - 1] == 0

注意，这仅仅适用于num中的数是排好序的情况。具体实现代码如下：

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
class Solution {
    List<List<Integer>> result = new ArrayList<>();

    public List<List<Integer>> permuteUnique(int[] nums) {
        if (nums.length == 0) {
            return result;
        }
        int[] used = new int[nums.length];
        List<Integer> tmp = new ArrayList<>();
        Arrays.sort(nums);
        dfs(nums, used, tmp);
        return result;
    }

    void dfs(int[] nums, int[] used, List<Integer> tmp) {
        if (tmp.size() == nums.length) {
            result.add(new ArrayList<>(tmp));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (used[i] == 1 || (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == 0)) {
                continue;
            }
            tmp.add(nums[i]);
            used[i] = 1;
            dfs(nums, used, tmp);
            used[i] = 0;
            tmp.remove(tmp.size() - 1);
        }
    }
}

发表于 | 更新于 | 分类于

Description:

Given a collection of distinct integers, return all possible permutations. Example:

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

解法：

以A{a,b,c}为例，来说明全排列的生成方法，对于这个集合，其包含3个元素，所有的排列情况有3!=6种，对于每一种排列，其第一个元素有3种选择a,b,c，对于第一个元素为a的排列，其第二个元素有2种选择b,c；第一个元素为b的排列，第二个元素也有2种选择a，c，……，依次类推，我们可以将集合的全排列与一棵多叉树对应。如下图所示

因为没有重复项，可以各位交换模拟选择的过程。在此树中，每一个从树根到叶子节点的路径，就对应了集合A的一个排列。通过递归算法，可以避免多叉树的构建过程，直接生成集合A的全排列，具体代码如下：

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
class Solution {
    List<List<Integer>> result = new ArrayList<List<Integer>>();

    public List<List<Integer>> permute(int[] nums) {
        if (nums.length == 0) {
            return result;
        }
        get_permutation(nums, 0, nums.length);
        return result;
    }

    void get_permutation(int[] num, int i, int len) {
        if (i == len - 1) {
            List<Integer> tmp = new ArrayList<Integer>();
            for (int j = 0; j < len; j++) {
                tmp.add(num[j]);
            }
            result.add(tmp);
            return;
        }
        for (int j = i; j < len; j++) {
            swap(num, i, j);
            get_permutation(num, i + 1, num.length);
            swap(num, i, j);
        }

    }

    void swap(int[] array, int i, int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
}

另一种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
class Solution {
    List<List<Integer>> result = new ArrayList<>();

    public List<List<Integer>> permute(int[] nums) {
        if (nums.length == 0) {
            return result;
        }
        int[] used = new int[nums.length];
        List<Integer> tmp = new ArrayList<>();
        dfs(nums, used, tmp);
        return result;
    }

    void dfs(int[] nums, int[] used, List<Integer> tmp) {
        if (tmp.size() == nums.length) {
            result.add(new ArrayList<>(tmp));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (used[i] == 1) {
                continue;
            }
            tmp.add(nums[i]);
            used[i] = 1;
            dfs(nums, used, tmp);
            used[i] = 0;
            tmp.remove(tmp.size() - 1);
        }
    }
}

发表于 | 更新于 | 分类于

Description:

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers. If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order). The replacement must be in-place and use only constant extra memory. Here are some examples.

Inputs are in the left-hand column and its corresponding outputs are in the right-hand column. 1,2,3 → 1,3,2 3,2,1 → 1,2,3 1,1,5 → 1,5,1

解法：

简而言之，这道题的意思就是寻找下一个字典序的全排列，所谓字典序，就是从小到大的顺序。算法思路如下： 以1，2，4，3，1为例：

因为是找递增的下一个排列，所以从后往前找到第一个升序对的位置，如1,2,4,3,1， 从后向前找就是2,4,3,1，因为2比前一个数4小，所以就锁定2这个数。之后就是在4,3,1中找到比2大的最小的那个数3，将3与2对换得到降序排列4,2,1.然后就是将4,2,1反序得到1,2,4.最终结果就是1,3,1,2,4。

代码如下：

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
44
45
46
47
48
49
50
51
52
53
class Solution {
    public void nextPermutation(int[] nums) {
        int rear = nums.length - 1;
        if (rear == -1) {
            return;
        }
        for (int i = rear - 1; i >= 0; i--) {
            int j = i + 1;
            if (nums[i] < nums[j]) {
                int min = 999999999;
                int exchangeindex = i;
                for (int ii = j; ii <= rear; ii++) {
                    int minus = nums[ii] - nums[i];
                    if (min > minus && minus > 0) {
                        min = minus;
                        exchangeindex = ii;
                    }
                }
                int l = nums[i];
                nums[i] = nums[exchangeindex];
                nums[exchangeindex] = l;
                sort(nums, j, rear);
                return;
            }
        }
        for (int i = 0; i <= rear; i++) {
            int j = rear - i;
            if (i >= j) {
                break;
            }
            int l = nums[i];
            nums[i] = nums[j];
            nums[j] = l;
        }
        return;
    }

    void sort(int[] array, int start, int end) {
        for (int i = start; i <= end; i++) {
            int x = array[i];
            int j = i - 1;
            while (j >= start) {
                if (array[j] > x) {
                    array[j + 1] = array[j];
                    j -= 1;
                } else {
                    break;
                }
            }
            array[j + 1] = x;
        }
    }
}

发表于 | 更新于 | 分类于

Description:

Given a _m_ x _n_ grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path. Note: You can only move either down or right at any point in time. Example:

Input:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
Output: 7
Explanation: Because the path 1→3→1→1→1 minimizes the sum.

解法： 经典的动态规划题，这里给出状态转移公式：

1
2
3
4
5
6
7
8
//起点
dp[0][0] = grid[0][0];
//第一行
dp[i][j] = dp[i][j - 1] + grid[i][j];
//第一列
dp[i][j] = dp[i - 1][j] + grid[i][j];
//其他
dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];

具体的代码如下：

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
class Solution {
    public int minPathSum(int[][] grid) {
        int[][] dp = new int[grid.length][grid[0].length];
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (i == 0 && j != 0) {
                    dp[i][j] = dp[i][j - 1] + grid[i][j];
                } else if (j == 0 && i != 0) {
                    dp[i][j] = dp[i - 1][j] + grid[i][j];
                } else if (i != 0 && j != 0) {
                    dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
                } else {
                    dp[i][j] = grid[i][j];
                }
            }
        }
        return dp[grid.length - 1][grid[0].length - 1];
    }

    public int min(int a, int b) {
        if (a > b) {
            return b;
        }
        return a;
    }
}

发表于 | 更新于 | 分类于

归并排序

基本思想

归并排序是分治的典型例子(divide-conquer)。总体的步骤为采用分的思想，将问题小化递归求解（分的阶段），然后将小化后的子问题合并得到最终大问题的解。对于排序而言，若细化为两个只有一个数字的数列时对齐合并处理可以很简单地得到有序的数列，归并排序运用的就是这种思想。

算法设计：

整体设计上，算法主要包括分与治这两个过程，

分的设计：

分是递归地解决问题，所以要充分考虑好参数的问题。 参数1：为了节省空间，不会在递归的函数中为分产生的数组分配新的空间，故分的数组是基于原数组空间的，所以需要一个参数为原数组的地址。 参数2与3：另外分主要依靠的是待分数组的左起点和右终点，同时这两个参数也可作为递归终止条件的判断。（这里顺便聊一下递归终止条件的书写，为了使递归有出口，终止条件应当尽量严格，比如在可以写right <= left 和 right == left 的情况下，前者更好，这里相当于偷了个懒，因为不确定分到最后right和left的具体情况） 参数4：考虑到合的过程中需要将结果临时存在一个辅助数组里再赋值到原数组中，故在这里设置一个已经分配好空间的数组指针作为参数。 分析好参数之后，递归就按照宏观思想来写就可以了。即先写终止条件，然后写递归体。

治的设计：

合并数组变得相对简单了。因为合并是在一个数组中的前后两部分进行，所以只需要知道开始点，中点，结束点就可以了。注意，因为采用了递归的设计，最终的结果应当保留到原数组中覆盖之前的结果，别只留在临时数组里。 具体代码如下： （这里为了调用方便包装了一下，所以其实两个函数是够了的）

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
class solution {
    public void merge(int[] a, int left, int mid, int right, int[] b) {
        int i = left, j = mid + 1, k = 0;
        while (i <= mid && j <= right) {
            if (a[i] < a[j]) {
                b[k++] = a[i++];
            } else {
                b[k++] = a[j++];
            }
        }
        while (i <= mid) {
            b[k++] = a[i++];
        }
        while (j <= right) {
            b[k++] = a[j++];
        }
        k = 0;
        while(left <= right){
            a[left++] = b[k++];
        }
    }

    public int[] merge_sort(int[] input) {
        if(input.length == 1){
            return input;
        }
        int[] result = new int[input.length];
        sort(input, 0, input.length - 1, result);
        return result;
    }

    private void sort(int[] input, int left, int right, int[] result) {
        if (left < right) {
            int mid = (right + left) / 2;
            sort(input, left, mid, result);
            sort(input, mid+1, right, result);
            merge(input, left, mid, right, result);
        }

    }
}