leetcode C++

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int length = sizeof(nums)/sizeof(nums[0]);
        for(int i = 0;i < length;++i)       
            for(int j = 0; j<length;++i)
                if (nums[i] + nums[j] == target)
                {
                    
                    return {nums[i],nums[j]};
                }
    
    }
};

后来改正的：python

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int length = nums.size();
        vector<int> ans;
        for(int i = 0;i < length;i++)       
            for(int j = i + 1; j<length;j++)
                if (nums[i] + nums[j] == target)
                {
                    ans.push_back(i);
                    ans.push_back(j);
                    return ans;
                }
    return ans;
    }
};

几点说明：
1.一个函数是必须有返回值的，若是只有if里加了return，当出现else的状况这个函数就没有了，因此要加else，要么最后加return也行；
2.返回一个列表时，能够定义一个容器来装
3.计算数组长度用size（）函数；
用暴力法就没有意义了，测试用例必定后面的过不了
一开始想对数组进行排序，这样能够极大程度的进行剪枝，可是排序以后丢失了原有的下标，若是返回的是元素不是下标的话这样就是可行的，可是下标不能用这种方法
哈希表的方法：ios

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {

        unordered_map<int,int> m;

        for(int i=0;i<nums.size();i++)
            m[nums[i]] = i;         //向map中添加元素
        
        for(int i=0;i<nums.size();i++)
        {
            if(m.find(target-nums[i]) != m.end() && m[target-nums[i]] != i)     //若是m中存在对应的键值，而且不为i，后面这个条件很重要，由于会有重复的元素
                return {i , m[target-nums[i]]};
        }
        return {};
    }
};

做者：zrita
连接：https://leetcode-cn.com/problems/two-sum/solution/c-san-chong-fang-fa-jian-dan-yi-dong-ji-bai-100-z-/
来源：力扣（LeetCode）
著做权归做者全部。商业转载请联系做者得到受权，非商业转载请注明出处。

2. 两数相加(链表)

能够说有思路，先补齐不齐的，而后再添加到新的链表中，最后考虑进位，可是代码过长既浪费时间又容易出错git

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* temp1 = l1;
        int len1 = 0;
        while(temp1)
        {
            temp1 = temp1->next;
            len1++;
        }
        ListNode* temp2 = l2;
        int len2 = 0;
        while(temp2)
        {
            temp2 = temp2->next;
            len2++;
        }
        temp1 =l1;
        while(temp1->next)
        {
            temp1 = temp1->next;
        }
        temp2=l2;
        while(temp2->next)
        {
            temp2=temp2->next;
        }
        while(len1 <len2)
        {
            ListNode* zero = new ListNode(0);
            temp1->next=zero;
            temp1 = zero;
            len1++; 
        }      
        while(len2<len1)
        {
            ListNode* zero = new ListNode(0);
            temp2->next = zero;
            temp2 = zero ;
            len2++;
        }
        ListNode* head = new ListNode(l1->val+l2->val);
        ListNode* temp = head;
        temp1=l1;
        temp1 = temp1->next;
        temp2=l2;
        temp2 = temp2->next;
        while(len1-1)
        {
            ListNode* cur = new ListNode(temp1->val+temp2->val);
            temp1=temp1->next;
            temp2=temp2->next;
            temp->next = cur;
            temp = cur;
            len1--;
        }
        temp = head;
        while(temp->next)
        {
            if(temp->val>=10)
            {
                temp->val -=10;
                temp->next->val +=1;
            }
            temp =temp->next;
        }
        if(temp->val>=10)
        {
            ListNode* zero = new ListNode(1);
            temp->val -=10;
            temp->next = zero; 
        }
        return head;
    }
};

相同的思路更简洁的代码
里面值得学习的地方是新建一个头节点，可是不许备放在终链表中，这样不用再把中间过渡的一些代码写出来
还有就是新建节点的时候直接new就能够的web

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        int len1=1;//记录l1的长度
        int len2=1;//记录l2的长度
        ListNode* p=l1;
        ListNode* q=l2;
        while(p->next!=NULL)//获取l1的长度
        {
            len1++;
            p=p->next;
        }
        while(q->next!=NULL)//获取l2的长度
        {
            len2++;
            q=q->next;
        }
        if(len1>len2)//l1较长，在l2末尾补零
        {
            for(int i=1;i<=len1-len2;i++)
            {
                q->next=new ListNode(0);
                q=q->next;
            }
        }
        else//l2较长，在l1末尾补零
        {
            for(int i=1;i<=len2-len1;i++)
            {
                p->next=new ListNode(0);
                p=p->next;
            }
        }
        p=l1;
        q=l2;
        bool count=false;//记录进位
        ListNode* l3=new ListNode(-1);//存放结果的链表
        ListNode* w=l3;//l3的移动指针
        int i=0;//记录相加结果
        while(p!=NULL&&q!=NULL)
        {
            i=count+p->val+q->val;
            w->next=new ListNode(i%10);
            count=i>=10?true:false;
            w=w->next;
            p=p->next;
            q=q->next;
        }
        if(count)//若最后还有进位
        {
            w->next=new ListNode(1);
            w=w->next;
        }
        return l3->next; 
    }
};

做者：chenlele
连接：https://leetcode-cn.com/problems/add-two-numbers/solution/liang-shu-xiang-jia-by-gpe3dbjds1/
来源：力扣（LeetCode）
著做权归做者全部。商业转载请联系做者得到受权，非商业转载请注明出处。

3. 无重复字符的最长子串（滑动窗口双指针）

用了带剪枝的暴力法，每次维护一个set，可是最后仍是超时了算法

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        //遍历确定不行，子串表示要连续
        //尝试双指针遍历加剪枝
        if(s.empty())return 0;
        if(s.size()==1)return 1;
        int len = s.size();
        int max = 1;
        for(int i= 0 ; i<len ; i++)
        {
            set<int> st;
            st.insert(s[i]);
            for(int j = i+1; j<len ;j++)
            {
                int k = st.size();
                st.insert(s[j]);
                if(st.size()==k) break;
                if(st.size()>max)max=st.size();
            }
        }
        return max;
    }
};

对于字符串的题，最容易出现的就是超时，而这是更好的办法每每是哈希表法docker

class Solution
{
public:
    int lengthOfLongestSubstring(string s)
    {
        //s[start,end) 前面包含 后面不包含
        int start(0), end(0), length(0), result(0);
        int sSize = int(s.size());
        unordered_map<char, int> hash;
        while (end < sSize)
        {
            char tmpChar = s[end];
            //仅当s[start,end) 中存在s[end]时更新start
            if (hash.find(tmpChar) != hash.end() && hash[tmpChar] >= start)
            {
                start = hash[tmpChar] + 1;
                length = end - start;
            }
            hash[tmpChar] = end;

            end++;
            length++;
            result = max(result, length);
        }
        return result;
    }
};

做者：pinku-2
连接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/solution/wu-zhong-fu-zi-fu-de-zui-chang-zi-chuan-cshi-xian-/
来源：力扣（LeetCode）
著做权归做者全部。商业转载请联系做者得到受权，非商业转载请注明出处。

双指针法可使用滑动窗口法，每次要找到是哪里多出来了，再从这个地方开始数组

class Solution
{
public:
    // 在左闭右开[left,right)的字符串s中，找字符target对应的下标位置，若未找到，则返回-1
    int getThePosOfSame(int left, int right, const string& s, char target) const
    {
        for (int i = left; i < right; i++)
        {
            if (s[i] == target)
            {
                return i;
            }
        }

        return -1;
    }

    int lengthOfLongestSubstring(string s)
    {
        const int len = s.length();

        int max_len = 0;
        int i = 0;
        int j = 0;

        while (j < len)
        {
            int pos = getThePosOfSame(i, j, s, s[j]);

            if (pos == -1)
            {
                j++;
            }
            else
            {
                max_len = (j - i) > max_len ? (j - i) : max_len;

                i = pos + 1;
            }
        }

        max_len = (j - i) > max_len ? (j - i) : max_len;

        return max_len;
    }
};

做者：hui-mao-zi-2
连接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/solution/hua-dong-chuang-kou-by-hui-mao-zi-2/
来源：力扣（LeetCode）
著做权归做者全部。商业转载请联系做者得到受权，非商业转载请注明出处。

本身的写的滑动窗口，要特别注意对数组的维护和每次更替时i和j的值缓存

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        //遍历确定不行，子串表示要连续
        //尝试双指针遍历加剪枝
        if(s.empty())return 0;
        if(s.size()==1)return 1;
        int len = s.size();
        int max = 1;
        int i = 0;
        int j = 1;
        vector<char> temp;
        temp.push_back(s[0]);
        while(i<len && j<len)
        {
            if( find(temp.begin(),temp.end(),s[j])==temp.end() )
            {
                temp.push_back(s[j]);
                j++;
                if(temp.size()>max)max =temp.size();
            }
            else
            {
                int k = find(temp.begin(),temp.end(),s[j])-temp.begin();
                i = i+k+1;
                j=i+1;
                temp.clear();
                temp.push_back(s[i]);
            }
            
        }
        return max;
        
    }
};

中间空缺的因为未保存丢失了，包括容器的知识，如二维数组，string、char等

6.Z 字形变换

拿到题目以后的思路：
1.每行须要创建一个容器存放值
2.可是因为行数是题目给定的，并非常量，因此只能先创建一个二维矩阵，行数就是题目的行数
3.设置在到达边界是当即返回，这个地方还想的不是很清楚
4.可想而知会很是复杂
官方解答：

class Solution {
public:
    string convert(string s, int numRows) {

        if (numRows == 1) return s;

        vector<string> rows(min(numRows, int(s.size())));
        int curRow = 0;
        bool goingDown = false;

        for (char c : s) {
            rows[curRow] += c;
            if (curRow == 0 || curRow == numRows - 1) goingDown = !goingDown;
            curRow += goingDown ? 1 : -1;
        }

        string ret;
        for (string row : rows) ret += row;
        return ret;
    }
};

做者：LeetCode
连接：https://leetcode-cn.com/problems/zigzag-conversion/solution/z-zi-xing-bian-huan-by-leetcode/
来源：力扣（LeetCode）
著做权归做者全部。商业转载请联系做者得到受权，非商业转载请注明出处。

首先因为是字符串型，没必要设置char型的二维矩阵而是直接设置一维而后进行拼接就好了，其次，对于到终点就返回的一个要求，就简单定义一个变量，从上到下时每次变量加1，从下到上每次变量键1，能够设置一个bool开关，做为加一和减一的标志，以前想的堆栈什么都太复杂了，虽然容器好用，可是能用一维的就不用二维，能用一两个指针或者变量的就不用堆栈

7.整数反转

class Solution {
public:
    int reverse(int x) {
        int p = 10;
        int n;
        long result = 0;
        if(x == INT_MIN)
        {
            return 0;
        }
        if (x >= 0)
        {
            
            while(x > 0)
            {
                n = x % p;
                x = x / p;
                result = result*10 + n;
            }
            if(result > INT_MAX)
            {
                return 0;
            }
            return result;

        }
        else
        {
            int y = -x;
            while(y > 0)
            {
                n = y % p;
                y = y / p;
                result = result*10 + n;
            }
            if(result > INT_MAX)
            {
                return 0;
            }
            return -result;
        }
    }
};

几点说明：
1.INT_MIN ,INT_MAX第一次见
INT_MAX = 2^31-1
INT_MIN= -2^31
另外为了防止result直接溢出了先试用long类型（8字节）进行定义！
2.反转后不用放到容器里而是分离的时候能够直接构成反转数；
3.遇到正反两种状况时不须要分两大类，而是在开头转换就能够，使用一次递归，以下所示

class Solution
{
public:
    int reverse(int x)
    {
        long result(0); //利用long避免溢出
        if (x == INT_MIN)
        {
            return 0;
        }
        if (x < 0)
        {
            return -reverse(-x);//当x小于0，再次调用该函数解出x大于0的状况，结果加负号返回
        }

        int digit(0);
        while (x > 0)
        {
            digit = x % 10;
            x /= 10;
            result = result * 10 + digit;//这里能够直接返回
        }

        if (result > INT_MAX)
        {
            return 0;
        }
        return int(result);
    }
};

做者：pinku-2
连接：https://leetcode-cn.com/problems/reverse-integer/solution/zheng-shu-fan-zhuan-cshi-xian-liang-chong-jie-fa-z/
来源：力扣（LeetCode）
著做权归做者全部。商业转载请联系做者得到受权，非商业转载请注明出处。

class Solution {
public:
    int reverse(int x) {
        int rev = 0;
        while (x != 0) {
            int pop = x % 10;
            x /= 10;
            if (rev > INT_MAX/10 || (rev == INT_MAX / 10 && pop > 7)) return 0;
            if (rev < INT_MIN/10 || (rev == INT_MIN / 10 && pop < -8)) return 0;
            rev = rev * 10 + pop;
        }
        return rev;
    }
};

做者：LeetCode
连接：https://leetcode-cn.com/problems/reverse-integer/solution/zheng-shu-fan-zhuan-by-leetcode/
来源：力扣（LeetCode）
著做权归做者全部。商业转载请联系做者得到受权，非商业转载请注明出处。

9.回文数

这里使用了整数反转的思路，直接比对反转后是否相等就知道是不是回文数；
另外，为了防止超范围，result可使用类型long；
另外，数字和字符串转换不如算法方式好；

class Solution {
public:
    bool isPalindrome(int x) {
        if(x < 0){return false;}
        else
        {
            long result = 0;
            int y = x;
            int n = 0;
            while(x > 0)
            {
                n = x % 10;
                x = x / 10;
                result = result*10 + n;
            }
            if (result == y){return true;}
            else{return false;}
        }
    }
};

看到一种新写法

return (x==n) ? true : false;

可代替原来的代码为

return (result == y) ? true: false;

13.罗马数字转换

这则代码在map的使用上花费了较多时间，s是string字符串，s[0]能够去除字符串的第一个元素，可是必定不能使用luoma[“s[0]”]去提取值，由于s[0]这里不会进行编译的！因此要提取的话要找自己就是string类型的，而s.substr(n,m)能够作到这一点，n表明起始位置，m表明提取的个数，将其放入luoma[]中能够提取到想要的value。

#include <map>
#include <iostream>
using namespace std;
class Solution {
public:
    int romanToInt(string s) {
        int length = s.size();
        std::map<string,int> luoma;
        luoma.insert(pair<string,int>("I",1));
        luoma.insert(pair<string,int>("V",5));
        luoma.insert(pair<string,int>("X",10));
        luoma.insert(pair<string,int>("L",50));
        luoma.insert(pair<string,int>("C",100));
        luoma.insert(pair<string,int>("D",500));
        luoma.insert(pair<string,int>("M",1000));
        long result = 0;
        if (length >1)
        {
            for (int i = 0;i < length-1; i++ )
            {
                if(luoma[s.substr(i,1)] >= luoma[s.substr(i+1,1)])
                {
                    result = result + luoma[s.substr(i,1)];   
                }
                else 
                {
                    result = result - luoma[s.substr(i,1)];
                }
            }
            result = result + luoma[s.substr(length-1,1)];           
        }
        else{
           result = luoma[s.substr(0)]; 
        }

        
        return result;

    }
};

官方的

class Solution {
public:
    int romanToInt(string s) {
        unordered_map<string, int> m = {{"I", 1}, {"IV", 3}, {"IX", 8}, {"V", 5}, {"X", 10}, {"XL", 30}, {"XC", 80}, {"L", 50}, {"C", 100}, {"CD", 300}, {"CM", 800}, {"D", 500}, {"M", 1000}};
        int r = m[s.substr(0, 1)];
        for(int i=1; i<s.size(); ++i){
            string two = s.substr(i-1, 2);
            string one = s.substr(i, 1);
            r += m[two] ? m[two] : m[one];
        }
        return r;
    }
};

做者：QQqun902025048
连接：https://leetcode-cn.com/problems/roman-to-integer/solution/2-xing-python-on-by-knifezhu/
来源：力扣（LeetCode）
著做权归做者全部。商业转载请联系做者得到受权，非商业转载请注明出处。

map：

优势：

有序性，这是map结构最大的优势，其元素的有序性在不少应用中都会简化不少的操做
红黑树，内部实现一个红黑书使得map的不少操做在lgn的时间复杂度下就能够实现，所以效率很是的高
缺点：空间占用率高，由于map内部实现了红黑树，虽然提升了运行效率，可是由于每个节点都须要额外保存父节点、孩子节点和红/黑性质，使得每个节点都占用大量的空间

适用处：对于那些有顺序要求的问题，用map会更高效一些

unordered_map：

优势：由于内部实现了哈希表，所以其查找速度很是的快
缺点：哈希表的创建比较耗费时间
适用处：对于查找问题，unordered_map会更加高效一些，所以遇到查找问题，常会考虑一下用unordered_map

14.最长公共前缀

整体来讲思路难度不大，
1.要注意函数可能没有返回值的状况
2.要求一个公共最小长度，不必定非要建出容器而后求最小值，能够直接在求每一个值的时候顺带求出最小值
3.substr函数仍是很好用的，主要是还能指定输出的个数

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        int a = strs.size();


        if (a == 0)
        {
            return "";
        }
        else if (a == 1)
        {
            return strs[0];
        }
        else
        {
            int aamin = strs[0].size();
            for(int i = 1; i <a ; i++)
            {
                if(aamin > strs[i].size()){aamin = strs[i].size();}
            }            
            
            for (int i = 0; i < aamin; i++ )
            {
                for (int j = 0; j< a; j++)
                {
                    if (strs[0].substr(i,1) != strs[j].substr(i,1))
                    {
                        return strs[0].substr(0,i);
                    }
                }
            
            }
            return strs[0].substr(0,aamin);
            
        }
    }
};

基本同样，不过其并无使用substr函数

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if(strs.size()==0)
            return "";
        string str="";
        int min_lenth=strs[0].size();
        for(int i=1;i<strs.size();i++)
        {
            if(min_lenth>=strs[i].size())
                min_lenth=strs[i].size();
        }
        for(int k=0;k<min_lenth;k++)    
        {
            char s=strs[0][k];
            for(int j=1;j<strs.size();j++)
            {
                if(s!=strs[j][k])
                    return str;
            }
            str+=s;
        }
        return str;
    }
};

15. 三数之和(双指针)

直接暴力法，必定是不可取的

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        //没有好的办法，双指针不行，矩阵不行，贪心不行
        //二维数组
        
        int len = nums.size();
        //vector<vector<int> > myvec(len, vector<int>(nums,0));
        set<multiset<int> > res;
        for (int i = 0; i<len; i++)
        {
            for(int j= i+1; j<len ; j++)
            {
                for (int c=j+1 ;c<len; c++)
                {
                    //if (c==i || c==j){continue;}
                    if ((nums[i]+nums[j]+nums[c])==0)
                    {
                        multiset<int> x;
                        x.insert(nums[i]);
                        x.insert(nums[j]);
                        x.insert(nums[c]);
                        res.insert(x);
                    }
                }
            }
        }
        vector<vector<int> > re;
        for(auto i:res)
        {
            vector<int> x;
            for(auto j:i)
            {
                x.push_back(j);
            }
            re.push_back(x);
        }
        //vector<vector<int> > re = res;
        return re;
        
        
    }
};

再暴力法上加了剪枝，可是仍是超时了，说明这种方法是不行的

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        int len = nums.size();
        if(len<3)return {};
        sort(nums.begin(),nums.end());
        int i = 0 ;
        int j = 1 ;
        int l = 2;
        
        set<vector<int>> res;
        for(int i = 0 ; i<len ;i++)
        {
            if(nums[i]>0) break;//直接中止循环
            if(nums[i]+nums[len-2]+nums[len-1]<0)continue;//直接跳过这次循环
            for(int j = i+1;j<len ;j++)
            {
                if(nums[i]+nums[j]+nums[len-1]<0)continue;//跳过这次循环
                for(int k = j+1 ; k<len ;k++)
                {
                    if(nums[i]+nums[j]+nums[k]==0)
                    {
                        vector<int> temp = {nums[i],nums[j],nums[k]};
                        res.insert(temp);
                        //为了防止又相同值这里不能中止
                    }
                    if(nums[i]+nums[j]+nums[k]>0) break;//后面的k也都不行了
                }
            }

        }
        vector<vector<int>> r(res.begin(),res.end());
        return r;

        
    }
};

正确的作法，双指针法，一个在前一个在后，寻找0-nums[i]的两个值，特别适用于已经排序的数组，要记住排序以后数组常用一前一后的双指针法

class Solution
{
public:
    vector<vector<int>> threeSum(vector<int> &nums)
    {
        vector<vector<int>> result;
        int vecSize = int(nums.size());
        if (vecSize <= 2)
        {
            return result;
        }
        int possibleSize = vecSize - 2;
        sort(nums.begin(), nums.end());

        for (int index = 0; index < possibleSize; index++)
        {
            int intNow = nums[index];
            if(intNow > 0){
                break;
            }
            int negativeNow = 0 - intNow;
            int lo = index + 1;
            int hi = vecSize - 1;
            while (lo < hi)
            {
                int intLo = nums[lo];
                int intHi = nums[hi];

                if (intLo + intHi == negativeNow)
                {
                    vector<int> tmpVec{intNow, intLo, intHi};
                    result.push_back(tmpVec);
                    //去重
                    while (lo < hi && nums[lo] == intLo)
                    {
                        lo++;
                    }
                    while (lo < hi && nums[hi] == intHi)
                    {
                        hi--;
                    }
                }
                else if (intLo + intHi < negativeNow)
                {
                    lo++;
                }
                else if (intLo + intHi > negativeNow)
                {
                    hi--;
                }
            }
            //去重
            while (index + 1 < possibleSize && nums[index] == nums[index + 1])
            {
                index++;
            }
        }

        return result;
    }
};

做者：pinku-2
连接：https://leetcode-cn.com/problems/3sum/solution/san-shu-zhi-he-cshi-xian-shuang-zhi-zhen-fa-tu-shi/
来源：力扣（LeetCode）
著做权归做者全部。商业转载请联系做者得到受权，非商业转载请注明出处。

本身写的，勉强不超时，考虑多是去重那里费了比较多功夫

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        int len = nums.size();
        int k=0, i=1,j = len-1;
        sort(nums.begin(),nums.end());
        vector<vector<int>> res;
        while(k<=len-3)
        {
            if(nums[k]+nums[k+1]+nums[k+2]>0)break;
            if(nums[k]+nums[k+1]+nums[k+2]==0)
            {       vector<int> temp={nums[k],nums[k+1],nums[k+2]};
                    res.push_back(temp);break;};
            //if(nums[k]+nums[i]+nums[j]>0){k++;i=k+1;j=len-1;continue;}
            if(nums[k]+nums[j-1]+nums[j]<0){k++;i=k+1;j=len-1;continue;}
            while(i<j)
            {
                if(nums[i]+nums[j]==-nums[k])
                {
                    vector<int> temp={nums[k],nums[i],nums[j]};
                    res.push_back(temp);
                    i++;j--;
                }
                else if(nums[i]+nums[j]>-nums[k])
                {
                    j--;
                }
                else
                {
                    i++;
                }
            }
            k++;
            i=k+1;
            j=len-1;
        }
        set<vector<int>> r(res.begin(),res.end());
        res.assign(r.begin(),r.end());
        return res;
    }
};

16. 最接近的三数之和

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        int len = nums.size();
        int k=0,i=1,j=len-1;
        sort(nums.begin(),nums.end());
        int res = 1e6;
        if(nums[0]+nums[1]+nums[2]>target) return nums[0]+nums[1]+nums[2];
        if(nums[len-3]+nums[len-2]+nums[len-1]<target) return nums[len-3]+nums[len-2]+nums[len-1];
        while(k<=len-3)
        {
            if(nums[k]+nums[k+1]+nums[k+2]>target)
            return abs(res-target)<abs(nums[k]+nums[k+1]+nums[k+2]-target)?res:nums[k]+nums[k+1]+nums[k+2];
            while(i<j)
            {
                if(nums[k]+nums[i]+nums[j]==target)return target;
                else if(nums[k]+nums[i]+nums[j]>target)
                {
                    res = abs(res-target)<abs(nums[k]+nums[i]+nums[j]-target)?res:nums[k]+nums[i]+nums[j];j--;
                }
                else
                {
                    res =abs(res-target)<abs(nums[k]+nums[i]+nums[j]-target)?res:nums[k]+nums[i]+nums[j];i++;
                }
            }
            k++;
            i=k+1;
            j=len-1;
        }
        return res;
    }
};

17. 电话号码的字母组合

怎么排列出全部的状况，时最难的地方

	string str;
	str = str + 'm' + "m" + to_string(m)+char(m) + char(m+'0') ;

字符串拼接，加号也行，单双引号都能拼，整型用to_string
这题能使用递归，可是很差理解，这个队列的思想很是实用，很是像二叉树层序遍历的过程！先遍历第一曾（单个的），每个生成一个组合再放到队列末尾，而这个弹出，像极了把子节点放入队列后面，而后将此节点弹出的过程
队列是有效的一种遍历手段

class Solution {
public:
	vector<string> letterCombinations(string digits) {
		vector<string> res;//用于输出向量
		map<char, string> m = { {'2',"abc" },{'3',"def"},{'4',"ghi"},{'5',"jkl"},{'6',"mno"},{'7',"pqrs"},{'8',"tuv"},{'9',"wxyz"} };//映射map哈希表
		int size = digits.size();//输入字符串产长度
		queue<string> que;//新建队列
		
		//先将第一个元素对应的码表入队
		for (int j = 0; j < m[digits[0]].size(); j++)
		{
			string str;
			str.push_back(m[digits[0]][j]);//char转string
			que.push(str);//string入队，分别将'a','b','c'入队列
		}
		string s;//用于存储队头元素
		for (int i = 1; i < size; i++)//对剩下的第二个开始进行遍历，每一都会组成新的字符串放入队列，而后将此弹出
		{
			int length = que.size();//当前队列长度，这时的队列存放的是上一层全部的字符串，以前的都弹掉了，对于里面的每一个，都须要新的组合进入队尾，再弹出这个
			while (length--)//
			{
				for (int j = 0; j < m[digits[i]].size(); j++)
				{
					s = que.front();
					s = s + m[digits[i]][j];//队头元素加上新元素
					que.push(s);//入队
				}
				que.pop();//队头出队
			}
		}
		while (!que.empty())
		{
			res.push_back(que.front());//队头元素存储至res
			que.pop();//队头出队
		}
		return res;//返回
	}
};

做者：su-ge
连接：https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/solution/c-dui-lie-jian-dan-shi-xian-yi-dong-by-su-ge/
来源：力扣（LeetCode）
著做权归做者全部。商业转载请联系做者得到受权，非商业转载请注明出处。

套用递归模板能够写出递归

class Solution {
private:
vector<string> res;
string path;
int len;
public:
    void dfs(unordered_map<char,string> mymap, int pos, string digits)
    {
        if(pos == len)
        {
            res.push_back(path);
        }
        for(auto i:mymap[digits[pos]])
        {
            path = path+ i;
            dfs(mymap,pos+1,digits);
            path.pop_back();
        }
    }

    vector<string> letterCombinations(string digits) {
        if(digits.empty())return res;
        len = digits.size();
        unordered_map<char,string> mymap{{'2',"abc"},{'3',"def"},{'4',"ghi"},{'5',"jkl"},{'6',"mno"},{'7',"pqrs"},{'8',"tuv"},{'9',"wxyz"}};
        dfs(mymap,0,digits);
        return res;
    }
};

18. 四数之和

借鉴以前三数之和的双指针法，能作可是计算量大

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        sort(nums.begin(),nums.end());
        int len = nums.size();
        int i = 0, j = 1, k1= 2,k2= len-1;
        set<vector<int> > res;
        while(i< len-3  )
        {
            while(j<len-2)
            {
                while( k1<k2)
                {
                    int temp = nums[i]+nums[j]+nums[k1]+nums[k2];
                    if (temp == target)
                    {
                        vector<int> vec ={nums[i], nums[j], nums[k1],nums[k2]};
                        res.insert(vec); 
                        k1++; 
                    }
                    else if (temp > target){k2--;}
                    else {k1++;}
                }
                j++;
                k1 = j+1;
                k2 = len-1;
            }
            i++;
            j=i+1;
            k1=j+1;
            k2=len-1;
        }
        vector<vector<int> > re;
        for (auto i :res)
        {
            re.push_back(i);
        }
        return re;
    }
};

这样的方法可行，在这个方法上能够有更优化的办法，以前有特殊状况0，因此即判断第一个指针值的大小和0的关系就好了，可是当target不为0时不能这样简单的判断，由于0如下的值越加越小，0以上的值越加越大，因此能够换个稍微复杂的验证方式，假设头节点是p，若是p和右边的三个的和都大于target，就不必了，能够中止循环，由于还会大于target，若是p和最后三位的加和还小于target的话，那么就说明这个p不可能组成，直接计算p+1的状况

指针依次是 p,k,i,j，若是 nums[p] + 3 * nums[p + 1] > target，由于 nums 按升序排列，因此以后的数确定都大于 target ，直接 break；

若是 nums[p] + 3 * nums[-1] < target，那么当前的 nums[p] 加其他三个数必定小于 target，故 p 直接下一位便可，continue；

做者：z1m
连接：https://leetcode-cn.com/problems/4sum/solution/shuang-zhi-zhen-gao-su-jie-fa-by-ml-zimingmeng/
来源：力扣（LeetCode）
著做权归做者全部。商业转载请联系做者得到受权，非商业转载请注明出处。

第二次写的加入剪枝的操做

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        int len = nums.size();
        int k=0,l=1,i=2,j=len-1;
        sort(nums.begin(),nums.end());
        set<vector<int>> res;
        while(k<=len-4)
        {
            if(nums[k]+nums[k+1]+nums[k+2]+nums[k+3]>target)break;
            if(nums[k]+nums[j-2]+nums[j-1]+nums[j]<target){k++;l=k+1;i=k+2;j=len-1;continue;}
            while(l<=len-3)
            {
                if(nums[k]+nums[l]+nums[l+1]+nums[l+2]>target)break;
                if(nums[k]+nums[l]+nums[j-1]+nums[j]<target){l++;i=l+1;j=len-1;continue;}
                while(i<j)
                {
                    if(nums[k]+nums[l]+nums[i]+nums[j]==target)
                    {
                        vector<int> temp={nums[k],nums[l],nums[i],nums[j]};
                        res.insert(temp);i++;j--;
                    }
                    else if(nums[k]+nums[l]+nums[i]+nums[j]>target)
                    {
                        j--;
                    }
                    else
                    {
                        i++;
                    }
                }
                l++;i=l+1;j=len-1;
            }
            k++;
            l=k+1;
            i=l+1;
            j=len-1;
        }
        vector<vector<int>> r(res.begin(),res.end());
        return r;
    }
};

19. 删除链表的倒数第N个节点

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        
        int len=0;
        ListNode* temp = head;
        while(temp!=nullptr)
        {
            len++;
            temp = temp->next;
        }
        if(len==1){return NULL;}
        else if (len==n){head = head->next;}
        else 
        {
            temp =head;
            for(int i= 0;i<len-n-1;i++)
            {
                temp=temp->next;
            }
            
            temp ->next = temp ->next->next;
        }
        return head;
    }
};

思想是找到该节点的前一个节点，可是要注意特殊状况，即删除的是第一个节点的状况，这种状况下会没有前一个节点

双指针，当快的前进n时，慢的开始；当快的到结尾时，慢的正好到能够删除的那个节点前一个，对于一维方向上的问题，双指针能够解决绝大数

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {   
        ListNode* dummy = new ListNode(NULL);
        dummy->next = head;  //添加头节点，便于操做
        ListNode* slow=dummy,* fast=dummy;
        int distance=0;
        while(fast->next){
            if(distance<n){
                fast=fast->next;
                distance++;
            }else{
                fast=fast->next;
                slow=slow->next;
            }
        }
        slow->next=slow->next->next;
        return dummy->next;
    }
};

做者：zgdgod
连接：https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/solution/c-by-zgdgod-4/
来源：力扣（LeetCode）
著做权归做者全部。商业转载请联系做者得到受权，非商业转载请注明出处。

20.有效的括号（堆栈的运用）

有效运用了break和continue：一个是当即退出当前循环，一个是结束本次循环；

class Solution {
public:
    bool isValid(string s) {
        int length = s.size();
        if (length % 2 == 1)
        {
            return false;
        }
        else
        {
            map <string ,int> fuhao = {{"(",1}, {")",-1}, {"[",2}, {"]",-2}, {"{",3}, {"}",-3}};
            while((s.size()) > 0)
            {
                
                length = s.size();
                for(int i = 0; i < s.size()-1; i++)
                {
                    if ( fuhao[s.substr(i,1)] == - fuhao[s.substr(i+1,1)])
                    {
                        s.erase(i,2);
                        break;
                    }
                }
                if(length == 0)
                {
                    return true;
                }
                else if (length == s.size())
                {           
                    return false;
                }
                else
                {
                    continue;
                }

            }
            return (s.size() == 0) ? (true) : (false);
        }
    }
    

};

思路：对于字符串s
若下一个字符是左括号：则任务数量task+1，且将须要匹配的右括号数字添加至key容器；
若下一个字符是右括号：
一、如果key容器中最后一个数字对应的右括号，则任务数量task-1，移除容器最后一项；
二、若不是key容器中最后一个数字对应的右括号，则直接结束，返回False。

知识点：
1.for(auto i : s)遍历s中的全部字符、元素，甚至可使用自动类型推断，一个冒号就解决了，实用性很大！
2.vector.empty()与
if (vector.size() == 0 ){return true}
else {return false} 的效果更简洁，若是要反着来能够在前面加一个！
3.对于s中的每个符号，若是是左半边，就把这个推动容器；若是是右半边，此时若容器为空则说明以前没有左半边入栈，则false，若是容器不为空继续，把容器最后一个左半括号提取出来，若是此右半边和这个括号不匹配，则false，若是匹配则弹出此左半括号，继续下去，所有走完后，直接用空就表明是否所有匹配，一语双关！

class Solution {
public:
    bool isValid(string s) {
        if(s.size() % 2) return false;
        vector<char> vecStack;//字符型的容器
        char c;
        //对于s中的每个符号，若是是左半边，就把这个推动容器；若是是右半边，此时若容器为空则说明以前没有左半边入栈，则false，若是容器不为空继续，把容器最后一个左半括号提取出来，若是此右半边和这个括号不匹配，则false，若是匹配则弹出此左半括号，继续下去，所有走完后，直接用空就表明是否所有匹配，一语双关！
        for(auto i : s) { 
            if(i == '}' || i == ')' || i== ']') {
                if (!vecStack.empty()) c = vecStack[vecStack.size()-1];
                else return false;
                if(i == '}' && c != '{') return false;
                if(i == ')' && c != '(') return false;
                if(i == ']' && c != '[') return false;
                vecStack.pop_back();
            }
            else vecStack.push_back(i);
        }
        return vecStack.empty();
    }
};

做者：wallcwr
连接：https://leetcode-cn.com/problems/valid-parentheses/solution/jing-dian-jian-dan-de-zhan-wen-ti-by-wallcwr/
来源：力扣（LeetCode）
著做权归做者全部。商业转载请联系做者得到受权，非商业转载请注明出处。

本身又写了一遍，发现一个问题：必须是单引号才行，双引号就不行——单引号字符，双引号字符串

class Solution {
public:
    bool isValid(string s) {
        vector <char> kuohao;
        if (s.size() % 2 == 1) return false;
        for (auto str : s)
        {
            if ((str == '{') || (str == '[') || (str == '('))
            {
                kuohao.push_back(str);
            }
            else
            {
                if(kuohao.size() == 0) return false;
                if (str == '}' && kuohao[kuohao.size()-1] == '{') 
                {
                    kuohao.pop_back();
                    continue;
                }
                else if (str == ']' && kuohao[kuohao.size()-1] == '[') 
                {
                    kuohao.pop_back();
                    continue;
                }
                else if (str == ')' && kuohao[kuohao.size()-1] == '(' )
                {
                    kuohao.pop_back();
                    continue;
                }                                
                else
                {
                    return false;
                }
            }
        }
        return kuohao.empty();
    }
};

在C++中单引号表示字符，双引号表示字符串。

例如：在定义一个数组的时候string a [5]={“nihao”,“henhao”,“good”,“en”,“h”};

定义的是一个字符串数组，这是字符串元素要用双引号。

char b[5]={‘a’,‘b’,‘c’,‘d’,‘e’};

定义的是一个字符数组，元素要用单引号。

要注意元素的输出不一样：

int a=10;

cout<<“a”;输出为字符a;这就是上次“s[0]”中不能再编译s[0]的缘由，可是若是是单引号没准能编译

cout<<a;输出为10；

cout<<‘a’ ;输出为65；

21.合并链表

思路正确，但就是代码有些复杂

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode* head = new ListNode(0);
        ListNode* res = head;
        ListNode* temp1 = l1;
        ListNode* temp2 = l2;
        while(temp1!= nullptr && temp2!= nullptr)
        {
            while (temp1 != nullptr && temp1->val <= temp2->val)
            {
                ListNode* temp = new ListNode(temp1->val);
                res->next = temp;
                res = temp; 
                temp1 = temp1->next;
            }
            while (temp1 != nullptr&&temp2 != nullptr && temp1->val > temp2->val)
            {
                ListNode* temp = new ListNode(temp2->val);
                res->next = temp;
                res = temp;
                temp2 = temp2->next;
            }
        }
        while (temp1!=nullptr)
        {
            ListNode* temp = new ListNode(temp1->val);
            res->next = temp;
            res= temp;
            temp1=temp1->next;
        }
        while(temp2!=nullptr)
        {
            ListNode* temp = new ListNode(temp2->val);
            res->next =temp;
            res= temp;
            temp2=temp2->next;
        }
        return head->next;
    }
};

#include <vector>
using namespace std;

/**
 * Definition for singly-linked list.
 */

struct ListNode//链表的结构体
{
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution
{
public:
    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2)
    {
        ListNode *result = new ListNode(-1); //哑节点简化代码
        ListNode *workNode = result;
        while (l1 != nullptr && l2 != nullptr) //直到有一个为空指针为止
        {
            if (l1->val <= l2->val) //若是1的值小于2的值，就考察1的下一个值
            {
                workNode->next = l1;
                l1 = l1->next;
            }
            else//考察2的下一个值
            {
                workNode->next = l2;
                l2 = l2->next;
            }
            workNode = workNode->next;
        }
        workNode->next = (l1 != nullptr) ? l1 : l2;//谁不为空就把谁剩下的加进去

        return result->next;
    }
};


连接：https://leetcode-cn.com/problems/merge-two-sorted-lists/solution/he-bing-liang-ge-you-xu-

22. 括号生成

借鉴了以前电话号码题的思路，经过一个队列作到了层序遍历，可是因为产生的括号的有效性不能保证，因此又写了一个判断有效性的函数，过程十分复杂

class Solution {
public:
    bool isright(string s)
    {
        stack<char> st;
        for (auto i : s)
        {
            if (i == '(') { st.push('('); }
            else
            {
                if (!st.empty() && st.top() == '(') { st.pop(); }
                else { return false; }
            }
        }
        if (st.empty()) { return true; }
        else { return false; }
    }

    vector<string> generateParenthesis(int n) {
        if (n == 0)
        {
            vector<string> s = { "" };
            return s;
        }
        else
        {
            string s = "(";
            queue<string> res;
            res.push(s);
            for (int i = 0; i < 2 * (n-1); i++)
            {
                int j = res.size();
                while (j)
                {

                    string s1 = res.front() + "(";
                    res.push(s1);
                    string s2 = res.front() + ")";
                    res.push(s2);
                    res.pop();
                    j--;
                }
            }
            vector<string> re;
            while (!res.empty())
            {
                string s3 = res.front() + ")";
                if (isright(s3))
                {
                    re.push_back(s3);
                    res.pop();
                }
                else { res.pop(); }
            }
            return re;
        }



    }
};

有一种能大大提升效率的方法（多用于树形问题）是剪枝算法，及时判断是否可行，不可行就舍去这一树枝

递归作法（代码简单可是情景必需要知足递归条件）：

class Solution {
public:
	vector<string> generateParenthesis(int n) {
		if (n == 0)  return{ "" };
		if (n == 1)  return{ "()" };
		vector<string> ans;
		generateParenthesisIter("(", n-1, n, ans);
		return ans;
	}

	void generateParenthesisIter(string valid, int left_num, int right_num, vector<string>& ans){
		if (left_num == 0){     //递归终止条件
			valid.append(right_num, ')');
			ans.push_back(valid);
			return;
		}
		for (int n = left_num; n >= 0; n--){ //本层使用的左括号数量
			string str = valid;
			if (left_num - n > right_num - 1)//剪枝: 无效的分支 
				return; //剩余括号中左括号数量大于右括号数量，说明已用的右括号数量大于左括号数量
			str.append(n, '(');
			str.append(1, ')');
			generateParenthesisIter(str, left_num - n, right_num - 1, ans);
		}
		return;
	}
};

做者：lcl-17
连接：https://leetcode-cn.com/problems/generate-parentheses/solution/c-shen-du-you-xian-bian-li-0ms-by-lcl-17/
来源：力扣（LeetCode）
著做权归做者全部。商业转载请联系做者得到受权，非商业转载请注明出处。

找到全部括号的组合方式看起来比较复杂。
因此咱们能够尝试换个思路：若是“(”对应数字1，“)”对应数字-1呢？
经过观察咱们能够发现这样一个规律：
凡有效的括号组合，转化成数字，任意前n项和都不小于0！
好比：“（）（）（）”
前1位：1>=0;前2位：1+(-1)=0>=0;前3位：1+(-1)+1=1>=0;
…以此类推，前n位数字和均大于等于0.
又好比：“（（（）））”
前3位：1+1+1=3>=0;前4位：1+1+1+(-1)=2>=0;前5位：1+1+1+(-1)+(-1)=1>=0;
…依然知足规律。
至此，咱们就能想到这样一个思路：
1.目标为n时，能够转化为n个-1和n个1
2.求这串数字的全部排列
3.知足以上规律的就是有效的括号组合
4.最后一步再将数字组合转化成括号组合

整个过程须要一些小的工具：
1.求全排列的函数：next_permutation
2.数字转化成括号：容器map

class Solution {
public:
    vector<string> generateParenthesis(int n)
    {
        vector<string> result;
        if(n == 0){return result;}
        vector<vector<int>> mid;
        vector<int> temp;
        for(int i = 0 ; i < n ; i ++)
        {
            temp.push_back(-1); //先放全部的-1
        }
        for(int i = 0 ; i < n ; i ++)
        {
            temp.push_back(1);  //再放全部的+1（这样的缘由是由于全排列须要从小到大的顺序）
        }
        while(next_permutation(temp.begin(),temp.end()))    //求全排列
        {
            int target = 0;
            int judg = 1;
            for(auto i:temp)
            {
                target+=i;
                if(target < 0)
                {
                    judg = 0;break; //是否知足前n项之和不小于0
                }
            }
            if(judg == 1){mid.push_back(temp);}//若是不用剪枝，则能够将数组放入mid
        }
        map<int,string> invert;
        invert.insert(map<int,string>::value_type(1,"("));  //1对应左括号
        invert.insert(map<int,string>::value_type(-1,")")); //-1对应右括号
        for(auto i:mid)
        {
            string s;
            for(auto j:i)
            {
                s += invert[j]; //数字组合转化成字符串
            }
            result.push_back(s);
        }
        return result;
    }
};

做者：da-lian-mao-ai-chi-yu
连接：https://leetcode-cn.com/problems/generate-parentheses/solution/gua-hao-tai-fu-za-shu-zi-zhuan-hua-ta-by-da-lian-m/
来源：力扣（LeetCode）
著做权归做者全部。商业转载请联系做者得到受权，非商业转载请注明出处。

全排列函数next_permutation

用这个函数一会儿就省去了找全部可能的排列，在排列以后再转成括号就好了，因为只有一种括号，就用1和-1来代替并使用剪枝算法

 while(next_permutation(temp.begin(),temp.end())) 
 {}

next_permutation(num,num+n)函数是对数组num中的前n个元素进行全排列，同时并改变num数组的值。

另外，须要强调的是，next_permutation（）在使用前须要对欲排列数组按升序排序，不然只能找出该序列以后的全排列数。

23. 合并K个排序链表

这种思路太好了，放到一块儿再重构，只要掌握好新建链表的方法就能够了，必须用new

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        vector<int> v;
        for(auto head:lists)
        {
            while(head)
            {
                v.push_back(head->val);
                head=head->next;
            }

        }
        sort(v.begin(),v.end());
        ListNode* head = new ListNode(0);
        ListNode* res = head;
        //int i = v.size();
        for(int i = 0 ; i<v.size(); i++)
        {
            ListNode* temp =new ListNode(v[i]);
            res->next = temp;
            res = temp; 
        }
        return head->next;
    }
};

26. 删除排序数组中的重复项

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        
        int i =1;
        int j = 0;
        int len = nums.size();
        if(len==0)return 0;
        for(i=1; i<len;i++)
        {
            if(nums[i]==nums[j])continue;
            else
            {
                nums[++j] = nums[i];
            }
        }
        return j+1;
    }
};

27. 移除元素

循环这里必须加等号

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
       int i = 0 ; 
       int j = nums.size()-1;
       while(i<=j)
       {
           while(i<=j && nums[i]!=val) i++;
           while(i<=j && nums[j]==val)j--;
           if(i<=j) swap(nums[i],nums[j]);
       } 
       return i;
    }
};

31. 下一个排列

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        if(next_permutation(nums.begin(),nums.end()))
        {
            return ;
        }
        else
        {
            sort(nums.begin(),nums.end());
            return ;
        }
    }
};

采用的是遍历判断法，可以剪枝的地方很是有限，因此超时了

class Solution {
public:
    
    bool is(string s1)
    {
        if(s1[0]==')')return false;
        int len = s1.size();
        if(len%2!=0)return false;
        stack<char> st;
        for(auto i:s1)
        {
            if(i=='(')
            {
                st.push(i);
            }
            else
            {
                if(!st.empty() && st.top()=='(')
                {
                    st.pop();
                }
                else
                {
                    return false;
                }
            }
        }
        return st.empty();
    }    
    
    int longestValidParentheses(string s) {
        //两种办法，第一种双指针窗口法，当遇到破坏结构时，从中间的地方开始起，可是可能会有一点复杂
        //遍历判断法，专门呢写一个函数，第一种的复杂度确定是最低的
        if(s.empty())return 0;
        int max = 0;
        int len = s.size();
        if(len==1)return 0;
        for(int i = 0 ; i<len ;i++)
        {
            for(int j = i+1;j<len;j++)
            {
                string s1=s.substr(i,j-i+1);
                if(is(s1) && j-i+1>max)max = j-i+1;
            }
        }
        return max;
    }
};

33. 搜索旋转排序数组

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int right = nums.size();
        int left = 0;
        while(left<right)
        {
            int mid = left + (right-left)/2;
            if(nums[mid]==target){return mid;}
            else if (nums[mid]>target)
            {
                if(target>=nums[0] || nums[mid]<nums[0]){right = mid;}
                else{left=mid+1;}
            }
            else
            {
                if(nums[mid]>=nums[0] ||target<nums[0]){left=mid+1;}
                else{right=mid;}
            }
        }
        return -1;
    }
};

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int lo = 0, hi = nums.size() - 1;
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            if ((nums[0] > target) ^ (nums[0] > nums[mid]) ^ (target > nums[mid]))
                lo = mid + 1;
            else
                hi = mid;
        }
        return lo == hi && nums[lo] == target ? lo : -1;
    }
};

做者：LukeLee
连接：https://leetcode-cn.com/problems/search-in-rotated-sorted-array/solution/ji-jian-solution-by-lukelee/
来源：力扣（LeetCode）
著做权归做者全部。商业转载请联系做者得到受权，非商业转载请注明出处。

34. 在排序数组中查找元素的第一个和最后一个位置

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int left = 0, right = nums.size();
        while(left<right)
        {
            int mid = left + (right-left)/2;
            if(nums[mid]==target)
            {
                int t1 =mid-1, t2 = mid+1;
                while(t1>=0 && nums[t1]==target)t1--;
                while(t2<(int)nums.size() && nums[t2]==target)t2++;
                return {t1+1,t2-1};
            }
            else if(nums[mid]<target)
            {
                left = mid +1;
            }
            else{right = mid;}
        }
        return {-1,-1};
    }
};

35. 搜索插入位置（二分法***************）

二分法的边界仍是比较难处理，这道题中当存在相等时就直接返回mid，当不相等的时候须要进行两值夹逼并返回有值，并且两个边界都不能舍去，可是这样又会可能无限循环，最后还要加个if判断是否夹逼了

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int len = nums.size();
        int left=0,right = len-1;
        if(target<=nums[0])return 0;
        if(target>nums[len-1])return len;
        if(target==nums[len-1])return len-1;
        while(left<right)
        {
            int mid = (left+right)/2;
            if(nums[mid]==target)return mid;
            else if(nums[mid]>target)
            {
                right = mid;
            }
            else
            {
                left = mid;
            }
            if(left==right-1 && nums[left]<target && nums[right]>target )return right;
        }
        return right;
    }
};

简单的写法
能够不用夹逼，由于找的时刚刚大于等于这个值的，因此每次让左边界加1

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

比较使用的模板
用来求刚刚大于等于target的第一个值

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int len = nums.size();
        int left=0,right = len;
        while(left<right)
        {
            int mid = (left+right)/2;
            if(nums[mid]==target)return mid;
            else if(nums[mid]<target)
            {
                left = mid+1;
            }
            else
            {
                right = mid;
            }
        }
        return left;
    }
};

36. 有效的数独

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        //主要考察二维数组用法
        //每一列
        for(int i= 0 ; i<9 ;i++)
        {
            set<char> st;
            int num = 0;
            for(int j = 0 ; j < 9; j++)
            {
                if(board[i][j]=='.'){continue;}
                else{st.insert(board[i][j]);num++;}
            }
            if(st.size()!=num){return false;}
        }
        //每行
        for(int i= 0 ; i<9 ;i++)
        {
            set<char> st;
            int num = 0;
            for(int j = 0 ; j < 9; j++)
            {
                if(board[j][i]=='.'){continue;}
                else{st.insert(board[j][i]);num++;}
            }
            if(st.size()!=num){return false;}
        }
        
        for(int c1 = 0 ; c1<9; c1=c1+3)
        {
            for(int c2 =0 ; c2<9 ;c2=c2+3)
            {
                set<char>st;
                int num=0;
                for(int i=0 ; i<3 ;i++)
                {
                    for(int j = 0; j<3; j++)
                    {
                        if(board[c1+i][c2+j]=='.'){continue;}
                        else{st.insert(board[c1+i][c2+j]);num++;}
                    }
                    
                }
                if(st.size()!=num){return false;}
            }
        } 
        
        return true;      
    }
};

36. 有效的数独

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        vector<int> wow(9,0);
        int mux1;
        int mux2;
        int mux3;
        int box_index;

        for(int i=0;i<9;i++){
            for(int j=0;j<9;j++){
                if(board[i][j] == '.'){
                    continue;
                }
                mux1 = 0x01 << (board[i][j] - '1');
                mux2 = 0x01 << 9 << (board[i][j] - '1');
                mux3 = 0x01 << 9 << 9 << (board[i][j] - '1');
                box_index = (i/3) * 3 + j/3;
                if((wow[i]&mux1) != mux1 && (wow[j]&mux2) != mux2 && (wow[box_index]&mux3) != mux3){
                    wow[i] = wow[i]|mux1;
                    wow[j] = wow[j]|mux2;
                    wow[box_index] = wow[box_index]|mux3;
                }
                else{
                    return false;
                }
            }
        }
        return true;
    }
};

这个遍历三次太复杂了，并且使用set时间也比较长
下面这个方法灵活运用了三个哈希表（二维数组实现）的，单次遍历，用目的区域（行、列、快）来表示行，用1-9来9个数字出现次数做为列，列为10由于直接对应，0不算，给9加一行

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        int row[9][10] = {0};// 哈希表存储每一行的每一个数是否出现过，默认初始状况下，每一行每个数都没有出现过
        // 整个board有9行，第二维的维数10是为了让下标有9，和数独中的数字9对应。
        int col[9][10] = {0};// 存储每一列的每一个数是否出现过，默认初始状况下，每一列的每个数都没有出现过
        int box[9][10] = {0};// 存储每个box的每一个数是否出现过，默认初始状况下，在每一个box中，每一个数都没有出现过。整个board有9个box。
        for(int i=0; i<9; i++){
            for(int j = 0; j<9; j++){
                // 遍历到第i行第j列的那个数,咱们要判断这个数在其所在的行有没有出现过，
                // 同时判断这个数在其所在的列有没有出现过
                // 同时判断这个数在其所在的box中有没有出现过
                if(board[i][j] == '.') continue;
                int curNumber = board[i][j]-'0';
                if(row[i][curNumber]) return false; 
                if(col[j][curNumber]) return false;
                if(box[j/3 + (i/3)*3][curNumber]) return false;

                row[i][curNumber] = 1;// 以前都没出现过，如今出现了，就给它置为1，下次再碰见就可以直接返回false了。
                col[j][curNumber] = 1;
                box[j/3 + (i/3)*3][curNumber] = 1;
            }
        }
        return true;
    }
};

做者：liujin-4
连接：https://leetcode-cn.com/problems/valid-sudoku/solution/36-jiu-an-zhao-cong-zuo-wang-you-cong-shang-wang-x/
来源：力扣（LeetCode）
著做权归做者全部。商业转载请联系做者得到受权，非商业转载请注明出处。

写了一套很是复杂的算法，原理是依次判断每一个控制区域，若是有个地方能用三个条件判断出来则填上，而后再解决其余的，结果发现代码在无限循环，缘由是不存在这样的直接能够判断出来的位置，这样原理上就出错了

class Solution {
public:
    int num(vector<vector<char>>& board, int k1, int k2)
    {

        map<char, int> m = { {'1',0},{'2',0},{'3',0},{'4',0},{'5',0},{'6',0},{'7',0},{'8',0},{'9',0} };
        for (int i = 0; i < 9; i++)
        {
            if (board[k1][i] != '.') { m[board[k1][i]] = 1; }
            if (board[i][k2] != '.') { m[board[i][k2]] = 1; }
        }
        for (int i = 0; i < 3; i++)
        {
            for (int j = 0; j < 3; j++)
            {
                if (board[k1 / 3 + i][k2 / 3 + j] != '.') { m[board[k1 / 3 + i][k2 / 3 + j]] = 1; }
            }
        }
        map<char, int>::iterator iter;
        int num = 0;
        int res = 0;
        for (auto iter = m.begin(); iter != m.end(); iter++)
        {
            //int num = 0;
            if (iter->second == 0) { res = iter->second; num++; }

        }
        if (num == 1) { return res; }
        else { return 0; }


    }


    bool is(vector<vector<char>>& board)
    {
        for (int i = 0; i < 9; i++)
        {
            for (int j = 0; j < 9; j++)
            {
                if (board[i][j] == '.') { return false; }

            }
        }
        return true;
    }
        void solveSudoku(vector<vector<char>>& board) {
        //想法使用递归，终止条件是填满了，方法是对空着的位置进行遍历，每个都设置一个哈希，当行列块又出现的设为1，当剩最后一个 了时就返回这个表

        for (int i = 0; i < 9; i++)
        {
            for (int j = 0; j < 9; j++)
            {
                if (board[i][j] == '.')
                {
                    if (num(board, i, j)) { board[i][j] = char(num(board, i, j)+'0' ); }
                    else { continue; }
                }
            }
        }
        while (!is(board)) { solveSudoku(board); }
        return;
    }
};

39. 组合总和

要特别注意将i放入下次dfs的写法，目的就是为了下次再也不查找以前的元素，值得学习

class Solution {
private:
    vector<vector<int>> res;
    vector<int> path;
    int sum = 0;
public:
    void dfs(vector<vector<int>>& res,vector<int>& candidates,vector<int>& path, int sum,int target ,int j)
    {
        if(sum == target)
        {
            res.push_back(path);return;
        }
        if(sum>target)return;
        for(int i = j; i<(int)candidates.size() ;i++)
        {
            path.push_back(candidates[i]);
            sum +=candidates[i];
            dfs(res,  candidates,  path,  sum,  target,i);
            path.pop_back();
            sum -=candidates[i];
        }
    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        sort(candidates.begin(),candidates.end());
        dfs(res,candidates,path,0,target,0);
        return res;
    }
};

dfs深度优先搜索***

回溯算法：当给定终点时，能够进行回退
再加上递归和剪枝算法

（二叉树经常使用算法：回溯、队列、递归、剪枝）

负递归算法：

// author:rmokerone
#include <iostream>
#include <vector>

using namespace std;

class Solution {
private://成员变量
    vector<int> candidates;
    vector<vector<int>> res;
    vector<int> path;
public:
    void DFS(int start, int target) {
        if (target == 0) {  //递归终止条件
            res.push_back(path);
            return;
        }
        for (int i = start; i < candidates.size() && target - candidates[i] >= 0; i++) {
            path.push_back(candidates[i]);
            DFS(i, target - candidates[i]);
            path.pop_back();
        }
    }

    vector<vector<int>> combinationSum(vector<int> &candidates, int target) {
        std::sort(candidates.begin(), candidates.end());
        this->candidates = candidates;
        DFS(0, target);

        return res;
    }

};

做者：liweiwei1419
连接：https://leetcode-cn.com/problems/combination-sum/solution/hui-su-suan-fa-jian-zhi-python-dai-ma-java-dai-m-2/
来源：力扣（LeetCode）
著做权归做者全部。商业转载请联系做者得到受权，非商业转载请注明出处。

正递归加剪枝算法：
要特别注意几点：
1.是用了剪枝是为了提速
2.除此以外，在深度优先搜索的时候能够设置从当前元素开始，由于以前的元素在以前的节点已经用过了，因此加了一个start变量用来记录在can容器中的位置
3.像sum这种的不用每次都计算，直接加个参数就好了，注意全局变量的定义位置，由于递归函数要用，因此定义在全局的地方，还能够在外面定义可是在函数中进行计算，好比siz这个变量，更严格点能够定义在private中

class Solution {
public:
    vector<int> tmp;
    vector<vector<int>> ans;
    int siz;

    void dfs(int now, int sum, int tar, vector<int>& num)
    {
        if(sum > tar) return;
        if(sum == tar)
        {
            ans.push_back(tmp);
            return;
        }
        for(int i = now; i < siz; i ++)
        {
            tmp.push_back(num[i]); //一层一层往下走
            dfs(i, sum + num[i], tar, num); //当大于或者等于时都会返回
            tmp.pop_back();//回到上一个分叉节点，从整个树的最左边一条开始试
        }
    }

    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        siz = candidates.size();
        dfs(0, 0, target, candidates);
        return ans;
    }
};

做者：iswJXkYVv3
连接：https://leetcode-cn.com/problems/combination-sum/solution/c-di-gui-shen-sou-by-iswjxkyvv3/
来源：力扣（LeetCode）
著做权归做者全部。商业转载请联系做者得到受权，非商业转载请注明出处。

41. 缺失的第一个正数

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        //sort(nums.begin(),nums.end());
        for(int i = 1;true;i++)
        {
            auto temp = find(nums.begin(),nums.end(),i);
            if (temp==nums.end()){return i;}
        }
    }
};

还可使用哈希表作，创建一个1到n的哈希表，遍历过数组后找第一个哈希值为0的

42. 接雨水

这是一个创建在一维数组上的问题，理论上这类的全部问题均可以用双指针来解决，这道题的难点在于找到最大值以后的后半部分怎么处理，怎么去找到剩下的部分，这时候须要求最大值，使用max_element函数，可是注意返回的是一个迭代器，用法以下

#include <algorithm>
//返回迭代器
auto max = max_element(v.begin(), v.end());
//获得最大值对应下标
int kk = max-v.begin();

当开始使用这个函数的时候想把里面全部的索引换成迭代器指针，可是发如今执行起来十分有困难，就是由于迭代器之间不传递，好比i和j都是v的迭代器，i++被容许，可是j=i+1就不被容许，因此能不使用迭代器就不使用，当要使用那些返回迭代器的方法时，能够用他减去v.begin()天然就返回的是下标位置

class Solution {
public:
    int trap(vector<int>& height) {
        if(height.size()<=2){return 0;}
        int i = 0;
        int j = 1;
        int sum = 0;
        while (i < height.size() - 2)
        {
            while (j<height.size() && height[i] > height[j]) { j++; }
            if (j == height.size()) 
            {
                auto m = max_element(height.begin()+i+1, height.end());
                j=m-height.begin(); 
            }
            sum = sum + (j - i - 1)*min(height[i], height[j]);
            for (int c = i + 1; c < j; c++)
            {
                sum = sum - height[c];
            }
            i = j;
            j = i + 1;
        }
        return sum;
    }
};

堆栈的方法，不是很好理解

直观想法

咱们能够不用像方法 2 那样存储最大高度，而是用栈来跟踪可能储水的最长的条形块。使用栈就能够在一次遍历内完成计算。

咱们在遍历数组时维护一个栈。若是当前的条形块小于或等于栈顶的条形块，咱们将条形块的索引入栈，意思是当前的条形块被栈中的前一个条形块界定。若是咱们发现一个条形块长于栈顶，咱们能够肯定栈顶的条形块被当前条形块和栈的前一个条形块界定，所以咱们能够弹出栈顶元素而且累加答案到
\text{ans}ans 。

算法

使用栈来存储条形块的索引下标。遍历数组：当栈非空且
\text{height}[current]>\text{height}[st.top()]height[current]>height[st.top()]
意味着栈中元素能够被弹出。弹出栈顶元素 \text{top}top。计算当前元素和栈顶元素的距离，准备进行填充操做
\text{distance} = \text{current} - \text{st.top}() -
1distance=current−st.top()−1 找出界定高度 \text{bounded_height} =
\min(\text{height[current]}, \text{height[st.top()]}) -
\text{height[top]}bounded_height=min(height[current],height[st.top()])−height[top]
往答案中累加积水量\text{ans} \mathrel{+}= \text{distance} \times
\text{bounded_height}ans+=distance×bounded_height 将当前索引下标入栈将
\text{current}current 移动到下个位置

做者：LeetCode
连接：https://leetcode-cn.com/problems/trapping-rain-water/solution/jie-yu-shui-by-leetcode/
来源：力扣（LeetCode）
著做权归做者全部。商业转载请联系做者得到受权，非商业转载请注明出处。

int trap(vector<int>& height)
{
    int ans = 0, current = 0;
    stack<int> st;
    while (current < height.size()) {
        while (!st.empty() && height[current] > height[st.top()]) {
            int top = st.top();
            st.pop();
            if (st.empty())
                break;
            int distance = current - st.top() - 1;
            int bounded_height = min(height[current], height[st.top()]) - height[top];
            ans += distance * bounded_height;
        }
        st.push(current++);
    }
    return ans;
}

做者：LeetCode
连接：https://leetcode-cn.com/problems/trapping-rain-water/solution/jie-yu-shui-by-leetcode/
来源：力扣（LeetCode）
著做权归做者全部。商业转载请联系做者得到受权，非商业转载请注明出处。

43. 字符串相乘

没有思路，原来是利用乘法的计算方式来的
在这里插入图片描述

class Solution {
public:
    string multiply(string num1, string num2) {
        int n1=num1.size();
        int n2=num2.size();
        string res(n1+n2,'0');
        for(int i=n2-1;i>=0;i--){
            for(int j=n1-1;j>=0;j--){
                int temp=(res[i+j+1]-'0')+(num1[j]-'0')*(num2[i]-'0');
                res[i+j+1]=temp%10+'0';//当前位
                res[i+j]+=temp/10; //前一位加上进位，res[i+j]已经初始化为'0'，加上int类型自动转化为char，因此此处不加'0'
            }
        }
        
//去除首位'0'
        for(int i=0;i<n1+n2;i++){
            if(res[i]!='0')
                return res.substr(i);
        }
        return "0";
       
        
    }
};

做者：carryzz
连接：https://leetcode-cn.com/problems/multiply-strings/solution/c-shu-shi-cheng-fa-dai-ma-jian-ji-you-ya-yi-dong-b/
来源：力扣（LeetCode）
著做权归做者全部。商业转载请联系做者得到受权，非商业转载请注明出处。

44. 通配符匹配

在这里插入图片描述

class Solution {
public:
    bool isMatch(string s, string p) {
        int n = s.size(), m = p.size();
        vector< vector<bool> > dp(n+1, vector<bool>(m+1, false)); dp[0][0] = true;

        // initialize 
        for (int i = 1; i <= m; ++ i){
            if(p[i - 1] == '*' && dp[0][i - 1]) dp[0][i] = dp[0][i - 1];
        }

        for (int i = 1; i <= n; ++ i){
            for (int j = 1; j <= m; ++ j){
                if (s[i - 1] == p[j - 1] || p[j - 1] == '?'){
                    dp[i][j] = dp[i - 1][j - 1];// ismatch, move on
                }else if (p[j - 1] == '*'){
                    bool zero, mul;// '*' act as zero, '*' act as multiple characters
                    zero = (j < m && s[i - 1] == p[j] && dp[i - 1][j - 1]) || dp[i][j - 1];
                    mul = dp[i -1][j];
                    dp[i][j] = zero || mul;
                }
            }
        }

        return dp[n][m];
    }
};

做者：wen-mu-yang
连接：https://leetcode-cn.com/problems/wildcard-matching/solution/c-dong-tai-gui-hua-yu-shuang-zhi-zhen-tan-xin-by-w/
来源：力扣（LeetCode）
著做权归做者全部。商业转载请联系做者得到受权，非商业转载请注明出处。![在这里插入图片描述](https://img-blog.csdnimg.cn/20200329203606940.PNG?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzU3OTA3OQ==,size_16,color_FFFFFF,t_70)

45. 跳跃游戏 II

使用了递归算法，不断更新起点，每更新一次跳到能跳到的最远的地方，记录到达终点时的步数，但在过程当中关于什么时候记录步数的问题很难。终于调成功后发现这样是错误的，由于有时不须要全跳，尤为是最后几个值为0的状况，要是早早跳到这里反而会到不了终点！

class Solution {

public:
	int ans=0;

	int summm(int start, vector<int> nums)
	{
		int  temp = max_element(nums.begin() + start +1, nums.begin() + start + nums[start]+1) - nums.begin();
		
		if (start + nums[start] >= temp + nums[temp]) { ans++; return start + nums[start]; }
		else { ans++; return temp ; }
		
	}
	int jump(vector<int>& nums) {
		int len = nums.size();
		//int ans = 0;
		if (len == 1) { return 0; }
		else
		{
			int start = 0;
			//if (start + nums[start] >= len) { return 1; }
			while (start<len )
			{

				if (start + nums[start] >= len-1) { return ans + 1; }
				start = summm(start, nums);
	
				
			}
			return ans;



		}
	}
};

在这里插入图片描述

贪心算法

看了解答，发现这种思路总体是对的，就是追求每一次能走的最大，然而以前的错误在于，并非比较start+nums[start]和max[start,start+len(start)]之间的最大值，应该比较的是和区间里每个值和其值的和即i+len(i)，这才是走的最远的方法，按照这种方法不断更新，就能够找到最后了
即便意思相近可是别人的表达也十分简介

int jump(vector<int> &nums)
{
    int ans = 0;
    int start = 0;
    int end = 1;
    while (end < nums.size())
    {
        int maxPos = 0;
        for (int i = start; i < end; i++)
        {
            // 能跳到最远的距离
            maxPos = max(maxPos, i + nums[i]); //在遍历的过程当中不断更新这个最大值
        }
        start = end;      // 下一次起跳点范围开始的格子
        end = maxPos + 1; // 下一次起跳点范围结束的格子，加一是由于上面的遍历时左闭右开的
        ans++;            // 跳跃次数
    }
    return ans;
}

做者：ikaruga
连接：https://leetcode-cn.com/problems/jump-game-ii/solution/45-by-ikaruga/
来源：力扣（LeetCode）
著做权归做者全部。商业转载请联系做者得到受权，非商业转载请注明出处。

46. 全排列

关于全排列next_permumation有几点须要说明
1.之气那要排序
2.只要开始全排列，第一个结果是已经改变以后的数组，而不是原来的
3。参数是首末迭代器

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int> > res;
        sort(nums.begin(), nums.end());
        res.push_back(nums);
        while(next_permutation(nums.begin(),nums.end()))
        {
            res.push_back(nums);
        }
        return res;
        
    }
};

这是使用队列层序遍历的方法写的，可是因为不容许重复，每次要使用find判断，十分复杂

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int> > res;
        if (nums.size()==0 || nums.size()==1)
        {
            res.push_back(nums);
            return res;
        }
        sort(nums.begin(), nums.end());
        queue<vector<int>> q;
        
        for(auto i:nums)
        {
            vector<int> temp;
            temp.push_back(i);
            q.push(temp);
        }
        
        //int i=nums.size()-1;
        while(q.front().size()!=nums.size())
        {                
                
                for (auto i:nums)
                {
                    vector<int> temp = q.front();
                    if(find(temp.begin(),temp.end(),i)==temp.end())
                    {
                        temp.push_back(i);
                        q.push(temp);
                    }
                }
                q.pop();
        }
        while(!q.empty())
        {
            res.push_back(q.front());
            q.pop();
        }
        return res;
        
    }
};

回溯问题+决策树

算法模板

递归{
    递归出口；
    for(int i = 1;i<=n;i++){
    	add(i);
    	进入递归；
   		remove(i);
	}
}


做者：windliang
连接：https://leetcode-cn.com/problems/unique-binary-search-trees-ii/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-2-7/
来源：力扣（LeetCode）
著做权归做者全部。商业转载请联系做者得到受权，非商业转载请注明出处。

void backtrack(路径，选择列表)
{
	if(终止条件)
	{
		传出路径结果
		return;
	}
	for i in 选择列表
	{
		进入该选择
		back(路径，选择列表)
		退出该选择
	}
}

这是根据该思想写的代码，代码结构简单，清晰，可是优化的很差

class Solution {
private:
    vector<vector<int> > res;
    int len;
    vector<int> path;
public:
    void backtrack(vector<int> &path, vector<int>& nums)
    {
        set<int> s(path.begin(),path.end());
        if(path.size()==len)
        {
            if (s.size()==len)
            {
                res.push_back(path);
                return;                
            }
            else
            {
                return;
            }
        }        
        for(auto i : nums)
        {
            path.push_back(i);
            backtrack(path,nums);
            path.pop_back();
        }
    }
    
    vector<vector<int>> permute(vector<int>& nums) {
        len = nums.size();
        if (nums.size()==0 || nums.size()==1)
        {
            res.push_back(nums);
            return res;
        }
        sort(nums.begin(), nums.end());
        backtrack(path,nums);
        return res;

        
    }
};

48. 旋转图像

将图片沿正对角线和竖轴翻转一下就能够了

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();
        int m = matrix[0].size();
        
        // 对于正对角线对称翻转
        for (int i = 0; i < n; i++) {
            for (int j = i; j < m; j++) {
                swap(matrix[i][j], matrix[j][i]);
            }
        }
        // 竖轴镜像操做
        for (int i = 0; i < n; i++) {
            reverse(matrix[i].begin(), matrix[i].end());
        }
    }
};

做者：happy_yuxuan
连接：https://leetcode-cn.com/problems/rotate-image/solution/leetcode48-fan-zhuan-gui-lu-by-happy_yuxuan/
来源：力扣（LeetCode）
著做权归做者全部。商业转载请联系做者得到受权，非商业转载请注明出处。

49. 字母异位词分组

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> res;
        vector<pair<multiset<char>,vector<string>>> st;
        for(auto str:strs)
        {
            multiset<char> temp(str.begin(),str.end());
            bool b = false;
            for(int i = 0 ;i<(int)st.size() ;i++)
            {
                
                if(st[i].first==temp)
                {
                    st[i].second.push_back(str);
                    b = true;
                    break;
                }

            }
            if(!b)
            {
                st.push_back(pair<multiset<char>,vector<string>>(temp,{str}));
            }
        }
        for(auto i:st)
        {
            vector<string> temp;
            for(auto j:i.second)
            {
                temp.push_back(j);
            }
            res.push_back(temp);
        }
        return res;
    }
};

更好的办法：哈希表和数组联系，只要引入一个hash表，索引是排序后的单词，值为结果vector的下标，循环一遍就行了

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> res;  
        int sub=0;  //结果vector的下标值
        string tmp; //临时string
        unordered_map<string,int> work; //判断排序后单词是否存在，即字母组成是否一致
        for(auto str:strs)
        {
            tmp=str;
            sort(tmp.begin(),tmp.end());
            if(work.count(tmp))
            {
               res[work[tmp]].push_back(str);
            }
            else
            {
                vector<string> vec(1,str);
                res.push_back(vec);
                work[tmp]=sub++;
            }
        }
        return res;
    }
};

做者：rjs
连接：https://leetcode-cn.com/problems/group-anagrams/solution/c-yin-ru-hashbiao-shi-jian-32ms-ji-bai-9948-nei-cu/
来源：力扣（LeetCode）
著做权归做者全部。商业转载请联系做者得到受权，非商业转载请注明出处。

50. Pow(x, n)

暴力法

class Solution {
public:
    double myPow(double x, int n) {
        if(x==0)return 0;
        if(x==1 || n==0) return 1;
        double res=1;
        while(n>0)
        {
            res=res*x;
            n--;
        }
        while(n<0)
        {
            res = res/x;
            n++;
        }

        return res;

    }
};

递归法，将指数幂进行二分，十分巧妙

class Solution {
public:
    double myPow(double x, int n) {
        if (n == 0) { return 1; }
        if (n == 1) { return x; }
        if (n == -1) { return 1 / x; }
        double half = myPow(x, n / 2);
        double rest = myPow(x, n % 2);
        return rest * half * half;
    }
};

做者：frank588
连接：https://leetcode-cn.com/problems/powx-n/solution/qing-xi-jian-dan-de-dan-han-shu-di-gui-wu-lei-xing/
来源：力扣（LeetCode）
著做权归做者全部。商业转载请联系做者得到受权，非商业转载请注明出处。

51. N皇后（回溯dfs）

思路很是清晰，典型的n皇后的问题，稍微麻烦的问题是判断是否额可以知足条件，并且注意不用在最后才检查条件。应该在中间进行判断，只要可以知足条件才继续下去，这样到最后也就知足条件了，放一个知足一个，最后就必定知足，这里一行一行创建的会稍微简单一点

class Solution {
    vector<vector<string>> res;//存结果
    vector<string> tmp;//存棋盘
public:
    vector<vector<string>> solveNQueens(int n) {
        string line(n,'.');//既然一行一行试，那就一行一行存
        solveNQueens(line, 0, n);//从第0行开始
        return res;
    }

private:
    //试某一行
    void solveNQueens(string& line, int row, int n)
    {
        if(tmp.size() == n)//棋盘绘制够n行存进结果，不用继续试了
        {
            res.push_back(tmp);
            return;
        }
        for(int i = 0; i < n; ++i)//一格一格，每格都要试
        {
            if(checkAll(row, i, n))     //符合条件了
            {
                line[i] = 'Q';          //就把当前试的这一格放皇后
                tmp.push_back(line);    //而后把这一行绘制进棋盘
                line[i] = '.';          //棋盘的下一行应该是没有皇后的
                solveNQueens(line, row + 1, n);//去试下一行
                tmp.pop_back();         //接下来要去试下一格，刚才绘制进去的那一行删掉
            }
        }
    }

    //暴力检查条件
    bool checkAll(int row, int col, int n)
    {
        for(int i = row - 1, j = col - 1; i >= 0 && j >= 0; --i,--j)//左上方
        {
            if(tmp[i][j] == 'Q')
                return false;
        }
        for(int i = row - 1; i >= 0; --i)//正上方
        {
            if(tmp[i][col] == 'Q')
                return false;
        }
        for(int i = row -1, j = col + 1; i >= 0 && j < n; --i, ++j)//右上方
        {
            if(tmp[i][j] == 'Q')
                return false;
        }
        return true;
    }
};

做者：zynflicker
连接：https://leetcode-cn.com/problems/n-queens/solution/4ms89mhui-su-fa-jian-dan-yi-dong-by-zynflicker/
来源：力扣（LeetCode）
著做权归做者全部。商业转载请联系做者得到受权，非商业转载请注明出处。

53. 最大子序和（贪心）

很典型的使用贪心算法的例题

class Solution
{
public:
    int maxSubArray(vector<int> &nums)
    {
        //相似寻找最大最小值的题目，初始值必定要定义成理论上的最小最大值
        int result = INT_MIN;
        int numsSize = int(nums.size());
        int sum = 0;
        for (int i = 0; i < numsSize; i++)
        {
            sum += nums[i];
            result = max(result, sum);
            //若是sum < 0，从新开始找子序串
            if (sum < 0)
            {
                sum = 0;
            }
        }

        return result;
    }
};

做者：pinku-2
连接：https://leetcode-cn.com/problems/maximum-subarray/solution/zui-da-zi-xu-he-cshi-xian-si-chong-jie-fa-bao-li-f/
来源：力扣（LeetCode）
著做权归做者全部。商业转载请联系做者得到受权，非商业转载请注明出处。

55. 跳跃游戏

每次跟新一次位置，当最远达到的地方是0，说明false，代码用vs会出现莫名其妙的问题，可是作法应该是对的
另外因为可能出现的请状况太多了，在边界的设置上出错的地方太多了

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int left = 0;
        int len = nums.size();
        while(1)
        {
            if(left>=len-1 || left+nums[left]>=len-1)return true;
            
            int max = 0;
            int temp = 0;
            for(int i = left ; i<=len-1 &&i<=left+nums[left] ;i++)
                {
                if(i+nums[i]>max){max = i+nums[i];temp=i;}

            }
            if(max<len-1&& nums[max]==0)return false;
            left = temp;
        }
        return false;
    }
};

一样意思但更简洁的代码
解题思路：
1.若是某一个做为起跳点的格子能够跳跃的距离是 3，那么表示后面 3 个格子均可以做为起跳点。
2.能够对每个能做为起跳点的格子都尝试跳一次，把能跳到最远的距离不断更新。
3.若是能够一直跳到最后，就成功了。

做者：ikaruga
连接：https://leetcode-cn.com/problems/jump-game/solution/55-by-ikaruga/
来源：力扣（LeetCode）
著做权归做者全部。商业转载请联系做者得到受权，非商业转载请注明出处。

bool canJump(vector<int>& nums) 
{
	int k = 0;
	for (int i = 0; i < nums.size(); i++)
	{
		if (i > k) return false;//k表示到i的时候，以前全部位置能到达的最大距离，每个都走一下，可是不用考虑怎么走的，当走到一个位置不能再更新了，就会小于下一个i
		k = max(k, i + nums[i]);
	}
	return true;
}

做者：ikaruga
连接：https://leetcode-cn.com/problems/jump-game/solution/55-by-ikaruga/
来源：力扣（LeetCode）
著做权归做者全部。商业转载请联系做者得到受权，非商业转载请注明出处。

56. 合并区间(贪心)

一样的格式，可是改为max了，并且维护的不是一个树，而是先放到二维向量中的末尾

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector<vector<int>> res;
        if(intervals.empty())return res;
        sort(intervals.begin(),intervals.end());
        res.push_back(intervals[0]);
        for(int i = 1 ;i< (int)intervals.size() ;i++)
        {
            if(intervals[i][0]<= res.back()[1])
            {
                res.back()[1] = max(res.back()[1],intervals[i][1]);
            }
            else
            {
                res.push_back(intervals[i]);
            }
        }
        return res;
    }
};

使用长度为1的滑动窗口在滑动，可是没想到题目仍是会出现后面区间包含前面的状况，这样就要从新设计了
看到答案说sort函数排序能够默认按照第一个第二个这样排序，能够排序以后在作,排序以后后面的值确定是大于等于前面的，可是还要考虑后面包含前面的状况

考点：排序+数组
思路：先对二维数组表示的全部区间的左端点进行升序排序，而后从第二个区间（下标为1）开始遍历判断是否能够作合并操做：只要前一个区间的右端点大于等于当前区间的左端点，那说明这两个区间能够合并，合并后的区间左端点是前一个区间的左端点，只须要更新右端点为两个区间右端点的最大值便可。
不然，说明两个区间没有重叠，直接更新表示不重复区间的pos值

做者：xing2fan
连接：https://leetcode-cn.com/problems/merge-intervals/solution/qu-jian-he-bing-de-pai-xu-fa-by-xing2fan/
来源：力扣（LeetCode）
著做权归做者全部。商业转载请联系做者得到受权，非商业转载请注明出处。

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        if (!intervals.size()) return {};

        //先把区间集合按照左端点从小到大进行排序
        sort(intervals.begin(), intervals.end(), less<vector<int>>());
        int pos = 0;//pos的值是每一个不重叠的区间
        //直接在原区间上作就能够
        //从第二个区间开始去比较
        for (int i = 1; i < intervals.size(); ++i) 
        {
            //两个区间若能合并，则第一个区间的右端点必定大于等于第二个区间的左端点
            //好比[1,3] [2,6]
            if (intervals[pos][1] >= intervals[i][0]) 
            {
                //第一个区间的尾部须要更新为：两个区间的最大值即[1,6]
                intervals[pos][1] = max(intervals[pos][1], intervals[i][1]);
            } 
            else//没有重叠时 
            {
                //[1,6] [2,8]====>区间1就是目前的这个区间
                intervals[++pos] = intervals[i];
            }
        }

        intervals.resize(pos + 1);//把最后的不用的弹出
        return intervals;
    }
   
};

做者：xing2fan
连接：https://leetcode-cn.com/problems/merge-intervals/solution/qu-jian-he-bing-de-pai-xu-fa-by-xing2fan/
来源：力扣（LeetCode）
著做权归做者全部。商业转载请联系做者得到受权，非商业转载请注明出处。

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        if (intervals.empty()) {
            return intervals;
        }
        sort(intervals.begin(), intervals.end());
        vector<vector<int>> result{ intervals.front() };
        for (auto&& interval : intervals) {
            if (interval.front() > result.back().back()) {
                result.emplace_back(move(interval));
            } else {
                result.back().back() = max(interval.back(), result.back().back());
            }
        }
        return result;
    }
};

做者：klaxxi
连接：https://leetcode-cn.com/problems/merge-intervals/solution/c-pai-xu-tan-xin-by-klaxxi/
来源：力扣（LeetCode）
著做权归做者全部。商业转载请联系做者得到受权，非商业转载请注明出处。

57. 插入区间

和上题同样，先插入再作

class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        vector<vector<int>> res;
        if(newInterval.empty())return intervals;
        intervals.push_back(newInterval);
        sort(intervals.begin(),intervals.end());
        res.push_back(intervals[0]);
        for(int i =1; i< (int)intervals.size() ;i++)
        {
            if(intervals[i][0]<= res.back()[1])
            {
                res.back()[1] = max(res.back()[1], intervals[i][1]);
            }
            else
            {
                res.push_back(intervals[i]);
            }
        }
        return res;
        
    }
};

62. 不一样路径(dp)

在多种题解法中，动态规划每每是最简单的一种，而递归每每是麻烦也很差写的一种，因此最好仍是先考虑dp，这道理可想而知dp较为简单，以前作的dp都是在一维上，这回是二维上的dp

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> board(m,vector<int>(n,0));
        for(int i = 0 ; i <m ;i++)
        {
            board[i][0]=1;
        }
        for(int j = 0; j<n ;j++)
        {
            board[0][j]=1;
        }
        for(int i = 1; i<m ;i++)
        {
            for(int j = 1 ; j<n ;j++)
            {
                board[i][j] = board[i-1][j] + board[i][j-1];
            }
        }      
        return board[m-1][n-1];  
    }
};

64. 最小路径和(dp)

很典型的动态规划题目，和上题同样

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        if(grid.empty())return 0;
        int m = grid.size();
        int n = grid[0].size();
        vector<vector<int>> board(m,vector<int>(n,0));
        board[0][0]=grid[0][0];
        for(int i = 1 ; i< n ;i++)
        {
            board[0][i] = grid[0][i]+board[0][i-1];
        }
        for(int i = 1 ; i< m ; i++)
        {
            board[i][0] = grid[i][0]+board[i-1][0];
        }
        for(int i = 1 ; i < m ;i++)
        {
            for(int j = 1 ; j< n; j++)
            {
                board[i][j] = grid[i][j] + min(  board[i-1][j],board[i][j-1]);
            }
        }
        return board[m-1][n-1];
    }
};

69. x 的平方根(二分法)

虽然就是典型的二分法，可是有不少值得讲究的地方：
1.mid最好设置为两个的和除以2再加1，扩大范围更好，否则可能会chucuo
2.初始值能够设置的更小点
3.最后是left和right的变化问题，最后两个都变化或者至少一个变化，而后返回left就能够，没必要要返回mid

class Solution {
public:
    int mySqrt(int x) {
        if(x==0)return 0;
        long left = 1;
        long right = x;
        while(left<right)
        {
            long mid = (left+right)/2+1;
            if(mid==x/mid)return mid;
            else if(mid>x/mid)
            {right = mid-1;}
            else
            {left = mid;}
        }
        return left;
    }
};

70. 爬楼梯（dp）

动态规划

class Solution {
public:
    int climbStairs(int n) {
        if(n==0)return 0;
        if(n==1)return 1;
        if(n==2) return 2;
        vector<int> dp(n+1,0);
        dp[0]=0;
        dp[1]=1;
        dp[2]=2;
        for(int i = 3 ; i<n+1; i++)
        {
            dp[i] = dp[i-1]+ dp[i-2];
        }
        return dp[n];
    }
};

72. 编辑距离

class Solution {
public:
    int minDistance(string word1, string word2) {
        int len1 = word1.size();
        int len2 = word2.size();
        vector<vector<int>> dp(len1+1, vector<int>(len2+1,0));
        for(int i = 0 ;i<=len1; i++)
        {
            dp[i][0] = i;
        }
        for(int j = 0 ; j<=len2 ;j++)
        {
            dp[0][j] = j;
        }
        
        for(int i=1 ;i<=len1 ;i++)
        {
            for(int j=1; j<=len2 ;j++)
            {
                if(word1[i-1]==word2[j-1])
                {
                    dp[i][j] = dp[i-1][j-1] ;
                }
                else
                {
                    dp[i][j] = min(dp[i-1][j-1],min(dp[i-1][j],dp[i][j-1]))+1;
                }
            }

        }
        return dp[len1][len2];
    }
};

73. 矩阵置零

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        if(matrix.size()==0)return;
        vector<int> row;
        vector<int> col;
        int len1 = matrix.size();
        int len2 = matrix[0].size();
        for(int i= 0 ;i<len1 ; i++)
        {
            for(int j = 0 ; j <len2 ;j++)
            {
                if(matrix[i][j]==0) 
                {
                    row.push_back(i);
                    col.push_back(j);
                }
            }
        }
        for(auto i :row)
        {
            for(int j = 0 ; j<len2 ;j++)
            {
                matrix[i][j]=0;
            }
        }
        for(auto j:col)
        {
            for(int i = 0 ; i<len1 ; i++)
            {
                matrix[i][j] = 0;
            }
        }
        return;
    }
};

75. 颜色分类（三数快排）

只有三个数的时候排序能够如此简单

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int left = 0 , right = nums.size()-1;
        for(int i = left ;i<=right ;i++)
        {
            if(nums[i]==0)swap(nums[left++],nums[i]);
            if(nums[i]==2)swap(nums[right--],nums[i--]);

        }
        return;
    }
};

快速排序

巩固一下快速排序，要特注意的是先循环j再循环i

class Solution {
public:
    void quicksort(int left,int right, vector<int>& nums)
    {
        if(left>=right)return;
        int i = left;
        int j = right;
        while(i<j)
        {
            while(i<j && nums[j]>=nums[left])j--;
            while(i<j && nums[i]<=nums[left])i++;
            
            if(i<j)
            {
                swap(nums[i],nums[j]);
            }

        }
        swap(nums[left],nums[i]);
        quicksort(left,i-1,nums);
        quicksort(i+1,right,nums);
    }
    void sortColors(vector<int>& nums) {
        int len = nums.size();
        if(len==0 || len==1)return;
        quicksort(0,len-1,nums);
        return;
    }
};

74. 搜索二维矩阵

采用了两个二分法模板作的，注意衔接的时候，要考虑小于第一个个值的状况

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if(matrix.empty())return false;
        if(matrix[0].empty())return false;
        int len = matrix.size();
        int left = 0,right = len;
        while(left<right)
        {
            int mid = (left+right)/2;
            if(matrix[mid][0]==target)return true;
            else if(matrix[mid][0]<target)
            {
                left = mid+1;
            }
            else
            {
                right = mid;
            }
        }
        int temp = left-1;
        if(temp<0)return false;
        len = matrix[0].size();
        left = 0;right=len;
        while(left<right)
        {
            int mid = (left+right)/2;
            if(matrix[temp][mid]==target) return true;
            else if(matrix[temp][mid]<target)
            {
                left=mid+1;
            }
            else
            {
                right=mid;
            }
        }
        return false;
    }
};

77. 组合

因为这个pos表明的是初始位置，当进行过一次遍历后，这个值也要加1才行

class Solution {
private:
vector<vector<int> > res;
vector<int> path;
public:
    void dfs(int n,int pos, int k)
    {
        if (path.size()==k)
        {
            res.push_back(path);
        }
        for(int i = pos; i<= n; i++)
        {
            path.push_back(i);
            dfs(n,pos+1,k);
            path.pop_back();
            pos++;
        }
    }

    vector<vector<int>> combine(int n, int k) {
        if(n==0||k==0) return res;
        dfs(n,1,k);
        return res;
    }
};

其余解答，道理是同样的

class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> list;
        vector<int> result;
        dfs(list,result,n,k,0,-1);       
        return list;
    }
    void dfs(vector<vector<int>>& list, vector<int>& result, int n, int k, int pos,int pre){
        if(pos == k){
            list.push_back(result);
            return;
        }
        if((pos + (n-pre)) <= k)return;//剪枝，添加以后用时节省了2/3
        //在当前对不合理的取值进行判断，结束下一层的递归操做。
        //若是当前剩余可操做数字的个数即（n-pre）< k-pos+1(即组合中有待赋值的位置个数)，（+1是由于当前pos尚未进行操做），则能够判断该条路径不可能获得正确的解，再也不向下探寻。
        for(int i=pre+1; i<n ; i++){
            result.push_back(i+1);
            pre = i;
            dfs(list,result,n,k,pos+1,pre);
            result.pop_back();//回溯
        }
        return;
    }
};

做者：rouzi
连接：https://leetcode-cn.com/problems/combinations/solution/dfsjian-zhi-by-rouzi/
来源：力扣（LeetCode）
著做权归做者全部。商业转载请联系做者得到受权，非商业转载请注明出处。

78. 子集

适合用递归作，可是递归并很差写
下面这个递归式return，是在最后（至关于没有），这个结构比较少见，主要是由于没有肯定的返回条件，进行一个遍历，而后在遍历的过程当中不断的放入大的容器

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int> > res;
        vector<int> tmp;
        helper(res,tmp,nums,0);
        return res;
    }
    void helper(vector<vector<int> >& res,vector<int> tmp,vector<int>& nums,int level){
        if(tmp.size()<=nums.size()){
            res.push_back(tmp);
        }
        for(int i=level;i<nums.size();i++){
            tmp.push_back(nums[i]);
            helper(res,tmp,nums,i+1);
            tmp.pop_back();
        }
        return;
    }
};

做者：Tangzixia
连接：https://leetcode-cn.com/problems/subsets/solution/liang-chong-fang-fa-qiu-jie-zi-ji-by-tangzixia/
来源：力扣（LeetCode）
著做权归做者全部。商业转载请联系做者得到受权，非商业转载请注明出处。

class Solution {
public:
    vector<vector<int>> ans;
    vector<int> tmp;
    void find(int dep, vector<int>& nums)
    {
        // 已经处理完最后一位，将目前存储的集合存入 ans ，并回溯
        if(dep <= 0)
        {
            ans.push_back(tmp);
            return;
        }
        // 状况一：集合中有该元素
        tmp.push_back(nums[dep - 1]);
        find(dep - 1, nums);
        tmp.pop_back();
        // 状况二：集合中无该元素
        find(dep - 1, nums);
    }

    vector<vector<int>> subsets(vector<int>& nums) {
        find(nums.size(), nums);
        return ans;
    }
};

做者：iswJXkYVv3
连接：https://leetcode-cn.com/problems/subsets/solution/c-0ms-132mb-shen-sou-yong-shi-ji-bai-100mark-by-is/
来源：力扣（LeetCode）
著做权归做者全部。商业转载请联系做者得到受权，非商业转载请注明出处。

79. 单词搜索

因为代码太复杂没有全写完，可是道理应该是对的，遍历每一个word中的字符，当找到该字符时就将下一个字符、找到的坐标、board输入到判断函数中，当全部字符都判断成功时才算含有此字符串，道理时对的，但不算是dfs或者回溯方法

class Solution {
private:
    string s1;
    int h=0;
    int l = 0;
public:

    //位置必须传递，才能和上次有关联
    bool dfs(char s1, string& s, int a , int b , vector<vector<char>>& board)
    {
        if(a==0)
        {
            if(b==0)
            {
                if(board[a+1][b]==s1 || board[a][b+1]==s2){return true;}}
            }
            if(b==l-1 )
            {
                if(board[a+1][b]==s1 || board[a][b-1]==s2){return true;}}
            }
            else
            {
                if(board[a+1][b]==s1 || board[a][b+1]==s2 || board[a][b-1]==s2){return true;}}
            }
            
            for(int j = 0 ; j <b ; j++ )
            {
                if(board[a+1][j]==s1){return true;}

        }
        if(a==h-1)
        {
            for(int j = 0 ; j <b ; j++ )
            {
                if(board[a-1][j]==s1){return true;}
            }
        }
        if(b==l-1)
        {
            for(int i = 0 ; i<a; i++)
            {
                if(board[i][])
            }
        }        
        
        
        for(auto i :s)
        {
            
            dfs(i,s,)
            
        }

    }
    bool exist(vector<vector<char>>& board, string word) {
        h = board.size();
        l = board[0].size();
        //如何获取第一次的正确位置，或者进行遍历寻找
        for(int i = 0 ; i< h;i++ )
        {
            for(int j = 0; j<l ; j++)
            {
                if (board[i][j]==word[0])//这里不用判断
                {
                    if(dfs(word[1],word,i,j,board)){return true;}
                }
            }
        }
        return false;
        
    }
};

class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        if(board.size() == 0) return false;
        for (int i=0;i<board.size();i++){
            for(int j=0;j<board[0].size();j++){
                if (dfs(board,word,i,j,0)){
                    return true;
                }
            }
        }
        return false;
    }

    bool dfs(vector<vector<char>>& board, string& word, int i,int j,int length){
        if(i>=board.size()||j>=board[0].size()||i<0||j<0||length>=word.size()||word[length]!=board[i][j]){
            return false; //出界或者最后一位不相等
        }
        if(length==word.size()-1&&word[length]==board[i][j]){//word不为空且最后一位和当前位置相等
            return true;
        }
        char temp=board[i][j];
        board[i][j]='0';//这个位置
        bool flag=dfs(board,word,i,j+1,length+1)||dfs(board,word,i,j-1,length+1)||dfs(board,word,i+1,j,length+1)||dfs(board,word,i-1,j,length+1); //找四边的每个点，若是点
        board[i][j]=temp;  // 标记过的点恢复原状，以便进行下一次搜索
        return flag;
    }
};

做者：z1m
连接：https://leetcode-cn.com/problems/word-search/solution/tu-jie-di-gui-shen-du-you-xian-sou-suo-by-z1m/
来源：力扣（LeetCode）
著做权归做者全部。商业转载请联系做者得到受权，非商业转载请注明出处。

伪代码

dfs（i，j，word， board，len）
{
	if（i，j已经出界 || 这个位置和wordlen元素不相等）
	{返回false}
	if（这个位置和word最后一维相等）
	{返回true}
	
}
exist（）
{
	遍历board，并对每个位置执行一次判断//当每一个位置都输入进去，直接进入dfs，判断和第一位是否相等，若是不相等则到下一个位置，若是相等则进入函数主体，判断四周的四个位置都和下一位相等，true的终止条件是到了最后一位并且与此位置相等。里面有一点要注意为了防止出现AEA这种又回去的状况，在这次搜索中已经相等过的要设置为‘0’防止回去
}

1.总结：dfs也能够设置为有类型的，当设置为bool型这种特殊的类型时，要写两个终止条件，一个是true的，一个是false，false能够是每次的回退条件，可是true必定是最终的判断条件，剩下的函数主题就是默认的经过这次验证

80. 删除排序数组中的重复项 II

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int len = nums.size();
        int i = 0, j = 0;
        while(i<len)
        {
            int temp = i;
            while(i<len && nums[i]==nums[temp])i++;
            if(i-temp==1){nums[j++]=nums[temp];}
            else if(i-temp>=2){nums[j++]=nums[temp];nums[j++]=nums[temp];}
            
        }
        return j;
    }
};

81. 搜索旋转排序数组 II

先去重

class Solution {
public:
    bool search(vector<int>& nums, int target) {
        if(nums.empty())return false;
        int j = 0;
        for(int i =1 ;i<(int)nums.size() ;i++)
        {if(nums[i]!=nums[j])nums[++j]=nums[i];}
        vector<int> num;
        num.assign(nums.begin(),nums.begin()+j+1);
        if((int)num.size()>1 && num[j]==num[0]){num.pop_back();}
        int right = num.size();
        int left = 0;
        while(left<right)
        {
            int mid = left + (right-left)/2;
            if(num[mid]==target){return true;}
            else if (num[mid]>target)
            {
                if(target>=num[0] || num[mid]<num[0]){right = mid;}
                else{left=mid+1;}
            }
            else
            {
                if(num[mid]>=num[0] ||target<num[0]){left=mid+1;}
                else{right=mid;}
            }
        }
        return false;        
    }
};

88. 合并两个有序数组

class Solution {
public:
    void merge(vector<int>& arr1, int m, vector<int>& arr2, int n) {
	//int len1 = arr1.size();
	//int len2 = arr2.size();
    if(m==0)
    {
        arr1.assign(arr2.begin(),arr2.end());
        return;
    }
    if(n==0) return;
	int i = m - 1;
	int j = n - 1;
	int k = m + n - 1;
	while (i>= 0 && j>= 0)
	{
		while (i>= 0 && j>=0 && arr1[i] >= arr2[j])
		{
			arr1[k--] = arr1[i--];
		}
		while (i >= 0 && j >= 0 && arr1[i] <= arr2[j])
		{
			arr1[k--] = arr2[j--];
		}

	}
    while (i>=0 )
    {
        arr1[k--] = arr1[i--];
    }
    while (j>=0)
    {
        arr1[k--] = arr2[j--];
    }
	return ;        
    }
};

91.

字符串转数字

atoi(str.c_str());

字符转数字

int(char-'0')

94. 二叉树的中序遍历

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
vector<int> res;
public:
    void dfs(TreeNode* root)
    {
        if(!root) return;

        dfs(root->left);
        res.push_back(root->val);
        dfs(root->right);
    }

    vector<int> inorderTraversal(TreeNode* root) {
        if(!root) return res;
        dfs(root);
        return res;
    }
};

95. 不一样的二叉搜索树 II

看不懂为何这么作
解法一彻底没有用到查找二叉树的性质，暴力尝试了全部可能从而形成了重复。咱们能够利用一下查找二叉树的性质。左子树的全部值小于根节点，右子树的全部值大于根节点。

因此若是求 1…n 的全部可能。

咱们只须要把 1 做为根节点，[ ] 空做为左子树，[ 2 … n ] 的全部可能做为右子树。

2 做为根节点，[ 1 ] 做为左子树，[ 3…n ] 的全部可能做为右子树。

3 做为根节点，[ 1 2 ] 的全部可能做为左子树，[ 4 … n ] 的全部可能做为右子树，而后左子树和右子树两两组合。

4 做为根节点，[ 1 2 3 ] 的全部可能做为左子树，[ 5 … n ] 的全部可能做为右子树，而后左子树和右子树两两组合。

…

n 做为根节点，[ 1… n ] 的全部可能做为左子树，[ ] 做为右子树。

至于，[ 2 … n ] 的全部可能以及 [ 4 … n ] 以及其余状况的全部可能，能够利用上边的方法，把每一个数字做为根节点，而后把全部可能的左子树和右子树组合起来便可。

若是只有一个数字，那么全部可能就是一种状况，把该数字做为一棵树。而若是是 [ ]，那就返回 null。

做者：windliang
连接：https://leetcode-cn.com/problems/unique-binary-search-trees-ii/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-2-7/
来源：力扣（LeetCode）
著做权归做者全部。商业转载请联系做者得到受权，非商业转载请注明出处。

class Solution {
public:
    vector<TreeNode*> helper(int start,int end){
        vector<TreeNode*> ret;
        if(start > end)
            ret.push_back(nullptr);
        
        for(int i=start;i<=end;i++){
            vector<TreeNode*> left = helper(start,i-1);
            vector<TreeNode*> right = helper(i+1,end);
            for(auto l : left){
                for(auto r : right){
                    TreeNode* root = new TreeNode(i);
                    root -> left = l;
                    root -> right = r;
                    ret.push_back(root);
                }
            }
        }
        return ret;
    }
    
    vector<TreeNode*> generateTrees(int n) {
        vector<TreeNode*> ret;
        if(n == 0)
            return ret;    
        ret = helper(1,n);
        return ret;
    }
};

做者：black-hole
连接：https://leetcode-cn.com/problems/unique-binary-search-trees-ii/solution/c-30xing-dai-ma-di-gui-by-black-hole/
来源：力扣（LeetCode）
著做权归做者全部。商业转载请联系做者得到受权，非商业转载请注明出处。

97. 交错字符串

能正确判断，可是超时了，由于递归的效率比较低；
对于字符串的题，使用递归都比较耗时

class Solution {
private:
int len1;
int len2;
int len3;
public:
    bool dfs(int i, int j, int k, string& s1, string &s2, string &s3)
    {
        if(i==len1 && j==len2 && k==len3) return true;   
        
        if(i<len1 && j<len2)
        {
            if(s2[j]!=s3[k]&&s1[i]==s3[k])
            {
                return dfs(i+1,j,k+1,s1,s2,s3);
            } 
            if(s1[i]!=s3[k]&&s2[j]==s3[k])
            {
                return dfs(i,j+1,k+1,s1,s2,s3);
            }
            if(s1[i]==s3[k]&&s2[j]==s3[k])
            {
                return dfs(i+1,j,k+1,s1,s2,s3)||dfs(i,j+1,k+1,s1,s2,s3);
            }
            if(s1[i]!=s3[k]&&s2[j]!=s3[k])
            {
                return false;
            }
        }
        if(i==len1 && j<len2)
        {
            if(s2[j]==s3[k]) return dfs(i,j+1,k+1,s1,s2,s3);
            else{return false;}
        }
        if(i<len1 && j==len2)
        {
            if(s1[i]==s3[k]) return dfs(i+1,j,k+1,s1,s2,s3);
            else{return false;}
        }
        

    }

    bool isInterleave(string s1, string s2, string s3) {
        len1 = s1.size();
        len2 = s2.size();
        len3 = s3.size();
        if(len1+len2 != len3) return false;
        if(s1.empty()&&s2.empty()&&s3.empty()) return true;
        return dfs(0,0,0,s1,s2,s3);
    }
};

98. 验证二叉搜索树（dfs）

写了一堆不正确的代码，四层递归

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    
    //用来遍历，得到全部节点下的值
    void dfs1(TreeNode* root, vector<int>& res)
    {
        if(!root) return;
        res.push_back(root->val);
        dfs1(root->left,res);
        dfs1(root->right,res);
    }


    //用来判断每一个节点做为根节点时候是否符合标准
    bool dfs2(TreeNode* root, vector<int> r1, vector<int> r2)
    {
        if(r1.empty() && r2.empty()) return true;
        if(!r1.empty() && r2.empty())
        {
            for(auto i:r1)
            {
                if(i>=root->val)return false;
            }
        }
        if(r1.empty() && !r2.empty())
        {
            for(auto i:r2)
            {
                if(i<=root->val)return false;
            }
        }
        for(auto i:r1)
        {
            if(i>=root->val)return false;
        }
        for(auto i:r2)
        {
            if(i<=root->val)return false;
        }
        return true;
    }

    //对每个进行判断
    bool df3(TreeNode* root)
    {
        vector<int> left;
        dfs1(root->left,left);
        vector<int> right;
        dfs1(root->right,right);
        return dfs2(root,left,right);        
    }
    //遍历并返回判断结果
    void df4(TreeNode* root, bool& flag)
    {
        if(!root) return;
        
        if(!df3(root)) flag = false;
        isValidBST(root->left);
        isValidBST(root->right);        
    }
    bool isValidBST(TreeNode* root) {
        if(!root) return true;
        
        bool flag=true;
        df4(root,flag);
        if(flag==true)return true;
        return false;

    }
};

以前的思路是判断两百边的数组，可是得到数组就须要进行遍历，十分麻烦，下面的解法目的不是求节点是否在左右节点数组的中间，而是每一个节点和一个区间进行比较，这个区间一开始是无限大，每通过一个节点就将区间范围缩小，往左节点走时父节点做为有边界，往右边界走时父节点做为左边界，这样能够不断的将父节点的区间范围传递下去，十分巧妙
思路：引入上下边界

对于树的每一个节点 val ，设其上下边界 low , high。(用 long 防止 INT_MAX 溢出 )
判断根结点时，须知足 low < val < high ，不然返回 false
判断左节点时，仅上界变化 ( 新上界为 high 与 val 较小值。又因 val 必小于 high，故新上界为 val )
判断右节点时，仅下界变化 ( 同理，新下界为 val )

做者：penn-10
连接：https://leetcode-cn.com/problems/validate-binary-search-tree/solution/cyu-yan-yan-zheng-er-cha-sou-suo-shu-by-penn-10/
来源：力扣（LeetCode）
著做权归做者全部。商业转载请联系做者得到受权，非商业转载请注明出处。

bool fun(struct TreeNode* root, long low, long high) {
    if (root == NULL) return true;
    long num = root->val;
    if (num <= low || num >= high) return false;
    return fun(root->left, low, num) && fun(root->right, num, high);
}
bool isValidBST(struct TreeNode* root){
    return fun(root, LONG_MIN, LONG_MAX);
}

做者：penn-10
连接：https://leetcode-cn.com/problems/validate-binary-search-tree/solution/cyu-yan-yan-zheng-er-cha-sou-suo-shu-by-penn-10/
来源：力扣（LeetCode）
著做权归做者全部。商业转载请联系做者得到受权，非商业转载请注明出处。

100. 相同的树

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        //一种适用性很强的办法，都通过层序遍历，比较最后的结果，但这确定不是最优解法
        if(p==NULL && q==NULL)return true;
        if(p==NULL && q!= NULL)return false;
        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);
    }
};

101. 对称二叉树

易错点时三个条件不能少，并且注意对称时左节点的左孩子和右节点的右孩子相比

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool dfs(TreeNode* root1, TreeNode* root2)
    {   
        if(root1==NULL && root2==NULL){return true;}
        if(root1==NULL && root2!=NULL){return false;}
        if(root1!=NULL && root2==NULL){return false;}
        if(root1->val!=root2->val){return false;}
        
        return dfs(root1->left,root2->right) && dfs(root1->right,root2->left);
    }
    
    bool isSymmetric(TreeNode* root) {
        if(root==NULL){return true;}
        return dfs(root->left,root->right);

    }
};

102. 二叉树的层序遍历

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
private:
vector<vector<int> > res;
public:
    void dfs(vector<TreeNode*> cur)
    {
        if(cur.size()==0){return;}
        vector<int> temp;
        vector<TreeNode*> next;
        for(auto i:cur)
        {
            temp.push_back(i->val);
            if(i->left!=NULL){next.push_back(i->left);}
            if(i->right!=NULL){next.push_back(i->right);}
        }
        res.push_back(temp);
        dfs(next);

    }
    vector<vector<int>> levelOrder(TreeNode* root) {
        if(root==NULL){return res;}
        vector<TreeNode*> cur;
        cur.push_back(root);
        dfs(cur);
        return res;
    }
};

使用队列的方法

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> res;
        vector<int> level;
        if(root == nullptr) return res;
        queue<TreeNode*> que;
        que.push(root);
        que.push(nullptr);
        TreeNode *cur = nullptr;
        while(que.size()){
            cur = que.front();
            que.pop();
            if(cur){
                level.push_back(cur->val);
                if(cur->left) que.push(cur->left);
                if(cur->right) que.push(cur->right);
            }else{
                res.push_back(level);
                level.resize(0);
                if(que.size() > 0) que.push(nullptr);
            }
        }
        return res;
    }
};

103. 二叉树的锯齿形层次遍历

印象中是使用堆栈的，可是直接用一个bool量来标记也很方便
还能够正常层序遍历，而后隔一个倒叙一下就能够，和1007同样，都是遍历以后对数组作处理

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
private:
vector<vector<int> > res;
bool flag;
public:
    void dfs(vector<TreeNode*> cur)
    {
        if(cur.size()==0){return;}
        vector<TreeNode*> next;
        vector<int> temp;
        for(auto i:cur)
        {
            if(i->left!=NULL){next.push_back(i->left);}
            if(i->right!=NULL){next.push_back(i->right);}
            temp.push_back(i->val);
        }
        if(!flag){reverse(temp.begin(),temp.end());}
        flag = !flag;
        res.push_back(temp);
        dfs(next);
    }
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        if(root==NULL){return res;}
        vector<TreeNode*> temp;
        temp.push_back(root);
        flag = 1;
        dfs(temp);
        return res;
    }
};

104. 二叉树的最大深度(***********)

有一种很简单的写法，不少处会用到

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(root==NULL)return 0;
        return max(  maxDepth( root->left) , maxDepth( root->right)  )+1;
    }
};

通常最终值放到private处定义，中间每次须要用到的参量放入递归的参数列表

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
private:

int max;
public:
    void dfs(TreeNode* root, int num)
    {
        if(root->left==NULL&&root->right==NULL){return;}
        
        if(root->left!=NULL)
        {
            num++;
            if(max<num){max=num;}
            dfs(root->left,num);
            num--;
        }
        if(root->right!=NULL)
        {
            num++;
            if(max<num){max=num;}
            dfs(root->right,num);
            num--;
        }

    }
    int maxDepth(TreeNode* root) {
        max=0;
        if(root==NULL){return max;}       
        max=1;
        dfs(root,1);
        return max;
    }
};

105. 从前序与中序遍历序列构造二叉树

主要问题是代码写的太复杂了，可是思路是正确的，这里的递归函数须要设置成返回节点型，注意这种的最后仍是要吧头节点返回来，否则第一个递归函数就没有返回值了

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
private:
    
public:
    TreeNode* dfs(vector<int>& preorder, vector<int>& inorder)
    {
        if(preorder.size()==0){return NULL;}
        if(preorder.size()==1)
        {
            TreeNode* temp = new TreeNode(preorder[0]);
            return temp;
        }
        int mid = find(inorder.begin(),inorder.end(),preorder[0])-inorder.begin();
        TreeNode* root= new TreeNode(preorder[0]);

        vector<int> p1(preorder.begin()+1,preorder.begin()+ mid+1);
        vector<int> q1(inorder.begin() ,inorder.begin()+ mid);
        root->left = dfs(p1,q1);
        
        vector<int> p2(preorder.begin()+mid+1, preorder.end());
        vector<int> q2(inorder.begin()+mid+1 ,inorder.end());        
        root->right =dfs(p2,q2);

        return root;
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        
        if(preorder.size()==0){return NULL;}
        TreeNode* root = dfs(preorder,inorder);
        return root;
    }
};

在递归的过程当中传递了不少参数，代码量减小

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int pos = 0;
        return buildTree(preorder, pos, inorder, 0, inorder.size()-1);
    }

    TreeNode* buildTree(vector<int>& preorder, int& pos, vector<int>& inorder, int left, int right) {
        if (pos >= preorder.size()) return 0;
        int i = left;
        for (i = left; i <= right; ++i) {
            if (inorder[i] == preorder[pos]) break;
        }
        TreeNode* node = new TreeNode(preorder[pos]);
        if (left <= i-1) node->left = buildTree(preorder, ++pos, inorder, left, i-1);  // 左子树
        if (i+1 <= right) node->right = buildTree(preorder, ++pos, inorder, i + 1, right);  // 右子树
        return node;
    }
};

做者：yuexiwen
连接：https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/solution/c-fen-zhi-by-yuexiwen/
来源：力扣（LeetCode）
著做权归做者全部。商业转载请联系做者得到受权，非商业转载请注明出处。

106. 从中序与后序遍历序列构造二叉树

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* dfs(vector<int>& inorder,vector<int>& postorder)
    {
        if(inorder.size()==0){return NULL;}
        if(inorder.size()==1)
        {
            TreeNode* temp = new TreeNode(inorder[0]);
            return temp;
        }

        int mid = find(inorder.begin(), inorder.end(), postorder[postorder.size()-1] )- inorder.begin();
        TreeNode* root = new TreeNode(inorder[mid]);
        vector<int> l1(inorder.begin(), inorder.begin()+mid);
        vector<int> l2(postorder.begin(), postorder.begin()+mid);
        root->left = dfs(l1, l2);
        vector<int> r1(inorder.begin()+mid+1, inorder.end());
        vector<int> r2(postorder.begin()+mid, postorder.end()-1);
        root->right = dfs(r1,r2);
        return root;
    }

    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        if(postorder.size()==0){return NULL;}
        TreeNode* root =  dfs(inorder,postorder);
        return root;
    }
};

107. 二叉树的层次遍历 II

彻底能够从上到下遍历，而后拿一个堆栈存放，或者直接返回reverse的结果？！不是更简单，看来在使用堆栈的倒叙功能时，用reverse可能更方便

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
private:
stack<vector<int>> res;
public:
    void dfs(vector<TreeNode*> cur)
    {
        if(cur.size()==0){return;}

        vector<int> temp;
        vector<TreeNode*> next;
        for(auto i:cur)
        {
            if(i->left!=NULL){next.push_back(i->left);}
            if(i->right!=NULL){next.push_back(i->right);}
            temp.push_back(i->val);
        }
        res.push(temp);
        dfs(next);
    }
    
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        
        vector<TreeNode*> temp;
        temp.push_back(root);
        vector<vector<int>> r;
        if(root==NULL){return r;}
        dfs(temp);
        while(!res.empty())
        {
            r.push_back(res.top());
            res.pop();
        }
        return r;
    }
};

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

dfs方法

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


做者：dai-52
连接：https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree/solution/cdi-gui-jie-fa-by-dai-52-2/
来源：力扣（LeetCode）
著做权归做者全部。商业转载请联系做者得到受权，非商业转载请注明出处。

109. 有序链表转换二叉搜索树

转成数组是一种方法，另一种是使用快慢指针，把中间的找出来，这部分放到dfs最开始的地方

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* dfs(vector<int>& nums, int left, int right)
    {
        if(left>right) return NULL;
        int mid = left+(right-left)/2;
        auto root = new TreeNode(nums[mid]);
        root->left = dfs(nums,left,mid-1);
        root->right = dfs(nums,mid+1,right);
        return root;

    }
    TreeNode* sortedListToBST(ListNode* head) {
        //其实跟上一题区别不大，只是数组换成了链表，能够把链表转换成数组，而后和上题同样
        vector<int> v;
        while(head){v.push_back(head->val);head=head->next;}
        int len = v.size();
        return dfs(v,0,len-1);
    }
};

110. 平衡二叉树

有考虑的方法是写一个这个节点下面深度的函数，而后递归每个节点的左右节点进行判断，可是以前求最大深度的代码就写的很复杂
下面这个求深度的代码十分简单，不用进行num的维护每次返回值加1就能够了，代笔层数，这道题双递归函数十分巧妙
三个条件放再一块儿判断会更简便，不过传入单个节点会稍微比较难理解，为何到了叶节点就返回true了

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isBalanced(TreeNode* root) {
        if(!root) return true;
        
        int d = abs(depth(root->left)-depth(root->right)); //当前节点的左右子树的高度差
        
        return (d<=1) && (isBalanced(root->left)) && (isBalanced(root->right));
    }
    
    // 求解二叉树深度（104题）
    int depth(TreeNode* node)
    {
        if(node ==NULL) return 0;
        return max( depth(node->left), depth(node->right) )+1;
    }
    
};

做者：fly_sky
连接：https://leetcode-cn.com/problems/balanced-binary-tree/solution/c-ban-ben-dai-ma-jian-ji-by-fly_sky/
来源：力扣（LeetCode）
著做权归做者全部。商业转载请联系做者得到受权，非商业转载请注明出处。

111. 二叉树的最小深度

形式基本上是仿照最大深度来的，可是有一点不同，要注意对最小深度的定义，不是出现null就行，而是必须出现叶节点，即自己存在可是左右孩子不存在的，这是惟一的状况，因为root可能会存在左右孩子为null的状况，因此不能将左右孩子直接输入，而是将根节点输入。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int minnn(TreeNode* root)
    {
        if(!root->left && !root->right){return 0;}
        if(root->left && !root->right){return minnn(root->left)+1;}
        if(!root->left && root->right){return minnn(root->right)+1;}
        return min(minnn(root->left),minnn(root->right))+1;
    }
    int minDepth(TreeNode* root) {
        if(!root){return 0;}
        return minnn(root)+1;
    }
};

112. 路径总和

要注意几点：
1.当根节点为空，其路径和不存在而不是为空，0和空在这里是不同的，以前这个地方就错过
2.这题的终止条件是到叶节点，因此终结条件（正+负）必须是关于叶节点的
3.不管是最大最小仍是其余，逻辑关系都体如今dfs的返回方式的逻辑关系上
4.sum这种变化的值能够做为参数

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool dfs(TreeNode* root, int sum)
    {
        if(!root->left && !root->right)
        { 
            if(root->val==sum)return true;
            return false;
        }
        if(!root->left && root->right)return dfs(root->right,sum-root->val);
        if(!root->right && root->left)return dfs(root->left,sum-root->val);
        return dfs(root->left,sum-root->val) || dfs(root->right,sum-root->val);
        
    }
    bool hasPathSum(TreeNode* root, int sum) {
        if(!root)return false;
        return dfs(root,sum);
    }
};

113. 路径总和 II

难点是如何应对何时存节点，何时放节点的问题，这个能够根据例子倒推一下

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
private:
vector<vector<int>> res;
vector<int> path;
public:
    void dfs(TreeNode* root,int sum)
    {
        
        if(!root->left && !root->right)
        {
            path.push_back(root->val);
            if(root->val==sum) res.push_back(path);
            path.pop_back();
            return;
        }
        if(root->left)
        {
            path.push_back(root->val);
            dfs(root->left,sum-root->val);
            path.pop_back();
        }
        if(root->right)
        {
            path.push_back(root->val);
            dfs(root->right,sum-root->val);
            path.pop_back();
        }
        
    }
    vector<vector<int>> pathSum(TreeNode* root, int sum) {
        if(!root)return res;
        dfs(root,sum);
        return res;
    }
};

114. 二叉树展开为链表

先先序遍历展开为一列，而后变成链表，先序遍历的代码时固定的，就像求最大深度那样要记住

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
private:
vector<int> list;
public:
    //先序遍历
    void dfs(TreeNode* root)
    {
        if(!root ) return ;
        list.push_back(root->val);
        dfs(root->left);
        dfs(root->right);
    }
    
    void dfs2(TreeNode* root,int pos, vector<int> list)
    {
        if(pos==list.size()) return;
        TreeNode* temp = new TreeNode(list[pos]);
        root->left = NULL;
        root->right = temp;
        dfs2(temp,pos+1,list);
    }    
    void flatten(TreeNode* root) {
        //作一下层序遍历，求出数组，而后都放到右孩子上
        if(!root)return;
        dfs(root);
        dfs2(root,1,list);
        return;


    }
};

115. 不一样的子序列

关于字符串的题使用递归由超时了，可是思路应该时对的：把t中的每一个字符在s中的位置求出来并组成一个二维数组，里面存放每一个t中字符的位置，而后对这个dfs递归计数，在值小于前一个个时须要进行剪枝，这个递归和求全部根节点到子节点时的模板很是像

class Solution {

public:
    void dfs(int& num,vector<int>& path, int pos, vector<vector<int>>& board)
    {
        if(path.size()==board.size())
        {
            num++;
            return;
        }

        for(int i:board[pos])
        {
            if( pos==0 || (pos>0 && i>path[path.size()-1])  )
            {
                path.push_back(i);
                dfs(num,path,pos+1,board);
                path.pop_back();
            }
        }
    }
    
    int numDistinct(string s, string t) {
        if(s.empty())return 0;
        int lens = s.size();
        int lent = t.size();
        vector<vector<int>> board;
        for(int i = 0 ; i<lent ; i++)
        {
            vector<int> temp;
            for(int j = 0; j<lens ; j++)
            {
                if(s[j]==t[i])
                {
                    temp.push_back(j);
                }

            }
            board.push_back(temp);
        }
        int num = 0;
        vector<int> path;
        int pos = 0;
        dfs(num,path,pos,board);
        return num;

    }
};

116. 填充每一个节点的下一个右侧节点指针(bfs)

dfs是深度优先遍历，有前序中序后序，参数为根节点；bfs是广度优先遍历，没有什么序之说，在遍历是后习惯用一个数组存放每一层的全部节点或者节点值，参数为数组
一般bfs用非递归队列比较多，可是用递归也能够较好的解决一些问题，自由的对结果进行调整，可是队列很差拿出来

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;

    Node() : val(0), left(NULL), right(NULL), next(NULL) {}

    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

    Node(int _val, Node* _left, Node* _right, Node* _next)
        : val(_val), left(_left), right(_right), next(_next) {}
};
*/
class Solution {
vector<vector<Node*>> res;
public:
    void bfs(vector<Node*> cur)
    {
        if(cur.empty())return;
        vector<Node*> temp;
        for(auto i:cur)
        {
            if(i->left)temp.push_back(i->left);
            if(i->right)temp.push_back(i->right);
        }

        bfs(temp);
        res.push_back(temp);
    }

    Node* connect(Node* root) {
       if(!root) return NULL;
       vector<Node*> cur;
       cur.push_back(root);
       res.push_back(cur);
       bfs(cur);
       for(auto i : res)
       {
           if(i.size()==1){continue;}
           int m = i.size();
           for(int j = 0 ; j< m-1; j++)
           {
               i[j]->next=i[j+1];
           }
       }
        return root;
    }
};

117. 填充每一个节点的下一个右侧节点指针 II(bfs)

和116的代码一摸同样

118. 杨辉三角

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> res;
        if(numRows==0) return res;
        vector<int> t = {1};
        res.push_back(t);
        if(numRows==1) return res;
        t.push_back(1);
        res.push_back(t);
        if(numRows==2) return res;
        numRows -=2;
        vector<int> cur = {1,1};
        while(numRows--)
        {
            vector<int> temp;
            temp.push_back(1);
            int len = cur.size();
            for(int i = 0 ; i<len-1 ; i++)
            {
                temp.push_back(cur[i]+cur[i+1]);
            }
            temp.push_back(1);
            cur.assign(temp.begin(),temp.end());
            res.push_back(cur);
        }
        return res;
    }
};

119. 杨辉三角 II

class Solution {
public:
    vector<int> getRow(int numRows) {
        vector<int> t = {1};
        if(numRows==0) return t;
        t.push_back(1);
        if(numRows==1) return t;
        numRows -=1;
        vector<int> cur = {1,1};
        while(numRows--)
        {
            vector<int> temp;
            temp.push_back(1);
            int len = cur.size();
            for(int i = 0 ; i<len-1 ; i++)
            {
                temp.push_back(cur[i]+cur[i+1]);
            }
            temp.push_back(1);
            cur.assign(temp.begin(),temp.end());
        }
        return cur;        
    }
};

额外的空间也能够不使用，可是要修改原数据，不太好，因此就用了额外的 n*sizeof(int)的空间。
line用于记录n层到n-1层最短的路径长度，其初始值为triangle的第n行。其递归公式为：

line[j] = triangle[i][j] + min(line[j], line[j + 1])，i 表示当前自下向上到达第 i 层。
line[j]=triangle[i][j]+min(line[j],line[j+1])，i表示当前自下向上到达第i层。

做者：liushang-leecode
连接：https://leetcode-cn.com/problems/triangle/solution/dong-tai-gui-hua-zi-di-xiang-shang-ke-yi-shi-yong-/
来源：力扣（LeetCode）
著做权归做者全部。商业转载请联系做者得到受权，非商业转载请注明出处。

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int n = triangle.size();
        vector<int> line(triangle[n - 1]);
        for (int i = n - 2; i >= 0; i--)
            for (int j = 0; j <= i; j++)
                line[j] = triangle[i][j] + min(line[j], line[j + 1]);
        return line[0];
    }
};

做者：liushang-leecode
连接：https://leetcode-cn.com/problems/triangle/solution/dong-tai-gui-hua-zi-di-xiang-shang-ke-yi-shi-yong-/
来源：力扣（LeetCode）
著做权归做者全部。商业转载请联系做者得到受权，非商业转载请注明出处。

121. 买卖股票的最佳时机（dp）

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if(prices.empty())return 0;
        int dp=prices[0],res = 0;
        for(int i = 1; i< (int)prices.size() ;i++)
        {
            dp = min(dp,prices[i]);
            res = max(res, prices[i]-dp);
        }
        return res;
    }
};

一次遍历法，不是特别好理解

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int inf = 1e9; //很大的值
        int minprice = inf, maxprofit = 0;
        for (int price: prices) {
            maxprofit = max(maxprofit, price - minprice);
            minprice = min(price, minprice);
        }
        return maxprofit;
    }
};

做者：LeetCode-Solution
连接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/solution/121-mai-mai-gu-piao-de-zui-jia-shi-ji-by-leetcode-/
来源：力扣（LeetCode）
著做权归做者全部。商业转载请联系做者得到受权，非商业转载请注明出处。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int len = prices.size();
        if(len==0 || len==1)return 0;        
        int minvalue = prices[0];
        int maxvalue = INT_MIN;
        for(int i = 1 ; i<len ; i++)
        {
            minvalue = min(minvalue,prices[i-1]);
            maxvalue = max(maxvalue,prices[i]-minvalue);
        }
        if(maxvalue<0)return 0;
        return maxvalue;
    }
};

动态规划法

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        if (n == 0) return 0; // 边界条件
        int minprice = prices[0];
        vector<int> dp (n, 0); //新建一个数组
	//在动态变化中维护了最小值，老是能得到这个点以前的最小值
	//最后原本不用再和本身比较了，可是题目有一个特殊要求，就是不能小于0，因此再生成这个动态数组的时候，每次都要和0比较，若是小于0就不要了
        for (int i = 1; i < n; i++){
            minprice = min(minprice, prices[i]);
            dp[i] = max(dp[i - 1], prices[i] - minprice);
        }
        return dp[n - 1];
    }
};

做者：z1m
连接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/solution/gu-piao-wen-ti-python3-c-by-z1m/
来源：力扣（LeetCode）
著做权归做者全部。商业转载请联系做者得到受权，非商业转载请注明出处。

122. 买卖股票的最佳时机 II

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int res = 0;
        for(int i=1; i< (int)prices.size() ;i++)
        {
            res += (prices[i]>prices[i-1])?(prices[i]-prices[i-1]):0;
        }
        return res;
    }
};

这道题不适合动态规划，能够用贪心结合双指针作
不用非等到上升到最高点才买，只要上升一次就买一次，低了就不动

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        //快慢指针标记
        int i=0,j=1,sum=0;
        //判断vector大小
        if(prices.size()<=1)
        return 0;
        
        //两个指针一直紧挨在一块儿，只有j的值大于i的值时，就把差值加入sum中
        while(j<prices.size()){
            if(prices[j]-prices[i]>0)
                sum+=(prices[j]-prices[i]);

                i++;
                j++;
        }
        return sum;
    }
};

做者：zhong-zhong-ban-da-dui-chang
连接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/solution/ctan-xin-suan-fa-by-zhong-zhong-ban-da-dui-chang/
来源：力扣（LeetCode）
著做权归做者全部。商业转载请联系做者得到受权，非商业转载请注明出处。

123. 买卖股票的最佳时机 III

是在上一题的基础上作的，可是次数再多就不行了，并且这种双循环方式也超时了，可是思路是对的

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if(prices.empty())return 0;
        int res1 = 0, dp1 = prices[0], res = 0;
        for(int i =1 ; i< (int)prices.size() ;i++)
        {
            dp1 = min(dp1, prices[i]);
            res1 = max(res1, prices[i]-dp1);
            int dp2 = prices[i];
            int res2 = 0;
            for(int j = i+1 ; j<(int)prices.size() ;j++)
            {
                dp2 = min(dp2, prices[j]);
                res2 = max(res2, prices[j]-dp2);                
            }
            res = max(res, res1+res2);
        }
        return res;
    }
};

124. 二叉树中的最大路径和(dfs,不懂)

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    //一个 根，左，右 的路径状况有（根，左+根，根+右，左+根+右）
    //可是该根做为其父亲的孩子时，其max 应该为 max（根，左+根，根+右）.若是包含左+根+右，则加上其父亲就构不成路径了
    int maxPathSum(TreeNode* root) {
        long long gMax = LLONG_MIN;
        maxPathSumCore(root, gMax);
        return gMax;
    }

    int maxPathSumCore(TreeNode* root, long long& gMax){
        if(root==nullptr) return 0;
        int curVal = root->val;
        int leftMax = maxPathSumCore(root->left, gMax);
        int rightMax = maxPathSumCore(root->right, gMax);
        long long curMax = max(curVal, max(curVal+leftMax, max(curVal+rightMax, curVal+leftMax+rightMax)));
        if(curMax>gMax) gMax = curMax;
        return max(curVal, max(curVal+leftMax, curVal+rightMax));
    }
};

做者：lou-ding-_shai-tai-yang
连接：https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/solution/di-gui-dang-qian-jie-dian-de-zui-da-lu-jing-he-dan/
来源：力扣（LeetCode）
著做权归做者全部。商业转载请联系做者得到受权，非商业转载请注明出处。

128. 最长连续序列

很简便的作法，稍难理解

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        if(nums.empty()){
            return 0;
        }
        unordered_set<int> myset(nums.begin(), nums.end());
        int res = 0;
        
        for(auto num : nums){
            if(myset.count(num-1)==0){
                int x = num + 1;
                while(myset.count(x)){
                    x ++;
                }
                res = max(res, x-num);
            }
        }
        return res;
    }
};

做者：anyaleung
连接：https://leetcode-cn.com/problems/longest-consecutive-sequence/solution/cdai-ma-li-yong-unordered_set-by-anyaleung/
来源：力扣（LeetCode）
著做权归做者全部。商业转载请联系做者得到受权，非商业转载请注明出处。

129. 求根到叶子节点数字之和

字符串转数字

int num = 0 ;
string s = "sdfsf";
num = std::atoi(s.c_str());

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
private:
vector<string> res;
string s;
public:
    void dfs(TreeNode* root)
    {
        if(!root->left && !root->right)
        {
            s = s + to_string(root->val);
            res.push_back(s);
            s.pop_back();
        }
        if(root->left)
        {
            s = s + to_string(root->val);
            dfs(root->left);
            s.pop_back();
        }
        if(root->right)
        {
            s = s + to_string(root->val);
            dfs(root->right);
            s.pop_back();
        }


    }
    int sumNumbers(TreeNode* root) {
        if(!root)return 0;
        dfs(root);
        int sum = 0;
        for(auto i:res)
        {
            sum += atoi(i.c_str());
        }
        return sum;
    }
};

130. 被围绕的区域

本身写的递归十分的复杂，主要问题在于，在判断的过程当中就把不是本位置的元素给改了，致使路径上发生变化，看了解答，发现是思路错了，或者说这道题逆向思惟一下很是好作，就像数学选择题里面的举反例同样
被围绕的区间不会存在于边界上，换句话说，任何边界上的 ‘O’ 都不会被填充为 ‘X’。任何不在边界上，或不与边界上的 ‘O’ 相连的 ‘O’ 最终都会被填充为 ‘X’。若是两个元素在水平或垂直方向相邻，则称它们是“相连”的。

做者：ZZYuting
连接：https://leetcode-cn.com/problems/surrounded-regions/solution/cbeats-9465easy-to-understand-by-zzyuting/
来源：力扣（LeetCode）
著做权归做者全部。商业转载请联系做者得到受权，非商业转载请注明出处。

/*
First, check the four border of the matrix. If there is a element is
'O', alter it and all its nei***or 'O' elements to '1'.

Then ,alter all the 'O' to 'X'

At last,alter all the '1' to 'O'

For example:

         X X X X           X X X X             X X X X
         X X O X  ->       X X O X    ->       X X X X
         X O X X           X 1 X X             X O X X
         X O X X           X 1 X X             X O X X
*/
class Solution {
public:
    void solve(vector<vector<char>>& board) {
        if(board.size()==0){
            return;
        }
        int rows=board.size(),cols=board[0].size();
        //对边界上的进行dfs
        for(int i=0;i<rows;i++){
            dfs(board,i,0);
            dfs(board,i,cols-1);
        }
        for(int j=1;j<cols-1;j++){
            dfs(board,0,j);
            dfs(board,rows-1,j);
        }
        //遍历所有的，1变0，其余为X，很巧妙的先把这些量都标出来来了
        for(int i=0;i<rows;i++){
            for(int j=0;j<cols;j++){
                if(board[i][j]=='1'){
                    board[i][j]='O';
                }
                else{
                    board[i][j]='X';
                }
            }
        }
    }
private:
    void dfs(vector<vector<char>>& board,int i,int j){
    	//若是既不在边界上并且又为X的直接跳过，当此边界上的点为0时才有动做
    	//若是在边界上为O，就直接改为1
        if(i>=0&&i<board.size()&&j>=0&&j<board[0].size()&&board[i][j]=='O'){
            board[i][j]='1';
            dfs(board,i-1,j);
            dfs(board,i+1,j);
            dfs(board,i,j-1);
            dfs(board,i,j+1);
        }
    }
};

做者：ZZYuting
连接：https://leetcode-cn.com/problems/surrounded-regions/solution/cbeats-9465easy-to-understand-by-zzyuting/
来源：力扣（LeetCode）
著做权归做者全部。商业转载请联系做者得到受权，非商业转载请注明出处。

在这里插入代码片

144. 二叉树的前序遍历

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
private:
vector<int> res;
public:
    void dfs(TreeNode* root)
    {
        if(root==NULL)return;
        res.push_back(root->val);
        dfs(root->left);
        dfs(root->right);
    }
    vector<int> preorderTraversal(TreeNode* root) {
        dfs(root);
        return res;
    }
};

146. LRU缓存机制

使用哈希map和双链表：
逻辑

// key 映射到 Node(key, val)
HashMap<Integer, Node> map;
// Node(k1, v1) <-> Node(k2, v2)...
DoubleList cache;

int get(int key) {
    if (key 不存在) {
        return -1;
    } else {        
        将数据 (key, val) 提到开头；
        return val;
    }
}

void put(int key, int val) {
    Node x = new Node(key, val);
    if (key 已存在) {
        把旧的数据删除；
        将新节点 x 插入到开头；
    } else {
        if (cache 已满) {
            删除链表的最后一个数据腾位置；
            删除 map 中映射到该数据的键；
        } 
        将新节点 x 插入到开头；
        map 中新建 key 对新节点 x 的映射；
    }
}

较简化的版本

class LRUCache {
public:
    //删除、查找、插入的复杂度都O（1）
    LRUCache(int capacity) {
        cap=capacity;
    } 
    int get(int key) {
        if(hashtable.count(key)==0) return -1;
        else//更新到表头
        {
            auto iter = hashtable[key];//找到对应结点地址
            cache.splice(cache.begin(),cache,iter);//移动到链表头
            return cache.begin()->second;//返回value
        }
    }
    
    void put(int key, int value) {
        if(hashtable.count(key)==0) {
            //若是容量到了，删除尾部元素,再加上新结点
            if(cache.size()==cap)   {
                hashtable.erase(cache.back().first);
                cache.pop_back();
            }//直接添加
            cache.push_front(make_pair(key,value));
            hashtable[key]=cache.begin(); 
        }
        else {//若是插入相同key的元素，除了要移动，value也须要更新
            auto iter = hashtable[key];
            iter->second=value;//更新地址value
            cache.splice(cache.begin(),cache,iter);//移动到链表头
            hashtable[key]=cache.begin();   //更新hashtable的value
        }
    }
    unordered_map<int,list<pair<int,int>>::iterator> hashtable;
    list<pair<int,int>> cache;//key value
    int cap=0;
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */

做者：tong-guai
连接：https://leetcode-cn.com/problems/lru-cache/solution/ha-xi-shuang-xiang-lian-biao-you-hua-ban-ben-by-to/
来源：力扣（LeetCode）
著做权归做者全部。商业转载请联系做者得到受权，非商业转载请注明出处。

class LRUCache {
public:
    LRUCache(int capacity) {
        _capacity = capacity;
    }
    
    int get(int key) {
        if(_map.count(key) != 0)
        {
            int ret = (*_map[key]).second;
            _list.erase(_map[key]);
            _list.push_front({key, ret});
            _map[key] = _list.begin();
            return ret;
        }
        else return -1;
    }
    
    void put(int key, int value) {
        if(_map.count(key) == 0)
        {
            if(_list.size() == _capacity)
            {
                int k = _list.back().first;
                _map.erase(_map.find(k));
                _list.pop_back();
            }
        }
        else{
            _list.erase(_map[key]);
            _map.erase(_map.find(key));
        }
        _list.push_front({key, value});
        _map[key] = _list.begin();
    }

private:
    unordered_map<int, list<pair<int, int>>::iterator> _map;
    list<pair<int, int>> _list;
    int _capacity;
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */

做者：ma-te-zai-wei-ma
连接：https://leetcode-cn.com/problems/lru-cache/solution/lruhuan-cun-ji-zhi-by-ma-te-zai-wei-ma/
来源：力扣（LeetCode）
著做权归做者全部。商业转载请联系做者得到受权，非商业转载请注明出处。

150. 逆波兰表达式求值

用bool判断第一个符号而且用一个值储存结果是很麻烦的事，不如就一直将结果放在堆栈中

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<string> st;
        //bool flag = true;第一次遇到的符号须要特殊处理，用flag来表示是不是第一个
        for(auto token:tokens)
        {
            if(token=="+")
            {
                int t1 =atoi(st.top().c_str());
                st.pop();
                int t2 = atoi(st.top().c_str());
                st.pop();
                st.push(to_string(t1+t2));
            }
            else if(token=="-")
            {
                int t1 =atoi(st.top().c_str());
                st.pop();
                int t2 = atoi(st.top().c_str());
                st.pop();
                st.push(to_string(t2-t1));
            }
            else if(token=="*")
            {
                int t1 =atoi(st.top().c_str());
                st.pop();
                int t2 = atoi(st.top().c_str());
                st.pop();
                st.push(to_string(t1*t2));
            }
            else if(token=="/")
            {
                int t1 =atoi(st.top().c_str());
                st.pop();
                int t2 = atoi(st.top().c_str());
                st.pop();
                st.push(to_string(t2/t1));
            }
            else
            {
                st.push(token);
            }
        } 
        return atoi(st.top().c_str());
    }
};

152. 乘积最大子数组(dp)

解题思路
这题是求数组中子区间的最大乘积，对于乘法，咱们须要注意，负数乘以负数，会变成正数，因此解这题的时候咱们须要维护两个变量，当前的最大值，以及最小值，最小值可能为负数，但没准下一步乘以一个负数，当前的最大值就变成最小值，而最小值则变成最大值了。

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int res = INT_MIN , imax = 1, imin =1;
        for(int i = 0 ; i< (int)nums.size() ;i++)
        {
            if(nums[i]<0)swap(imax,imin);
            imax = max(nums[i],imax*nums[i]);
            imin = min (nums[i],imin*nums[i]);
            res = max(res,imax);
        }
        return res;
    }
};

153. 寻找旋转排序数组中的最小值

class Solution {
public:
    int findMin(vector<int>& nums) {
        if(nums[0]<=nums.back())return nums[0];
        int left = 0 , right = nums.size();
        while(left<right)
        {
            int mid = left+(right-left)/2;
            if(nums[mid]>=nums[0])
            {left=mid+1;}
            else
            {right=mid;}
        }
        return nums[left];
    }
};

155. 最小栈

使用两个队列,可是会超时

class MinStack {
private:
queue<int> q1;
queue<int> q2;
public:
    /** initialize your data structure here. */
    MinStack() {
        
    }
    
    void push(int x) {
        if(q1.empty()&&q2.empty())q1.push(x);
        else if(q1.empty())q2.push(x);
        else if(q2.empty())q1.push(x);
    }
    
    void pop() {
        if(q1.empty())
        {
            while(q2.size()>1)
            {
                q1.push(q2.front());
                q2.pop();
            }
            q2.pop();
        }
        else
        {
            while(q1.size()>1)
            {
                q2.push(q1.front());
                q1.pop();
            }
            q1.pop();
        }
    }
    
    int top() {
        int res;
        if(q1.empty())
        {
            while(q2.size()>1)
            {
                q1.push(q2.front());
                q2.pop();
            }
            res = q2.front();
            q1.push(q2.front());
            q2.pop();

        }
        else
        {
            while(q1.size()>1)
            {
                q2.push(q1.front());
                q1.pop();
            }
            res = q1.front();
            q2.push(q1.front());
            q1.pop();            
        }
        return res;
    }
    
    int getMin() {
        int res = INT_MAX;
        if(q1.empty())
        {
            while(!q2.empty())
            {
                res = min(res, q2.front());
                q1.push(q2.front());
                q2.pop();
            }
        }
        else
        {
            while(!q1.empty())
            {
                res = min(res,q1.front());
                q2.push(q1.front());
                q1.pop();
            }
        }        
        return res;
    }
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(x);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->getMin();
 */

一个栈s存放数据，另外一个栈min存放前栈中最小的数据

class MinStack {
public:
    stack<int> s;//数据栈
    stack<int> min;//辅助栈
    /** initialize your data structure here. */
    MinStack() {
        
    }
    
    void push(int x) {
        s.push(x);
        if(min.empty()||x<=min.top())
        {
            min.push(x);
        }
    }
    
    void pop() {
        if(s.top()==min.top())
            min.pop();
        s.pop();
    }
    
    int top() {
        return s.top();
    }
    int getMin() {
        return min.top();
    }
};

做者：chenlele
连接：https://leetcode-cn.com/problems/min-stack/solution/zui-xiao-zhan-by-gpe3dbjds1/
来源：力扣（LeetCode）
著做权归做者全部。商业转载请联系做者得到受权，非商业转载请注明出处。

162. 寻找峰值

直接作是不符合要求的，看到logN应该直接想到使用二分法

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int len =nums.size();
        if(len==0 || len ==1) return 0;
        if(len==2)
        {
            int i = nums[0]>nums[1]? 0:1;
            return i;
        } 
        for(int i = 1 ; i<len-1 ;i++)
        {
            if(nums[i]>nums[i-1] && nums[i]>nums[i+1]) return i;
        }
        if(nums[0]>nums[1])return 0;
        if(nums[len-1]>nums[len-2])return len-1;
        return INT_MIN;

    }
};

以前作过一道两数之和的，因此在这里面使用了查找法，凡是查找须要遍历，因此这样作会超时，更好的办法是双指针一个在前一个在后，这里双指针法更好的缘由是数组已经排序好了，，能够有规律的缩小双指针的范围

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int len = numbers.size();
        for(int i = 0 ;i<len ;i++)
        {
            auto iter = find(numbers.begin()+i+1,numbers.end(), target- numbers[i]); 
            if( iter!=numbers.end())
            {
                int temp = iter-numbers.begin();
                vector<int> res={i+1,temp+1};
                return res;
            }
        }
        return {};
    }
};

169. 多数元素

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int len = nums.size();
        if(len==1) return nums[0];
        sort(nums.begin(),nums.end());
        return nums[len/2];
    }
};

179. 最大数

一开始想的是把全部数字都变成数组的形式，而后使用sort进行排序，可是会有一个问题，30和3进行比较的话确定会认为30大而且在前，可是最后303显然没有330大，因此这种方法是有问题的

题目解析：根据题目中给的例子来看，主要就是要给给定数组进行排序，可是排序方法不是普通的升序或者降序，由于9要排在最前面，而9既不是数组中最大的也不是最小的，因此咱们要自定义排序方法。对于两个数字a和b来讲，若是将其都转为字符串，若是ab > ba，则a排在前面，好比9和34，因为934>349，因此9排在前面，再好比说30和3，因为303<330，因此3排在30的前面。按照这种规则对原数组进行排序后，将每一个数字转化为字符串再链接起来就是最终结果。
————————————————
版权声明：本文为CSDN博主「pushup8」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处连接及本声明。
原文连接：https://blog.csdn.net/pushup8/article/details/85196465

class Solution {
public:
    string largestNumber(vector<int>& nums) {
        string res = "";
        sort(nums.begin(), nums.end(), [](int a, int b){
            return to_string(a) + to_string(b) > to_string(b) + to_string(a);
        });
        for(auto num : nums){
            res += to_string(num); 
        }
        return res[0] == '0' ? "0" : res;
    }
};

本身写的
注意sort函数重写的四个要素1.static2.inline3.const4.&

class Solution {
public:
    static inline bool func(const string& a, const string& b)
    {
        return a+b>b+a;
    }
    string largestNumber(vector<int>& nums) {
        vector<string> st;
        //st.assign(nums.begin(),nums.end());
        for(auto i:nums)st.push_back(to_string(i));
        sort(st.begin(),st.end(),func);
        string res;
        for(auto i:st)res += i;
        while( (int)res.size()>1 && res[0]=='0')res = res.substr(1,(int)res.size()-1);
        return res;
    }
};

189. 旋转数组

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int len = nums.size();
        reverse(nums.begin(),nums.end