数组中等差数列的组数 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int solution(int[] A) {
    int n = A.length;
    long res = 0;
    for (int i = 0; i < n; ) {
        int j = i + 1;
        while (j + 1 < n && (long) A[j + 1] - (long) A[j] == (long) A[j] - (long) A[j - 1]) j++;
        int num = j - i + 1;
        if (num >= 3) {
            for (int k = 3; k <= num; k++)
                res += num - k + 1;
        }
        i = j;
    }
    return (int) res;
}

展开全文 >>

找能构成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
public int solution(int[] X, int[] Y) {
    int n = X.length;
    int mod = (int) 1e9 + 7;
    Map<String, Integer> map = new HashMap<>();
    long res = 0;
    for (int i = 0; i < n; i++) {
        int ai = X[i], bi = Y[i], k = gcd(ai, bi);
        if (k != 1) {
            X[i] /= k;
            Y[i] /= k;
        }
        // 找前面配对的数量，配对的分数是px / py
        int px = Y[i] - X[i], py = Y[i];
        k = gcd(px, py);
        if (k != 1) {
            px /= k;
            py /= k;
        }
        // key是target数，如果包含target那么就加上
        String key = String.valueOf(px) + "_" + String.valueOf(py);
        if (map.containsKey(key)) res = (res + map.get(key)) % mod;
        // System.out.println(key);
        // 写入当前的值
        key = String.valueOf(X[i]) + "_" + String.valueOf(Y[i]);
        map.put(key, map.getOrDefault(key, 0) + 1);
    }
    return (int) (res % mod);
}

public int gcd(int x, int y) {
    return y > 0 ? gcd(y, x % y) : x;
}

排序+双指针

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
class Pair implements Comparable<Pair> {
    int numerator;
    int denominator;

    public Pair(int numerator, int denominator) {
        int k = gcd(numerator, denominator);
        this.numerator = numerator / k;
        this.denominator = denominator / k;
    }

    @Override
    public int compareTo(Pair o) {
        double res = this.numerator / this.denominator - o.numerator / o.denominator;
        if (res > 0) {
            return 1;
        } else if (res == 0) {
            return 0;
        } else {
            return -1;
        }
    }
}

public int test(int[] X, int[] Y) {
    // write your code in Java SE 8
    int n = X.length;
    int mod = (int) 1e9 + 7;
    Pair[] pair = new Pair[n];
    for (int i = 0; i < n; i++) {
        pair[i] = new Pair(X[i], Y[i]);
    }
    Arrays.sort(pair);

    long res = 0;
    for (int i = 0; i < n; i++) {
        int l = i, r = n - 1;
        while (l < r) {
            if (pair[l].denominator != pair[r].denominator) {
                r--;
                continue;
            }
            long res1 = (long) pair[l].numerator + (long) pair[r].numerator;
            long res2 = (long) pair[l].denominator;
            if (res1 == res2) {
                res = (res + 1) % mod;
                r--;
            } else if (res1 < res2) {
                l++;
            } else {
                r--;
            }
        }
    }
    return (int) (res % mod);
}

展开全文 >>

叶子相似的树

872. 叶子相似的树

难度简单111

请考虑一棵二叉树上所有的叶子，这些叶子的值按从左到右的顺序排列形成一个 叶值序列 。

img

举个例子，如上图所示，给定一棵叶值序列为 (6, 7, 4, 9, 8) 的树。

如果有两棵二叉树的叶值序列是相同，那么我们就认为它们是 叶相似 的。

如果给定的两个根结点分别为 root1 和 root2 的树是叶相似的，则返回 true；否则返回 false 。

示例 1：

img

1
2
输入：root1 = [3,5,1,6,2,9,8,null,null,7,4], root2 = [3,5,1,6,7,4,2,null,null,null,null,null,null,9,8]
输出：true

示例 2：

1
2
输入：root1 = [1], root2 = [1]
输出：true

示例 3：

1
2
输入：root1 = [1], root2 = [2]
输出：false

示例 4：

1
2
输入：root1 = [1,2], root2 = [2,2]
输出：true

示例 5：

img

1
2
输入：root1 = [1,2,3], root2 = [1,3,2]
输出：false

提示：

  • 给定的两棵树可能会有 1 到 200 个结点。
  • 给定的两棵树上的值介于 0 到 200 之间。

一个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
36
37
38
39
40
41
42
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean leafSimilar(TreeNode root1, TreeNode root2) {
        list = new ArrayList<Integer>();
        dfs(root1);
        flag = true;
        return dfs(root2)&&cnt==list.size();
    }

    List<Integer> list = null;
    boolean flag = false;
    int cnt  = 0;
    public boolean dfs(TreeNode root){
        if(null==root)return true;
        if(root.left==null&&root.right==null){
            if(!flag){
                list.add(root.val);
            }else{
                if(cnt<list.size()&&list.get(cnt)==root.val){
                    cnt++;
                }else{
                    return false;
                }
            }
        }
        return dfs(root.left)&&dfs(root.right);
    }
}

两个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
class Solution {
    public boolean leafSimilar(TreeNode root1, TreeNode root2) {
        List<Integer> seq1 = new ArrayList<Integer>();
        if (root1 != null) {
            dfs(root1, seq1);
        }

        List<Integer> seq2 = new ArrayList<Integer>();
        if (root2 != null) {
            dfs(root2, seq2);
        }

        return seq1.equals(seq2);
    }

    public void dfs(TreeNode node, List<Integer> seq) {
        if (node.left == null && node.right == null) {
            seq.add(node.val);
        } else {
            if (node.left != null) {
                dfs(node.left, seq);
            }
            if (node.right != null) {
                dfs(node.right, seq);
            }
        }
    }
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/leaf-similar-trees/solution/xie-zi-xiang-si-de-shu-by-leetcode-solut-z0w6/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

展开全文 >>

子数组最小乘积的最大值

5752. 子数组最小乘积的最大值

难度中等6收藏分享切换为英文接收动态反馈

一个数组的 最小乘积 定义为这个数组中 最小值 乘以 数组的 和 。

  • 比方说，数组 [3,2,5] （最小值是 2）的最小乘积为 2 * (3+2+5) = 2 * 10 = 20 。

给你一个正整数数组 nums ，请你返回 nums 任意 非空子数组 的最小乘积 的 最大值 。由于答案可能很大，请你返回答案对 10^9 + 7 取余 的结果。

请注意，最小乘积的最大值考虑的是取余操作 之前 的结果。题目保证最小乘积的最大值在 不取余 的情况下可以用 64 位有符号整数 保存。

子数组 定义为一个数组的 连续 部分。

示例 1：

1
2
3
4
输入：nums = [1,2,3,2]
输出：14
解释：最小乘积的最大值由子数组 [2,3,2] （最小值是 2）得到。
2 * (2+3+2) = 2 * 7 = 14 。

示例 2：

1
2
3
4
输入：nums = [2,3,3,1,2]
输出：18
解释：最小乘积的最大值由子数组 [3,3] （最小值是 3）得到。
3 * (3+3) = 3 * 6 = 18 。

示例 3：

1
2
3
4
输入：nums = [3,1,5,6,4,2]
输出：60
解释：最小乘积的最大值由子数组 [5,6,4] （最小值是 4）得到。
4 * (5+6+4) = 4 * 15 = 60 。

提示：

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^7

超时解法

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

public class Solution {
    public int maxSumMinProduct(int[] nums) {
        long result = 0;
        int len = nums.length;
        for(int i = 0; i < len; i++){
            // 用nums[i]作为子数组最小的元素,则向左向右构造一个子数组，使得子数组内每个元素都不小于nums[i]
            // 因为我们已经选定了最小的元素，所以子数组内的元素越多越好，越多和就越大，则乘积越大
            if(i != 0 && nums[i] == nums[i-1]){continue;}//去掉相邻重复的（已经用过了）
            long sum = 0;
            int j = i;
            while(j < len && nums[j] >= nums[i]){//向右寻找不小于它的数
                sum += nums[j];
                j++;
            }
            j = i-1;
            while(j >= 0 && nums[j] >= nums[i]){//向左寻找不小于它的数
                sum += nums[j];
                j--;
            }
            result = Math.max(result, nums[i]*sum);
        }
        return (int)(result%1000000007);
    }
}


作者：ji-bo-lai-zi-xing-xing-de
链接：https://leetcode-cn.com/problems/maximum-subarray-min-product/solution/java-gu-ding-zui-xiao-yuan-su-kuo-zhang-octq4/
来源：力扣（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
50
51
52
class Solution {
public int maxSumMinProduct(int[] nums) {
        long[] prefixNums = new long[nums.length];
    	// 计算前缀和
        prefixNums[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            prefixNums[i] = prefixNums[i - 1] + nums[i];
        }

        Deque<Integer> upStack = new LinkedList<>();
        long max = 0;
        // 数组元素 下标 单调递增栈
    
    	// upStack是单调递增的栈
        for (int i = 0; i < nums.length; i++) {
            // 如果栈顶元素小于当前的元素,当前的元素入栈
            // 否则栈顶元素出栈,并记录目前的最大值,直到栈顶元素小于等于当前的元素,将目前的元素入栈
            if (upStack.isEmpty() || nums[upStack.peek()] <= nums[i]) {
                upStack.push(i);
            } else {
                // 每次出栈计算乘积
                // 如果不满足元素递增......
                while (!upStack.isEmpty() && nums[upStack.peek()] > nums[i]) {
                    // 当前栈顶的元素是最小值(为什么?)
                    int minIndex = upStack.pop();
                    // 栈顶的元素的index+1是子数组开始的index，这里为什么要+1？？？
                    int start = upStack.isEmpty() ? 0 : upStack.peek() + 1;
                    int end = i - 1;
                    max = Math.max(max, calcu(prefixNums, start, end, nums[minIndex]));
                }
                upStack.push(i);
            }
        }
        // 栈中剩余元素依次出栈，并计算乘积
        while (!upStack.isEmpty()) {
            int minIndex = upStack.pop();
            int end = nums.length - 1;
            int start = upStack.isEmpty() ? 0 : upStack.peek()+1;
            max = Math.max(max, calcu(prefixNums, start, end, nums[minIndex]));
        }
        return (int) (max % 1000000007);
    }

    // 求乘积
    private long calcu(long[] prefixNums, int start, int end, int min) {
        long sum = start == 0 ?
                prefixNums[end] :
                prefixNums[end] - prefixNums[start-1];
        return sum * min;
    }

}

参考文献

JAVA单调栈+前缀和 - 子数组最小乘积的最大值 - 力扣（LeetCode） (leetcode-cn.com)

展开全文 >>

下标对中的最大距离

5751. 下标对中的最大距离

难度中等2收藏分享切换为英文接收动态反馈

给你两个 非递增 的整数数组 nums1 和 nums2 ，数组下标均 从 0 开始 计数。

下标对 (i, j) 中 0 <= i < nums1.length 且 0 <= j < nums2.length 。如果该下标对同时满足 i <= j 且 nums1[i] <= nums2[j] ，则称之为 有效 下标对，该下标对的 距离 为 j - i 。

返回所有 有效 下标对 (i, j) 中的 最大距离 。如果不存在有效下标对，返回 0 。

一个数组 arr ，如果每个 1 <= i < arr.length 均有 arr[i-1] >= arr[i] 成立，那么该数组是一个 非递增 数组。

示例 1：

1
2
3
4
输入：nums1 = [55,30,5,4,2], nums2 = [100,20,10,10,5]
输出：2
解释：有效下标对是 (0,0), (2,2), (2,3), (2,4), (3,3), (3,4) 和 (4,4) 。
最大距离是 2 ，对应下标对 (2,4) 。

示例 2：

1
2
3
4
输入：nums1 = [2,2,2], nums2 = [10,10,1]
输出：1
解释：有效下标对是 (0,0), (0,1) 和 (1,1) 。
最大距离是 1 ，对应下标对 (0,1) 。

示例 3：

1
2
3
4
输入：nums1 = [30,29,19,5], nums2 = [25,25,25,25,25]
输出：2
解释：有效下标对是 (2,2), (2,3), (2,4), (3,3) 和 (3,4) 。
最大距离是 2 ，对应下标对 (2,4) 。

示例 4：

1
2
3
输入：nums1 = [5,4], nums2 = [3,2]
输出：0
解释：不存在有效下标对，所以返回 0 。

提示：

  • 1 <= nums1.length <= 105
  • 1 <= nums2.length <= 105
  • 1 <= nums1[i], nums2[j] <= 105
  • nums1 和 nums2 都是 非递增 数组

二分查找

首先在第一个数组里面确定一个数字target

然后在第二个数组里面查找不小于当前target数字的最右边的那个数字的index，然后记录两个index差值的最大值。

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 maxDistance(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int max = 0;
        for (int i = 0; i < m; i++) {
            int index = binarySearch(nums2, nums1[i]);
            if (index >= i) {
                max = Math.max(index - i - 1, max);
            }
        }
        return max;
    }

    public int binarySearch(int[] nums, int target) {
        int l = 0, r = nums.length - 1;
        int m = 0;
        while (l <= r) {
            m = l + (r - l) / 2;
            if (nums[m] >= target) {
                l = m + 1;
            } else {
                r = m - 1;
            }
        }
        return l;
    }
}

展开全文 >>

人口最多的年份

5750. 人口最多的年份

难度简单2收藏分享切换为英文接收动态反馈

给你一个二维整数数组 logs ，其中每个 logs[i] = [birthi, deathi] 表示第 i 个人的出生和死亡年份。

年份 x 的 人口 定义为这一年期间活着的人的数目。第 i 个人被计入年份 x 的人口需要满足：x 在闭区间 [birthi, deathi - 1] 内。注意，人不应当计入他们死亡当年的人口中。

返回 人口最多 且 最早 的年份。

示例 1：

1
2
3
输入：logs = [[1993,1999],[2000,2010]]
输出：1993
解释：人口最多为 1 ，而 1993 是人口为 1 的最早年份。

示例 2：

1
2
3
4
5
输入：logs = [[1950,1961],[1960,1971],[1970,1981]]
输出：1960
解释： 
人口最多为 2 ，分别出现在 1960 和 1970 。
其中最早年份是 1960 。

提示：

  • 1 <= logs.length <= 100
  • 1950 <= birthi < deathi <= 2050

暴力统计

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 maximumPopulation(int[][] logs) {

        int max = 0;
        int maxIndex = 1950;
        for (int i = 1950; i <= 2050; i++) {
            // 统计当前年份的人数
            int cnt = 0;
            // 统计在当前年份之前出生的人的数量
            for (int j = 0; j < logs.length; j++) {
                if (logs[j][0] <= i) {
                    cnt++;
                }
            }
            // 统计在当前年份之前死亡的人的数量
            for (int j = 0; j < logs.length; j++) {
                if (logs[j][1] <= i) {
                    cnt--;
                }
            }
			// 如果当前活着的人口的数量大于其他年份的数量,那么记录最大值的年份
            if (cnt > max) {
                max = cnt;
                maxIndex = i;
            }

        }
        return maxIndex;
    }
}

差分法

  • 利用一个数组作为hash表记录当前年份出生的人的数量和死亡的人的数量
  • 再次遍历哈希表找到最大值的年份
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 {
    public int maximumPopulation(int[][] logs) {
        int[] d = new int[110];
        for(int[] log : logs) {     //遍历每个人的出生和死亡年份
            d[log[0] - 1950] += 1;  //出生年份人数+1
            d[log[1] - 1950] -= 1;  //死亡年份人数-1
        }
        int s = 0, res = 0, cnt = 0;
        for(int i = 0; i <= 100; i++){
            s += d[i];      //s是记录每一年的存活人数
            if(s > cnt){
                cnt = s; 
                res = i;
            }
        }
        return res + 1950;
    }
}

作者：hpq30Fv0IV
链接：https://leetcode-cn.com/problems/maximum-population-year/solution/javabao-li-chai-fen-by-hpq30fv0iv-bupd/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

展开全文 >>

制作m束花所需的最少天数

1482. 制作 m 束花所需的最少天数

难度中等96收藏分享切换为英文接收动态反馈

给你一个整数数组 bloomDay，以及两个整数 m 和 k 。

现需要制作 m 束花。制作花束时，需要使用花园中 相邻的 k 朵花 。

花园中有 n 朵花，第 i 朵花会在 bloomDay[i] 时盛开，恰好 可以用于 一束 花中。

请你返回从花园中摘 m 束花需要等待的最少的天数。如果不能摘到 m 束花则返回 -1 。

示例 1：

1
2
3
4
5
6
7
输入：bloomDay = [1,10,3,10,2], m = 3, k = 1
输出：3
解释：让我们一起观察这三天的花开过程，x 表示花开，而 _ 表示花还未开。
现在需要制作 3 束花，每束只需要 1 朵。
1 天后：[x, _, _, _, _]   // 只能制作 1 束花
2 天后：[x, _, _, _, x]   // 只能制作 2 束花
3 天后：[x, _, x, _, x]   // 可以制作 3 束花，答案为 3

示例 2：

1
2
3
输入：bloomDay = [1,10,3,10,2], m = 3, k = 2
输出：-1
解释：要制作 3 束花，每束需要 2 朵花，也就是一共需要 6 朵花。而花园中只有 5 朵花，无法满足制作要求，返回 -1 。

示例 3：

1
2
3
4
5
6
7
8
输入：bloomDay = [7,7,7,7,12,7,7], m = 2, k = 3
输出：12
解释：要制作 2 束花，每束需要 3 朵。
花园在 7 天后和 12 天后的情况如下：
7 天后：[x, x, x, x, _, x, x]
可以用前 3 朵盛开的花制作第一束花。但不能使用后 3 朵盛开的花，因为它们不相邻。
12 天后：[x, x, x, x, x, x, x]
显然，我们可以用不同的方式制作两束花。

示例 4：

1
2
3
输入：bloomDay = [1000000000,1000000000], m = 1, k = 1
输出：1000000000
解释：需要等 1000000000 天才能采到花来制作花束

示例 5：

1
2
输入：bloomDay = [1,10,2,9,3,8,4,7,5,6], m = 4, k = 2
输出：9

提示：

  • bloomDay.length == n
  • 1 <= n <= 10^5
  • 1 <= bloomDay[i] <= 10^9
  • 1 <= m <= 10^6
  • 1 <= k <= n

二分答案

使用二分查找方法查找所需的天数，如果mid天可以生成m束花那么可以减小这个天数，如果mid天不可以生成m束花那么需要增大这个天数，直至有一天能生成m束花，且m-1天不可以生成m束花。

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 minDays(int[] bloomDay, int m, int k) {
        int n = bloomDay.length;
        if (k * m > n) return -1;
        int max = bloomDay[0];
        for (int i = 1; i < n; i++) {
            max = Math.max(bloomDay[i], max);
        }
        int l = 1, r = max;
        while (l < r) {
            int day = l + (r - l) / 2;
            if (check(bloomDay, m, k, day)) {
                r = day;
            } else {
                l = day + 1;
            }
        }
        return l;
    }
    
    public boolean check(int[] bloomDay, int m, int k, int day) {
        int flower = 0;
        int cnt = 0;
        for (int i = 0; i < bloomDay.length && cnt < m; i++) {
            if (day >= bloomDay[i]) {
                flower++;
                if (flower == k) {
                    flower = 0;
                    cnt++;
                }
            } else {
                flower = 0;
            }
        }
        return cnt >= m;
    }
}

展开全文 >>

完成所有工作的最短时间

1723. 完成所有工作的最短时间

难度困难147收藏分享切换为英文接收动态反馈

给你一个整数数组 jobs ，其中 jobs[i] 是完成第 i 项工作要花费的时间。

请你将这些工作分配给 k 位工人。所有工作都应该分配给工人，且每项工作只能分配给一位工人。工人的 工作时间 是完成分配给他们的所有工作花费时间的总和。请你设计一套最佳的工作分配方案，使工人的 最大工作时间 得以 最小化 。

返回分配方案中尽可能 最小 的 最大工作时间 。

示例 1：

1
2
3
输入：jobs = [3,2,3], k = 3
输出：3
解释：给每位工人分配一项工作，最大工作时间是 3 。

示例 2：

1
2
3
4
5
6
输入：jobs = [1,2,4,7,8], k = 2
输出：11
解释：按下述方式分配工作：
1 号工人：1、2、8（工作时间 = 1 + 2 + 8 = 11）
2 号工人：4、7（工作时间 = 4 + 7 = 11）
最大工作时间是 11 。

提示：

  • 1 <= k <= jobs.length <= 12
  • 1 <= jobs[i] <= 107

该题目还没有理解（待填坑）

二分查找 + 回溯 + 剪枝

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
class Solution {
    public int minimumTimeRequired(int[] jobs, int k) {
        Arrays.sort(jobs);
        int low = 0, high = jobs.length - 1;
        while (low < high) {
            int temp = jobs[low];
            jobs[low] = jobs[high];
            jobs[high] = temp;
            low++;
            high--;
        }
        int l = jobs[0], r = Arrays.stream(jobs).sum();
        while (l < r) {
            int mid = (l + r) >> 1;
            if (check(jobs, k, mid)) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }

    public boolean check(int[] jobs, int k, int limit) {
        int[] workloads = new int[k];
        return backtrack(jobs, workloads, 0, limit);
    }

    public boolean backtrack(int[] jobs, int[] workloads, int i, int limit) {
        if (i >= jobs.length) {
            return true;
        }
        int cur = jobs[i];
        for (int j = 0; j < workloads.length; ++j) {
            if (workloads[j] + cur <= limit) {
                workloads[j] += cur;
                if (backtrack(jobs, workloads, i + 1, limit)) {
                    return true;
                }
                workloads[j] -= cur;
            }
            // 如果当前工人未被分配工作，那么下一个工人也必然未被分配工作
            // 或者当前工作恰能使该工人的工作量达到了上限
            // 这两种情况下我们无需尝试继续分配工作
            if (workloads[j] == 0 || workloads[j] + cur == limit) {
                break;
            }
        }
        return false;
    }
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/find-minimum-time-to-finish-all-jobs/solution/wan-cheng-suo-you-gong-zuo-de-zui-duan-s-hrhu/
来源：力扣（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
class Solution {
    public int minimumTimeRequired(int[] jobs, int k) {
        int n = jobs.length;
        int[] sum = new int[1 << n];
        for (int i = 1; i < (1 << n); i++) {
            int x = Integer.numberOfTrailingZeros(i), y = i - (1 << x);
            sum[i] = sum[y] + jobs[x];
        }

        int[][] dp = new int[k][1 << n];
        for (int i = 0; i < (1 << n); i++) {
            dp[0][i] = sum[i];
        }

        for (int i = 1; i < k; i++) {
            for (int j = 0; j < (1 << n); j++) {
                int minn = Integer.MAX_VALUE;
                for (int x = j; x != 0; x = (x - 1) & j) {
                    minn = Math.min(minn, Math.max(dp[i - 1][j - x], sum[x]));
                }
                dp[i][j] = minn;
            }
        }
        return dp[k - 1][(1 << n) - 1];
    }
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/find-minimum-time-to-finish-all-jobs/solution/wan-cheng-suo-you-gong-zuo-de-zui-duan-s-hrhu/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

展开全文 >>

树洞202105

2021.05.07

2021.05.08

2021.05.09

2021.05.19

今天leetcode突破了700题,继续加油，没有什么是高不可攀的，只要一步一个脚印，不停下来就能超过你的所有目标。

2021.05.21

狗子，没用的，已经跟你说过了，不是所有的事情努力就能向好的方向发展的，好好安心挣钱吧~

2021.05.22

又一位真正为全人类做出巨大贡献大国巨匠陨落了。要做独善其身，兼济天下的人。

2021.05.29

有道理哦，谁愿意找一个人来降低自己的生活质量呢？

2021.05.30

Imgur

展开全文 >>

数组异或操作

1486. 数组异或操作

难度简单52收藏分享切换为英文接收动态反馈

给你两个整数，n 和 start 。

数组 nums 定义为：nums[i] = start + 2*i（下标从 0 开始）且 n == nums.length 。

请返回 nums 中所有元素按位异或（XOR）后得到的结果。

示例 1：

1
2
3
4
输入：n = 5, start = 0
输出：8
解释：数组 nums 为 [0, 2, 4, 6, 8]，其中 (0 ^ 2 ^ 4 ^ 6 ^ 8) = 8 。
     "^" 为按位异或 XOR 运算符。

示例 2：

1
2
3
输入：n = 4, start = 3
输出：8
解释：数组 nums 为 [3, 5, 7, 9]，其中 (3 ^ 5 ^ 7 ^ 9) = 8.

示例 3：

1
2
输入：n = 1, start = 7
输出：7

示例 4：

1
2
输入：n = 10, start = 5
输出：2

提示：

  • 1 <= n <= 1000
  • 0 <= start <= 1000
  • n == nums.length

暴力计算O（N）

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int xorOperation(int n, int start) {
        int res = 0;
        int num = start;
        for(int i=0;i<n;i++){
            num = start+2*i;
            res = res^num;
        }
        return res;
    }
}

根据异或的性质

$∀i∈Z，有 4i \oplus (4i+1) \oplus (4i+2) \oplus (4i+3) = 0$

具体描述参考数组异或操作 - 数组异或操作 - 力扣（LeetCode） (leetcode-cn.com)

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
class Solution {
    public int xorOperation(int n, int start) {
        int s = start >> 1, e = n & start & 1;
        int ret = sumXor(s - 1) ^ sumXor(s + n - 1);
        return ret << 1 | e;
    }

    public int sumXor(int x) {
        if (x % 4 == 0) {
            return x;
        }
        if (x % 4 == 1) {
            return 1;
        }
        if (x % 4 == 2) {
            return x + 1;
        }
        return 0;
    }
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/xor-operation-in-an-array/solution/shu-zu-yi-huo-cao-zuo-by-leetcode-solution/
来源：力扣（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>希望有一天被领走