LeetCode热题（HOT 100）解题思路与代码_hot100在哪

739. 每日温度

题意就是要找在给定的一个序列中，指定元素后方第一个比它大的元素与该元素之间的距离，这道题借鉴了题解中第一位作者pilsaryu的思路（没有用栈来做，主要是还不太会用STL^_ ^），逆序对该数组进行遍历，遍历过程中首先记下倒数第一二个数的结果到结果数组中，然后对于其余元素，先与该元素后方的第一个元素比较，如果该元素比后方第一个元素小，那么该位置结果为1，结果写入结果数组，并continue到下次循环中；如果比后方第一个元素大，则通过之前得到的结果数组来直接寻找比后一个元素大的位置的元素，并进行比较，以此类推，直到查询到数组的最末端（这样就不用对每一个元素进行遍历）。
简单来讲就相当于在一个队伍中大家都拿着数字牌子，我先问一下我后面的人，发现他的数字没有我的大，然后我问他，上一个比你更大的在哪？然后我直接去找那个人，再比较，如果没有，继续问，继续比较，直到找到队尾，如果一直到队尾都没有人比我的数字大，那我这里结果就是0。
我这里是用容器做的，第一次用迭代器，两个迭代器绕来绕去都要绕晕了而且不能互相赋值，后来发现可以直接用int来代替迭代器，我。。。

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& T) {
        vector<int> indexArr(T.size(), 0);
        for(auto it = T.end()-2, itIndex = indexArr.end()-2; it != T.begin()-1; it--)
        {
            auto src = itIndex; // 记录当前位置
            if(*it < *(it+1)) // 比较与后一位数字的大小
            {
                *src = 1;
                itIndex--; // 后退一位继续循环
                continue;
            }
            for(itIndex++; itIndex != indexArr.end(); itIndex+=*itIndex)
            {
                if(*it < *(it+(itIndex-src)))
                {
                    *src = itIndex-src;
                    break;
                }
                else if(*itIndex == 0)
                {
                    *src = 0;
                    break;
                }
            }
            itIndex = src-1; // 重新给itIndex赋值，使其指向前一位
        }
        return indexArr;
    }
};
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

647. 回文子串

621. 任务调度器

第一眼看到这个题，感觉题意跟以前经常见到的一个做饭时间最短的问题差不多。首先想法就是以任务数量最多的那一个任务（设为A）为基准进行求解，然后第二个、第三个任务等等就可以往任务A的冷却间隔中插入，由于插入过程只有一种（因为要保持冷却间隔），所以不用考虑具体的插入代码，基本思路就是这样。

class Solution {
public:
    int leastInterval(vector<char>& tasks, int n) {
        // 基本思路就是先执行最多的任务（A），然后执行第二多（B），以此类推
        // 在最多的任务（A）被执行后的时间，一到n就再次执行A，以便降低最后的冷却时间，从而使时间最短
        // 最短时间是与最多次数的任务直接相关的
        
        // 解法
        int task[26] = {0}; // 初始化一个全为0的任务数组，用来统计任务数量
        int length = tasks.size();
        // 1.先遍历一遍列表，求出任务种类数和每种任务的数量
        for(auto it = tasks.begin(); it != tasks.end(); it++)
        {
            task[(*it-'A')]++;
        }
        sort(task, task+26); // 对任务数组进行升序排列
        int maxTask = task[25]; // 最多的任务次数
        int cntTask = (maxTask - 1) * (n + 1) + 1; // 最少要执行的任务次数
        for(int i = 24; i >= 0 && task[i] == maxTask; i--)
        {
            cntTask++;
        }
        // 当间隔可以容纳下所有的任务时，返回cntTask，当间隔不能满足时，返回数组长度
        return cntTask > length ? cntTask : length;
    }
};
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

这里涉及到一个返回时比较大小的问题，现在考虑一下代码中的循环部分，思路是当碰到一个跟A任务数量相同的任务（B）时，这时A和B是同样排开的（例如A-B-A-B-A-B），所以就要在A所计算出的最小任务时间上加一，后面以此类推。
这时就出现一个问题，如果所有任务A的总间隔(A-1)*n能放得下其余任务，那么我们便可以直接返回最小时间；如果A的冷却间隔不能够容下所有任务呢？这时就可以直接返回数组长度。