下降路径最小和 

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
给定一个方形整数数组 A，我们想要得到通过 A 的下降路径的最小和。

下降路径可以从第一行中的任何元素开始，并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列。

 

示例：

输入：[[1,2,3],[4,5,6],[7,8,9]]
输出：12
解释：
可能的下降路径有：
[1,4,7], [1,4,8], [1,5,7], [1,5,8], [1,5,9]
[2,4,7], [2,4,8], [2,5,7], [2,5,8], [2,5,9], [2,6,8], [2,6,9]
[3,5,7], [3,5,8], [3,5,9], [3,6,8], [3,6,9]
和最小的下降路径是 [1,4,7]，所以答案是 12。

 

提示：

1 <= A.length == A[0].length <= 100
-100 <= A[i][j] <= 100
通过次数8,626提交次数13,883

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-falling-path-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
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 minFallingPathSum(int[][] A) {
        int N = A.length;
        for (int r = N - 2; r >= 0; --r) {
            for (int c = 0; c < N; ++c) {
                // best = min(A[r+1][c-1], A[r+1][c], A[r+1][c+1])
                int best = A[r + 1][c];
                if (c > 0)
                    best = Math.min(best, A[r + 1][c - 1]);
                if (c + 1 < N)
                    best = Math.min(best, A[r + 1] [c + 1]);
                A[r][c] += best;
            }
        }

        int ans = Integer.MAX_VALUE;
        for (int x : A[0])
            ans = Math.min(ans, x);
        return ans;    
    }

}

展开全文 >>

最大平均值和的分组 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
我们将给定的数组 A 分成 K 个相邻的非空子数组 ，我们的分数由每个子数组内的平均值的总和构成。计算我们所能得到的最大分数是多少。

注意我们必须使用 A 数组中的每一个数进行分组，并且分数不一定需要是整数。

示例:
输入: 
A = [9,1,2,3,9]
K = 3
输出: 20
解释: 
A 的最优分组是[9], [1, 2, 3], [9]. 得到的分数是 9 + (1 + 2 + 3) / 3 + 9 = 20.
我们也可以把 A 分成[9, 1], [2], [3, 9].
这样的分组得到的分数为 5 + 2 + 6 = 13, 但不是最大值.
说明:

1 <= A.length <= 100.
1 <= A[i] <= 10000.
1 <= K <= A.length.
答案误差在 10^-6 内被视为是正确的。
通过次数4,206提交次数8,032

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/largest-sum-of-averages
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
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
class Solution{
    //最后一个数为止分成K个连续非空子数组的子数组的平均值的和的最大值（用xxx代指）
    //不能改变数组内元素的顺序
    public static double largestSumOfAverages(int[] A, int K) {
        int len = A.length;
        double[] sums = new double[len + 1];
        for (int i = 0; i < len; i++) {
            sums[i + 1] = sums[i] + A[i];//计算从0开始的区间和
        }

        double dp[] = new double[len];
        // 第一次dp， dp[i]表示A数组中下标i~(N - 1)分为一个非空连续子数组的平均值
        for (int i = 0; i < len; i++) {
            dp[i] = (sums[len] - sums[i]) / (len - i);//计算区间（i到len）之间的平均值
        }
        // 第2次到第K次dp,   k = 1，代表第二次，k = 2，代表第三次，以此类推，k = K - 1代表第K次dp
        // 第k + 1次dp的结果dp[i]就是A数组中从下标i开始到N-1结束分为k+1个非空连续子数组的xxx值
        for (int k = 0; k < K - 1; k++) {
            // 先把i固定，j变化作为分隔点
            // 分隔一次i~(N - 1)变为2个连续数组
            // 分隔两次i~N-1变为3个连续数组
            // 分隔K- 1次i~(N -1)变为K个连续数组
            // 这里有一点很好证明:一个数组分割后，他的xxx值一定比不分割要大，这是这里dp能求到正确值的前提条件
            for (int i = 0; i < len; i++) {
                for (int j = i + 1; j < len; j++) {
                    dp[i] = Math.max(dp[i], (sums[j] - sums[i]) / (j - i) + dp[j]);//假设i是最终结果，j是中间的某个结果，要想从j得到i，需要遍历j到i中间的所有结果，寻找最大的dp[j]+j到i之间区间的平均值
                }
            }
        }
        return dp[0];
    }
}

参考文献

codeBrick
官方题解

展开全文 >>

K站中转内最便宜的航班 

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

现在给定所有的城市和航班，以及出发城市 src 和目的地 dst，你的任务是找到从 src 到 dst 最多经过 k 站中转的最便宜的价格。 如果没有这样的路线，则输出 -1。

 

示例 1：

输入: 
n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]
src = 0, dst = 2, k = 1
输出: 200
解释: 
城市航班图如下
           0
         /  \
  100   /    \ 500
       /      \
      /  100   \
    1  -------- 2

从城市 0 到城市 2 在 1 站中转以内的最便宜价格是 200，如图中红色所示。

示例 2：

输入: 
n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]
src = 0, dst = 2, k = 0
输出: 500
解释: 
城市航班图如下
           0
         /  \
  100   /    \ 500
       /      \
      /  100   \
    1  -------- 2

从城市 0 到城市 2 在 0 站中转以内的最便宜价格是 500，如图中蓝色所示。

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

动态规划

计算到各节点的最短距离

假设 pre[node] 是到经过 T 个节点到达目的节点 node 的最短距离，然后求解经过 T+1 个节点到达目的节点的最短距离。对于每一条连接城市 u 和 v，成本为 w的航线，更新后的最短距离为 dis[v] = min(dis[v], pre[u] + w)。

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 {
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) {

        int INF = Integer.MAX_VALUE / 2;
        int[][] dp = new int[K + 1][n];
        for (int i = 0; i <= K; ++i) {
            Arrays.fill(dp[i], INF);
        }
        //初始化src可直达的班次
        for (int[] flight : flights) {
            if (flight[0] == src) {
                dp[0][flight[1]] = flight[2];
            }
        }
        //初始化数组中`dst == src`的行
        for (int i = 0; i <= K; i++) {
            dp[i][src] = 0;
        }

        for (int i = 1; i <= K; i++) {
            for (int[] flight : flights) {
                // 到flight[1]城市的cost=直达该城市的路线的cost和通过flight[0]+当前cost的最小值
                // 也就是选当前路线替换已有的路线和不选当前路线替换已有路线的最小值
                dp[i][flight[1]] = Math.min(dp[i][flight[1]], dp[i - 1][flight[0]] + flight[2]);
            }
        }
        return dp[K][dst] < INF ? dp[K][dst] : -1;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) {
        int[][] dist = new int[2][n];
        int INF = Integer.MAX_VALUE / 2;
        Arrays.fill(dist[0], INF);
        Arrays.fill(dist[1], INF);
        dist[0][src] = dist[1][src] = 0;

        for (int i = 0; i <= K; ++i)
            for (int[] edge: flights)//edge[1]是destination，edge[0]是当前节点的sorce，edge[2]是cost
                //i&1在i是奇数时为1，在i是偶数时为0，~对前面的结果取反
                dist[i&1][edge[1]] = Math.min(dist[i&1][edge[1]], dist[~i&1][edge[0]] + edge[2]);

        return dist[K&1][dst] < INF ? dist[K&1][dst] : -1;
    }
}

Dijkstra 算法

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
class Solution {
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) {
        int[][] graph = new int[n][n];
        for (int[] flight: flights)
            graph[flight[0]][flight[1]] = flight[2];//赋值为从i到j的航班的cost

        Map<Integer, Integer> best = new HashMap();

        PriorityQueue<int[]> pq = new PriorityQueue<int[]>((a, b) -> a[0] - b[0]);//利用优先级队列维护花费最低的下一城市
        pq.offer(new int[]{0, 0, src});//第一个是cost，第二个是中转的数量k，第三个是source

        while (!pq.isEmpty()) {
            int[] info = pq.poll();
            int cost = info[0], k = info[1], place = info[2];
            if (k > K+1 || cost > best.getOrDefault(k * 1000 + place, Integer.MAX_VALUE))
                continue;
            if (place == dst)//如果当前节点终点，则返回当前的最小cost
                return cost;

            for (int nei = 0; nei < n; ++nei) 
                if (graph[place][nei] > 0) {//如果可达
                    int newcost = cost + graph[place][nei];
                    if (newcost < best.getOrDefault((k+1) * 1000 + nei, Integer.MAX_VALUE)) {
                        pq.offer(new int[]{newcost, k+1, nei});
                        best.put((k+1) * 1000 + nei, newcost);
                    }
            }
        }

        return -1;
    }
}

Dijkstra最短路径的实现代码

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

//假设起点为src, 终点为dst, 图以二维矩阵的形式存储，若graph[i][j] == 0, 代表i,j不相连    
//visit[i] == 0,代表未访问,visit[0] == -1代表已访问    
public int Dijkstra(int src, int dst, int[][] graph,int[] visit){
    //节点个数        
    int n = graph.length;        
    PriorityQueue<Node> pq = new PriorityQueue<>(new Node());        
    //将起点加入pq        
    pq.add(new Node(src, 0));        
    while (!pq.isEmpty()){            
        Node t = pq.poll();            
        //当前节点是终点，即可返回最短路径            
        if(t.node == dst)                
            return t.cost;            
        //t节点表示还未访问            
        if (visit[t.node]==0){                
            //将节点设置为已访问                
            visit[t.node] = -1;                
            //将当前节点相连且未访问的节点遍历                
            for (int i = 0; i < n; i++) {                    
                if (graph[t.node][i]!=0 && visit[i]==0) {                        
                    pq.add(new Node(i, t.cost + graph[t.node][i]));                    
                }                
            }            
        }        
    }        
    return -1;    
}    
//定义一个存储节点和离起点相应距离的数据结构    
class Node implements Comparator<Node> {        
    public int node;        
    public int cost;
             
    public Node(){}
     
    public Node(int node, int cost){            
        this.node = node;            
        this.cost = cost;        
    }        
    @Override        
    public int compare(Node node1, Node node2){            
        return node1.cost-node2.cost;       
    }    
}

1
2
3
4
作者：LeetCode
链接：https://leetcode-cn.com/problems/cheapest-flights-within-k-stops/solution/k-zhan-zhong-zhuan-nei-zui-bian-yi-de-hang-ban-b-2/
来源：力扣（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
如果一个十进制数字不含任何前导零，且每一位上的数字不是 0 就是 1 ，那么该数字就是一个 十-二进制数 。例如，101 和 1100 都是 十-二进制数，而 112 和 3001 不是。

给你一个表示十进制整数的字符串 n ，返回和为 n 的 十-二进制数 的最少数目。

 

示例 1：

输入：n = "32"
输出：3
解释：10 + 11 + 11 = 32
示例 2：

输入：n = "82734"
输出：8
示例 3：

输入：n = "27346209830709182346"
输出：9
 

提示：

1 <= n.length <= 105
n 仅由数字组成
n 不含任何前导零并总是表示正整数
通过次数3,013提交次数3,417

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

贪心算法

因为数字的每个位都是由0和1组成的，所以要想组成该数字的数字数量最小，那么对于每一位的数字，它不应该有进位，如果有低位的进位，那么可以在高位直接用一个数字代替，因此组成该数字的最小的数字的数量应该取决于该数字中最大的那一位的数值

1
2
3
4
5
6
7
8
9
10
11
class Solution{
    public static int minPartitions(String n) {
        int max = 0;
        for (int i = 0; i < n.length(); i++) {
            max = Math.max(n.charAt(i)-'0', max);
        }

        return max;
    }
}

暴力解法（超时，不能保证正确性）

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
class Solution{
    public static int minPartitions(String n) {
        backtrack(n, "", 1, 1);
        return minDeep;
    }

    static char[] val = new char[]{'0', '1'};
    static int minDeep = Integer.MAX_VALUE;

    public static void backtrack(String n, String sum, int deep, int index) {
        if (sum.equals(n)) {
            minDeep = Math.min(minDeep, deep);
        } else {
            if (isGt(sum, n)) {
                return;
            }
            StringBuilder bd = new StringBuilder();
            bd.append(1);
            for (int i = index; i <= n.length(); i++) {
                for (int j = 1; j < i; j++) {
                    bd.append('1');
                }
                for (int j = i; j < n.length(); j++) {
                    bd.append('0');
                }
                String cur = bd.toString();
                sum = calSum(sum, cur);
                backtrack(n, sum, deep + 1, index);
                index++;
                bd.delete(1, bd.length());
            }

        }
    }

    public static boolean isGt(String s1, String s2) {
        if (s1.length() > s2.length() || (s1.length() == s2.length() && s1.charAt(0) > s2.charAt(0))) {
            return true;
        }
        return false;
    }

    public static String calSum(String last, String cur) {
        if (last.equals("")) {
            return cur;
        }
        int length1 = last.length() - 1;
        int length2 = cur.length() - 1;

        int flag = 0;
        StringBuilder bd = new StringBuilder();
        int minLen = Math.min(length1, length2);
        while (minLen >= 0) {
            int val1 = last.charAt(length1) - '0';
            int val2 = cur.charAt(length2) - '0';
            int sum = val1 + val2 + flag;
            if (sum > 9) {
                sum = sum - 10;
                flag = 1;
            } else {
                flag = 0;
            }
            bd.append(sum);
            minLen--;
            length1--;
            length2--;
        }

        while (length1 >= 0) {
            if (flag > 0) {
                int val1 = last.charAt(length1) - '0';
                int sum = val1 + flag;
                if (sum > 9) {
                    sum = sum - 10;
                    flag = 1;
                } else {
                    flag = 0;
                }
                bd.append(sum);
            } else {
                bd.append(last.charAt(length1));
            }
            length1--;
        }
        while (length2 >= 0) {
            if (flag > 0) {
                int val2 = cur.charAt(length2) - '0';
                int sum = val2 + flag;
                if (sum > 9) {
                    sum = sum - 10;
                    flag = 1;
                } else {
                    flag = 0;
                }
                bd.append(sum);
            } else {
                bd.append(last.charAt(length2));
            }
            length2--;
        }
        return bd.reverse().toString();
    }
}

展开全文 >>

石子游戏3 

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
石子游戏中，爱丽丝和鲍勃轮流进行自己的回合，爱丽丝先开始 。

有 n 块石子排成一排。每个玩家的回合中，可以从行中 移除 最左边的石头或最右边的石头，并获得与该行中剩余石头值之 和 相等的得分。当没有石头可移除时，得分较高者获胜。

鲍勃发现他总是输掉游戏（可怜的鲍勃，他总是输），所以他决定尽力 减小得分的差值 。爱丽丝的目标是最大限度地 扩大得分的差值 。

给你一个整数数组 stones ，其中 stones[i] 表示 从左边开始 的第 i 个石头的值，如果爱丽丝和鲍勃都 发挥出最佳水平 ，请返回他们 得分的差值 。

 

示例 1：

输入：stones = [5,3,1,4,2]
输出：6
解释：
- 爱丽丝移除 2 ，得分 5 + 3 + 1 + 4 = 13 。游戏情况：爱丽丝 = 13 ，鲍勃 = 0 ，石子 = [5,3,1,4] 。
- 鲍勃移除 5 ，得分 3 + 1 + 4 = 8 。游戏情况：爱丽丝 = 13 ，鲍勃 = 8 ，石子 = [3,1,4] 。
- 爱丽丝移除 3 ，得分 1 + 4 = 5 。游戏情况：爱丽丝 = 18 ，鲍勃 = 8 ，石子 = [1,4] 。
- 鲍勃移除 1 ，得分 4 。游戏情况：爱丽丝 = 18 ，鲍勃 = 12 ，石子 = [4] 。
- 爱丽丝移除 4 ，得分 0 。游戏情况：爱丽丝 = 18 ，鲍勃 = 12 ，石子 = [] 。
得分的差值 18 - 12 = 6 。
示例 2：

输入：stones = [7,90,5,1,100,10,10,2]
输出：122
 

提示：

n == stones.length
2 <= n <= 1000
1 <= stones[i] <= 1000
通过次数953提交次数3,127

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/stone-game-vii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
无论是B想要缩短价值差，或者A想要扩大价值差，其本质就是这次取法能得到与对手最大的价值差
所以这次DP也用类似的状态。

又因为每次删掉之后的得分是区间累加和，所以又涉及到区间和，所以需要维护
dp[i][j] : 表示从 i 到 j 的区间和
res[i][j]:表示轮到这一个人选时，石头剩下 i 到 j ，他能获得的最大价值差

接下来来推状态转移方程：

最初始的时候：i == j ，res[i][j] = 0，因为删了之后没得取
当 j - i == 1时，res[i][j] = max(stones[i], stones[j])，因为我要利益最大化，我肯定删掉一个较小的石头，取最大得分，反正下一个人是没分的
当j - i > 1时， res[i][j] = max(dp[i + 1][j] - res[i + 1][j], dp[i][j - 1] - res[i][j - 1]),
        本次选取，我只能从左端删或者从右端删，
从左端删，在剩下的石头中（不考虑前面的），下一个人与我的得分差值是 res[i + 1][j]
从右端删，在剩下的石头中（不考虑前面的），下一个人与我的得分差值是 res[i][j - 1]
所以我考虑本次差值最大，那么本次删掉的时候我能得到的最大差值应该是删掉一个之后得到的区间和，减去对手下次选时与我的差值
所以转移方程为： res[i][j] = max(dp[i + 1][j] - res[i + 1][j], dp[i][j - 1] - res[i][j - 1])
最后返回res[0][n - 1]即为我们所需的答案，表示剩下的石头为0到n - 1，Alice能取得的最大价值差

作者：spacex-1
链接：https://leetcode-cn.com/problems/stone-game-vii/solution/c-qu-jian-dp-si-lu-zheng-li-guo-cheng-by-3h0l/
来源：力扣（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
43
44
45
46
47
48
49
    public static int stoneGameVII(int[] stones) {

//        无论是B想要缩短价值差，或者A想要扩大价值差，其本质就是这次取法能得到与对手最大的价值差
//        所以这次DP也用类似的状态。
//
//        又因为每次删掉之后的得分是区间累加和，所以又涉及到区间和，所以需要维护
//        dp[i][j] : 表示从 i 到 j 的区间和
//        res[i][j]:表示轮到这一个人选时，石头剩下 i 到 j ，他能获得的最大价值差
//
//        接下来来推状态转移方程：
//
//        最初始的时候：i == j ，res[i][j] = 0，因为删了之后没得取
//        当 j - i == 1时，res[i][j] = max(stones[i], stones[j])，因为我要利益最大化，我肯定删掉一个较小的石头，取最大得分，反正下一个人是没分的
//        当j - i > 1时， res[i][j] = max(dp[i + 1][j] - res[i + 1][j], dp[i][j - 1] - res[i][j - 1]),
//                本次选取，我只能从左端删或者从右端删，
//        从左端删，在剩下的石头中（不考虑前面的），下一个人与我的得分差值是 res[i + 1][j]
//        从右端删，在剩下的石头中（不考虑前面的），下一个人与我的得分差值是 res[i][j - 1]
//        所以我考虑本次差值最大，那么本次删掉的时候我能得到的最大差值应该是删掉一个之后得到的区间和，减去对手下次选时与我的差值
//        所以转移方程为： res[i][j] = max(dp[i + 1][j] - res[i + 1][j], dp[i][j - 1] - res[i][j - 1])
//        最后返回res[0][n - 1]即为我们所需的答案，表示剩下的石头为0到n - 1，Alice能取得的最大价值差
//
//        作者：spacex-1
//        链接：https://leetcode-cn.com/problems/stone-game-vii/solution/c-qu-jian-dp-si-lu-zheng-li-guo-cheng-by-3h0l/
//        来源：力扣（LeetCode）
//        著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
        int n = stones.length;

        int[][] dp = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                if (i == j) dp[i][j] = stones[i]; //记录区间和
                else dp[i][j] = stones[j] + dp[i][j - 1];
            }
        }

        int res[][] = new int[n][n];
        for (int i = n - 1; i >= 0; i--) {//左边
            for (int j = i + 1; j < n; j++) {//右边

                //两个人都想使自己的分数与对方的分数的差值最小
                //如果只有两个元素时，那么两个人的最大得分差值应该是最大的那个值
                if (j - i == 1) res[i][j] = Math.max(stones[i], stones[j]);  //状态转移方程
                //如果多余两个元素时，两个人得分的最大差值应该是
                //左边的得分减去左边的最大差值，右边的得分减去右边的最大差值
                else res[i][j] = Math.max(dp[i + 1][j] - res[i + 1][j], dp[i][j - 1] - res[i][j - 1]);
            }
        }
        return res[0][n - 1]; //返回A能取的最大和
    }

展开全文 >>

二叉树的锯齿形层次遍历 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

例如：
给定二叉树 [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7
返回锯齿形层次遍历如下：

[
  [3],
  [20,9],
  [15,7]
]
通过次数82,729提交次数149,825

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

在java中使用双端队列，可以从头或者尾部取出或者加入元素，从而实现从前往后和从后往前遍历

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        ArrayDeque<TreeNode> treeNodeQueue = new ArrayDeque<>();
        List<List<Integer>> resultList = new ArrayList<>();
        if (root != null) {
            treeNodeQueue.add(root);
        }
        boolean flag = false;
        while (!treeNodeQueue.isEmpty()) {
            List<Integer> res = new ArrayList<>();
            int num = treeNodeQueue.size();

            if (!flag) {//从左往右
                flag = !flag;
                for (int i = 0; i < num; i++) {

                    TreeNode node = treeNodeQueue.poll();
                    res.add(node.val);
                    //因为是从后往前遍历因此需要先把右子树加进去
                    if (node.left != null) {
                        treeNodeQueue.offer(node.left);
                    }
                    if (node.right != null) {
                        treeNodeQueue.offer(node.right);
                    }
                }


            } else {//从右往左
                flag = !flag;

                for (int i = 0; i < num; i++) {
                    TreeNode node = treeNodeQueue.removeLast();

                    res.add(node.val);
                    if (node.right != null) {
                        treeNodeQueue.addFirst(node.right);
                    }
                    if (node.left != null) {
                        treeNodeQueue.addFirst(node.left);
                    }

                }
            }
            
            resultList.add(res);

        }
        return resultList;
    }
}

使用一个空节点作为每一层遍历结束的标志

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
  public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    if (root == null) {
      return new ArrayList<List<Integer>>();
    }

    List<List<Integer>> results = new ArrayList<List<Integer>>();

    // add the root element with a delimiter to kick off the BFS loop
    LinkedList<TreeNode> node_queue = new LinkedList<TreeNode>();
    node_queue.addLast(root);
    node_queue.addLast(null);//遇到空节点，结束本层遍历

    LinkedList<Integer> level_list = new LinkedList<Integer>();
    boolean is_order_left = true;

    while (node_queue.size() > 0) {//在遍历时不对TreeNode加入队列的顺序做修改，只是把遍历的结果插入结果列表的顺序进行了修改
      TreeNode curr_node = node_queue.pollFirst();
      if (curr_node != null) {//本层没有结束
        if (is_order_left)
          level_list.addLast(curr_node.val);
        else
          level_list.addFirst(curr_node.val);

        //以正常的顺序将节点加入队列
        if (curr_node.left != null)
          node_queue.addLast(curr_node.left);
        if (curr_node.right != null)
          node_queue.addLast(curr_node.right);

      } else {//遇到空节点，本层的遍历结束
        // we finish the scan of one level
        results.add(level_list);
        level_list = new LinkedList<Integer>();
        // prepare for the next level
        if (node_queue.size() > 0)
          node_queue.addLast(null);
        is_order_left = !is_order_left;//锯齿形的标志
      }
    }
    return results;
  }
}

时间复杂度和空间复杂度都是O(N)

深度优先遍历方式

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
  protected void DFS(TreeNode node, int level, List<List<Integer>> results) {
    if (level >= results.size()) {//如果在当前的层还没有遍历过，也就是当前层的List的还没有初始化，初始化一个List
      LinkedList<Integer> newLevel = new LinkedList<Integer>();//每一层的列表
      newLevel.add(node.val);
      results.add(newLevel);//最终的结果列表
    } else {
      if (level % 2 == 0)
        results.get(level).add(node.val);//加到尾部
      else
        results.get(level).add(0, node.val);//加到头部
    }

    if (node.left != null) DFS(node.left, level + 1, results);//遍历左子树
    if (node.right != null) DFS(node.right, level + 1, results);//遍历右子树
  }

  public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    if (root == null) {
      return new ArrayList<List<Integer>>();
    }
    List<List<Integer>> results = new ArrayList<List<Integer>>();
    DFS(root, 0, results);
    return results;
  }
}

时间复杂度O(N),空间复杂度O(H)，其中H是树的高度，包含N个节点的二叉树的高度大约为log（N）(以2为底)

参考文献

1
2
3
4
作者：LeetCode
链接：https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal/solution/er-cha-shu-de-ju-chi-xing-ceng-ci-bian-li-by-leetc/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

展开全文 >>

存在重复元素

217. 存在重复元素

难度：简单

给定一个整数数组，判断是否存在重复元素。

如果存在一值在数组中出现至少两次，函数返回 true 。如果数组中每个元素都不相同，则返回 false 。

示例 1:

1
2
输入: [1,2,3,1]
输出: true

示例 2:

1
2
输入: [1,2,3,4]
输出: false

示例 3:

1
2
输入: [1,1,1,3,3,4,3,2,4,2]
输出: true

哈希表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public boolean containsDuplicate(int[] nums) {
        HashMap<Integer, Integer> map = new HashMap<>();

        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
        }

        for (int i = 0; i < nums.length; i++) {
            if (map.get(nums[i]) > 1) {
                return true;
            }
        }
        return false;
    }
}

官方哈希表

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public boolean containsDuplicate(int[] nums) {
        Set<Integer> set = new HashSet<Integer>();
        for (int x : nums) {
            if (!set.add(x)) {
                return true;
            }
        }
        return false;
    }
}

排序

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public boolean containsDuplicate(int[] nums) {
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[i] == nums[i + 1]) {
                return true;
            }
        }
        return false;
    }
}

官方排序

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public boolean containsDuplicate(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        for (int i = 0; i < n - 1; i++) {
            if (nums[i] == nums[i + 1]) {
                return true;
            }
        }
        return false;
    }
}

参考文献

1
2
3
4
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/contains-duplicate/solution/cun-zai-zhong-fu-yuan-su-by-leetcode-sol-iedd/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

展开全文 >>

统计全为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
给你一个 m * n 的矩阵，矩阵中的元素不是 0 就是 1，请你统计并返回其中完全由 1 组成的 正方形 子矩阵的个数。

示例 1：

输入：matrix =
[
  [0,1,1,1],
  [1,1,1,1],
  [0,1,1,1]
]
输出：15
解释： 
边长为 1 的正方形有 10 个。
边长为 2 的正方形有 4 个。
边长为 3 的正方形有 1 个。
正方形的总数 = 10 + 4 + 1 = 15.

示例 2：

输入：matrix = 
[
  [1,0,1],
  [1,1,0],
  [1,1,0]
]
输出：7
解释：
边长为 1 的正方形有 6 个。 
边长为 2 的正方形有 1 个。
正方形的总数 = 6 + 1 = 7.
 

提示：

1 <= arr.length <= 300
1 <= arr[0].length <= 300
0 <= arr[i][j] <= 1
通过次数12,484提交次数17,559

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

暴力求解

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 int countSquares(int[][] matrix) {

        int h = matrix.length;
        int w = matrix[0].length;

        int max = Math.min(h, w);
        int count = 0;
        for (int y = 0; y < h; y++) {
            for (int x = 0; x < w; x++) {
                for (int i = 1; i <= max; i++) {
                    boolean flag = isSqare(matrix, y, x, y + i, x + i, h, w);
                    if (flag) {
                        // System.out.println(y + "\t" + x + "\t" + i);
                        count++;
                    }
                }
            }

        }
        return count;

    }

    //判断矩形里面是不是全是1
    public boolean isSqare(int[][] matrix, int y1, int x1, int y2, int x2, int h, int w) {
        if (y2 > h || x2 > w) {
            return false;
        } else {
            for (int i = y1; i < y2; i++) {
                for (int j = x1; j < x2; j++) {
                    if (matrix[i][j] == 0) {
                        return false;
                    }
                }
            }
        }
        return true;
    }
}

1
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
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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

在一个大小在 (0, 0) 到 (N-1, N-1) 的2D网格 grid 中，除了在 mines 中给出的单元为 0，其他每个单元都是 1。网格中包含 1 的最大的轴对齐加号标志是多少阶？返回加号标志的阶数。如果未找到加号标志，则返回 0。

一个 k" 阶由 1 组成的“轴对称”加号标志具有中心网格  grid[x][y] = 1 ，以及4个从中心向上、向下、向左、向右延伸，长度为 k-1，由 1 组成的臂。下面给出 k" 阶“轴对称”加号标志的示例。注意，只有加号标志的所有网格要求为 1，别的网格可能为 0 也可能为 1。

 

k 阶轴对称加号标志示例:

阶 1:
000
010
000

阶 2:
00000
00100
01110
00100
00000

阶 3:
0000000
0001000
0001000
0111110
0001000
0001000
0000000
 

示例 1：

输入: N = 5, mines = [[4, 2]]
输出: 2
解释:

11111
11111
11111
11111
11011

在上面的网格中，最大加号标志的阶只能是2。一个标志已在图中标出。
 

示例 2：

输入: N = 2, mines = []
输出: 1
解释:

11
11

没有 2 阶加号标志，有 1 阶加号标志。
 

示例 3：

输入: N = 1, mines = [[0, 0]]
输出: 0
解释:

0

没有加号标志，返回 0 。
 

提示：

整数N 的范围： [1, 500].
mines 的最大长度为 5000.
mines[i] 是长度为2的由2个 [0, N-1] 中的数组成.
(另外,使用 C, C++, 或者 C# 编程将以稍小的时间限制进行​​判断.)
 

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

题目的意思是在一个包含0和1的棋盘中，找出一个由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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
class Solution {
    public int orderOfLargestPlusSign(int N, int[][] mines) {

        int[][] board = new int[N][N];

        for(int i=0;i<N;i++)
            Arrays.fill(board[i], 1);//将棋盘填充1

        for (int i = 0; i < mines.length; i++) {//某些点是0
            int y = mines[i][0];
            int x = mines[i][1];
            board[y][x] = 0;
        }

        
        int max = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {//暴力搜索
                if (board[i][j] != 0) {
                    max = Math.max(max, getMaxStep(board, i, j, N));
                }
            }
        }
        return max;
    }

    //以某个位置为中心点，向四个方向找最大臂展
    public int getMaxStep(int[][] board, int y, int x, int N) {
        int lfc = 0, rtc = 0, upc = 0, dnc = 0;
        for (int i = y; i >= 0; i--) {//上边
            if (i < 0)
                break;
            if (board[i][x] == 1) {
                upc++;
            } else {
                break;
            }
        }

        for (int i = y; i < N; i++) {//下边
            if (board[i][x] == 1) {
                dnc++;
            } else {
                break;
            }
        }

        for (int i = x; i >= 0; i--) {//左边
            if (i < 0)
                break;
            if (board[y][i] == 1) {
                lfc++;
            } else {
                break;
            }

        }

        for (int i = x; i < N; i++) {//右边
            if (board[y][i] == 1) {
                rtc++;
            } else {
                break;
            }
        }

        //最长臂展由最小的那个值决定
        return Math.min(Math.min(lfc, rtc), Math.min(upc, dnc));
    }
}

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

class Solution {
    public int orderOfLargestPlusSign(int N, int[][] mines) {
        Set<Integer> banned = new HashSet();
        int[][] dp = new int[N][N];
        
        for (int[] mine: mines)
            banned.add(mine[0] * N + mine[1]);
        int ans = 0, count;
        
        for (int r = 0; r < N; ++r) {
            count = 0;
            for (int c = 0; c < N; ++c) {//从左往右
                count = banned.contains(r*N + c) ? 0 : count + 1;
                dp[r][c] = count;
            }
            
            count = 0;
            for (int c = N-1; c >= 0; --c) {//从右往左
                count = banned.contains(r*N + c) ? 0 : count + 1;
                dp[r][c] = Math.min(dp[r][c], count);//取决于最小的那个
            }
        }
        
        for (int c = 0; c < N; ++c) {
            count = 0;
            for (int r = 0; r < N; ++r) {//从上往下
                count = banned.contains(r*N + c) ? 0 : count + 1;
                dp[r][c] = Math.min(dp[r][c], count);
            }
            
            count = 0;
            for (int r = N-1; r >= 0; --r) {//从下往上
                count = banned.contains(r*N + c) ? 0 : count + 1;
                dp[r][c] = Math.min(dp[r][c], count);
                ans = Math.max(ans, dp[r][c]);//取决于最小的那个
            }
        }
        
        return ans;
    }
}


参考文献

1
2
3
4
作者：LeetCode
链接：https://leetcode-cn.com/problems/largest-plus-sign/solution/zui-da-jia-hao-biao-zhi-by-leetcode/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

展开全文 >>

摆动序列

376. 摆动序列

难度：中等

如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为摆动序列第一个差（如果存在的话）可能是正数或负数。少于两个元素的序列也是摆动序列。

例如， [1,7,4,9,2,5] 是一个摆动序列，因为差值 (6,-3,5,-7,3) 是正负交替出现的。相反, [1,4,7,2,5] 和 [1,7,4,5,5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。

给定一个整数序列，返回作为摆动序列的最长子序列的长度。 通过从原始序列中删除一些（也可以不删除）元素来获得子序列，剩下的元素保持其原始顺序。

示例 1:

1
2
3
输入: [1,7,4,9,2,5]
输出: 6 
解释: 整个序列均为摆动序列。

示例 2:

1
2
3
输入: [1,17,5,10,13,15,10,5,16,8]
输出: 7
解释: 这个序列包含几个长度为 7 摆动序列，其中一个可为[1,17,10,13,10,16,8]。

示例 3:

1
2
输入: [1,2,3,4,5,6,7,8,9]
输出: 2

进阶:
你能否用 O(n) 时间复杂度完成此题?

动态规划

  • up[i] 表示以前 i 个元素中的某一个为结尾的最长的「上升摆动序列」的长度。

  • down[i] 表示以前 i 个元素中的某一个为结尾的最长的「下降摆动序列」的长度。

avatar

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
class Solution {
    public int wiggleMaxLength(int[] nums) {
        int n = nums.length;
        if (n < 2) {
            return n;
        }
        int[] up = new int[n];
        int[] down = new int[n];
        up[0] = down[0] = 1;
        for (int i = 1; i < n; i++) {
            if (nums[i] > nums[i - 1]) {//上升
                up[i] = Math.max(up[i - 1], down[i - 1] + 1);
                //本次是上升，不再下降，所以下降序列的元素个数与前一次相同
                down[i] = down[i - 1];
            } else if (nums[i] < nums[i - 1]) {//下降
                //本次是下降，不再上升，所以上升序列的元素个数与前一次相同
                up[i] = up[i - 1];
                down[i] = Math.max(up[i - 1] + 1, down[i - 1]);
            } else {//相等
                //不升也不降，保持原来各自的元素数量
                up[i] = up[i - 1];
                down[i] = down[i - 1];
            }
        }
        return Math.max(up[n - 1], down[n - 1]);
    }
}

动态规划优化内存

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int wiggleMaxLength(int[] nums) {
        int n = nums.length;
        if (n < 2) {
            return n;
        }
        int up = 1, down = 1;
        for (int i = 1; i < n; i++) {
            if (nums[i] > nums[i - 1]) {
                up = Math.max(up, down + 1);
            } else if (nums[i] < nums[i - 1]) {
                down = Math.max(up + 1, down);
            }
        }
        return Math.max(up, down);
    }
}

优化比较

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int wiggleMaxLength(int[] nums) {
        int n = nums.length;
        if (n < 2) {
            return n;
        }
        int up = 1, down = 1;
        for (int i = 1; i < n; i++) {
            if (nums[i] > nums[i - 1]) {
                up = down + 1;
            } else if (nums[i] < nums[i - 1]) {
                down = up + 1;
            }
        }
        return Math.max(up, down);
    }
}

贪心算法

观察这个序列可以发现，我们不断地交错选择「峰」与「谷」，可以使得该序列尽可能长。

证明非常简单：如果我们选择了一个「过渡元素」，那么在原序列中，这个「过渡元素」的两侧有一个「峰」和一个「谷」。不失一般性，我们假设在原序列中的出现顺序为「峰」「过渡元素」「谷」。如果「过渡元素」在选择的序列中小于其两侧的元素，那么「谷」一定没有在选择的序列中出现，我们可以将「过渡元素」替换成「谷」；同理，如果「过渡元素」在选择的序列中大于其两侧的元素，那么「峰」一定没有在选择的序列中出现，我们可以将「过渡元素」替换成「峰」。这样一来，我们总可以将任意满足要求的序列中的所有「过渡元素」替换成「峰」或「谷」。并且由于我们不断地交错选择「峰」与「谷」的方法就可以满足要求，因此这种选择方法就一定可以达到可选元素数量的最大值。

这样，我们只需要统计该序列中「峰」与「谷」的数量即可（注意序列两端的数也是「峰」或「谷」），但需要注意处理相邻的相同元素。

在实际代码中，我们记录当前序列的上升下降趋势。每次加入一个新元素时，用新的上升下降趋势与之前对比，如果出现了「峰」或「谷」，答案加一，并更新当前序列的上升下降趋势。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int wiggleMaxLength(int[] nums) {
        int n = nums.length;
        if (n < 2) {
            return n;
        }
        int prevdiff = nums[1] - nums[0];
        int ret = prevdiff != 0 ? 2 : 1;
        for (int i = 2; i < n; i++) {
            int diff = nums[i] - nums[i - 1];
            if ((diff > 0 && prevdiff <= 0) || (diff < 0 && prevdiff >= 0)) {
                //diff > 0 && prevdiff <= 0是峰
                //diff < 0 && prevdiff >= 0是谷
                ret++;
                prevdiff = diff;
            }
        }
        return ret;
    }
}

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

展开全文 >>

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>希望有一天被领走