临夏建设网站,分类网站模板,调价智能关键词软件,做视频网站赚做视频网站赚文章目录 不要摆#xff0c;没事干就刷题#xff0c;只有好处#xff0c;没有坏处#xff0c;实在不行#xff0c;看看竞赛题面试经典 150 题80. 删除有序数组中的重复项 II189. 轮转数组122. 买卖股票的最佳时机 II 不要摆#xff0c;没事干就刷题#xff0c;只有好处没事干就刷题只有好处没有坏处实在不行看看竞赛题面试经典 150 题80. 删除有序数组中的重复项 II189. 轮转数组122. 买卖股票的最佳时机 II 不要摆没事干就刷题只有好处没有坏处实在不行看看竞赛题
面试经典 150 题
面试经典 150 题
80. 删除有序数组中的重复项 II
80. 删除有序数组中的重复项 II 这几题都很水
public int removeDuplicates(int[] nums) {int k 0, count 1;for (int i 1; i nums.length; i) {if (nums[i] ! nums[k]) {nums[k] nums[i];count 1;} else if (count 2) {nums[k] nums[i];}}return k 1;
}189. 轮转数组
189. 轮转数组
408原题4刷了现在感觉很水了
注意k可能很大需要对长度取一下模
public void rotate(int[] nums, int k) {int n nums.length-1;k k%(n1);reverse(nums,0,n-k);reverse(nums,n-k1,n);reverse(nums,0,n);
}public void reverse(int[] nums, int l,int r) {while (lr){int t nums[l];nums[l] nums[r];nums[r] t;l;r--;}
}122. 买卖股票的最佳时机 II
122. 买卖股票的最佳时机 II
没啥头绪先暴力拿分也是能力
DFS暴力枚举过了198个也不错了 剩下两个超时
public int maxProfit(int[] prices) {dfs(prices,-1,0,0);return max;
}int max -1;
public int dfs(int[] prices,int curr,int index,int sum){//System.out.println(index sum);max Math.max(max,sum);if(indexprices.length) return 0;if(curr!-1){//当前持有股票// 不卖dfs(prices,curr,index1,sum);// 卖if(prices[index]curr) dfs(prices,-1,index1,sumprices[index]);}else {//当前无股票// 买dfs(prices,prices[index],index1,sum-prices[index]);// 不买dfs(prices,-1,index1,sum);}return 0;
}先自己优化时间 强制加缓存竟然超出内存限制
public int maxProfit(int[] prices) {return dfs(prices,-1,0);
}
HashMapString, Integer cache new HashMap();
public int dfs(int[] prices,int curr,int index){//System.out.println(index sum);if(indexprices.length) return 0;String key curr-index;if(cache.get(key)!null) return cache.get(key);int ans 0;if(curr!-1){//当前持有股票// 不卖int t1 dfs(prices,curr,index1);int t20;// 卖 sumprices[index]if(prices[index]curr) {t2 dfs(prices,-1,index1)prices[index];}ans Math.max(t1,t2);}else {//当前无股票// 买 sum-prices[index]int t1 -prices[index]dfs(prices,prices[index],index1);// 不买 sumint t2 dfs(prices,-1,index1);ans Math.max(t1,t2);}cache.put(key,ans);return ans;
}没办法看题解喽
看题解后我傻了这一题竟然可以直接贪心
public int maxProfit(int[] prices) {int ans 0;for (int i 1; i prices.length; i) {int p prices[i]-prices[i-1];if(p0) ansp;}return ans;
}dp也很简单但是自己的猪脑想不到不会分析
// 也很简单 持有股票和没有股票两种状态而已 0不持有 1持有
public int maxProfit(int[] prices) {int n prices.length;int[][] dp new int[n][2];dp[0][1] -prices[0];for (int i 1; i prices.length; i) {dp[i][0] Math.max(dp[i-1][0],dp[i-1][1]prices[i]);//[头一天不持有股票且今天不买][头一天持有股票今天卖了]dp[i][1] Math.max(dp[i-1][1],dp[i-1][0]-prices[i]);//[头一天就持有股票且今天不卖][头一天不持有股票且今天买了]}return dp[n-1][0];
}
