每日算法-250530

每日算法 - 250530

记录一下今天完成的LeetCode算法题目，包含思路、解题过程、复杂度分析和代码实现。

3128. 直角三角形

题目

思路

数组

解题过程

显而易见的是，我们枚举中间的顶点最好计算。当我们的中间顶点是1时，它能够组成的直角三角形的个数就是这一行除了它以外的1的个数乘上这一列除了它以外的1的个数。

复杂度

• 时间复杂度: $O(NM)$
• 空间复杂度: $O(N+M)$

Code

class Solution {
    public long numberOfRightTriangles(int[][] grid) {
        long ret = 0;
        int r = grid.length;
        int c = grid[0].length;
        int[] r1 = new int[r];
        int[] c1 = new int[c];
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                if (grid[i][j] == 1) {
                    r1[i]++;
                    c1[j]++;
                }
            }
        }
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                if (grid[i][j] == 1) {
                    ret += (long)(r1[i] - 1) * (c1[j] - 1);
                }
            }
        }
        return ret;
    }
}

303. 区域和检索 - 数组不可变

思路

前缀和

解题过程

我们可以在初始化的时候将nums预处理成一个前缀和数组dp。dp[i]表示[0, i]区间的和。那么sumRange(left, right)方法只需返回 dp[right] - dp[left - 1] 就可以得到 [left, right] 区间的和了。
需要注意的是：当 left=0 时，dp[right] 就是 [0, right] 的和，此时不能减去 dp[left - 1]，可以直接返回 dp[right]。

复杂度

• 时间复杂度: 初始化是 $O(N)$，sumRange 是 $O(1)$
• 空间复杂度: $O(N)$ (如果创建新的dp数组) 或 $O(1)$ (如果在原数组上修改，不计输入数组本身)

Code

class NumArray {

    private int[] prefixSums;

    public NumArray(int[] nums) {
        prefixSums = new int[nums.length];
        prefixSums[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            prefixSums[i] = prefixSums[i - 1] + nums[i];
        }
    }

    public int sumRange(int left, int right) {
        if (prefixSums.length == 0 || left < 0 || right >= prefixSums.length || left > right) {
            return 0; 
        }
        if (left == 0) {
            return prefixSums[right];
        }
        return prefixSums[right] - prefixSums[left - 1];
    }
}

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray obj = new NumArray(nums);
 * int param_1 = obj.sumRange(left,right);
 */

3427. 变长子数组求和

题目

思路

前缀和

解题过程

1. 首先，预处理得到前缀和数组 dp，其中 dp[i] 表示原数组 nums 中区间 [0, i] 的元素之和。
2. 遍历数组 nums，对于每个索引 i：
   • 题目描述指出，对于索引 i，子数组 nums[start...i] 的长度为 nums[i]。
   • 这意味着 i - start + 1 = nums[i]，所以 start = i - nums[i] + 1。
   • 该子数组 nums[actualStart...i] 的和可以通过前缀和数组计算：dp[i] - (actualStart == 0 ? 0 : dp[actualStart - 1])。
3. 将所有这些子数组的和累加起来即为最终答案。

复杂度

• 时间复杂度: $O(N)$
• 空间复杂度: $O(N)$

Code

class Solution {
    public int subarraySum(int[] nums) {
        int sum = 0, n = nums.length;
        int[] dp = new int[n];
        dp[0] = nums[0];
        for (int i = 1; i < n; i++) {
            dp[i] = dp[i - 1] + nums[i];
        }
        for (int i = 0; i < n; i++) {
            int start = Math.max(0, i - nums[i]);
            sum += (start == 0) ? dp[i] : dp[i] - dp[start - 1];
        }
        return sum;
    }
}

2874. 有序三元组中的最大值 II（复习）

题目

这是第二次写这道题了，已经算是掌握了，就不再多说了，详细题解见每日算法-250527

代码

class Solution {
    public long maximumTripletValue(int[] nums) {
        long ret = 0;
        int n = nums.length;
        int[] suffixMax = new int[n];
        suffixMax[n - 1] = nums[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            suffixMax[i] = Math.max(suffixMax[i + 1], nums[i]);
        }
        int privMax = nums[0];
        for (int i = 1; i < n - 1; i++) {
            ret = Math.max(ret, ((long) (privMax - nums[i]) * suffixMax[i + 1]));
            privMax = Math.max(privMax, nums[i]);
        }
        return ret;
    }
}