面试经典150题

合并两个有序数组

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

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

直接合并后排序

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());
    }
};

双指针
合并后排序没有利用数组nums1与nums已经被排序的性质。

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int sorted[m+n];
        int index = 0, i = 0, j = 0;
        while(i < m && j < n){
            if(nums1[i] <= nums2[j]){
                sorted[index++] = nums1[i++];
            }else{
                sorted[index++] = nums2[j++];
            }
        }
        while(i < m){
            sorted[index++] = nums1[i++];
        }
        while(j < n){
            sorted[index++] = nums2[j++];
        }
        for(i=0; i<m+n; i++){
            nums1[i] = sorted[i];
        }
    }
};

逆向双指针
之所以要使用临时变量，是因为如果直接合并到nums1中，nums1中的元素可能在取出之前被覆盖。

如何直接避免覆盖nums1中的元素呢？

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int index = m + n -1, i = m-1, j = n-1;
        while(i >= 0 && j >= 0){
            if(nums1[i] >= nums2[j]){
                nums1[index--] = nums1[i--];
            }else{
                nums1[index--] = nums2[j--];
            }
        }
        while(i >= 0){
            nums1[index--] = nums1[i--];
        }
        while(j >= 0){
            nums1[index--] = nums2[j--];
        }
    }
};

移除元素

给一个数组nums和一个值val，需要移除所有数值等于val的元素，并返回不同于val的元素的数量。

双指针

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int left = 0;
        int right = 0;
        int n = nums.size();
        while(right < n){
            if(nums[right] != val){
                nums[left++] = nums[right];
            }
            right++;
        }
        return left;
    }
};

双指针优化
如果要移除的元素在数组的开头，例如序列[1,2,3,4,5]，当val为1时，我们需要把每一个元素都左移一位。
注意元素顺序可以改变，那么直接将5移动到序列开头。

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

删除有序数组中的重复项

原地删除重复出现的元素，使每个元素只出现一次。

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int left = 0;
        int right = 1;
        int n = nums.size();
        while(right < n){
            if(nums[left] != nums[right]){
                left++;
                nums[left] = nums[right];
            }
            right++;
        }
        return left+1;
    }
};

三角形最小路径和

给定一个三角形，找出自顶向下的最小路径和。

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int m = triangle.size();
        int n = triangle[0].size();
        vector<vector<int>> dp(m);
        for(int i=0; i<m ;i++){
            dp[i] = vector<int>(i+1,0);
        }
        dp[0][0] = triangle[0][0];
        for(int i=1; i<m; i++){
            for(int j=0; j<=i; j++){
                if(j == 0){
                    dp[i][j] = dp[i-1][j] + triangle[i][j];
                }else if(j == i){
                    dp[i][j] = dp[i-1][j-1] + triangle[i][j];
                }else{
                    dp[i][j] = min(dp[i-1][j-1], dp[i-1][j])+triangle[i][j];
                }
            }
        }
        return *std::min_element(dp[m-1].begin(), dp[m-1].end());
    }
};

最大正方形

暴力法
使用dp[i][j]表示以（i,j）为右下角，且只包含1的正方形的边长最大值。如果我们能计算出所有dp[i][j]的值，那么其中的最大值即为矩阵中只包含1的正方形的边长的最大值，其平方就是最大正方形的面积。

对于每个位置(i,j)，检查在矩阵中该位置的值：

• 如果该位置的值是0，则dp[i][j]=0，因为当前位置不可能在由1组成的正方形中；
• 如果该位置的值是1，则dp[i][j]的值由其上方，左方和左上方决定。

此外，还需要考虑边界条件，如果i和j中至少有一个为0，则以此位置为右下角的最大正方形的边长只能是1，因此dp[i][j] = 1。

class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        int maxSide = 0;
        int rows = matrix.size(), columns = matrix[0].size();
        vector<vector<int>> dp(rows, vector<int>(columns));

        for(int i=0; i<rows; i++){
            for(int j=0; j<columns; j++){
                if(matrix[i][j] == '1'){
                    if(i == 0 || j == 0){
                        dp[i][j] = 1;
                    }else{
                        dp[i][j] = min(min(dp[i-1][j], dp[i-1][j-1]), dp[i][j-1]) + 1;
                    }
                    maxSide = max(maxSide, dp[i][j]);
                }
            }
        }
        return maxSide * maxSide;
    }
};

课程表

这学期必须学numCourses门课程，选修某些课程之前需要一些先修课程。

本题是一道经典的拓扑排序问题。

给定一个包含n个节点的有向图G，我们给出它的节点编号的一种排列，如果满足：
对于图G中的任意一条有向边(u,v)，u在排列中都出现在v的签名。那么称该排列是图G的拓扑排序。

深度优先搜索
我们可以将深度优先搜索的流程与拓扑排序的求解联系起来，用一个栈存储所有已经搜索完成的节点。

对于一个节点u，如果它的所有相邻节点都已经搜索完成，那么回溯到u的时候，u本身也会变成一个已经搜索完成的节点。

多数元素

给定一个大小为n的数组nums，返回其中的多数元素。多数元素是指在数组中出现次数大于n/2的元素。

哈希表
使用哈希映射（HashMap）来存储每个元素以及出现的次数。对于哈希映射中的每个键值对，键表示一个元素，值表示该元素出现的次数。

我们用一个循环遍历数组nums，并将数组中的每个元素加入哈希映射中。
同样在遍历数组nums时候使用打擂台的方式，维护最大值，这样就省去了最后对哈希映射的遍历。

相同的树

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if(p == nullptr && q == nullptr){
            return true;
        }
        if((p == nullptr && q != nullptr) || (p != nullptr && q == nullptr)){
            return false;
        }
        bool leftCheck = isSameTree(p->left, q->left);
        bool rightCheck = isSameTree(p->right, q->right);
        return leftCheck && rightCheck && (p->val == q->val);
    }
};