剑指 offer 全记录

水深无声 2024-04-19 08:08 60阅读 0赞

### 文章目录 ###

*  排序
 *   *   *  1.快排(时间复杂度O(nlogn),空间复杂度O(1))，下面的实现是一种原地排序的实现。
         *  2.堆排
         *  3.归并(时间复杂度一直是O(NlogN)，空间复杂度O(n))
         *  4.插入
 *  关于排序延伸的几道题
 *   *   *  1.求最小/大的k个数字与求第k小/大的数字
         *  2.
 *  查找
 *   *   *  二分查找O(logN)
         *  变异的二分查找
         *  1.旋转数组的最小数字
         *  2.数字在排序数组中出现的次数
         *  3.
         *  4.
 *  数组
 *   *   *  1. 二维数组中的查找
         *  2. 数组中出现次数超过一半的数字
         *  3. 数组中重复的数字
         *  4.
 *  字符串
 *   *   *  1.替换空格
         *  2. 书写一个upCase函数
         *  3. leetcode151. 翻转字符串里的单词
         *  4.左旋转字符串
         *  5.字符串转换整数
 *  链表
 *   *   *  1.链表的逆置
         *  2.在O(1)时间内删除链表节点
         *  3.链表中的倒数第k个节点
         *  4.合并两个排序的链表
         *  5.两个链表的第一个公共节点
         *  6.环形链表（圆圈中最后剩下的数字）
         *  7.二叉搜索树与双向链表
         *  8.复杂链表的复制
 *  树
 *   *   *  0.树三种递归&&非递归遍历&&层次遍历
         *  1.重建二叉树
         *  2.二叉树的深度
         *  2.1 平衡二叉树
         *  3.树的子结构
         *  4.二叉树中和为某一值的路径
         *  5.二叉树的后序遍历序列
         *  6.从上到下遍历二叉树
         *  8.树中两个节点的最近公共祖先 lowest-common-ancestor问题
         *   *   *  (1) 树是二叉搜索树
                 *  (2) 树是普通的二叉树
                 *  (3) 树的节点中存在指向父节点的指针
         *  9.二叉树的镜像与对称的问题
         *   *   *  (1) 二叉树的镜像
                 *  (2)对称的二叉树
                 *  (3)
         *  9.二叉搜索树与双向链表
         *  10.求最小的k个数字与求第k小的数字的问题
 *  栈和队列
 *   *   *  1.栈的压入、弹出序列
 *  位运算
 *  动态规划和贪心
 *   *   *  1.最大子序和
         *  2.剪绳子/切割杆的问题
         *  3.动态规划:字符串编辑距离(edit distance)
         *  
 *  回溯法和DFS，BFS
 *   *   *  1.矩阵中的路径/单词搜索
         *  2.子集
         *  3.
 *  k 数之和的问题
 *   *   *  1.两数之和
         *  2.两数之和 II - 输入有序数组
         *  3.两数之和 IV - 输入 BST
         *  4.三数之和
         *  5.和为S的连续正数序列
 *  发散思维题以及单例的实现
 *   *   *  1.使用C++实现单例
         *  2.
         *  3.

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXNoZW5neGlfcm9vdA_size_16_color_FFFFFF_t_70]

最容易记忆的方式书写，记录所有思路和拓展。分门别类书写。  
确定每一个思路的时间复杂度

# 排序 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXNoZW5neGlfcm9vdA_size_16_color_FFFFFF_t_70 1]

### 1.快排(时间复杂度O(nlogn),空间复杂度O(1))，下面的实现是一种原地排序的实现。 ###

class Solution
    { 
    public:
        int partition(vector<int> &nums, int l, int r)
        { 
            int k = l, pivot = nums[r];
            for (int i = l; i < r; i++)
            { 
                if (nums[i] <= pivot)
                    std::swap(nums[i], nums[k++]);
            }
            std::swap(nums[k], nums[r]);
            return k;
        }
        void quick_sort(vector<int> &nums, int l, int r)
        { 
            if (l >= r)
                return;
            int q = partition(nums, l, r);
            quick_sort(nums, l, q - 1);
            quick_sort(nums, q + 1, r);
        }
        vector<int> sortArray(vector<int> &nums)
        { 
            if (nums.size() <= 1)
                return nums;
    
            quick_sort(nums, 0, nums.size() - 1);
            return nums;
        }
    };

**最差情况是O(n^2)**，这就在于基准点的选取。

### 2.堆排 ###

class Solution
    { 
    public:
        //构造的是 大顶堆 哦
        //每个节点堆化的时间复杂度是：O(logN)
        void heapify(vector<int> &a, int n, int i)
        { 
            while (true)
            { 
                int maxPos = i;
                if (i * 2 + 1 <= n && a[i] < a[i * 2 + 1]) //左子节点，就是下标为 i∗2+1 的节点，
                    maxPos = i * 2 + 1;
                if (i * 2 + 2 <= n && a[maxPos] < a[i * 2 + 2]) //右子节点，就是下标为 i∗2+2 的节点
                    maxPos = i * 2 + 2;
    
                if (maxPos == i)
                    break;
                std::swap(a[i], a[maxPos]);
                i = maxPos;
            }
        }
        //时间复杂度：O(N)
        void buildHeap(vector<int> &nums, int n)
        { 
            //从后向前，非叶子节点是：0 到 n/2-1
            for (int i = n / 2 - 1; i >= 0; i--)
            { 
                heapify(nums, n, i);
    
                for (auto tt : nums)
                    cout << tt << " ";
                cout << endl;
            }
        }
        vector<int> sortArray(vector<int> &nums)
        { 
            if (nums.size() <= 0)
                return nums;
    
            buildHeap(nums, nums.size() - 1);
            int k = nums.size() - 1;
            //排序过程的时间复杂度是 O(nlogn)
            while (k > 0)
            { 
                //从上到下再 堆化
                swap(nums[0], nums[k]); //依此将最大的数字换到数组末尾
                --k;
                heapify(nums, k, 0);
            }
            return nums;
        }
    };

注意：

*  以上下标是从0开始的哦。如果是以1开始的话，那么左子树，右子树下标就不一样了哦！
 *  堆排分为两步(建堆O(n)+排序(O(NlogN))),所以总的时间复杂度是O(NlogN)
 *  不稳定，空间复杂度是O(1)

[堆排序（完全二叉树形数据结构）][Link 1]

### 3.归并(时间复杂度一直是O(NlogN)，空间复杂度O(n)) ###

class Solution
    { 
    public:
        void merge_two(vector<int> &nums, int left, int middle, int right, vector<int> &tmp)
        { 
            int k = 0;          //临时数组下标
            int i = left;       //左边数组的起始
            int j = middle + 1; //右边数组的起始
    
            while (i <= middle && j <= right)
            { 
                if (nums[i] <= nums[j])
                    tmp[k++] = nums[i++];
                else
                    tmp[k++] = nums[j++];
            }
            while (i <= middle)
            { 
                tmp[k++] = nums[i++];
            }
            while (j <= right)
            { 
                tmp[k++] = nums[j++];
            }
            std::copy_n(tmp.begin(), k, nums.begin() + left); //拷到原来的地方
        }
        void merge_sort(vector<int> &nums, int left, int right, vector<int> &tmp)
        { 
            if (left >= right)
                return;
            int middle = (left + right) >> 1;
            merge_sort(nums, left, middle, tmp);
            merge_sort(nums, middle + 1, right, tmp);
    
            merge_two(nums, left, middle, right, tmp);
        }
        vector<int> sortArray(vector<int> &nums)
        { 
            if (nums.size() <= 0)
                return nums;
            vector<int> tmp(nums.size());
            merge_sort(nums, 0, nums.size() - 1, tmp);
            return nums;
        }
    };

### 4.插入 ###

class Solution
    { 
    public:
        void insertSort(vector<int> &nums)
        { 
            for (int i = 1; i < nums.size(); i++)
            { 
                int key = nums[i];
                int j = i - 1;
                /*查找插入的位置*/
                for (; j >= 0; j--)
                { 
                    if (nums[j] > key)
                        nums[j + 1] = nums[j]; /*数据移动*/
                    else
                        break;
                }
                nums[j + 1] = key; //数据插入
            }
        }
        vector<int> sortArray(vector<int> &nums)
        { 
            if (nums.size() <= 1)
                return nums;
    
            insertSort(nums);
            return nums;
        }
    };

# 关于排序延伸的几道题 #

### 1.求最小/大的k个数字与求第k小/大的数字 ###

在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

思路：

*  快排的思想。O(n)
 *  堆排的思想。 O(NlogK)

快排的思想。O(n)

class Solution
    { 
    public:
        int partition(vector<int> &nums, int l, int r)
        { 
            int k = l, privot = nums[r];
            for (int i = l; i < r; i++)
            { 
                if (nums[i] >= privot)
                    std::swap(nums[k++], nums[i]);
            }
            std::swap(nums[k], nums[r]);
            return k;
        }
        int findKthLargest(vector<int> &vv, int k)
        { 
            int l = 0;
            int r = vv.size() - 1;
            int q = partition(vv, l, r);
    
            while (q != k-1)
            { 
                if (q > k-1)
                { 
                    r = q - 1;
                    q = partition(vv, l, r);
                }
                else
                { 
                    l = q + 1;
                    q = partition(vv, l, r);
                }
            }
            return vv[q];
        }
    };

*  堆排的思想。 O(NlogK)

class Solution
    { 
    public:
        int findKthLargest(vector<int> &nums, int k)
        { 
            if (nums.size() <= 0 || nums.size() < k)
                return -1;
            //最大堆，底层实现的数据结构是 vector ,但需要满足堆的特性
            priority_queue<int, std::vector<int>, greater<int>> QQ;
            for (int i = 0; i < nums.size(); i++)
            { 
                if (i < k)
                { 
                    QQ.push(nums[i]);
                }
                else if (nums[i] > QQ.top())
                { 
                    QQ.pop();
                    QQ.push(nums[i]);
                }
            }
            return QQ.top();
        }
    };

### 2. ###

# 查找 #

### 二分查找O(logN) ###

循环实现

class Solution
    { 
    public:
        int search(vector<int> &nums, int target)
        { 
            if (nums.size() <= 0)
                return -1;
    
            int left = 0;
            int right = nums.size() - 1; //right一定要指向最后一个有效的数字
            int mid = 0;
    
            while (left <= right)
            { 
                mid = left + ((right - left) >> 1); //这里一定要加括号才行
                if (nums[mid] == target)
                    return mid;
                else if (nums[mid] < target)
                    left = mid + 1;
                else
                    right = mid - 1;
            }
            return -1;
        }
    };

递归实现

### 变异的二分查找 ###

### 1.旋转数组的最小数字 ###

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。  
输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。  
例如数组\{3,4,5,1,2\}为\{1,2,3,4,5\}的一个旋转，该数组的最小值为1。  
NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。

*  思路：二分的思路就是将其分为两个递增数组，然后看num\[mid\]属于哪一个数组，最后的结束条件是`low指向第一个递增数组最尾部，high 指向第二个递增数组最头部`。注意`当有重复元素时，会产生(num[mid]=nums[low] == nums[high])无法判断在那个数组的情况`，这时就需要顺序查找了。时间复杂度O(logN)

class Solution
    { 
    public:
        int MinFun(vector<int> &nums, int low, int high)
        { 
            int ret = 0;
            for (int i = low; i < high - 1; i++)
            { 
                if (nums[i + 1] < nums[i])
                { 
                    ret = i + 1;
                    break;
                }
            }
            return ret;
        }
        //考虑重复
        int minNumberInRotateArray(vector<int> nums)
        { 
            if (nums.size() <= 0)
                return 0;
            //处理：12345 的特殊情况
            if (nums[0] < nums[nums.size() - 1])
                return nums[0];
    
            int low = 0;
            int high = nums.size() - 1;
            int mid = low + ((high - low) >> 1);
            //明显的体现出 low指向第一个递增数组最尾部，high 指向第二个递增数组最头部的特点
            while (high - low != 1)
            { 
                if (nums[mid] == nums[low] && nums[mid] == nums[high])
                { 
                    high = MinFun(nums, low, high);
                    break;
                }
                if (nums[mid] >= nums[low])
                    low = mid;
                else if (nums[mid] <= nums[high])
                    high = mid;  //注意这里不能够 +-1，否则会造成死循环
                else
                    break; //54321 的情况
                mid = low + ((high - low) >> 1);
            }
            return nums[high];
        }
    };

类似题目：[https://leetcode-cn.com/problemset/all/?search=%20%E6%97%8B%E8%BD%AC%E6%95%B0%E7%BB%84][https_leetcode-cn.com_problemset_all_search_20_E6_97_8B_E8_BD_AC_E6_95_B0_E7_BB_84]

### 2.数字在排序数组中出现的次数 ###

*  思路：
 *  1.二分查找到数字，然后左右找。时间复杂度是O(n)
 *  2.用**两次 二分查找找到第一次出现的位置和最后一次出现的位置**，然后下标相减即可。时间复杂度O(logN)

统计一个数字在排序数组中出现的次数。

class Solution
    { 
    public:
        //存在返回 对应要求的下标，不存在返回 -1
        int GetFristIndex(const vector<int> &data, int k)
        { 
            int low = 0;
            int high = data.size() - 1;
            int mid = low + ((high - low) >> 1);
            while (low <= high)
            { 
                if (data[mid] == k)
                { 
                    if (mid == 0 || data[mid - 1] != k)
                        break;//说明找到了第一次出现的k的位置
                    else
                        high = mid - 1;
                }
                else if (data[mid] < k)
                    low = mid + 1;
                else
                    high = mid - 1;
                mid = low + ((high - low) >> 1);
            }
            if (low > high)
                return -1;
            else
                return mid;
        }
        int GetLastIndex(const vector<int> &data, int k)
        { 
            int low = 0;
            int high = data.size() - 1;
            int mid = low + ((high - low) >> 1);
            while (low <= high)
            { 
                if (data[mid] == k)
                { 
                    if (mid == data.size() - 1 || data[mid + 1] != k)
                        break;//说明找到了最后一个k
                    else
                        low = mid + 1;
                }
                else if (data[mid] < k)
                    low = mid + 1;
                else
                    high = mid - 1;
                mid = low + ((high - low) >> 1);
            }
            if (low > high)
                return -1;
            else
                return mid;
        }
        int GetNumberOfK(vector<int> data, int k)
        { 
            if (data.size() <= 0)
                return 0;
            int start = GetFristIndex(data, k);
    
            if (start == -1)
                return 0;
            int end = GetLastIndex(data, k);
            return end - start + 1;
        }
    };

### 3. ###

### 4. ###

# 数组 #

### 1. 二维数组中的查找 ###

在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

思路：

*  把每一行看成有序递增的数组，  
    利用二分查找（logN），  
    通过遍历每一行得到答案，  
    时间复杂度是nlogn
 *  利用二维数组由上到下，由左到右递增的规律，那么选取右上角或者左下角的元素与target进行比较。类似于二叉查找树的形式.复杂度是O(logN)

class Solution
    { 
    public:
        bool Find(int target, vector<vector<int>> array)
        { 
            //二叉查找树
            int row = array.size();
            if (row <= 0)
                return false;
            int col = array[0].size();
            for (int j = col - 1, i = 0; j >= 0 && i < row;)
            //从右上角开始，注意循环结束条件
            { 
                if (target == array[i][j])
                { 
                    return true;
                }
                else if (target < array[i][j])
                { 
                    j--;
                }
                else
                { 
                    i++;
                }
            }
            return false;
        }
    };

### 2. 数组中出现次数超过一半的数字 ###

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组\{1,2,3,2,2,2,5,4,2\}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。

思路：

*  1.hash\_map 辅助，数字作为key。出现的次数作为 value 。时间 O(n)，空间 O(n)《略》
 *  2.基于Partition 函数的算法。时间O(n)，空间O(1)。但会修改输入输入数组！！！
 *  3.根据数组特点找出O(n)的算法（数学）。

2.基于 Partition 函数的算法。`由于该数字出现的次数超过数组的一半，所以如果我们将数组排序，那么位于最中间的数字就是我们要找的数字啦！`也就是说`该数字是第n/2大的数字`啦。

//方法二
    class Solution
    { 
    public:
        int partition(vector<int> &vv, int l, int r)
        { 
            int k = l, pivot = vv[r];
            for (int i = l; i < r; i++)
            { 
                if (vv[i] <= pivot)
                    std::swap(vv[k++], vv[i]);
            }
            std::swap(vv[k], vv[r]);
            return k;
        }
        int MoreThanHalfNum_Solution(vector<int> numbers)
        { 
            int len = numbers.size();
    
            if (len < 1)
                return 0;
    
            int left = 0;
            int right = len - 1;
            int k = partition(numbers, left, right);
            while (k != len / 2)
            { 
                if (k < len / 2)
                { 
                    left = k + 1;
                    k = partition(numbers, left, right);
                }
                else if (k > len / 2)
                { 
                    right = k - 1;
                    k = partition(numbers, left, right);
                }
            }
            int time = 0;
            for (auto it : numbers)
            { 
                if (it == numbers[k])
                { 
                    time++;
                }
            }
            //数组中出现次数超过一半
            if (time > len / 2)
                return numbers[k];
            else
                return 0;
        }
    };

3.如果有一个数字出现的次数超过了数组的一半，比剩余的其他数字出现的次数的和都要大。因此：

*  我们可以在遍历数组的时候记录两个值：

1.  数组中的数字;
2.  次数。

*  遍历下一个数字时，若它与之前保存的数字相同，则次数加1，否则次数减1；若次数为0，则保存下一个数字，并将次数置为1。遍历结束后，所保存的数字即为所求。最后再判断它是否符合条件。

class Solution
    { 
    public:
        int MoreThanHalfNum_Solution(vector<int> numbers)
        { 
            int len = numbers.size();
    
            if (len < 1)
                return 0;
            int value = numbers[0];
            int count = 1;
            for (int i = 1; i < len; i++)
            { 
                if (numbers[i] == value)
                    count++;
                else
                    count--;
                if (count == 0)
                { 
                    value = numbers[i];
                    count = 1;
                }
                printf("num[%d] == %d ,value == %d ,count == %d \n", i, numbers[i], value, count);
            }
            //检查找出的这个数是不是出现的次数超过一半
            int time = 0;
            for (auto it : numbers)
            { 
                if (it == value)
                { 
                    time++;
                }
            }
            //数组中出现次数超过一半
            if (time > len / 2)
                return value;
            else
                return 0;
        }
    };
    int main()
    { 
        Solution s1;
        cout << s1.MoreThanHalfNum_Solution({ 1, 2, 3, 2, 2, 2, 5, 4, 2}) << endl;
        cout << "vffelvnfdknkfnvknfb\n\n\n\n";
    
        cout << s1.MoreThanHalfNum_Solution({ 1, 2, 3, 2, 4, 2, 5, 2, 3}) << endl;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXNoZW5neGlfcm9vdA_size_16_color_FFFFFF_t_70 2]

### 3. 数组中重复的数字 ###

在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组\{2,3,1,0,2,5,3\}，那么对应的输出是第一个重复的数字2。

思路：

*  排序
 *  哈希
 *  特殊方法：交换法。题中给出的是一个长度为n的数组，数组的下标是0n-1，数组中的数字也是0n-1。因此，当数组中不存在重复数字且排序之后，数字i将出现在下标为i的位置。由于数组中存在重复数字，因此，按照上面的思路，存在有的位置没有数字，有的位置要存放多个相同的数字。

根据这种思路，我们可以采用交换法解决这个问题。扫描数组，每扫描一个数字，就比较当前数字是否与其下标相等，若相等，继续向后扫描；若不相等，比较以该数字为下标的元素是否与该元素相等，若相等，说明该元素是一个重复元素，向后扫描，否则，交换该元素和数组中以该元素为下标的元素。时间O(n)，空间O(1)

class Solution
    { 
    public:
        // Parameters:
        // numbers: an array of integers
        // length: the length of array numbers
        // duplication: (Output) the duplicated number in the array number
        // Return value: true if the input is valid, and there are some duplications in the array number
        // otherwise false
        bool duplicate(int numbers[], int length, int *duplication)
        { 
            if (length < 1)
            { 
                return false;
            }
            for (int i = 0; i < length; i++)
            { 
                if (numbers[i] < 0 || numbers[i] > length - 1)
                    return false;
            }
    
            for (int i = 0; i < length; i++)
            { 
                while (numbers[i] != i)
                { 
                    if (numbers[numbers[i]] == numbers[i])
                    { 
                        *duplication = numbers[i];
                        return true;
                    }
                    else
                    { 
                        std::swap(numbers[i], numbers[numbers[i]]);
                    }
                }
            }
            return false;
        }
    };

### 4. ###

# 字符串 #

### 1.替换空格 ###

请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

思路：很明显，这样子的替换会**改变字符串的大小。所以一种就是使用原来字符串后面的内存，一种就是自己分配内存。**

如何替换：

1.  从前向后扫描，遇到空格就替换，需要移动元素。时间复杂度O(n^2)
2.  `从后往前遍历并替换`，一个指针指向新的，一个指向旧的。遍历旧的字符串对新指针直接赋值或者替换即可。时间复杂度O(n)

*  从前向后扫描，遇到空格就替换，需要移动元素。时间复杂度O(n^2)

class Solution { 
    public:
    	void replaceSpace(char *str,int length) { 
            for(int i= 0 ;i< length ;)
            { 
                if(str[i] == ' ')
                { 
                    for(int j = length-1 ;j >= i ;j--)
                    { 
                        str[j+2] = str[j];    
                    }
                    str[i++]= '%';
                    str[i++] ='2';
                    str[i++] ='0';
                    continue;
                }
                i++;
    	    }
        }
    };

*  `从后往前遍历并替换`，一个指针指向新的，一个指向旧的。遍历旧的字符串对新指针直接赋值或者替换即可。时间复杂度O(n)

class Solution
    { 
    public:
        //length 为str 的 内存capity
        void replaceSpace(char *str, int length)
        { 
            if (str == nullptr || length == 0)
                return;
    
            int spaceNumber = 0;
            int originLength = 0;
            //统计空格和str的长度
            char *tmp = str;
            while (*tmp != '\0')
            { 
                originLength++;
                if (*tmp == ' ')
                    spaceNumber++;
                tmp++;
            }
    
            int indexOrigin = originLength; //将'\0'也直接当作非空格自负处理即可
            int indexNew = originLength + 2 * spaceNumber;
            if (indexNew > length)
                return;
    
            while (indexOrigin >= 0 && indexNew > indexOrigin)
            { 
                if (str[indexOrigin] != ' ')
                { 
                    str[indexNew--] = str[indexOrigin];
                }
                else
                { 
                    str[indexNew--] = '0';
                    str[indexNew--] = '2';
                    str[indexNew--] = '%';
                }
                indexOrigin--;
            }
        }
    };

拓展：`合并两个数组（字符串）的时候都可以使用这种方法，会减少移动的次数，提高效率`

[https://leetcode-cn.com/problems/merge-sorted-array/][https_leetcode-cn.com_problems_merge-sorted-array]

### 2. 书写一个upCase函数 ###

char *upCase(const char *str) //const 属性
    { 
        cout << *str << endl;
    
        char *ret = new char(strlen(str) + 1); 
        //strlen 开头和终止空字符之间的字符数（不包括终止空字符‘\0’本身）.
        char *tmp = ret;
        
        while (*str)
        { 
            cout << *str << " ";
            if (*str >= 'a' && *str <= 'z')
                *tmp = *str - 32;
            else
                *tmp = *str;
            str++;
            tmp++;
        }
        cout << endl;
        *tmp = '\0'; //需要调整以满足字符串的格式
    
        return ret;
    }
    int main()
    { 
        char str[] = "liu shE4ng xi!!!";
        cout << str << endl;
    
        cout << upCase(str) << endl;
        return 0;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXNoZW5neGlfcm9vdA_size_16_color_FFFFFF_t_70 3]

### 3. leetcode151. 翻转字符串里的单词 ###

给定一个字符串，逐个翻转字符串中的每个单词。  
示例 1：  
输入: “the sky is blue”  
输出: “blue is sky the”

示例 2：  
输入: " hello world! "  
输出: “world! hello”  
解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。

示例 3：  
输入: “a good example”  
输出: “example good a”  
解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

说明：  
无空格字符构成一个单词。  
输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。  
如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

进阶：

请选用 C 语言的用户尝试使用 O(1) 额外空间复杂度的原地解法。

链接：[https://leetcode-cn.com/problems/reverse-words-in-a-string][https_leetcode-cn.com_problems_reverse-words-in-a-string]

注意这道题有很多的坑点需要注意：

1.  中间有很多空格
2.  前后有空格
3.  字符串输入为空，字符串输入只有空格。

思路：

*  1.直接利用 stringstream 提取单词，利用 string 的 + 号逆序添加。（非原地算法）
 *  2.上面的算法主要耗时点在逆序插入上。那么我们给他变成顺序插入看看。(非原地算法)
 *  3.就是剑指offer上面的做法 。先逆转整个字符串，然后逆转每一个单词。(原地算法)

直接利用 stringstream 提取单词，利用 string 的 + 号（insert也一样）逆序添加。

class Solution
    { 
    public:
        string reverseWords(string s)
        { 
            string ans, str;
            stringstream ss(s);
    
            ss >> str;
            ans.insert(0, str);  //特殊处理第一个单词
    
            while (ss >> str)
                ans.insert(0, str + " ");//最主要的耗时也在这里 ?‍❤️‍?
                
            return ans.size() ? ans : "";
        }
    };

变成顺序插入看看。(非原地算法)

class Solution
    { 
    public:
        string reverseWords(string s)
        { 
            string ans, tmp;
            stringstream ss(s);
            vector<string> vv;
    
            while (ss >> tmp)
                vv.push_back(tmp); //全部流入 vector 容器中
    
            //处理 字符串输入为空，字符串输入只有空格 的情况
            if (vv.size() < 1)
                return ans;
    
            for (int i = vv.size() - 1; i > 0; i--)
            { 
                ans += vv[i] + " ";
            }
            //特殊处理 最终放置在 尾部 的单词
            ans += vv[0];
    
            return ans.size() ? ans : "";
        }
    };
    //虽然我是这样写的，但是我觉得如下这样写是看起来最简洁明了的代码。上面一个解法也是一样。
    class Solution
    { 
    public:
        string reverseWords(string s)
        { 
            string ans, tmp;
            stringstream ss(s);
            vector<string> vv;
            
            while (ss >> tmp)
                vv.push_back(tmp); //全部流入 vector 容器中
                
            for (int i = vv.size() - 1; i >= 0; i--)
            { 
                ans += vv[i] + " ";
            }
            return ans.size() ? string(ans.begin(), ans.end() - 1) : "";
            //去掉多加的一个空格
        }
    };

剑指offer上面的做法 。先逆转整个字符串，然后逆转每一个单词。(原地算法)，剑指offer上面的输入中间是没有多个空格的。

class Solution
    { 
    public:
        template <typename T> //摘自 std::reverse
        void reverseFun(T frist, T last)
        { 
            while ((frist != last) && (frist != --last))
            { 
                std::iter_swap(frist++, last);
            }
        }
        string reverseWords(string s)
        { 
            if (s.size() <= 0)
                return s;
    
            reverseFun(s.begin(), s.end()); //翻转整体
    
            int start = 0, end = s.size() - 1;
            while (s[start] == ' ' && start <= end)
                start++;
    
            while (s[end] == ' ' && end >= start)
                end--;
    
            if (start > end)
            { 
                return s; //特殊情况即字符串全为空字符
            }
    
            // 翻转中间的单词
            for (int i = start; i <= end; i++)
            { 
                while (s[i] == ' ' && i <= end)
                { 
                    i++;
                }
    
                int l = i;
                while (s[i] != ' ' && i <= end)
                { 
                    i++;
                }
                reverseFun(s.begin() + l, s.begin() + i);
            }
            // 处理中间部分多 ? 的空格
            int tail = start;
            for (int i = start; i <= end; i++)
            { 
                if (s[i] == ' ' && s[i + 1] == ' ')
                { 
                    continue;
                }
                s[tail++] = s[i];
            }
            return s.substr(start, tail - start);
        }
    };

### 4.左旋转字符串 ###

对于一个给定的字符序列S，请你把其循环左移K位后的序列输出。例如，字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果，即“XYZdefabc”。是不是很简单？OK，搞定它！

这个思路还用说吗？

class Solution
    { 
    public:
    	string LeftRotateString(string str, int n)
    	{ 
    		if(str.size()<= 0)
    			return string();
    		if(n ==  0)
    			return str;
    		string tt = str.substr(0, n );
    		string rr = str.substr(n, str.size());
    		return rr + tt;
    	}
    };

emmmm，将abcXYZdef分为abc和其他。分别将他们翻转。得到cba fedZYX。然后再整体翻转得到 XYZdefabc，即为最终所求结果！！！时间O(n),空间O(1)

class Solution
    { 
    public:
        template <typename T> //摘自 std::reverse
        void reverseFun(T frist, T last)
        { 
            while ((frist != last) && (frist != --last))
            { 
                std::iter_swap(frist++, last);
            }
        }
        string LeftRotateString(string str, int n)
        { 
            if (str.size() <= 0)
                return str;
            if (n == 0)
                return str;
            reverseFun(str.begin(), str.begin() + n);
            reverseFun(str.begin() + n, str.end());
            reverseFun(str.begin(), str.end());
            
            return str;
        }
    };

### 5.字符串转换整数 ###

[https://leetcode-cn.com/problems/string-to-integer-atoi/][https_leetcode-cn.com_problems_string-to-integer-atoi]

请你来实现一个 atoi 函数，使其能将字符串转换成整数。

首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。

当我们寻找到的第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字组合起来，作为该整数的正负号；假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成整数。

该字符串除了有效的整数部分之后也可能会存在多余的字符，这些字符可以被忽略，它们对于函数不应该造成影响。

注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换。

在任何情况下，若函数不能进行有效的转换时，请返回 0。

说明：

假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 \[−231, 231 − 1\]。如果数值超过这个范围，请返回 INT\_MAX (231 − 1) 或 INT\_MIN (−231) 。

示例 1:

输入: “42”  
输出: 42  
示例 2:

输入: " -42"  
输出: -42  
解释: 第一个非空白字符为 ‘-’, 它是一个负号。  
我们尽可能将负号与后面所有连续出现的数字组合起来，最后得到 -42 。  
示例 3:

输入: “4193 with words”  
输出: 4193  
解释: 转换截止于数字 ‘3’ ，因为它的下一个字符不为数字。  
示例 4:

输入: “words and 987”  
输出: 0  
解释: 第一个非空字符是 ‘w’, 但它不是数字或正、负号。  
因此无法执行有效的转换。  
示例 5:

输入: “-91283472332”  
输出: -2147483648  
解释: 数字 “-91283472332” 超过 32 位有符号整数范围。  
因此返回 INT\_MIN (−231) 。

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/string-to-integer-atoi  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。  
思路：

class Solution
    { 
      public:
    	int myAtoi(string str)
    	{ 
    		double result = 0;
    		int tag = 1;
    		int frist = 0;
    		while (str[frist] == ' ')
    			frist++;
    
    		switch (str[frist])
    		{ 
    		case '-':
    			frist++;
    			tag = -1;
    			break;
    		case '+':
    			frist++;
    			break;
    		}
    
    		for (int i = frist; i < str.size(); i++)
    		{ 
    
    			if (str[i] <= '9' && str[i] >= '0')
    				result = result * 10 + (str[i] - '0');
    			else
    				break;
    		}
    		result *= tag;
    		if (result > INT_MAX)
    			return INT_MAX;
    		else if (result < INT_MIN)
    			return INT_MIN;
    		else
    			return result;
    	}
    };

# 链表 #

### 1.链表的逆置 ###

> `当打算修改输入的数据时，最好问清面试官是否可以！！！`

思路：

1.  使用栈的结构，时间复杂度O(n),空间复杂度O(n)
2.  递归，时间复杂度O(n),空间复杂度O(n)，由于使用递归，将会使用隐式栈空间。递归深度可能会达到 n 层。
3.  修改输入数据，逆置链表，时间复杂度O(n),空间复杂度O(1)

*  使用栈的结构

/** * struct ListNode { * int val; * struct ListNode *next; * ListNode(int x) : * val(x), next(NULL) { * } * }; */
    class Solution
    { 
    public:
        vector<int> printListFromTailToHead(ListNode *head)
        { 
            vector<int> res;
            std::stack<ListNode *> QQ;
            ListNode *p = head;
            while (p)
            { 
                QQ.push(p);
                p = p->next;
            }
            while (!QQ.empty())
            { 
                res.push_back(QQ.top()->val);
                QQ.pop();
            }
            return res;
        }
    };

*  递归的方式

class Solution { 
    public:
        ListNode* reverseList(ListNode* head) { 
            // 0 node || at the end of list
            if (head == nullptr || head->next == nullptr) { 
                return head;
            }
            ListNode* HEAD = reverseList(head->next);
            head->next->next = head;
            head->next = NULL;
            return HEAD;
        }
    };

*  迭代的方式(头插法嘛)

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */
    class Solution
    { 
    public:
        ListNode *reverseList(ListNode *head)
        { 
            if (head == nullptr)
                return nullptr;
            ListNode *prev = nullptr;
            ListNode *curr = head;
            ListNode *nextTemp = nullptr;
            while (curr)
            { 
                nextTemp = curr->next;
                curr->next = prev;
                prev = curr;
                curr = nextTemp;
            }
            return prev;
        }
    };

### 2.在O(1)时间内删除链表节点 ###

请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点，你将只被给定要求被删除的节点。  
输入: head = \[4,5,1,9\], node = 5  
输出: \[4,1,9\]  
解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.

思路：OK。`我们现在知道了需要删除的节点。那么我们把后面节点的内容覆盖到前面需要删除的节点，然后把后面的节点删除掉就行了呗。`

时间复杂度O(1)

注意有几大坑点：

*  只有一个节点，删除节点位于头节点（也是尾节点）
 *  删除节点位于尾节点
 *  需要调用者确保要删除的节点在该链表中。

void DeleteNode(ListNode *head, ListNode *deListNode)
    { 
        if (deListNode == nullptr || head == nullptr)
            return;
        //1.普通情况
        if (deListNode->next)
        { 
            ListNode *p = deListNode->next;
    
            deListNode->val = deListNode->next->val;
            deListNode->next = deListNode->next->next;
            delete p;
            p = nullptr;
        }
        //2.只有一个节点
        else if (head == deListNode)
        { 
            delete deListNode;
            deListNode = nullptr;
            head = nullptr;
        }
        //3.删除的节点是尾节点
        else
        { 
            ListNode *p = head;
            while (p->next != deListNode)
            { 
                p = p->next;
            }
            p->next = nullptr;
            delete deListNode;
            deListNode = nullptr;
        }
    }

### 3.链表中的倒数第k个节点 ###

输入一个链表，输出该链表中倒数第k个结点。

思路：双指针思路。时间复杂度 O(n)

/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { } };*/
    class Solution
    { 
    public:
        ListNode *FindKthToTail(ListNode *head, unsigned int k)
        { 
            if (head == nullptr || k == 0)
                return nullptr;
    
            ListNode *p1 = head;
            ListNode *p2 = head;
        
            for (int i = 0; i < k-1 ; i++) //注意 k-1 
            { 
                if (p2->next)
                    p2 = p2->next;
                else //如果 k 比链表整个的长度还要长，怎么办？
                    return nullptr;
            }
            while (p2->next)//不需要循环到 nullptr 
            { 
                p1 = p1->next;
                p2 = p2->next;
            }
            return p1;
        }
    };

拓展：`找最中间的节点和判断是否成环也是双指针的思路`

### 4.合并两个排序的链表 ###

### 5.两个链表的第一个公共节点 ###

### 6.环形链表（圆圈中最后剩下的数字） ###

*  约瑟夫环的问题。时间复杂度O(MN),空间复杂度O(N)

class Solution
    { 
    public:
        int LastRemaining_Solution(int n, int m)
        { 
            if (n < 1 || m < 1)
                return -1;
    
            std::list<int> ll;
            for (int i = 0; i < n; i++)
                ll.push_back(i);
    
            auto it = ll.begin();
            while (ll.size() != 1)
            { 
                for (int i = 0; i < m - 1; i++)
                { 
                    it++;
                    if (it == ll.end())
                        it = ll.begin();
                }
                //删除 第 m 个
                auto tmp = it;
                it++;
                if (it == ll.end())
                    it = ll.begin();
                ll.erase(tmp);
            }
            return *it;
        }
    };

*  经过上面复杂的分析，我们终于找到了一个递归公式。`要得到n个数字的序列中最后剩下的数字，只需要得到n-1个数字的序列中最后剩下的数字，并以此类推`。当n=1时，也就是序列中开始只有-一个数字0,那么很显然最后剩下的数字就是0。我们把这种关系表示为:  
    ![在这里插入图片描述][20190929232138832.png]  
    时间复杂度O(n)，空间复杂度O(1)

class Solution
    { 
    public:
        int LastRemaining_Solution(int n, int m)
        { 
            if (n < 1 || m < 1)
                return -1;
                
            int last = 0;
            for (int i = 2; i <= n; i++)
                last = (last + m) % i;
            return last;
        }
    };

### 7.二叉搜索树与双向链表 ###

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。  
思路：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXNoZW5neGlfcm9vdA_size_16_color_FFFFFF_t_70 4]  
时间复杂度O (n)

/* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } };*/
    class Solution { 
    public:
        //左 根 右
        TreeNode *lastMax = nullptr ;
        void ConvertNode(TreeNode* node){ 
           if(node)
            { 
                if(node->left)
                    ConvertNode(node->left);
                
                node->left = lastMax;
                if(lastMax)
                    lastMax->right = node;
                lastMax = node ;
                
                if(node->right)
                    ConvertNode(node->right);
            }
        }
        TreeNode* Convert(TreeNode* root)
        { 
            if(root == nullptr )
               return nullptr;
             //先找到需要返回的节点的指针
            TreeNode *ret = root;
            while(ret->left)
                ret = ret->left;
             
            ConvertNode(root);
             
            return ret;
        }
    };

### 8.复杂链表的复制 ###

给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。

要求返回这个链表的深拷贝。

class Solution
    { 
    public:
        //1.复制节点
        void CloneNodes(Node *pHead)
        { 
            Node *p = pHead;
            while (p)
            { 
                Node *pNew = new Node(p->val, nullptr, nullptr);//一定要置空，不然过不了
                pNew->next = p->next; //节点的中间插入法
                p->next = pNew;
                p = pNew->next;
            }
        }
        //2.设置 random 指针
        void SetRandom(Node *pHead)
        { 
            Node *p = pHead;
            Node *pClone = nullptr;
            while (p)
            { 
                pClone = p->next;
                if (p->random)
                { 
                    pClone->random = p->random->next;
                }
                p = pClone->next;
            }
        }
        //3.将复制链表从原链表分离。
        Node *GetResult(Node *head)
        { 
            Node *node = head;
            Node *newHead = head->next;
            Node *newNode = head->next;
            while (node != nullptr)
            { 
                node->next = node->next->next;
                if (newNode->next != nullptr)
                { 
                    newNode->next = newNode->next->next;
                }
                node = node->next;
                newNode = newNode->next;
            }
            return newHead;
        }
    
        Node *copyRandomList(Node *pHead)
        { 
            if (pHead == nullptr)
                return nullptr;
            CloneNodes(pHead);
            SetRandom(pHead);
            return GetResult(pHead);
        }
    };

# 树 #

### 0.树三种递归&&非递归遍历&&层次遍历 ###

[二叉树基本数学知识，建立及三种递归遍历][Link 2]

[二叉树的三种非递归遍历和层次遍历][Link 3]

### 1.重建二叉树 ###

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列\{1,2,4,7,3,5,6,8\}和中序遍历序列\{4,7,2,1,5,3,8,6\}，则重建二叉树并返回。

思路：

*  `前序遍历序列的第一个节点是根节点，可以根据根节点将中序遍历序列划分成左子树区间和右子树区间`。根据左子树和右子树节点的个数，又可以将前序遍历序列划分成左子树区间和右子树区间。因此得到了**左子树的前序遍历序列和中序遍历序列、右子树的前序遍历序列和中序遍历序列。递归构造左右子树**

class Solution
    { 
    public:
        TreeNode *buildTree(vector<int> &pre, vector<int> &vin)
        { 
            if (pre.empty() || vin.empty() || (pre.size() != vin.size()))
            { 
                return nullptr;
            }
            return reConstructBinaryTreeCore(pre, 0, pre.size() - 1, vin, 0, vin.size() - 1);
        }
    
        TreeNode *reConstructBinaryTreeCore(const vector<int> &pre, int preL, int preR,
                                            const vector<int> &vin, int vinL, int vinR)
        { 
            if (preL > preR)
                return nullptr;
    
            TreeNode *root = new TreeNode(pre.at(preL));
    
            int i = vinL;
            for (; i <= vinR; i++)
            { 
                if (vin.at(i) == pre.at(preL))
                    break;
            }
    
            int leftsz = i - vinL;
            int rightsz = vinR - i;
    
            root->left = reConstructBinaryTreeCore(pre, preL + 1, preL + leftsz, 
            vin, vinL, i - 1);
            
            root->right = reConstructBinaryTreeCore(pre, preL + leftsz + 1, preR, 
            vin, i + 1, vinR);
    
            return root;
        }
    };

### 2.二叉树的深度 ###

输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。时间复杂度为O(N)，空间复杂度为O(logN)。  
思路：

*  如果没有左右子树，深度为1  
    如果只有左子树，深度为左子树深度加1  
    如果只有右子树，深度为右子树深度加1  
    如果都有，深度为左子树和右子树深度较大者加1

class Solution { 
    public:
        int TreeDepth(TreeNode* pRoot)
        { 
            if(!pRoot)
                return 0;
            int left = TreeDepth(pRoot->left);
            int right = TreeDepth(pRoot->right);
            
            return (left > right)? left+1 : right+1;
        }
    };

### 2.1 平衡二叉树 ###

给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。

示例 1:

给定二叉树 \[3,9,20,null,null,15,7\]

/  
9 20  
/  
15 7  
返回 true 。

示例 2:

给定二叉树 \[1,2,2,3,3,null,null,4,4\]

1
      / \
     2   2
    / \

3 3  
/  
4 4  
返回 false 。

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/balanced-binary-tree

思路：

*  1.对每一个节点分别求左右子树的高度，然后通过遍历所有节点得到答案。这样**会重复遍历树的节点。让我想起了美团出的那道面试题，难怪人家会问我还有更好的解决方案吗？?**

class Solution
    { 
    public:
        int getDeep(TreeNode *root)
        { 
            if (!root)
                return 0;
            int ll = getDeep(root->left);
            int rr = getDeep(root->right);
    
            return ll > rr ? ll + 1 : rr + 1;
        }
        bool isBalanced(TreeNode *root)
        { 
            if (root)
            { 
                int ll = getDeep(root->left);
                int rr = getDeep(root->right);
    
                if (std::abs(ll - rr) > 1)
                { 
                    return false;
                }
                return isBalanced(root->left) && isBalanced(root->right);
            }
            return true;
        }
    };

*  2.在求高度的过程中判断是否是平衡二叉树。**这样子每个节点只遍历一遍的解法，才是面试官想要的东西**。

class Solution
    { 
    public:
        int getDeep(TreeNode *root)
        { 
            if (!root)
                return 0;
    
            int ll = getDeep(root->left);
            if (ll == -1)
                return -1;
    
            int rr = getDeep(root->right);
            if (rr == -1)
                return -1;
    
            //这里就已经是递归计算高度了，直接使用一下
            if (std::abs(ll - rr) > 1)
            { 
                return -1;
            }
            else
            { 
                return 1 + std::max(ll, rr);
            }
        }
        bool isBalanced(TreeNode *root)
        { 
            if (getDeep(root) == -1)
                return false;
            else
                return true;
        }
    };

### 3.树的子结构 ###

输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

思路：

*  先判断当前以及对应的左右子树，这是比较完整的一颗树的流程。  
    然后 如果当前的就不满足要求的话，就看左子树与其的对比。右子树也相同。

class Solution
    { 
      public:
    	bool HasSubtree(TreeNode *s, TreeNode *t)
    	 { 
            if (s == nullptr || t == nullptr)
                return false;
            bool ret = false;
            //完整的判断是否相同
            if (t->val == s->val)
            { 
                //判断左右子树
                ret = sameTree(s->left, t->left) && sameTree(s->right, t->right);
                if (ret)
                    return true;
            }
            return (HasSubtree(s->left, t) || HasSubtree(s->right, t));
        }
        bool sameTree(TreeNode *p1, TreeNode *p2)
        { 
            if (p2 == nullptr)
                return true;
            if (p1 == nullptr)
                return false;
    
            if (p1->val == p2->val)
                return sameTree(p1->left, p2->left) && sameTree(p1->right, p2->right);
            else 
                return false;
        }
    };

### 4.二叉树中和为某一值的路径 ###

输入一颗二叉树的根节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的**根结点开始往下一直到叶结点**所经过的结点形成一条路径。

思路：  
当用前序遍历的方式访问到某一节点时，把该节点添加到路径(vector)上，并累加该节点的值

*  如果节点为叶节点，并且路径中节点值的和刚好等于输入的整数，则当前路径符合要求，打印出来
 *  如果不是叶节点，继续访问子节点

当前节点访问结束后，递归函数将自动回到它的父节点。因此，在函数退出之前要在路径上删除当前节点并减去当前节点的值，以确保返回父节点时路径刚好是从根节点到父节点

class Solution
    { 
    public:
        vector<vector<int>> res;
        void fun(TreeNode *root, int expectNumber, int curSum, vector<int> &path)
        { 
            curSum += root->val;
            　path.push_back(root->val);
    
            bool isLeaf = (root->left == nullptr) && (root->right == nullptr);
            if (isLeaf && curSum == expectNumber)
                res.push_back(path);
    
            if (root->left)
                fun(root->left, expectNumber, curSum, path);
            if (root->right)
                fun(root->right, expectNumber, curSum, path);
    
            path.pop_back();
            curSum -= root->val;
        }
        vector<vector<int>> FindPath(TreeNode *root, int expectNumber)
        { 
            if (root == nullptr)
                return res;
    
            vector<int> path;
            fun(root, expectNumber, 0, path);
            return res;
        }
    };

### 5.二叉树的后序遍历序列 ###

### 6.从上到下遍历二叉树 ###

### 8.树中两个节点的最近公共祖先 lowest-common-ancestor问题 ###

##### (1) 树是二叉搜索树 #####

思路就是如果两个节点都比当前的节点大，那么最近公共祖先一定在右子树。  
如果两个节点都比当前的节点小，那么最近公共祖先一定在左子树。  
否则当前节点就是所需要的节点。  
时间O(n)，空间O(n)

class Solution
    { 
    public:
        TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q)
        { 
            if (!root || !p || !q)
                return nullptr;
                
            if (root->val > std::max(p->val, q->val))
                return lowestCommonAncestor(root->left, p, q);
            else if (root->val < std::min(p->val, q->val))
                return lowestCommonAncestor(root->right, p, q);
            else
                return root;
        }
    };

##### (2) 树是普通的二叉树 #####

思路 1：

*  在左、右子树中分别查找是否包含p或q：
 *  如果以下两种情况（左子树包含p，右子树包含q/左子树包含q，右子树包含p），那么此时的根节点就是最近公共祖先
 *  如果左子树包含p和q，那么到root->left中继续查找，最近公共祖先在左子树里面
 *  如果右子树包含p和q，那么到root->right中继续查找，最近公共祖先在右子树里面

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

思路 2：（`适用于普遍的树，不只是二叉树`）

用两个容器 ，保存从根节点到输入的两个节点的路径，然后把问题转换成求两个链表的最后最后公共节点。时间复杂度O(logn) ，空间复杂度O(logn)

class Solution
    { 
        vector<vector<TreeNode *>> paths;
        vector<TreeNode *> path;
    
    public:
        TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q)
        { 
            if (!root || !p || !q)
                return nullptr;
            if (p == q)
                return p;
    
            dfs(root, p, q); //dfs 找到两条路径
            // 去找最后相同的一个数字即可
            if (paths.size() != 2)
                return nullptr;
    
            int idx = 0;
            while (idx < paths[0].size() && idx < paths[1].size() && paths[0][idx]->val == paths[1][idx]->val)
            { 
                idx++;
            }
            return paths[0][idx - 1];
        }
    private:
        void dfs(TreeNode *root, TreeNode *p, TreeNode *q)
        { 
            if (!root)
                return;
            path.push_back(root);
    
            if (root == p || root == q)
                paths.push_back(path);
    
            if (root->left)
                dfs(root->left, p, q);
            if (root->right)
                dfs(root->right, p, q);
    
            path.pop_back();
        }
    };

##### (3) 树的节点中存在指向父节点的指针 #####

思路：通过所给的节点去逆着将每个节点串联起来，直到到达根节点。然后就是找两个链表的公共节点的问题。时间复杂度O(n)。空间复杂度O(n)

### 9.二叉树的镜像与对称的问题 ###

##### (1) 二叉树的镜像 #####

操作给定的二叉树，将其变换为源二叉树的镜像。

class Solution { 
    public:
        void Mirror(TreeNode *pRoot) { 
            if(pRoot)
            { 
                std::swap(pRoot->left,pRoot->right);
                Mirror(pRoot->left);
                Mirror(pRoot->right);
            }
        }
    };

##### (2)对称的二叉树 #####

请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。

递归：

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

迭代：二叉树的层次遍历，然后就是判断是不是回文数组！！！

class Solution
    { 
    public:
        bool isSymmetric(TreeNode *root)
        { 
            if (!root)
                return true;
    
            std::queue<TreeNode *> QQ;
            QQ.push(root);
    
            while (!QQ.empty())
            { 
                int len = QQ.size();
                vector<int> vv;
                for (int i = 0; i < len; i++)
                { 
                    TreeNode *tmp = QQ.front();
                    QQ.pop();
    
                    if (!tmp)
                    { 
                        vv.push_back(-100);//特殊值，独一无二的值
                    }
                    else
                    { 
                        vv.push_back(tmp->val);
                        QQ.push(tmp->left); 
                        //这里就会将空指针也给 push 进去，在这道题中是需要这样做的。
                        QQ.push(tmp->right);
                    }
                }
                //判断是不是回文数组
                for (int j = 0; j < vv.size() / 2; j++)
                { 
                    if (vv[j] != vv[vv.size() - 1 - j])
                        return false;
                }
            }
            return true;
        }
    };

##### (3) #####

### 9.二叉搜索树与双向链表 ###

### 10.求最小的k个数字与求第k小的数字的问题 ###

# 栈和队列 #

### 1.栈的压入、弹出序列 ###

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）

思路：

*  将 pushed 队列中的每个数都 push 到栈中，同时检查这个数是不是 popped 序列中下一个要 pop 的值，如果是就把它 pop 出来。

最后，检查不是所有的该 pop 出来的值都是 pop 出来了。时间复杂度O(n)，空间复杂度O(n)

class Solution { 
    public:
        bool validateStackSequences(vector<int>& pushV, vector<int>& popV) { 
            if (pushV.empty() || popV.empty() || pushV.size() != popV.size())
                return true;
            std::stack<int> QQ;
            int index = 0;
            // 遍历的是 push 序列
            for (const auto &it : pushV)
            { 
                QQ.push(it);
                //栈不空 数组下标不越界 （如果不相等就继续把 push 序列的数字压入栈中）
                while (!QQ.empty() && index < pushV.size() && QQ.top() == popV[index])
                { 
                    QQ.pop();
                    index++;
                }
            }
            return index == pushV.size();
        }
    };

# 位运算 #

# 动态规划和贪心 #

### 1.最大子序和 ###

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例:

输入: \[-2,1,-3,4,-1,2,1,-5,4\],  
输出: 6  
解释: 连续子数组 \[4,-1,2,1\] 的和最大，为 6。

链接：[https://leetcode-cn.com/problems/maximum-subarray][https_leetcode-cn.com_problems_maximum-subarray]

思路：

*  贪心 。`如果之前的数值状态不会对我们当前的数值产生减幅，就将其加入进来` 。时间复杂度O(n),空间复杂度O(1)

class Solution
    { 
      public:
        int maxSubArray(vector<int> &nums)
        { 
            int before = 0;
            int result = nums[0];
            //贪心法 O(n) 的解法
            for (int i = 0; i < nums.size(); i++)
            { 
                if (before > 0) //注意判断的是 before 
                    before += nums[i];
                else
                    before = nums[i];
                
                if (before > result) result = before;
            }
            return result;
        }
    };

*  DP ,dp数组表示以 i 为右端点的最大子序和。时间复杂度O(n),空间复杂度O(n)

class Solution
    { 
    public:
        int maxSubArray(vector<int> &vv)
        { 
            if (vv.size() <= 0)
                return -1;
            vector<int> dp(vv.size());
            int res = vv[0];
            dp[0] = vv[0];
            
            for (int i = 1; i < vv.size(); i++)
            { 
                dp[i] = std::max(vv[i], vv[i] + dp[i - 1]); //DP 方程
                if (res < dp[i])
                    res = dp[i];
            }
            return res;
        }
    };

*  分治法 时间O(nlogn)，空间O(1)

### 2.剪绳子/切割杆的问题 ###

给你一根长度为n的绳子，请把绳子剪成m段（m、n都是整数，n>1并且m>1），每段绳子的长度记为k\[0\],k\[1\],…,k\[m\]。请问k\[0\]xk\[1\]x…xk\[m\]可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。

思路：

*  贪心 / 动态规划

动态规划：  
设f(n)代表长度为n的绳子剪成若干段的最大乘积，如果第一刀下去，第一段长度是i，那么剩下的就需要剪n-i，那么 `f(n)=max{f(i)*f(n-i)}`。而f(n)的最优解对应着f(i)和f(n-i)的最优解，假如f(i)不是最优解，那么其最优解和f(n-i)乘积肯定大于f(n)的最优解，和f(n)达到最优解矛盾，`所以f(n)的最优解对应着f(i)和f(n-i)的最优解。`

首先，剪绳子是最优解问题，其次，大问题包含小问题，并且大问题的最优解包含着小问题的最优解，所以可以使用动态规划求解问题，并且从小到大求解，把小问题的最优解记录在数组中，求大问题最优解时就可以直接获取，避免重复计算。

n<2时，由于每次至少减一次，所以返回0。n=2时，只能剪成两个1，那么返回1。n=3时，可以剪成3个1，或者1和2，那么最大乘积是2。当n>3时，就可以使用公式进行求解。

f(4)=max{ f(1)f(3), f(2)f(2)}
        f(5)=max{ f(1)f(4), f(2)f(3)}`
        ...
        f(n)=max{ f(1)f(n-1), f(2)f(n-2), f(3)f(n-3), ..., f(i)(fn-i), ...}

class Solution
    { 
    public:
        int cutRope(int n)
        { 
            if (n < 2)
                return 0;
            if (n == 2)
                return 1;
            if (n == 3)
                return 2;
    
            vector<int> dp(n + 1, 0);
            //数组中第i个元素表示 把长度为i的绳子剪成 若干段之后 各段长度乘积的最大值
    
            dp[1] = 0;
            dp[1] = 1;
            dp[2] = 2;
            dp[3] = 3;
    
            for (int i = 4; i <= n; i++)
            { 
                int Max = 0;
                for (int j = 1; j <= i / 2; j++)
                { 
                    int product = dp[j] * dp[i - j];
                    if (product > Max)
                        Max = product;
                }
                dp[i] = Max;
            }
            return dp[n];
        }
    };

贪心：（需要一定的数学知识，暂时略）

### 3.动态规划:字符串编辑距离(edit distance) ###

Posted on 2017-05-21 | In 动态规划  
转载请注明出处：blog.justkitt.com

问题描述  
有两个字符串A和B，现在将A经过三种变换可以得到B，即插入、删除和修改，这三种操作的代价分别为c0,c1和c2，问题就是A到B的变换所需要的最小代价是多少。

思路  
典型的动态规划问题，娇哥曾经说过，字符串的问题大部分都是动态规划的问题，那么这个问题要怎么解决呢？动态规划问题首先定义状态，然后定义状态转移方程，然后确定初始状态和终止状态，然后就可以得到终止状态下的结果输出。

定义状态  
我们定义状态dp\[i\]\[j\]表示A从0-i和B从0-j这两段的最小编辑距离。状态的定义需要注意的是，状态只能和前面的情况有联系不能和后面的情况有联系。

转移方程  
有了状态，那么就定义状态转移方程，状态转移方程的定义有时候会需要“找规律”，但是这道题的规律比较明显，很容易知道，当A\[i\] == B\[j\]的时候，从dp\[i-1\]\[j-1\]到dp\[i\]\[j\]是不需要任何编辑的，所以dp\[i-1\]\[j-1\] = dp\[i\]\[j\]，但是当他们不相等的时候，就需要考虑是插入、删除还是编辑的代价最短了，那么自然而然地有三种情况：插入，删除和编辑。插入的情况是什么？

插入是A在和B的前j-1个比，然后再在A的基础上进行插入一个字符，插入的字符是B的第j位，所以插入的代价是dp\[i\]\[j-1\]+c0  
删除是A的前i-1个和B的j个比，因为把A删除了一个字符，所以删除的代价是dp\[i-1\]\[j\]+c1  
编辑是A的前i-1个和B的j-1个比，然后把A的第i位变成B的第j位。所以编辑的代价是dp\[i-1\]\[j-1\]+c2  
由以上分析，可以得到状态转移方程如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXNoZW5neGlfcm9vdA_size_16_color_FFFFFF_t_70 5]  
有了状态转移方程，代码就很好写了。代码如下

int findMinCost(string A, int n, string B, int m, int c0, int c1, int c2) { 
        vector<vector<int>> dp(n+1,vector<int>(m+1,0));
        for(int i = 1;i<=m;++i){ 
            dp[0][i] = dp[0][i-1]+c0;
        }
        for(int i = 1;i<=n;++i){ 
            dp[i][0] = dp[i-1][0] + c1;
        }
        for(int i = 1;i<=n;++i){ 
            for(int j = 1;j<=m;++j){ 
                if(A[i-1] == B[j-1])
                    dp[i][j] = dp[i-1][j-1];
                else
                    dp[i][j] = min(min(dp[i-1][j]+c1,dp[i-1][j-1]+c2),
                    dp[i][j-1]+c0);
            }
        }
        return dp[n][m];

###  ###

# 回溯法和DFS，BFS #

### 1.矩阵中的路径/单词搜索 ###

请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。 例如 a b c e s f c s a d e e 矩阵中包含一条字符串"bcced"的路径，但是矩阵中不包含"abcb"路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXNoZW5neGlfcm9vdA_size_16_color_FFFFFF_t_70 6]

思路：DFS

class Solution
    { 
    private:
        int dir[4][2] = { { 1, 0}, { 0, 1}, { -1, 0}, { 0, -1}};
        int row = 0;
        int col = 0;
    
    public:
        bool check(vector<vector<char>> &board,
                   const string &word, const int pathLength, int rr, int cc)
        { 
            if (rr < 0 || rr > row - 1)
                return false;
            if (cc < 0 || cc > col - 1)
                return false;
            if (board[rr][cc] != word[pathLength])
                return false;
    
            return true;
        }
        bool dfs(vector<vector<char>> &board, const string &word,
                 int pathLength, int r, int c, vector<vector<int>> &visted)
        { 
            if (pathLength == word.size())
                return true;
    
            for (int i = 0; i < 4; i++)
            { 
                int rr = r + dir[i][0];
                int cc = c + dir[i][1];
    
                if (check(board, word, pathLength, rr, cc) && visted[rr][cc] != 1)
                { 
                    visted[rr][cc] = 1;
    
                    if (dfs(board, word, pathLength + 1, rr, cc, visted)) //注意这里的 pathLength + 1
                        return true;
    
                    visted[rr][cc] = 0;
                }
            }
            return false;
        }
        bool exist(vector<vector<char>> &board, string word)
        { 
            if (word == "")
                return true;
            if (board.empty())
                return false;
    
            row = board.size();
            col = board[0].size();
    
            vector<vector<int>> visted(row, vector<int>(col, 0));
    
            int pathLength = 0;
            for (int i = 0; i < row; i++)
            { 
                for (int j = 0; j < col; j++)
                { 
                    if (visted[i][j] != 1 && board[i][j] == word[0])
                    { 
                        visted[i][j] = 1;
                        if (dfs(board, word, pathLength + 1, i, j, visted))
                            return true;
                        visted[i][j] = 0;
                    }
                }
            }
            return false;
        }
    };

简单优化就是直接将 board 修改掉来表示是否走过 ，不实用辅助空间visted，从而降低空间复杂度。

### 2.子集 ###

/*给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。  
说明：解集不能包含重复的子集。  
示例:  
输入: nums = \[1,2,3\]  
输出:  
\[  
\[3\],  
\[1\],  
\[2\],  
\[1,2,3\],  
\[1,3\],  
\[2,3\],  
\[1,2\],  
\[\]  
\]*/

class Solution
    { 
      public:
        vector<vector<int>> subsets(vector<int> &nums)
        { 
            result.push_back(path);
    
            dfs(0, nums);
    
            return result;
        }
    
      private:
        vector<vector<int>> result;
        vector<int> path;
    
        void dfs(int index, const vector<int> &nums)
        { 
            for (int i = index; i < nums.size(); i++)
            { 
                path.push_back(nums[i]);
                result.push_back(path);
                
                //便于理解
                for(auto i:path)
                    cout << i<<" ";
                cout << endl;
                
                dfs(i+1, nums);
                path.pop_back();
            }
        }
    };

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXNoZW5neGlfcm9vdA_size_16_color_FFFFFF_t_70 7]

### 3. ###

# k 数之和的问题 #

### 1.两数之和 ###

思路：

*  哈希表维护 数值到下标的映射。时间O(n)，空间O(n)

class Solution
    { 
    public:
        vector<int> twoSum(vector<int> &nums, int target)
        { 
            unordered_map<int, int> map;
            vector<int> res;
            for (int i = 0; i < nums.size(); i++)
            { 
                if (map.find(target - nums[i]) != map.end())
                { 
                    res.push_back(map[target - nums[i]]);
                    res.push_back(i);
                    return res;
                }
                map[nums[i]] = i;
            }
            return res;
        }
    };

### 2.两数之和 II - 输入有序数组 ###

给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。

函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。

说明:

返回的下标值（index1 和 index2）不是从零开始的。  
你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted

思路：

*  双指针思想，时间复杂度O(n)，空间复杂度O(1)

class Solution
    { 
    public:
       vector<int> twoSum(vector<int> &numbers, int target)
       { 
           if (numbers.size() < 2)
               return { };
    
           int start = 0, end = numbers.size() - 1;
    
           while (start < end)
           { 
               int addUp = numbers[start] + numbers[end];
               if (addUp > target)
                   end--;
               else if (addUp < target)
                   start++;
               else
                   return { start + 1, end + 1};
           }
           return { };
       }
    };

### 3.两数之和 IV - 输入 BST ###

给定一个二叉搜索树和一个目标结果，如果 BST 中存在两个元素且它们的和等于给定的目标结果，则返回 true。

案例 1:

输入:  
5  
/  
3 6  
/ \\  
2 4 7

Target = 9

输出: True

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/two-sum-iv-input-is-a-bst

思路：

*  1.HashSet 法  
    任意方法遍历，通过把遍历的值记录到 set 中，然后在遍历的过程中通过 set.contains(target - node.val) 来判断是否存在。

时间复杂度 O(N)，空间复杂度 O(N)

*  2.双指针法  
    通过中序遍历可以把值存入一个 list 中，而且该 list 中的值升序排列。我们可以用两个指针分别指向头和尾，然后通过判断他们的和与 target 的大小关系来移动头指针或者尾指针，最终得出结果。

时间复杂度 O(N)，空间复杂度 O(N)

*  3.BST 查找法

时间复杂度 O(NlogN)，空间复杂度 O(1)

class Solution
    { 
    public:
        TreeNode *findNum(TreeNode *root, int num)
        { 
            if (root == nullptr)
                return nullptr;
            if (root->val == num)
                return root;
            else if (root->val > num)
                return findNum(root->left, num);
            else
                return findNum(root->right, num);
        }
        bool fun(TreeNode *node, TreeNode *root, int k) // O(n)
        { 
            if (node == nullptr)
                return false;
            TreeNode *p = findNum(root, k - root->val); // O(logN)
            if (p == nullptr || p == node)
                return fun(node->left, root, k) || fun(node->right, root, k);
            else
                return true;
        }
        bool findTarget(TreeNode *root, int k)
        { 
            if (root == nullptr)
                return false;
            return fun(root, root, k);
        }
    };

### 4.三数之和 ###

给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。

注意：答案中不可以包含重复的三元组。

例如, 给定数组 nums = \[-1, 0, 1, 2, -1, -4\]，

满足要求的三元组集合为：  
\[  
\[-1, 0, 1\],  
\[-1, -1, 2\]  
\]

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/3sum  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXNoZW5neGlfcm9vdA_size_16_color_FFFFFF_t_70 8]

class Solution
    { 
    public:
        vector<vector<int>> threeSum(vector<int> &nums)
        { 
            vector<vector<int>> result;
            int len = nums.size();
            if (len < 3)
                return result;
    
            sort(nums.begin(), nums.end()); //先转换成有序向量
    
            for (int i = 0; i < len; ++i)
            { 
                if (nums[i] > 0)
                    break; // 如果当前数字大于0，则三数之和一定大于0，所以结束循环
                if (i > 0 && nums[i] == nums[i - 1])
                    continue; //去重
    
                int L = i + 1;
                int R = len - 1;
    
                while (L < R)
                { 
                    int sum = nums[i] + nums[L] + nums[R]; //转换成两数之和的问题
                    if (sum == 0)
                    { 
                        result.push_back({ nums[i], nums[L++], nums[R--]});
                        while (L < R && nums[L] == nums[L - 1])
                            L++; //L跳过重复元素
                        while (L < R && nums[R] == nums[R + 1])
                            R--; //R跳过重复元素
                    }
                    else if (sum > 0)
                        R--; //sum(两数和)较大时，R左移
                    else
                        L++; //sum 较小时，L右移
                }
            }
            return result;
        }
    };

### 5.和为S的连续正数序列 ###

小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck!

思路：

*  同两数之和的双指针的思路。时间O(n)，空间最坏 O(n)

class Solution
    { 
    public:
        vector<vector<int>> FindContinuousSequence(int sum)
        { 
            vector<vector<int>> res;
            if (sum < 3)
                return res;
    
            int small = 1;
            int big = 2;
    
            int curSum = small + big;
    
            //当small > mid 时，自然就不会形成 == sum 的情况了
            while (small <= sum / 2)
            { 
                if (curSum > sum)
                { 
                    curSum -= small; //注意这里与下面的代码顺序不同
                    small++;
                }
                else if (curSum < sum)
                { 
                    big++;
                    curSum += big;
                }
                else
                { 
                    vector<int> tmp;
                    for (int i = small; i <= big; i++)
                        tmp.push_back(i);
                    res.push_back(tmp);
                    tmp.clear();
    
                    big++;
                    curSum += big; //继续移动 big ,找下一个序列！！！
                }
            }
            return res;
        }
    };

*  拓展：  
    最接近的三数之和  
    中等  
    四数之和  
    中等  
    较小的三数之和

# 发散思维题以及单例的实现 #

### 1.使用C++实现单例 ###

[C++如何实现单例模式？][C]

### 2. ###

### 3. ###

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXNoZW5neGlfcm9vdA_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/066c155040f543f48d7c0c94b6107533.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXNoZW5neGlfcm9vdA_size_16_color_FFFFFF_t_70 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/9be5147f418842d1865ad9b63cef0501.png
[Link 1]: https://blog.csdn.net/liushengxi_root/article/details/84886544#2__45
[https_leetcode-cn.com_problemset_all_search_20_E6_97_8B_E8_BD_AC_E6_95_B0_E7_BB_84]: https://leetcode-cn.com/problemset/all/?search=%20%E6%97%8B%E8%BD%AC%E6%95%B0%E7%BB%84
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXNoZW5neGlfcm9vdA_size_16_color_FFFFFF_t_70 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/8ad8f8f24573462d8ab2c2445d9d4f99.png
[https_leetcode-cn.com_problems_merge-sorted-array]: https://leetcode-cn.com/problems/merge-sorted-array/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXNoZW5neGlfcm9vdA_size_16_color_FFFFFF_t_70 3]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/c7abc161259642e09782815f10773e1f.png
[https_leetcode-cn.com_problems_reverse-words-in-a-string]: https://leetcode-cn.com/problems/reverse-words-in-a-string
[https_leetcode-cn.com_problems_string-to-integer-atoi]: https://leetcode-cn.com/problems/string-to-integer-atoi/
[20190929232138832.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/d796a83a18b74e4e8091b5b4c96addaf.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXNoZW5neGlfcm9vdA_size_16_color_FFFFFF_t_70 4]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/d06a4f2d34a04d67be12c3c9fa81eb95.png
[Link 2]: https://blog.csdn.net/liushengxi_root/article/details/78536175
[Link 3]: https://blog.csdn.net/liushengxi_root/article/details/78588197
[https_leetcode-cn.com_problems_maximum-subarray]: https://leetcode-cn.com/problems/maximum-subarray
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXNoZW5neGlfcm9vdA_size_16_color_FFFFFF_t_70 5]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/23eb3eb745214160b60709f80863b4b3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXNoZW5neGlfcm9vdA_size_16_color_FFFFFF_t_70 6]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/7e86d38ce43c4dff94bba825987902a6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXNoZW5neGlfcm9vdA_size_16_color_FFFFFF_t_70 7]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/c9cc64ab6fe549f082d05b127cb37be0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXNoZW5neGlfcm9vdA_size_16_color_FFFFFF_t_70 8]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/1a6a85a0f62d4f118ddbf6f91f26c093.png
[C]: https://blog.csdn.net/liushengxi_root/article/details/79333246