题目链接：颜色分类

给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地 对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

必须在不使用库内置的 sort 函数的情况下解决这个问题。

方法一：插入排序

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

题目链接：多数元素

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

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

方法一：摩尔投票

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int t = 0,votes = 0;
        for (auto x : nums) {
            if (votes == 0) t = x;
            votes += x == t ? 1 : -1;
        }
        return t;
    }
};

题目链接：最小路径和

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

方法一：二维动态规划

class Solution {
public:
    int dp[210][210];
    int minPathSum(vector<vector<int>>& grid) {
        for (int i = 0;i < grid.size();i++) {
            for (int j = 0;j < grid[0].size();j++) {
                if (i-1 >= 0 && j - 1 >= 0) {
                    dp[i][j] = min(dp[i-1][j] , dp[i][j-1]);
                }else if (i-1 >= 0) dp[i][j] = dp[i-1][j];
                else if (j-1 >= 0) dp[i][j] = dp[i][j-1];
                dp[i][j] += grid[i][j];
            }
        }
        return dp[grid.size()-1][grid[0].size()-1];
    }
};

题目链接：不同路径

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

方法一：二维动态规划

class Solution {
public:
    int dp[110][110];
    int uniquePaths(int m, int n) {
        for (int i = 1;i <= m;i++) {
            dp[i][1] = 1;
        }
        for (int i = 1;i <= n;i++) {
            dp[1][i] = 1;
        }
        for (int i = 2;i <= m;i++) {
            for (int j = 2;j <= n;j++) {
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        return dp[m][n];
    }
};

题目链接：最长有效括号

给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号 子串 的长度。

左右括号匹配，即每个左括号都有对应的右括号将其闭合的字符串是格式正确的，比如 "(()())"。

方法一：栈

class Solution {
public:
    int longestValidParentheses(string s) {
        vector<int> t;
        stack<int> ss;
        for (int i = 0;i < s.size();i++) {
            if (s[i] == '(') {
                ss.push(i);
            }else {
                if (ss.size() && s[ss.top()] == '(') {
                    t.push_back(ss.top());
                    t.push_back(i);
                    ss.pop();
                }
            }
        }
        int ans = 0;
        int tt = 1;
        sort(t.begin(),t.end());
        for (int i = 1;i < t.size();i++) {
            if (t[i] == t[i-1] + 1) {
                tt++;
                ans = max(ans,tt);
            }else {
                
                tt = 1;
            }
        }
        return ans;
    }
};