题目链接：多数元素

给定一个大小为 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;
    }
};

题目链接：对称二叉树

给你一个二叉树的根节点 root ， 检查它是否轴对称。

方法一：递归

/**
 * 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 check(TreeNode* l,TreeNode* r) {
        if (!l && !r) return true;
        if (!l || !r) return false;
        return l->val == r->val && check(l->left,r->right) && check(l->right,r->left);
    }
    bool isSymmetric(TreeNode* root) {
        return check(root->left,root->right);
    }
};

题目链接：只出现一次的数字

给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

方法一：异或

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ans = 0;
        for (auto t : nums) ans ^= t;
        return ans;
    }
};

题目链接：杨辉三角

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

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

方法一：动态规划

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> ans;
        ans.push_back({1});
        for (int i = 1;i < numRows;i++) {
            vector<int> tmp;
            for (int j = 0;j <= i;j++) {
                
                if (j == 0 || j == i) tmp.push_back(1);
                else {
                    tmp.push_back(ans[i-1][j-1] + ans[i-1][j]);
                }
            }
            ans.push_back(tmp);
        }
        return ans;
    }
};

题目链接：爬楼梯

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

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

方法一：动态规划

class Solution {
public:
    int climbStairs(int n) {
        int f[50];
        f[1] = 1;
        f[2] = 2;
        f[3] = 3;
        for (int i = 4;i <= n;i++) {
            f[i] = f[i-2] + f[i-1];
        }
        return f[n];
    }
};

方法二：递归

class Solution {
public:
    int nums[50] = {0};

    int f(int x) {
        if (x <= 2) return nums[x];
        if (nums[x] != 0) return nums[x];   // 关键：已经算过就直接返回

        nums[x] = f(x - 1) + f(x - 2);
        return nums[x];
    }

    int climbStairs(int n) {
        nums[1] = 1;
        nums[2] = 2;
        return f(n);
    }
};