目录
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){
//无法到达i
return 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的引用次数，归为n
cnt[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+1
s+=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;
}
}
