LeetCode刷題第八九十周

来源:https://www.cnblogs.com/noviceprogrammeroo/archive/2023/01/11/17009207.html
-Advertisement-
Play Games

Image模塊是PIL最基本的模塊，其中導出了Image類，一個Image類實例對象就對應了一副圖像。同時，Image模塊還提供了很多有用的函數。本文只是初步學習了一些用法與實際操作。 ...


509、斐波那契數

class Solution {
    public int fib(int n) {
        // 方法一：遞歸
        // if(n==0){
        //     return 0;
        // }else if(n==1){
        //     return 1;
        // }else{
        //     return fib(n-1)+fib(n-2);
        // }
        // 方法二：動態規劃
        if(n<=1) return n;
        int[] dp = new int[2];
        dp[0] = 0;
        dp[1] = 1;
        int sum = 0;;
        for(int i = 2; i <= n; i++){
            sum = dp[0] + dp[1];
            dp[0] = dp[1];
            dp[1] = sum;
        }
        return dp[1];
    }
}

70、爬樓梯

class Solution {
    public int climbStairs(int n) {
        if(n==1) return n;
        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 2;
        for(int i = 3; i <= n; i++){
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
}

746、使用最小花費爬樓梯

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int[] dp = new int[cost.length + 1];
        dp[0] = 0;
        dp[1] = 0;
        for(int i = 2; i <= cost.length; i++){
            dp[i] = Math.min(dp[i - 1] + cost[i - 1],dp[i - 2] + cost[i - 2]);
        }
        return dp[cost.length];
    }
}

62、 不同路徑

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        dp[0][0] = 1;
        for(int i = 1; i < m; i++){
            dp[i][0] = 1;
        }
        for(int j = 1; j < n; j++){
            dp[0][j] = 1;
        }
        for(int i = 1; i < m; i++){
            for(int j = 1; j < n; j++){
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];

    }
}

63、不同路徑 II

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        int[][] dp = new int[m][n];
        if(obstacleGrid[0][0] == 1){
            return 0;
        }else{
            dp[0][0] = 1;
        }
        for(int i = 1; i < m; i++){
            if(obstacleGrid[i][0] == 1){
                break;
            }else{
                dp[i][0] = 1;
            }
        }
        for(int j = 1; j < n; j++){
            if(obstacleGrid[0][j] == 1){
                break;
            }else{
                dp[0][j] = 1;
            }
        }
        for(int i = 1; i < m; i++){
            for(int j = 1; j < n; j++){
                if(obstacleGrid[i][j] == 1){
                    continue;
                }else{
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                } 
            }
        }
        return dp[m - 1][n - 1];
    }
}

343、整數拆分

class Solution {
    public int integerBreak(int n) {
        // 方法一：貪心
        // if(n == 2){
        //     return 1;
        // }else if(n == 3){
        //     return 2;
        // }
        // int result = 1;
        // while(n > 0){
        //     if(n > 4){
        //         result *= 3;
        //         n = n - 3;
        //     }else if(n == 4){
        //         result *= 4;
        //         break;
        //     }else if(n == 3 || n == 2){
        //         result *= n;
        //         break;
        //     }
        // }
        // return result;
        // 方法二：動態規劃
        int[] dp = new int[n + 1];
        dp[2] = 1;
        for(int i = 3; i <= n; i++){
            for(int j = 1; j <= i - j; j++){
                dp[i] = Math.max(dp[i],Math.max(j*(i - j),j*dp[i - j]));
            }
        }
        return dp[n];
    }
}

96、不同的二叉搜索樹

class Solution {
    public int numTrees(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        for(int i = 2; i <= n; i++){
            for(int j = 1; j <= i; j++){
                dp[i] += dp[j - 1] * dp[i - j];
            }
        }
        return dp[n];
    }
}

416、分割等和子集

class Solution {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for(int i = 0; i < nums.length; i++){
            sum += nums[i];
        }
        if(sum%2==1){
            return false;
        }else{
            sum = sum/2;
        }
        Arrays.sort(nums);
        int[][] dp = new int[nums.length][sum + 1];
        for(int i = nums[0]; i <= sum; i++){
            dp[0][i] = nums[0];
        }
        for(int i = 1; i < nums.length; i++){
            for(int j = 1; j <= sum; j++){
                if(nums[i] > j){
                    dp[i][j] = dp[i - 1][j];
                }else{
                    dp[i][j] = Math.max(dp[i - 1][j], nums[i] + dp[i - 1][j - nums[i]]);
                }
            }
        }
        return dp[nums.length - 1][sum] == sum;
    }
}

1049、最後一塊石頭的重量 II

class Solution {
    public int lastStoneWeightII(int[] stones) {
        int target = 0;
        for(int i : stones){
            target += i;
        }
        int sum = target/2;
        int[][] dp = new int[stones.length][sum + 1];
        for(int i = stones[0]; i <= sum; i++){
            dp[0][i] = stones[0];
        }
        for(int i = 1; i < stones.length; i++){
            for(int j = 1; j <= sum; j++){
                if(j < stones[i]){
                    dp[i][j] = dp[i - 1][j];
                }else{
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - stones[i]] + stones[i]);
                }
            }
        }
        return target - 2 * dp[stones.length - 1][sum];
    }
}

494、目標和

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        for(int i:nums){
            sum += i;
        }
        if(Math.abs(target) > sum) return 0;
        if((sum + target) % 2 == 1) return 0;
        int bageSize = (sum + target) / 2;
        int[] dp = new int[bageSize + 1];
        dp[0] = 1;
        for(int i = 0; i < nums.length; i++){
            for(int j = bageSize; j >= nums[i]; j--){
                dp[j] += dp[j - nums[i]];
            }
        }
        return dp[bageSize];
    }
}

474、一和零

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        int[][] dp = new int[m + 1][n + 1];
        for(String str : strs){
            int zeroNum = 0;
            int oneNum = 0;
            for(char c: str.toCharArray()){
                if(c == '0'){
                    zeroNum++;
                }else{
                    oneNum++;
                } 
            }
            for(int i = m; i >= zeroNum; i--){
                for(int j = n; j >= oneNum; j--){
                    dp[i][j] = Math.max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
                }
            }
        }
        return dp[m][n];
    }
}

518、 零錢兌換 II

class Solution {
    public int change(int amount, int[] coins) {
        int[] dp = new int[amount + 1];
        dp[0] = 1;
        for(int i = 0; i < coins.length; i++){
            for(int j = coins[i]; j <= amount; j++){
                dp[j] += dp[j - coins[i]];
            }
        }
        return dp[amount];
    }
}

377、組合總和 Ⅳ

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

322、零錢兌換

class Solution {
    public int coinChange(int[] coins, int amount) {
        int max = Integer.MAX_VALUE;
        int[] dp = new int[amount + 1];
        for(int i = 0; i < dp.length; i++){
            dp[i] = max;
        }
        dp[0] = 0;
        for(int i = 0; i <= amount; i++){
            for(int j = 0; j < coins.length; j++){
                if(i >= coins[j] && dp[i - coins[j]] != max){
                    dp[i] = Math.min(dp[i - coins[j]] + 1, dp[i]);
                }
            }
        }
        return dp[amount]==max?-1:dp[amount];
    }
}

279、完全平方數

class Solution {
    public int numSquares(int n) {
        // 創建物品
        int length = (int)Math.floor(Math.sqrt(n));
        int[] nums = new int[length];
        for(int i = 0; i < length; i++){
            nums[i] = (i + 1) * (i + 1);
        }
        int[] dp = new int[n + 1];
        int max = Integer.MAX_VALUE;
        for(int j = 0; j < dp.length; j++){
            dp[j] = max;
        }
        dp[0] = 0;
        for(int i = 0; i < nums.length; i++){
            for(int j = nums[i]; j <= n; j++){
                dp[j] = Math.min(dp[j], dp[j - nums[i]] + 1);
            }
        }
        return dp[n];
    }
}

139、單詞拆分

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        HashSet<String> set = new HashSet<>(wordDict);
        boolean[] valid = new boolean[s.length() + 1];
        valid[0] = true;
        for(int i = 1; i <= s.length(); i++){
            for(int j = 0; j < i && !valid[i]; j++){
                if(set.contains(s.substring(j, i)) && valid[j]){
                    valid[i] = true;
                }
            }
        }
        return valid[s.length()];
    }
}

198、打家劫舍

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

213、打家劫舍 II

class Solution {
    public int rob(int[] nums) {
        if(nums.length == 1) return nums[0];
        return Math.max(robAction(nums, 0, nums.length - 2), robAction(nums, 1, nums.length - 1));
    }
    public int robAction(int[] nums, int start, int end){
        if(start == end) return nums[start];
        int[] dp = new int[nums.length];
        dp[start] = nums[start];
        dp[start + 1] = Math.max(dp[start], nums[start + 1]);
        for(int i = start + 2; i <= end; i++){
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
        }
        return dp[end];
    }
}

337、打家劫舍 III

class Solution {
    public int rob(TreeNode root) {
// 後序遍歷
        int[] res = robAction(root);
        return Math.max(res[0], res[1]);
    }
    public int[] robAction(TreeNode root){
        int[] res = new int[2];
        if(root == null) return res;
        int[] left = robAction(root.left);
        int[] right = robAction(root.right);
        res[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        res[1] = root.val + left[0] + right[0];
        return res;
    }
}

121、買賣股票的最佳時機

class Solution {
    public int maxProfit(int[] prices) {
        int len = prices.length;
        if(len == 1) return 0;
        int[][] dp = new int[len][2];
        dp[0][0] = -prices[0];
        dp[0][1] = 0;
        for(int i = 1; i < len; i++){
            dp[i][0] = Math.max(dp[i - 1][0], -prices[i]);
            dp[i][1] = Math.max(dp[i - 1][0] + prices[i], dp[i - 1][1]);
        }
        return dp[len - 1][1];
    }
}

122、買賣股票的最佳時機 II

class Solution {
    public int maxProfit(int[] prices) {
        // 貪心
        // int max = 0;
        // for(int i = 1; i < prices.length; i++){
        //     if(prices[i] > prices[i - 1]){
        //         max += prices[i] - prices[i - 1];
        //     }
        // }
        // return max;
        // 動態規劃
        int len = prices.length;
        if(len == 1) return 0;
        int[][] dp = new int[len][2];
        dp[0][0] = -prices[0];
        dp[0][1] = 0;
        for(int i = 1; i < len; i++){
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] -prices[i]);
            dp[i][1] = Math.max(dp[i - 1][0] + prices[i], dp[i - 1][1]);
        }
        return dp[len - 1][1];
    }
}

123、買賣股票的最佳時機 III

class Solution {
    public int maxProfit(int[] prices) {
        int len = prices.length;
        int[][] dp = new int[len][5];
        dp[0][1] = -prices[0];
        dp[0][3] = -prices[0];
        for(int i = 1; i < len; i++){
            dp[i][1] = Math.max(-prices[i], dp[i - 1][1]);
            dp[i][2] = Math.max(dp[i - 1][1] + prices[i], dp[i - 1][2]);
            dp[i][3] = Math.max(dp[i - 1][2] - prices[i], dp[i - 1][3]);
            dp[i][4] = Math.max(dp[i - 1][3] + prices[i], dp[i - 1][4]);
        }
        return dp[len - 1][4];
    }
}

188、買賣股票的最佳時機 IV

class Solution {
    public int maxProfit(int k, int[] prices) {
        int len = prices.length;
        int[][] dp = new int[len][1 + 2 * k];
        for(int i = 1; i < 1 + 2 * k; i = i + 2){
            dp[0][i] = -prices[0];
        }
        for(int i = 1; i < len; i++){
            for(int j = 1; j < 1 + 2 * k; j++){
                if(j == 1){
                    dp[i][j] = Math.max(-prices[i], dp[i - 1][1]);
                }else if(j%2==0){
                    dp[i][j] = Math.max(dp[i - 1][j - 1] + prices[i], dp[i - 1][j]);
                }else{
                    dp[i][j] = Math.max(dp[i - 1][j - 1] - prices[i], dp[i - 1][j]);
                }
            }
        }
        return dp[len - 1][2 * k];
    }
}

309、最佳買賣股票時機含冷凍期

class Solution {
    public int maxProfit(int[] prices) {
        int len = prices.length;
        if(len == 1) return 0;
        int[][] dp = new int[len][4];
        dp[0][0] = -prices[0];
        for(int i = 1; i < len; i++){
            dp[i][0] = Math.max(dp[i - 1][0], Math.max(dp[i - 1][1], dp[i - 1][3]) - prices[i]);
            dp[i][1] = Math.max(dp[i - 1][3], dp[i - 1][1]);
            dp[i][2] = dp[i - 1][0] + prices[i];
            dp[i][3] = dp[i - 1][2];
        }
        return Math.max(dp[len - 1][1], Math.max(dp[len - 1][2], dp[len - 1][3]));
    }
}

714、買賣股票的最佳時機含手續費

class Solution {
    public int maxProfit(int[] prices, int fee) {
        // 貪心
        // if(prices.length==1){
        //     return 0;
        // }
        // int index = prices[0]+fee;
        // int sum=0;
        // for(int i = 1; i < prices.length; i++){
        //     if(prices[i]>index){
        //         sum+=prices[i]-index;
        //         index=prices[i];
        //     }else if(prices[i]+fee<index){
        //         index=prices[i]+fee;
        //     }
        // }
        // return sum;
        // 動態規劃
        int len = prices.length;
        if(len == 1) return 0;
        int[][] dp = new int[len][2];
        dp[0][0] = -prices[0];
        dp[0][1] = 0;
        for(int i = 1; i < len; i++){
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] -prices[i]);
            dp[i][1] = Math.max(dp[i - 1][0] + prices[i] - fee, dp[i - 1][1]);
        }
        return Math.max(dp[len - 1][1],dp[len - 1][0]);
    }
}

300、最長遞增子序列

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

674、最長連續遞增序列

class Solution {
    public int findLengthOfLCIS(int[] nums) {
        int[] dp = new int[nums.length];
        Arrays.fill(dp,1);
        int result = 1;
        int index = 0;
        for(int i = 1; i < nums.length; i++){
            index = nums[i];
            for(int j = i - 1; j >= 0; j--){
                if(index <= nums[j]){
                    break;
                }else{
                    dp[i] = dp[i] + 1;
                    index = nums[j];
                }
            }
            if(dp[i] > result) result = dp[i];
        }
        return result;
    }
}

718、最長重覆子數組

class Solution {
    public int findLength(int[] nums1, int[] nums2) {
        int[][] dp = new int[nums1.length + 1][nums2.length + 1];
        int result = 0;
        for(int i = 1; i <= nums1.length; i++){
            for(int j = 1; j <= nums2.length; j++){
                if(nums1[i - 1] == nums2[j - 1]){
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }
            if(dp[i][j] > result) result = dp[i][j];
            }
        }
        return result;
    }
}

1143、最長公共子序列

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        char[] nums1 = text1.toCharArray();
        char[] nums2 = text2.toCharArray();
        int[][] dp = new int[nums1.length + 1][nums2.length + 1];
        int result = 0;
        for(int i = 1; i <= nums1.length; i++){
            for(int j = 1; j <= nums2.length; j++){
                if(nums1[i - 1] == nums2[j - 1]){
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }else{
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            if(dp[i][j] > result) result = dp[i][j];
            }
        }
        return result;
    }
}

1035、不相交的線

class Solution {
    public int maxUncrossedLines(int[] nums1, int[] nums2) {
        int[][] dp = new int[nums1.length + 1][nums2.length + 1];
        int result = 0;
        for(int i = 1; i <= nums1.length; i++){
            for(int j = 1; j <= nums2.length; j++){
                if(nums1[i - 1] == nums2[j - 1]){
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }else{
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            if(dp[i][j] > result) result = dp[i][j];
            }
        }
        return result;
    }
}

53、最大子數組和

class Solution {
    public int maxSubArray(int[] nums) {
        // 貪心
        // if(nums.length == 1){
        //     return nums[0];
        // }
        // int count = 0;
        // int sum = Integer.MIN_VALUE;
        // for(int i = 0; i < nums.length; i++){
        //     count += nums[i];
        //     sum = Math.max(sum, count);
        //     if(count <= 0){
        //         count = 0;
        //     }
        // }
        // return sum;
        // 動態規劃
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        int result = nums[0];
        for(int i = 1; i < nums.length; i++){
            dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
            result = dp[i] > result ? dp[i] : result;
        }
        return result;
    }
}

392、 判斷子序列

class Solution {
    public boolean isSubsequence(String s, String t) {
        char[] nums1 = s.toCharArray();
        char[] nums2 = t.toCharArray();
        int[][] dp = new int[nums1.length + 1][nums2.length + 1];
        int result = 0;
        for(int i = 1; i <= nums1.length; i++){
            for(int j = 1; j <= nums2.length; j++){
                if(nums1[i - 1] == nums2[j - 1]){
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }else{
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            if(dp[i][j] > result) result = dp[i][j];
            }
        }
        return result == s.length();
    }
}

115、不同的子序列

class Solution {
    public int numDistinct(String s, String t) {
        char[] nums1 = s.toCharArray();
        char[] nums2 = t.toCharArray();
        int[][] dp = new int[nums1.length + 1][nums2.length + 1];
        for(int i = 0; i < nums1.length; i++){
            dp[i][0] = 1;
        }
        for(int i = 1; i <= nums1.length; i++){
            for(int j = 1; j <= nums2.length; j++){
                if(nums1[i - 1] == nums2[j - 1]){
                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
                }else{
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[nums1.length][nums2.length];
    }
}

583、兩個字元串的刪除操作

class Solution {
    public int minDistance(String word1, String word2) {
        char[] nums1 = word1.toCharArray();
        char[] nums2 = word2.toCharArray();
        int[][] dp = new int[nums1.length + 1][nums2.length + 1];
        int result = 0;
        for(int i = 1; i <= nums1.length; i++){
            for(int j = 1; j <= nums2.length; j++){
                if(nums1[i - 1] == nums2[j - 1]){
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }else{
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            if(dp[i][j] > result) result = dp[i][j];
            }
        }
        return word1.length() + word2.length() - 2 * result;
    }
}

72、編輯距離

class Solution {
    public int minDistance(String word1, String word2) {
        char[] nums1 = word1.toCharArray();
        char[] nums2 = word2.toCharArray();
        int[][] dp = new int[nums1.length + 1][nums2.length + 1];
        int result = 0;
        for(int i = 0; i <= nums1.length; i++){
            dp[i][0] = i;
        }
        for(int i = 0; i <= nums2.length; i++){
            dp[0][i] = i;
        }
        for(int i = 1; i <= nums1.length; i++){
            for(int j = 1; j <= nums2.length; j++){
                if(nums1[i - 1] == nums2[j - 1]){
                    dp[i][j] = dp[i - 1][j - 1];
                }else{
                    dp[i][j] = Math.min(dp[i - 1][j], Math.min(dp[i][j - 1], dp[i - 1][j - 1])) + 1;;
                }
            }
        }
        return dp[nums1.length][nums2.length];
    }
}

647、迴文子串

class Solution {
    public int countSubstrings(String s) {
        boolean[][] dp = new boolean[s.length()][s.length()];
        for(int i = s.length() - 1; i >= 0; i--){
            for(int j = i; j < s.length(); j++){
                if(s.charAt(i) == s.charAt(j)){
                    if(j - i < 3){
                        dp[i][j] = true;
                    }else{
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }else{
                    dp[i][j] = false;
                }
            }
        }
        int count = 0;
        for (int i = 0; i < s.length(); i++) {
            for (int j = 0; j < s.length(); j++) {
                if (dp[i][j]) count++;
            }
        }
        return count;
    }
}

516、最長迴文子序列

class Solution {
    public int longestPalindromeSubseq(String s) {
        int[][] dp = new int[s.length() + 1][s.length() + 1];
        int result = 1;
        for(int i = s.length() - 1; i >= 0; i--){
            dp[i][i] = 1;
            for(int j = i + 1; j < s.length(); j++){
                if(s.charAt(i) == s.charAt(j)){
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                }else{
                    dp[i][j] = Math.max(dp[i][j], Math.max(dp[i + 1][j], dp[i][j - 1]));
                }
                result = result > dp[i][j] ? result : dp[i][j];
            }
        }
        return result;
    }
}

739、每日溫度

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int lens = temperatures.length;
        int[] res = new int[lens];
        Stack<Integer> stack = new Stack<>();
        stack.push(0);
        for(int i = 1; i < lens; i++){
            if(temperatures[i] <= temperatures[stack.peek()]){
                stack.push(i);
            }else{
                while(!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]){
                    int temp = stack.pop();
                    res[temp] = i - temp;
                }
                stack.push(i);
            }
        }
        return res;
    }
}

496、下一個更大元素 I

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int lens = nums1.length;
        int[] res = new int[lens];
        Arrays.fill(res,-1);
        Stack<Integer> stack = new Stack<>();
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        for (int i = 0 ; i< nums1.length ; i++){
            hashMap.put(nums1[i],i);
        }
        stack.push(0);
        for(int i = 1; i < nums2.length; i++){
            if(nums2[i] <= nums2[stack.peek()]){
                stack.push(i);
            }else{
                while(!stack.isEmpty() && nums2[i] > nums2[stack.peek()]){
                    if (hashMap.containsKey(nums2[stack.peek()])){
                        Integer index = hashMap.get(nums2[stack.peek()]);
                        res[index] = nums2[i];
                    }
                    stack.pop();
                }
                stack.push(i);
            }
        }
        return res;
    }
}

503、下一個更大元素 II

class Solution {
    public int[] nextGreaterElements(int[] nums) {
        int lens = nums.length;
        int[] res = new int[lens];
        Arrays.fill(res,-1);
        Stack<Integer> stack = new Stack<>();
        stack.push(0);
        for(int i = 1; i < 2*lens; i++){
            if(nums[i%lens] <= nums[stack.peek()]){
                stack.push(i%lens);
            }else{
                while(!stack.isEmpty() && nums[i%lens] > nums[stack.peek()]){
                    int temp = stack.pop();
                    res[temp] = nums[i%lens];
                }
                stack.push(i%lens);
            }
        }
        return res;
    }
}

[42]
[84]


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 單向綁定vs雙向綁定、單向數據流vs雙向數據流
    參考文章：http://www.qb5200.com/article/482839.html 單雙向綁定指的是View層跟Model層之間的映射關係 單向綁定vs雙向綁定 react採用單向綁定，vue採用單向綁定和雙向綁定。 在React中Veiw發生改變，用戶通過發生Actions進行處理，Ac ...
  • UnoCSS 簡化 CSS 的書寫，Nice！
    CSS 樣式太多，重覆寫 在學習 UnoCSS 之前，我提出幾個問題： 你是否有過寫完了 HTML 之後，跳轉到 style 寫 CSS 這樣來回跳轉的痛苦？ 你是否有過不知道如何給節點取類名的痛苦（有的節點確實沒啥必要取類名，但就是需要寫 CSS）？ 你是否有過管理重覆、繁雜、繁多的 CSS 而痛 ...
  • JavaScript 圖像壓縮
    JavaScript 可以使用類似於 canvas 和 web workers 來實現圖像壓縮。 使用 canvas，可以將圖像繪製到 canvas 上，然後使用 canvas 提供的 toBlob() 或 toDataURL() 方法將其轉換為不同格式的圖像。在這些方法中指定圖像質量參數即可實現壓... ...
  • H5直播技術起航
    視頻格式就是通常所說的.mp4,.flv,.ogv,.webm等。簡單來說，它其實就是一個盒子，用來將實際的視頻流以一定的順序放入，確保播放的有序和完整性。 ...
  • MySql樹形結構（多級菜單）查詢設計方案
    電銷是什麼？就是坐席拿著電話給客戶打電話嗎？no no no，讓我們一起走進京音平臺之電銷系統。 京音平臺2020年初開始建設，過去的兩年多的時間里，經歷了跌宕起伏，有經驗、有教訓，整體來說平臺經歷了人工、自動化階段，目前處於初步智能化階段，希望可以將過去的一些心路歷程分享給大家，共同交流、共同進... ...
  • C++ 使用 new 創建二維數組
    1. 直接創建 C++ 使用 new 創建二維數組最直接的方法就是 new T[M][N]。返回的指針類型是 T (*)[N]，它是指向數組的指針，可以直接使用數組下標形式訪問元素。釋放記憶體直接使用delete[]。示例代碼： #include <iostream> class A { public ...
  • 代碼隨想錄演算法訓練營day01 | leetcode 704/27
    前言 考研結束半個月了，自己也簡單休整了一波，估了一下分，應該能進覆試，但還是感覺不夠托底。不管怎樣，要把代碼能力和八股撿起來了，正好看到卡哥有這個演算法訓練營，遂果斷參加，為機試和日後求職打下一個基礎。 我之前斷斷續續地刷過一些LeetCode，但是不成體系，數量也少得可憐，才區區50+，在尋找暑期 ...
  • P2448 無盡的生命
    題目傳送門 題意簡述 看到題目顯而易見是求逆序對個數。 思路分析 看到數據範圍 $x_i,y_i \le 2^{31}-1$，$k \le 10^5$。數據值域大但是個數少，且與數據之間的大小關係有關，因此考慮離散化。 離散化簡單介紹 離散化實際就是一種映射，當數據值域過大而個數有限時，可以嘗試離散 ...
一周排行
    -Advertisement-
    Play Games
  • UOS 開啟 VisualStudio 遠程調試 .NET 應用之旅
    前言 在我們開發過程中基本上不可或缺的用到一些敏感機密數據，比如SQL伺服器的連接串或者是OAuth2的Secret等，這些敏感數據在代碼中是不太安全的，我們不應該在源代碼中存儲密碼和其他的敏感數據，一種推薦的方式是通過Asp.Net Core的機密管理器。 機密管理器 在 ASP.NET Core ...
  • C# - 能否讓 SortedSet.RemoveWhere 內傳入的委托非同步執行
    新改進提供的Taurus Rpc 功能，可以簡化微服務間的調用，同時可以不用再手動輸出模塊名稱，或調用路徑，包括負載均衡，這一切，由框架實現並提供了。新的Taurus Rpc 功能，將使得服務間的調用，更加輕鬆、簡約、高效。 ...
  • 順序棧的介面程式
    順序棧的介面程式 目錄順序棧的介面程式頭文件創建順序棧入棧出棧利用棧將10進位轉16進位數驗證 頭文件 #include <stdio.h> #include <stdbool.h> #include <stdlib.h> 創建順序棧 // 指的是順序棧中的元素的數據類型，用戶可以根據需要進行修改 ...
  • mORMot2 獲取數據集1
    前言 整理這個官方翻譯的系列，原因是網上大部分的 tomcat 版本比較舊，此版本為 v11 最新的版本。 開源項目 從零手寫實現 tomcat minicat 別稱【嗅虎】心有猛虎，輕嗅薔薇。 系列文章 web server apache tomcat11-01-官方文檔入門介紹 web serv ...
  • 萬字長文總結與剖析C語言關鍵字 -- <<C語言深度解剖>>
    C總結與剖析:關鍵字篇 -- <<C語言深度解剖>> 目錄C總結與剖析:關鍵字篇 -- <<C語言深度解剖>>程式的本質:二進位文件變數1.變數:記憶體上的某個位置開闢的空間2.變數的初始化3.為什麼要有變數4.局部變數與全局變數5.變數的大小由類型決定6.任何一個變數,記憶體賦值都是從低地址開始往高地 ...
  • 【Flink入門修煉】2-3 Flink Checkpoint 原理機制
    如果讓你來做一個有狀態流式應用的故障恢復，你會如何來做呢？ 單機和多機會遇到什麼不同的問題？ Flink Checkpoint 是做什麼用的？原理是什麼？ ...
  • C++ 多級繼承與多重繼承：代碼組織與靈活性的平衡
    C++ 多級繼承 多級繼承是一種面向對象編程（OOP）特性，允許一個類從多個基類繼承屬性和方法。它使代碼更易於組織和維護，並促進代碼重用。 多級繼承的語法 在 C++ 中，使用 : 符號來指定繼承關係。多級繼承的語法如下： class DerivedClass : public BaseClass1 ...
  • 圖文結合手把手教你創建SpringCloud項目
    前言 什麼是SpringCloud？ Spring Cloud 是一系列框架的有序集合，它利用 Spring Boot 的開發便利性簡化了分散式系統的開發，比如服務註冊、服務發現、網關、路由、鏈路追蹤等。Spring Cloud 並不是重覆造輪子，而是將市面上開發得比較好的模塊集成進去，進行封裝，從 ...
  • 類模板的常見用法
    class_template 類模板和函數模板的定義和使用類似，我們已經進行了介紹。有時，有兩個或多個類，其功能是相同的，僅僅是數據類型不同。類模板用於實現類所需數據的類型參數化 template<class NameType, class AgeType> class Person { publi ...
  • system-v IPC共用記憶體通信
    目錄system v IPC簡介共用記憶體需要用到的函數介面shmget函數--獲取對象IDshmat函數--獲得映射空間shmctl函數--釋放資源共用記憶體實現思路註意 system v IPC簡介 消息隊列、共用記憶體和信號量統稱為system v IPC(進程間通信機制)，V是羅馬數字5，是UNI ...
所有分類