刷题日记 - 2

class Solution {
    public int maxProfit(int[] prices) {
         int res = 0;
         int min = Integer.MAX_VALUE;
         for(int n : prices){
             min = Math.min(min,n);
             res = Math.max(res,n - min);
         }
         return res;
    }
}

class Solution {
    public int maxProfit(int[] prices) {
        int len = prices.length;
        if(len<2) return 0;
        int[][] dp = new int[len][2];  // dp[i][0]代表第i天手上未持股的最大金额
        dp[0][1] = - prices[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][1],dp[i-1][0]-prices[i]);
        }
        return dp[len-1][0];
    }
}

class Solution{
    public int maxProfit(int[] prices){
        int len = prices.length;
        int res = 0;
        if(len<2)return 0;
        for(int i=1;i<len;i++){
            int diff = prices[i] - prices[i-1];
            if(diff>0){
                res += diff;
            }
        }
        return res;
    }
}

class Solution {
    public int hIndex(int[] citations) {
        int len = citations.length;

        int[] count = new int[1001];  // count[i] = j 表示引用次数大于等于i的有j篇

        for(int citation:citations){   // 根据citations的值完善count数组
            for(int i=citation;i>=0;i--){
                count[i]++;
            }
        }
        
        int res = 1000;
        for(;res>=0;res--){     // 从后向前遍历
            if(count[res]>=res) return res;
        }
        
        return res;
    }
}

import java.util.HashMap;
import java.util.Random;

class RandomizedSet {

    Random random;
    HashMap<Integer, Integer> map;
    int[] nums;
    int idx;

    // 构造函数，初始化数据结构
    public RandomizedSet() {
        random = new Random();  // 用于生成随机数
        map = new HashMap<>();  // 存储值及其对应的索引
        nums = new int[200001]; // 存储实际的值
        idx = -1;               // 数组的当前最大索引，表示为空
    }
    
    // 插入一个值。如果该值不存在，则插入并返回true，否则返回false
    public boolean insert(int val) {
        if(map.containsKey(val)){ // 如果值已经存在
            return false;
        } else {
            nums[++idx] = val;    // 将值插入数组的下一个位置
            map.put(val, idx);    // 将值及其索引存入哈希表
            return true;
        }
    }
    
    // 删除一个值。如果该值存在，则删除并返回true，否则返回false
    public boolean remove(int val) {
        if(map.containsKey(val)){ // 如果值存在
            int valIdx = map.get(val); // 获取值的索引
            map.remove(val);           // 从哈希表中移除该值
            // 将数组中最后一个元素移动到被删除元素的位置
            nums[valIdx] = nums[idx];
            if(idx != valIdx){          // 如果被删除的不是最后一个元素
                map.put(nums[idx], valIdx); // 更新最后一个元素的新索引
            }
            idx--;                      // 减少数组的有效长度
            return true;
        } else {
            return false;
        }
    }
    
    // 返回集合中的一个随机元素
    public int getRandom() {
        return nums[random.nextInt(idx + 1)]; // 从0到idx（包括idx）之间选择一个随机索引
    }
}

/**
 * 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();
 */

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        for(int i=0;i<gas.length;i++){
            if(gas[i]>=cost[i]){  // 遍历每一个加油站，如果当前的油足够到下一个加油站
                if (i==fun(gas,cost,i)){ // 开始环形绕圈
                    return i;
                }
            }
        }
        return -1;
    }

    private int fun(int[] gas,int[] cost,int start){
        int len = gas.length;
        int pos = start;   // 当前位置
        int curGas = gas[pos];  // 当前油量
        int nextPos = (pos+1)%len; // 下一个位置
        while(curGas>=cost[pos]){ // 如果当前油够前往下一个位置
            curGas = curGas - cost[pos]+ gas[nextPos]; // 到下一个位置，刷新curGas
            pos = nextPos; // 更新位置
            nextPos = (pos+1)%len; // 更新下一个位置
            if(pos==start)break; //返回起点则表示找到了
        }
        return pos;
    };
}

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        for(int i=0;i<gas.length;i++){
            if(gas[i]>=cost[i]){  // 遍历每一个加油站，如果当前的油足够到下一个加油站
                int end = fun(gas,cost,i);
                if(i == end){
                    return i;
                }else if(end<i){ // 优化点
                    return -1;
                }else{
                    i = end;  // for循环会+1
                }
            }
        }
        return -1;
    }

    private int fun(int[] gas,int[] cost,int start){
        int len = gas.length;
        int pos = start;   // 当前位置
        int curGas = gas[pos];  // 当前油量
        int nextPos = (pos+1)%len; // 下一个位置
        while(curGas>=cost[pos]){ // 如果当前油够前往下一个位置
            curGas = curGas - cost[pos]+ gas[nextPos]; // 到下一个位置，刷新curGas
            pos = nextPos; // 更新位置
            nextPos = (pos+1)%len; // 更新下一个位置
            if(pos==start)break; //返回起点则表示找到了
        }
        return pos;
    };
}

class Solution {
    public int candy(int[] ratings) {
        int len = ratings.length;
        int[] candies = new int[len];
        
        // 初始化每个孩子的糖果数为1，确保每个孩子至少有一颗糖果
        Arrays.fill(candies, 1);

        // 特殊情况处理，如果孩子数量小于2，直接返回孩子数量
        if(len < 2) return len;

        // 从左到右遍历，如果右边的孩子评分比左边高，糖果数+1
        for(int i = 1; i < len; i++) {
            if(ratings[i] > ratings[i - 1]) {
                candies[i] = candies[i - 1] + 1;
            }
        }

        // 从右到左遍历，如果左边的孩子评分比右边高，糖果数为当前值和右边孩子糖果数+1的较大值
        for(int j = len - 2; j >= 0; j--) {
            if(ratings[j] > ratings[j + 1]) {
                candies[j] = Math.max(candies[j + 1] + 1, candies[j]);
            }
        }

        // 计算总糖果数
        int res = 0;
        for(int candy : candies) {
            res += candy;
        }

        // 返回总糖果数
        return res;
    }
}