前言

从力扣100题开始的算法总结，决定真正走科班的代码之路后，果然还是得彻底从头开始总结一些算法代码了，感觉会是一个长期的总结过程，而且还要保持长期热情，只能加油吧。之前技能点全点在做游戏上了，但如果真的决定要改变世界，那就不能止步不前了。

这个总结目前来说还比较简单片面，后续可能考虑针对各个算法进行单一深入应用总结。

wallhaven-5g22q5_1920x1080

哈希

这一部分其实主要是利用哈希表来辅助解决问题。

可能困难比较大的是记住哈希表的使用方式（呃呃这就是记性差的坏处了）

记住之后很多问题在考虑到查找、拼接就可以直接从哈希表入手了：

unordered_map<string, vector<string>> groups;
for(auto it = groups.begin(); it != groups.end(); it++)
{
    ans.emplace_back(it->second);           // 每一组键值对的值加入结果中
}

unordered_set<int> st(nums.begin(), nums.end()); // 把 nums 转成哈希集合
st.contains(x - 1); // 哈希判断条件

经典题目链接：

49. 字母异位词分组 - 力扣（LeetCode）

128. 最长连续序列 - 力扣（LeetCode）

双指针

双指针题目比较灵活，可以有以下两类（目前）：

  1. 指针同时出发，主要挪动一个指针，满足特定条件再挪动另一个指针
  2. 指针同时出发，但是位于数列两端，进行比较选择挪动的指针

代表性题目分别有：

283. 移动零 - 力扣（LeetCode）

42. 接雨水 - 力扣（LeetCode）

滑动窗口

先附上比较玄妙的一道题：

438. 找到字符串中所有字母异位词 - 力扣（LeetCode）

这个的话比较字面意思，有点像双指针，主要通过动态调节窗口大小，来满足特定条件

主要操作是拓展窗口、缩减窗口、比较、选择。

然后可能会和子串在一起。

子串

普通数组

矩阵

链表

二叉树

图论

回溯

主要是有一个标准的板子

在此记录一下（其实感觉不是很难）

题目出处：46. 全排列 - 力扣（LeetCode）

class Solution {
private:
    vector<vector<int>> res;
    vector<int> path;
public:
    void backtracking(vector<int>& nums, vector<bool>& used)
    {
        if (path.size() == nums.size())
        {
            res.push_back(path);
            return;
        }

        for (int i = 0; i < nums.size(); i++)
        {
            if (used[i] == true)   //如果该元素被使用过了，则直接跳过
                continue;

            used[i] = true;        //下面要用，先标记上已使用
            path.push_back(nums[i]);
            backtracking(nums, used);
            path.pop_back();       //回溯path和used，即将本层的处理全部Ctrl + Z(撤销~~)
            used[i] = false;
        }
    }

    vector<vector<int>> permute(vector<int>& nums) 
    {
        vector<bool> used(nums.size(), false);
        backtracking(nums, used);
        return res;
    }
};

还有感觉时不时可以回忆一下n皇后：51. N 皇后 - 力扣（LeetCode）

把**行（row）**视为回溯推进的路标！

感觉重要的就是路标的标定和查找。

二分查找

感觉是因为自己有一个很笨笨的方法，导致写的每次逻辑都非常不通畅。

因此在此记录下两者区别：

题目出处：153. 寻找旋转排序数组中的最小值 - 力扣（LeetCode）

官方题解：

class Solution {
public:
    int findMin(vector<int>& nums) {
        int low = 0;
        int high = nums.size() - 1;
        while (low < high) {
            int pivot = low + (high - low) / 2;
            if (nums[pivot] < nums[high]) {
                high = pivot;
            }
            else {
                low = pivot + 1;
            }
        }
        return nums[low];
    }
};

作者：力扣官方题解
链接：https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array/solutions/698479/xun-zhao-xuan-zhuan-pai-xu-shu-zu-zhong-5irwp/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

我的铸币理解：

class Solution {
public:
    int findMin(vector<int>& nums) {
        if(nums.size() == 1)
            return nums[0];
        return find(0,nums.size()-1,nums);
    }

    int find(int left,int right,vector<int> nums)
    {
        int mid = (left + right)/2;
        if(left == right-1)
        {
            return nums[right] > nums[left] ? nums[left] : nums[right];
        }
        else if(nums[mid]<nums[left])
        {
            return find(left,mid,nums);
        }
        else if(nums[mid]>nums[right])
        {
            return find(mid,right,nums);
        }
        else
        {
            return nums[left];
        }
    }
};

栈

堆

贪心算法

嘶……

大部分贪心都被我用dp过去了……

不过这道倒是dp没想出来:

45. 跳跃游戏 II - 力扣（LeetCode）

动态规划

感觉没有想象中的那么恐怖，其实就是要找到一条可以表示所有情况的通式。

接着找到他的初状态就可以了。

最好是要常备草稿纸！

多维动态规划

技巧