算法笔记-贪心类型

image.png

贪心类型

贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解  。 贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择。也就是说，不从整体最优上加以考虑，做出的只是在某种意义上的局部最优解 。

局部最优得出整体最优

相关题目

柠檬水找零(简单)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public boolean lemonadeChange(int[] bills) {
        int five = 0, ten = 0;
        for (int bill : bills) {
            if (bill == 5) {
                five++;
            } else if (bill == 10) {
                if (five == 0) {
                    return false;
                }
                five--;
                ten++;
            } else {
                if (five > 0 && ten > 0) {
                    five--;
                    ten--;
                } else if (five >= 3) {
                    five -= 3;
                } else {
                    return false;
                }
            }
        }
        return true;
    }
}

岛屿数量(中等)

广度优先遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
    int[][] visit ;//记录已经走过的坐标
    char[][] arr;
    public int numIslands(char[][] grid) {
        int ans = 0;
        arr = grid;
        visit = new int[grid.length][grid[0].length];//记录已经走过的坐标
        //深度优先搜索
        for(int i=0;i<grid.length;i++){
            for (int j = 0; j < grid[i].length; j++) {
                if (grid[i][j]=='1'&&visit[i][j]==0){
                    bfs(i,j);
                    ans+=1;
                }
            }
        }
        return ans;
    }
    //
    public void bfs(int x,int y){
        visit[x][y]=1;
        //上
        if(x-1>=0&&visit[x-1][y]==0&&arr[x-1][y]=='1')bfs(x-1,y);
        //下
        if(x+1<arr.length&&visit[x+1][y]==0&&arr[x+1][y]=='1')bfs(x+1,y);
        //左
        if(y-1>=0&&visit[x][y-1]==0&&arr[x][y-1]=='1')bfs(x,y-1);
        //右
        if(y+1<arr[x].length&&visit[x][y+1]==0&&arr[x][y+1]=='1')bfs(x,y+1);
    }
}

买卖股票的最佳时机 II(简单)

贪心算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
class Solution {
    //动态规划(dp[i][j] 表示到下标为 i 的这一天，持股状态为 j 时，我们手上拥有的最大现金数。)    
    public int maxProfit(int[] prices) {
        int len = prices.length;
        if (len < 2)return 0;
        // cash：持有现金
        // hold：持有股票
        // 状态数组
        // 状态转移：cash → hold → cash → hold → cash → hold → cash
        int[] cash = new int[len];
        int[] hold = new int[len];
    
        cash[0] = 0;
        hold[0] = -prices[0];
    
        for (int i = 1; i < len; i++) {
            // 这两行调换顺序也是可以的
            cash[i] = Math.max(cash[i - 1], hold[i - 1] + prices[i]);//卖出
            hold[i] = Math.max(hold[i - 1], cash[i - 1] - prices[i]);//买入
        }
        return cash[len - 1];
    }
    //空间优化
    public int maxProfit(int[] prices) {
        int len = prices.length;
        if (len < 2)return 0;
        // cash：持有现金
        // hold：持有股票
        // 状态转移：cash → hold → cash → hold → cash → hold → cash
        int cash = 0;
        int hold = -prices[0];
    
        int preCash = cash;
        int preHold = hold;
        for (int i = 1; i < len; i++) {
            cash = Math.max(preCash, preHold + prices[i]);
            hold = Math.max(preHold, preCash - prices[i]);
            preCash = cash;
            preHold = hold;
        }
        return cash;
    }
    //贪婪算法
    public int maxProfit(int[] prices) {
        int ans = 0;
        int n = prices.length;
        for (int i = 1; i < n; ++i) {
            ans += Math.max(0, prices[i] - prices[i - 1]);
        }
        return ans;
    }
}

跳跃游戏(中等)

给定一个非负整数数组，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个位置。 

1
2
3
输入: [2,3,1,1,4]
输出: true
解释: 我们可以先跳 1 步，从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public class Solution {
    //循环方式
    public boolean canJump(int[] nums) {
        int n = nums.length;//数字长度
        int rightmost = 0;//可以到达最远位置
        //迭代
        for (int i = 0; i < n; ++i) {
            //当前下标小于可达最远下标则更新
            if (i <= rightmost) {
                rightmost = Math.max(rightmost, i + nums[i]);//更新可达最远位置
                if (rightmost >= n - 1) {//如果最远可达大于等于末尾下标返回true
                    return true;
                }
            }
        }
        return false;
    }
    //dfs方式
    public boolean canJump0(int[] nums) {
       return bfs(0,nums);
    }
    public boolean bfs(int index,int[] nums){
        if (index==nums.length-1)return true;//满足条件
            for (int j = 1; j < nums[index]; j++) {
                boolean bfs = bfs(index + j, nums);
                if (bfs)return true;
            }
        return false;
    }  
}

跳跃游戏 II（mid)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
class Solution {
    //反向
    /**
    * 我们的目标是到达数组的最后一个位置，因此我们可以考虑最后一步跳跃前所在的位置，该位置通过跳跃能够到达最后一个位置。
    * 如果有多个位置通过跳跃都能够到达最后一个位置，那么我们应该如何进行选择呢？直观上来看，我们可以「贪心」地选择距离最后一个位置最远的那个位置，也就是对应下标最小的那个位置。因此，我们可以从左到右遍历数组，选择第一个满足要求的位置。
    * 找到最后一步跳跃前所在的位置之后，我们继续贪心地寻找倒数第二步跳跃前所在的位置，以此类推，直到找到数组的开始位置。
    * @param nums
    * @return 
    */
    public int jump(int[] nums) {
        int position = nums.length - 1;//终点
        int steps = 0;//步数
        while (position > 0) {
            //每次寻找距离终点最远的那个下标，更新终点和step
            for (int i = 0; i < position; i++) {
                if (i + nums[i] >= position) {//如果当前
                    position = i;
                    steps++;
                    break;
                }
            }
        }
        return steps;
    }
    //正向
    //思想就一句话：每次在上次能跳到的范围（end）内选择一个能跳的最远的位置（也就是能跳到maxPosition位置的点）作为下次的起跳点
    public int jump(int[] nums) {
        int end = 0;//上次跳跃可达范围右边界（下次的最右起跳点）
        int maxPosition = 0; // 目前能跳到的最远位置
        int steps = 0;// 跳跃次数
        for (int i = 0; i < nums.length - 1; i++) {
            maxPosition = Math.max(maxPosition, i + nums[i]); 
            // 到达上次跳跃能到达的右边界了
            if (i == end) {
                end = maxPosition;// 目前能跳到的最远位置变成了下次起跳位置的右边界
                steps++;// 跳跃次数++
            }
        }
        return steps;
    }
    //动态规划
    public int jump(int[] nums) {
        int length = nums.length;
		int dp[] = new int[length];
		dp[0] = 0;
		if(length==1)return 0;//排除为1的状况，否则后面动态规划时会让第一个点的步数变为1，从而答案错
		int maxn =0; //当前能到达的最大下标
		for(int i=0;i<=maxn;i++) {
			maxn = Math.max(maxn, i+nums[i]);//更新最大下标
			if(maxn>=length-1) {
				dp[length-1]=dp[length-1]==0?dp[i]+1:Math.min(dp[length-1], dp[i]+1);
					return dp[length-1];
			}//当某一时刻能够达到最大下标时，直接进入最大下标，避免不必要的循环
			for(int j=i+1;j<=i+nums[i]&&j<length;j++) {
				dp[j]=dp[j]==0?dp[i]+1:Math.min(dp[j], dp[i]+1);
			}//每次从当前结点出发，遍历每一个能达到的结点，并更新他们的dp值
		}
		return dp[nums.length-1];
    }
}

环形子数组的最大和(中等)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
/**
 *    环形子数组的最大和具有两种可能，一种是不使用环的情况，另一种是使用环的情况
 *      不使用环的情况时，直接通过53题的思路，逐步求出整个数组中的最大子序和即可
 *      使用到了环，则必定包含 A[n-1]和 A[0]两个元素且说明从A[1]到A[n-2]这个子数组中必定包含负数【否则只通过一趟最大子序和就可以的出结果】
 *    因此只需要把A[1]-A[n-2]间这些负数的最小和求出来用整个数组的和 sum减掉这个负数最小和即可实现原环型数组的最大和
 *                
 *                max
 *    无环: |----|////|----|
 *           
 *    有环: |////|----|////|
 *    　　    |---max---|
 *    
 **/
    public int maxSubarraySumCircular(int[] A) {
        int[] dp = new int[A.length];   //dp[i]用来记录以nums[i]结尾的最大子序列和
        dp[0] = A[0];                   //初始化dp
        int max = dp[0];                //最大子序列和
        int sum = dp[0];                //整个数组的和
        //求最大子序列和，见53题
        for (int i = 1; i < dp.length; i++) {
            sum += A[i];
            dp[i] = A[i] + Math.max(dp[i - 1], 0);
            max = Math.max(dp[i], max);
        }
        //使用环情况
        int min = 0;    //开始求A[1]~A[n-1]上的最小子序列和
        for (int i = 1; i < dp.length - 1; i++) {
            dp[i] = A[i] + Math.min(0, dp[i - 1]);
            min = Math.min(dp[i], min);
        }
        return Math.max(sum - min, max);
    }
}

乘积最大子数组(中等)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
    //动态规划
    public int maxProduct0(int[] nums) {
        //dp[i] = Math.max(dp[i],dp[i]*nums[i]);
        //如果只是维护上面这一个dp的话，会存在当nums[i]为负数时，取的还是dp[i],但num[i]之和在出现负数时(负负得正)可能是出现最大值的
        //所以需要维护两个dp
        int maxF = nums[0], minF = nums[0], ans = nums[0];
        int length = nums.length;
        for (int i = 1; i < length; ++i) {
            int mx = maxF, mn = minF;
            maxF = Math.max(mx * nums[i], Math.max(nums[i], mn * nums[i]));
            minF = Math.min(mn * nums[i], Math.min(nums[i], mx * nums[i]));
            ans = Math.max(maxF, ans);
        }
        return ans;
    }
    //窗口滑动
    public int maxProduct(int[] nums) {
        /*思想：双指针，遇到0左指针开始收敛*/
        int n = nums.length;
        if(n == 1) return nums[0];
        int max = Integer.MIN_VALUE;
        int muti = 1;
        int l = 0, r = 0;
        while(r <= n && l < n){
            if(r == n){//如果右指针到达最后一个位置，左指针开始滑动
                muti /= nums[l++];
            }else{
                if(nums[r] != 0){//如果右指针所指元素不为0，右滑，更新muti
                    muti *= nums[r++];
                }else if(l < r){//右指针为0，开始左滑，更新muti
                    muti /= nums[l++];
                }else{//左右指针都滑到了0的位置，更新max，左右指针指向下一位置重新滑动
                    max = Math.max(max, 0);
                    ++l;
                    ++r;
                }
            }
            //只要左右指针没有指向同一位置，更新max（指向同一位置说明左滑到顶了，记录的muti一定为1，但并不是乘积值）
            if(l != r) max = Math.max(max, muti);
        }
        return max;
    }
}

乘积为正数的最长子数组长度(中等)

给你一个整数数组 nums ，请你求出乘积为正数的最长子数组的长度。
一个数组的子数组是由原数组中零个或者更多个连续数字组成的数组。
请你返回乘积为正数的最长子数组长度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    public int getMaxLen(int[] nums) {
        int length = nums.length;
        int[] positive = new int[length];//正数dp
        int[] negative = new int[length];//负数dp
        if (nums[0] > 0) {
            positive[0] = 1;
        } else if (nums[0] < 0) {
            negative[0] = 1;
        }
        int maxLength = positive[0];
        for (int i = 1; i < length; i++) {
            //num[i]分为三种情况 大于、小于、等于零
            if (nums[i] > 0) {
                positive[i] = positive[i - 1] + 1;//正数直接+1
                negative[i] = negative[i - 1] > 0 ? negative[i - 1] + 1 : 0;//负数直接置为0
            } else if (nums[i] < 0) {
                positive[i] = negative[i - 1] > 0 ? negative[i - 1] + 1 : 0;
                negative[i] = positive[i - 1] + 1;
            } else {
                positive[i] = 0;
                negative[i] = 0;
            }
            maxLength = Math.max(maxLength, positive[i]);
        }
        return maxLength;
    }
}

盛最多水的容器（medium)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    //思路：双指针从头尾缩小
    public int maxArea(int[] height) {
        int m = height.length;
        if(m<2)return 0;
        int left = 0,right = m-1;
        int ans = 0;
        while(left<right){
            ans = Math.max(Math.min(height[left],height[right])*(right-left),ans);
            if(height[left]<=height[right])left++;
            else right--;
        }
        return ans;
    }
}

把数组排成最小的数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    //思路:排序+贪心
    //优先贪心选择第一个字符小的
    //x+y < y+x
    public String minNumber(int[] nums) {
        int n = nums.length;
        String[] strs = new String[n];
        for(int i=0;i<n;i++)strs[i] = String.valueOf(nums[i]); 
        Arrays.sort(strs,(x,y)->(x+y).compareTo(y+x));
        StringBuilder sb = new StringBuilder();
        for(int i=0;i<n;i++)sb.append(strs[i]);
        return sb.toString();
    }
}

135. 分发糖果（hard）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    //1.每个孩子至少分配到 1 个糖果。
    //2.相邻两个孩子评分更高的孩子会获得更多的糖果。
    //思路：贪心
    //先对每一个元素设置为1,满足条件1
    //从左边遍历：如果ratings[i]>ratings[i-1]那说明,i分到的糖果多于i-1,即ratings[i]=ratings[i-1]+1
    //从右边遍历：如果ratings[i]>ratings[i+1]那说明,i分到的糖果多于i+1,即ratings[i]=ratings[i+1]+1
    //贪心取两者最大值即为答案
    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;
    }
}

最大交换

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    //贪心:前面查找最小的与后面最大的交换
    public int maximumSwap(int num) {
        StringBuilder sb = new StringBuilder(String.valueOf(num));
        int n = sb.length();
        for(int i=0;i<n;i++){
            char change = sb.charAt(i);
            for(int j=i+1;j<n;j++){
                if(change<sb.charAt(j)){//从[j-,n-1]查找出最大的一个来交换
                    int maxIndex = j;
                    for(int k=maxIndex+1;k<n;k++)maxIndex=sb.charAt(maxIndex)<=sb.charAt(k)?k:maxIndex;
                    char max = sb.charAt(maxIndex);
                    sb.setCharAt(i,max);
                    sb.setCharAt(maxIndex,change);
                    int x = 0;
                    for(int index=0;index<n;index++)x=x*10+sb.charAt(index)-'0';
                    return x;
                }
            }
        }
        return num;
    }
}

煎饼排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
    //思路: 这道题,要想到如何通过翻转把列表最大数依次往列表底移动.
    //例如:[3,2,4,1]---->[?,?,?,4]
    //我们可以先找到数字4的位置,将数字4前进行翻转变成[4,2,3,1],接下来我们在整体翻转[1,3,2,4],这样我们把数字4移动列表底.
    //然后,我们[1,3,2,4]--->[?,?,3,4],还是用刚才方法,首先找到数字3,翻转数字3前面的,再翻转已经排好数字(这里指数字4)前就可以了.
    //依次类推...
    public List<Integer> pancakeSort(int[] arr) {
        List<Integer> ret = new ArrayList<Integer>();
        for (int n = arr.length; n > 1; n--) {
            int index = 0;
            for (int i = 1; i < n; i++) {
                if (arr[i] >= arr[index]) {
                    index = i;
                }
            }
            if (index == n - 1) {
                continue;
            }
            reverse(arr, index);
            reverse(arr, n - 1);
            ret.add(index + 1);
            ret.add(n);
        }
        return ret;
    }

    public void reverse(int[] arr, int end) {
        for (int i = 0, j = end; i < j; i++, j--) {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
}

加油站

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class Solution {
    //思路：贪心
    //[1,2,3,4,5]
    //[3,4,5,1,2]
    //作差
    //[-2,-2,-2,3,6]
    //[-2,-4,-6,-3,0]
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length;
        int retIndex = 0;
        int reduce = 0;
        int up = 0;
        for(int i=0;i<n;i++){
            reduce += gas[i] - cost[i];
            up += gas[i] - cost[i];
            if(up<0){//连续上升不用变
                retIndex = i+1;
                up = 0;
            }
        }
        return reduce>=0?retIndex:-1;
    }
    //
    //gas = [1,2,3,4,5]
    //cost= [3,4,5,1,2]
    //思路：从第一个下标开始累计拥有的汽油和消耗的汽油，如果sumGas<sumCost(表示无法前进)退出循环，判断是否已经走了一轮，
    //如果走完直接返回下标，否则更新最新下标在判断
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int n = gas.length;
        int i = 0;
        while (i < n) {
            int sumOfGas = 0, sumOfCost = 0;
            int cnt = 0;
            while (cnt < n) {
                int j = (i + cnt) % n;//取模
                sumOfGas += gas[j];
                sumOfCost += cost[j];
                if (sumOfCost > sumOfGas) {//花费大于拥有的汽油退出
                    break;
                }
                cnt++;
            }
            if (cnt == n) {//可以通过n个数即一轮
                return i;
            } else {//否则跟下下标
                i = i + cnt + 1;
            }
        }
        return -1;
    }
}

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

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    //贪心:有利可图就出售
    public int maxProfit(int[] prices) {
        int ret = 0;
        int n = prices.length;
        for(int i=1;i<n;i++){
            int price = prices[i]-prices[i-1];
            if(price>0)ret+=price;
        }
        return ret;
    }
}

402. 移掉 K 位数字（mid)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    //思路：贪心+单调栈（遇到num[i]<num[i-1]删除掉num[i-1]）
    public String removeKdigits(String num, int k) {
        int n = num.length();
        Stack<Character> stack = new Stack<>();
        for(int i=0;i<n;i++){
            char c = num.charAt(i);
            while(!stack.isEmpty()&&k>0&&c<stack.peek()){
                stack.pop();k--;
            }
            stack.push(c);
        }
        //k!=0继续弹
        while(k>0&&!stack.isEmpty()){
            stack.pop();k--;
        }
        //拼接结果
        StringBuilder sb = new StringBuilder();
        while(!stack.isEmpty()){
            char p = stack.pop();
            sb.append(p);
        }
        sb.reverse();
        //首位为0
        while(sb.length()>0 && sb.charAt(0)=='0')sb.deleteCharAt(0);
        return sb.length()==0?"0":sb.toString();
    }
}

55. 跳跃游戏（mid)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Solution {
    public boolean canJump(int[] nums) {
        int n = nums.length;
        int rightmost = 0;//可跳到右边的最远距离
        for (int i = 0; i < n; ++i) {
            if (i <= rightmost) {//如果i在上一次的可选范围内则尝试刷新
                rightmost = Math.max(rightmost, i + nums[i]);
                if (rightmost >= n - 1) {
                    return true;
                }
            }
        }
        return false;
    }
}

763. 划分字母区间（mid）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    //思路:记录其出现的最右位置，
    public List<Integer> partitionLabels(String s) {
        int n = s.length();
        int[] right = new int[26];
        List<Integer> ret = new ArrayList<>();
        for(int i=0;i<n;i++){
            right[s.charAt(i)-'a']=i;
        }
        int i=0;
        while(i<n){
            int rightMost = right[s.charAt(i)-'a'];
            //判断(i,rightMost]中检查是否有元素最后出现在rightMost后面
            for(int j=i+1;j<rightMost;j++){
                int jcRight = right[s.charAt(j)-'a'];
                if(jcRight>rightMost){
                    rightMost = jcRight;
                }
            }
            ret.add(rightMost-i+1);
            i = rightMost+1;
        }
        return ret;
    }
}

316. 去除重复字母（mid）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
    //"bcabc"
    //单调栈+贪心
    //遇到字典序比当前字符大的往后查找是否存在重复，如果存在则出栈，否则压栈
    public String removeDuplicateLetters(String s) {
        int n = s.length();
        //记录每个字符最后出现位置
        int[] right = new int[26];
        for(int i=0;i<n;i++)right[s.charAt(i)-'a']=i;
        boolean[] visited = new boolean[26];
        Deque<Character> stack = new ArrayDeque<>();
        for(int i=0;i<n;i++){
            char c = s.charAt(i);
            //栈中已经有该字符
            if(visited[c-'a'])continue;
            //判断当前字符是否小于栈顶字符，且栈顶字符往后还有出现的话将其弹出
            while(!stack.isEmpty() && stack.peek()> c && i < right[stack.peek()-'a']){
                char p = stack.pop();
                visited[p-'a'] = false;
            }
            //压入当前字符
            stack.push(c);
            //设置当前字符已经访问过
            visited[c-'a']=true;
        }
        StringBuilder sb = new StringBuilder();
        while(!stack.isEmpty())sb.append(stack.pop());
        return sb.reverse().toString();
    }
}

767. 重构字符串（mid)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
    //思路：最多的那个字符不能超过总字符的一半，优先摆放出现次数最多的字符到数组的偶数位置，在将其他字符依次插入奇数位
    public String reorganizeString(String s) {
        char[] arr = s.toCharArray();
        int n = arr.length;
        int[] count = new int[26];
        //统计每个字符出现的次数
        for(char c : arr)count[c-'a']++;
        //得到出现最多次数的字符的下标
        int maxIndex = 0;
        for(int i=0; i<count.length; i++){
            if(count[i] > count[maxIndex]) maxIndex = i;
        }
        //最多的那个字符不能超过总字符的一半否则直接返回
        // (n+1) / 2 同时考虑了 奇数 和 偶数 情况
        if(count[maxIndex] > (n+1)/2)   return "";

        // 先把出现次数最多的字符放在偶数位置上
        char[] res = new char[n];
        int i = 0;
        while(count[maxIndex]-- > 0){
            res[i] = (char)('a' + maxIndex);
            i += 2;
        }
        // 考虑其他的字符
        for(int j=0; j<count.length; j++){
            while(count[j]-- > 0){
                if(i >= n)  i = 1; // 偶数位置用完了，放到奇数位置
                res[i] = (char)('a' + j);
                i += 2;
            }
        }

        return String.valueOf(res);
    }
}

1353. 最多可以参加的会议数目（mid)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
    //思路：排序+贪心(在开始时间相同的情况下尽量选择结束时间短的)
    public int maxEvents(int[][] events) {
        int n = events.length;
        // 按照开始时间升序排列，这样，对于相同开始时间的会议，可以一起处理
        Arrays.sort(events, ((o1,o2)->o1[0]-o2[0]));
        // 小顶堆：用于高效的维护最小的 endDay
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        int res = 0;
        int currDay = 1;
        int i = 0;
        while (i < n || !pq.isEmpty()) {
            // 将所有开始时间等于 currDay 的会议的结束时间放到小顶堆
            while (i < n && events[i][0] == currDay) {
                pq.add(events[i][1]);
                i++;
            }
            // 将已经结束的会议弹出堆中，即堆顶的结束时间小于 currDay 的
            while (!pq.isEmpty() && pq.peek() < currDay) {
                pq.remove();
            }
            // 贪心的选择结束时间最小的会议参加
            if (!pq.isEmpty()) {
                // 参加的会议，就从堆中删除
                pq.remove();
                res++;
            }
            // 当前的天往前走一天，开始看下下一天能不能参加会议
            currDay++;
        }
        return res;
    }
}

44. 通配符匹配（hard）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
class Solution {
    public boolean isMatch(String s, String p) {
        int sRight = s.length(), pRight = p.length();
        while (sRight > 0 && pRight > 0 && p.charAt(pRight - 1) != '*') {
            if (charMatch(s.charAt(sRight - 1), p.charAt(pRight - 1))) {
                --sRight;
                --pRight;
            } else {
                return false;
            }
        }

        if (pRight == 0) {
            return sRight == 0;
        }

        int sIndex = 0, pIndex = 0;
        int sRecord = -1, pRecord = -1;
        
        while (sIndex < sRight && pIndex < pRight) {
            if (p.charAt(pIndex) == '*') {
                ++pIndex;
                sRecord = sIndex;
                pRecord = pIndex;
            } else if (charMatch(s.charAt(sIndex), p.charAt(pIndex))) {
                ++sIndex;
                ++pIndex;
            } else if (sRecord != -1 && sRecord + 1 < sRight) {
                ++sRecord;
                sIndex = sRecord;
                pIndex = pRecord;
            } else {
                return false;
            }
        }

        return allStars(p, pIndex, pRight);
    }

    public boolean allStars(String str, int left, int right) {
        for (int i = left; i < right; ++i) {
            if (str.charAt(i) != '*') {
                return false;
            }
        }
        return true;
    }

    public boolean charMatch(char u, char v) {
        return u == v || v == '?';
    }
}

252. 会议室（easy)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public boolean canAttendMeetings(int[][] intervals) {
        int n = intervals.length;
        if(n==0)return true;
        //对开始时间进行排序，如果存在第i+1个会议的开始时间小于第i个会员的结束时间则false
        Arrays.sort(intervals,(o1,o2)->o1[0]-o2[0]);
        int end = intervals[0][1];
        for(int i=1;i<n;i++){
            int curStart = intervals[i][0];
            if(curStart<end)return false;
            end = intervals[i][1];
        }
        return true;
    }
}

253. 会议室 II（mid）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    //---
    //----
    // --
    //   ---
    //思路：计算重叠区间,如果存在n场会议重叠则需要n个会议室
    //抄别人的优先队列
    public int minMeetingRooms(int[][] intervals) {
        if(intervals==null||intervals.length==0) return 0;
        // 按结束时间排序
    	PriorityQueue<Integer> queue = new PriorityQueue<Integer>();
        // 按开始时间排序
    	Arrays.sort(intervals,(i,j)->i[0]-j[0]);
    	queue.add(intervals[0][1]);
    	for(int i=1;i!=intervals.length;i++) {
    		int last=queue.peek();//最早结束的
    		if(last<=intervals[i][0]) { // 最早结束的可以腾出会议室
    			queue.poll();
    		    queue.add(intervals[i][1]); //修改该会议室的结束时间
            }else{ //最早结束的都来不及腾出会议室
                queue.add(intervals[i][1]);// 需要一个新的会议室
            }
    	}
    	return queue.size();
    }
}

376. 摆动序列（mid)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    //思路：记录前一个是上坡(下坡)，查找下一个下坡(上坡)
    public int wiggleMaxLength(int[] nums) {
        int n = nums.length;
        if (n < 2) return n;
        //前面相差的值
        int prevdiff = nums[1] - nums[0];
        int ret = prevdiff != 0 ? 2 : 1;
        //迭代比较
        for (int i = 2; i < n; i++) {
            int diff = nums[i] - nums[i - 1];
            //上坡或者下坡（如果前面是下坡，那么只有现在是上坡才能计数）
            if ((diff > 0 && prevdiff <= 0) || (diff < 0 && prevdiff >= 0)) {
                ret++;
                prevdiff = diff;
            }
        }
        return ret;
    }
}

870. 优势洗牌（mid)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
    //田忌赛马
    //贪心：每次选择刚刚好超过num2[i]的数来覆盖,如果没有则选择最小的来覆盖num2[i]
    public int[] advantageCount(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        int[] ret = new int[m];
        //对nums1排序
        Arrays.sort(nums1);
        //大堆顶
        PriorityQueue<int[]> queue = new PriorityQueue<>((o1,o2)->o2[0]-o1[0]);
        for(int i=0;i<n;i++)queue.offer(new int[]{nums2[i],i});
        //定义左右指针指向最大最小值
        int left = 0;
        int right = m-1;
        while(!queue.isEmpty()){
            int[] pop = queue.poll();
            int num = pop[0],index = pop[1];
            //从nums1查找数据
            if(nums1[right]>num){
                ret[index] = nums1[right];
                right--;
            }else{
                ret[index] = nums1[left];
                left++;
            }
        }
        return ret;
    }
}

435. 无重叠区间（mid)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    //贪心:按照结束时间排序最大可能组成不冲突的区间，在用n减去组成的区间
    public int eraseOverlapIntervals(int[][] intervals) {
        int n = intervals.length;
        if(n==0)return 0;
        Arrays.sort(intervals,(o1,o2)->o1[1]-o2[1]);
        //最少能取一个区间
        int ret = 1;
        //前面一个区间的结束
        int preEnd = intervals[0][1];
        for(int i=1;i<n;i++){
            //如果当前的开始时间大于等于前面一个区间的结束值，则可取
            if(intervals[i][0]>=preEnd){
                ret++;//可取区间加一
                preEnd = intervals[i][1];//更新结束值
            }
        }
        //结果作差
        return n-ret;
    }
}

2038. 如果相邻两个颜色均相同则删除当前颜色（mid)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Solution {
    /**
     * 贪心：分别计算出alice和bob的可操作数
     */
    public boolean winnerOfGame(String colors) {
        int n = colors.length();
        int alice = 0,bob = 0;
        for (int i = 1; i < n-1; i++) {
            if(colors.charAt(i-1)=='A'&&colors.charAt(i)=='A'&&colors.charAt(i+1)=='A')alice++;
            else if(colors.charAt(i-1)=='B'&&colors.charAt(i)=='B'&&colors.charAt(i+1)=='B')bob++;
        }
        return alice>bob;
    }
}

942. 增减字符串匹配（easy）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    //如果 s[i] == 'I'，那么perm[i] < perm[i + 1]   
    //如果 s[i] == 'D'，那么perm[i] > perm[i + 1] 
    //如果 s[0]=‘I’，那么令 perm[0]=0，则无论 perm[1] 为何值都满足 perm[0]<perm[1]
    //如果 s[0]=‘D’，那么令 perm[0]=n，则无论 perm[1] 为何值都满足 perm[0]>perm[1]
    //确定好 perm[0] 后，剩余的 n−1 个字符和 n 个待确定的数就变成了一个和原问题相同，但规模为 n−1 的问题。
    //
    //两个指针来控制值，如果当前是’I‘则赋值并自增low，否则是’D‘则赋值并自键
    public int[] diStringMatch(String s) {
        int n = s.length();
        int[] ret = new int[n+1];
        int low = 0,height = n;
        for(int i=0;i<n;i++){
            ret[i] = s.charAt(i)=='I'?low++:height--;
        }
        ret[n] = low;
        return ret;
    }
}

241. 为运算表达式设计优先级（mid）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
    //贪心
    //将expression看做一个整体，对其进行左右划分，得出左右式子的结果再组合
    String expression;
    public List<Integer> diffWaysToCompute(String expression) {
        int n = expression.length();
        this.expression = expression;
        return dfs(0,n-1);
    }
    private List<Integer> dfs(int left,int right){
        List<Integer> ret = new ArrayList<>();
        for(int i=left;i<=right;i++){
            char c = expression.charAt(i);
            if(c>='0'&&c<='9')continue;
            List<Integer> l1 = dfs(left,i-1),l2 = dfs(i+1,right);
            for(int a:l1){
                for(int b:l2){
                    int cur = 0;
                    if(c=='+')cur = a+b;
                    if(c=='-')cur = a-b;
                    if(c=='*')cur = a*b;
                    ret.add(cur);
                }
            }
        }
        //如果ret是空说明当前[left,right]表达式不可再分，直接取值即可
        if(ret.isEmpty()){
            int cur = 0;
            for(int i=left;i<=right;i++)cur = cur * 10 + expression.charAt(i)-'0';
            ret.add(cur);
        }
        return ret;
    }
}

相关资料

基础算法 > 刷题记录
#贪心
算法笔记-贪心类型
https://mikeygithub.github.io/2020/07/01/yuque/算法笔记-贪心类型/
作者
Mikey
发布于
2020年7月1日
许可协议