天天看點
傳回

leetcode——數組系列題型

數組

尋找兩個正序數組的中位數

連結：

https://leetcode-cn.com/problems/median-of-two-sorted-arrays/

 
class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int n1 = nums1.length;
        int n2 = nums2.length;
        int[] nums = new int[n1 + n2];
        System.arraycopy(nums1, 0, nums, 0, n1);
        System.arraycopy(nums2, 0, nums, n1, n2);
        Arrays.sort(nums);
        int n = nums.length;
        if (n % 2 == 0) {
            return (nums[(n/2)-1] + nums[n/2])/2.0;
        } else {
            return nums[n/2];
        }
    }
}

二分查找

https://leetcode-cn.com/problems/binary-search/

 
class Solution {
    public int search(int[] nums, int target) {
        int start = 0;
        int end = nums.length-1;
        int mid = -1;
        while(start <= end){
            mid = (end-start)/2+start;
             if(nums[mid] == target){
                 return mid;
             }
             if(nums[mid] > target){
                 end = mid -1;
             }
             if(nums[mid]<target){
                 start=mid+1;
             }
        }
        return -1;
    }
}

其他

跳躍遊戲

這題應該可以采用動态規劃的思想，但參考了其他方法。

https://leetcode-cn.com/problems/jump-game/

 
class Solution {
    public boolean canJump(int[] nums) {
        if (nums == null){
            return false;
        }
        int k = 0;
        int n =nums.length;//數組的長度
        for(int i = 0; i<n ;i++){
            if(i>k){
                return false;
            }
            k = Math.max(k,i+nums[i]);
        }
        return true;
    }
}

動态規劃

裴波那契數列

https://leetcode-cn.com/problems/fibonacci-number/

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

裴波那契數列的變形題有：

  • 第 N 個泰波那契數(1137):

    https://leetcode-cn.com/problems/n-th-tribonacci-number/
  • 爬樓梯(70):

    https://leetcode-cn.com/problems/climbing-stairs/

打家劫舍——線形

  • https://leetcode-cn.com/problems/Gu0c2T/

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

類似題：

按摩師：

https://leetcode-cn.com/problems/the-masseuse-lcci/

打家劫舍——環形

https://leetcode-cn.com/problems/house-robber-ii/

解法思路：

環狀排列意味着第一個房子和最後一個房子中隻能選擇一個偷竊，是以可以把此環狀排列房間問題約化為兩個單排排列房間子問題：

  • 在不偷竊第一個房子的情況下（即 nums[1:]nums[1:]nums[1:]），最大金額是 p1p_1p1​
  • 在不偷竊最後一個房子的情況下（即 nums[:n−1]nums[:n-1]nums[:n−1]），最大金額是 p2p_2p2​
    • 綜合偷竊最大金額： 為以上兩種情況的較大值，即 max(p1,p2)max(p1,p2)max(p1,p2)

另外，需要特别介紹Java中的Arrays.copyOfRange()方法,要引用 import java.util.Arrays;

  • 這個方法主要是用來進行數組的複用，我遇到這個方法是在遞歸函數的調用中，這個方法比較的普遍，能夠優化代碼的結構。

  • array=Arrays.copyOfRange(oringinal,int from, int to)

     此時要注意下标的變化，

    array

     拷貝

    original

     數組從from下标開始，一直到

    to

     下标結束，注意包含

    from

     下标，不包含

    to

     下标，是左閉右開區間。 
class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        if(n == 0) return 0;
        if(n == 1) return nums[0];
        return Math.max(x_rob(Arrays.copyOfRange(nums, 0, n - 1)),
                       x_rob(Arrays.copyOfRange(nums, 1, nums.length)) );

    }
    public int x_rob(int[] nums) {
        int n =nums.length;
        if(n == 0) return 0;
        if(n == 1) return nums[0];
        int[] arr = new int[n+1];
        arr[0] = nums[0];
        arr[1] = Math.max(nums[0],nums[1]);
        for(int i=2;i<n;i++){
            arr[i] = Math.max(arr[i-1],arr[i-2]+nums[i]);
        }
        return arr[n-1];
    }
}

零錢兌換

https://leetcode-cn.com/problems/coin-change/

思路：

首先：貪心算法未必能拿到最優解

解題的思路是動态規劃：

  • （1）定義數組dp[],其中dp[i]表示金額的最優解，即為組成金額i最少使用的鈔票數量
  • （2）計算金額amount的最優解，則需要dp數組的長度為amount+1，進而表示0到金額amount的最優解
  • （3）最初dp數組所有元素初始化為-1，dp[0]為金額0的最優解初始化為0，完成dp數組的計算後，将金額amount的最優解dp[amount]傳回 
class Solution {
    public int coinChange(int[] coins, int amount) {
        int n = coins.length;
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount+1);
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            for (int j = 0; j < n; j++) {
                if (coins[j] <= i) {
                    dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
                }
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];

    }
}

删除并獲得點數

連結(740)：https://leetcode-cn.com/problems/delete-and-earn/

class Solution {
    public int deleteAndEarn(int[] nums) {
        int n = nums.length;
        if(n == 0) return 0;
        if(n == 1) return nums[0];
        //找出數組裡的最大數
        int max = nums[0];
        for(int i = 1;i<n;i++){
            max = Math.max(max,nums[i]);
        }
        //構造新的數組dp
        int[] sum = new int[ max + 1 ];
        for (int item : nums) {
            sum[item] ++;
        }
        //動态規劃
        int[] dp = new int[max + 1];
        dp[1] = sum[1] * 1;
        dp[2] = Math.max(dp[1], sum[2] * 2);
        for (int i = 2; i <= max; ++i) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + i * sum[i]);
        }
        return dp[max];
    }
}

最大子數組和

連結(53)：

https://leetcode-cn.com/problems/maximum-subarray/

 
class Solution {
    public int maxSubArray(int[] nums) {
        // f(i)=max{f(i−1)+nums[i],nums[i]}
        int n = nums.length;
        //int[] dp = new int[n+1];
        int pre = 0,maxAns = nums[0];
        for(int i = 0;i<n;i++){
            pre = Math.max(pre+nums[i],nums[i]);
            maxAns = Math.max(maxAns,pre);
        }
        return maxAns;
    }
}

買賣股票的最佳時機

連結（121）：

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/

 
class Solution {
    public int maxProfit(int[] prices) {
        if(prices.length <= 1)
            return 0;
        int min = prices[0], max = 0;
        for(int i = 1; i < prices.length; i++) {
            //記錄最小買入值
            min = Math.min(min, prices[i]);
            //記錄利潤最大值
            max = Math.max(max, prices[i] - min);
        }
        return max;
    }
}

最佳觀光組合

連結(1014)：

https://leetcode-cn.com/problems/best-sightseeing-pair/

 
class Solution {
    public int maxScoreSightseeingPair(int[] values) {
        int n = values.length,mx = values[0] + 0,ans = 0;
        for(int j = 1; j < n; j++){
            ans = Math.max(ans , mx + values[j] - j);
            mx = Math.max(mx, values[j] + j);
        }
        return ans;
    }
}
上一篇: 如何解決redis緩存穿透
下一篇: mysql資料庫（8）：獲得資料庫和表的資訊