数据结构之入门篇

前言

算法模板，最科学的刷题方式，最快速的刷题路径，一个月从入门到 offer，你值得拥有 🐶~

算法模板顾名思义就是刷题的套路模板，掌握了刷题模板之后，刷题也变得好玩起来了~

此项目是根据github大佬项目改写的C++版本（大佬的是Go版本），从0开始学习，通过各种刷题文章、专栏、视频等总结了一套自己的刷题模板。

这个模板主要是介绍了一些通用的刷题模板，以及一些常见问题，如到底要刷多少题，按什么顺序来刷题，如何提高刷题效率等。

数据结构与算法

数据结构是一种数据的表现形式，如链表、二叉树、栈、队列等都是内存中一段数据表现的形式。算法是一种通用的解决问题的模板或者思路，大部分数据结构都有一套通用的算法模板，所以掌握这些通用的算法模板即可解决各种算法问题。

后面会分专题讲解各种数据结构、基本的算法模板、和一些高级算法模板，每一个专题都有一些经典练习题，完成所有练习的题后，你对数据结构和算法会有新的收获和体会。

先介绍两个算法题，试试感觉~

1、实现 strStr()

给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从 0 开始)。如果不存在，则返回 -1。

思路：核心点遍历给定字符串字符，判断以当前字符开头字符串是否等于目标字符串

class Solution {
 public:
  int strStr(string haystack, string needle) {
    if (needle.size() == 0) {
      return 0;
    }
    if (needle.size() > haystack.size()) {
      return -1;
    }
    int i, j;
    for (i = 0; i < haystack.size() - needle.size() + 1; i++) {
      for (j = 0; j < needle.size(); j++) {
        if (haystack[i + j] != needle[j]) {
          break;
        }
      }
      if (needle.size() == j) {
        return i;
      }
    }
    return -1;
  }
};

需要注意点

循环时，i 不需要到 len-1
如果找到目标字符串，len(needle)==j

（下一步，试试KMP算法）

2、子集

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

思路：这是一个典型的应用回溯法的题目，简单来说就是穷尽所有可能性，算法模板如下

result = []
def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return
    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择

通过不停的选择，撤销选择，来穷尽所有可能性，最后将满足条件的结果返回

答案代码

vector<vector<int>> res;

vector<vector<int>> subsets(vector<int>& nums) {
    // 记录走过的路径
    vector<int> track;
    backtrack(nums, 0, track);
    return res;
}

// 路径：记录在 track 中
// 选择列表：nums 中不存在于 track 的那些元素
// 结束条件：nums 中的元素全都在 track 中出现
void backtrack(vector<int>& nums, int start, vector<int>& track) {
    res.push_back(track);
    // 注意 i 从 start 开始递增
    for (int i = start; i < nums.size(); i++) {
        // 做选择
        track.push_back(nums[i]);
        // 回溯，进入下一层决策树
        backtrack(nums, i + 1, track);
        // 撤销选择
        track.pop_back();
    }
}

可以看见，对 res 的更新是一个前序遍历，也就是说，res 就是树上的所有节点：

序列为{1,2,3}

说明：后面会深入讲解几个典型的回溯算法问题，如果当前不太了解可以暂时先跳过（可参考这个）

简单法：

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        int size = nums.size();
        vector<vector<int>> obj;
        vector<int> outArray;
        for (int i:nums) {
            int len = obj.size();
            obj.push_back({i});
            for (int j = 0; j < len ; j++) {
                outArray = obj[j];
                outArray.push_back(i);
                obj.push_back(outArray);
            }
        }
        obj.push_back({});

        return obj;
    }
};