力扣之数据结构入门的刷题总结

目录

• • 一、数组总结
  • • 1、vector数组
    • 2、哈希表
  • 二、字符串总结
  • 三、链表总结
  • 四、二叉树总结
  • • 0、树的定义
    • 1、二叉树的前序、中序、后序遍历（递归）
    • 2、二叉树的层序遍历（BFS广度优先遍历）--用队列
    • 3、二叉树的中序遍历（DFS深度优先遍历）--用堆栈
    • 4、 二叉树中的递归思想（以最大深度中DFS递归方法为例）
    • 5、二叉搜索树的技巧
  • 五、算法总结
  • • 1、最大和的连续子数组（数组）
    • 2、两数之和（数组&树）
    • 3、一维动态规划（数组）
    • 4、快慢指针（链表）
    • 5、map如何找到字符在原字符串的位置？（字符串）
    • 6、别再两个for循环来遍历了，太慢了（vector）
  • 六、语法总结
  • • 1、 for循环
    • 2、STL里面的find *** 作
    • 3、switch~case
    • 4、STL中的push与emplace（可一直用emplace）
    • 5、NULL与nullptr
    • 6、递归时的变量定义问题（一般设定局部变量）
    • 7、力扣的递归小技巧（所给函数的变量不够）
  • 七、BUG总结

第一次完成力扣刷题，休息了一天后打算赶快的整理总结，以便能继续刷题。

力扣的数据结构主要是包括数组、字符串、链表、树。

以后希望每天上午都可以起来刷题（别赖床了都研一了啊！），掌握数据结构的同时能够提高算法水平-----本次记录希望之后复习可以用到！！

一、数组总结 1、vector数组

1、vector中的迭代器使用，迭代器本身是个指针，只要用* 去解引用就可以使用迭代器了。

2、像题目为函数返回类型为vector的，就在函数体内定义一个vector，然后往里push值，最后返回该vector即可也可以，直接返回{}中括号里面放元素即可。

3、一个数组的值直接赋给另一个数组可以用下面的 *** 作完成
v1.assign(v2.begin(), v2.end()); //v2赋给v1.
4、.erase()函数，在vector中是消除指定的范围的数，在哈希表中是消除该键。

5、vec1.size() 就是”二维数组”的行数vec1[0].size() 就是”二维数组”的列数

2、哈希表

1、哈希表unorder_set中的.find()函数可以遍历该集合看是否有重复的数据出现。

对于找重复值、**找两个数其和为目标值（数组和树都遇到此类题目）**等题目，可以常用哈希表来解决。

2、哈希表在使用时会涉及到指向为空，因此要学会用迭代器来判断(注意map中返回的查找函数的类型为迭代器)it == map.end（）//若为true，表示find（）函数没有找到目标值。


3、哈希映射用unorder_map，做数独的时候用了一个很猛的三维mapunordered_map>>mat33;//行，然后列，然后数组
其中mat33[i33][j33].find(board[i][j]);就可以访问到最里面的set啦！
4、哈希表在创建时，已经默认int类型的映射全为0了，可以直接使用++之类的 *** 作。

然后哈希表在使用时，不必先查找有没有再赋0或者再++，可以直接赋0或者++。

c++帮你直接完成定义并且赋值的 *** 作；同样，再- -时，也不用查找，可以直接就map【键】–；这样值直接就减了。

最后判断其是不是小于0的就ok了！！
5、unordered_set有个count函数，会返回0或者1来表示有无此数。

二、字符串总结

1、注意string类型中的删除erase是区间的删除！！

string.erase(pos,n)//其中pos为子字符串起始位置，n是要删除的字符串长度.
string.erase(firset,last)//删除迭代器 [first, last) 区间的所有字符（特别注意这里的区间是左闭右开的）

2、像这种字母的查找，其实都不用建立哈希表，因为字母可以直接对应数字，用ASCII码创建普通数组就行。

3、注意，stirng是由sort *** 作函数的！

三、链表总结

1、需要定义一个头节点（方便之后进行返回整个数组的 *** 作）和临时节点（作为交换的介质）。

那么如何定义一个新的头节点呢：（这里的new就是开辟一个地址啦！）

ListNode* newhead = new ListNode(0)

2、链表递进根本不需要用临时变量来搭建，直接通过head = head->next即可。

3、对于链表来说，首先要会判断空链表：用head！=nullptr
4、最后是链表的定义学习一下：就是值为值，下一个属性为指针

  struct ListNode {
      int val;
      ListNode *next;
      ListNode(int x) : val(x), next(NULL) {}};//构造函数

四、二叉树总结

没什么可说的，两个复杂的迭代必须会（分别为第二、第三点）背过就完了。

0、树的定义

  Definition for a binary tree node.
  struct TreeNode {
      int val;
      TreeNode *left;
      TreeNode *right;
      TreeNode() : val(0), left(nullptr), right(nullptr) {}
      TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
      TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}};

1、二叉树的前序、中序、后序遍历（递归）

这个十分简单。

就记得一个模板就可以。

前序：abc
中序：bac
后序：bca

void preorder(TreeNode *root, vector<int> &res) {
        if (root == nullptr) {
            return;
        }
        res.push_back(root->val);----a
        preorder(root->left, res);---b
        preorder(root->right, res);----c
    }

2、二叉树的层序遍历（BFS广度优先遍历）–用队列

思想：
1、先定义一个队列deque，查看头节点是否为空树，不为空放入队列
2、将root指向队列的头，然后取出来（一定记得pop出来，如果需要可以过后push进去再）
3、对root的值进行 *** 作（可有可无）
4、查看左右是否存在子节点，若有则放入队列中（先左后右）
5、查看队列是否还有元素，有则继续执行步骤2

      if(root==nullptr)return ans;
        deq.push_back(root);
        while(!deq.empty())
        {
            root = deq.front();
            deq.pop_front();
            ans.push_back(root->val);
            if(root->left!=nullptr)deq.push_back(root->left);
            if(root->right!=nullptr)deq.push_back(root->right);
        }

3、二叉树的中序遍历（DFS深度优先遍历）–用堆栈

思想：
1、先将所有左边的所有节点放进堆栈
2、然后取出来（一定记得pop出来，如果需要可以过后push进去再）
3、进行对节点 *** 作（可有可无）
4、将节点指向右节点即可。

（这样右边如果为空，会直接不判左往上跑！！不用担心重复进入的问题。

但如果后序啥的就要搞prev指着右边了，防止回去又指向右边了）

 		stack<TreeNode*>stk;
        while(!stk.empty()||root!= nullptr)
        {
            while(root!=nullptr)
            {
                stk.emplace(root);
                root= root->left;
            }
            root = stk.top();
            stk.pop();
            ans.push_back(root->val);//此处对值进行 *** 作
            root = root->right;
        }

4、 二叉树中的递归思想（以最大深度中DFS递归方法为例）

其实只要是有这两句话，理论就是会到达最下面的每个叶子节点：

if(root==nullptr)return 0;//这句不算哈
maxDepth(root->left);
maxDepth(root->right);

就是一个不断往下，然后从最下面开始往上面跑，比如，想知道最大深度就可以以下 *** 作：

    int maxDepth(TreeNode* root) {
        int RH,LH,max_H;
        if(root==nullptr)return 0;
        LH = maxDepth(root->left);
        RH = maxDepth(root->right);
        max_H = max(LH,RH)+1;//学会用c++中的max函数
        return max_H;
    }

递归的使用思想：1、确定返回值2、确定需要迭代的式子（只能靠多刷题来长进了）
递归return的条件思想：毕竟在二叉树使用递归，就差不多会把所有点跑一遍，这个时候如何把找到的结果遗传下去呢
1、如果是有一个为false的情况，就都为false，那么就要用的&&
例如hasPathSum(root->left,targetSum) && hasPathSum(root->right,targetSum)
2、如果是有一个为true的情况，就都为true，那么就要用的||
例如hasPathSum(root->left,targetSum) || hasPathSum(root->right,targetSum)

5、二叉搜索树的技巧

首先要知道其性质：
1、左子树所有节点的元素值均小于根的元素值；右子树所有节点的元素值均大于根的元素值。

2、一个二叉搜索树「中序遍历」得到的值构成的序列一定是升序的！
3、找搜索树两个节点最近公共祖先的两个办法：
1、分别记录从根节点到两个节点所经过的节点，第一个不同的节点就是公共祖先
2、直接比较root与两节点就行，都小才会往左边找祖先；都大才会往右边找祖先；一大一小，那么祖先就是现在的root。

五、算法总结 1、最大和的连续子数组（数组）

对于找最大和的连续子数组，复杂度最最小的，其实就是一个相邻的相加作比较而已

2、两数之和（数组&树）

对于两数之和此类题，无论是树的形式还是数组的形式，均可以用1、哈希表2、排序+for来解决。

3、一维动态规划（数组）

动态规划一般分为一维、二维、多维（使用状态压缩），其所应求的结果对应形式为 dp(i)dp(i)、dp(i)(j)dp(i)(j)、二进制dp(i)(j)二进制dp(i)(j)。

【对于一维的动态规划–做题步骤】
1、明确 dp(i)应该表示什么（二维情况：dp(i)(j)dp(i)(j)）；
2、根据 dp(i)和 dp(i-1)的关系得出状态转移方程；写出 dp(i)=…（此过程用for循环就可以搞出来了！）
3、确定初始条件，如 dp(0)。

4、快慢指针（链表）

本次用于判断是否为环形链表题中
快指针直接->next->next慢指针只有一下->next，所以看看是否相遇就知道是不是成环了！！
1、当链表中不存在环时，快指针将先于慢指针到达链表尾部。

2、当链表中存在环时，每一轮移动后，快慢指针的距离将减小，并相遇。

5、map如何找到字符在原字符串的位置？（字符串）

将字符与其出现的次数放入map后，map如何找到字符在原字符串的位置？
解：直接用序号i来for循环字符串，将字符串的字符放入哈希表查找其出现的次数，次数符合直接返回i就ok了！

6、别再两个for循环来遍历了，太慢了（vector）

找数组两个数加起来是否等于另一个数。

用了vector的双重for遍历，不如用双指针迭代器。

如果加起来小，左指针动；如果加起来打，右指针动！

六、语法总结 1、 for循环

学会用简单的for循环(int 勿忘定义)，下面的代码实现直接将vector（nums1）的值挨个拿出来作为num使用。

同样若for（char ch：s）就是循环string里面的每个字符了！！

for (int num : nums1) 
{
	++m[num];
}

2、STL里面的find *** 作

string和map都有成员函数find
但是map返回迭代器，而string返回整型变量，所以找不到返回-1。

如果vector也想用find，就得用泛型的find（其中L为vector）：

find( L.begin( ), L.end( ), 3 ); //查找3

3、switch~case

1、记得每个case要break
2、记得最后的else叫default

4、STL中的push与emplace（可一直用emplace）

除了push_back，要学会使用emplace_back。

在pushback创造的类型时，常常需要再重定义拷贝一下子，而emplaceback就像是加了auto的push，直接很轻松的额就插入进去了。

在STL中的push *** 作都可用emplace代替，其效率较高！

5、NULL与nullptr

NULL在c++中常常指代为0，想指代空指针还得靠nullpt

6、递归时的变量定义问题（一般设定局部变量）

int RH,LH,max_H;//学会集中起来，那样搞得乱乱的！
递归要考虑清楚变量的位置，一般常为局部变量，若全局变量，则会产生覆盖的现象！
因为递归过程中，每一次局部变量都会在返回时重新访问到的。

如果把它当成全局变量，那么每次递归由于RH\LH从0开始增，那么前面记忆的LH或者RH就会同时被覆盖掉从0开始增。

因此想【1，2，3，4，5】此类右边层数小的，就会因为先判断左边，而导致左边的大数被覆盖！！

7、力扣的递归小技巧（所给函数的变量不够）

当使用递归的时候，发现题目所给的函数变量不够使用的，这时候就可以自己再定义一个函数，里面放够所需要的变量数目，然后题目所给的函数 return 自己定义的函数就ok了!

七、BUG总结

1、sorted[p1+p2] = nums1[p1++];
上述写法有问题，因为你会搞不清先p1++还是先p1+p2，最好还是先找个int tem承接。

2、好几次犯此类错误了。

判断里面应该是==两个等号。

我老写成1个等号=。

服了！！
3、for（；xxx；）中的xxx和while（xxx）中的xxx一样，都是需要满足才能往下走的，别搞晕了！！！