力扣刷题记录10.12

k

2024/10/12

（1）贪心

1、加油站

在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。

你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。

给定两个整数数组 gas 和 cost ，如果你可以按顺序绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则 保证 它是 唯一 的。

思路：每个加油站的汽油数减去开往下一个加油站的消耗数，就是这一站能剩余的汽油数。如果加起来小于0就说明一定不能环路一周。如果可以，由于题目说开始的加油站的编号唯一，则到达那个加油站前，累计的剩余汽油数一定是最少的。否则这一站出发一定会到不了后面的某一站。

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int n=gas.size(),cnt=0,min_g=0,ans=0;
        for(int i=0;i<n;i++){
            cnt+=gas[i]-cost[i];
            if(cnt<min_g){
                min_g=cnt;
                ans=i+1;
            }
        }
        return cnt<0?-1:ans;
    }
};

2、分发糖果

n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。

你需要按照以下要求，给这些孩子分发糖果：

• 每个孩子至少分配到 1 个糖果。
• 相邻两个孩子评分更高的孩子会获得更多的糖果。

请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。

需要考虑两边！！！！

这个思路很简单聪明：就是维护两个数组分别代表从左、右遍历后每个人分发的糖果数。起始每个人糖果数均为1，如果大于前一个人的糖果数，则比前一个人多一个。最后比较左右遍历的数组中每个小孩的糖果数，较大的那个值才能满足条件。这样累加起来是满足条件并且需要准备的糖果最少。

class Solution {
public:
    int candy(vector<int>& ratings) {
        int n=ratings.size();
        vector<int> left(n,1),right(n,1);
        int cnt=0;
        for(int i=1;i<n;i++)
            if(ratings[i]>ratings[i-1])
                left[i]=left[i-1]+1;
        for(int i=n-2;i>=0;i--){
            if(ratings[i]>ratings[i+1]){
                right[i]=right[i+1]+1;
            }
            cnt+=max(left[i],right[i]);
        }
        return cnt+max(left[n-1],right[n-1]);
    }
};

（2）广度优先搜索

1、课程表

你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。

在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。

• 例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。

请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        vector<int> step(numCourses,0);   //存储每个课程依赖的先修课程数（度数）
        unordered_map<int,vector<int> > map;   //键：被依赖的课程    值：被它依赖的课程集合
        int cnt=0;   //计算一共能修多少节课
       //遍历依赖数组
        for(auto pre:prerequisites){
            step[pre[0]]++;   //更新度数
            map[pre[1]].push_back(pre[0]);  //更新依赖该课程的课程清单
        }
       
        queue <int> zero;  //放置零度课程，也就是可以直接修读的课程
        for(int i=0;i<numCourses;i++)
            if(!step[i])
                zero.push(i);
       
        while(!zero.empty()){
            int select=zero.front();   
            zero.pop();   //出队列，表示修读本课程
            cnt++;       //更新已修读课程数
            for(int cur: map[select]){   //在修读的课程的依赖课程清单中遍历
                if(--step[cur]==0)    //把要依赖此修读课程的课程的度数减一，并判断此时它的度数是否清零
                    zero.push(cur);   //如果它的度数清零则也将它加入零度课程数组
            }
        }
        return cnt==numCourses;     //如果最后修读的课程数不满总课程数说明无法修完，返回-1
    }
};

（3）回溯

1、电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。给出数字到字母的映射如下（与电话按键相同）。注意 0、1 不对应任何字母。

注意：

• digits是字符串，映射到数字时要减去'0'

class Solution {
   //按顺序存储2-9代表的字符串
    string MAPPING[10] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    
    // 定义一个成员函数来替代 lambda 实现递归
    void dfs(const string& digits, int i, string& path, vector<string>& ans) {
        if (i == digits.length()) { // 递归结束条件
            ans.emplace_back(path); // 将完整的路径加入结果集
            return;
        }
        for (char c : MAPPING[digits[i] - '0']) { // 遍历数字对应的字母
            path[i] = c; // 放入当前的字母
            dfs(digits, i + 1, path, ans); // 递归处理下一个数字
        }
    }

public:
    vector<string> letterCombinations(string digits) {
        int n = digits.length();
        if (n == 0) {
            return {}; // 如果输入为空，返回空的 vector
        }
        vector<string> ans;
        string path(n, 0); // 初始化 path，长度为 n
        dfs(digits, 0, path, ans); // 调用递归函数
        return ans;
    }
};

（）？

给一个数组，只含有0或者1，求最大的连续的0的个数；注意：有一次机会可以将数字翻转（1变成0，或者0变成1）。

int findMaxConsecutiveZeros(vector<int>& nums) {
    int maxCount = 0;        // 记录最大连续0的数量
    int zeroCount = 0;       // 当前连续0的数量
    int flipZeroCount = 0;   // 翻转1后的连续0数量

    for (int i = 0; i < nums.size(); ++i) {
        if (nums[i] == 0) {
            zeroCount++;      // 当前连续0计数增加
            flipZeroCount++;  // 翻转后的连续0计数也增加
        } else {
            // 当遇到1时，尝试翻转这个1
            flipZeroCount = zeroCount + 1; // 翻转后的连续0数量是当前zeroCount + 1
            zeroCount = 0;  // 翻转后，重置当前的连续0计数器
        }
        maxCount = max(maxCount, flipZeroCount); // 更新最大连续0的个数
    }

    return maxCount;
}