如果某一问题有很多重叠子问题，使用动态规划是最有效的
解题步骤：
背包问题：01背包，完全背包，多重背包
01背包：
统一使用一维数组来进行遍历
public static void main(String[] args) {
int[] weight = {1, 3, 4};
int[] value = {15, 20, 30};
int bagWight = 4;
testWeightBagProblem(weight, value, bagWight);
}
public static void testWeightBagProblem(int[] weight, int[] value, int bagWeight){
int wLen = weight.length;
//定义dp数组：dp[j]表示背包容量为j时，能获得的最大价值
int[] dp = new int[bagWeight + 1];
//遍历顺序：先遍历物品，再遍历背包容量
for (int i = 0; i < wLen; i++){
for (int j = bagWeight; j >= weight[i]; j--){
dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
//对于组合问题的递推公式为：dp[j] += dp[j - nums[i]]，需要初始化dp[0]=1;
}
}
//打印dp数组
for (int j = 0; j <= bagWeight; j++){
System.out.print(dp[j] + " ");
}
}
完全背包：
01背包和完全背包唯一不同就是体现在遍历顺序上,完全背包的物品是可以添加多次的，所以要从小到大去遍历
// 先遍历物品，再遍历背包
for(int i = 0; i < weight.size(); i++) { // 遍历物品
for(int j = weight[i]; j <= bagWeight ; j++) { // 遍历背包容量
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
//对于组合问题的递推公式为：dp[j] += dp[j - nums[i]]，需要初始化dp[0]=1;
}
}
//对于排列问题，先遍历背包，再遍历物品
dp[0] = 1;
for (int j = 0; j <= amount; j++) { // 遍历背包容量
for (int i = 0; i < coins.size(); i++) { // 遍历物品
if (j - coins[i] >= 0) dp[j] += dp[j - coins[i]];
}
}
509、斐波那契数
class Solution {
public int fib(int n) {
// if(n==1){
// return 1;
// }
// if(n==0){
// return 0;
// }
// return fib(n-1)+fib(n-2);
if(n==1){
return 1;
}
if(n==0){
return 0;
}
int[] dp = new int[n+1];
dp[0] = 0;
dp[1] = 1;
for(int i = 2; i < n+1; i++){
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n];
}
}
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];
dp[0] = 1;
dp[1] = 1;
for(int i = 2; i < n; i++){
int left = 0;
int right = i - 1;
while(left <= right){
dp[i] = Math.max(dp[i],Math.max(left+1,dp[left])*Math.max(right+1,dp[right]));
left++;
right--;
}
}
return dp[n-1];
}
}
96、不同的二叉搜索树
class Solution {
public int numTrees(int n) {
if(n==1){
return 1;
}
int[] dp = new int[n+1];
dp[0] = 1;
dp[1] = 1;
dp[2] = 2;
for(int i = 3; i <= n; i++){
int temp = i-1;
while(temp>=0){
dp[i] += dp[temp]*dp[i-temp-1];
temp--;
}
}
return dp[n];
}
}
416、分割等和子集
class Solution {
public boolean canPartition(int[] nums) {
int sum = 0;
for(int i : nums){
sum += i;
}
if(sum%2==1){
return false;
}
sum=sum/2;
int[] dp = new int[sum+1];
for(int i = 0; i < nums.length; i++){
for(int j = sum; j >= nums[i]; j--){
dp[j] = Math.max(dp[j],dp[j-nums[i]]+nums[i]);
if(dp[j]==sum){
return true;
}
}
}
return false;
}
}
1049、最后一块石头的重量 II
class Solution {
public int lastStoneWeightII(int[] stones) {
int sum = 0;
for(int i : stones){
sum += i;
}
int target = sum/2;
int[] dp = new int[target+1];
for(int i = 0; i < stones.length; i++){
for(int j = target; j >= stones[i]; j--){
dp[j] = Math.max(dp[j],dp[j-stones[i]]+stones[i]);
}
}
return sum-2*dp[target];
}
}
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[] dp = new int[amount + 1];
Arrays.fill(dp,Integer.MAX_VALUE);
dp[0] = 0;
for(int i = 0; i < coins.length; i++){
for(int j = coins[i]; j <= amount; j++){
if(dp[j-coins[i]]!=Integer.MAX_VALUE)
dp[j] = Math.min(dp[j],dp[j - coins[i]] + 1);
}
}
return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
}
}
279、完全平方数
class Solution {
public int numSquares(int n) {
int k = (int)Math.pow(n,0.5);
int[] nums = new int[k];
for(int i = 0; i < nums.length; i++){
nums[i] = (i+1)*(i+1);
}
int[] dp = new int[n+1];
Arrays.fill(dp,Integer.MAX_VALUE);
dp[0] = 0;
for(int i = 0; i < nums.length; i++){
for(int j = nums[i]; j <= n; j++){
if(dp[j - nums[i]]!=Integer.MAX_VALUE)
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) {
boolean[] dp = new boolean[s.length() + 1];
dp[0] = true;
for(int j = 0; j <= s.length(); j++){
for(String str : wordDict){
int len = str.length();
if(j>=len&&s.substring(j-len,j).equals(str)&&dp[j-len]){
dp[j] = true;
}
}
}
return dp[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;
for(int i = 1; i < nums.length; i++){
if(nums[i]>nums[i-1]){
dp[i] = Math.max(dp[i-1]+1,dp[i]);
result = result > dp[i] ? 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()];
int count = 0;
for(int i = dp.length-1; i >= 0; i--){
for(int j = i; j < dp.length; j++){
if(s.charAt(i)==s.charAt(j)){
if(j-i<=1){
count++;
dp[i][j] = true;
}else if(dp[i+1][j-1]){
count++;
dp[i][j] = true;
}
}
}
}
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]
class Solution {
public int searchInsert(int[] nums, int target) {
// 有序数组，考虑用二分查找
int left = 0;
int right = nums.length - 1;
int mid = (left + right) >> 1;
if(target < nums[left]){
return left;
}
if(target > nums[right]){
return right + 1;
}
while(left <= right){
if(target == nums[mid]){
return mid;
}else if(target < nums[mid]){
right = mid -1;
}else{
left = mid + 1;
}
mid = (left + right) >> 1;
}
return left;//找不到，返回需要插入的位置
}
}
class Solution {
public int[] searchRange(int[] nums, int target) {
// 非递减说明是升序的，但可以有重复元素
int[] arr = {-1, -1};
if(nums.length == 0){
return arr;
}
int left = 0;
int right = nums.length - 1;
int mid = (left + right) >> 1;
if(target < nums[left] || target > nums[right]){
return arr;//边界值
}
int leftPoint;//目标数组的开始位置
int rightPoint;//目标数组的结束位置
while(left <= right){
if(target == nums[mid]){
leftPoint = mid;
rightPoint = mid;
while(leftPoint >= 0 && target == nums[leftPoint]){
arr[0] = leftPoint;
leftPoint--;//向左寻找重复元素
}
while(rightPoint <= (nums.length - 1) && target == nums[rightPoint]){
arr[1] = rightPoint;
rightPoint++;//向右寻找重复元素
}
return arr;//返回找到的目标值的位置
}else if(target < nums[mid]){
right = mid - 1;
}else{
left = mid + 1;
}
mid = (left + right) >> 1;
}
return arr;//没有找到
}
}
ValidPalindromeGivenastring,determineifitisapalindrome,consideringonlyalphanumericcharactersandignoringcases. [#125]Example:"Aman,aplan,acanal:Panama"isapalindrome."raceacar"isnotapalindrome.Haveyouconsiderthatthestringmightbeempty?Thisisagoodquestiontoaskduringaninterview.Forthepurposeofthisproblem
前言我们习惯用idea编写、调试代码，在LeetCode上刷题时，如果能够在IDEA编写代码，并且做好代码管理，是一件事半功倍的事情。对于后续复习题目，做笔记也会非常便利。本文目的在于介绍LeetCodeEditor的使用，以及配置工具类，最终目录结构如下：note：放置笔记src：放置代码leetcode.editor.cn：插件LeetCodeEditor自动生成utils：自定义的工具包，可用于自动化输入测试用例，定义题目需要的类（结构体）out：运行测试时自动生成LeetCodeEditorGitHub：https://github.com/shuzijun/leetcode-edit
一、题目给你一个整数数组ranks和一个字符数组suit。你有5张扑克牌，第i张牌大小为ranks[i]，花色为suits[i]。下述是从好到坏你可能持有的手牌类型：“Flush”：同花，五张相同花色的扑克牌。“ThreeofaKind”：三条，有3张大小相同的扑克牌。“Pair”：对子，两张大小一样的扑克牌。“HighCard”：高牌，五张大小互不相同的扑克牌。请你返回一个字符串，表示给定的5张牌中，你能组成的最好手牌类型。注意：返回的字符串大小写需与题目描述相同。来源：力扣（LeetCode）链接：https://leetcode.cn/problems/best-poker-hand/d
一.面试总结 4月20号下午进行了一场大数据视频面试，总结一下踩坑点： 1.确定面试后，第一件事要和HR确定面试方式，具体时间、地点、什么软件、岗位JD等必须信息。 这里很多人有一个思想误区，认为问的太多会给HR不好的印象；其实大可不必，如果你通过了简历筛选，你就有权力使用公司招聘的人力资源。 2.要在面试10分钟前就进入面试的环境中，以防突发事件。 3.面试最开始都会有一个自我介绍环节，这个自我介绍环节，一定要慎之又慎，最好写下来，让朋友、长辈等审核多遍。 注：我面试时，在这踩了一个坑，自我介绍的时候踩了我要面试的岗位一脚，被技术面试官抓住了这一点
🍎道阻且长，行则将至。🍓🌻算法，不如说它是一种思考方式🍀算法专栏：👉🏻123一、🌱344.反转字符串题目描述：编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组s的形式给出。不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用O(1)的额外空间解决这一问题。来源：力扣（LeetCode）难度：简单提示：1s[i]都是ASCII码表中的可打印字符示例1：输入：s=[“h”,“e”,“l”,“l”,“o”]输出：[“o”,“l”,“l”,“e”,“h”]示例2：输入：s=[“H”,“a”,“n”,“n”,“a”,“h”]输出：[“h”,“a”,“n”,“n”,“a”,“H”
数据规模->时间复杂度10^8内容二维数组中的路径问题买卖股票的最佳时机lc62【剑指098】【top100】：不同路径https://leetcode.cn/problems/unique-paths/提示：1题目数据保证答案小于等于2*10^9#方案一：dfs+记忆化classSolution:defuniquePaths(self,m:int,n:int)->int:memo=[[-1]*nfor_inrange(m)]defdfs(i,j):ifi==m-1andj==n-1:return1ifi>=morj>=n:return0ifmemo[i][j]!=-1:returnmemo[
🍎道阻且长，行则将至。🍓🌻算法，不如说它是一种思考方式🍀算法专栏：👉🏻123hash是什么，哈希表为什么叫哈希表？一、🌱454.四数相加II题目描述：给你四个整数数组nums1、nums2、nums3和nums4，数组长度都是n，请你计算有多少个元组(i,j,k,l)能满足：0nums1[i]+nums2[j]+nums3[k]+nums4[l]==0来源：力扣（LeetCode）难度：中等提示：n==nums1.lengthn==nums2.lengthn==nums3.lengthn==nums4.length1-2^28示例1：输入：nums1=[1,2],nums2=[-2,-1],n
Halo，这里是Ppeua。平时主要更新C语言，C++，数据结构算法......感兴趣就关注我吧！你定不会失望。🌈个人主页：主页链接🌈算法专栏：专栏链接 我会一直往里填充内容哒！🌈LeetCode专栏：专栏链接 目前在刷初级算法的LeetBook。若每日一题当中有力所能及的题目，也会当天做完发出🌈代码仓库：Gitee链接🌈点击关注=收获更多优质内容🌈目录题目:111. 二叉树的最小深度题解:代码实现:题目:700. 二叉搜索树中的搜索题解:代码实现:题目:701. 二叉搜索树中的插入操作题解:代码实现:题目:450. 删除二叉搜索树中的节点题解:代码实现:完结撒花：人生苦短，
👻内容专栏：《LeetCode刷题专栏》🐨本文概括：189.轮转数组🐼本文作者：花碟🐸发布时间：2023.4.12目录思想1暴力求解代码实现：思想2三次倒置代码实现： 思想3memcpy零时拷贝代码实现：189.轮转数组 点击跳转到LeetCode平台OJ页面题目：给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。示例1：输入:nums=[1,2,3,4,5,6,7],k=3输出:[5,6,7,1,2,3,4]解释:向右轮转1步:[7,1,2,3,4,5,6]向右轮转2步:[6,7,1,2,3,4,5]向右轮转3步:[5,6,7,1,2,3,4]
🚀算法题🚀🌲算法刷题专栏|面试必备算法|面试高频算法🍀🌲越难的东西,越要努力坚持，因为它具有很高的价值，算法就是这样✨🌲作者简介：硕风和炜，CSDN-Java领域新星创作者🏆，保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文|经验分享|好用的网站工具分享💎💎💎🌲恭喜你发现一枚宝藏博主,赶快收入囊中吧🌻🌲人生如棋，我愿为卒，行动虽慢，可谁曾见我后退一步？🎯🎯🚀算法题🚀🍔目录🚗知识回顾🚩题目链接⛲题目描述🌟求解思路&实现代码&运行结果⚡动态规划🥦求解思路🥦实现代码🥦运行结果💬共勉🚗知识回顾大家再看这道题目之前，可以先去看一下我之前写过的一篇关于最长递增子序列算法