发表更新刷题15 分钟读完 (大约2242个字)

贪心算法

贪心

NC134 股票(无限次交易)

描述

假定你知道某只股票每一天价格的变动。

你最多可以同时持有一只股票。但你可以无限次的交易（买进和卖出均无手续费）。

请设计一个函数，计算你所能获得的最大收益。

示例

1
[1,2,3,4,5]

最优策略是第一天买，最后一天卖。

实际上可以简化成，只要是两天之间是上涨的，那我们就要这一段的收益。

解法：贪心

参考评论区

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 计算最大收益
     * @param prices int整型一维数组 股票每一天的价格
     * @return int整型
     */
    public int maxProfit (int[] prices) {
        // write code here
        int n = prices.length;
        int ans=0;
        for(int i=1;i<n;i++){
            if(prices[i]>prices[i-1]){
                ans += prices[i]-prices[i-1];
            }
        }
        return ans;
        
    }
}

解法：动态规划

参考评论区：【数据结构和算法】动态规划和贪心算法，图文详解_牛客博客 (nowcoder.net)

定义dp[i][0]表示第i+1天交易完之后手里没有股票的最大利润，

dp[i][1]表示第i+1天交易完之后手里持有股票的最大利润。

当天交易完之后手里没有股票可能有两种情况:

  • 一种是当天没有进行任何交易，又因为当天手里没有股票，所以当天没有股票的利润只能取前一天手里没有股票的利润。
  • 一种是把当天手里的股票给卖了，既然能卖，说明手里是有股票的，所以这个时候当天没有股票的利润要取前一天手里有股票的利润加上当天股票能卖的价格。这两种情况我们取利润最大的即可，所以可以得到
1
dp[i][0]=max(dp[i-1][0],dp[i-1][1]+prices[i]);

当天交易完之后手里持有股票也有两种情况

  • 一种是当天没有任何交易，又因为当天手里持有股票，所以当天手里持有的股票其实前一天就已经持有了。
  • 还一种是当天买入了股票，当天能买股票，说明前一天手里肯定是没有股票的，我们取这两者的最大值，所以可以得到
1
dp[i][1]=max(dp[i-1][1],dp[i-1][0]-prices[i]);

动态规划的递推公式有了，那么边界条件是什么，就是第一天:

  • 如果买入：dp[0][1] = -price[0]
  • 如果没买：dp[0][0] = 0

代码：

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
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 计算最大收益
     * @param prices int整型一维数组 股票每一天的价格
     * @return int整型
     */
    public int maxProfit (int[] prices) {
        // write code here
        if (prices == null || prices.length < 2){
            return 0;
        }
        int length = prices.length;
        int [][]dp = new int[length][2];
        // 初始条件
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        
        for(int i=1;i<length;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]);
        }
    //最后一天肯定是手里没有股票的时候，利润才会最大，
    //只需要返回dp[length - 1][0]即可
    return dp[length - 1][0];
        
    }
}

总结：

其实际上是对当天交易完后，手上有没有股票进行了划分。

如果当天交易完后，手上没有股票，可能有两种情况：

  1. 昨天就没有股票，故今天没有股票的利润取一天的
  2. 昨天有股票，今天卖掉了，故今天没有股票的利润应该是取前一天股票的利润加上今天卖出的价格

如果当天交易完后，手上还有股票，可能有两种情况：

  1. 昨天没有股票，今天买入的，今天还能买入，说明昨天没有股票；故是拿昨天没有股票的利润减去今天买入的价格
  2. 昨天有股票，今天没有卖；故今天持有股票的利润是昨天持有的利润

解法：代码优化

上面的计算中可以看出当天的利润只和前一天有关，没有必要使用二维数组，只需要使用两个变量：

  • 一个记录当天交易完后持有股票的最大利润
  • 一个记录当天交易完后不持有股票的最大利润
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
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 计算最大收益
     * @param prices int整型一维数组 股票每一天的价格
     * @return int整型
     */
    public int maxProfit (int[] prices) {
        // write code here
        if (prices == null || prices.length < 2){
            return 0;
        }
        int length = prices.length;
        int hold = -prices[0]; // 第一买入
        int noHold = 0; // 第一天不买

        for(int i=1; i<length;i++){
            noHold = Math.max(noHold,hold+ prices[i];  
            hold = Math.max(hold, noHold - prices[i]);
        }

    //最后一天肯定是手里没有股票的时候，利润才会最大，
    //只需要返回dp[length - 1][0]即可
    return noHold;  
    }
}

NC130 分糖果问题

描述

一群孩子做游戏，现在请你根据游戏得分来发糖果，要求如下：

  1. 每个孩子不管得分多少，起码分到一个糖果。

  2. 任意两个相邻的孩子之间，得分较多的孩子必须拿多一些糖果。(若相同则无此限制)

给定一个数组 arrs代表得分数组，请返回最少需要多少糖果。

要求: 时间复杂度为 $O(n)$ 空间复杂度为 $O(1)$。

解法：左右各遍历一次

  • 把所有孩子的糖果数初始化为 1;
  • 先从左往右遍历一遍，如果右边孩子的评分比左边的高，则右边孩子的糖果数更新为左边孩子的 糖果数 加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
public class Solution {
    /**
     * pick candy
     * @param arr int整型一维数组 the array
     * @return int整型
     */
    public int candy (int[] arr) {
        // write code here
        int [] tmp = new int[arr.length];
        Arrays.fill(tmp,1);
        int count = 0;
        // 从左往右遍历
        for(int i=1;i<arr.length;i++){
            // 右边的比左边的大
            if(arr[i]>arr[i-1]){
                tmp[i] = tmp[i-1]+1;
            }
        }
        // 从右往左遍历
        for(int i=arr.length-1; i > 0; i--){
            // 如果左的大于右边的
            if(arr[i-1] > arr[i]){
                // 左边的至少比右边的大1
                tmp[i-1] = Math.max(tmp[i-1],tmp[i]+1);
            }
        }
        for(int i:tmp){
            count += i;
        }
        return count;
    }
}

NC85 拼接所有的字符串产生字典序最小的字符串

描述

给定一个长度为n的字符串数组 str ，请找到一种拼接顺序，使得数组中所有的字符串拼接起来组成的字符串是所有拼接方案中字典序最小的，并返回这个拼接后的字符串。

解法：重载比较函数

解体思路：

“abc”, “de”

拼接后：”abcde” < “deabc”

因此，我们只需要将每个字符串进行拼接后比较，既 str1 + str2 ? str2 + str1

算法流程：

  • Java通过重写优先级队列PriorityQueue的比较器方法
  • 保证 s1 + s2 > s2 + s1 时，返回值大于0，否则返回值小于0
  • 同时保证queue中越靠近队头的元素，字典序越小
  • 将所有字符串放入队列中排好序，然后重新从队列中获取
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
public class Solution {
    /**
     * 
     * @param strs string字符串一维数组 the strings
     * @return string字符串
     */
    public String minString (String[] strs) {
        // write code here
        if(strs == null || strs.length < 1){
            return null;
        }
        // 重载比较函数
        PriorityQueue<String> queue = new PriorityQueue<>(new Comparator<String>(){
           public int compare(String s1,String s2){
               // 保证 s1 + s2 > s2 + s1时，返回值大于0，否则返回值小于0
               // 保证 queue中越靠近队头的元素，字典序越小
               return (s1 + s2).compareTo(s2 + s1);
           } 
        });
        
        // 放入队列中进行排序
        for(String str:strs){
            queue.offer(str);
        }
        
        StringBuilder res = new StringBuilder();
        // 重新从队列中获取
        while(queue.size() > 0){
            res.append(queue.poll());
        }
//         System.out.println(res);
        return res.toString();
    }
}

解法二：快排

来自评论区：题解 | #拼接所有的字符串产生字典序最小的字符串#_牛客博客 (nowcoder.net)

NC147 主持人调度

描述

有n个活动即将举办，每个活动都有活动的开始时间与活动的结束时间，第$i$个活动的开始时间是 $start_i$ ，第$i$个活动的结束时间是$end_i$,举办某个活动就需要为该活动准备一个活动主持人。一位活动主持人在同一时间只能参与一个活动。并且活动主持人需要全程参与活动，换句话说，活动主持人参与了第$i$个活动，那么该主持人在 $strat_i$, $end_i$ 这个时间段不能参与其他任何活动。求为了成功举办这n个活动，最少需要多少名主持人。

解法：优先级队列

来自评论区：NC147 主持人调度（四种语言+视频讲解）_牛客博客 (nowcoder.net)

根据题意，如果想要合理的分配这个问题，就必须安装活动的开始时间从小到大往后排，只有这样才能确保每一步都是最优的。

  • 如果两个活动开始的时间一样，那就按结束时间早的来排序
  • 如果a、b两活动中a的结束时间比b的开始时间大，那么b活动肯定就需要一名主持人（相交）
  • 故整个算法核心确定了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def minmumNumberOfHost(self , n , startEnd ):
        # write code here
        import heapq
        # 按照起始时间，从小到大排序
        startEnd = sorted(startEnd,key=lambda x:x[0])

        pq = [] # 用来控制调度的结束时间
        heapq.heappush(pq,startEnd[0][1]) # 添加第一个活动的结束时间

        # 遍历剩余的活动
        for i in range(1,n):
            # 如果当前活动的开始时间，在前一个活动的结束时间之后，则不需要添加主持人
            if startEnd[i][0] >= pq[0]:
                heapq.heappop(pq) # 当前活动出队，当前主持人即可完成
            
            # 否则，将该活动的结束时间添加到队列中
            heapq.heappush(pq,startEnd[i][1])
        return len(pq)

贪心算法

http://example.com/2021/09/01/贪心算法/

作者

bd160jbgm

发布于

2021-09-01

更新于

2021-09-14

许可协议

#

喜欢这篇文章？打赏一下作者吧

关注我

链接

分类

最新文章

标签

BFS3
DFS3
Java面经1
algorithm4
android1
bfs2
c++9
dfs7
dp1
dpLearning13
java1
jvm9
ordered-map1
python8
spring6
sql3
tools16
二分查找1
二叉树13
位运算10
傻屌题1
分治2
分治算法2
动态规划6
双指针7
哈希1
哈希表2
回溯5
堆2
堆排序1
多线程1
字符串5
总结1
找规律2
指针1
排序9
数字1
数据库1
数组9
最短路径1
查找2
栈9
树12
测试6
测试知识1
滑动窗口1
自动机1
计算机基础2
计算机网络1
计算机网络基础1
论文阅读10
设计1
贪心算法3
较难13
递归6
链表14
队列1
需要review8
面试记录1
×