leetCode刷题记录3-面试经典150题

不要摆，没事干就刷题，只有好处，没有坏处，实在不行，看看竞赛题

面试经典 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%(n+1);reverse(nums,0,n-k);reverse(nums,n-k+1,n);reverse(nums,0,n);
}public void reverse(int[] nums, int l,int r) {while (l<r){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(index>=prices.length) return 0;if(curr!=-1){//当前持有股票// 不卖dfs(prices,curr,index+1,sum);// 卖if(prices[index]>curr) dfs(prices,-1,index+1,sum+prices[index]);}else {//当前无股票// 买dfs(prices,prices[index],index+1,sum-prices[index]);// 不买dfs(prices,-1,index+1,sum);}return 0;
}

先自己优化时间
强制加缓存，竟然超出内存限制

public int maxProfit(int[] prices) {return dfs(prices,-1,0);
}
HashMap<String, Integer> cache = new HashMap<>();
public int dfs(int[] prices,int curr,int index){//System.out.println(index+" "+sum);if(index>=prices.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,index+1);int t2=0;// 卖 sum+prices[index]if(prices[index]>curr) {t2 = dfs(prices,-1,index+1)+prices[index];}ans = Math.max(t1,t2);}else {//当前无股票// 买 sum-prices[index]int t1 = -prices[index]+dfs(prices,prices[index],index+1);// 不买 sumint t2 = dfs(prices,-1,index+1);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(p>0) ans+=p;}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];
}