JZ01 赋值运算符号函数

JZ02 替换空格

class Solution {
public:
    string replaceSpace(string s) {
        int spaceNum = count(s.begin(), s.end(), ' ');
        if (spaceNum==0) return s;
        s.append(spaceNum*2, '0');
        int i=s.size()-1, j=i-spaceNum*2;
        while (j >= 0)
        {
            if (s[j] == ' ')
            {
                j--;
                s[i--] = '0', s[i--] = '2', s[i--] = '%';
                continue;
            }
            s[i--] = s[j--];
        }
        return s;
    }
};

JZ03. 数组中重复的数字

题目
在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
示例 1：
输入：[2, 3, 1, 0, 2, 5, 3]输出：2 或 3
思路

先排序，第一次出现相连元素相同则返回。

根据题目条件，从头开始，依次将元素归位（（0,0），（1,1）……），当第一次出现当前元素和前一个元素相等时（这里指的是程序中的，不是真实数组里第一次出现相等），返回。

/*
当前面的元素都是连续的时候，返回的是第一个重复的元素，
当不连续时，返回的不一定是一个次重复的元素。
*/
class Solution {
public:
 int findRepeatNumber(vector<int>& nums) {
     for(int i=0;i<nums.size();++i){
        while(nums[i]!=i){ //将元素依次归位
            if(nums[i] == nums[nums[i]])//当前元素和前一个元素相等
                 return nums[i];
            swap(nums[i],nums[nums[i]]);
        }
     }
     return 0;
 }
};

JZ06 从尾到头打印链表

思路

使用栈

采用递归（递归层数深了效率降低）

class Solution {
public:
 vector<int> reversePrint(ListNode* head) {
     vector<int> res;
     stack<ListNode *> s;
     //插入stack
     ListNode* pHead = head;
     while(pHead != nullptr){
         s.push(pHead);
         pHead = pHead->next;
     }
     //打印
     while(!s.empty()){
         res.push_back(s.top()->val);
         s.pop();
     }
     return res;
 }
};

JZ07 重建二叉树（hard）

题目描述
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
思路
根据前序（根左右）和中序（左根右）的特点
前序第一个为根确定区间的根节点，根据中序确定根节点的左右子树。
依次递归区间，最后返回节点。

/**
* Definition for binary tree
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
 TreeNode* helper(vector<int> &pre, int ps, int pe, vector<int> &vin, int vs, int ve){
     if(ps>pe) return nullptr;
     TreeNode *node = new TreeNode(pre[ps]);
     int idx = vs;
     //找到区间中的中序遍历的根节点的索引idx
     for(;idx<=ve;++idx)
         if(vin[idx]==pre[ps])
             break;
     int subSpaceLength = idx - vs;//左子区间的长度
     node->left = helper(pre, ps+1,ps+subSpaceLength, vin, vs, idx-1);
     node->right = helper(pre,ps+subSpaceLength+1, pe, vin, idx+1, ve);
     return node;
 }
 TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
     return helper(pre,0,pre.size()-1,vin,0,vin.size()-1);
 }
};

```cpp class Solution { private: unordered_map index;

public: TreeNode* myBuildTree(const vector& preorder, const vector& inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right) { if (preorder_left > preorder_right) { return nullptr; }

    // 前序遍历中的第一个节点就是根节点
    int preorder_root = preorder_left;
    // 在中序遍历中定位根节点
    int inorder_root = index[preorder[preorder_root]];
    // 先把根节点建立出来
    TreeNode* root = new TreeNode(preorder[preorder_root]);
    // 得到左子树中的节点数目
    int size_left_subtree = inorder_root - inorder_left;
    // 递归地构造左子树，并连接到根节点
    // 先序遍历中「从 左边界+1 开始的 size_left_subtree」个元素就对应了中序遍历中「从 左边界 开始到 根节点定位-1」的元素
    root->left = myBuildTree(preorder, inorder, preorder_left + 1, preorder_left + size_left_subtree, inorder_left, inorder_root - 1);
    // 递归地构造右子树，并连接到根节点
    // 先序遍历中「从 左边界+1+左子树节点数目 开始到 右边界」的元素就对应了中序遍历中「从 根节点定位+1 到 右边界」的元素
    root->right = myBuildTree(preorder, inorder, preorder_left + size_left_subtree + 1, preorder_right, inorder_root + 1, inorder_right);
    return root;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    int n = preorder.size();
    // 构造哈希映射，帮助我们快速定位根节点
    for (int i = 0; i < n; ++i) {
        index[inorder[i]] = i;
    }
    return myBuildTree(preorder, inorder, 0, n - 1, 0, n - 1);
}

};

作者：LeetCode-Solution 链接：https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/solution/cong-qian-xu-yu-zhong-xu-bian-li-xu-lie-gou-zao-9/ 来源：力扣（LeetCode）著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

<a name="vzz1x"></a>
## [JZ08 二叉树的下一个节点](https://www.nowcoder.com/practice/9023a0c988684a53960365b889ceaf5e?tpId=13&&tqId=11210&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking)
**题目描述**<br />给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。<br />思路
<font color='red' size=5></font>
<a name="CpoVl"></a>
## [JZ09 变态跳台阶](https://www.nowcoder.com/practice/22243d016f6b47f2a6928b4313c85387?tpId=13&&tqId=11162&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking)
**题目描述**<br />一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。<br />思路<br /><font color='red' size=5></font>
<a name="awmYZ"></a>
## [JZ10矩形覆盖](https://www.nowcoder.com/practice/72a5a919508a4251859fb2cfb987a0e6?tpId=13&&tqId=11163&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking)
题目描述<br />我们可以用2_1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2_1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？<br />思路<br />动态规划：写出状态转移方程即可
```cpp
class Solution {
public:
    int rectCover(int number) {
        if(0==number || 1==number || 2==number)
            return number;
        int a = 1;
        int b = 2,c;
        for (int i = 3; i <= number; ++i) {
            c = a +b;
            a = b;
            b = c;
        }
        return c;
    }
};

JZ11 旋转数组的最小数字

题目描述
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
输入
[3,4,5,1,2]
返回值
1
思路
mid的两边一遍有序，一边无序
采用二分法缩小查找范围。根据所给的实例可以推断出当：
array[mid] >= array[low]时，则所选值在右边的区间。
反之，则在左边的区间。
low<high-1：当low=high-1时，low和high相连，直接返回high就是最小值。

class Solution {
public:
    int minNumberInRotateArray(vector<int> rotateArray) {
        if(rotateArray.size()==0) return 0;
        int len = rotateArray.size();
        int high = len-1, low = 0;
        while(low<high-1)   //这里的high-1很关键，不知道为啥
        {
            int mid = low + (high-low)/2;
            if(rotateArray[mid]>=rotateArray[low])
                low = mid;
            else
                high = mid;
        }
       return rotateArray[high];
    }
};

上面的解法不是常规的二分模板

待验证

int minArray(vector<int>& numbers)
{
    int l = 0, r = numbers.size()-1;
    while (l < r)
    {
        int mid = l + r >> 1;
        if (numbers[mid] <= numbers[r]) r = mid;
        else l = mid + 1;
    }
    return numbers[l];
}

此种解法无法处理「3，3，1，3」这种情况

当出现mid和r相等时，r前移

class Solution {
public:
    int minArray(vector<int>& numbers)
    {
        int l = 0, r = numbers.size()-1;
        while (l < r)
        {
            int mid = l + r  >> 1;
            if (numbers[mid] < numbers[r]) r = mid;
            else if (numbers[mid] > numbers[r]) l = mid + 1;
            else r--;
        }
        return numbers[l];
    }
};

JZ12 矩阵中的路径（hard）

题目
请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一格开始，每一步可以在矩阵中向左、右、上、下移动一格。如果一条路径经过了矩阵的某一格，那么该路径不能再次进入该格子。例如，在下面的3×4的矩阵中包含一条字符串“bfce”的路径（路径中的字母用加粗标出）。
[[“a”,”b“,”c”,”e”],[“s”,”f“,”c“,”s”],[“a”,”d”,”e“,”e”]]
但矩阵中不包含字符串“abfb”的路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入这个格子。
示例 1：
输入：board = [[“A”,”B”,”C”,”E”],[“S”,”F”,”C”,”S”],[“A”,”D”,”E”,”E”]], word = “ABCCED”
输出：true
思路
剑指offer - 图2
link

class Solution {
public:
    int x[4] = {0,0,-1,1}; //x[4]、y[4]和dfs中for循环，共同构成遍历字符board[i][j]的“左右上下”四个字符这一功能
    int y[4] = {-1,1,0,0}; // 这里用的特别巧妙
    int rows,cols;
    bool dfs(vector<vector<char>>& board,string word,int i,int j,int num) {
        if (num == word.size()) return true;
        char tmp = board[i][j]; // 用于暂时保存字符
        board[i][j] = '.'; // 代表这个字符已经访问过
        for (int k = 0; k < 4; k++) {
            int d_x = x[k] + i; // 新的i值
            int d_y = y[k] + j; // 新的j值
            if (d_x >= 0 && d_x < rows && d_y >= 0 && d_y < cols && word[num] == board[d_x][d_y]) {
                if (dfs(board,word,d_x,d_y,num + 1)) return true;
            }
        }
        board[i][j] = tmp; // 遍历结束后改回来  
        return false;
    }
    bool exist(vector<vector<char>>& board, string word) {
        rows = board.size();
        cols = board[0].size();
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (board[i][j] == word[0]) { //若是没有这一步的判断，则会报错如两个a a
                    if (dfs(board,word,i,j,1)) 
                        return true;
                }
            }
        }
        return false;
    }
};

link

class Solution {
public:
    bool hasPath(char* matrix, int rows, int cols, char* str)
    {
        // 只通过76%
        //if(matrix==nullptr || cols<1 || cols<1 || str==nullptr)
        //     return false;
        if(rows == 1 && cols == 1){
            if(matrix[0] == str[0])
                return true;
            else
                return false;
        }
         for(int i=0; i < rows; i++){
            for(int j=0; j < cols; j++){
                if(dfs(matrix, rows, cols, i, j, str, 0)){
                    return true;
                }
            }
        }
        return false;
    }
    bool dfs(char* matrix, int rows, int cols, int x, int y, char* str, int s){
        if(str[s] == '\0') return true;
        int dx[] = {0, 0, -1, 1};
        int dy[] = {1, -1, 0, 0};
        for(int i=0; i<4; i++){
            int row = x+dx[i];
            int col = y+dy[i];
            if(row>=0 && row<rows && col>=0 && col<cols && matrix[row*cols+col]==str[s]){
                char t = str[s];
                matrix[row*cols+col] = '*';
                if(dfs(matrix, rows, cols, row, col, str, s+1))
                    return true;
                matrix[row*cols+col] = t;
            }
        }
        return false;
    }
};

JZ13 机器人的运动范围

题目描述
地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？
思路
常规思路

class Solution {
public:
    int movingCount(int threshold, int rows, int cols)
    {
        if (threshold < 0 || rows < 1 || cols < 1)
            return 0;
        bool* visited = new bool[rows * cols];
        memset(visited, false, rows * cols);
        int count = movingCountCore(threshold, rows, cols, 0, 0, visited);
        delete[] visited;
        return count;
    }
    int movingCountCore(int threshold, int rows, int cols, int row, int col, bool* visited)
    {
        int count = 0;
        if (check(threshold, rows, cols, row, col, visited))//可以访问(row, col)
        {
            visited[row * cols + col] = true;
            count = 1 + movingCountCore(threshold, rows, cols, row - 1, col, visited)
                + movingCountCore(threshold, rows, cols, row + 1, col, visited)
                + movingCountCore(threshold, rows, cols, row, col - 1, visited)
                + movingCountCore(threshold, rows, cols, row, col + 1, visited);
        }
        return count;
    }
    bool check(int threshold, int rows, int cols, int row, int col, bool* visited)
    {
        if (row >= 0 && row < rows && col >= 0 && col < cols         /*未越界*/
            && threshold >= getDigitSum(row) + getDigitSum(col)    /*满足题目条件*/
            && !visited[row * cols + col])                         /*未访问*/
            return true;
        return false;
    }
    int getDigitSum(int number)
    {
        int sum = 0;
        while (number > 0)
        {
            sum += number % 10;
            number /= 10;
        }
        return sum;
    }
};

下面的解法更加通俗一些

这里我前面思路有些许问题，总觉得要判断周围的点是否访问过，才能dfs当前点，没有绕过来，如果没有访问到周围的点，当前点也递归不到啊， hhhhha

class Solution {
private:
    vector<vector<bool>> vis;
    int m, n;
    int ans;
    vector<pair<int, int>> directions = {{-1,0}, {1,0}, {0,1},{0,-1}};
public:
    int movingCount(int m, int n, int k) {
        this->m = m, this->n = n;
        ans = 0;
        vis = vector<vector<bool>>(m, vector<bool>(n,false));
        dfs(0, 0, k);
        return ans;
    }
    void dfs(int x, int y, int k)
    {
        if (x<0 || x>=m || y<0 || y>=n || vis[x][y] || !isMovable(x,y,k))
            return;
        ans++;
        vis[x][y] = true;
        for (auto &dir : directions)
        {
            int dx = x + dir.first, dy = y + dir.second;
            dfs(dx, dy, k);
        }
    }
    bool isMovable(int x, int y, int k)
    {
        vector<int> arr{x, y};
        int res = 0;
        for (auto &i : arr)
        {
            while (i)
            {
                res += i%10;
                i /= 10;
            }
        }
        return res <= k;
    }
};

第3章高质量的代码

JZ16数值的整数次方

给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。
思路
注意exponent为负数的情况

double Power(double base, int exponent) {
        double result=1;
        bool negative = false;
        if(exponent < 0){
            negative = true;
            exponent = -exponent;
        }
        for(int i=1;i<=exponent;++i){
            result *= base;
        }
        if(negative)
            result = 1/result;
        return result;
    }

log(N)解法，二进制优化

double myPow(double x, int n) 
{
    double res = 1, cur = x;
    bool neg = false;
    if (n<0) neg = true, n = -n;
    while (n)
    {
        if (n&0x01) res *= cur;
        cur *= cur;
        n >>= 1;
    }
    if (neg) res = 1/res;
    return res;
}

JZ17. 打印从1到最大的n位数

输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数 999。
示例 1:

输入: n = 1
输出: [1,2,3,4,5,6,7,8,9]

void printNumber(char* number)
{
    int len = strlen(number);
    bool isBeginning0 = true;
    for (int i = 0; i < len; ++i)
    {
        if (isBeginning0 && number[i] != '0')
            isBeginning0 = false;
        if (!isBeginning0)
            printf("%c", number[i]);
    }
    printf("\t");
}
void dfs(char* number, int length, int idx)
{
    if (idx == length - 1)
    {
        printNumber(number);
        return;
    }
    for (int i = 0; i < 10; ++i)
    {
        number[idx+1] = '0' + i;
        dfs(number, length, idx + 1);
    }
}
void priprint1ToMaxOfNDigitsnt(int n)
{
    if (n <= 0)
        return;
    char* number = new char[n + 1];
    number[n] = '\0';
    for (int i = 0; i < 10; ++i)
    {
        number[0] = i + '0';
        dfs(number, n, 0);
    }
    delete[] number;
}

## JZ23 链表中环的入口结点 题目描述
给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。
思路

假设快指针和满指针在Z点相遇。
由于a的长度未知，故假设：相遇时，fast已绕环n圈。则：
slow前进的距离是：a+b
fast 前进的距离是：a+n(c+b)+b
又有 2slow = fast ===> a = (n-1)(b+c)+c
a 的长度是（n-1）圈，加c的长度，
则一个点从z点出发（多余的c长度），一个点从起点出发。
肯定在Y点相遇。

cpp
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if(head == nullptr) return NULL;//头结点为空
        ListNode* fast = head;
        ListNode* slow = head;  
        while(fast!=nullptr && fast->next!=nullptr)
        {
            fast = fast->next->next;
            slow = slow->next;
            if(fast==slow)//相遇
                break;
        }
        if(fast==nullptr || fast->next==nullptr) //没有环
            return NULL;
        else
        {
            slow = head;//重置slow从起点开始
            while(fast != slow)
            {
                fast = fast->next;
                slow = slow->next;
            }
            return slow;
        }
    }
};
/*链表中的++没有重载时，和next不一样的。*/

## JZ18-2删除链表中的的重复节点（hard）参考书上的答案

cpp
void  deleteDuplication(ListNode* pHead)
    {
        if (pHead == NULL)
            return;

        ListNode* pPreNode = NULL;
        ListNode* pNode = pHead;

        while (pNode != NULL) {
            ListNode* pNext = pNode->next;
            bool needDelete = false;
            if (pNext != NULL && pNext->val == pNode->val)/*出现重复节点*/
                needDelete = true;
            if (!needDelete) {/*do not need delete*/
                pPreNode = pNode;
                pNode = pNode->next;
            }
            else { /*需要删除时*/
                int  val = pNode->val;
                ListNode* pToBeDel = pNode;
                /**/
                while (pNext != NULL && pToBeDel->val == val) {
                    pNext = pToBeDel->next;
                    /*delete pToBeDel;
                    pToBeDel = NULL;*/

                    pToBeDel = pNext;
                }
                /*循环结束时，pNext指向了第一个不相同的节点，比如图中的节点5*/

                if (pPreNode == NULL)/*最开始的节点出现重复时*/
                    pHead = pNext;
                else
                    pPreNode->next = pNext;
                pNode = pNext;
            }
        }
    }

下面的解法是我自己写的，显然是没有考虑到一些特殊情况的，如从root开始就出现重复的情况

cpp
ListNode* deleteDuplication(ListNode* pHead)
    {
        if (pHead == NULL)
            return NULL;
        bool duplicate = false;
        ListNode* pre = NULL, * cur = pHead, * newnode = pHead;
        while (cur->next != NULL)
        {
            auto node = cur->next;
            if (node->val != newnode->val)
            {
                if (duplicate)
                {
                    pre->next = node;
                    newnode = node;
                }
                else
                {
                    pre = newnode;
                    newnode = node;
                    duplicate = false;
                }
            }
            else
            {
                duplicate = true;
            }
            cur = cur->next;
        }
        return pHead;
    }

## JZ21调整数组顺序使奇数位于偶数前面输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。

cpp
void reOrderArray(vector<int> &array) {
       int n = array.size();
        if(0==n || 1==n)
            return;

        vector<int> even;
        int oddsNumber = 0;
         for(int i=0;i<n;++i){
             if(array[i]&0x01)
                 array[oddsNumber++] = array[i];
             else
                 even.emplace_back(array[i]);
         }
        int k =0;
        for(int i=oddsNumber;i<n;++i)
            array[i] = even[k++];
    }

这里直接使用partition中交换的思路，不用开辟空间

cpp
vector<int> exchange(vector<int>& nums) 
{
    int l = 0, r = nums.size()-1;
    while (l<r)
    {
        while (l<nums.size() && nums[l]&0x01) l++;
        while (r>=0 && nums[r]%2==0) r--;
        if (l < r) swap(nums[l], nums[r]);
    }

    return nums;
}

## JZ22链表的倒数第K个节点常见的解法是

cpp
ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
    if (pListHead == NULL || k == 0)
        return NULL;
    ListNode* fast = pListHead， * slow = pListHead;
    for (unsigned int i = 0; i < k; --i) {
        fast = fast->next;
    }

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

这个解法是有问题的，当k大于链表的长度就会出现溢出问题。

cpp
ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
        if(pListHead==nullptr || k==0) 
            return nullptr;
        ListNode *fast = pListHead ,* slow=pListHead;
        while(k--){
            if(fast)
               fast = fast->next;
            else
                return nullptr;
        }

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

## JZ23 链表中环的入口结点 题目描述
给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。
思路

cpp
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if(head == nullptr) return NULL;//头结点为空
        ListNode* fast = head;
        ListNode* slow = head;  
        while(fast!=nullptr && fast->next!=nullptr)
        {
            fast = fast->next->next;
            slow = slow->next;
            if(fast==slow)//相遇
                break;
        }
        if(fast==nullptr || fast->next==nullptr) //没有环
            return NULL;
        else
        {
            slow = head;//重置slow从起点开始
            while(fast != slow)
            {
                fast = fast->next;
                slow = slow->next;
            }
            return slow;
        }
    }
};
/*链表中的++没有重载时，和next不一样的。*/

## JZ24 反转链表 解题思路
在反转的过程中，反转节点的下一个节点一定要提前保存，否则，后面的节点都丢失了。

cpp
ListNode* reverseList(ListNode* head)
{
    if (head == nullptr)
        return nullptr;

    ListNode* cur=nullptr;
    ListNode* pre=head;

    while (pre != nullptr)
    {
        ListNode* node = pre->next; /*先保存，断开之后就找不到了*/
        pre->next = cur;

        cur = pre;
        pre = node;

    }
    return cur;
}

## JZ25 合并两个有序链表

写的时候一定要有清晰的思路

cpp
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if(l1 == NULL)
            return l2;
        else if(l2 == NULL)
            return l1;
        else if(l1->val<l2->val){
            l1->next = mergeTwoLists(l1->next, l2);
            return l1;
        }
        else{
            l2->next = mergeTwoLists(l1, l2->next);
            return l2;
        }       
    }
};

## JZ26 树的子结构 # 第4章解决面试题的思路 ## JZ27 二叉树的镜像思路
所有的树都是小的子树构成的。依次交换
将节点插入队尾并弹出对头，进行交换。

cpp
void Mirror(TreeNode* pRoot)
{
    if (pRoot == nullptr)
        return;

    queue<TreeNode*> q;
    q.push(pRoot);
    while (!q.empty())
    {
        auto node = q.front();
        q.pop();
        if (node->left != NULL)
            q.push(node->left);
        if (node->right != NULL)
            q.push(node->right);
        if (node->left != NULL || node->right != NULL)/*swap left and right*/
        {
            auto tmp = node->right;
            node->right = node->left;
            node->left = tmp;
        }
    }
}

## JZ28 对称的二叉树思路
尝试使用的层序遍历的思路。但是有以下的情况是无法突破的。

cpp
class Solution01 {
public:
    bool isSymmetrical(TreeNode* pRoot)
    {
        return bfs_isBlanced(pRoot);
    }

    bool bfs_isBlanced(TreeNode* root)
    {
        if (root == nullptr)
            return true;
        TreeNode* node = root;
        queue<TreeNode*> q;
        q.push(node);
        int len = 0;
        while (!q.empty())
        {
            int curLevelSize = q.size();
            ++len;
            vector<int> res;
            for (int i = 0; i < curLevelSize; ++i)
            {
                node = q.front();
                q.pop();
                res.emplace_back(node->val);
                if (node->left)
                    q.push(node->left);
                if (node->right)
                    q.push(node->right);
            }

            int newSize = q.size();
            if (len > 1 && newSize & 0x01)
            {
                return false;
            }
            else
            {
                int l = 0, r = curLevelSize - 1;
                while (l <= r)
                {
                    if (res[l++] != res[r--])
                        return false;
                }
            }
            res.clear();
        }
        return true;
    }
};

转换思路，采用书上的方法。递归法
剑指offer - 图6

若满足对称二叉树，必须满足：
1. L->val == R->val2. L->left->val == R->right->val3. L->right->val == R->left->val

cpp
class Solution {
public:
    bool isSymmetrical(TreeNode* pRoot)
    {
        return isSymmetrical(pRoot, pRoot);
    }

    bool isSymmetrical(TreeNode* node1, TreeNode* node2)
    {
        if(node1==NULL && node2==NULL)
            return true;
        if(node1==NULL || node2==NULL)
            return false;

        if(node1->val != node2->val)
            return false;

        return isSymmetrical(node1->left, node2->right)
            && isSymmetrical(node1->right, node2->left);
    }
};

## JZ29 顺时针打印矩阵解题思路
注意特殊情况的处理：
right —> left && down —> up 时需要先判断。

cpp
class Solution {
public:
    vector<int> spiralOrder(vector<vector<int> >& matrix) {
        int rows = matrix.size();
        int cols = matrix[0].size();
        vector<int> res;
        if (rows == 0 || cols == 0)
            return res;

        int left = 0, right = cols-1;
        int up = 0, down = rows-1;

        while (left <= right && up <= down)
        {
            for (int i = left; i <= right; ++i)//left --> right
                res.push_back(matrix[up][i]);
            up++;

            for (int i = up; i <= down; ++i)//up --> down
                res.push_back(matrix[i][right]);
            --right;

            /*这里要注意特殊情况，所剩区域是一个（right-left+1）*1的矩形*/
            if(down>=up) //right --> left
                for (int i = right; i >= left; --i)
                    res.push_back(matrix[down][i]);
            --down;

            if(right>=left)// down --> up
                for (int i = down; i >= up; --i)
                    res.push_back(matrix[i][left]);
            ++left;
        }
        return res;
    }
};

void main_test()
{
    vector<vector<int>> matrix = { {1,2,3},{4,5,6},{7,8,9} };
    Solution so;
    for (auto i : so.spiralOrder(matrix))
        printf("%d \t", i);


}

个人觉得下面的解法更为优雅

cpp
class Solution {
private:
    vector<pair<int, int>> direction = {{0,1}, {1,0}, {0,-1},{-1,0}};
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        if (matrix.size() == 0 || matrix[0].size() == 0) {
            return {};
        }

        int m = matrix.size(), n = matrix[0].size();
        vector<vector<bool>> vis(m, vector<bool>(n, false));
        vector<int> res;

        int i = 0, j = 0, idx = 0,  cnt = 0;
        for ( ; cnt < m*n; cnt++)
        {
            res.emplace_back(matrix[i][j]);
            vis[i][j] = true;

            int nextI = i + direction[idx].first, nextJ = j + direction[idx].second;
            if (nextI<0 || nextI>=m || nextJ<0 || nextJ>=n || vis[nextI][nextJ])
                idx = (idx + 1) % 4;

            i += direction[idx].first, j += direction[idx].second;
        }
        return res;
    }
};

## JZ30 包含min函数的栈 ## JZ31 栈的压入和弹出序列自己独立写的哈

cpp
bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        stack<int> sPush, sPop;

        for (int i=0, j=0; i<pushed.size(); )
        {
            sPush.push(pushed[i++]);

            while (!sPush.empty() && sPush.top() == popped[j])
            {
                sPush.pop();
                j++;
            }
        }

        return sPush.empty();

    }

## JZ32-1 从上往下打印二叉树

cpp
class Solution {
public:

    vector<int> PrintFromTopToBottom(TreeNode* root) {
         vector<int> res;
        if (root == nullptr)
            return res;

        TreeNode* node = root;
        queue<TreeNode*> q;
        q.push(node);
        while (!q.empty())
        {
            int curLevelSize = q.size();
            for (int i = 0; i < curLevelSize; ++i)
            {
                node = q.front();
                q.pop();
                res.emplace_back(node->val);
                if (node->left)
                    q.push(node->left);
                if (node->right)
                    q.push(node->right);
            }
        }
        return res;
    }
};

## JZ32-3 之字形打印二叉树思路
层序遍历

cpp
class Solution {
public:
    vector<vector<int> > Print(TreeNode* pRoot) {
        vector<vector<int>> res;
        if (pRoot == NULL)
            return res;
        bfs(pRoot, res);
        return res;
    }

    void bfs(TreeNode* root, vector<vector<int>>& res)
    {

        TreeNode* node = root;
        queue<TreeNode*> q;
        q.push(node);
        vector<int> ans;
        bool flag = true;
        while (!q.empty())
        {
            int curLevelSize = q.size();
            for (int i = 0; i < curLevelSize; ++i)
            {
                node = q.front();
                q.pop();
                ans.emplace_back(node->val);
                if (node->left)
                    q.push(node->left);
                if (node->right)
                    q.push(node->right);
            }
            flag = !flag;
            if (flag)
                reverse(ans.begin(), ans.end());
            res.emplace_back(ans);
            ans.clear();
        }
    }

};

## JZ33 二叉搜索树的后序遍历序列 ## JZ34 二叉树中和为某一值的路径采用DFS进行深度优先遍历，然后采用回溯法，得到想要的结果。
注意一些代码中的细节问题。

cpp
/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/

class Solution {
public:
    vector<vector<int> > FindPath(TreeNode* root,int expectNumber) {
        vector<vector<int> > res;
        if (root == nullptr)
            return res;
        vector<int> path;
        helper(root, res, expectNumber, path, 0);
        return res;
    }

    void helper(TreeNode* node, vector < vector<int> >& res,  int expectsum, vector<int>&path,int curSum)
    {

        curSum = curSum + node->val;
        path.emplace_back(node->val);

        bool isLeaf = (node->left == NULL && node->right == NULL);
        if (curSum == expectsum && isLeaf)
        {
            res.push_back(path);
            path.pop_back(); /*形成路径后要返回父节点，由于直接返回
                                跳过了弹出节点，需要进行回溯*/
            return;
        }

        if (node->left != NULL)
            helper(node->left, res, expectsum, path, curSum);

        if(node->right!=NULL)
            helper(node->right, res, expectsum, path, curSum);
        path.pop_back(); /*返回父节点就回溯*/

    }
};

hha
发现我现在的代码更加的简洁了，xixi

cpp
class Solution {
private:
    vector<vector<int>> res;
    vector<int> cur;
public:
    vector<vector<int>> pathSum(TreeNode* root, int target) {
        if (root == nullptr) return res;
        dfs(root, target);
        return res;
    }

    void dfs(TreeNode* node, int target)
    {
        cur.push_back(node->val);

        if (target==node->val && node->left==nullptr && node->right==nullptr)
        {
            res.push_back(cur);
            cur.pop_back(); // it's likely to forget backtrace
            return ;
        }

        if (node->left) dfs(node->left, target - node->val);
        if (node->right) dfs(node->right, target - node->val);
        cur.pop_back(); // backtrace
    }
};

## JZ35 复杂链表的复制 ## JZ36 二叉搜索树与双向链表 ## JZ37 二叉树的序列化与反序列化 ## JZ38 字符串的排列 # 第5章优化时间和空间效率 ## JZ39 数组中出现次数超过一半的数哈希表统计法：
遍历数组 nums ，用 HashMap 统计各数字的数量，即可找出众数。此方法时间和空间复杂度均为 O(N) 数组排序法：
将数组 nums 排序，数组中点的元素一定为众数。以上两种方法都比较简单，就不写了摩尔投票法：
核心理念为票数正负抵消。此方法时间和空间复杂度分别为 O(N)O(N) 和 O(1)O(1) ，为本题的最佳解法。

shell
int majorityElement(vector<int>& nums) {

        int x=0, vote=0;

        for (auto &i : nums)
        {
            if (vote == 0) x = i;

            vote += (x == i) ? 1 : -1;
        }

        return x;
    }

## 剑指 Offer 48. 最长不含重复字符的子字符串 1. 双指针解法

cpp
class Solution {
public:
    unordered_map<char, int> mp;
    int lengthOfLongestSubstring(string s) {
        int i=0, j=0, maxLen = 0;
        while (j < s.size())
        {
            mp[s[j]]++;
            if (mp[s[j]] > 1) // dup happens, move i
            {
                while (s[i] != s[j] && i < j)
                {
                    mp[s[i]]--;
                    i++;
                }

                if (s[i] == s[j])
                {
                    mp[s[i]]--;
                    i++;
                }
            }

            maxLen = max(maxLen, j-i+1);
            j++;
        }
        return maxLen;
    }
};

## 剑指 Offer 49. 丑数

cpp
class Solution {
public:
    int nthUglyNumber(int n) {
        vector<long> factors{2,3,5};
        priority_queue<long, vector<long>, greater<long>> pq;
        unordered_set<long> used;
        long cur;

        pq.push(1), used.insert(1);
        for (int i=0; i<n; i++)
        {
            cur = pq.top();
            pq.pop();

            for (auto &f : factors)
            {
                long num = f * cur;
                if (!used.count(num))
                {
                    pq.push(num);
                    used.insert(num);
                }
            }
        }
        return cur;
    }
};

剑指 Offer 66. 构建乘积数组

class Solution {
public:
    vector<int> constructArr(vector<int>& a) {
        int n = a.size(); if (!n) return {};
        vector<int> forward(n, a[0]), reverse(n, a[n-1]);
        for (int i=1; i<n; i++) forward[i] = forward[i-1] * a[i];
        for (int i=n-2; i>=0; i--) reverse[i] = reverse[i+1] * a[i];
        vector<int> res(n, 0);
        res[0] = reverse[1];
        for (int i=1; i<n-1; i++)
            res[i] = forward[i-1] * reverse[i+1];
        res[n-1] = forward[n-2];
        return res;
    }
};

这里可以将后面的两次循环合并为一次

剑指offer

JZ01 赋值运算符号函数

第3章 高质量的代码

第3章高质量的代码