LeetCode算法刷题_leetcode离线刷题

天气：晴
刮风；
今天继续刷贪心算法题目

---

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

这题目看起来有点难以理解，多看几遍就懂了（反复结合例子去看）

结题思路：
用贪心算法的思想，每次选数组中最大的数就能保证所选的子序列满足条件而且是比较短的，直到选取数大于剩下的数为止
这是我的代码实现：

class Solution {
public:
    vector<int> minSubsequence(vector<int>& nums) {
        int S = 0;
        for(auto x : nums){
            S += x;
        }
        sort(nums.begin(),nums.end());

        vector<int> ans;
        int c=0;
        for(int i=nums.size() - 1;i >= 0;--i){
            if(c + nums[i] > (S - c - nums[i])){
                ans.push_back(nums[i]);
                return ans;
            }else{
                ans.push_back(nums[i]);
                c += nums[i];
            }
        }
        return ans;
    }
};
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:
    vector<int> minSubsequence(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int sum = 0;
        for (auto item : nums) {
            sum += item;
        }
        vector<int> res;
        int sum1 = 0;
        for (int i = nums.size() - 1; i >= 0; i--) {
            res.push_back(nums[i]);
            sum1 += nums[i];
            if (sum1 * 2 > sum) {
                break;
            }
        }
        return res;
    }
};

作者：ByNir
链接：https://leetcode-cn.com/problems/minimum-subsequence-in-non-increasing-order/solution/zhao-da-yu-yi-ban-de-xu-lie-by-bynir/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
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

1217 .玩筹码

---

这题感觉就是阅读理解，详细题解可以参考leetcode上面的解题思路
这题开始我也没想到这么简单

class Solution {
public:
    int minCostToMoveChips(vector<int>& position) {
        //贪心策略尽量进行2的跳转
        //所有偶数位置的都能通过’2‘移动到同一位置，所有的奇数位置也是
        //同时由于我们所求的最小代价,
        int sumOdd,sumEven;
        sumOdd=sumEven=0;
        for(int i=0;i<position.size();i++)
          {
              if(position[i]%2==0) sumOdd++;
              else sumEven++;
          }

        if(sumEven>sumOdd)   return sumOdd;
        else return sumEven;  

    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

392.判断子序列

---

 **使用双指针方法就很方便** 我的想法和官方的想法差不多 但是官方有个动态规划的思想是我没想到

class Solution {
public:
    bool isSubsequence(string s, string t) {
        //首先我所想到的就是遍历算法的实现
        //使用遍历算法在s中找出t中字母所对应的字的位置，在于前一个位置比较，小于则继续进行下一步

    
        //leetcode题解所使用的是双指针的方式+贪心策略
        int sPoint,tPoint;
        sPoint=tPoint=0;
        while(sPoint<s.length()&&tPoint<t.length())
        {
            if(s[sPoint]==t[tPoint]) {sPoint++;}
            tPoint++;
        }
        if(sPoint==s.length()) {return true;}
        else
        {return false;}
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

---

---

---

今晚高数测验，感觉就是自己写过的方法模模糊糊，这样子的学习状态可不对，做学问的人不能这么浮躁

---

鲁迅的《明天》--

只有那暗夜为想变成明天，却仍在这寂静里奔波；另有几天狗，也躲在暗地里呜呜的叫。