qypx の blog

区域和检索 - 数组不可变

发表于 2019-12-27 更新于 2019-12-28 分类于 leetcode

方法二：缓存

class NumArray {
    private int[] sum;
    
    public NumArray(int[] nums) {
        sum = new int[nums.length+1]; // 多增加一位
        for(int i = 0; i < nums.length; i++){
            sum[i+1] = sum[i] + nums[i];
        }
    }
    
    public int sumRange(int i, int j) {
        return sum[j+1] - sum[i];
    }
}

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

注意，在上面的代码中，我们插入了一个虚拟 0 作为 sum 数组中的第一个元素。这个技巧可以避免在 sumrange 函数中进行额外的条件检查。

最长上升子序列

发表于 2019-12-27 分类于 leetcode

最长上升子序列（难度：中等）

方法：动态规划

代码

class Solution {
    public int lengthOfLIS(int[] nums) {
        if(nums.length==0)
            return 0;
        int[] dp = new int[nums.length];
        int ans = 1;
        for(int i = 0; i < nums.length; i++){
            dp[i] = 1;
            for(int j = 0; j < i; j++){
                if(nums[i] > nums[j])
                    dp[i] = Math.max(dp[i], 1 + dp[j]);
            }
            ans = Math.max(ans, dp[i]);
        }
        return ans;
    }
}

进阶：将时间复杂度降低到O(nlogn)。使用贪心算法+二分查找

完全平方数

发表于 2019-12-27 更新于 2019-12-28 分类于 leetcode

完全平方数（难度：中等）

方法一：动态规划

dp[i]表示i最少可以由几个平方数构成。

初试化dp=[0,1,2,..., n]，长度为n+1，最多次数就是全由1构成。

遍历dp，对于i，遍历区间[1,n]：

遍历所有平方数小于i的数j，遍历区间[1, sqrt(i)]

动态转移方程：

dp[i] = min(dp[i], dp[i - j * j]+1)，i表示当前数字，j*j表示平方数

复杂度

时间复杂度：O(n*sqrt(n))

空间复杂度：O(n)

代码

class Solution {
    public int numSquares(int n) {
        int[] dp = new int[n+1]; //dp[i]存放的是i最少可以由几个平方数构成， 初始化为[0,1,...,n]
        for(int i = 1; i <= n; i++){
            dp[i] = i;
            for(int j = 1; i-j*j >= 0; j++){
                dp[i] = Math.min(dp[i], dp[i-j*j]+1);
            }
        }
        return dp[n];
    }
}

方法二：广度优先搜索（BFS）

乘积最大子序列

发表于 2019-12-26 分类于 leetcode

乘积最大子序列（难度：中等）

注意：不能只保存到当前为止的最大值，还需保存到当前为止的最小值，因为若下一个数是负数，那么以前的最小值（若为负数）会变成现在的最大值.

代码

class Solution {
    public int maxProduct(int[] nums) {
        int imax = nums[0], imin = nums[0];
        int ans = nums[0];
        for(int i = 1; i < nums.length; i++){
            if(nums[i]<0){
                int temp = imin;
                imin = imax;
                imax = temp;
            }
            imax = Math.max(imax*nums[i], nums[i]);
            imin = Math.min(imin*nums[i], nums[i]);
            ans = Math.max(ans,imax);
        }
        return ans;
    }
}

链表中的下一个更大节点

发表于 2019-12-26 分类于 leetcode

链表中的下一个更大节点（难度：中等）

方法：单调栈

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public int[] nextLargerNodes(ListNode head) {
        Stack<Integer> stack = new Stack<>();
        int[] arr = new int[10000];
        int[] arr2 = new int[10000];

        int length = 0;

        while(head != null){
            // 栈里存放索引
            arr2[length] = head.val;
            while(!stack.empty() && arr2[stack.peek()] < head.val){
                arr[stack.pop()] = head.val;
            }
            stack.push(length);
            head = head.next;
            length++;
        }

        int res[] = new int[length];
        for(int i = 0; i<length; i++){
            res[i] = arr[i];
        }
        return res;
    }
}

下一个更大元素2

发表于 2019-12-26 分类于 leetcode

下一个更大元素2（难度：中等）

方法：单调栈

思路

转自：

作者：labuladong 链接：https://leetcode-cn.com/problems/next-greater-element-ii/solution/dan-diao-zhan-jie-jue-next-greater-number-yi-lei-2/ 来源：力扣（LeetCode）

同样是 Next Greater Number，现在假设给你的数组是个环形的，如何处理？

首先，计算机的内存都是线性的，没有真正意义上的环形数组，但是我们可以模拟出环形数组的效果，一般是通过 % 运算符求模（余数），获得环形特效：

int[] arr = {1,2,3,4,5};
int n = arr.length, index = 0;
while (true) {
    print(arr[index % n]);
    index++;
}

回到 Next Greater Number 的问题，增加了环形属性后，问题的难点在于：这个 Next 的意义不仅仅是当前元素的右边了，有可能出现在当前元素的左边。

我们可以考虑这样的思路：将原始数组 “翻倍”，就是在后面再接一个原始数组，这样的话，按照之前“比身高”的流程，每个元素不仅可以比较自己右边的元素，而且也可以和左边的元素比较了。

复杂度

时间复杂度：O(n)

空间复杂度：O(n)

代码

class Solution {
    public int[] nextGreaterElements(int[] nums) {
        int n = nums.length;
        Stack<Integer> stack = new Stack<>();
        int[] res = new int[nums.length];

        for(int i = 2*n-1; i >= 0; i--){ // i从2*n-1开始
            while(!stack.empty() && stack.peek() <= nums[i%n]){
                stack.pop();
            }
            res[i%n] = stack.empty() ? -1 : stack.peek();
            stack.push(nums[i%n]);
        }
        return res;
    }
}