简化路径 

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
以 Unix 风格给出一个文件的绝对路径，你需要简化它。或者换句话说，将其转换为规范路径。

在 Unix 风格的文件系统中，一个点（.）表示当前目录本身；此外，两个点 （..） 表示将目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。更多信息请参阅：Linux / Unix中的绝对路径 vs 相对路径

请注意，返回的规范路径必须始终以斜杠 / 开头，并且两个目录名之间必须只有一个斜杠 /。最后一个目录名（如果存在）不能以 / 结尾。此外，规范路径必须是表示绝对路径的最短字符串。
 
示例 1：

输入："/home/"
输出："/home"
解释：注意，最后一个目录名后面没有斜杠。
示例 2：

输入："/../"
输出："/"
解释：从根目录向上一级是不可行的，因为根是你可以到达的最高级。
示例 3：

输入："/home//foo/"
输出："/home/foo"
解释：在规范路径中，多个连续斜杠需要用一个斜杠替换。
示例 4：

输入："/a/./b/../../c/"
输出："/c"
示例 5：

输入："/a/../../b/../c//.//"
输出："/c"
示例 6：

输入："/a//b////c/d//././/.."
输出："/a/b/c"
通过次数61,219提交次数149,306

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/simplify-path
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

醍醐灌顶

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
   public String simplifyPath(String path) {
    Stack<String> stack = new Stack<>();
    String[] items = path.split("/");
    for (String item : items) {
        if (item.isEmpty() || item.equals(".")) continue;
        if (item.equals("..")) {
            if (!stack.empty()) stack.pop();
        } else {
            stack.push(item);
        }
    }
    return "/" + String.join("/", stack);
}
}

参考文献

verygoodlee的题解

展开全文 >>

最小路径和 

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
给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

 

示例 1：


输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。
示例 2：

输入：grid = [[1,2,3],[4,5,6]]
输出：12
 

提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 200
0 <= grid[i][j] <= 100
通过次数160,664提交次数237,325

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-path-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

最简单的动态规划

因为位置（i，j）只能由（i-1,j）或者（i,j-1）走到,因此dp[i][j]=Math.min(dp[i - 1][j], dp[i][j - 1])+ grid，此外需要考虑边际条件，i-1<0以及j-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 int minPathSum(int[][] grid) {
        int h = grid.length;
        int w = grid[0].length;
        int[][] dp = new int[h][w];
        dp[0][0] = grid[0][0];
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                if (i - 1 >= 0 && j - 1 >= 0) {
                    dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
                } else if (i - 1 >= 0) {
                    dp[i][j] = dp[i - 1][j] + grid[i][j];
                } else if (j - 1 >= 0) {
                    dp[i][j] = dp[i][j - 1] + grid[i][j];
                }

            }
        }
        return dp[h - 1][w - 1];
    }
}

展开全文 >>

插入区间

57. 插入区间

难度：中等

给你一个 无重叠的 ，按照区间起始端点排序的区间列表。

在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。

示例 1：

1
2
输入：intervals = [[1,3],[6,9]], newInterval = [2,5]
输出：[[1,5],[6,9]]

示例 2：

1
2
3
输入：intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
输出：[[1,2],[3,10],[12,16]]
解释：这是因为新的区间 [4,8] 与 [3,5],[6,7],[8,10] 重叠。

示例 3：

1
2
输入：intervals = [], newInterval = [5,7]
输出：[[5,7]]

示例 4：

1
2
输入：intervals = [[1,5]], newInterval = [2,3]
输出：[[1,5]]

示例 5：

1
2
输入：intervals = [[1,5]], newInterval = [2,7]
输出：[[1,7]]

提示：

  • 0 <= intervals.length <= 104
  • intervals[i].length == 2
  • 0 <= intervals[i][0] <= intervals[i][1] <= 105
  • intervals 根据 intervals[i][0] 按 升序 排列
  • newInterval.length == 2
  • 0 <= newInterval[0] <= newInterval[1] <= 105

模拟

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
class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        if (intervals.length == 0 || intervals[0].length == 0) {
            return new int[][]{newInterval};
        }
        List<int[]> list = new ArrayList<>();

        boolean flag = true;
        for (int i = 0; i < intervals.length; i++) {
            // 如果存在交叉
            if ((intervals[i][0] <= newInterval[0] && intervals[i][1] >= newInterval[0]) ||
                    (intervals[i][1] >= newInterval[0] && intervals[i][0] <= newInterval[1])) {
                int min = Math.min(intervals[i][0], newInterval[0]);
                int max = Math.max(intervals[i][1], newInterval[1]);
                // 如果当前结果的最大右边界小于当前的最小值，那么移除原先结果中的区间
                if (list.size() > 0 && list.get(list.size() - 1)[1] >= min) {
                    min = list.get(list.size() - 1)[0];
                    list.remove(list.size() - 1);
                }
                // 加入更新后的区间
                list.add(new int[]{min, max});
                flag = false;
            } else {
                // 如果不存在交叉，直接插入
                list.add(intervals[i]);
            }
        }
        // 处理边界条件
        if (flag) {
            flag = false;
            for (int i = 0; i < list.size(); i++) {
                if (list.get(i)[0] > newInterval[1]) {
                    list.add(i, newInterval);
                    flag = true;
                    break;
                }
            }
            if (!flag) {
                list.add(newInterval);
            }
        }
        // 返回结果
        int[][] res = new int[list.size()][2];
        for (int i = 0; i < list.size(); i++) {
            res[i] = list.get(i);
        }
        return res;
    }
}

优雅的写法

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

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        int left = newInterval[0];
        int right = newInterval[1];
        boolean placed = false;
        List<int[]> ansList = new ArrayList<int[]>();
        for (int[] interval : intervals) {
            if (interval[0] > right) {
                // 在插入区间的右侧且无交集
                if (!placed) {
                    ansList.add(new int[]{left, right});
                    placed = true;                    
                }
                ansList.add(interval);
            } else if (interval[1] < left) {
                // 在插入区间的左侧且无交集
                ansList.add(interval);
            } else {
                // 与插入区间有交集，计算它们的并集
                left = Math.min(left, interval[0]);
                right = Math.max(right, interval[1]);
            }
        }
        if (!placed) {
            ansList.add(new int[]{left, right});
        }
        int[][] ans = new int[ansList.size()][2];
        for (int i = 0; i < ansList.size(); ++i) {
            ans[i] = ansList.get(i);
        }
        return ans;
    }
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/insert-interval/solution/cha-ru-qu-jian-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

作者：LeetCode-Solution来源：力扣（LeetCode）著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

展开全文 >>

用最少数量的箭引爆气球 

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
在二维空间中有许多球形的气球。对于每个气球，提供的输入是水平方向上，气球直径的开始和结束坐标。由于它是水平的，所以纵坐标并不重要，因此只要知道开始和结束的横坐标就足够了。开始坐标总是小于结束坐标。

一支弓箭可以沿着 x 轴从不同点完全垂直地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足  xstart ≤ x ≤ xend，则该气球会被引爆。可以射出的弓箭的数量没有限制。 弓箭一旦被射出之后，可以无限地前进。我们想找到使得所有气球全部被引爆，所需的弓箭的最小数量。

给你一个数组 points ，其中 points [i] = [xstart,xend] ，返回引爆所有气球所必须射出的最小弓箭数。

 
示例 1：

输入：points = [[10,16],[2,8],[1,6],[7,12]]
输出：2
解释：对于该样例，x = 6 可以射爆 [2,8],[1,6] 两个气球，以及 x = 11 射爆另外两个气球
示例 2：

输入：points = [[1,2],[3,4],[5,6],[7,8]]
输出：4
示例 3：

输入：points = [[1,2],[2,3],[3,4],[4,5]]
输出：2
示例 4：

输入：points = [[1,2]]
输出：1
示例 5：

输入：points = [[2,3],[2,3]]
输出：1
 

提示：

0 <= points.length <= 104
points[i].length == 2
-231 <= xstart < xend <= 231 - 1
通过次数43,900提交次数86,153

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-number-of-arrows-to-burst-balloons
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

avatar

贪心算法

按照右边界排序

  1. 最小的右边界可以穿过当前的气球以及所有左边界小于等于该边界的气球
  2. 没有被穿过的气球只需要将箭移动到剩余最小的右边界
  3. 每移动一次箭需要的箭的数量就增加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
class Solution {
    public int findMinArrowShots(int[][] points) {
        if (points.length == 0 || points[0].length == 0) {
            return 0;
        }
        Arrays.sort(points, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return Integer.compare(o1[1],o2[1]);
            }
        });
        int pos = points[0][1];//最小的右边界
        int ans = 1;
        for (int[] balloon: points) {
            if (balloon[0] > pos) {//这个气球无法在本次中被穿破
                pos = balloon[1];//移动到下一个最小的右边界
                ++ans;
            }
        }
        //System.out.println(ans);
        return ans;
    }
}

展开全文 >>

子集

78. 子集

难度中等1159

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

示例 1：

1
2
输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

示例 2：

1
2
输入：nums = [0]
输出：[[],[0]]

提示：

  • 1 <= nums.length <= 10
  • -10 <= nums[i] <= 10
  • nums 中的所有元素 互不相同

位运算

例子[5,2,9]

0/1 序列 子集 0/10/1 序列对应的二进制数
000000 {} 0
001001 {9} 1
010010 {2} 2
011011 {2,9} 3
100100 {5} 4
101101 {5,9} 5
110110 {5,2} 6
111111 {5,2,9} 7 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    List<Integer> t = new ArrayList<Integer>();
    List<List<Integer>> ans = new ArrayList<List<Integer>>();

    public List<List<Integer>> subsets(int[] nums) {
        int n = nums.length;
        for (int mask = 0; mask < (1 << n); ++mask) {
            t.clear();
            for (int i = 0; i < n; ++i) {
                if ((mask & (1 << i)) != 0) {
                    t.add(nums[i]);
                }
            }
            ans.add(new ArrayList<Integer>(t));
        }
        return ans;
    }
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/subsets/solution/zi-ji-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
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
class Solution {
    private int arr[] = null;
    public List<List<Integer>> subsets(int[] nums) {
         arr = nums;
        for (int i = 0; i < nums.length; i++) {
            List<List<Integer>> res = combine(nums.length, i);
        }
        List<Integer> allTemp = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            allTemp.add(nums[i]);
        }
        res.add(allTemp);
        res.add(new ArrayList<>());
        return res;
    }

    List<List<Integer>> res = new ArrayList<List<Integer>>();
    List<Integer> temp = new ArrayList<Integer>();

    public List<List<Integer>> combine(int n, int k) {
        if (n < 1 || k == 0) {
            return res;
        }
        dfs(n, k, 0);
        return res;
    }

    private void dfs(int n, int k, int start) {
        if (k == 0) {
            res.add(new ArrayList<Integer>(temp));
            return;
        }
        for (int i = start + 1; i <= n; ++i) {
            if (n - i < k - 1) {
                break;
            }
            temp.add(arr[i - 1]);
            dfs(n, k - 1, i);
            temp.remove(temp.size() - 1);
        }
    }
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/subsets/solution/zi-ji-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

展开全文 >>

有效的字母异位词 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

示例 1:

输入: s = "anagram", t = "nagaram"
输出: true
示例 2:

输入: s = "rat", t = "car"
输出: false
说明:
你可以假设字符串只包含小写字母。

进阶:
如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？

通过次数164,990提交次数263,489

哈希表方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }
        int[] alphabet1 = new int[26];
        int[] alphabet2 = new int[26];
        for (int i = 0; i < s.length(); i++) {
            int index1 = s.charAt(i) - 'a';
            alphabet1[index1]++;
            int index2 = t.charAt(i) - 'a';
            alphabet2[index2]++;
        }
        for (int i = 0; i < 26; i++) {
            if (alphabet1[i] != alphabet2[i]) {
                return false;
            }
        }
        return true;
    }
}

展开全文 >>

不同路径2

63. 不同路径 II

难度中等491

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

img

网格中的障碍物和空位置分别用 1 和 0 来表示。

示例 1：

img

1
2
3
4
5
6
7
输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出：2
解释：
3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右

示例 2：

img

1
2
输入：obstacleGrid = [[0,1],[0,0]]
输出：1

提示：

  • m == obstacleGrid.length
  • n == obstacleGrid[i].length
  • 1 <= m, n <= 100
  • obstacleGrid[i][j] 为 0 或 1

动态规划

  • 如果在边缘有阻碍，那么改阻碍后面的都不可达

  • 如果当前有障碍，那么当前的值是0

  • 其余的是从i-1,j-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
38
39
40
41
42
43
44
45
class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int dp[][] = new int[obstacleGrid.length][obstacleGrid[0].length];
        boolean iFlag = false;
        boolean jFlag = false;
        for (int i = 0; i < obstacleGrid.length; i++) {
            for (int j = 0; j < obstacleGrid[0].length; j++) {
                if (i == 0 || j == 0) {//如果在边缘有阻碍，那么改阻碍后面的都不可达
                    if (i == 0) {
                        if (obstacleGrid[i][j] == 1) {
                            dp[i][j] = 0;
                            iFlag = true;
                        }
                        if (iFlag == false) {
                            dp[i][j] = 1;
                        } else {
                            dp[i][j] = 0;
                        }

                    }
                    if (j == 0) {
                        if (obstacleGrid[i][j] == 1) {
                            dp[i][j] = 0;
                            jFlag = true;
                        }
                        if (jFlag == false) {
                            dp[i][j] = 1;
                        } else {
                            dp[i][j] = 0;
                        }
                    }

                } else {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                    if (obstacleGrid[i][j] == 1) {
                        dp[i][j] = 0;
                    }
                }
            }
        }

        return dp[obstacleGrid.length - 1][obstacleGrid[0].length - 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
class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int n = obstacleGrid.length, m = obstacleGrid[0].length;
        int[] f = new int[m];

        f[0] = obstacleGrid[0][0] == 0 ? 1 : 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (obstacleGrid[i][j] == 1) {
                    f[j] = 0;
                    continue;
                }
                if (j - 1 >= 0 && obstacleGrid[i][j - 1] == 0) {
                    f[j] += f[j - 1];
                }
            }
        }
        
        return f[m - 1];
    }
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/unique-paths-ii/solution/bu-tong-lu-jing-ii-by-leetcode-solution-2/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

展开全文 >>

不同路径

62. 不同路径

难度：中等

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

示例 1：

img

1
2
输入：m = 3, n = 7
输出：28

示例 2：

1
2
3
4
5
6
7
输入：m = 3, n = 2
输出：3
解释：
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下

示例 3：

1
2
输入：m = 7, n = 3
输出：28

示例 4：

1
2
输入：m = 3, n = 3
输出：6

提示：

  • 1 <= m, n <= 100
  • 题目数据保证答案小于等于 2 * 109

暴力递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    private int count=0;
    public int uniquePaths(int m, int n) {
        deep(m, n, 0, 0);
        return count;
    }
    public void deep(int m, int n, int x, int y) {
        if (x == m - 1 && y == n - 1) {
            count++;
        } else {
            if (x < m - 1) {
                deep(m, n, x + 1, y);
            }
            if (y < n - 1) {
                deep(m, n, x, y + 1);
            }
        }
    }
}

动态规划

  • 第一行和第一列的可达数量是1
  • 其余的是从i-1,j-1到来的
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 int uniquePaths(int m, int n) {
        if (m == 0 || n == 0) {
            return 0;
        }
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) {
            dp[i][0] = 1;
        }
        for (int i = 0; i < n; i++) {
            dp[0][i] = 1;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];

            }
        }
        return dp[m - 1][n - 1];
    }
}

动态规划

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

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 || j == 0)
                    dp[i][j] = 1;//边上的格子只有一个可到达路径
                else {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];//每个格子可到达的所有路线的数目等于它的左边的格子和上边的格子的道路的数目之和
                }
            }
        }
        return dp[m - 1][n - 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
给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

进阶：
你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？
 

示例 1：
输入：head = [4,2,1,3]
输出：[1,2,3,4]

示例 2：
输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]

示例 3：
输入：head = []
输出：[]
 
提示：
链表中节点的数目在范围 [0, 5 * 104] 内
-105 <= Node.val <= 105

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sort-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

插入排序

时间复杂度不符合要求

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null) {
            return head;
        }
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;
        ListNode lastSorted = head, curr = head.next;
        while (curr != null) {
            if (lastSorted.val <= curr.val) {
                lastSorted = lastSorted.next;
            } else {
                ListNode prev = dummyHead;
                while (prev.next.val <= curr.val) {
                    prev = prev.next;
                }
                lastSorted.next = curr.next;
                curr.next = prev.next;
                prev.next = curr;
            }
            curr = lastSorted.next;
        }
        return dummyHead.next;
    }
}

自顶向下的归并排序

空间复杂度不符合要求

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
class Solution {
    public ListNode sortList(ListNode head) {
        return sortList(head, null);
    }

    public ListNode sortList(ListNode head, ListNode tail) {        //递归划分与排序
        if (head == null) {
            return head;
        }
        if (head.next == tail) {
            head.next = null;
            return head;
        }
        ListNode slow = head, fast = head;                          //两个指针，慢指针一次走一步，快指针一次走两步，等到快指针走到连边的尾部，慢指针走到链表的中间
        while (fast != tail) {
            slow = slow.next;
            fast = fast.next;
            if (fast != tail) {
                fast = fast.next;
            }
        }
        ListNode mid = slow;                                        //慢指针走到中间
        ListNode list1 = sortList(head, mid);                       //对左半部分链表划分排序
        ListNode list2 = sortList(mid, tail);                       //对右半部分链表划分排序
        ListNode sorted = merge(list1, list2);                      //合并两个子链表
        return sorted;
    }

    public ListNode merge(ListNode head1, ListNode head2) {
        ListNode dummyHead = new ListNode(0);
        ListNode temp = dummyHead, temp1 = head1, temp2 = head2;
        while (temp1 != null && temp2 != null) {                    //两个子链表都没有遍历到底时
            if (temp1.val <= temp2.val) {                           //如果第一个链表的当前值小于第二个链表的当前值，有序链表加入第一个链表的当前值
                temp.next = temp1;
                temp1 = temp1.next;
            } else {                                                //有序链表加入第二个链表的当前值
                temp.next = temp2;
                temp2 = temp2.next;
            }
            temp = temp.next;
        }
        //将多出的一个加入到链表末尾
        if (temp1 != null) {
            temp.next = temp1;
        } else if (temp2 != null) {
            temp.next = temp2;
        }
        return dummyHead.next;
    }
}

自底向上的归并排序

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
54
55
56
57
58
59
60
61
62
63
64
65

class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null) {
            return head;
        }
        int length = 0;
        ListNode node = head;
        while (node != null) {                                              // 统计链表的长度
            length++;
            node = node.next;
        }

        ListNode dummyHead = new ListNode(0, head);
        for (int subLength = 1; subLength < length; subLength <<= 1) {      // subLength <<= 1是sublength*2
            ListNode prev = dummyHead, curr = dummyHead.next;
            while (curr != null) {
                ListNode head1 = curr;
                for (int i = 1; i < subLength && curr.next != null; i++) {  // 划分subLength长度
                    curr = curr.next;
                }
                ListNode head2 = curr.next;
                curr.next = null;
                curr = head2;
                for (int i = 1; i < subLength && curr != null && curr.next != null; i++) {// 在上个基础上划分subLength长度
                    curr = curr.next;
                }
                ListNode next = null;
                if (curr != null) {                                                       //对剩余的排序
                    next = curr.next;
                    curr.next = null;
                }
                ListNode merged = merge(head1, head2);                                    //归并排序两个链表
                prev.next = merged;
                while (prev.next != null) {
                    prev = prev.next;
                }
                curr = next;
            }
        }
        return dummyHead.next;
    }

    public ListNode merge(ListNode head1, ListNode head2) {                              //归并两个链表
        ListNode dummyHead = new ListNode(0);
        ListNode temp = dummyHead, temp1 = head1, temp2 = head2;
        while (temp1 != null && temp2 != null) {
            if (temp1.val <= temp2.val) {
                temp.next = temp1;
                temp1 = temp1.next;
            } else {
                temp.next = temp2;
                temp2 = temp2.next;
            }
            temp = temp.next;
        }
        if (temp1 != null) {
            temp.next = temp1;
        } else if (temp2 != null) {
            temp.next = temp2;
        }
        return dummyHead.next;
    }
}

参考文献

作者：LeetCode-Solution来源：力扣（LeetCode）著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

1
2
3
4
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/sort-list/solution/pai-xu-lian-biao-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

展开全文 >>

颜色分类 

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
给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

 

进阶：

你可以不使用代码库中的排序函数来解决这道题吗？
你能想出一个仅使用常数空间的一趟扫描算法吗？
 

示例 1：

输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]
示例 2：

输入：nums = [2,0,1]
输出：[0,1,2]
示例 3：

输入：nums = [0]
输出：[0]
示例 4：

输入：nums = [1]
输出：[1]
 

提示：

n == nums.length
1 <= n <= 300
nums[i] 为 0、1 或 2
通过次数151,604提交次数266,612

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sort-colors
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

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 void sortColors(int[] nums) {
        int n = nums.length;
        int p0 = 0, p1 = 0;
        for (int i = 0; i < n; ++i) {
            if (nums[i] == 1) {
                swap(i, p1, nums);
                ++p1;
            } else if (nums[i] == 0) {
                swap(i, p0, nums);
                if (p0 < p1) {              //p0后面有p1,会把p1换出去，所以要换回p1最后的位置
                    swap(i, p1, nums);
                }
                ++p0;
                ++p1;
            }
        }
    }
    
    public void swap(int index1, int index2, int[] nums) {
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    }
}

展开全文 >>

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

我是一只<br>又水又笨又菜的<br>菜狗子<br>希望有一天被领走