力扣简单题刷题记录C++

本文章主要用于记录在LeetCode-简单难度题刷题过程中的心得与新学习算法的比较

C++ 中，STL容器主要分为两类，序列式容器、关联式容器。
序列式容器主要指的就是数组、链表、队列等只是顺序式的容器。
而关联式容器指的是容器在存储元素值的同时，还会为元素配备一个键值，此操作就能够在查找元素过程中，只需要已知键值，就能够找到元素值，不需要再遍历整个容器。即关联式容器存储元素，是以“键值对”的形式进行存储，即<key， value>的形式进行存储

vector用法题

vector用法
动态数组，一维建立方法：vector<数据类型> 数组名字，
二维建立方法：//使用vector的resize函数进行二维数组的定义（注意：此种方法适用于每一行的列数相等或不相等的二维数组，调整for循环内的resize函数的参数即可）
vector<vector> matrix(m); //创建一维数组matirx，这个数组里有m个元素，元素是int型vector。不能省略m。
使用方法：push_back添加元素，pop_back删除尾元素，size()返回元素个数，clear()删除所有元素
数组起始：数组名.begin()
数组末尾：数组名.end()
迭代器： vector::iterator it; 使用方法如下
for(it = a.begin(); it != a.end(); it++)
printf(“%d”, *it);
insert(it, x)向指定位置插入元素x,
erase(it) 即删除迭代器为it处的元素。
erase(first,last)即删除 [ first , last) 内的所有元素。例如：erase(vi.begin(), vi.end())；

118. 杨辉三角 I

脍炙人口的杨辉三角，在创建二维vector的时候要注意要加上长度

    vector<vector<int>> generate(int numRows) {vector<vector<int>> ans(numRows);for (int i = 0;i < numRows ; i++){ans[i].resize(i + 1);ans[i][0] = ans[i][i] = 1;for (int j = 1; j < i ; j++)ans[i][j] = ans[i - 1][j - 1] + ans[i - 1][j];}return ans;}

119.杨辉三角 II

这道题跟118题其实很像，不同之处就在于他只需要某一特定的行，题解的方法很巧妙…滚动数组，我直接暴力打表返回了

    vector<int> getRow(int rowIndex) {vector<vector<int>>ans(35);for (int i = 0;i <= rowIndex ; i++){ans[i].resize(i + 1);ans[i][0] = ans[i][i] = 1;for (int j = 1; j < i ; j++)ans[i][j] = ans[i - 1][j - 1] + ans[i - 1][j];}return ans[rowIndex];}

2500.删除每行中的最大值

题意：m*n的矩阵，每次操作会删去每行的当前最大值，然后在每一次删除的操作中，要求所有的最大值中的最大值的累加和。
思路：本来以为需要用优先队列维护，于是觉得这也太难了吧，这为啥是Easy啊，想半天没想到好解法，然后联想到之前有个题有个异或解法，或许这也是一条出路？然后暴死了，直接看题解！
题解：这题还不简单🐎，直接排序，排序完了遍历，每一列选个最大值相加

    int deleteGreatestValue(vector<vector<int>>& grid) {int m = grid.size(), n = grid[0].size();int ans = 0;for (int i = 0; i < m; i++)sort(grid[i].begin(), grid[i].end());for (int i = 0; i < n; i++){int maxx = grid[0][i];for (int j = 0; j < m ;j ++)maxx = max(maxx, grid[j][i]);ans += maxx;}return ans;}

好好好，是个好题

Map用法题

Map用法
哈希表，红黑树原理，关键字（key）-值对，key值唯一
初始化方法：map<int,int>mp;
添加对象：insert，例如：mp.insert({2,13});
删除元素：erase，例如：mp.erase(1);
修改元素：可以根据对应的key值修改value，mp[键值] = 新value
查找元素：可以通过key值直接查找，例如：cout<< mp[key值];
也可以通过value找键值，例如:cout<<find(value值) -> first;
其他用法
map_1.clear(); //清除所有元素
map_1.empty(); //如果为空返回1，负责返回0
map_1.size(); //返回容器的元素个数
map_1.max_size; //返回容器可以容纳的最大元素

//可以用过迭代器与first，second访问元素
map_1.begin()->first; //结果为容器的第一个元素的key值
map_1.begin()->second; //结果为容器的第一个元素的value值**

1.两数之和

题意：给定target和数组，需要在数组中找到两个数，这两个数之和为target
做法：
主要利用Map的红黑树特性，即关键值与数字相匹配的特性来进行判断
遍历整个nums数组，如果target - 当前值已经加入map中，则可以认为已经找到了答案，取消匹配过程，以Vecror的形式输出结果，否则将当前值加入map进行匹配

    vector<int> twoSum(vector<int>& nums, int target) {map<int,int>mp;vector<int>a;for (int i = 0; i < nums.size(); i++){if(mp.count(target - nums[i])) // find successfully{a.push_back(mp[target - nums[i]]);a.push_back(i);break;}mp[nums[i]] = i;}return a;}

136.只出现一次的数字

题目中给定的条件是给一个非空整数数组，这个数组中只有一个元素出现了一次，其他元素都出现了两次。本来想着用set映射一下，但是好像只能检查一遍是否存在，没存在无论如何也要加进去，好像不太合适，果断放弃，瞄了一眼题解说是要用HashMap，因为HashMap能够更改value，只要让value存储的值为出现次数即可。
这里用到了一个新学的概念：C++11中基于范围的for循环
基于范围的for语句

    int singleNumber(vector<int>& nums) {unordered_map<int,int>a;for (auto i:nums)a[i]++;for (auto i:nums)if(a[i] == 1)return i;return -1;}

题解里有一个更厉害的思路，就是用异或（初看惊为天人，因为每个数字都可能出现两次，所以用异或，不同为1，每个数字都会被抵消掉，真的震撼）^^^^^^^^^^^^打几个异或符号压压惊

205. 同构字符串

题意：给定两个字符串s and t，如果s中的字符可以按照某种映射关系替换得到t，则称为同构。每个字符都应该映射到另一个字符，不同字符不能映射到同一个字符上，相同字符只能映射到同一个字符上，字符可以映射到自己本身。
这个题目没想到好解法，看了题解（下次一定自己做
做法就是需要用到两个映射，一个用于s -> t的映射 一个用于t -> s 的映射，使用单个映射也可以解决问题，但判断条件会多写一些，我是看了官方题解，所以直接用的双映射。
双映射的判断条件是：首先遍历s -> t 的映射，建立映射关系，然后再遍历 t -> s 的映射，检查有没有s中的不同字母映射到了t 中的同一字母的情况。
单映射的判断逻辑是：遍历 s -> t 的映射，判断对于当前字符，当前存在的映射和已经存在的映射是否相等，不相等的话，返回false，如果当前映射关系还没有建立，但是已经有别的字符产生了t对应位置上字符的映射，也返回false，即使用map的特性检查是否有一对多或者多对一的情况

bool isIsomorphic(string s, string t) {int length = s.size();map<char,char>s_t,t_s;for (int i = 0; i < length ; i++)if(s_t.find(s[i]) != s_t.end() && s_t[s[i]] != t[i])return false;elses_t[s[i]] = t[i];for (int i = 0; i < length ; i++)if(t_s.find(t[i]) != t_s.end() && t_s[t[i]] != s[i])return false;elset_s[t[i]] = s[i];return true;}

Set 用法题

首先要区分：Set和Map存在本质性的区别，Set主要是一个集合，他只能允许一个数字存在一次，主要是用于集合类题目使用的，但Map主要用于hash
set与map用法的不同主要体现在：用set存储<key, value>时，key和value必须相等。因此，若是想要修改set容器中的元素做法是：先删除某个元素，再添加修改后的元素。

要注意的是，在判断set容器中是否含有元素时，判断条件应该是：是否等于迭代器的最末端。

771.宝石与石头

这道题就是非常经典的一个set用法题，因为我只需要判断前后两个字符串中字符的重合性，而不需要进行别的判断，因此没有必要使用map等容器，先将jwels中的元素加入set中，然后再遍历stones。

    int numJewelsInStones(string jewels, string stones) {set<char>a;int count = 0;for(int i = 0; i < jewels.size(); i++)a.insert(jewels[i]);for (int i = 0;i < stones.size(); i ++)if(a.find(stones[i]) != a.end())count++;return count;}

141.环形链表

看到这个题的第一想法就是用HashMap记录每个节点的遍历情况，如果在遍历过程中遇到了已经遍历过了的节点，则把标志变量flag 置为True，认为有环存在。但是实现过程中没想到不同节点可以有相同的val值，直接暴死。
偷偷去看了一眼题解，然后发现题解用的是Set，Set中存储的类型是ListNode类型，这样就可以对整个链表进行查重了。

    bool hasCycle(ListNode *head) {if(head == NULL)return false;unordered_set<ListNode*>a;while(head){if(a.find(head) == a.end())a.insert(head);elsereturn true;head = head -> next;}return false;}

题解的另一种做法：
快慢双指针法，即使用两个指针同时对整个链表进行遍历，如果快指针能追上慢指针，则说明存在回环。

202.快乐数

题意是将每个数字都进行变换，变换的规则就是新数 = 原数字的各个位上的数字的平方和，问最终能不能变为1，能变为1的数字叫做快乐数字，否则不快乐。

其实题目中也给了一定的暗示，就是这个数是不会一直变大的，但是一定会一直循环，我的理解是这样的，这样的欢乐数的变换规则下，数字是绝对不会越来越大的，因为一位数字，表示不了十，如果这样的话，0-9得到的数字，在不断的平方之下一定会越来越小，例如99 ->81 + 81 = 162，事实上，虽然数字变大了，但是由于新数字要继续进行欢乐数的变换规则，实际上是越来越小了，我将其称为“有缺”，因此0-9这种有缺的数字，一定不会变得无限大，但是有可能变成循环，这个是合理的。
将每个数字视为欢乐数变换过程中的一个节点，我们可以将题目换为：链表中是否有环？这种思路，也就是说，我们只要两次碰到相同的数字，就可以认为链表中有环，也就可以返回数字非欢乐数，因为会一直循环环中的节点。
set集合做法：

    int get_happy(int n){int sum = 0;while(n){sum += (n % 10) * (n % 10);n /= 10;}return sum;}bool isHappy(int n) {set<int>a;if(n == 1)return true;a.insert(n);while(1){n = get_happy(n);if(a.find(n) != a.end())return false;if(n == 1)return true;a.insert(n);}return false;}

快慢指针做法：

    int get_happy(int n){int sum = 0;while(n){sum += (n % 10) * (n % 10);n /= 10;}return sum;}bool isHappy(int n) {if(n == 1)return true;int fast = get_happy(get_happy(n));int slow = get_happy(n);while(fast != slow){fast = get_happy(get_happy(fast));slow = get_happy(slow);}if(fast == 1)return true;return false;}

字符串题

28. 找出字符串中第一个匹配项的下标

看到Easy标签，本来想一发strstr函数解决潇洒走人，然后发现离谱的是没有strstr函数。
KMP算法
BF算法就是最朴素的字符串匹配算法，在解题过程中，将源字符串与匹配字符串分别称为原串与模式串，如果使用BF算法，当原串与模式串某一位不同时，将会将模式串整体后移一位，重新进行匹配，但是若是引入前后缀相等的
KMP算法指的是三位大佬共同研发的字符串匹配算法，KMP算法的核心就是要利用模式字符串的前缀后缀相等，来减少匹配的冗余问题。
一个详解：
https://www.zhihu.com/question/21923021/answer/281346746
问题在于：如何处理模式串的next数组？next数组中实际上存储的就是模式串开头到当前字符为止最长相等的前后缀。
这里使用的方法是两个指针，i，j，分别维护的是右端点和左端点。
在KMP算法中存在多种写法，这里选用一种较为容易理解的一种，即在字符串开头插入一个空格，默认相等，这样的话 j可以从0开始

        for(int i = 2, j = 0; i <= m; i++){while(j and p[i] != p[j + 1]) j = next[j];if(p[i] == p[j + 1]) j++;next[i] = j;}

解析代码：在更新next数组的过程中，当左右端点的字符不相等时，即当前的前后缀字符串不相等，j向前回溯（因此是p[i]与p[j + 1]进行判断），回溯时才能j = next[j]
但是如果相等的话，j++ 即左端点也往后移动。

    int strStr(string haystack, string needle) {int n = haystack.size();int m = needle.size();haystack.insert(haystack.begin(), ' ');needle.insert(needle.begin(), ' ');vector<int>nxt(m + 1);for (int i = 2, j = 0; i <= m ; i++){while(j > 0 && needle[i] != needle[j + 1])j = nxt[j];if(needle[i] == needle[j + 1])j++;nxt[i] = j;}for(int i = 1, j = 0; i <= n; i++){while(j && haystack[i] != needle[j + 1])j = nxt[j];if(haystack[i] == needle[j + 1]) j++;if(j == m) return i - m;}return -1;}

9. 回文数

题中说给一个整数x，不能使用字符串函数，尽量使用整数反转。
做法是直接使用了暴力反转

    bool isPalindrome(int x) {if(x < 0)return false;string s = to_string(x);int wei = s.size();long int n = 0, xx = x, now = 0;while(wei){n += ((long int) (x / pow(10, wei - 1))) * pow(10, now);x %= (long int) (pow(10, wei - 1));wei--;now++;}if(n == xx)return true;return false;}

链表题

21. 合并两个有序链表

我的原本做法：
遍历两个链表的同时建立一个新链表，进行逐个比较，如果较小，则将较小的节点挂到新链表上，同时，较小的节点需要去向它指向的下一个有序节点。

    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {ListNode* list = new ListNode(-1);ListNode* bianli;ListNode* list3 = list1;ListNode* list4 = list2;ListNode* ans = list;bianli = list3;if(list1 == NULL)return list2;if(list2 == NULL)return list1;while(list1 != NULL && list2 != NULL){int a1 = list1 -> val;int a2 = list2 -> val;if(a1 <= a2){list -> next = list1;list1 = list1 -> next;}else{list -> next = list2;list2 = list2 -> next;}list = list -> next;}if(list1 == NULL)list -> next = list2;if(list2 == NULL)list -> next = list1;ans = ans -> next;return ans;}

该做法的缺陷就是链表遍历的时间太长，而且当其中有空链表时需要多重判断，而且需要创建多个链表节点。
另一种比较神奇的做法就是递归，递归在这道题的神奇之处的应用就在于：

每一次处理，本层都只需要处理应该做的两个节点，只需要针对这两个节点比大小，而这两个节点前面是什么，后面是什么，都不关心，如果list1的节点更小，那么list1后面挂的链就应该是当前的list1 -> next 与当前的list2 两条链合并而来的结果，因为最终结果的链应该要挂在节点值更小的那个结点上，但是我并不关心这条链是怎么来的，自行去下一层处理。

    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {if(list1 == NULL)return list2;if(list2 == NULL)return list1;if(list1 -> val < list2 -> val){list1 -> next = mergeTwoLists(list1 -> next, list2);return list1;}list2 -> next = mergeTwoLists(list1, list2 -> next);return list2;}

83.删除排序链表中的重复元素

记录这个题目的原因是遍历链表的写法还没有完全熟悉，而这个题目又是很能反应链表用法的一个题。
发现我经常写链表题写着写着就挂了，分析了一下发现是我很喜欢在链表遍历循环里套链表循环…其实大可不必，一次次遍历过去也是能够解决问题的，不需要急于求成。
本题需要解决的一个问题就是：如何在遍历过程中，将所有重复节点全部删除干净？
思路：当出现重复节点时，当前节点不动，重复节点一直往下next，直到所有的节点都被清除干净。
代码如下

    ListNode* deleteDuplicates(ListNode* head) {ListNode* bianli = head;if(bianli == NULL)return NULL;while(bianli -> next){if(bianli -> next -> val == bianli -> val)bianli -> next = bianli -> next -> next;elsebianli = bianli -> next;}return head;}

141.环形链表

题意：给你一个链表的头节点，判断链表中是否有环的存在。
首先想到的做法是用Set来进行hash判断，即用每个结点的val值来进行判断，然后就被狠狠暴死了，因为题目中并没有说过不能存在两个val值相同的节点，（然后开始抄题解
题解中点明了一种新思路就是建立ListNode*的集合，以此来判断是否重复，用该种集合就能够对整个链表进行查重。
新思路Get

    bool hasCycle(ListNode *head) {if(head == NULL)return false;unordered_set<ListNode*>a;while(head){if(a.find(head) == a.end())a.insert(head);elsereturn true;head = head -> next;}return false;}

然后又跑去抄题解，发现题解还有一种很巧妙的做法，即快慢双指针法，使用两个指针来遍历整个链表，一个指针一次移动两步，一个指针一次移动一步，如果整个链表中存在环的话，这个问题就会变成一个追及问题，就是慢指针迟早会被快指针追上，因为他们一直在绕着环跑跑跑，而且速度不同。
（力扣经常莫名其妙报错空指针，所以加了个判断）

    bool hasCycle(ListNode *head) {if(head == NULL)return false;ListNode* fast;ListNode* slow;fast = head -> next;slow = head;while(fast && slow){if(fast == slow)return true;if(fast -> next == NULL)break;fast = fast -> next -> next;slow = slow -> next;}return false;}

160.相交链表

题意：给两个链表，如果两个链表相交，返回第一个相交节点，否则返回NULL
第一思路：HashMap

    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {if(headA == NULL || headB == NULL)return NULL;set<ListNode*>a;while(headA){a.insert(headA);headA = headA -> next;}while(headB){if(a.find(headB) != a.end())return headB;headB = headB -> next;}return NULL;}

题解的妙思路：两个链表，用两个指针，将其演化成了追及运动，利用长短链表的长度差。
两个指针图解

    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {if(headA == NULL || headB == NULL)return NULL;ListNode* pA = headA;ListNode* pB = headB;while(pA != pB){if(pA == NULL)pA = headB;elsepA = pA -> next;if(pB == NULL)pB = headA;elsepB = pB -> next;}return pA;}

203.移除链表元素

刚开始的想法是在原指针head上进行操作，理解了一部分指针操作，例如：指针的移动并不会造成实际的内存地址上的变化，因此，我们进行更改的时候，往往是更改next值
刚开始的想法本来是想在原链表的基础上进行更改，但是因为对于删除和替换这些操作不熟练，卡了半天，然后决定用新链表头，自己建链表。要注意的是，在建立新链表时，头尾都要进行处理，因为尾节点是直接使用的原来的链表的节点，原来这个节点的next可能还有指向，因此需要手动添加一下。
然后就是头部，头部可能出现的情况就是元素一直相同。

    ListNode* removeElements(ListNode* head, int val) {ListNode* first = new ListNode(val - 1);ListNode* bianli = head;ListNode* second = first;if(bianli == nullptr)return NULL;while(bianli && bianli -> val == val)bianli = bianli -> next;while(bianli){if(bianli -> val != val){first -> next = bianli;first = first -> next;}bianli = bianli -> next;}first -> next = nullptr;second = second -> next;return second;}

然后学习了题解的解法：
在链表当中，一定要注意一个问题，就是如果当前链表的下一个节点需要删除，删除完以后不要直接进入下一个节点，而是要继续检查当前节点的下一节点，因为可能仍然不满足条件，还需要继续删除。

    ListNode* removeElements(ListNode* head, int val) {while(head && head -> val == val)head = head -> next;if(head == nullptr)return NULL;ListNode* pre = head;while(head -> next){if(head -> next -> val == val)head -> next = head -> next -> next;elsehead = head -> next;}return pre;}

206.反转链表

emmmm我觉得这题官方题解写的比我好得多，递归法暂时学不会，过两天找个集中的时间硬啃一下。
我的垃圾代码：

    ListNode* reverseList(ListNode* head) {if(head == NULL)return NULL;ListNode* prev = head;// prev = 1head = head -> next;// head = 2prev -> next = NULL;while(head){ListNode* temp = head -> next;//temp = 3;head -> next = prev;//head : 2 -> next = 1prev = head;//prev 从1 到 2head = temp;// head = 3}return prev;}

树题

100. 相同的树

我的思路：分别对两棵树跑一遍中序遍历和前序遍历，比较一下结果，如果结果不同，则说明两棵树不相同，如果结果相同，则说明不相同，
缺陷：中序遍历 + 前序遍历只能确定层序遍历，因此无法确定树的结构。
题解思路：
树形结构最合适的解法就是递归，不断遍历整个子树，然后分别比较。
当时做题时想了这个思路，但是觉得会非常麻烦，实际上比我的思路还更简单一些。

    bool isSameTree(TreeNode* p, TreeNode* q) {if(p == NULL && q == NULL)return true;if(p == NULL || q == NULL)return false;if(p -> val != q -> val)return false;return isSameTree(p -> left, q -> left) && isSameTree(p -> right, q -> right);}

另一个思路：BFS，用队列拓展树形结构，然后进行比较，整体思路与递归相近，但是实现方法主要依赖于队列结构。队列结构的优点就是空间换取时间，因此会加速时间。

    bool isSameTree(TreeNode* p, TreeNode* q) {queue<TreeNode*>Q;Q.push(p);Q.push(q);while(!Q.empty()){TreeNode* n1 = Q.front();Q.pop();TreeNode* n2 = Q.front();Q.pop();if(n1 == NULL && n2 == NULL)continue;if(n1 == NULL || n2 == NULL)return false;if(n1 -> val != n2 -> val)return false;Q.push(n1 -> left);Q.push(n2 -> left);Q.push(n1 -> right);Q.push(n2 -> right);}return true;}

101.对称二叉树

题意：要求找一个轴对称的二叉树，很容易想到的一种解法：从根节点开始分，将子树分别分为左右两颗子树，递归判断左子树的最右节点和右子树的最左节点是否相等，又因为要判断轴对称，乍一看题以为节点的值不相等也无所谓，遇到[1,2,3]这样的样例结构才发现要相等才可以，代码如下：

class Solution {
public:bool Is_sym(TreeNode* left, TreeNode* right){if(left == NULL && right == NULL)return true;if(left == NULL || right == NULL)return false;if(left -> val != right -> val)return false;return Is_sym(left -> right, right -> left) && Is_sym(left -> left, right -> right);}bool isSymmetric(TreeNode* root) {if(root == NULL)return true;return Is_sym(root -> left, root -> right);}
};

题解做法跟101题有些相似之处，仍然是使用队列来维护算法。思想还是一致的，不过是使用队列来进行迭代
代码：

class Solution {
public:bool Is_sym(TreeNode* left, TreeNode* right){queue<TreeNode*>Q;Q.push(left);Q.push(right);while(!Q.empty()){auto n1 = Q.front();Q.pop();auto n2 = Q.front();Q.pop();if(n1 == NULL && n2 == NULL)continue;if(n1 == NULL || n2 == NULL)return false;if(n1 -> val != n2 -> val)return false;Q.push(n1 -> right);Q.push(n2 -> left);Q.push(n1 -> left);Q.push(n2 -> right);}return true;}bool isSymmetric(TreeNode* root) {if(root == NULL)return true;return Is_sym(root -> left, root -> right);}
};

104. 二叉树的最大深度

思想：遍历整个二叉树，但是只需要计算深度，因此只需要返回深度，简单的递归题。

    int maxDepth(TreeNode* root) {if(root == NULL)return 0;return max(maxDepth(root -> left), maxDepth(root -> right) ) + 1;}

108.将有序数组转换为二叉搜索树

这个题目刚开始做是有些困难，因为并不能够理解什么是二叉搜索树，偷偷看了一下题解，发现二叉搜索树的定义指的是一颗尽可能平衡的树（根节点的左子树和右子树层数差距小于1，而且根节点的左子树的值都小于根节点的值，根节点的右子树的值都大于根节点的值），比较容易想到的算法还是递归建树，递归建树还是要注意区分左右子树。

class Solution {
public:TreeNode* BuildTree(vector<int>& nums, int left, int right){if(left > right)return NULL;int mid = left + (right - left) / 2;TreeNode* root = new TreeNode(-1);root -> val = nums[mid];root -> left = BuildTree(nums, left, mid - 1);root -> right = BuildTree(nums, mid + 1, right);return root;}TreeNode* sortedArrayToBST(vector<int>& nums) {return BuildTree(nums, 0, nums.size() - 1);}
};

110.平衡二叉树

经典题目没看全…
给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
因此，只需要在之前二叉树高度的基础上判断加一个递归，即将左右子树都纳入判断范围内即可。

    int MaxDep(TreeNode* root){if(root == NULL)return 1;return max(MaxDep(root -> left), MaxDep(root -> right)) + 1;}bool isBalanced(TreeNode* root) {if(root == NULL)return true;int LeftDep = MaxDep(root -> left);int RightDep = MaxDep(root -> right);if(abs(LeftDep - RightDep) > 1)return false;return isBalanced(root -> left) && isBalanced(root -> right);}

111. 二叉树的最小深度

大概题意：一颗普通二叉树，不一定是满的，要求计算根节点到叶子节点的最小深度。
思路：如果这颗二叉树是一颗所有节点都有叶子节点的二叉树，那么只需要在求深度时进行一个min函数计算，
第一个难点：从根节点开始，每个节点都只有一个子节点，跟理想情况相差甚远，此时拓展思路：
如果遇到子节点只有一个的子树，此时在求其子节点深度时，应该返回的是max（两个子树深度值），因为其中必有空子树，所以采用max做法。

    int minDepth(TreeNode* root) {if(root == NULL)return 0;if(root -> left != NULL && root -> right != NULL)  return min(minDepth(root -> left), minDepth(root -> right)) + 1;return max(minDepth(root -> left), minDepth(root -> right)) + 1;}

112.路径总和

尝试性地写了一下DFS，但是确实写得很烂，看完题解之后大呼优雅，上代码！
我写的垃圾：

class Solution {
public:int flag = 0;void PathSum(TreeNode* root, int targetSum, int now){if(root == NULL)return ;if(root ->left == NULL && root -> right == NULL){if(now + root -> val == targetSum)flag = 1;return ;}PathSum(root -> left, targetSum, now + root -> val);PathSum(root -> right, targetSum, now + root -> val);return ;}bool hasPathSum(TreeNode* root, int targetSum) {if(root == NULL )return false;PathSum(root, targetSum, 0);if(flag)return true;return false;}
};

题解的优雅代码：

class Solution {
public:bool hasPathSum(TreeNode *root, int sum) {if (root == nullptr) {return false;}if (root->left == nullptr && root->right == nullptr) {return sum == root->val;}return hasPathSum(root->left, sum - root->val) ||hasPathSum(root->right, sum - root->val);}
};

二叉树遍历全解，透彻！
二叉树遍历的递归解法不用多说，非常简单（但是如果只会递归解法不是很菜吗！学点迭代挺好

144.二叉树的前序遍历

    vector<int> preorderTraversal(TreeNode* root) {vector<int>ans;stack<TreeNode*>st;TreeNode* now;if(root == NULL)return ans;st.push(root);while(!st.empty()){now = st.top();st.pop();ans.push_back(now -> val);if(now -> right)st.push(now -> right);if(now -> left)st.push(now -> left);}return ans;}

145.二叉树的后序遍历

 // 现在想实现的效果是左右根// 可以学习前序遍历，前序遍历的顺序为根 左右 root right left// 现在只需要左右根 root left right  然后倒转，即可左右根？// 因为栈是先进后出的vector<int> postorderTraversal(TreeNode* root) {vector<int>ans;stack<TreeNode*>st;if(root == NULL)return ans;st.push(root);while(!st.empty()){TreeNode* now = st.top();st.pop();ans.push_back(now -> val);if(now -> left)st.push(now -> left);if(now -> right)st.push(now -> right);}reverse(ans.begin(), ans.end());return ans;}

257.二叉树的所有路径

题意是要返回一个二叉树的根节点到所有叶子节点的距离。
主要的难点在于如何传递参数a

    void BuildTreePaths(TreeNode* root, string s, vector<string>& path){if(root && root -> left == NULL && root -> right == NULL){if(s == "")s += to_string(root -> val);elses += "->" + to_string(root -> val);path.emplace_back(s);}else if (root){if(s == "")s += to_string(root -> val);elses += "->" + to_string(root -> val);BuildTreePaths(root -> left, s, path);BuildTreePaths(root -> right, s, path);}return ;     }vector<string> binaryTreePaths(TreeNode* root) {vector<string>a;BuildTreePaths(root, "", a);return a;}

贪心算法

121.买卖股票的最佳时机

第一思路肯定是暴力循环，先试试暴力循环能不能解决问题，直接TLE，暴死
然后就跑去看题解，看到题解也有暴力甚是费解…为什么题解能跑暴力而我不行捏，然后底下说题解的暴力也TLE，笑死
算法大致流程我认为是一种小贪心，计算直到当前这一天的最大利润，实时更新

    int maxProfit(vector<int>& prices) {int min_price = prices[0];int maxx = 0;int length = prices.size();for(int i = 1; i < length; i++){if(prices[i] - min_price > maxx)maxx = prices[i] - min_price;if(prices[i] < min_price)min_price = prices[i];}return maxx;}

巧用位运算

190.颠倒二进制位

题意就是有一个32位、以二进制表示的无符号型整数，要在其用二进制表示的时候颠倒一下，颠倒的效果即从1000 变为0001（以四位二进制举例）
普通的位运算做法很容易想到，就是第i位，有就移31-i位，

    uint32_t reverseBits(uint32_t n) {uint32_t m = 0;for (int i = 0;i <= 31 ; i++){if((1 << i) & n)m += 1 << (31 - i);}return m;}

题解里另一种比较有意思的做法是类归并排序的交换
我们要实现一个二进制数字的颠倒，本质上是要将数字完成移位操作，例如：
一个数字 1111 0000 1010 0101要进行移位
则会变成数字 1010 0101 0000 1111
我们可以将其理解为：首先是将高八位与低八位进行交换，然后再将交换完的数字里，每八位的高四位与低四位进行交换，然后再将交换完的数字里，每四位的高两位与低两位进行交换，最后再将两两交换。
归并排序主要利用的就是上述思想，但归并排序主要依赖递归进行实现，这里我们可以直接用位运算进行实现。

    uint32_t reverseBits(uint32_t n) {n = (n >> 16) | (n << 16);//这一步主要实现高低十六位的互换，n >> 16，高十六位去了低十六位，n << 16，低十六位去了高十六位n = (n & 0xff00ff00) >> 8 | (n & 0x00ff00ff) << 8;//这一步主要实现交换后数字的高低八位的互换，n & 0xff00ff00 即取每十六位中的前八位，然后与后八位互换位置n = (n & 0xf0f0f0f0) >> 4 | (n & 0x0f0f0f0f) << 4;//这一步主要实现交换后数字的高低四位的互换，n & 0xf0f0f0f0 即取每八位中的前四位，然后 与 后四位互换位置n = (n & 0xcccccccc) >> 2 | (n & 0x33333333) << 2;//这一步主要实现交换后数字的高低两位的互换，n & 0xcccccccc 即取每四位中的前两位，然后与后两位互换位置n = (n & 0xaaaaaaaa) >> 1 | (n & 0x55555555) << 1;return n;}

191.位1的个数

这题跟上题目的普通做法一致，循环找数字~

    int hammingWeight(uint32_t n) {int count = 0;for (int i = 0; i <= 31; i++)if(n & (1 << i))count ++;return count;}

有一个比较巧妙的二进制算法，即统计n & n -1的次数（每次看到这种巧妙算法都觉得自己是five）
n 和 n - 1的不同主要在于进位上，相当于强行减一，即让n最末尾的1被消去了，而n别的位都不变，让n & (n - 1)的次数，即是总次数。

    int hammingWeight(uint32_t n) {int count = 0;while(n){n = n & (n - 1);count ++;}return count;}