Leetcode(easy Greedy)

leetcode 贪心算法的简单题目

122. 买卖股票的最佳时机 II

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

class Solution {
    public int maxProfit(int[] prices) {
        // 贪心算法：只要今天买明天赚就买入
        // profit用来记录前后两天的差值
        int res = 0;
        int[] profit = new int[prices.length - 1];
        for(int i =0;i<prices.length-1;i++) profit[i] = prices[i+1] - prices[i];
        for(int n:profit) if(n>0) res+=n;
        return res;
    }
}

455. 分发饼干

class Solution {
    public int findContentChildren(int[] grid, int[] size) {
        if (grid == null || size == null) return 0;
        Arrays.sort(grid);
        Arrays.sort(size);
        int gi = 0, si = 0;
        while (gi < grid.length && si < size.length) {
            if (grid[gi] <= size[si]) {
                gi++;
            }
            si++;
        }
        return gi;
    }

}

860 柠檬水找零

class Solution {
    public boolean lemonadeChange(int[] bills) {
        if(bills == null || bills.length==0) return true;
        int[] money = new int[3];
        for(int n:bills){
            if(n==5) money[0]++;
            if(n==10){
                if(money[0]<1){
                    return false;
                }else{
                    money[0]--;
                    money[1]++;
                }
            }
            if(n==20){
                if(money[0]>0 && money[1]>0){
                    money[0]-=1;
                    money[1]-=1;
                    money[2]++;
                }
                else if(money[0]>2){
                    money[0]-=3;
                    money[2]++;
                }
                else{
                    return false;
                }
            }
        }
        return true;

    }
}

874. 模拟行走机器人

class Solution {
    public int robotSim(int[] commands, int[][] obstacles) {
        //direction表当前朝向，0123 表 北东南西
        int ans = 0,direction = 0,x = 0,y = 0;
        //每个朝向上的数据变化，比如朝北时取Direction[0]  ->   {0,1}
        //那么x轴的变化为x+0，y轴变化为y+1;
        int[][] Direction = {{0,1},{1,0},{0,-1},{-1,0}};

        HashSet<String> set = new HashSet<>();
        //将所有障碍物坐标组合成字符串存入set中方便查询
        for (int[] arr : obstacles) set.add(arr[0]+"，"+arr[1]);

        for (int com : commands){
            //定义下一步的坐标
            int next_x = 0,next_y = 0;
            //当命令为前进，开始移动
            if (com >= 0 ){
                for(int i = 0; i < com; i++){
                    //取得下一步的坐标
                    next_x = x + Direction[direction][0];
                    next_y = y + Direction[direction][1];
                    //若下一步有障碍物，结束当前命令，跳至下一命令
                    if(set.contains(next_x+"，"+next_y)) break;
                    //否则更新坐标与最远距离
                    x = next_x;
                    y = next_y;
                    ans = Math.max(ans, x*x + y*y);
                }
            }else{
                //改变朝向
                direction = com == -1 ? (direction + 1) % 4 : (direction + 3) % 4;
            }
        }
        return ans;
    }
}

944. 删列造序

class Solution {
    public int minDeletionSize(String[] A) {
        int ans = 0;
        for (int c = 0; c < A[0].length(); ++c)
            for (int r = 0; r < A.length - 1; ++r)
                if (A[r].charAt(c) > A[r+1].charAt(c)) {
                    ans++;
                    break;
                }

        return ans;
    }
}

1005. K 次取反后最大化的数组和

class Solution {
    public int largestSumAfterKNegations(int[] A, int K) {
        Arrays.sort(A);
        int m=0;
        for(int n:A) if(n<0) m++;
        int flag =0;
        for(int n:A) if(n==0) flag=1;
        int i = 0;
        while(m>0&&K>0){
            A[i]=-A[i];
            m--;
            i++;
            K--;
        }
        int res = 0;
        if(K==0||flag==1) for(int n:A) res+=n;
        else{
            Arrays.sort(A);
            while(K>0){
                A[0]=-A[0];
                K--;
            } 
            for(int n:A) res+=n;
        }
        return res;

    }
}

1046. 最后一块石头的重量

有一堆石头，每块石头的重量都是正整数。
每一回合，从中选出两块 最重的 石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：
如果 x == y，那么两块石头都会被完全粉碎；
如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。
最后，最多只会剩下一块石头。返回此石头的重量。如果没有石头剩下，就返回 0。

class Solution {
    public int lastStoneWeight(int[] stones) {
        // myidea : 利用一个优先队列，每次都去敲两块最大的石头，敲碎的石头再重新进入优先队列也就是大顶堆
        Queue<Integer> queue = new PriorityQueue<>((o1, o2) -> (o2 - o1));
        for(int num:stones) queue.offer(num);
        while(queue.size()>1) queue.offer(Math.abs(queue.poll()-queue.poll()));
        int res =0;
        res = queue.poll();
        return res;
    }
}

1217. 玩筹码

数轴上放置了一些筹码，每个筹码的位置存在数组 chips 当中。
你可以对 任何筹码 执行下面两种操作之一（不限操作次数，0 次也可以）：
将第 i 个筹码向左或者右移动 2 个单位，代价为 0。
将第 i 个筹码向左或者右移动 1 个单位，代价为 1。
最开始的时候，同一位置上也可能放着两个或者更多的筹码。
返回将所有筹码移动到同一位置（任意位置）上所需要的最小代价。

class Solution {
    public int minCostToMoveChips(int[] position) {
        // myieda：偶数位置全部移动到偶数位置的代价是0，同理奇数位置全部移动到同一奇数位置的代价也为0，最终的结果就是奇数位置的元素和偶数位置的元素较小的那一个
        int[] pos = new int[2];
        for(int num:position) if(num%2==1) pos[1]++; else pos[0]++;
        return Math.min(pos[0],pos[1]);
    }
}

1221. 分割平衡字符串

在一个「平衡字符串」中，'L' 和 'R' 字符的数量是相同的。
给出一个平衡字符串 s，请你将它分割成尽可能多的平衡字符串。
返回可以通过分割得到的平衡字符串的最大数量。

class Solution {
    public int balancedStringSplit(String s) {
        // myidea 贪心 记录R与L之间的差值，若为0，res++
        int res = 0;
        int flag = 0;
        for(char c:s.toCharArray()){
            if(c=='R') flag++;
            if(c=='L') flag--;
            if(flag==0) res++;
        }
        return res;
    }
}

1403. 非递增顺序的最小子序列

class Solution {
    public List<Integer> minSubsequence(int[] nums) {
        Arrays.sort(nums);
        List<Integer> list = new ArrayList<>();
        int sum = 0;
        int temp = 0;
        for(int i:nums) sum+=i;
        for(int i=nums.length-1;i>-1;i--){
            temp +=nums[i];
            list.add(nums[i]);
            if(temp>sum-temp) break;
        }
        for(int i:list) System.out.println(i);
        return list;
        
    }
}

1518. 换酒问题

class Solution {
    public int numWaterBottles(int numBottles, int numExchange) {
        int ans = numBottles;
        while(numBottles!=0){
            ans+=helper(numBottles,numExchange)[0];
            numBottles=helper(numBottles,numExchange)[1]/numExchange;;
        }
        return ans;
    }

    public int[] helper(int numOfNullBottles,int numExchange){
        int res = 0;
        int[] temp = new int[2];
        while(numOfNullBottles/numExchange!=0){
            res+=numOfNullBottles/numExchange;
            numOfNullBottles=numOfNullBottles%numExchange+numOfNullBottles/numExchange;
        }
        temp[0] = res;
        temp[1] = numOfNullBottles; 
        return temp;
    }
}