题

剑指 Offer II 060. 出现频率最高的 k 个数字

多数元素，n/3,转换成该题k=2

class Solution {
public:
    static bool cmp(pair<int, int>& m, pair<int, int>& n) {
        return m.second > n.second;
    }
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> occurrences;
        for (auto& v : nums) {
            occurrences[v]++;
        }
        // pair 的第一个元素代表数组的值，第二个元素代表了该值出现的次数
        priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(&cmp)> q(cmp);
        for (auto& [num, count] : occurrences) {
            if (q.size() == k) {
                if (q.top().second < count) {
                    q.pop();
                    q.emplace(num, count);
                }
            } else {
                q.emplace(num, count);
            }
        }
        vector<int> ret;
        while (!q.empty()) {
            ret.emplace_back(q.top().first);
            q.pop();
        }
        return ret;
    }
};

210. 课程表 II

class Solution {
public:
    vector<int> findOrder(int n, vector<vector<int>>& edges) {
        vector<vector<int>> g(n);
        vector<int> d(n);
        for (auto& e: edges) {
            int b = e[0], a = e[1];
            g[a].push_back(b);
            d[b] ++ ;
        }
        queue<int> q;
        for (int i = 0; i < n; i ++ )
            if (d[i] == 0)
                q.push(i);

        vector<int> res;
        while (q.size()) {
            auto t = q.front();
            q.pop();
            res.push_back(t);
            for (int i: g[t])
                if ( -- d[i] == 0)
                    q.push(i);
        }
        if (res.size() < n) res = {};
        return res;
    }
};

362. 敲击计数器

class HitCounter {
private:
    deque<pair<int, int>> q;
    int cnt;
public:
    /** Initialize your data structure here. */
    HitCounter() {
        cnt = 0;
    }
    /** Record a hit.
        @param timestamp - The current timestamp (in seconds granularity). */
    void hit(int timestamp) {
        if (!q.empty() && q.back().first == timestamp) q.back().second++;
        else q.push_back({timestamp, 1});
        cnt ++;
    }
    /** Return the number of hits in the past 5 minutes.
        @param timestamp - The current timestamp (in seconds granularity). */
    int getHits(int timestamp) {
        while (!q.empty() && timestamp - q.front().first + 1 > 300) {
            cnt -= q.front().second;
            q.pop_front();
        }
        return cnt;
    }
};


/**
 * Your HitCounter object will be instantiated and called as such:
 * HitCounter* obj = new HitCounter();
 * obj->hit(timestamp);
 * int param_2 = obj->getHits(timestamp);
 */

类似：平均负载
写一个类，里面有record（int t）和avarage（）两个方法。调用record可以记录下当前时间点的负载均衡数，调用avarage要返回过去5分钟内的负载均衡数的平均数。
之前以为用循环数组就好了，但是其实用链表就能够完成。
struct node{
int num;
int timestamp;
};

01串递推

第一题：一颗完全二叉树，最上面根结点的值为0，然后其余，左边为0 右边为1。问这颗二叉树中序遍历之后的：01串 如何用一个递推公式表示？

48. 旋转图像

第一步沿对角线翻转；第二步沿中轴翻转

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();
        for(int i = 0; i < n; ++ i)
            for(int j = 0; j < i; ++ j)
                swap(matrix[i][j], matrix[j][i]);

        for(int i = 0; i < n; ++ i)
            for(int j = 0, k = n - 1; j < k; ++ j, -- k)
                swap(matrix[i][j], matrix[i][k]);
            // for(int j = 0; j < n/2; ++ j)
            //     swap(matrix[i][j], matrix[i][n-1-j]);

    }
};

时间复杂度：O(n2)， 额外空间：O(1)

47. 全排列 II 有重复元素

(回溯) O(n!)
由于有重复元素的存在，这道题的枚举顺序和 Permutations 不同。

先将所有数从小到大排序，这样相同的数会排在一起；
从左到右依次枚举每个数，每次将它放在一个空位上；
对于相同数，我们人为定序，就可以避免重复计算：我们在dfs时记录一个额外的状态，记录上一个相同数存放的位置 start，我们在枚举当前数时，只枚举 start+1,start+2,…,nstart+1,start+2,…,n 这些位置。
不要忘记递归前和回溯时，对状态进行更新。
时间复杂度分析：搜索树中最后一层共 n!个节点，前面所有层加一块的节点数量相比于最后一层节点数是无穷小量，可以忽略。且最后一层节点记录方案的计算量是 O(n)，所以总时间复杂度是 O(n×n!)。
class Solution {
public:
    vector<bool> st;
    vector<int> path;
    vector<vector<int>>ans;
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        st = vector<bool>(nums.size(), false);
        path = vector<int>(nums.size());
        dfs(nums, 0, 0);
        return ans;
    }

    //记录上一个相同数存放的位置start
    //在枚举当前数时，只枚举 start+1,start+2,…,nstart+1,start+2,…,n 这些位置。
    void dfs(vector<int>& nums, int u, int start)
    {
        if(u == nums.size())
        {
            ans.push_back(path);
            return;
        }

        for(int i = start; i < nums.size(); ++ i)
        {
            if(!st[i])
            {
                st[i] = true;
                path[i] = nums[u];
                if(u+1 < nums.size() && nums[u+1] != nums[u])
                    dfs(nums, u+1, 0);
                else
                    dfs(nums, u+1, i+1);
                st[i] = false;
            }
        }

    }
};

31. 下一个排列

• 从末尾开始找第一个升序位置k
  • 如果没有：例54321，说明是已经是最大字典序排列，反转就是最小排列，即下一个排列
  • 如果存在：例23541，这里541降序，所以第一个升序是35，k = 2

从末尾到k遍历找比nums[k-1]大的第一个数nums[t] nums[3]=4
交换nums[k-1]和nums[t] 23541->24531
将nums[k+1]到末尾反转，变成升序 24531->24135

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int k = nums.size() - 1;
        while(k > 0 && nums[k-1] >= nums[k]) k --;
        if(k == 0) reverse(nums.begin(), nums.end());
        else{
            for(int t = nums.size() - 1; t >= k ; t --)
            {
                if(nums[t] > nums[k-1]) 
                {
                    swap(nums[t], nums[k-1]);
                    reverse(nums.begin()+k, nums.end());
                    break;
                }
            }
        }
    }
};

//yxc
class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int k = nums.size() - 1;
        while (k > 0 && nums[k - 1] >= nums[k]) k -- ;
        if (k <= 0) {
            reverse(nums.begin(), nums.end());
        } else {
            int t = k;
            //nums[t]是第一个小于nums[k-1]的数
            //nums[t-1]是大于nums[k-1]的最小数
            while (t < nums.size() && nums[t] > nums[k - 1]) t ++ ;
            swap(nums[t - 1], nums[k - 1]);
            reverse(nums.begin() + k, nums.end());
        }
    }
};

75. 颜色分类

1. 单指针

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

2. 三指针

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

148. 排序链表

• 空间复杂度为O(1)，用迭代的归并排序（自底向上）来做

  class Solution {
  public:
    ListNode* sortList(ListNode* head) {
        //计算链表大小n
        int n = 0; 
        for(auto p = head; p; p = p->next) n ++;
  
        //设置虚头节点，因为头节点可能在排序中改变位置，最后返回dummy->next
        auto dummy = new ListNode();
        dummy->next = head;
  
        //首先循环每层归并段的大小i，自底向上，依次1，2，4，……，n/2
        for(int i = 1; i < n; i *= 2)
        {
            auto cur = dummy;//方便每层都能索引到当前的头节点dummy->next
            //j表示每两个归并段组的开端索引，从0开始，间隔2i
            //i = 2, j = j + 2i 【（0，1）（2，3）】【（4，5）（6，7）】【（8，_）（_，_）】
            //i = 1, j = j + 2i （0，1）（2，3）（4，5）（6，7）（8，_）
            //                    j j+i j+2i
            //j的范围：保证每组有两个归并段，即第二个归并段开端索引（j+i）小于n
            for(int j = 0; j + i < n; j += 2 * i)
            {
                //cur表示上一组已排好序的尾节点
                //first表示当前组第一段起点，second表示第二段起点
                auto first = cur->next;
                auto second = first;
                for(int k = 0; k < i; k ++) second = second->next;
  
                //归并
                //f,s用于计数第一段和第二段归并的节点个数，段长度可能不足i，需要判断first, second存不存在，由于first在second前，只用考虑second是否存在
                int f = 0, s = 0;
                while(f < i && s < i && first && second)
                {
                    if(first->val <= second->val) 
                    {
                        //将更小的节点插到cur之后,也可写成cur = cur->next = first;赋值顺序由右向左
                        //first移到下一个
                        cur->next = first;
                        cur = cur->next;
                        first = first->next;
                        f ++;
                    }
                    else
                    {
                        cur->next = second;
                        cur = cur->next;
                        second = second->next;
                        s ++;
                    }
                }
                //归并排序基本套路
                while(f < i && first) cur = cur->next = first, first = first->next, f ++;//first一定存在
                while(s <  i && second) cur = cur->next = second, second = second->next, s ++;
                //跳出循环时，s = i 或 second为空；
                //当s=i,下一组的第一段开端为i，即当前的second
                //将cur置为second的前一个节点，方便下一次循环用cur->next表示第一段开端
                cur->next = second;
            }
        }
        return dummy->next;
    } 
  };
  

• 空间复杂度为O(logn)，用递归的归并排序（自顶向下）来做

  class Solution {
  public:
    ListNode* sortList(ListNode* head) {
        if(!head || !head->next) return head;
        ListNode *slow = head, *fast = head->next;
        while(fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;
        }
        fast = slow->next;
        slow->next = nullptr;
  
        ListNode* left = sortList(head);
        ListNode* right = sortList(fast);
  
        return merge(left, right);
    }
  
    ListNode* merge(ListNode* left, ListNode* right)
    {
        ListNode* dummy = new ListNode();
        ListNode* cur = dummy;
        while(left && right)
        {
            if(left->val < right->val)
            {
                cur = cur->next = left;
                left = left->next;
            }
            else
            {
                cur = cur->next = right;
                right = right->next;
            }
        }
        if(left) cur->next = left;
        else if(right) cur->next = right;
  
        return dummy->next;
    }
  };
  

  给定一个字符串数组，以及一个目标字符串 target，在这个数组中找出两个字符串，使得它们的拼接结果等于 target，问可以找出多少对这样的字符串。

  ```cpp

  include

  include

  include

  using namespace std;

vector> twoStrSum(vector& str, string& target) { vector> res; unordered_map map;//{字符，在str中的下标} for(int i = 0; i < str.size(); i ++) map[str[i]] = i; auto iter0 = map.find(target); if(iter0 != map.end()) res.push_back({iter0->second});

for(int i = 0; i < target.size()-1; i ++)
{
    auto iter1 = map.find(target.substr(0,i + 1));
    if (iter1 != map.end())
    {
       auto iter2 = map.find(target.substr(i + 1, target.size()-i-1));
       if(iter2 != map.end())
       {
           res.push_back({iter1->second, iter2->second});
       }
    }
}

return res;

}

int main() { string s; vector str; string target; cout << “input target: “ << endl; getline(cin, target);

cout << "input str: " << endl;
while(getline(cin, s))
{
    str.push_back(s);
    if(s.size() == 0) break;
}
cout << "结束输入" <<endl;

vector<vector<int>> res = twoStrSum(str, target);
for(auto r: res)
{
    for(auto i : r)
        cout << i << " ";
    cout << endl;
}

return 0;

}

<a name="SGYfa"></a>
#### [两数之和](https://programmercarl.com/0001.%E4%B8%A4%E6%95%B0%E4%B9%8B%E5%92%8C.html#%E6%80%9D%E8%B7%AF)
<a name="r7DNn"></a>
#### 汉字数字转阿拉伯数字 [题解](https://leetcode-cn.com/circle/discuss/EY0b4W/)
![image.png](https://cdn.nlark.com/yuque/0/2022/png/2664485/1648382791205-8295c845-f216-4914-9bdf-a90cc3c72a7c.png#clientId=u5f038ec3-2546-4&crop=0&crop=0&crop=1&crop=1&from=paste&height=404&id=u93365c7b&margin=%5Bobject%20Object%5D&name=image.png&originHeight=606&originWidth=846&originalType=binary&ratio=1&rotation=0&showTitle=false&size=150711&status=done&style=none&taskId=u05a10308-6b45-48e9-bd29-2de421402ec&title=&width=564)
```python
w2n = {'一': 1, '二': 2, '三': 3, '四': 4, '五': 5, '六': 6, '七': 7, '八': 8, '九': 9}
w2e = {'十': 10, '百': 100, '千': 1000, '万': 10000, '亿': 100000000}


def zh2num(zh):
    def helper(st, zh):
        if zh == '':
            return True
        elif zh[0] in w2e:
            if len(st) == 0 or st[-1] >= w2e[zh[0]]:
                return False
            tmp = 0
            while len(st) >= 1 and st[-1] < w2e[zh[0]]:
                tmp += st.pop()
            st.append(tmp * w2e[zh[0]])
            return helper(st, zh[1:])
        elif zh[0] in w2n:
            st.append(w2n[zh[0]])
            return helper(st, zh[1:])
        elif zh[0] == '零':
            return helper(st, zh[1:])
        else:
            return False

    stack_list = []
    ok = helper(stack_list, zh)
    if ok:
        res = 0
        for e in stack_list:
            res += e
        return res
    return None


if __name__ == '__main__':
    print(zh2num('二千亿零一百零一万零二百'))

贡献一个python程序，处理字符串更方便一些；
代码逻辑：

首先将表示量级和表示各位数字分别存入字典；
递归处理字符串：
如果字符串首位是数字，就压入st栈列表中储存
如果字符串首位是量级，就弹出栈列表中储存的各位数字，乘以量级
循环跳出条件是栈列表不为空，且栈顶元素小于量级
边界条件是栈列表为空或者栈顶元素大于量级，返回false
处理特殊的边界条件：首字符为零，跳过处理
递归结束条件：字符串遍历结束
st栈列表中从栈顶到栈底已经存储了量级由小到大的数，求和即为答案；
边界条件是返回为false，字符串非法，无法转为阿拉伯数字；

作者：千乘仲达
链接：https://leetcode-cn.com/circle/discuss/EY0b4W/view/Cz8W3Z/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

78. 子集

#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> res;
vector<int> sub;
void dfs(vector<int>& nums, int start)
{
    res.push_back(sub);
    for(int i = start; i < nums.size(); i ++)
    {
        sub.push_back(nums[i]);
        dfs(nums, i + 1);
        sub.pop_back();
    }
}
vector<vector<int>> subsets(vector<int>& nums) {
    dfs(nums, 0);
    return res;
}

int main()
{
    vector<int> nums;
    int num;
    while(cin >> num)
    {
        nums.push_back(num);
        if(cin.get() == '\n') break;
    }
//    for(int i : nums) cout << i << endl;

    vector<vector<int>> res = subsets(nums);

    for(int i = 0; i < res.size(); ++ i)
    {
        cout << "[";
        for (int j = 0; j < res[i].size(); ++ j)
        {
            if(j == res[i].size() - 1) cout << res[i][j];
            else cout << res[i][j] << ",";
        }
        cout << "],";

    }
    cout << endl;
}

实现memcpy（）函数

https://www.cnblogs.com/chuanfengzhang/p/8447251.html
https://blog.csdn.net/xiaotaiyangzuishuai/article/details/77978825

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void *my_memcpy(void *dst, const void *src, int n)
{
    if (dst == NULL || src == NULL || n <= 0)
        return NULL;

    char * pdst = (char *)dst;
    char * psrc = (char *)src;

    if (pdst > psrc && pdst < psrc + n)//向前拷贝
    {
        pdst = pdst + n - 1;
        psrc = psrc + n - 1;
        while (n--)
            *pdst-- = *psrc--;
    }
    else//向后拷贝
    {
        while (n--)
            *pdst++ = *psrc++;
    }
    return dst;
}
//20200104  看到评论，又看了下之前写的memcpy实现　　　　
// 按字节拷贝实现的memcpy没有问题　　　　
// *pdst-- = *psrc--;  查了下运算符优先级（*,--）优先级相同，从右向左结合，psrc--是先使用，后减减　　　　
// 等价于*pdst = *psrc;psrc--;pdst--;

int main()
{
    char buf[100] = "abcdefghijk";
    //memcpy(buf+2, buf, 5);
    my_memcpy(buf+2, buf, 5);
    printf("%s\n", buf+2);
}

373. 查找和最小的 K 对数字

class Solution {
public:
    vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
        bool flag = true;
        vector<vector<int>> res;
        //保证nums1比nums2的size小，若交换则置flag为false
        int n = nums1.size();
        int m = nums2.size();
        if(n > m)
        {
            swap(nums1, nums2);
            swap(m, n);
            flag = false;
        }

        //定义比较规则 匿名函数 小根堆
        auto cmp = [&](const auto& a, const auto& b){
            return nums1[a.first] + nums2[a.second] > nums1[b.first] + nums2[b.second];
        };

        priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> pq(cmp);

        //将[i,0]push进堆,i为nums1的最小k个数的index（若n<k,则push nums1的所有n个数的index）
        for(int i = 0; i < min(n, k); i ++)
        {
            pq.push({i, 0});
        }
        //将堆顶存到res数组中，注意堆是否为空，堆大小小于k
        while(res.size() < k && pq.size())
        {
            auto [a, b] = pq.top();
            pq.pop();
            flag ? res.push_back({nums1[a], nums2[b]}) : res.push_back({nums2[b], nums1[a]});
            if(b+1 < m) pq.push({a, b + 1});
        }
        return res;
    }
};

变形：查找积最小的k对数字

#include <string>
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>

using namespace std;

vector<vector<int>> ksmallproduct(vector<int>& nums1, vector<int>& nums2, int k){
    vector<vector<int>> res;
    bool flag = true;
    int n = nums1.size();
    int m = nums2.size();
    if(n > m)
    {
        swap(nums1, nums2);
        swap(n, m);
        flag = false;
    }

    auto cmp = [&](const auto & a, const auto & b)
    {
        return nums1[a.first] * nums2[a.second] > nums1[b.first] * nums2[b.second];
    };

    priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> pq(cmp);
    for(int i = 0; i < min(n, k); i++)
    {
        pq.push({i, 0});
    }

    while(res.size() < k && pq.size())
    {
        auto [a, b] = pq.top();
        pq.pop();
        flag ? res.push_back({nums1[a], nums2[b]}):res.push_back({nums2[b], nums1[a]});
        if(b+1<m) pq.push({a, b+1});
    }

    return res;
}

int main() {
    vector<int> nums1;
    vector<int> nums2;
    int k;
    int num;
    while(cin>>num)
    {
        nums1.push_back(num);
        if(cin.get() == '\n') break;
    }
    while(cin>>num)
    {
        nums2.push_back(num);
        if(cin.get() == '\n') break;
    }
    cin >> k;

    vector<vector<int>> res = ksmallproduct(nums1, nums2, k);

    for(int i = 0; i < k; i ++)
    {
        cout << '['<<res[i][0] <<','<< res[i][1]<< ']'<<endl;
    }

    return 0;
}

二叉搜索树转换为双向链表 剑指 Offer 36. 二叉搜索树与循环双向链表

#include <iostream>

using namespace std;

struct Node{
    int val;
    Node* left, * right;
    Node():val(0),left(nullptr),right(nullptr){}
    Node(int x):val(x),left(nullptr),right(nullptr){}
};

//pre保存当前dfs根节点root的上一个节点,中序遍历顺序
//head保存双向链表头节点
//pre->root,root->pre,pre右移 pre = root
Node* pre = NULL, * head = NULL;
void dfs(Node* root)
{
    if(root == NULL) return;
    dfs(root->left);
    if(pre) pre->right = root;
    else head = root;
    root->left = pre;
    pre = root;
    dfs(root->right);
}

Node* treeToDoublyList(Node* root) {
    if(!root) return root;
    dfs(root);
    return head;
}

int main()
{
    Node* head = new Node(11);
    head->left = new Node(9);
    head->left->left = new Node(6);
    head->left->right = new Node(10);
    head->right = new Node(12);

    Node* res = treeToDoublyList(head);

    while(res)
    {
        cout << res->val <<" ";
        res = res->right;
    }
    cout << endl;
    return 0;
}

236. 二叉树的最近公共祖先

class Solution {
    public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root == p || root == q || root == NULL) return root;
        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);
        if(left!=NULL && right!=NULL) return root;
        if(left!=NULL && right==NULL) return left;
        if(left==NULL && right!=NULL) return right;
        return NULL;

    }
};

题解
时间复杂度：O(N)，其中 N是二叉树的节点数。二叉树的所有节点有且只会被访问一次，因此时间复杂度为 O(N)。
空间复杂度：O(N)，其中 NN 是二叉树的节点数。递归调用的栈深度取决于二叉树的高度，二叉树最坏情况下为一条链，此时高度为 N，因此空间复杂度为 O(N)。

剑指 Offer II 051. 节点之和最大的路径 124. 二叉树中的最大路径和

题解

class Solution {
public:
    int maxPathSum(TreeNode* root) {
        ret = INT_MIN;
        dfs(root);
        return ret;
    }

private:
    int ret;
    int dfs(TreeNode* root) {
        if (root == nullptr) {
            return 0;
        }
        int left = max(0, dfs(root->left));
        int right = max(0, dfs(root->right));
        ret = max(ret, left + right + root->val);
        return root->val + max(left, right);
    }
};

98. 验证二叉搜索树

题解
二叉搜索树中序遍历后是升序排列。

1. 递归

时间复杂度 : O(n)，其中 n为二叉树的节点个数。二叉树的每个节点最多被访问一次
空间复杂度 : O(n)，其中 n 为二叉树的节点个数。递归函数在递归过程中需要为每一层递归函数分配栈空间，所以这里需要额外的空间且该空间取决于递归的深度，即二叉树的高度。最坏情况下二叉树为一条链，树的高度为 n，递归最深达到 n 层，故最坏情况下空间复杂度为 O(n)。

1. 迭代

时间复杂度 : O(n)，其中 n 为二叉树的节点个数。二叉树的每个节点最多被访问一次
空间复杂度 : O(n)，其中 n为二叉树的节点个数。栈最多存储 n个节点

#include <iostream>
#include <stack>
#include <vector>
using namespace std;


struct TreeNode{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode():val(0),left(nullptr),right(nullptr){}
    TreeNode(int x): val(x),left(nullptr),right(nullptr){}
    TreeNode(int x, TreeNode* left, TreeNode* right): val(x), left(left), right(right){}
};

//层序数组构建二叉树
// https://leetcode-cn.com/problems/xu-lie-hua-er-cha-shu-lcof/solution/zha-zha-fa-xian-de-wen-ti-xi-wang-geng-duo-ren-kan/
TreeNode* deserialize(string data)
{
    if(data.size() == 0) return NULL;
    int len = data.size();
    int i  = 0;
    vector<TreeNode*> vec;
    while(i < len)
    {
        string str = "";
        while(i < len && data[i] != ',')
        {
            str.push_back(data[i]);
            i ++;
        }

        if(str == "null")
        {
            TreeNode* temp = NULL;
            vec.push_back(temp);
        }
        else
        {
            int temp = stoi(str);
            TreeNode* cur = new TreeNode(temp);
            vec.push_back(cur);
        }
        i ++;
    }
    int j = 1;
    for(int i = 0; j < vec.size(); i ++)
    {
        if(vec[i] == NULL) continue;
        if(j < vec.size()) vec[i] ->left = vec[j++];
        if(j < vec.size()) vec[i] ->right = vec[j++];
    }
    return vec[0];
}

//1.递归法
TreeNode* pre = NULL; // 用来记录前一个节点
bool isValidBST(TreeNode* root) {
    if(root == NULL) return true;
    bool left = isValidBST(root->left);

    if(pre != NULL && pre->val >= root->val) return false;
    pre = root;//视当前判断的树为右子树，pre为根节点即中序遍历的前一个节点

    bool right = isValidBST(root->right);
    return left && right;
}
//2.迭代法
bool isValidBST_iterate(TreeNode* root) {
    stack<TreeNode*> st;
    TreeNode* cur = root;
    TreeNode* p = NULL;

    while(cur != NULL || !st.empty())
    {
        if(cur != NULL)
        {
            st.push(cur);
            cur = cur->left;
        }
        else
        {
            cur = st.top();
            st.pop();
            if(p != NULL && p->val >= cur->val) return false;
            p = cur;
            cur = cur->right;
        }
    }
    return true;
}

int main() {
    TreeNode *t;
    string data;
    getline(cin, data);
    t = deserialize(data);
    if(isValidBST(t)) cout << "true";
    else cout << "false";
    return 0;
}

交换链表的两个节点

#include <string>
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>

using namespace std;

struct ListNode{
    int val;
    ListNode* next;
    ListNode(): val(0), next(nullptr){}
    ListNode(int x): val(x), next(nullptr){}
};
//删除节点k后面的节点
void remove(ListNode* k){
    k->next = k->next->next;
}

//将n插到k后 k->n
void add(ListNode* k, ListNode* n)
{
    n->next = k->next;
    k->next = n;
}

ListNode* swapxy(ListNode* head, int x, int y){
    if(x == y) return head;
    ListNode* dummy = new ListNode();
    dummy->next = head;
    if(x > y) swap(x, y);//x<y
    ListNode* p = dummy;
    for(int i = 0; i < x-1; i++)//p到x-1处
    {
        p = p->next;
    }
    ListNode* nx = p->next;
    ListNode* q = p;
    for(int i = x-1; i < y-1; i++)//q到y-1处
    {
        q = q->next;
    }
    ListNode* ny = q->next;
    //xy相邻,交换x,y
    if(x == y -1)
    {
        remove(p);
        add(ny,nx);
    }
    else{
        remove(p);
        remove(q);
        add(p, ny);
        add(q, nx);
    }
    return dummy->next;
}

int main() {
    int num;
    cin >> num;
    ListNode* head = new ListNode(num);
    ListNode* cur = head;
    while(cin >> num)
    {
        cur->next = new ListNode(num);
        cur = cur->next;
        if(cin.get() == '\n') break;
    }
    int x, y;
    cin >> x >> y;

    ListNode* res = swapxy(head, x, y);
    while(res)
    {
        cout << res->val << " ";
        res = res->next;
    }
    cout << endl;

    return 0;
}

24. 两两交换链表中的节点

#include <iostream>
using namespace std;

struct ListNode{
    int val;
    ListNode* next;
    ListNode():val(0), next(nullptr) {}
    ListNode(int x):val(x), next(nullptr) {}
    ListNode(int x, ListNode* next):val(x), next(next) {}
};

class Solution {
public:
    //递归
    ListNode* swapPairs1(ListNode* head) {
        if(!head || !head->next) return head;

        ListNode* next = head->next;
        head->next = swapPairs(next->next);
        next->next = head;
        return next;
    }

    //非递归
    ListNode* swapPairs2(ListNode* head) {
        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        ListNode* temp = dummy;
        //temp-node1-node2 ---> temp-node2-node1
        //temp迭代为node1
        //若temp后只有0或1个结点，直接返回
        while(temp->next && temp->next->next)
        {
            ListNode* node1 = temp->next;
            ListNode* node2 = temp->next->next;
            node1->next = node2->next;
            node2->next = node1;
            temp->next = node2;
            temp = node1;
        }

        return dummy->next;
    }
};

int main() {
    int num;
    cin >> num;
    ListNode* head = new ListNode(num);
    ListNode* ptr = head;//一般不会在原链表上直接操作，创建指向head的ptr,对ptr进行操作
    while(cin.get()!='\n'){
        cin >> num;
        ptr->next = new ListNode(num);
        ptr = ptr->next;
    }

    Solution A;

    head = A.swapPairs1(head);

    for(ListNode* i = head; i != nullptr; i = i->next)
    {
        cout << i->val;
    }
    cout << endl;
    return 0;
}

141. 环形链表

1. 哈希表set存链表结点

时间复杂度O（n），最坏遍历整个链表
空间复杂度O（n），最坏哈希表存了所有节点

class Solution {
public:
    bool hasCycle(ListNode *head) {
        unordered_set<ListNode*> us;
        ListNode* p = head;
        while(p)
        {
            if(us.count(p)) return true;
            us.insert(p);
            p = p->next;
        }
        return false;    
    }
};

1. 快慢指针

慢指针每次只移动一步，而快指针每次移动两步。初始时，慢指针在位置 head，而快指针在位置 head.next。这样一来，如果在移动的过程中，快指针反过来追上慢指针，就说明该链表为环形链表。否则快指针将到达链表尾部，该链表不为环形链表。

为什么我们要规定初始时慢指针在位置 head，快指针在位置 head.next，而不是两个指针都在位置 head？
观察下面的代码，我们使用的是 while 循环，循环条件先于循环体。由于循环条件一定是判断快慢指针是否重合，如果我们将两个指针初始都置于 head，那么 while 循环就不会执行。因此，我们可以假想一个在 head 之前的虚拟节点，慢指针从虚拟节点移动一步到达 head，快指针从虚拟节点移动两步到达 head.next，这样我们就可以使用 while 循环了。当然，我们也可以使用 do-while 循环。此时，我们就可以把快慢指针的初始值都置为 head。
时间复杂度：O（n），最坏遍历整个链表
空间复杂度：O（1），快慢指针

class Solution {
public:
    bool hasCycle(ListNode *head) {
        if(!head || !head->next) return false;
        ListNode* fast = head->next;
        ListNode* slow = head;

        while(fast != slow)
        {
            if(!fast || !fast->next) return false;
            fast = fast->next->next;
            slow = slow->next;
        }

        return true;
    }
};

142. 环形链表 II

1. 哈希set

   class Solution {
   public:
    ListNode *detectCycle(ListNode *head) {
        if(!head || !head->next) return NULL;
        unordered_set<ListNode*> us;
        while(head)
        {
            if(us.count(head)) return head;
            us.insert(head);
            head = head->next;
        }
        return NULL;
    }
   };
   

2. 双指针法

fast，slow指针从head出发，每次fast走2，slow走1
若有环，设从head到环前（不包括环入口）有a个节点，环有b个节点
1）当fast和slow在环中相遇时
设slow走s, fast走f = nb+s，fast走的距离是slow的两倍，f = 2s, 可得s = nb,f = 2nb
2）所有走到环入口的步数是a+nb，所有slow再走a步即可到达环入口，a未知
3）当s走到nb时，让fast回到head，head到入口的距离也为a
4）fast和slow第二次在环入口a处相遇，返回a

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode* fast = head;
        ListNode* slow = head;

        while(1)
        {
            if(!fast || !fast->next) return NULL;
            fast = fast->next->next;
            slow = slow->next;
            //fast,slow挪动后再比较是否相遇，因为一开始都指向了head
            if(fast == slow) break;
        }
        cout<<fast->val<<slow->val<<endl;

        fast = head;
        while(fast != slow)
        {
            fast = fast->next;
            slow = slow->next;
        }

        return fast;
    }
};

待看

（经典）求两个单链表相交结点

146. LRU 缓存机制

题解

/*
    哈希表快速查找的特性
    双向链表快速添加删除节点的特性
*/
//手写双链表
struct DLinkedNode{
    int key, value;
    DLinkedNode* prev;
    DLinkedNode* next;
    DLinkedNode(): key(0), value(0), prev(nullptr), next(nullptr){}
    DLinkedNode(int _key, int _value): key(_key), value(_value), prev(nullptr), next(nullptr){}
};

class LRUCache {
private:
    unordered_map<int, DLinkedNode*> cache;//哈希链表
    int size, cap;
    DLinkedNode* head;
    DLinkedNode* tail;

public:
    LRUCache(int capacity):cap(capacity), size(0) {
        //使用伪头部和伪尾部节点
        head = new DLinkedNode();
        tail = new DLinkedNode();
        head->next = tail;
        tail->prev = head;
    }

    int get(int key) {
        //如果key不存在，返回-1
        if(!cache.count(key)) return -1;
        //如果key存在
        DLinkedNode* node = cache[key];//通过key在哈希表中定位，得到对应的双链表节点
        moveToHead(node);
        return node->value;
    }

    void put(int key, int value) {
        //如果key不存在
        //1.将<key, node>添加到哈希表中
        //2.在虚拟头节点前插入新节点node
        //3.cache的size加1
        //4.判断size是否超过最大容量cap
        if(!cache.count(key))
        {
            DLinkedNode* node = new DLinkedNode(key, value);
            cache[key] = node;
            addToHead(node);
            ++ size;
            //如果超出容量
            //1.删除双向链表的尾节点(虚拟尾节点之前)
            //2.删除哈希表中对应的项
            //3.delete被删除的点，防止内存泄漏
            //4.cache的size减1
            if(size > cap){
                DLinkedNode* removed = removeTail();
                cache.erase(removed->key);
                delete removed;
                size --;
            }
        }
        //如果key存在
        //1.通过哈希表定位到双链表节点
        //2.修改value
        //3.将该节点移到头部
        else
        {
            DLinkedNode* node = cache[key];
            node->value = value;
            moveToHead(node);
        }
    }

    void moveToHead(DLinkedNode* node)//双向链表：将该节点移动到虚拟头节点后面
    {
        removeNode(node);
        addToHead(node);//在头节点插入node
    }

    void removeNode(DLinkedNode* node)//双向链表：删除node
    {
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }

    void addToHead(DLinkedNode* node)//双向链表：在虚拟头节点后面插入node
    {
        node->prev = head;
        node->next = head->next;
        head->next->prev = node;
        head->next = node;
    }

    DLinkedNode* removeTail()//双向链表：删除的尾节点(虚拟尾节点之前)，并返回被删除的节点
    {
        DLinkedNode* node = tail->prev;
        removeNode(node);
        return node;
    }
};

/**
 * 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);
 */

124(变式). 二叉树中的最大路径和

二叉树前中后序遍历递归法和迭代法