力扣面试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;//将表中只需要一张的设置为1if(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;// 特殊情况：如果数组为空，直接返回0if (n == 0) {return 0;}// d 数组的含义：d[i] 代表「长度为i的递增子序列的最小末尾元素」// 注意：d数组的索引从1开始（d[1]对应长度1的子序列），所以长度设为n+1int[] 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]) {// 最长长度+1len++;// 更新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;}
}