目录
1.买卖股票的最佳时机 II
2.跳跃游戏
3.跳跃游戏 II
4.H 指数
5.O(1) 时间插入、删除和获取随机元素
6.除自身以外数组的乘积
7.加油站
8.分发糖果
1.买卖股票的最佳时机 II
class Solution {public int maxProfit(int[] prices) {//和1相比，这个可以一直买卖股票，所以可以使用贪心策略，因为局部最优解就是全局最优解//亏钱直接不买卖int profit=0;for(int i=1;i<prices.length;i++){int tmp=prices[i]-prices[i-1];if(tmp>0) profit+=tmp;}return profit;}
}2.跳跃游戏
最右可达位置维护。
有点类似拼接的路段。
class Solution {public boolean canJump(int[] nums) {int mx=0;for(int i=0;i<nums.length;i++){if(i>mx){//无法到达ireturn false;}//最右可以跳到i+nums[i]mx=Math.max(mx,i+nums[i]);}return true;}
}3.跳跃游戏 II
class Solution {public int jump(int[] nums) {int ret=0;//已建造的桥的右端点int cur_right=0;//下一座桥的右端点最大值int next_right=0;for(int i=0;i<nums.length-1;i++){next_right=Math.max(next_right,i+nums[i]);//到达已造桥的右端点if(i==cur_right){cur_right=next_right;ret++;}}return ret;}
}4.H 指数
class Solution {public int hIndex(int[] citations) {int n=citations.length;//cnt统计引用次数的出现次数int [] cnt=new int [n+1];for(int c:citations){//min是处理>n的引用次数，归为ncnt[Math.min(c,n)]++;}int sum=0;//倒序遍历更好，一旦符合马上接收for(int i=n;;i--){sum+=cnt[i];if(sum>=i){return i;}}}
}5.O(1) 时间插入、删除和获取随机元素
class RandomizedSet {static int[] nums=new int[200010];Random random=new Random();Map<Integer,Integer>map=new HashMap<>();int idx=-1;public boolean insert(int val) {if(map.containsKey(val)) return false;nums[++idx]=val;map.put(val,idx);return true; }public boolean remove(int val) {if(!map.containsKey(val)) return false;int loc=map.remove(val);if(loc!=idx) map.put(nums[idx],loc);nums[loc]=nums[idx--];return true;}public int getRandom() {return nums[random.nextInt(idx+1)];}
}/*** Your RandomizedSet object will be instantiated and called as such:* RandomizedSet obj = new RandomizedSet();* boolean param_1 = obj.insert(val);* boolean param_2 = obj.remove(val);* int param_3 = obj.getRandom();*/6.除自身以外数组的乘积
class Solution {public int[] productExceptSelf(int[] nums) {//pre表示前缀积；suf表示后缀积；ret=两者之积即可；int n=nums.length;int[] pre=new int[n];pre[0]=1;for(int i=1;i<n;i++){pre[i]=nums[i-1]*pre[i-1];}int[] suf=new int[n];suf[n-1]=1;for(int i=n-2;i>=0;i--){suf[i]=nums[i+1]*suf[i+1];}int[] ret = new int[n];for(int i=0;i<n;i++){ret[i]=pre[i]*suf[i];}return ret;}
}7.加油站
class Solution {public int canCompleteCircuit(int[] gas, int[] cost) {int ret=0;//最小油量int mins=0;//油量int s=0;for(int i=0;i<gas.length;i++){//i处加油，从i到i+1s+=gas[i]-cost[i];if(s<mins){//更新最小油量mins=s;ret=i+1;}}//循环结束后，s 即为 gas 之和减去 cost 之和return s<0?-1:ret;}
}8.分发糖果
class Solution {public int candy(int[] ratings) {//贪心算法int [] left=new int[ratings.length];int [] right=new int[ratings.length];//都发一颗糖Arrays.fill(left,1);Arrays.fill(right,1);for(int i=1;i<ratings.length;i++){if(ratings[i]>ratings[i-1]) left[i]=left[i-1]+1;}int count=left[ratings.length-1];for(int i = ratings.length - 2; i >= 0; i--) {if(ratings[i] > ratings[i + 1]) right[i] = right[i + 1] + 1;count += Math.max(left[i], right[i]);}return count; }
}