三维形体投影面积 

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
在 N * N 的网格中，我们放置了一些与 x，y，z 三轴对齐的 1 * 1 * 1 立方体。

每个值 v = grid[i][j] 表示 v 个正方体叠放在单元格 (i, j) 上。

现在，我们查看这些立方体在 xy、yz 和 zx 平面上的投影。

投影就像影子，将三维形体映射到一个二维平面上。

在这里，从顶部、前面和侧面看立方体时，我们会看到“影子”。

返回所有三个投影的总面积。

 

示例 1：

输入：[[2]]
输出：5
示例 2：

输入：[[1,2],[3,4]]
输出：17
解释：
这里有该形体在三个轴对齐平面上的三个投影(“阴影部分”)。

示例 3：

输入：[[1,0],[0,2]]
输出：8
示例 4：

输入：[[1,1,1],[1,0,1],[1,1,1]]
输出：14
示例 5：

输入：[[2,2,2],[2,1,2],[2,2,2]]
输出：21
 

提示：

1 <= grid.length = grid[0].length <= 50
0 <= grid[i][j] <= 50

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

投影

  • 从上往下投影（只要grid[i][j]>0就加一）
  • 从左往右投影（每一行的最大值的和）
  • 从右往左投影（每一列的最大值的和）
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
class Solution {
    public int projectionArea(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) return 0;

        int m = grid.length;
        int n = grid[0].length;

        int gArea = 0;
        int lArea = 0;
        int rArea = 0;

        int[] mCol = new int[n];

        for (int i = 0; i < m; i++) {
            int maxRow = 0;
            for (int j = 0; j < n; j++) {
                if (grid[i][j] > 0) gArea++;
                maxRow = Math.max(grid[i][j], maxRow);      // 每一行的最大值
                mCol[j] = Math.max(grid[i][j], mCol[j]);    // 每一列的最大值
            }
            lArea += maxRow;
        }
        for (int i = 0; i < n; i++) {
            rArea += mCol[i];
        }

        return gArea + lArea + rArea;
    }
}

优雅写法

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 projectionArea(int[][] grid) {
        int N = grid.length;
        int ans = 0;

        for (int i = 0; i < N;  ++i) {
            int bestRow = 0;  // largest of grid[i][j]
            int bestCol = 0;  // largest of grid[j][i]
            for (int j = 0; j < N; ++j) {
                if (grid[i][j] > 0) ans++;  // top shadow
                bestRow = Math.max(bestRow, grid[i][j]);
                bestCol = Math.max(bestCol, grid[j][i]);
            }
            ans += bestRow + bestCol;
        }

        return ans;
    }
}

作者：LeetCode
链接：https://leetcode-cn.com/problems/projection-area-of-3d-shapes/solution/san-wei-xing-ti-tou-ying-mian-ji-by-leetcode/
来源：力扣（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
在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。

示例 1：
输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
输出：4

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

输入：matrix = [["0"]]
输出：0
 

提示：

m == matrix.length
n == matrix[i].length
1 <= m, n <= 300
matrix[i][j] 为 '0' 或 '1'

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

动态规划

用 $dp(i, j)$ 表示以 $(i, 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
class Solution {
    public int maximalSquare(char[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        int[][] dp = new int[m][n];

        int max = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {

                if (i == 0 || j == 0) {
                    dp[i][j] = matrix[i][j] - '0';
                } else if (matrix[i][j] == '0') {
                    dp[i][j] = 0;
                } else {
                    dp[i][j] = Math.min(Math.min(dp[i][j - 1], dp[i - 1][j]), dp[i - 1][j - 1]) + 1;
                }
                max = Math.max(max, dp[i][j]);
            }
        }
        return max * max;
    }
}

相关题目

统计全为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
给你一个 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

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

动态规划

我们用 $dp[i][j]$ 表示以 $(i, j)$ 为右下角的正方形的最大边长，那么除此定义之外，$dp[i][j] = x$ 也表示以 $(i, j)$ 为右下角的正方形的数目为 $x$（即边长为 $1, 2, …, x$ 的正方形各一个）。在计算出所有的 $dp[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
class Solution {
    public int countSquares(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        int[][] dp = new int[m][n];

        int ans = 0;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 || j == 0) {
                    dp[i][j] = matrix[i][j];
                } else if (matrix[i][j] == 0) {
                    dp[i][j] = 0;
                } else {
                    // 以边长理解时，当前的最大边长与左边，上边和左上角的最小边长有关
                    // 是左边上边和左上角的最小值
                    dp[i][j] = Math.min(Math.min(dp[i][j - 1], dp[i - 1][j]), dp[i - 1][j - 1]) + 1;
                }
                ans += dp[i][j];
            }
        }
        return ans;
    }
}

参考文献

1
2
3
4
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/count-square-submatrices-with-all-ones/solution/tong-ji-quan-wei-1-de-zheng-fang-xing-zi-ju-zhen-2/
来源：力扣（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
44
45
46
47
48
49
给你一个只包含 0 和 1 的 rows * columns 矩阵 mat ，
请你返回有多少个 子矩形 的元素全部都是 1 。

示例 1：
输入：mat = [[1,0,1],
            [1,1,0],
            [1,1,0]]
输出：13
解释：
有 6 个 1x1 的矩形。
有 2 个 1x2 的矩形。
有 3 个 2x1 的矩形。
有 1 个 2x2 的矩形。
有 1 个 3x1 的矩形。
矩形数目总共 = 6 + 2 + 3 + 1 + 1 = 13 。

示例 2：
输入：mat = [[0,1,1,0],
            [0,1,1,1],
            [1,1,1,0]]
输出：24
解释：
有 8 个 1x1 的子矩形。
有 5 个 1x2 的子矩形。
有 2 个 1x3 的子矩形。
有 4 个 2x1 的子矩形。
有 2 个 2x2 的子矩形。
有 2 个 3x1 的子矩形。
有 1 个 3x2 的子矩形。
矩形数目总共 = 8 + 5 + 2 + 4 + 2 + 2 + 1 = 24 。

示例 3：
输入：mat = [[1,1,1,1,1,1]]
输出：21

示例 4：
输入：mat = [[1,0,1],[0,1,0],[1,0,1]]
输出：5
 

提示：

1 <= rows <= 150
1 <= columns <= 150
0 <= mat[i][j] <= 1

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/count-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
class Solution {
    public int numSubmat(int[][] mat) {
        int m = mat.length;
        int n = mat[0].length;

        int[][] row = new int[m][n];

        for (int i = 0; i < m; i++) {
            row[i][0] = mat[i][0];
        }

        for (int i = 0; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (mat[i][j] == 1) {
                    row[i][j] = row[i][j - 1] + 1;
                }
            }
        }

        int ans = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // 得到当前的宽度
                // width就代表了以当前 j 的值作为矩形右边的矩形个数
                int width = row[i][j];
                for (int k = i; k >= 0 && width != 0; k--) {
                    // 对高度进行枚举
                    // 每次枚举中找到当前行的宽度
                    width = Math.min(width, row[k][j]);
                    // 计算数量（不太明白）
                    ans += width;
                }
            }
        }

        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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
    public int numSubmat(int[][] mat) {
        int n = mat.length;
        int m = mat[0].length;
        int[][] row = new int[n][m];
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (j == 0) {
                    row[i][j] = mat[i][j];
                } else if (mat[i][j] != 0) {
                    row[i][j] = row[i][j - 1] + 1;
                } else {
                    row[i][j] = 0;
                }
            }
        }

        int ans = 0;
        for (int j = 0; j < m; ++j) { 
            int i = 0;
            Deque<int[]> Q = new LinkedList<int[]>();
            int sum = 0; 
            while (i <= n - 1) { 
                int height = 1; 
                while (!Q.isEmpty() && Q.peekFirst()[0] > row[i][j]) {
                   // 弹出的时候要减去多于的答案
                    sum -= Q.peekFirst()[1] * (Q.peekFirst()[0] - row[i][j]); 
                    height += Q.peekFirst()[1]; 
                    Q.pollFirst(); 
                } 
                sum += row[i][j]; 
                ans += sum; 
                Q.offerFirst(new int[]{row[i][j], height}); 
                i++; 
            } 
        } 
        return ans;
    }
}

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

展开全文 >>

使数组和能被P整除

1590. 使数组和能被 P 整除

难度中等

给你一个正整数数组 nums，请你移除 最短 子数组（可以为 空），使得剩余元素的 和 能被 p 整除。 不允许 将整个数组都移除。

请你返回你需要移除的最短子数组的长度，如果无法满足题目要求，返回 -1 。

子数组 定义为原数组中连续的一组元素。

示例 1：

1
2
3
输入：nums = [3,1,4,2], p = 6
输出：1
解释：nums 中元素和为 10，不能被 p 整除。我们可以移除子数组 [4] ，剩余元素的和为 6 。

示例 2：

1
2
3
输入：nums = [6,3,5,2], p = 9
输出：2
解释：我们无法移除任何一个元素使得和被 9 整除，最优方案是移除子数组 [5,2] ，剩余元素为 [6,3]，和为 9 。

示例 3：

1
2
3
输入：nums = [1,2,3], p = 3
输出：0
解释：和恰好为 6 ，已经能被 3 整除了。所以我们不需要移除任何元素。

示例 4：

1
2
3
输入：nums = [1,2,3], p = 7
输出：-1
解释：没有任何方案使得移除子数组后剩余元素的和被 7 整除。

示例 5：

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

提示：

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 109
  • 1 <= p <= 109

同余定理：数论中的重要概念。给定一个正整数m，如果两个整数 $a$ 和 $b$ 满足$a-b$ 能够被m整除，即 $(a-b)/m$ 得到一个整数，那么就称整数 $a$ 与 $b$ 对模 $m$ 同余，记作 $a≡b(mod\quad m)$ 。对模 $m$ 同余是整数的一个等价关系。

  • 反身性：$a≡a (mod\quad m)$；

  • 对称性：若$a≡b(mod\quad m)$，则$b≡a (mod\quad m)$；

  • 传递性：若$a≡b(mod\quad m)$，$b≡c(mod\quad m)$，则$a≡c(mod\quad m)$；

  • 同余式相加：若$a≡b(mod\quad m)$，$c≡d(mod\quad m)$，则$a c≡b d(mod\quad m)$；

  • 同余式相乘：若$a≡b(mod\quad m)$，$c≡d(mod\quad m)$，则$ac≡bd(mod\quad m)$。

1
2
3
4
5
两数a, b 对 p 同余, 则 (a - b) % p = 0.
sum(nums) % p = k
如果 k != 0,  记 sum(nums) = a, 
要求 (a - b) % p = 0, 其中 a % p = k, 
则 b % p = k,  b 为连续的一段 子数组之和. 取最短的 b .
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 minSubarray(int[] nums, int p) {
        int ans = Integer.MAX_VALUE;
        HashMap<Long, Integer> map = new HashMap<>();
        //用 mod 存储 和 的余数
        long mod = 0;
        for (int num : nums) {
            mod += num;
        }
        mod = mod % p;                                  // 得到余数
        if (mod == 0) {
            return 0;                                   // 如果 余数 为零，就说明整个数组的和是能被整除的！
        }
        long sum = 0;                                   // sum存储的是 nums[0] 到 nums[i]的和，也就是前缀和
        map.put((long) 0, -1);                          // 把 0 设置为 -1，因为数组起始坐标为0
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            long preMod = sum % p;                      // 求出 前缀和 对 p 取余!
            long target = (preMod - mod + p) % p;       // 求出目前的前缀和的模抵消了多少最开始的那个模,其中加p是为了防止模小于0
            if (map.get(target) != null) {
                ans = Math.min(ans, i - map.get(target));
            }
            map.put(preMod, i);                         // 将当前位置的抵消后的前缀和的模存储map中！
        }
        return ans >= nums.length ? -1 : ans;
    }
}

作者：yi-dai-mi-kang-ji-lou
链接：https://leetcode-cn.com/problems/make-sum-divisible-by-p/solution/xiang-xi-zhu-shi-zou-guo-lu-guo-bu-yao-c-8hkm/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

相似题目

和可被k整除的子数组

和为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
给你一个二进制矩阵 matrix ，它的大小为 m x n ，你可以将 matrix 中的 列 按任意顺序重新排列。

请你返回最优方案下将 matrix 重新排列后，全是 1 的子矩阵面积。

示例 1：
输入：matrix = [[0,0,1],[1,1,1],[1,0,1]]
输出：4
解释：你可以按照上图方式重新排列矩阵的每一列。
最大的全 1 子矩阵是上图中加粗的部分，面积为 4 。

示例 2：
输入：matrix = [[1,0,1,0,1]]
输出：3
解释：你可以按照上图方式重新排列矩阵的每一列。
最大的全 1 子矩阵是上图中加粗的部分，面积为 3 。

示例 3：
输入：matrix = [[1,1,0],[1,0,1]]
输出：2
解释：由于你只能整列整列重新排布，所以没有比面积为 2 更大的全 1 子矩形。

示例 4：
输入：matrix = [[0,0],[0,0]]
输出：0
解释：由于矩阵中没有 1 ，没有任何全 1 的子矩阵，所以面积为 0 。
 

提示：

m == matrix.length
n == matrix[i].length
1 <= m * n <= 105
matrix[i][j] 要么是 0 ，要么是 1 。

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

预处理数组，计算以这个点为结尾，上面有多少个连续的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
class Solution {
    public int largestSubmatrix(int[][] matrix) {
        int n=matrix.length;
        int m=matrix[0].length;
        int res=0;
        for(int i=1;i<n;i++){
            for(int j=0;j<m;j++){
                if(matrix[i][j]==1){
                    // 记录每一列到当前点时连续的1的个数
                    // 记录向上连续1的个数
                    matrix[i][j]+=matrix[i-1][j];
                }
            }
        }


        for(int i=0;i<n;i++){
            // 根据矩形的高度排序，高度低的在前面，高度高的在后面
            Arrays.sort(matrix[i]);
            for(int j=m-1;j>=0;j--){
                // 更新矩形的最大高度
                int height=matrix[i][j];
                // 更新最大面积
                res=Math.max(res,height*(m-j));
            }
        }
        return res;
    }
}

作者：rational-irrationality
链接：https://leetcode-cn.com/problems/largest-submatrix-with-rearrangements/solution/java-yu-chu-li-shu-zu-bian-li-mei-xing-p-qpqu/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

参考文献

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

相关题目

统计全 1 子矩形

统计全1的正方形子矩阵

最大矩形

最大正方形

展开全文 >>

缀点成线 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
在一个 XY 坐标系中有一些点，我们用数组 coordinates 来分别记录它们的坐标，其中 coordinates[i] = [x, y] 表示横坐标为 x、纵坐标为 y 的点。

请你来判断，这些点是否在该坐标系中属于同一条直线上，是则返回 true，否则请返回 false。

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

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

提示：

2 <= coordinates.length <= 1000
coordinates[i].length == 2
-10^4 <= coordinates[i][0], coordinates[i][1] <= 10^4
coordinates 中不含重复的点

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

使用向量判断多点是否共线。

求向量

求坐标为$(x_1,y_1)$,$(x_2,y_2)$两点的向量的公式为$\vec{a}=(x_2-x_1,y_2-y_1)$,

如何判断两点是否共线？

  • 两个点一定是共线的；
  • 判断多点是否共线时，只需要判断两两之间是否可以共线（向量的传递性证明）。

判断两点是否共线的公式
$x_1y_2=x_2y1$

向量共线的传递性证明

证明：
如果$\vec{a}≠0$，那么向量$\vec{b}$与$\vec{a}$共线的充要条件是：存在唯一实数$λ$，使得$\vec{b}=λ\vec{a}$。

若$\vec{a}$与$\vec{b}$共线，$\vec{b}$与$\vec{c}$共线，则$\vec{b}=λ_1 \vec{a}$，$\vec{c}=λ_2\vec{b}$，则$\vec{c}=λ_1 *λ_2 *\vec{a}$.即$\vec{a}$与$\vec{c}$也是共线的。

为了高效判断是否两两共线，可以通过中间点判断来减少时间复杂度，即如果存在三个点$p_1,p_2,p_3$，如果$p_1$与$p_2$共线并且$p_2$与$p_3$是共线的，那么$p_1$与$p_3$也是共线的。

因为题目中不包含重复的点，因此通过两两判断向量是否满足 $x_1y_2=x_2y1$，就可以判断所有的点是否共线

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution{

    public boolean checkStraightLine(int[][] coordinates) {
        if (coordinates.length <= 2) return true;
        int lastX = coordinates[1][0] - coordinates[0][0];
        int lastY = coordinates[1][1] - coordinates[0][1];

        for (int i = 1; i < coordinates.length; i++) {
            int x = coordinates[i][0] - coordinates[i - 1][0];
            int y = coordinates[i][1] - coordinates[i - 1][1];
            if( lastX * y != x * lastY){
                return false;
            }
        }
        return true;
    }
}

展开全文 >>

同积元组 

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
给你一个由 不同 正整数组成的数组 nums ，请你返回满足 a * b = c * d 的元组 (a, b, c, d) 的数量。
其中 a、b、c 和 d 都是 nums 中的元素，且 a != b != c != d 。
 

示例 1：

输入：nums = [2,3,4,6]
输出：8
解释：存在 8 个满足题意的元组：
(2,6,3,4) , (2,6,4,3) , (6,2,3,4) , (6,2,4,3)
(3,4,2,6) , (3,4,2,6) , (3,4,6,2) , (4,3,6,2)
示例 2：

输入：nums = [1,2,4,5,10]
输出：16
解释：存在 16 个满足题意的元组：
(1,10,2,5) , (1,10,5,2) , (10,1,2,5) , (10,1,5,2)
(2,5,1,10) , (2,5,10,1) , (5,2,1,10) , (5,2,10,1)
(2,10,4,5) , (2,10,5,4) , (10,2,4,5) , (10,2,4,5)
(4,5,2,10) , (4,5,10,2) , (5,4,2,10) , (5,4,10,2)
示例 3：

输入：nums = [2,3,4,6,8,12]
输出：40
示例 4：

输入：nums = [2,3,5,7]
输出：0
 

提示：

1 <= nums.length <= 1000
1 <= nums[i] <= 104
nums 中的所有元素 互不相同

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/tuple-with-same-product
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
  1. 对数组进行排序
  2. 遍历两个元素，一个从头遍历，一个从尾遍历
  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
class Solution {
    public int tupleSameProduct(int[] nums) {
        Arrays.sort(nums);
        int ans = 0;
        int l = 0, r = nums.length - 1;

        for (int i = 0; i < nums.length; i++) {
            for (int j = nums.length - 1; j >= i + 2; j--) {
                l = i + 1;
                r = j - 1;
                while (l < r) {
                    int a = nums[i] * nums[j];
                    int b = nums[l] * nums[r];
                    if (a == b) {
                        ans++;
                        l++;
                        r--;
                    } else if (a > b) {
                        l++;
                    } else {
                        r--;
                    }
                }
            }
        }

        return ans * 8;
    }
}

题目要求计算数组中 ab == cd的四元组，实际上可以看做求数组中两个数的积是否会在数组中重复出现。
也就是可以想到用map来判断是否会重复出现，重复出现的次数用key来记录。
因为是四元组相同的元素会有8种不同的组合，所以最终结果是重复出现次数*8；

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 tupleSameProduct(int[] nums) {
        if(nums == null || nums.length == 0){
            return 0;
        }
        Map<Integer, Integer> map = new HashMap<>();
        int len = nums.length;
        int ans = 0;
        for(int i = 0; i < len - 1; i++){
            for(int j = i + 1; j < len; j++ ){    // 遍历 获得两两组合的积，并且不会出现重复
                int mutil = nums[i] * nums[j];    // 计算两两的积
                if(map.containsKey(mutil)){       // 如果积已经存在map
                    ans +=  map.get(mutil);       // 结果加上value，因为重复出现2次以上，组合会增多，不能只加1
                    map.put(mutil, map.get(mutil) + 1); // 出现次数加1
                }else{                            // 未出现在map
                    map.put(mutil, 1);            // 次数加1
                } 
            }
        }
        return ans*8;                             // 相同数字的四元组，能够组合成2的4次方，也就是8次
    }
}

作者：mai-dong-cao
链接：https://leetcode-cn.com/problems/tuple-with-same-product/solution/java-mapjie-fa-shuang-100-by-mai-dong-ca-jrew/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

参考文献

作者：mai-dong-cao来源：力扣（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

给你一个数组 rectangles ，其中 rectangles[i] = [li, wi] 表示第 i 个矩形的长度为 li 、宽度为 wi 。

如果存在 k 同时满足 k <= li 和 k <= wi ，就可以将第 i 个矩形切成边长为 k 的正方形。例如，矩形 [4,6] 可以切成边长最大为 4 的正方形。

设 maxLen 为可以从矩形数组 rectangles 切分得到的 最大正方形 的边长。

返回可以切出边长为 maxLen 的正方形的矩形 数目 。


示例 1：
输入：rectangles = [[5,8],[3,9],[5,12],[16,5]]
输出：3
解释：能从每个矩形中切出的最大正方形边长分别是 [5,3,5,5] 。
最大正方形的边长为 5 ，可以由 3 个矩形切分得到。

示例 2：
输入：rectangles = [[2,3],[3,7],[4,3],[3,7]]
输出：3

提示：

1 <= rectangles.length <= 1000
rectangles[i].length == 2
1 <= li, wi <= 109
li != wi

1、先计算每个矩形中可以形成的最大正方形的边长

2、记录最大的正方形边长

3、判断每个矩形是否可以生成最大边长的正方形

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int countGoodRectangles(int[][] rectangles) {
        int max = 0;
        for (int[] re : rectangles) {
            max = Math.max(Math.min(re[0], re[1]), max);
        }
        int res = 0;
        for (int[] re : rectangles) {
            if (re[0] >= max && re[1] >= max) {
                res++;
            }
        }
        return res;
    }
}

展开全文 >>

在区间范围内统计奇数数目 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
给你两个非负整数 low 和 high 。请你返回 low 和 high 之间（包括二者）奇数的数目。
 

示例 1：

输入：low = 3, high = 7
输出：3
解释：3 到 7 之间奇数数字为 [3,5,7] 。
示例 2：

输入：low = 8, high = 10
输出：1
解释：8 到 10 之间奇数数字为 [9] 。

提示：

0 <= low <= high <= 10^9

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/count-odd-numbers-in-an-interval-range
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
1
2
3
4
5
6
7
8
9
class Solution {
    public int countOdds(int low, int high) {
        int interval = high - low;
        int more = 0;
        if (low % 2 != 0 || high % 2 != 0) more = 1;
        int val = interval / 2;
        return val + more;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int countOdds(int low, int high) {
        return pre(high) - pre(low - 1);
    }

    public int pre(int x) {
        return (x + 1) >> 1;
    }
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/count-odd-numbers-in-an-interval-range/solution/zai-qu-jian-fan-wei-nei-tong-ji-qi-shu-shu-mu-by-l/
来源：力扣（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>希望有一天被领走