力扣面试150题--爬楼梯 打家劫舍 零钱兑换 最长递增子序列

Day 97

题目描述

思路

斐波那契不多说了

class Solution {
    public int climbStairs(int n) {
     if(n == 1){return 1;}
        if(n == 2){return 2;}
        int a = 1, b = 2, temp;
        for(int i = 3; i <= n; i++){
            temp = a;
            a = b;
            b = temp + b;
        }
        return b;   
    }
}

题目描述

思路

递推公式：nums[i]=Math.max(nums[i-1],nums[i-2]+nums[i]);

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

题目描述

思路

初次思路：

class Solution {
    public int coinChange(int[] coins, int amount) {
        if(amount==0){
            return 0;
        }
        Arrays.sort(coins);
        int[]num=new int[amount+1];
        int min=coins[0];
        for(int i=0;i<coins.length;i++){
        if(coins[i]<=amount){
            num[coins[i]]=1;//将表中只需要一张的设置为1
            if(coins[i]<min){
                min=coins[i];//找到最小的面值
            }
        }
        }
        if(amount<min){
            return -1;
        }
        for(int i=min+1;i<num.length;i++){
            int y=0;
            if(num[i]>0){
                continue;
            }
            int les=100000;
            for(int j=0;j<coins.length;j++){
                if(i-coins[j]<=0){
                    break;
                }
                else if(num[i-coins[j]]==0){
                    continue;
                }
                else{
                    y=num[i-coins[j]]+1;
                }

                if(y<les){
                    les=y;
                }
            }
            num[i]=les;
        }
        if(num[amount]==0||num[amount]==100000){
            num[amount]=-1;
        }
        return num[amount];

    }
}

题解思路：其实和我做法差不多，但是这样会省略很多没必要计算的金额

public class Solution {
    public int coinChange(int[] coins, int amount) {
        if (amount < 1) {
            return 0;
        }
        return coinChange(coins, amount, new int[amount]);
    }

    private int coinChange(int[] coins, int rem, int[] count) {
        if (rem < 0) {
            return -1;
        }
        if (rem == 0) {
            return 0;
        }
        if (count[rem - 1] != 0) {
            return count[rem - 1];
        }
        int min = Integer.MAX_VALUE;
        for (int coin : coins) {
            int res = coinChange(coins, rem - coin, count);
            if (res >= 0 && res < min) {
                min = 1 + res;
            }
        }
        count[rem - 1] = (min == Integer.MAX_VALUE) ? -1 : min;
        return count[rem - 1];
    }
}

题目描述

思路

初次思路：

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

题解思路（进阶）：贪心加二分查找

class Solution {
    public int lengthOfLIS(int[] nums) {
        // len 表示当前找到的最长递增子序列的长度
        int len = 1;
        // n 是数组的长度
        int n = nums.length;
        
        // 特殊情况：如果数组为空，直接返回0
        if (n == 0) {
            return 0;
        }
        
        // d 数组的含义：d[i] 代表「长度为i的递增子序列的最小末尾元素」
        // 注意：d数组的索引从1开始（d[1]对应长度1的子序列），所以长度设为n+1
        int[] d = new int[n + 1];
        // 初始化：第一个元素自己构成长度为1的子序列，所以d[1] = nums[0]
        d[len] = nums[0];
        
        // 从数组的第二个元素开始遍历（i从1到n-1）
        for (int i = 1; i < n; ++i) {
            // 情况1：当前元素比「最长子序列的末尾元素」大
            // 说明可以直接把当前元素接在后面，形成更长的子序列
            if (nums[i] > d[len]) {
                // 最长长度+1
                len++;
                // 更新d数组：长度为len的子序列，末尾元素是当前元素
                d[len] = nums[i];
            } else {
                // 情况2：当前元素不能直接接在最长子序列后面
                // 此时需要用二分查找，找到d数组中「小于当前元素的最大位置pos」
                // 然后用当前元素替换d[pos+1]（优化子序列的末尾元素）
                int l = 1;          // 二分查找的左边界（d数组的有效起始索引）
                int r = len;        // 二分查找的右边界（当前最长长度）
                int pos = 0;        // 记录找到的位置（初始为0，防止找不到的情况）
                
                // 二分查找过程
                while (l <= r) {
                    // 计算中间位置（等价于(l+r)/2，位运算更快）
                    int mid = (l + r) >> 1;
                    // 如果d[mid] < 当前元素，说明可以尝试更长的子序列
                    if (d[mid] < nums[i]) {
                        pos = mid;       // 更新pos为mid（暂时记录这个位置）
                        l = mid + 1;     // 向右查找，看看有没有更大的位置
                    } else {
                        // 如果d[mid] >= 当前元素，说明需要向左查找更小的位置
                        r = mid - 1;
                    }
                }
                
                // 找到pos后，用当前元素替换d[pos+1]
                // 目的是让「长度为pos+1的子序列」的末尾元素尽可能小
                d[pos + 1] = nums[i];
            }
        }
        
        // 最终len就是最长递增子序列的长度
        return len;
    }
}