One day a leetcode.

https://leetcode.cn/problemset/all/

1.腐烂的橘子

题目描述

在给定的网格中，每个单元格可以有以下三个值之一：

值 0 代表空单元格；
值 1 代表新鲜橘子；
值 2 代表腐烂的橘子。
每分钟，任何与腐烂的橘子（在 4 个正方向上）相邻的新鲜橘子都会腐烂。

返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1。

输入输出

1
2
3
4
5
6
7
8
9
10
输入：[[2,1,1],[1,1,0],[0,1,1]]
输出：4

输入：[[2,1,1],[0,1,1],[1,0,1]]
输出：-1
解释：左下角的橘子（第 2 行， 第 0 列）永远不会腐烂，因为腐烂只会发生在 4 个正向上。

输入：[[0,2]]
输出：0
解释：因为 0 分钟时已经没有新鲜橘子了，所以答案就是 0 。

大致思路

广度优先搜索(DFS)

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
class Solution {
    public int orangesRotting(int[][] grid) {
        Queue<int[]> queue = new LinkedList<>();
        int e = 0;
        for (int i = 0; i < grid.length; i++)
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 2)
                    queue.offer(new int[]{i, j});
                    //[0, 0]作为队列中的一个元素
                else if (grid[i][j] == 1)
                    e++;
            }
        if (queue.isEmpty() && e > 0)
            return -1;
        if (queue.isEmpty() && e == 0)
            return 0;
        int count = -1;
        int[][] dis = new int[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        while (!queue.isEmpty()) {

            int size = queue.size();
            for (int j = 0; j < size; j++) {

                int[] p = queue.poll();
                //p[0]作为横坐标 p[1]作为纵坐标
                for (int i = 0; i < 4; i++) {
                    int nx = p[0] + dis[i][0], ny = p[1] + dis[i][1];
                    if (check(grid, nx, ny)) {
                        queue.offer(new int[]{nx, ny});
                        grid[nx][ny] = 2;
                        e--;
                    }
                }
            }
            count++;
        }
        return e == 0 ? count : -1;
    }
    
    public boolean check(int[][] grid, int x, int y) {
        return x < grid.length && x >= 0 && y < grid[0].length && y >= 0 && grid[x][y] == 1;
    }

}

2.分糖果II

题目描述

排排坐，分糖果。

我们买了一些糖果 candies，打算把它们分给排好队的 n = num_people 个小朋友。

给第一个小朋友 1 颗糖果，第二个小朋友 2 颗，依此类推，直到给最后一个小朋友 n 颗糖果。

然后，我们再回到队伍的起点，给第一个小朋友 n + 1 颗糖果，第二个小朋友 n + 2 颗，依此类推，直到给最后一个小朋友 2 * n 颗糖果。

重复上述过程（每次都比上一次多给出一颗糖果，当到达队伍终点后再次从队伍起点开始），直到我们分完所有的糖果。注意，就算我们手中的剩下糖果数不够（不比前一次发出的糖果多），这些糖果也会全部发给当前的小朋友。

返回一个长度为 num_people、元素之和为 candies 的数组，以表示糖果的最终分发情况（即 ans[i] 表示第 i 个小朋友分到的糖果数）。

输入输出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
示例 1：
输入：candies = 7, num_people = 4
输出：[1,2,3,1]
解释：
第一次，ans[0] += 1，数组变为 [1,0,0,0]。
第二次，ans[1] += 2，数组变为 [1,2,0,0]。
第三次，ans[2] += 3，数组变为 [1,2,3,0]。
第四次，ans[3] += 1（因为此时只剩下 1 颗糖果），最终数组变为 [1,2,3,1]。

示例 2：
输入：candies = 10, num_people = 3
输出：[5,2,3]
解释：
第一次，ans[0] += 1，数组变为 [1,0,0]。
第二次，ans[1] += 2，数组变为 [1,2,0]。
第三次，ans[2] += 3，数组变为 [1,2,3]。
第四次，ans[0] += 4，最终数组变为 [5,2,3]。

大致思路

暴力搜索分糖 官方还有更好的方法 需数学推导

java实现

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int[] distributeCandies(int candies, int num_people) {
        int[] ans = new int[num_people];
        int i = 0;
        while (candies != 0) {
            ans[i % num_people] += Math.min(candies, i + 1);
            candies -= Math.min(candies, i + 1);
            i += 1;
        }
        return ans;
    }
}

3.和为s连续整数序列

题目描述

输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。

序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。

输入输出

1
2
3
4
5
输入：target = 9
输出：[[2,3,4],[4,5]]

输入：target = 15
输出：[[1,2,3,4,5],[4,5,6],[7,8]]

大致思路

1
2
3
4
5
6
7
8
9
10
11
由：
n (n1 + n1 + n - 1)
-----------------------  = target
2
和
nb = n1 + n - 1
上述两个初中数学推导后得：
                2 * target - n * n - n
    n1  =  -----------------------------
                    2 * n
此时n1必须为正整数

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
class Solution {
    public int[][] findContinuousSequence(int target) {
        int n = 2;
        int limit = target >> 1;
        LinkedList<int []> result = new LinkedList<>();
        while (true) {
            int numerator = 2 * target - n * n + n;
            int denominator = 2 * n;
            // 如果不是整除，我们需要略过。
            if (numerator % denominator != 0) {
                n++;
                continue;
            }
            int n1 =  numerator / denominator;
            if (n >= limit || n1 <= 0) {
                break;
            }
            int[] a = new int[n];
            for (int k = n1, i = 0; i < n; i++, k++) {
                a[i] = k;
            }
            result.addFirst(a);
            n++;
        }
        return result.toArray(new int[result.size()][]);
    }
}

4.买卖股票的最佳时机

题目描述

1
2
3
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。
注意你不能在买入股票前卖出股票。

大致思路

维护一个maxprice = prices[i] - minprice 不推荐使用暴力解法

java思路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int maxProfit(int[] prices) {
        int minprice = Integer.MAX_VALUE;
        int maxprice = 0;
        for(int i = 0; i < prices.length; i++){
            if(prices[i] < minprice){
                minprice = prices[i];
            }
            else if(prices[i] - minprice > maxprice){
                maxprice = prices[i] - minprice;
            }
        }
        return maxprice;
    }
}

5.二叉树的直径

题目描述

给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过根结点。

输入输出

1
2
3
4
5
6
7
8
9
10
示例 :
给定二叉树

          1
         / \
        2   3
       / \     
      4   5    
返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。
注意：两结点之间的路径长度是以它们之间边的数目表示。

大致思路

递归求最大深度

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int diameter = 0;
    
    public int diameterOfBinaryTree(TreeNode root) {
        
        maxDepth(root);
        return diameter;
    }

    public int maxDepth(TreeNode root){
        if(root == null){
            return 0;
        }
        int left = maxDepth(root.left);
        int right = maxDepth(root.right);
        diameter = Math.max(diameter, left + right);
        return Math.max(left, right) + 1;
    }
}