leetcode-ThirdWeek

本文为记录自己学习算法的过程

[70]爬楼梯

假设你正在爬楼梯。需要n阶你才能到达楼顶。

每次你可以爬1或2个台阶。你有多少种不同的方法可以爬到楼顶呢？

示例 1：

输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶

示例 2：

输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

提示：

$1 <= n <= 45$

题解：

class Solution {
public:
    int climbStairs(int n) {
        if (n <= 2) {//1个台阶一种方法，2个台阶有两种方法
            return n;
        }
        //第n级台阶可以由n-1级台阶上来，也可以由n-2级台阶上来
        int ans = 0;
        int a = 1;
        int b = 2;
        for (int i = 3; i <= n; ++i) {
            ans = a + b;
            a = b;
            b = ans;
        }
        return ans;
    }
};

思路：

这题主要考察的就是思维能力是动态规划吧，在思考的时候不能总是固定着自己的思想，总是想着下一步可以走一步或者两步，一般都会考虑直接递归，但是在这题会导致超时，所以需要重新考虑方法。

在这题主要的思路就是想清楚考虑好走台阶的真正意思。在这题中我们可以分析发现走第n个台阶可以由第n-1个台阶走上来，也可以由n-2个台阶走上来，所以我们直接计算好上1个台阶有几种走法，第2个台阶有几种走法，后面的第n级台阶的走法就是n-1级台阶的走法加上n-2级台阶的走法。

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

给定一个已排序的链表的头head，删除所有重复的元素，使每个元素只出现一次。返回已排序的链表。

示例 1：

示例1

1 2	输入：head = [1,1,2] 输出：[1,2]

示例 2：

示例2

1 2	输入：head = [1,1,2,3,3] 输出：[1,2,3]

提示：

$链表中节点数目在范围 [0, 300] 内$
$-100 <= Node.val <= 100$
$题目数据保证链表已经按升序排列$

题解：

class Solution {
public:
    ListNode *deleteDuplicates(ListNode *head) {
        ListNode *p = head;
        if (head == nullptr) {//链表为空
            return head;
        }
        //当下一个节点为空就退出循环
        while (p->next != nullptr) {
            //当前这个值与下一个值相等
            if (p->next->val == p->val) {
                p->next = p->next->next;//断开重复元素的节点
            }
            //下一个节点不为空并且下一个元素与当前这个元素不重复就往后移动
            if (p->next && p->next->val != p->val) {
                p = p->next;
            }
        }
        return head;
    }
};

思路：

这题就是简单的将重复元素去重，这题最大的特点是链表的元素已经是排序好了的，所以要利用这个特点来解题。

思路就是遍历链表，让一个指针p指向链表第一个元素，然后向后遍历，判断当前指向的元素的值与下一个元素的值是否相等，相等就让当前这个元素的next域指向next->next，这样就相当于去掉了重复的元素，这里需要注意的是最好在断开节点的时候，将断开的那个节点释放资源。还有一点就是在更新操作之后不要马上向后移动节点，因为更新操作了，可能导致移动指针指向的是空节点，再判断空节点的后一个域会出现异常。

LeetCode题解

方法一：一次遍历

思路与算法

由于给定的链表是排好序的，因此重复的元素在链表中出现的位置是连续的，因此我们只需要对链表进行一次遍历，就可以删除重复的元素。

具体地，我们从指针 $\textit{cur}$ 指向链表的头节点，随后开始对链表进行遍历。如果当前 $\textit{cur}$ 与 $\textit{cur.next}$对应的元素相同，那么我们就将 $\textit{cur.next}$ 从链表中移除；否则说明链表中已经不存在其它与 $\textit{cur}$ 对应的元素相同的节点，因此可以将 $\textit{cur}$ 指向 $\textit{cur.next}$。

当遍历完整个链表之后，我们返回链表的头节点即可。

细节

当我们遍历到链表的最后一个节点时，$\textit{cur.next}$ 为空节点，如果不加以判断，访问 $\textit{cur.next}$ 对应的元素会产生运行错误。因此我们只需要遍历到链表的最后一个节点，而不需要遍历完整个链表。

代码

注意下面 $\texttt{C++}$ 代码中并没有释放被删除的链表节点的空间。如果在面试中遇到本题，读者需要针对这一细节与面试官进行沟通。

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if (!head) {
            return head;
        }

        ListNode* cur = head;
        while (cur->next) {
            if (cur->val == cur->next->val) {
                cur->next = cur->next->next;
            }
            else {
                cur = cur->next;
            }
        }

        return head;
    }
};
作者：LeetCode-Solution

[88]合并两个有序数组

给你两个按非递减顺序排列的整数数组nums1和nums2，另有两个整数m和n，分别表示nums1和nums2中的元素数目

请你合并nums2到nums1中，使合并后的数组同样按非递减顺序排列

注意：最终，合并后数组不应由函数返回，而是存储在数组nums1中。为了应对这种情况，nums1的初始长度为m + n，其中前m个元素表示应合并的元素，后n个元素为0，应忽略。nums2的长度为n。

示例 1：

输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]
解释：需要合并 [1,2,3] 和 [2,5,6] 。
合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。

示例 2：

1
2
3

输出：[1]
解释：需要合并 [1] 和 [] 。
合并结果是 [1] 。

示例 3：

输入：nums1 = [0], m = 0, nums2 = [1], n = 1
输出：[1]
解释：需要合并的数组是 [] 和 [1] 。
合并结果是 [1] 。
注意，因为 m = 0 ，所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。

提示：

$nums1.length == m + n$
$nums2.length == n$
$0 <= m, n <= 200$
$1 <= m + n <= 200$
$-10^9 <= nums1[i], nums2[j] <= 10^9$

题解：

class Solution {
public:
    void merge(vector<int> &nums1, int m, vector<int> &nums2, int n) {
        int i = m - 1, j = n - 1;
        //数组n的长度为0，直接退出
        if (n == 0) {
            return;
        }
        //数组nums1的长度为0，将nums2数组里面的元素全部放入数组nums1
        if (m == 0) {
            for (int k = 0; k < n; ++k) {
                nums1[k] = nums2[k];
            }
            return;
        }
        //遍历比较数组nums1和数组nums2里面的元素，大的放数组nums1的最后面
        while (j >= 0 && i >= 0) {
            if (nums1[i] < nums2[j]) {//将数组nums2的元素放在nums1最后面
                nums1[i + j + 1] = nums2[j];
                j--;
            } else {//将数组nums1有效的元素放在nums1最后面
                nums1[i + j + 1] = nums1[i];
                i--;
            }
        }
        //可能数组nums1遍历完了，但是数组nums2里面的元素还没有放入nums1
        while (j >= 0) {
            nums1[j] = nums2[j];
            j--;
        }
    }
};

思路：

这题就是考察双指针问题，拿到题目我们就可以想到就是遍历两个数组，将数组中的元素进行比较放入恰当的位置即可。唯一不同的就是我们需要将所有的元素都放入数组nums1。

思路就是首先判断nums2数组的长度是否等于0，等于0说明数组num2没有元素，直接返回就可以了。如果num1数组长度等于0此时就可以直接将数组num2里面的元素全部按顺序放进nums1里面不需要考虑数组nums2里面有没有元素。接着就是遍历两个数组，一开始都指向有效元素的位置，比较元素的大小，大的元素就插入到数组nums1中，插入的位置为如下公式：

$插入位置=指向nums1数组的指针的下标 i +指向nums2数组的指针的下标 j +1$

判断结束的条件是j>=0&&i>=0因为当j<0时表示已经将nums2数组中的元素都放入nums1中，而i<0则表示nums1数组中的元素都放在了恰当的位置，所以最后来个while将nums2数组中的元素放入nums1中就可以了。

LeetCode题解

方法一：直接合并后排序

算法

最直观的方法是先将数组 $\textit{nums}_2$放进数组 $\textit{nums}_1$的尾部，然后直接对整个数组进行排序。

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        for (int i = 0; i != n; ++i) {
            nums1[m + i] = nums2[i];
        }
        sort(nums1.begin(), nums1.end());
    }
};
作者：LeetCode-Solution

方法二：双指针

算法

方法一没有利用数组 $\textit{nums}_1$ 与 $\textit{nums}_2$ 已经被排序的性质。为了利用这一性质，我们可以使用双指针方法。这一方法将两个数组看作队列，每次从两个数组头部取出比较小的数字放到结果中。如下面的动画所示：

双指针

我们为两个数组分别设置一个指针 $p_1$ 与 $p_2$ 来作为队列的头部指针。代码实现如下：

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int p1 = 0, p2 = 0;
        int sorted[m + n];
        int cur;
        while (p1 < m || p2 < n) {
            if (p1 == m) {
                cur = nums2[p2++];
            } else if (p2 == n) {
                cur = nums1[p1++];
            } else if (nums1[p1] < nums2[p2]) {
                cur = nums1[p1++];
            } else {
                cur = nums2[p2++];
            }
            sorted[p1 + p2 - 1] = cur;
        }
        for (int i = 0; i != m + n; ++i) {
            nums1[i] = sorted[i];
        }
    }
};
作者：LeetCode-Solution

方法三：逆向双指针

算法

方法二中，之所以要使用临时变量，是因为如果直接合并到数组 $\textit{nums}_1$ 中，$\textit{nums}_1$ 中的元素可能会在取出之前被覆盖。那么如何直接避免覆盖 $\textit{nums}_1$ 中的元素呢？观察可知，$\textit{nums}_1$ 的后半部分是空的，可以直接覆盖而不会影响结果。因此可以指针设置为从后向前遍历，每次取两者之中的较大者放进 $\textit{nums}_1$ 的最后面。严格来说，在此遍历过程中的任意一个时刻，$\textit{nums}_1$ 数组中有 $m-p_1-1$ 个元素被放入 $\textit{nums}_1$ 的后半部，$\textit{nums}_2$ 数组中有 $n-p_2-1$ 个元素被放入 $\textit{nums}_1$ 的后半部，而在指针 $p_1$ 的后面，$\textit{nums}_1$ 数组有 $m+n-p_1$ 个位置。由于

$m+n−p_1−1≥m−p_1−1+n−p_2−1$

等价于

$p_2≥-1$

永远成立，因此 $p_1$ 后面的位置永远足够容纳被插入的元素，不会产生 $p_1$ 的元素被覆盖的情况。

实现代码如下：

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int p1 = m - 1, p2 = n - 1;
        int tail = m + n - 1;
        int cur;
        while (p1 >= 0 || p2 >= 0) {
            if (p1 == -1) {
                cur = nums2[p2--];
            } else if (p2 == -1) {
                cur = nums1[p1--];
            } else if (nums1[p1] > nums2[p2]) {
                cur = nums1[p1--];
            } else {
                cur = nums2[p2--];
            }
            nums1[tail--] = cur;
        }
    }
};
作者：LeetCode-Solution

[94]二叉树的遍历

给定一个二叉树的根节点root，返回它的中序遍历

示例 1：

示例1

1 2	输入：root = [1,null,2,3] 输出：[1,3,2]

示例 2：

1 2	输入：root = [] 输出：[]

示例 3：

1 2	输入：root = [1] 输出：[1]

提示：

$树中节点数目在范围 [0, 100] 内$
$-100 <= Node.val <= 100$

进阶:递归算法很简单，你可以通过迭代算法完成吗？

题解：

方法一：递归

class Solution {
public:
    vector<int> v;

    vector<int> inorderTraversal(TreeNode *root) {
        if (root != nullptr) {
            inorderTraversal(root->left);
            v.push_back(root->val);
            inorderTraversal(root->right);
        }
        return v;
    }
};

方法二：迭代

class Solution {
public:
    vector<int> inorderTraversal(TreeNode *root) {
        vector<int> v;//定义返回的容器
        if (root == nullptr) {//root为空直接返回
            return v;
        }
        TreeNode *p = root;//指向root节点
        stack<TreeNode *> s;
        //栈不为空或者p节点不为空，防止到达某个节点就退出不搜寻
        while (!s.empty() || p) {
            //一直向子树搜寻
            while (p) {
                s.push(p);//入栈
                p = p->left;//找左孩子
            }
            p = s.top();//指向栈顶元素
            s.pop();//弹出栈顶元素
            v.push_back(p->val);//此时表明可以入容器，是按照中序的序列
            p = p->right;//获取当前节点的右孩子，然后找这个右孩子节点的左孩子
        }
        return v;
    }
};

思路：

这道题就是二叉树的基本操作，具体可以查看我的文章二叉树

LeetCode题解

方法一和方法二类似就不实现了。

方法三：Morris 中序遍历

思路与算法

Morris 遍历算法是另一种遍历二叉树的方法，它能将非递归的中序遍历空间复杂度降为 $O(1)$。

Morris 遍历算法整体步骤如下（假设当前遍历到的节点为 $x$）：

如果 $x$ 无左孩子，先将 $x$ 的值加入答案数组，再访问 $x$ 的右孩子，即 $x = x.\textit{right}$。
如果 $x$ 有左孩子，则找到 $x$ 左子树上最右的节点（即左子树中序遍历的最后一个节点，$x$ 在中序遍历中的前驱节点），我们记为 $\textit{predecessor}$。根据 $\textit{predecessor}$ 的右孩子是否为空，进行如下操作。
- 如果 $\textit{predecessor}$ 的右孩子为空，则将其右孩子指向 xx，然后访问 xx 的左孩子，即 $x = x.\textit{left}$。
- 如果 $\textit{predecessor}$ 的右孩子不为空，则此时其右孩子指向 $x$，说明我们已经遍历完 $x$ 的左子树，我们将$\textit{predecessor}$ 的右孩子置空，将 $x$ 的值加入答案数组，然后访问 $x$ 的右孩子，即 $x = x.\textit{right}$。
重复上述操作，直至访问完整棵树。

其实整个过程我们就多做一步：假设当前遍历到的节点为 $x$，将 $x$ 的左子树中最右边的节点的右孩子指向 $x$，这样在左子树遍历完成后我们通过这个指向走回了 $x$，且能通过这个指向知晓我们已经遍历完成了左子树，而不用再通过栈来维护，省去了栈的空间复杂度。

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        TreeNode *predecessor = nullptr;

        while (root != nullptr) {
            if (root->left != nullptr) {
                // predecessor 节点就是当前 root 节点向左走一步，然后一直向右走至无法走为止
                predecessor = root->left;
                while (predecessor->right != nullptr && predecessor->right != root) {
                    predecessor = predecessor->right;
                }
                
                // 让 predecessor 的右指针指向 root，继续遍历左子树
                if (predecessor->right == nullptr) {
                    predecessor->right = root;
                    root = root->left;
                }
                // 说明左子树已经访问完了，我们需要断开链接
                else {
                    res.push_back(root->val);
                    predecessor->right = nullptr;
                    root = root->right;
                }
            }
            // 如果没有左孩子，则直接访问右孩子
            else {
                res.push_back(root->val);
                root = root->right;
            }
        }
        return res;
    }
};
作者：LeetCode-Solution

[118]杨辉三角

给定一个非负整数numRows，生成「杨辉三角」的前numRows行。

在「杨辉三角」中，每个数是它左上方和右上方的数的和。

杨辉三角

示例 1:

1 2	输入: numRows = 5 输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

示例 2:

1 2	输入: numRows = 1 输出: [[1]]

提示:

$1 <= numRows <= 30$

题解：

class Solution {
public:
    //将杨辉三角转化成如下
    /**
     * 1
     * 1 1
     * 1 2 1
     * 1 3 3 1
     * ...
     */
    int a[31][31];//将杨辉三角放入二维数组
    //根据行数初始化杨辉三角
    void init(int numRows) {
        for (int i = 1; i <= numRows; ++i) {
            for (int j = 1; j <= i; ++j) {
                if (j == 1 || i == j) {
                    a[i][j] = 1;
                } else {
                    a[i][j] = a[i - 1][j] + a[i - 1][j - 1];
                }
            }
        }
    }

    //根据二维数组的每行的元素放入数组
    vector<int> get(int row) {
        vector<int> vIn;
        for (int i = 1; i <= row; ++i) {
            vIn.push_back(a[row][i]);//放入第row行的每个元素
        }
        return vIn;
    }

    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> vOut;
        init(numRows);
        for (int i = 1; i <= numRows; ++i) {
            vOut.push_back(get(i));//将每行的杨辉三角放入容器
        }
        return vOut;
    }
};

思路：

这题主要考察的就是杨辉三角，所以只需要了解杨辉三角的基本性质就可以，这题目的不同的区别就是将杨辉三角的每行的数据放入vector容器里面。

我的主要的思路就是根据给定的行数来生成好杨辉三角，然后题目给定了numRows。遍历numRows，每次将每行里面的元素放入一个vector容器，这个vector再放入需要返回的vector即可。其实这题最主要的就是要知道杨辉三角的性质

$当列数 j == 1时或者和行数 i == j列数 j 时，杨辉三角的值为 1$
$其他的 a [ i ][ j ] = a [ i -1 ] [ j -1 ] + a [ i -1 ] [ j ] $

LeetCode题解

方法一：数学

思路及解法

杨辉三角，是二项式系数在三角形中的一种几何排列。它是中国古代数学的杰出研究成果之一，它把二项式系数图形化，把组合数内在的一些代数性质直观地从图形中体现出来，是一种离散型的数与形的结合。

杨辉三角具有以下性质：

每行数字左右对称，由 $1$ 开始逐渐变大再变小，并最终回到 $1$。
第 $n$ 行（从 $0$ 开始编号）的数字有 $n+1$ 项，前 $n$ 行共有 $\frac{n(n+1)}{2}$ 个数。
第 $n$ 行的第 $m$ 个数（从 $0$ 开始编号）可表示为可以被表示为组合数 $\mathcal{C}(n,m)$，记作 $\mathcal{C}_n^m$或 $\binom{n}{m}$，即为从 $n$ 个不同元素中取 $m$ 个元素的组合数。我们可以用公式来表示它：$\mathcal{C}_n^m=\dfrac{n!}{m!\times (n-m)!}$。
每个数字等于上一行的左右两个数字之和，可用此性质写出整个杨辉三角。即第 $n$ 行的第 $i$ 个数等于第 $n-1$ 行的第 $i-1$ 个数和第 $i$ 个数之和。这也是组合数的性质之一，即：
$\mathcal{C}_n^i=\mathcal{C}_{n-1}^{i}+\mathcal{C}_{n-1}^{i-1}$
$(a+b)^n$ 的展开式（二项式展开）中的各项系数依次对应杨辉三角的第 $n$ 行中的每一项。

依据性质 $4$，我们可以一行一行地计算杨辉三角。每当我们计算出第 $i$ 行的值，我们就可以在线性时间复杂度内计算出第 $i+1$ 行的值。

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> ret(numRows);
        for (int i = 0; i < numRows; ++i) {
            ret[i].resize(i + 1);
            ret[i][0] = ret[i][i] = 1;
            for (int j = 1; j < i; ++j) {
                ret[i][j] = ret[i - 1][j] + ret[i - 1][j - 1];
            }
        }
        return ret;
    }
};
作者：LeetCode-Solution