题目链接：单词搜索

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

方法一：回溯

class Solution {
public:
    int dx[4] = {1,0,-1,0};
    int dy[4] = {0,1,0,-1};
    bool visited[20][20];
    bool ans = false;
    void dfs(vector<vector<char>>& board, string word,int x,int y,int t) {
        if (t >= word.size()) {
            ans = true;
            return ;
        }
        if (x < 0 || x >= board.size() || y < 0 || y >= board[0].size() || visited[x][y]) return;
        if (board[x][y] != word[t]) return ;
        visited[x][y] = true;
        for (int i = 0;i < 4;i++) {
            int tx = x + dx[i];
            int ty = y + dy[i];
            
            dfs(board,word,tx,ty,t+1);
        }
        visited[x][y] = false;
    }
    bool exist(vector<vector<char>>& board, string word) {
        for (int i = 0;i < board.size();i++) {
            for (int j = 0;j < board[0].size();j++) {
                dfs(board,word,i,j,0);
            }
        }
        return ans;
    }
};

题目链接：完全平方数

给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。

完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

方法一：动态规划

class Solution {
public:
    int numSquares(int n) {
        int f[10010];
        //f[0] = 0;
        for (int i = 1;i <= n;i++) {
            f[i] = i;
            for (int j = 1;j * j <= i;j++) {
                f[i] = min(f[i],f[i-j*j]+1);
            }
           // f[i] = minn + 1;
        }
        return f[n];
    }
};

题目链接：最长递增子序列

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

方法一：动态规划

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int f[2550];
        f[0] = 1;
        int ans = 1;
        for (int i = 1;i < nums.size();i++) {
            f[i] = 1;
            for (int j = 0;j < i;j++) {
                if (nums[j] < nums[i]) {
                    f[i] = max(f[i],f[j] + 1);
                    ans = max(ans,f[i]);
                }
            }
        }
        return ans;
    }
};

方法二：贪心+二分

int first_ge(const vector<int>& a, int x) {
    int l = 0, r = (int)a.size(); // [l, r)
    while (l < r) {
        int m = l + (r - l) / 2;
        if (a[m] >= x) r = m;
        else l = m + 1;
    }
    return l; // 第一个 >= x 的位置（可能等于 a.size()）
}

int lengthOfLIS(vector<int>& nums) {
    vector<int> tails;
    for (int x : nums) {
        int i = first_ge(tails, x);
        if (i == (int)tails.size()) tails.push_back(x);
        else tails[i] = x;
    }
    return (int)tails.size();
}

题目链接：乘积最大子数组

给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续 子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

测试用例的答案是一个 32-位 整数。

请注意，一个只包含一个元素的数组的乘积是这个元素的值。

方法一：动态规划

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int u_nums[20010];
        int d_nums[20010];
        u_nums[0] = nums[0] > 0 ? nums[0] : 1;
        d_nums[0] = nums[0] < 0 ? nums[0] : 0;
        int ans = nums[0];
        for (int i = 1;i < nums.size();i++) {
            if (nums[i] >= 0) {
                ans = max(ans,u_nums[i-1] * nums[i]);
                u_nums[i] = max(u_nums[i-1] * nums[i],1);
                d_nums[i] = d_nums[i-1] * nums[i];
            }else {
                ans = max(ans,d_nums[i-1] * nums[i]);
                u_nums[i] = max(d_nums[i-1] * nums[i],1);
                d_nums[i] = u_nums[i-1] * nums[i];
            }
        }
        return ans;
    }
};

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

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

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

方法一：异或

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