6月1日 1431. 拥有最多糖果的孩子（简单）

给你一个数组 candies 和一个整数 extraCandies ，其中 candies[i] 代表第 i 个孩子拥有的糖果数目。
对每一个孩子，检查是否存在一种方案，将额外的 extraCandies 个糖果分配给孩子们之后，此孩子有最多的糖果。注意，允许有多个孩子同时拥有最多的糖果数目。
示例：

1
2
3

输入：candies = [4,2,1,1,2], extraCandies = 1
输出：[true,false,false,false,false] 
解释：只有 1 个额外糖果，所以不管额外糖果给谁，只有孩子 1 可以成为拥有糖果最多的孩子。

提示：

1
2
3

2 <= candies.length <= 100
1 <= candies[i] <= 100
1 <= extraCandies <= 50

题解：
如果采用暴力法，在每个孩子的糖果数上加上extraCandies再与其他孩子比，时间复杂度为O(n2)。
可以先找出最大值most，遍历时与most-extraCandies比较，此时只需O(n)。
找数组中的最大值可以自己实现，也可以使用STL实现。

int getMostCandies(vector<int>& candies){
    int most = 0;
    for(int n:candies){
        if(n>most)
            most = n;
    }
    return most;
}
vector<bool> kidsWithCandies(vector<int>& candies, int extraCandies) {
    int most = getMostCandies(candies);
    vector<bool> isMostCandies(candies.size());
    for(int i=0;i<candies.size();i++){
        if(most-candies[i]>extraCandies)
            isMostCandies[i] = false;
        else
            isMostCandies[i] = true;
    }
    return isMostCandies;
}

6月2日剑指Offer面试题64. 求1+2+…+n

求 1+2+...+n ，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。
1 <= n <= 10000
题解：
通常实现递归的时候我们都会利用条件判断语句来决定递归的出口，但由于题目的限制我们不能使用条件判断语句，所以我们使用逻辑运算符的短路性质：
以逻辑运算符 && 为例，对于 A && B 这个表达式，如果 A 表达式返回 False ，那么 A && B 已经确定为 False ，此时不会去执行表达式 B。同理，对于逻辑运算符 ||，对于 A || B 这个表达式，如果 A 表达式返回 True ，那么 A || B 已经确定为 True ，此时不会去执行表达式 B。

int sumNums(int n) {
    n && (n += sumNums(n-1));
    return n;
}

6月3日 837. 新21点（中等）

爱丽丝参与一个大致基于纸牌游戏 “21点” 规则的游戏，描述如下：
爱丽丝以 0 分开始，并在她的得分少于 K 分时抽取数字。抽取时，她从 [1, W] 的范围中随机获得一个整数作为分数进行累计，其中 W 是整数。每次抽取都是独立的，其结果具有相同的概率。
当爱丽丝获得不少于 K 分时，她就停止抽取数字。爱丽丝的分数不超过 N 的概率是多少？
示例：

1 2	输入：N = 21, K = 17, W = 10 输出：0.73278

提示：

1 2	0 <= K <= N <= 10000 1 <= W <= 10000

题解：
dp[x]为她已经获得的分数为x时，能获胜的概率。

dp[x] = (dp[x+1]+dp[x+2]+dp[x+3]...+dp[x+W])/W
dp[x-1] = (dp[x]+dp[x+1]+dp[x+2]...+dp[x-1+W])/W
dp[x-1]-dp[x] = (dp[x]-dp[x-1+W])/W

最后公式为：

dp[x] = x <= N ? 1 : 0&emsp;&emsp;K <= x < K+W
dp[K-1] = (dp[K]+dp[K+1]+dp[K+2]...+dp[K-1+W])/W
dp[x-1] = dp[x] + (dp[x]-dp[x+W])/W&emsp;&emsp;0 <= x < K-1

如果不求dp[x]与dp[x-1]的状态转移方程，可以用概率和的状态转移方程代替：

sumOfW[x] = sumOfW[x+1] - dp[x+W] + dp[x]

因为抽取点数机会都是均等的，她能抽取的面值在[1,W]之间，所以将概率之和平均一下就是dp[x]的概率。
她可能达到的最大牌面是K-1+W，而一开始她的牌面是0，所以我们用一个长度为K+W的dp数组来保存她在所有面值下的胜率。
dp[0]就是最开始爱丽丝还没有抽牌时的胜率。

使用dp状态转移方程：

double new21Game(int N, int K, int W) {
    if(K==0)
        return 1.0;
    vector<double> dp(K + W);
    double sumOfW = 0;
    for (int i = K; i < K + W;i++){
        dp[i] = i <= N ? 1.0 : 0.0;
        sumOfW += dp[i];
    }
    dp[K - 1] = sumOfW / W;
    for (int i = K - 2; i >= 0; i--)
    {
        dp[i] = dp[i + 1] + (dp[i + 1] - dp[i +1 + W]) / W;
    }
    return dp[0];
}

使用概率和状态转移方程：

double new21Game(int N, int K, int W) {
    vector<double> dp(K + W + 1);
    double sumOfW = 0;
    for (int i = K; i < K + W;i++){
        //不能抽牌时，超过N为0，不超过N为1
        dp[i] = i <= N ? 1 : 0;
        sumOfW += dp[i];//为了方便求sum(dp[x+1]...dp[x+W])
    }
    for (int i = K - 1; i >= 0;i--){
        //使用分析中的公式
        dp[i] = sumOfW / W;
        sumOfW = sumOfW - dp[i + W] + dp[i];
    }
    return dp[0];
}

6月4日 238. 除自身以外数组的乘积（中等）

给你一个长度为 n 的整数数组 nums，其中 n > 1，返回输出数组 output ，其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。
示例:

1 2	输入: [1,2,3,4] 输出: [24,12,8,6]

提示： 题目数据保证数组之中任意元素的全部前缀元素和后缀（甚至是整个数组）的乘积都在 32 位整数范围内。
说明: 请不要使用除法（数组中有0时失效），且在 O(n) 时间复杂度内完成此题。

题解：

时间复杂度O(N)，空间复杂度O(N)的方法：
利用左侧所有数字的乘积和右侧所有数字的乘积相乘得到：通过两次遍历（从前向后，从后向前）得到两个乘积表：
productOfLeft(n)和productOfRight(n)
productOfLeft(i) = productOfLeft[i-1] * nums[i-1]表示nums[i]左边所有数的乘积，其中productOfLeft(0)=1；
productOfRight(i) = productOfRight[i+1] * nums[i+1]表示nums[i]右边所有数的乘积，其中productOfLeft(n-1)=1。

vector<int> productExceptSelf(vector<int>& nums) {
    int n = nums.size();

    vector<int> productOfLeft(n,0), productOfRight(n,0), output(n,0);
    
    productOfLeft[0] = 1;
    for(int i=1;i<n;i++)
        productOfLeft[i] = productOfLeft[i-1] * nums[i-1];
    
    productOfRight[n-1] = 1;
    for(int i = n-2;i>=0;i--)
        productOfRight[i] = productOfRight[i+1] * nums[i+1];

    for(int i = 0;i<n;i++)
        output[i] = productOfLeft[i] * productOfRight[i];

    return output;
}

时间复杂度O(N)，空间复杂度O(1)的方法，这是对上面方法的优化：
1）把productOfLeft(n)存放都output(n)中（输出数组不算占用空间）
2）用一个int来代替productOfRight(n)

vector<int> productExceptSelf(vector<int>& nums) {
    int n = nums.size();

    vector<int> output(n,0);
    
    output[0] = 1;
    for(int i=1;i<n;i++)
        output[i] = output[i-1] * nums[i-1];
    
    int productOfRight = 1;
    for(int i = n-1;i>=0;i--){
        output[i] = output[i] * productOfRight;
        productOfRight *= nums[i];
    }

    return output;
}

6月5日剑指Offer面试题29. 顺时针打印矩阵（简单）

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。
示例：

1 2	输入：matrix = [[1,2,3],[4,5,6],[7,8,9]] 输出：[1,2,3,6,9,8,7,4,5]

题解：
顺时针访问矩阵共有4个遍历方向，依次循环直到全部访问：1）从左到右；2）从上到下；3）从右到左；4）从下到上。
关键是方向改变的判定条件。

可以设置一个hasVisited[row][col]数组来不标记访问过的元素。这需要这样的话空间复杂度为O(row*col)。

也可以使用4个int分别表示上下左右的访问边界，每次变换方向，就把该行/列的边界向里面缩一行。

第二种方法的代码：
时间复杂度O(row*col)：其中 row 和 col 分别是输入矩阵的行数和列数。矩阵中的每个元素都要被访问一次。
空间复杂度：O(1)。除了输出数组以外，只需要4个int来表示边界。

vector<int> spiralOrder(vector<vector<int>>& matrix) {
    vector<int> result;
    if(matrix.empty())
        return result;
    int upWall = 0,downWall = matrix.size()-1,leftWall = 0,rightWall = matrix[0].size()-1;
    //1 L To R; 2 Up To D; 3R To L; 4 D To Up
    int dir = 1;
    int row = 0, col = 0;
    while(upWall<=downWall && leftWall<=rightWall){
        result.push_back(matrix[row][col]);
        if(dir==1){//从左到右
            if(col!=rightWall)
                col++;
            else{
                row++;
                upWall++;
                dir = 2;
            }
        }else if(dir==2){//从上到下
            if(row!=downWall)
                row++;
            else{
                col--;
                rightWall--;
                dir = 3;
            }
        }else if(dir==3){//从右到左
            if(col!=leftWall)
                col--;
            else{
                row--;
                downWall--;
                dir = 4;
            }
        }else{//从下到上
            if(row!=upWall)
                row--;
            else{
                col++;
                leftWall++;
                dir = 1;
            }
        }
    }
    return result;
}

6月6日 128. 最长连续序列（困难）

给定一个未排序的整数数组，找出最长连续序列的长度。
要求算法的时间复杂度为 O(n)。
示例:

1
2
3

输入: [100, 4, 200, 1, 3, 2]
输出: 4
解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。

题解：

暴力枚举。最外层枚举每一个元素O(n)；每个数要找它的前一个和后一个连续数O(n)；在数组中定位一个元素，暴力法O(n)，map、set这些红黑树实现的O（lgn），哈希表O(1)。所以纯暴力法时间复杂度O(n3)，最优也是用哈希表的O(n2)。

排序。时间复杂度为O(n*lgn)。虽然不满足要求，但是提交能过。
排序后用双指针，遍历一遍O(n)。（去重可以用stl库的unique函数，这里直接设置一个重复计数器eqNums，最后减掉重复数即可）

int longestConsecutive(vector<int>& nums) {
    if(nums.size()==0)
        return 0;
    sort(nums.begin(),nums.end());
    int idxL = 0, idxR = 0, maxSub = 1, eqNums = 0;
    for(int i = 1;i<nums.size();i++){
        if(nums[i]==nums[i-1]){
            idxR++;
            eqNums++;
        }else if(nums[i]==nums[i-1]+1){
            idxR++;
            maxSub = max(maxSub,idxR-idxL+1-eqNums);
        }else{
            maxSub = max(maxSub,idxR-idxL+1-eqNums);
            idxL = i;
            idxR = i;
            eqNums = 0;
        }
    }
    return maxSub;
}

使用哈希表(unordered_set)一遍遍历O(n)。在进入while循环，以当前数字为首增加currentSub时，先在哈希表中寻找前一位数字是否存在。只有前一位不存在，才开始以当前数字为首扩充子序列。

int longestConsecutive(vector<int>& nums) {
    unordered_set<int> num_set;
    for (const int& num : nums) {
        num_set.insert(num);
    }
    int maxSub = 0;
    for (const int& num : num_set) {
        if (!num_set.count(num - 1)) {
            int currentNum = num;
            int currentSub = 1;

            while (num_set.count(currentNum + 1)) {
                currentNum += 1;
                currentSub += 1;
            }

            maxSub = max(maxSub, currentSub);
        }
    }
    return maxSub;           
}

并查集(视频讲解)
什么是并查集
代码：
初始化的时候先把数组里每个元素初始化为他的下一个数；
并的时候找他能到达的最远的数字就可以了。

unordered_map<int,int> a;
int find(int x){
    return a.count(x)?a[x]=find(a[x]):x;
}
int longestConsecutive(vector<int>& nums) {
    for(auto i:nums)
        a[i]=i+1;
    int maxSub=0;
    for(auto i:nums){
        int y=find(i+1);
        maxSub=max(maxSub,y-i);
    }
    return maxSub;
}

6月7日 126. 单词接龙 II（困难）

给定两个单词（beginWord 和 endWord）和一个字典 wordList，找出所有从 beginWord 到 endWord 的最短转换序列。转换需遵循如下规则：
每次转换只能改变一个字母；转换过程中的中间单词必须是字典中的单词。
说明:
如果不存在这样的转换序列，返回一个空列表。
所有单词具有相同的长度。
所有单词只由小写字母组成。
字典中不存在重复的单词。
你可以假设 beginWord 和 endWord 是非空的，且二者不相同。
示例 1:

输入:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]
输出:
[
  ["hit","hot","dot","dog","cog"],
  ["hit","hot","lot","log","cog"]
]

示例 2:

输入:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]
输出: []
解释: endWord "cog" 不在字典中，所以不存在符合要求的转换序列。

题解：

回溯算法。先建图，然后找出所有路径，然后再从所有路径中找出最短路径。
建图时间复杂度：建图需要外层枚举O(n)，里层遍历O(n)，两个单词之间的比较O(m)（m为单词的长度）。所以时间复杂度为O(n2*m)。
但是在回溯算法找路径时，时间会随字典中的单词数成指数增长。
下面代码能通过19/39，最后超时

bool isConnection(string word1, string word2){
    int diff = 0;
    for (int i = 0; i < word1.size() && diff<=1 ;i++){
        if(word1[i]!=word2[i])
            diff++;
    }
    return diff == 1;
}

vector<vector<int> > buildGraphic(vector<string>& wordList){
    int N = wordList.size();
    vector<vector<int> > graphic(N);
    for (int i = 0; i < N; i++){
        string curWord = wordList[i];
        for (int j = 0; j < N; j++)
        {
            string nextWord = wordList[j];
            if (isConnection(curWord,nextWord))
                graphic[i].push_back(j);
        }
    }
    for(auto g:graphic){
        for(int n:g)
            cout << n << " ";
        cout << endl;
    }
    cout << "build graphic done" << endl;
    return graphic;
}

void backTracking(vector<string> &wordList, vector<vector<int> > &graphic, vector<bool> &hasVisted, vector<string> &preWord, vector<vector<string> > &result, string endWord, int current)
{
    if (wordList[current] == endWord)
    {
        result.push_back(preWord);
        return;
    }
    for(int next : graphic[current]){
        if(hasVisted[next])
            continue;
        preWord.push_back(wordList[next]);
        hasVisted[next] = true;
        backTracking(wordList, graphic, hasVisted, preWord, result, endWord, next);
        hasVisted[next] = false;
        preWord.pop_back();
    }
}

vector<vector<string> > findLadders(string beginWord, string endWord, vector<string>& wordList) {
    vector<vector<string> > resultAll;
    vector<string>::iterator it = find(wordList.begin(), wordList.end(), endWord);
    if(it==wordList.end())//wordList中没有endWord
        return resultAll;
    wordList.push_back(beginWord);

    vector<vector<int> > graphic = buildGraphic(wordList);

    vector<bool> hasVisted(wordList.size(), false);
    hasVisted[wordList.size() - 1] = true;//beginWord
    vector<string> preWord;
    preWord.push_back(beginWord);
    backTracking(wordList, graphic, hasVisted, preWord, resultAll, endWord, wordList.size() - 1);

    int less = wordList.size();
    vector<vector<string> > result;
    for (auto res : resultAll)//找长度最小值
        less = res.size() < less ? res.size() : less;
    for(auto res : resultAll){//过滤长度最小的
        if(res.size()==less)
            result.push_back(res);
    }

    return result;
}

先通过BFS找到最短路径长度（方法可以看我的算法总结：查找/BFS 专题中的62题），然后再在方法1回溯的时候加上路径长度条件。
虽然减少了一些分支，但是还是最坏情况的时间复杂度还是和1一样，与单词数成指数相关。
21/39个通过，最后超时

bool isConnection(string word1, string word2){
    int diff = 0;
    for (int i = 0; i < word1.size() && diff<=1 ;i++){
        if(word1[i]!=word2[i])
            diff++;
    }
    return diff == 1;
}

vector<vector<int> > buildGraphic(vector<string>& wordList){
    int N = wordList.size();
    vector<vector<int> > graphic(N);
    for (int i = 0; i < N; i++){
        string curWord = wordList[i];
        for (int j = 0; j < N; j++)
        {
            string nextWord = wordList[j];
            if (isConnection(curWord,nextWord))
                graphic[i].push_back(j);
        }
    }
    return graphic;
}

int getShortestPath(vector<string> &wordList, vector<vector<int> > &graphic, string endWord){
    int N = graphic.size();
    vector<bool> hasVisited(N, false);
    hasVisited[N - 1] = true;
    queue<int> que;
    que.push(N - 1);//beginWord
    int shortestPath = 1;
    while (!que.empty())
    {
        shortestPath++;
        int size = que.size();
        while(size-- > 0){
            int current = que.front();
            que.pop();
            for(int next : graphic[current]){
                if(wordList[next]==endWord)
                    return shortestPath;
                if(hasVisited[next])
                    continue;
                hasVisited[next] = true;
                que.push(next);
            }
        }
    }
    return 0;
}

void backTracking(vector<string> &wordList, vector<vector<int> > &graphic, vector<bool> &hasVisted, vector<string> &preWord, vector<vector<string> > &result, string endWord, int current, int curPath, int shortestPath)
{
    if(curPath>shortestPath)
        return;
    if (wordList[current] == endWord)
    {
        result.push_back(preWord);
        return;
    }
    for(int next : graphic[current]){
        if(hasVisted[next])
            continue;
        preWord.push_back(wordList[next]);
        hasVisted[next] = true;
        backTracking(wordList, graphic, hasVisted, preWord, result, endWord, next, curPath+1, shortestPath);
        hasVisted[next] = false;
        preWord.pop_back();
    }
}

vector<vector<string> > findLadders(string beginWord, string endWord, vector<string>& wordList) {
    vector<vector<string> > result;
    vector<string>::iterator it = find(wordList.begin(), wordList.end(), endWord);
    if(it==wordList.end())//wordList中没有endWord
        return result;
    wordList.push_back(beginWord);

    vector<vector<int> > graphic = buildGraphic(wordList);

    int shortestPath = getShortestPath(wordList, graphic, endWord);

    vector<bool> hasVisted(wordList.size(), false);
    hasVisted[wordList.size() - 1] = true;//beginWord
    vector<string> preWord;
    preWord.push_back(beginWord);
    backTracking(wordList, graphic, hasVisted, preWord, result, endWord, wordList.size() - 1, 1, shortestPath);

    return result;
}

反向BFS建图，从endWord开始向上BFS，同时记录每个结点的父结点。再从beginWord开始回溯。
（代码略）

双向BFS建图。
使用unordered_map<string, vector<string> > graphic来记录单词的子结点，string是wordList中的单词，vector<string>是可以与string连接的子结点（与这个string只有一个字母之差且存在与字典中的集合）。

vector<vector<string> > result;

bool isConnection(string word1, string word2){
    int diff = 0;
    for (int i = 0; i < word1.size() && diff<=1 ;i++){
        if(word1[i]!=word2[i])
            diff++;
    }
    return diff == 1;
}

unordered_map<string, vector<string> > buildGraphic(vector<string>& wordList, string beginWord, string endWord){
    unordered_map<string, vector<string>> graphic; //存储string能连接到的下一层结点
    unordered_set<string> dict(wordList.begin(), wordList.end());
    unordered_set<string> beginToEnd{beginWord};
    unordered_set<string> endToBegin{endWord};
    bool findShortest = false; //是否找到最短序列标志,
    bool dirction = 0; //方向标志。0:begin to end   1:end to begin
    while(!beginToEnd.empty()){
        unordered_set<string> nextLayer;
        for (string s : beginToEnd) //把图里已经有的从list中删除
            dict.erase(s);
        for(string curStr:beginToEnd){//建立下一层连接
            for(string nextStr:dict){
                if(isConnection(curStr,nextStr)){
                    if(endToBegin.find(nextStr) != endToBegin.end())//双边遍历碰到了
                        findShortest = true;
                    else
                        nextLayer.insert(nextStr);
                    dirction ? graphic[nextStr].push_back(curStr) : graphic[curStr].push_back(nextStr);
                }
            }
        }
        if(findShortest)
            break;
        if(nextLayer.size()<=endToBegin.size())
            beginToEnd = nextLayer;
        else{
            beginToEnd = endToBegin;
            endToBegin = nextLayer;
            dirction = !dirction;//end和begin反转，方向标志也要反转
        }
    }

    return graphic;
}

void backTracking(unordered_map<string, vector<string> > &graphic, vector<string>& preWords, string beginWord, string endWord)
{
    if (beginWord == endWord)
    {
        result.push_back(preWords);
        return;
    }
    if(graphic.find(beginWord) == graphic.end())
        return;
    for(string str:graphic[beginWord]){
        preWords.push_back(str);
        backTracking(graphic, preWords, str, endWord);
        preWords.pop_back();
    }
}

vector<vector<string> > findLadders(string beginWord, string endWord, vector<string>& wordList) {
    vector<string>::iterator it = find(wordList.begin(), wordList.end(), endWord);
    if(it==wordList.end())//wordList中没有endWord
        return result;

    unordered_map<string, vector<string> > graphic = buildGraphic(wordList, beginWord, endWord);

    vector<string> preWords = {beginWord};

    backTracking(graphic, preWords, beginWord, endWord);

    return result;
}

时间复杂度：
建图需要O(n^2)。建图时比较两个单词是否可以连接需要O(c)，c为单词的长度。普通BFS时间复杂度为O(n2)。
回溯需要O(2^m)，m为建好的图中的单词数。
普通BFS建图中单词数m=n，双向BFS建图可以大大减少图中的单词数。

6月8日 990. 等式方程的可满足性（中等）

给定一个由表示变量之间关系的字符串方程组成的数组，每个字符串方程 equations[i] 的长度为 4，并采用两种不同的形式之一：”a==b” 或 “a!=b”。在这里，a 和 b 是小写字母（不一定不同），表示单字母变量名。

只有当可以将整数分配给变量名，以便满足所有给定的方程时才返回 true，否则返回 false。

示例 1：

1
2
3

输入：["a==b","b!=a"]
输出：false
解释：如果我们指定，a = 1 且 b = 1，那么可以满足第一个方程，但无法满足第二个方程。没有办法分配变量同时满足这两个方程。

示例 2：

1
2
3

输出：["b==a","a==b"]
输入：true
解释：我们可以指定 a = 1 且 b = 1 以满足满足这两个方程。

示例 3：

1 2	输入：["a==b","b==c","a==c"] 输出：true

示例 4：

1 2	输入：["a==b","b!=c","c==a"] 输出：false

示例 5：

1 2	输入：["c==c","b==d","x!=z"] 输出：true

提示：

1 <= equations.length <= 500
equations[i].length == 4
equations[i][0] 和 equations[i][3] 是小写字母
equations[i][1] 要么是 '='，要么是 '!'
equations[i][2] 是 '='

题解：
这题需要用到并查集，相关专题可以查看我的博客。
把相等的左右两边放到一个子集里面，然后看不相等的是否在同一个子集里。如果在同一个子集的两个字母不相等返回false。

class UnionFind {
private:
    vector<int> parent;

public:
    UnionFind() {
        parent.resize(26);
        iota(parent.begin(), parent.end(), 0);
    }

    int find(int index) {
        if (index == parent[index]) {
            return index;
        }
        parent[index] = find(parent[index]);
        return parent[index];
    }

    void unite(int index1, int index2) {
        parent[find(index1)] = find(index2);
    }
};

class Solution {
public:
    bool equationsPossible(vector<string>& equations) {
        UnionFind uf;
        for (const string& str: equations) {
            if (str[1] == '=') {
                int index1 = str[0] - 'a';
                int index2 = str[3] - 'a';
                uf.unite(index1, index2);
            }
        }
        for (const string& str: equations) {
            if (str[1] == '!') {
                int index1 = str[0] - 'a';
                int index2 = str[3] - 'a';
                if (uf.find(index1) == uf.find(index2)) {
                    return false;
                }
            }
        }
        return true;
    }
};

6月9日剑指Offer面试题46. 把数字翻译成字符串（中等）

给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。
示例 1:

1
2
3

输入: 12258
输出: 5
解释: 12258有5种不同的翻译，分别是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"

提示：

1	0 <= num < 2^31

题解：
典型的动态规划题，同类型例题可以看我的算法总结中的动态规划专题
dp[i]表示第 i 位数字之前（含）的不同翻译种数，i=[1,n]，dp[0]是为了递推方便初始化的，没有实际意义。
有两种情况：

dp[i] = dp[i-1]前2位中的第一位是为0，如求506的dp[3]时，前一位为0，所以dp[3] = dp[2]；前面两位数字大于25，如535，其中35不能翻译为字母，所以dp[3]=dp[2]

dp[i] = dp[i-1] + dp[i-2]如516，dp[3]=dp[2]+dp[1]：516的翻译方法等于5的翻译种数（尾巴添16），加上51的翻译方法种数（尾巴添6）。

int translateNum(int num){
    string numStr = to_string(num);
    int n = numStr.size();
    vector<int> dp(n + 1);
    dp[0] = 1, dp[1] = 1;//dp[i]表示第i数字之前（含）的不同翻译种数，i=[1,n]，dp[0]是为了递推方便初始化的，没有实际意义
    for (int i = 2; i <= n; i++)
    {   
        string pre1num = numStr.substr(i - 2, 1);//看前面2位中的第一位是否为0
        string pre2num = numStr.substr(i - 2, 2);
        dp[i] = (stoi(pre2num) > 25 || stoi(pre1num)==0) ? dp[i - 1] : dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

时间复杂度O(n)
空间复杂度O(n)。因为只用到前面2个，所以可以优化为O(1)，只用dp[0],dp[1],dp[2]（代码略）。

6月10日回文数（简单）

判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。

示例 1:

1 2	输入: 121 输出: true

示例 2:

1
2
3

输入: -121
输出: false
解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。

题解：

将数字转换为字符串，设置双指针idxL和idxR，分别指向字符串的头和尾。两个指针边比较边向中间移动。

bool isPalindrome(int x) {
    if(x<0)
        return false;
    string numStr = to_string(x);
    int idxL = 0, idxR = numStr.size() - 1;
    while (idxR>idxL)
    {
        if(numStr[idxL]!=numStr[idxR])
            return false;
        else{
            idxL++;
            idxR--;
        }
    }
    return true;
}

时间复杂度O(n)
空间复杂度O(n)
n是数字的位数

不转换成字符串。当x位数为偶数时只用看后一半反转后与前一半是否相等；当x位数为奇数时，我们可以通过 revertedNum/10 去除处于中位的数字。

bool isPalindrome(int x) {
    if(x<0 || (x % 10 == 0 && x != 0))//末尾是0的也不可能是回文
        return false;
    int revertedNum = 0;
    while(x > revertedNum){//已经到一半了
        revertedNum = revertedNum * 10 + x % 10;
        x /= 10;
    }
    return x == revertedNum || x == revertedNum / 10;
}

6月11日 739. 每日温度（中等）

根据每日 气温 列表，请重新生成一个列表，对应位置的输出是需要再等待多久温度才会升高超过该日的天数。如果之后都不会升高，请在该位置用 0 来代替。

例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。

提示：

1	气温列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度，都是在 [30, 100] 范围内的整数。

题解：

纯暴力法（超时）。

vector<int> dailyTemperatures(vector<int>& T) {
    vector<int> res(T.size(),0);
    for(int i=0;i<T.size();i++){
        for(int j=i+1;j<T.size();j++){
            if(T[j]>T[i]){
                res[i] = j-i;
                break;
            }
        }
    }
    return res;
}

时间复杂度O(n^2)。空间复杂度(1)。

温度数组加暴力。由于温度范围在[30, 100]之内，因此可以维护一个数组tempFirstPos记录每个温度第一次出现的下标。数组tempFirstPos中的元素初始化为n，因为数组的最大索引为n-1。在反向遍历温度列表的过程中更新 tempFirstPos 的值。

vector<int> dailyTemperatures(vector<int>& T) {
    int n = T.size();
    vector<int> res(n), tempFirstPos(101, n);
    for (int i = n - 1; i >= 0; i--) {
        int warmerIndex = n;//最大值为数组长度
        for (int t = T[i] + 1; t <= 100; t++) {
            warmerIndex = min(warmerIndex, tempFirstPos[t]);
        }
        if (warmerIndex != n) {
            res[i] = warmerIndex - i;
        }
        tempFirstPos[T[i]] = i;
    }
    return res;
}

时间复杂度O(n*m)，n是数组长度，m是温度的范围。空间复杂度O(n)。

单调栈。维护一个单调递减的栈，栈中元素为温度值的索引。当前温度比栈顶索引温度低时，直接进栈；当前温度比栈顶索引温度高时，两个索引之间的差就是栈顶索引值所求结果。
视频讲解

vector<int> dailyTemperatures(vector<int>& T) {
    int n = T.size();
    vector<int> res(n,0);
    stack<int> s;
    for (int i = 0; i < n; ++i) {
        while (!s.empty() && T[i] > T[s.top()]) {
            int previousIndex = s.top();
            res[previousIndex] = i - previousIndex;
            s.pop();
        }
        s.push(i);
    }
    return res;
}

时间复杂度O(n)。空间复杂度O(n)。

6月12日 15. 三数之和

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例：

给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为：
[
  [-1, 0, 1],
  [-1, -1, 2]
]

题解：

暴力（超时）

vector<vector<int>> threeSum(vector<int>& nums) {
    int n = nums.size();
    set<vector<int> > resultSet;
    vector<vector<int> > result;
    if (n < 3)
        return result;
    for (int i = 0; i < n; i++)
    {
        for (int j = i + 1; j < n; j++){
            for (int k = j + 1; k < n; k++){
                if(nums[i]+nums[j]+nums[k]==0){
                    vector<int> tmp;
                    tmp.push_back(nums[i]);
                    tmp.push_back(nums[j]);
                    tmp.push_back(nums[k]);
                    sort(tmp.begin(), tmp.end());
                    resultSet.insert(tmp);
                }
            }
        }
    }
    for(auto s:resultSet){
        result.push_back(s);
    }
    return result;
}

311 / 313 个通过测试用例
时间复杂度O(n^3)，空间复杂度O(1)

把最里面一层改为二分查找，需要先排序。还是超时。

bool biSearch(int resNum, int &idx, vector<int>& nums){
    int idxL = 0, idxR = nums.size()-1;
    int mid = idxR / 2;
    while(idxL <= idxR){
        if(resNum > nums[mid]){
            idxL = mid + 1;
        }else if(resNum < nums[mid]){
            idxR = mid - 1;
        }else{
            idx = mid;
            return true;
        }
        mid = (idxL+idxR)/2;
    }
    return false;
}

vector<vector<int> > threeSum(vector<int>& nums) {
    int n = nums.size();
    vector<vector<int> > result;
    unordered_set<vector<int> > resultSet;
    
    sort(nums.begin(),nums.end());
    if (n < 3 || nums[0] > 0 || nums[n-1] < 0)//全正或全负
        return result;
    if(nums[0] == 0 && nums[n-1] == 0){//全是0
        vector<int> tmp0 = {0, 0, 0};
        result.push_back(tmp0);
        return result;
    }
    
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++){
            if(j == i)
                continue;
            int resNum = 0 - nums[i] - nums[j];
            int idx = -1;
            if(biSearch(resNum,idx,nums) && idx != i && idx != j){
                vector<int> tmp;
                tmp.push_back(nums[i]);
                tmp.push_back(nums[j]);
                tmp.push_back(nums[idx]);
                sort(tmp.begin(), tmp.end());
                resultSet.insert(tmp);
            }
        }
    }
    for(auto s:resultSet){
        result.push_back(s);
    }
    return result;
}

313 / 313 个通过测试用例
时间复杂度O(N^2 * logn)，空间复杂度O(1)

还可以在最里层用一个unordered_set/map来查找。可以把时间复杂度降到O(n^2)。但是每次建立unordered_set都需要去掉nums[i] 和 nums[j] 的值，如果有重复，在查重的时候又要增加时间复杂度。

双指针。先排序O(nlong)。第一层循环O(n)，第二个数和第三个数是此消彼长的关系。所以左指针向右移动时，右指针也需要忘左缩进（因为随着第二个数的增加，第三个数必然会减小）。这样时间复杂度就从两层循环O(n^2)减少至只需要一层循环O(n)。

vector<vector<int> > threeSum(vector<int>& nums) {
    int n = nums.size();
    sort(nums.begin(), nums.end());
    vector<vector<int> > result;
    
    if (n < 3 || nums[0] > 0 || nums[n-1] < 0)//全正或全负
        return result;
    if(nums[0] == 0 && nums[n-1] == 0){//全是0
        vector<int> tmp0 = {0, 0, 0};
        result.push_back(tmp0);
        return result;
    }
    
    // 第一个数循环
    for (int first = 0; first < n; ++first) {
        // 去重
        if (first > 0 && nums[first] == nums[first - 1]) {
            continue;
        }
        // 第三个数对应的指针初始指向数组的最右端
        int third = n - 1;
        int target = -nums[first];
        // 第二层循环
        for (int second = first + 1; second < n; ++second) {
            if (second > first + 1 && nums[second] == nums[second - 1]) {// 去重
                continue;
            }
            // 需要保证第二个数指针在第三个数指针的左侧
            while (second < third && nums[second] + nums[third] > target) {
                --third;
            }
            // 如果指针重合，随着第二个数的增加，就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环
            if (second == third) {
                break;
            }
            if (nums[second] + nums[third] == target) {
                result.push_back({nums[first], nums[second], nums[third]});
            }
        }
    }
    return result;
}

6月13日 70. 爬楼梯（简单）

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

示例：

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

题解：
和6月9日的题一样，典型的dp问题。可以看我的算法总结里的dp专题。

一维dp问题。dp[i] = dp[i-1] + dp[i-2]

int climbStairs(int n) {
    vector<int> dp(n + 1);
    dp[0] = 1;
    dp[1] = 1;
    for (int i = 2; i <= n;i++){
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

时间复杂度O(n)
空间复杂度O(n)

空间优化：实际上，只用到了前两个dp[i-1]，dp[i-2]。所以可以只用到3个int，把空间优化为O(1)。

int climbStairs(int n) {
    vector<int> dp(3);
    dp[0] = 1;
    dp[1] = 1;
    for (int i = 2; i <= n;i++){
        dp[2] = dp[1] + dp[0];
        dp[0] = dp[1];
        dp[1] = dp[2];
    }
    return dp[1];
}

第28场双周赛 6.13

5420. 商品折扣后的最终价格（简单）

给你一个数组 prices ，其中 prices[i] 是商店里第 i 件商品的价格。
商店里正在进行促销活动，如果你要买第 i 件商品，那么你可以得到与 prices[j] 相等的折扣，其中 j 是满足 j > i 且 prices[j] <= prices[i] 的最小下标，如果没有满足条件的 j ，你将没有任何折扣。
请你返回一个数组，数组中第 i 个元素是折扣后你购买商品 i 最终需要支付的价格。

示例：

输入：prices = [8,4,6,2,3]
输出：[4,2,4,2,3]
解释：
商品 0 的价格为 price[0]=8 ，你将得到 prices[1]=4 的折扣，所以最终价格为 8 - 4 = 4 。
商品 1 的价格为 price[1]=4 ，你将得到 prices[3]=2 的折扣，所以最终价格为 4 - 2 = 2 。
商品 2 的价格为 price[2]=6 ，你将得到 prices[3]=2 的折扣，所以最终价格为 6 - 2 = 4 。
商品 3 和 4 都没有折扣。

题解：

vector<int> finalPrices(vector<int>& prices) {
    vector<int> res = prices;
    for (int i = 0; i < prices.size(); i++)
    {
        for (int j = i + 1; j < prices.size();j++){
            if(prices[j]<=prices[i]){
                res[i] = prices[i] - prices[j];
                break;
            }
        }
    }
    return res;
}

5423. 找两个和为目标值且不重叠的子数组（中等）

给你一个整数数组 arr 和一个整数值 target 。
请你在 arr 中找两个互不重叠的子数组且它们的和都等于 target 。可能会有多种方案，请你返回满足要求的两个子数组长度和的最小值。
请返回满足要求的最小长度和，如果无法找到这样的两个子数组，请返回 -1 。

示例 1：

1
2
3

输入：arr = [3,2,2,4,3], target = 3
输出：2
解释：只有两个子数组和为 3 （[3] 和 [3]）。它们的长度和为 2 。

示例 2：

1
2
3

输入：arr = [7,3,4,7], target = 7
输出：2
解释：尽管我们有 3 个互不重叠的子数组和为 7 （[7], [3,4] 和 [7]），但我们会选择第一个和第三个子数组，因为它们的长度和 2 是最小值。

示例 3：

1
2
3

输入：arr = [4,3,2,6,2,3,4], target = 6
输出：-1
解释：我们只有一个和为 6 的子数组。

题解：

最容易想到的办法就是遍历数组得到所有sum为target的子数组，再从子数组列表中找出不重合的最小的两个子数组。找子数组处理重合的时候要很仔细。（代码略）

双指针（滑动窗口）。左右指针从右到左移动，同时用一个数组len记录后面的最小子数组。其中，len[i]表示i后面（含i）的最小子数组长度。

int minSumOfLengths(vector<int>& arr, int target) {
    int sum = 0, r = arr.size() - 1, ans = 200000; 
    vector<int> len(arr.size() + 1, 200000);//后面子数组的最小长度
    for (int l = r; l >= 0; --l) { //l,r是滑动区间的左右坐标
        sum += arr[l];
        while (sum > target)
            sum -= arr[r--];
        if (sum == target) {
            int cur = r - l + 1; //子数组长度
            ans = min(ans, cur + len[r + 1]); //子数组长度 + r后面子数组的最小长度
            len[l] = min(len[l + 1], r - l + 1); //更新l后面子数组的最小长度
        }else
            len[l] = len[l + 1]; //更新子数组的最小长度
    }
    return ans == 200000 ? -1 : ans;
}

5421. 安排邮筒（困难）

给你一个房屋数组houses 和一个整数 k ，其中 houses[i] 是第 i 栋房子在一条街上的位置，现需要在这条街上安排 k 个邮筒。
请你返回每栋房子与离它最近的邮筒之间的距离的最小总和。
答案保证在 32 位有符号整数范围以内。

示例 1：

输入：houses = [1,4,8,10,20], k = 3
输出：5
解释：将邮筒分别安放在位置 3， 9 和 20 处。
每个房子到最近邮筒的距离和为 |3-1| + |4-3| + |9-8| + |10-9| + |20-20| = 5 。

示例 2：

输入：houses = [2,3,5,12,18], k = 2
输出：9
解释：将邮筒分别安放在位置 3 和 14 处。
每个房子到最近邮筒距离和为 |2-3| + |3-3| + |5-3| + |12-14| + |18-14| = 9 。

示例 3：

1 2	输入：houses = [7,4,6,1], k = 1 输出：8

示例 4：

1 2	输入：houses = [3,6,14,10], k = 4 输出：0

提示：

n == houses.length
1 <= n <= 100
1 <= houses[i] <= 10^4
1 <= k <= n
数组 houses 中的整数互不相同。

第193场周赛 6.14

5436. 一维数组的动态和（简单）

题目难度Easy
给你一个数组 nums 。数组「动态和」的计算公式为：runningSum[i] = sum(nums[0]…nums[i]) 。

请返回 nums 的动态和。

示例 1：

输入：nums = [1,2,3,4]
输出：[1,3,6,10]
解释：动态和计算过程为 [1, 1+2, 1+2+3, 1+2+3+4] 。
示例 2：

输入：nums = [1,1,1,1,1]
输出：[1,2,3,4,5]
解释：动态和计算过程为 [1, 1+1, 1+1+1, 1+1+1+1, 1+1+1+1+1] 。
示例 3：

输入：nums = [3,1,2,10,1]
输出：[3,4,6,16,17]

vector<int> runningSum(vector<int>& nums) {
    vector<int> res(nums.size(),0);
    res[0] = nums[0];
    for (int i = 1; i < nums.size(); i++)
        res[i] = res[i - 1] + nums[i];
    return res;
}

5437. 不同整数的最少数目（Medium）

给你一个整数数组 arr 和一个整数 k 。现需要从数组中恰好移除 k 个元素，请找出移除后数组中不同整数的最少数目。

示例 1：

1
2
3

输入：arr = [5,5,4], k = 1
输出：1
解释：移除 1 个 4 ，数组中只剩下 5 一种整数。

示例 2：

1
2
3

输入：arr = [4,3,1,1,3,3,2], k = 3
输出：2
解释：先移除 4、2 ，然后再移除两个 1 中的任意 1 个或者三个 3 中的任意 1 个，最后剩下 1 和 3 两种整数。

题解：

bool cmpByValue(const vector<int> &a, const vector<int> &b){//注意！这个函数要在类外面定义
    return a[1] > b[1];//value降序
}

int findLeastNumOfUniqueInts(vector<int>& arr, int k) {
    map<int, int> numMap;
    for(int n:arr){
        if(numMap.count(n) == 0)
            numMap.insert(pair<int, int>(n, 1));
        else
            numMap[n]++;
    }

    vector<vector<int> > numMapV;
    for (auto m : numMap)
        numMapV.push_back({m.first, m.second});

    sort(numMapV.begin(), numMapV.end(), cmpByValue);

    while (k > 0 && numMap.size() > 0)
    {
        vector<int> minNum = numMapV.back();
        if (minNum[1] > k)
            return numMap.size();
        else if(minNum[1] == k)
            return numMap.size() - 1;
        else{
            k = k - minNum[1];
            numMap.erase(minNum[0]);
            numMapV.pop_back();
        }
    }
    return numMap.size();
}

5438. 制作 m 束花所需的最少天数（Medium）

给你一个整数数组 bloomDay，以及两个整数 m 和 k 。
现需要制作 m 束花。制作花束时，需要使用花园中相邻的 k 朵花。
花园中有 n 朵花，第 i 朵花会在 bloomDay[i] 时盛开，恰好可以用于一束花中。
请你返回从花园中摘 m 束花需要等待的最少的天数。如果不能摘到 m 束花则返回 -1 。

示例 1：

输入：bloomDay = [1,10,3,10,2], m = 3, k = 1
输出：3
解释：让我们一起观察这三天的花开过程，x 表示花开，而 _ 表示花还未开。
现在需要制作 3 束花，每束只需要 1 朵。
1 天后：[x, _, _, _, _]   // 只能制作 1 束花
2 天后：[x, _, _, _, x]   // 只能制作 2 束花
3 天后：[x, _, x, _, x]   // 可以制作 3 束花，答案为 3

示例 2：

1
2
3

输入：bloomDay = [1,10,3,10,2], m = 3, k = 2
输出：-1
解释：要制作 3 束花，每束需要 2 朵花，也就是一共需要 6 朵花。而花园中只有 5 朵花，无法满足制作要求，返回 -1 。

示例 3：

输入：bloomDay = [7,7,7,7,12,7,7], m = 2, k = 3
输出：12
解释：要制作 2 束花，每束需要 3 朵。
花园在 7 天后和 12 天后的情况如下：
7 天后：[x, x, x, x, _, x, x]
可以用前 3 朵盛开的花制作第一束花。但不能使用后 3 朵盛开的花，因为它们不相邻。
12 天后：[x, x, x, x, x, x, x]
显然，我们可以用不同的方式制作两束花。

示例 4：

1
2
3

输入：bloomDay = [1000000000,1000000000], m = 1, k = 1
输出：1000000000
解释：需要等 1000000000 天才能采到花来制作花束

示例 5：

1 2	输入：bloomDay = [1,10,2,9,3,8,4,7,5,6], m = 4, k = 2 输出：9

题解：
（待补充）

5188. 树节点的第 K 个祖先（困难）

给你一棵树，树上有 n 个节点，按从 0 到 n-1 编号。树以父节点数组的形式给出，其中 parent[i] 是节点 i 的父节点。树的根节点是编号为 0 的节点。
请你设计并实现 getKthAncestor(int node, int k) 函数，函数返回节点 node 的第 k 个祖先节点。如果不存在这样的祖先节点，返回 -1 。
树节点的第 k 个祖先节点是从该节点到根节点路径上的第 k 个节点。

示例：

输入：
["TreeAncestor","getKthAncestor","getKthAncestor","getKthAncestor"]
[[7,[-1,0,0,1,1,2,2]],[3,1],[5,2],[6,3]]

输出：
[null,1,0,-1]

解释：
TreeAncestor treeAncestor = new TreeAncestor(7, [-1, 0, 0, 1, 1, 2, 2]);

treeAncestor.getKthAncestor(3, 1);  // 返回 1 ，它是 3 的父节点
treeAncestor.getKthAncestor(5, 2);  // 返回 0 ，它是 5 的祖父节点
treeAncestor.getKthAncestor(6, 3);  // 返回 -1 因为不存在满足要求的祖先节点

题解：
（待补充）

6月14日 1300. 转变数组后最接近目标值的数组和（中等）

给你一个整数数组 arr 和一个目标值 target ，请你返回一个整数 value ，使得将数组中所有大于 value 的值变成 value 后，数组的和最接近 target （最接近表示两者之差的绝对值最小）。
如果有多种使得和最接近 target 的方案，请你返回这些整数中的最小值。
请注意，答案不一定是 arr 中的数字。

示例 1：

1
2
3

输入：arr = [4,9,3], target = 10
输出：3
解释：当选择 value 为 3 时，数组会变成 [3, 3, 3]，和为 9 ，这是最接近 target 的方案。

示例 2：

1 2	输入：arr = [2,3,5], target = 10 输出：5

示例 3：

1 2	输入：arr = [60864,25176,27249,21296,20204], target = 56803 输出：11361

提示：

1 2	1 <= arr.length <= 10^4 1 <= arr[i], target <= 10^5

题解：

其实就是从一个范围中找到一个数。这个范围的下界是0，因为arr[i]>=1，所以sum肯定是>=1的。上界是arr中的最大值maxNum，因为当value > maxNum时，arr中的元素不会变，得到的sum是一样的。所以就是从[0, maxNum]中找到value。从排序的数组中查找，用二分查找来减少时间复杂度。初始条件 l=0, r=maxNum, mid=(l+r)/2，判定条件是：当sum(mid)-target > 0（value=mid）时，值偏大，r = mid - 1；当sum(mid)-target < 0时，值偏小，l = mid + 1；当sum(mid)-target == 0时mid为所寻找的值。循环条件为l<=r && sumArr != target。循环中需要用一个minAbs来保存最接近的值。

int getSum(vector<int> arr, int value){
    int sumArr = 0;
    for (int i = 0; i < arr.size();i++){
        if(arr[i]<=value)
            sumArr += arr[i];
        else
            sumArr += value;
    }
    return sumArr;
}

int findBestValue(vector<int>& arr, int target) {
    int maxNum = 0, sumArr = 0;
    for (int a : arr){
        sumArr += a;
        maxNum = max(maxNum, a);
    }
    if(sumArr<=target)
        return maxNum;

    int l = 0, r = maxNum, mid;
    int minAbs = sumArr - target > 0 ? sumArr - target : target - sumArr;
    int value = maxNum;
    int diff, abs;
    while (l <= r && sumArr != target){
        mid = (l + r) / 2;
        sumArr = getSum(arr, mid);//看value==mid后的和
        diff = sumArr - target;
        if(diff==0){//找到其中一个
            value = min(value, mid);
        }else if(diff>0){
            r = mid - 1;
        }
        else{//diff<0
            l = mid + 1;
        }
        abs = diff > 0 ? diff : -diff;
        if(abs<minAbs || (abs==minAbs && mid<value)){
            value = mid;
            minAbs = abs;
        }
    }
    return value;
}

时间复杂度：O(logc*n)，c为最大值maxNum，n为数组长度。
空间复杂度：O(1)

先排序，再从头遍历，当arr[i] > (target-preSum[i]) / (n-i)时，就是不能再增大了，返回剩余的平均值。preSum[i]是 arr[i] 之前的所有数的和。注意小数部分的处理。

int findBestValue(vector<int>& arr, int target){
    int maxNum = 0, sumArr = 0;
    for (int a : arr){
        sumArr += a;
        maxNum = max(maxNum, a);
    }
    if(sumArr<=target)
        return maxNum;

    sort(arr.begin(), arr.end());
    
    int preSum = 0, n = arr.size();
    for (int i = 0; i < n; i++) {
        int x = (target - preSum) / (n - i);
        if (x < arr[i]) {
            double t = ((double)(target - preSum)) / (n - i);
            if (t - x > 0.5) {
                return x + 1;
            } else {
                return x;
            }
        }
        preSum += arr[i];
    }
    return arr[n - 1];
}

时间复杂度：排序O(nlogn)，遍历O(n)，所以是O(nlogn)。
空间复杂度：O(1)

6月15日 14. 最长公共前缀（简单）

编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 “”。

示例 1:

1 2	输入: ["flower","flow","flight"] 输出: "fl"

示例 2:

1
2
3

输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。

说明:

1	所有输入只包含小写字母 a-z 。

题解：
一位一位比较。

string longestCommonPrefix(vector<string>& strs) {
    string res = "";
    bool stop = false;
    for(int i = 0; !stop; i++){
        char cur = strs[0][i];
        for(string s:strs){
            if(s.size()==i+1)//有一个str已经到最后一位了
                stop = true;
            if(s[i]==cur){
                continue;
            }
            else
                return res;
        }
        res += cur;
    }
    return res;
}

时间复杂度：O(m*n)，m 是 strs 中最短字符串的长度，n是字符串列表的长度。
空间复杂度：O(1)

6月16日 297. 二叉树的序列化与反序列化（困难）

序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。
请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。

示例:

提示: 这与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。

说明: 不要使用类的成员 / 全局 / 静态变量来存储状态，你的序列化和反序列化算法应该是无状态的。

树的结构：

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

题解：

按照示例层序遍历，即BFS。可以使用队列来序列化，也可以使用递归。
先序遍历，即DFS。使用栈来系列化，也可以使用递归。

6月17日 1014. 最佳观光组合（中等）

给定正整数数组 A，A[i] 表示第 i 个观光景点的评分，并且两个景点 i 和 j 之间的距离为 j - i。
一对景点（i < j）组成的观光组合的得分为（A[i] + A[j] + i - j）：景点的评分之和减去它们两者之间的距离。
返回一对观光景点能取得的最高分。

示例：

1
2
3

输入：[8,1,5,2,6]
输出：11
解释：i = 0, j = 2, A[i] + A[j] + i - j = 8 + 5 + 0 - 2 = 11

题解：

暴力（超时）

int maxScoreSightseeingPair(vector<int>& A) {
    int maxScore = 0;
    for (int i = 0; i < A.size();i++){
        for (int j = i + 1; j < A.size();j++)
            maxScore = max(maxScore, A[i] + A[j] + i - j);
    }
    return maxScore;
}

时间复杂度：O(n^2)
空间复杂度：O(1)

把A[i]+A[j]+i-j分解为两部分：A[i]+i 和 A[j]-j。dpPre[j] = max(dpPre[j-1],A[j-1]+j-1)，表示索引j之前A[i]+i的最大值；
dp[i] = max(dp[i-1],dpPre[i-1]+A[i]-i)。但是这需要O(n)的空间复杂度保存之前的最大值。因为dp只用到了之前的一个值，所以可以优化为只用两个 int 来保存前面的状态，遍历时同时更新dpPre和dp。
用一个preMax保存j前面A[i]+i的最大值，maxScore保存答案。同时更新两个量，一遍遍历即可。

int maxScoreSightseeingPair(vector<int>& A) {
    int maxScore = 0, preMax = A[0] + 0;
    for (int j = 1; j < A.size();j++){
        maxScore = max(maxScore, preMax + A[j] - j);//更新dp[j]
        preMax = max(preMax, A[j] + j);//更新下一次j的dpPre[j-1]
    }
    return maxScore;
}

时间复杂度：O(n)
空间复杂度：O(1)

6月18日 1028. 从先序遍历还原二叉树（困难）

我们从二叉树的根节点 root 开始进行深度优先搜索。
在遍历中的每个节点处，我们输出 D 条短划线（其中 D 是该节点的深度），然后输出该节点的值。（如果节点的深度为 D，则其直接子节点的深度为 D + 1。根节点的深度为 0）。
如果节点只有一个子节点，那么保证该子节点为左子节点。
给出遍历输出 S，还原树并返回其根节点 root。

示例1:

1 2	输入："1-2--3--4-5--6--7" 输出：[1,2,5,3,4,6,7]

示例2:

1 2	输入："1-2--3---4-5--6---7" 输出：[1,2,5,3,null,6,null,4,null,7]

示例 3：

1 2	输入："1-401--349---90--88" 输出：[1,401,null,349,88,90]

题解：
当前节点为T，上一个节点为S，只有两种情况：

T 是 S 的左子节点；
T 是根节点到 S 这一条路径上（不包括 S，因为题目中规定了如果节点只有一个子节点，那么保证该子节点为左子节点）某一个节点的右子节点。

所以，我们用一个栈保存根节点到当前节点的上一个节点的路径：

当前节点的深度刚好比栈的高度大1：当前节点正好是栈顶节点的左子节点；ps. 深度是从0开始，所以当深度的值和栈高度相等时，就是深度刚好比栈的高度大1

当前节点的深度小于等于栈的高度：

当前节点的深度刚和栈的高度相等：当前节点是栈顶节点右兄弟节点即栈顶节点父节点的右子节点；
当前节点的深度小于栈的高度：当前节点是根节点到栈顶节点路径上某一个节点的右子节点。一直弹出栈顶节点直到满足情况1。

*ps. 当前节点的深度刚和栈的高度相等即 level=path.size()-1，也是需要弹出栈顶节点一次*

TreeNode* recoverFromPreorder(string S) {
    stack<TreeNode *> path;
    int pos = 0;
    while(pos<S.size()){
        int level = 0;
        while(S[pos]=='-'){
            level++;
            pos++;
        }
        
        int value = 0;
        while (pos < S.size() && isdigit(S[pos])){//取当前节点的值
            value = value * 10 + (S[pos] - '0');
            pos++;
        }

        TreeNode *node = new TreeNode(value);
        if(level==path.size()){//第1种情况
            if(!path.empty())
                path.top()->left = node;
        }else{//第2种情况
            while(level!=path.size())
                path.pop();
            path.top()->right = node;
        }
        path.push(node);
    }
    while(path.size()>1)
        path.pop();
    return path.top();
}

时间复杂度：O(n)。n为S的长度
空间复杂度：O(h)。h为树的高度

6月19日 125. 验证回文串（简单）

给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。

说明：本题中，我们将空字符串定义为有效的回文串。

示例 1:

1 2	输入: "A man, a plan, a canal: Panama" 输出: true

示例 2:

1 2	输入: "race a car" 输出: false

题解：
用一前一后双指针依次往中间遍历，直到指针碰见。可以在开始时用transform()先把字符串全部转换为小写字母，也可以在比较时使用toupper()/tolower()转单个字母。

bool isPalindrome(string s) {
    // transform(s.begin(), s.end(), s.begin(), ::tolower);
    if (s.size() == 0)
        return true;
    int idxL = 0, idxR = s.size() - 1;
    while(idxL<idxR){
        while(!isalnum(s[idxL]) && idxL<idxR)
            idxL++; 
        while(!isalnum(s[idxR]) && idxL<idxR)
            idxR--;
        if(tolower(s[idxL]) != tolower(s[idxR]))
            return false;
        else{
            idxL++;
            idxR--;
        }
    }
    return true;
}

时间复杂度：O(n)。n为字符串s的长度
空间复杂度：O(1)

6月20日 10. 正则表达式匹配（困难）

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 ‘.’ 和 ‘*’ 的正则表达式匹配。

1
2
3

'.' 匹配任意单个字符
'*' 匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。

说明:

1 2	s 可能为空，且只包含从 a-z 的小写字母。 p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。

示例 1:

输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。

示例 2:

输入:
s = "aa"
p = "a*"
输出: true
解释: 因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。

示例 3:

输入:
s = "ab"
p = ".*"
输出: true
解释: ".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。

示例 4:

输入:
s = "aab"
p = "c*a*b"
输出: true
解释: 因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。

示例 5:

输入:
s = "mississippi"
p = "mis*is*p*."
输出: false

题解：

递归（超时）。需要用到有限状态机的思想。

当p索引的下一个字符是’*’时：
- 当前字符匹配：当作没有’*‘ || 转移状态，看s的下一位 ||’*‘匹配0个
- 当前字符不匹配：’*‘匹配0个，p索引向后移动两位

当p索引的下一个字符不是’*‘时。如果当前字符匹配，则都向后移动一位。

bool matchCore(string s, string p, int idxS, int idxP){
    if(idxS==s.size() && idxP==p.size())
        return true;
    if(idxS<s.size() && idxP==p.size())
        return false;
    
    if(p[idxP+1]=='*'){//p索引的下一个字符是'*'
        if(p[idxP]==s[idxS] || (p[idxP]=='.' && idxS<s.size())) //当前字符匹配
            return matchCore(s, p, idxS + 1, idxP + 2)//当作没有*
                || matchCore(s, p, idxS + 1, idxP) //
                || matchCore(s, p, idxS, idxP + 2);//*匹配0个
        else //当前字符不匹配
            return matchCore(s, p, idxS, idxP + 2);
    }

    if(s[idxS]==p[idxP] || (p[idxP]=='.' && idxS<s.size())) //p索引的下一个字符不是'*'
        return matchCore(s, p, idxS + 1, idxP + 1);

    return false;
}

bool isMatch(string s, string p)
{
    return matchCore(s, p, 0, 0);
}

dp。用 dp[i][j] 表示 s 的前 i 个字符与 p 中的前 j 个字符是否能够匹配。
- p[j]不是’*‘
  - dp[i][j] = dp[i-1][j-1] (s[i] == p[j] 含p[j]==’.’的情况)
  - false (s[i] != p[j])
- p[j]是’*‘
  - dp[i][j] = dp[i-1][j](匹配s的该位字符) || dp[i][j-2](字母+星号不匹配任何字符) (s[i] == p[j-1] s[i] == p[j] 含p[j-1]==’.’的情况)
  - dp[i][j] = dp[i][j-2] (s[i]!=p[j-1])

ps. 需要特别注意字符串的索引是从0开始的，和dp的索引相差1

bool isMatch(string s, string p)
{
    int m = s.size(), n = p.size();
    vector<vector<bool> > dp(m+1,vector<bool>(n+1));

    //初始化很重要！！！
    dp[0][0] = true;
    for (int i = 2; i <= n; i++) {
        if (p[i-1] == '*' && dp[0][i - 2]){
            // p[0]不可能是'\*'，因为'\*'必须依附前面的字符。
            // p = "a*c*b*a"这种情况，dp[0][2/4/6]都为true
            dp[0][i] = true;
        }
    }
    
    for (int i = 1; i <= m; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if(p[j-1]!='*'){
                if(s[i-1]==p[j-1] || p[j-1]=='.')
                    dp[i][j] = dp[i - 1][j - 1];
                else
                    dp[i][j] = false;
            }else{
                if(s[i-1]==p[j-2] || p[j-2]=='.'){
                    dp[i][j] = (dp[i - 1][j] || dp[i][j - 2]);
                }
                else
                {
                    dp[i][j] = dp[i][j - 2];
                }
            }
        }
    }
    return dp[m][n];
}

6月21日 124. 二叉树中的最大路径和（困难）

给定一个非空二叉树，返回其最大路径和。

本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。

示例 1:

输入: [1,2,3]

       1
      / \
     2   3

输出: 6

示例 2:

输入: [-10,9,20,null,null,15,7]
       -10
       / \
      9  20
        /  \
       15   7

输出: 42

题解：
递归。
一个节点处于最大路径上时，可能有两种情况：

他是最上层节点，不再父节点走。这时候需要求lANDr：当前节点和左右路径的最大值
他不是最上层，有父节点。这时候需要求lORr：当前节点往左子树还是子树和更大

递归函数返回的是左/右子树的最大路径和。同时更新一个保存全局最大路径和的引用maxSum。

int getMaxPathSum(TreeNode* root, int &maxSum){
    if(root==nullptr)
        return 0;
    int lPath = getMaxPathSum(root->left, maxSum);
	int rPath = getMaxPathSum(root->right, maxSum);
	int lANDr = root->val + max(0, lPath) + max(0, rPath);
	int lORr = root->val + max(0, max(lPath, rPath));
	maxSum = max(maxSum, max(lANDr, lORr));
	return lORr;
}

int maxPathSum(TreeNode* root) {
    int maxSum = INT_MIN;
    getMaxPathSum(root, maxSum);
    return maxSum;
}

时间复杂度：O(n)，其中 n 是二叉树中的节点个数。对每个节点访问不超过 2 次。
空间复杂度：O(n)，其中 n 是二叉树中的节点个数。空间复杂度主要取决于递归调用层数，最大层数等于二叉树的高度，最坏情况下，二叉树的高度等于二叉树中的节点个数。

第194场周赛 6.21

5440. 数组异或操作

题目难度Easy
给你两个整数，n 和 start 。

数组 nums 定义为：nums[i] = start + 2*i（下标从 0 开始）且 n == nums.length 。

请返回 nums 中所有元素按位异或（XOR）后得到的结果。

示例 1：

输入：n = 5, start = 0
输出：8
解释：数组 nums 为 [0, 2, 4, 6, 8]，其中 (0 ^ 2 ^ 4 ^ 6 ^ 8) = 8 。
“^” 为按位异或 XOR 运算符。

int xorOperation(int n, int start) {
    vector<int> nums(n);
    for (int i = 0; i < n; i++)
        nums[i] = start + 2 * i;

    int res = nums[0];
    for (int i = 1; i < n;i++)
        res ^= nums[i];
    return res;
}

5441. 保证文件名唯一（中等）

给你一个长度为 n 的字符串数组 names 。你将会在文件系统中创建 n 个文件夹：在第 i 分钟，新建名为 names[i] 的文件夹。

由于两个文件不能共享相同的文件名，因此如果新建文件夹使用的文件名已经被占用，系统会以 (k) 的形式为新文件夹的文件名添加后缀，其中 k 是能保证文件名唯一的最小正整数。

返回长度为 n 的字符串数组，其中 ans[i] 是创建第 i 个文件夹时系统分配给该文件夹的实际名称。

示例 1：

输入：names = ["pes","fifa","gta","pes(2019)"]
输出：["pes","fifa","gta","pes(2019)"]
解释：文件系统将会这样创建文件名：
"pes" --> 之前未分配，仍为 "pes"
"fifa" --> 之前未分配，仍为 "fifa"
"gta" --> 之前未分配，仍为 "gta"
"pes(2019)" --> 之前未分配，仍为 "pes(2019)"

示例2:

1
2
3

输入：names = ["onepiece","onepiece(1)","onepiece(2)","onepiece(3)","onepiece"]
输出：["onepiece","onepiece(1)","onepiece(2)","onepiece(3)","onepiece(4)"]
解释：当创建最后一个文件夹时，最小的正有效 k 为 4 ，文件名变为 "onepiece(4)"。

示例 3：

1
2
3

输入：names = ["kaido","kaido(1)","kaido","kaido(1)"]
输出：["kaido","kaido(1)","kaido(2)","kaido(1)(1)"]
解释：注意，如果含后缀文件名被占用，那么系统也会按规则在名称后添加新的后缀 (k) 。

题解：

vector<string> getFolderNames(vector<string>& names) {
    unordered_map<string, int> fileMap;
    vector<string> res;
    for (int i = 0; i < names.size(); i++)
    {
        int tmp = fileMap[names[i]]; //如果该key不存在，会自动创建一个{key,0}的插入map，并返回0
        if (tmp == 0)
        {//文件名不存在
            res.push_back(names[i]);
            fileMap[names[i]] = 1;
        }
        else
        {//文件名已存在
            while (fileMap.count(names[i]+"("+to_string(tmp)+")"))
                tmp++;
            res.push_back(names[i]+"("+to_string(tmp)+")");
            fileMap[names[i]] = tmp;
            fileMap[names[i]+"("+to_string(tmp)+")"] = 1;
        }
    }
    return res;
}

5442. 避免洪水泛滥（中等）

你的国家有无数个湖泊，所有湖泊一开始都是空的。当第 n 个湖泊下雨的时候，如果第 n 个湖泊是空的，那么它就会装满水，否则这个湖泊会发生洪水。你的目标是避免任意一个湖泊发生洪水。

给你一个整数数组 rains ，其中：
rains[i] > 0 表示第 i 天时，第rains[i]个湖泊会下雨。
rains[i] == 0 表示第 i 天没有湖泊会下雨，你可以选择一个湖泊并抽干这个湖泊的水。

请返回一个数组 ans ，满足：
ans.length == rains.length
如果 rains[i] > 0 ，那么ans[i] == -1 。
如果 rains[i] == 0 ，ans[i] 是你第 i 天选择抽干的湖泊。
如果有多种可行解，请返回它们中的任意一个。如果没办法阻止洪水，请返回一个空的数组。

请注意，如果你选择抽干一个装满水的湖泊，它会变成一个空的湖泊。但如果你选择抽干一个空的湖泊，那么将无事发生（详情请看示例 4）。

示例 1：

输入：rains = [1,2,3,4]
输出：[-1,-1,-1,-1]
解释：第一天后，装满水的湖泊包括 [1]
第二天后，装满水的湖泊包括 [1,2]
第三天后，装满水的湖泊包括 [1,2,3]
第四天后，装满水的湖泊包括 [1,2,3,4]
没有哪一天你可以抽干任何湖泊的水，也没有湖泊会发生洪水。

示例 2：

输入：rains = [1,2,0,0,2,1]
输出：[-1,-1,2,1,-1,-1]
解释：第一天后，装满水的湖泊包括 [1]
第二天后，装满水的湖泊包括 [1,2]
第三天后，我们抽干湖泊 2 。所以剩下装满水的湖泊包括 [1]
第四天后，我们抽干湖泊 1 。所以暂时没有装满水的湖泊了。
第五天后，装满水的湖泊包括 [2]。
第六天后，装满水的湖泊包括 [1,2]。
可以看出，这个方案下不会有洪水发生。同时， [-1,-1,1,2,-1,-1] 也是另一个可行的没有洪水的方案。

示例 3：

输入：rains = [1,2,0,1,2]
输出：[]
解释：第二天后，装满水的湖泊包括 [1,2]。我们可以在第三天抽干一个湖泊的水。
但第三天后，湖泊 1 和 2 都会再次下雨，所以不管我们第三天抽干哪个湖泊的水，另一个湖泊都会发生洪水。

示例 4：

1
2
3

输入：rains = [69,0,0,0,69]
输出：[-1,69,1,1,-1]
解释：任何形如 [-1,69,x,y,-1], [-1,x,69,y,-1] 或者 [-1,x,y,69,-1] 都是可行的解，其中 1 <= x,y <= 10^9

示例 5：

1
2
3

输入：rains = [10,20,20]
输出：[]
解释：由于湖泊 20 会连续下 2 天的雨，所以没有没有办法阻止洪水。

题解：
lastRainDay保存了湖号(key)到目前的最后一天下雨的日期。
set s 保存了前面未下雨的日期。

碰到rains[i]==0后（没下雨），把未下雨的天数先存到s里，继续往后。
如果下雨
- 湖lakeNum未满，就更新lastRainDay[lakeNum]=i和res[i]=-1
- 湖lakeNum满了，就从未下雨的日期set s 中取出湖lakeNum 最后下雨日期lastRainDay[lakeNum] 之后最近的未下雨的日期，在lastRainDay[lakeNum]当天把lakeNum抽干。

简单来说，就是在碰到水满之后，把最前面没下雨的一天用来抽该湖上次下的雨。（当然，抽水的日期要在下雨日期之后）

vector<int> avoidFlood(vector<int>& rains) {
    set<int> s;
    vector<int> res(rains.size(), 1);
    unordered_map<int, int> lastRainDay;//key是第i天下雨的湖号码，val是i
    for (int i = 0; i < rains.size(); i++) {
        int lakeNum = rains[i];//第i天下雨的湖号
        //第i天没下雨
        if (lakeNum == 0) {
            s.insert(i);
            continue;
        }
        
        //第i天下雨了
        res[i] = -1;
        if (lastRainDay.find(lakeNum) == lastRainDay.end()) {//湖里没水
            lastRainDay[lakeNum] = i;
            continue;
        }
        //湖里有水
        auto lastDay = lastRainDay[lakeNum];
        auto it = s.upper_bound(lastDay);
        if (it == s.end()) {
            return vector<int>();
        }
        
        res[*it] = lakeNum;
        lastRainDay[lakeNum] = i;
        s.erase(it);
    }
    return res;
}

6月22日面试题 16.18. 模式匹配（中等）

你有两个字符串，即pattern和value。 pattern字符串由字母”a”和”b”组成，用于描述字符串中的模式。例如，字符串”catcatgocatgo”匹配模式”aabab”（其中”cat”是”a”，”go”是”b”），该字符串也匹配像”a”、”ab”和”b”这样的模式。但需注意”a”和”b”不能同时表示相同的字符串。编写一个方法判断value字符串是否匹配pattern字符串。

示例 1：

1 2	输入： pattern = "abba", value = "dogcatcatdog" 输出： true

示例 2：

1 2	输入： pattern = "abba", value = "dogcatcatfish" 输出： false

示例 3：

1 2	输入： pattern = "aaaa", value = "dogcatcatdog" 输出： false

示例 4：

1
2
3

输入： pattern = "abba", value = "dogdogdogdog"
输出： true
解释： "a"="dogdog",b=""，反之也符合规则

题解：
枚举模式a和b的长度lA 和 lB，在看该长度下的substr是否满足条件。

bool patternMatching(string pattern, string value) {
    if(pattern=="" && value!="")
        return false;
    if (pattern.size() == 1 || (pattern=="" && value==""))
        return true;

    int cntA = 0, cntB = 0;
    for(char c:pattern){//统计pattern里种类的数量
        if(c=='a')
            cntA++;
        if(c=='b')
            cntB++;
    }

    if(cntA==0 || cntB==0){//只有1个模式
        if(value.size()%pattern.size()!=0)
            return false;
        int n = pattern.size();
        int nSub = value.size() / pattern.size();
        for (int i = 1; i < n; i++)
        {
            int idx = i * nSub;
            for (int j = 0; j < nSub;j++){
                if(value[j]!=value[idx+j])
                    return false;
            }
        }
        return true;
    }
    else
    { //2个模式
        if(value.size()==0)
            return false;
        if(cntA==1 || cntB==1)
            return true;
        //枚举每个模式的字符串长度
        for (int lA = 0; lA <= value.size() / cntA; lA++)
        {
            for (int lB = 0; lB <= value.size() / cntB;lB++){
                if(lA*cntA + lB*cntB != value.size())
                    continue;
                
                map<char, string> pMap;
                int idxA = 0, idxB = 0;
                int a = 0, b = 0;
                while (pattern[a++] != 'a')
                {
                    idxA += lB;
                }
                while(pattern[b++]!='b')
                    idxB += lA;
                
                pMap['a'] = value.substr(idxA, lA);
                pMap['b'] = value.substr(idxB, lB);
                
                //按模式的长度lA和lB验证是否匹配
                int pos = 0;
                for (int i = 0; i < pattern.size(); i++)
                {
                    char cur = pattern[i];
                    int l = cur == 'a' ? lA : lB;
                    if (pMap[cur] == value.substr(pos,l)){
                        pos += l;
                        continue;
                    }
                }
                if(pos==value.size())
                    return true;
            }
        }
        return false;
    }
}

6月23日 67. 二进制求和（简单）

给你两个二进制字符串，返回它们的和（用二进制表示）。
输入为非空字符串且只包含数字 1 和 0。

示例 1:

1 2	输入: a = "11", b = "1" 输出: "100"

示例 2:

1 2	输入: a = "1010", b = "1011" 输出: "10101"

题解：

数位法。和做大数乘法一样，处理每一位和进位。

string addBinary(string a, string b) {
    int carry = 0;
    int i = a.size() - 1, j = b.size() - 1;
    string endDigital = "";
    while (i >= 0 && j >= 0)
    {
        string curDigit = "";
        if(carry == 0){
            if(a[i]=='1' && b[j]=='1'){
                curDigit = "0";
                carry = 1;
            }else if((a[i]=='1' && b[j]=='0') || (a[i]=='0' && b[j]=='1')){
                curDigit = '1';
            }else{
                curDigit = '0';
            }
        }else{
            if(a[i]=='1' && b[j]=='1'){
                curDigit = "1";
            }else if((a[i]=='1' && b[j]=='0') || (a[i]=='0' && b[j]=='1')){
                curDigit = '0';
            }else{
                curDigit = '1';
                carry = 0;
            }
        }
        endDigital = curDigit + endDigital;
        i--;
        j--;
    }
    
    while(i>=0){
        if(carry==1){
            if(a[i]=='0'){
                endDigital = '1' + endDigital;
                carry = 0;
            }else{
                endDigital = '0' + endDigital;
            }
        }else{
            endDigital = a[i] + endDigital;
        }
        i--;
    }
    while(j>=0){
        if(carry==1){
            if(b[j]=='0'){
                endDigital = '1' + endDigital;
                carry = 0;
            }else{
                endDigital = '0' + endDigital;
            }
        }else{
            endDigital = b[j] + endDigital;
        }
        j--;
    }
    if(carry == 1){
        endDigital = "1" + endDigital;
    }
    return endDigital;
}

其实可以在短的前面添0补齐，就会方便一些。而且也可以通过 %2, /2 来得到更简洁的代码（前提是允许使用加减乘除）。

string addBinary(string a, string b) {  
    string res;
    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());

    int n = max(a.size(), b.size()), carry = 0;
    for (int i = 0; i < n; i++) {
        carry += i < a.size() ? (a[i] == '1') : 0;
        carry += i < b.size() ? (b[i] == '1') : 0;
        res.push_back((carry % 2) ? '1' : '0');
        carry /= 2;
    }

    if (carry) {
        res.push_back('1');
    }
    reverse(res.begin(), res.end());

    return res;
}

时间复杂度O(l)。l为最长的位数。
空间复杂度O(1)。

先转为10进制运算后再转回来。但是如果有很多位，就会导致溢出。
（代码略）

6月24日 16. 最接近的三数之和（中等）

给定一个包括 n 个整数的数组 nums 和一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。

示例：

1
2
3

输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。

题解：
排序+双指针。类似的题：15. 三数之和

暴力法的话时间复杂度是O(n^3)。我们需要想办法来降低时间复杂度：先枚举第一个数nums[i]，再剩下nums中找和最接近target-nums[i]。经过排序之后，可以用两数和与target-nums[i]的大小关系来决定两数和的变化趋势。

这样寻找后两个数是，只需遍历一遍，相当于把O(n^2)的时间降到了O(n)。

int threeSumClosest(vector<int>& nums, int target) {
    if(nums.size()==3)
        return nums[0] + nums[1] + nums[2];

    sort(nums.begin(), nums.end());
    int n = nums.size();
    int diff = INT_MAX;
    for (int i = 0; i < n-2;i++){
        if (i > 0 && nums[i] == nums[i - 1]) //防止重复元素
            continue;
        int find = target - nums[i];
        int idxL = i + 1, idxR = n - 1;
        while (idxL < idxR)
        {
            int sumLR = nums[idxL] + nums[idxR];
            if(sumLR == find) //如果相等，直接返回target
                return target;
            diff = abs(diff) < abs(sumLR - find) ? diff : (sumLR - find);//更新最小差值
            if (sumLR > find) idxR--;
            else idxL++;
        }
    }
    return target + diff;
}

时间复杂度：O(n^2)。排序需要O(nlogn)，算法主体O(n^2)。
空间复杂度：如果nums可以修改，则只需要排序算法的空间复杂度。如果nums不能修改，则需要O(n)来存储nums。

6月25日 [139. 单词拆分（中等）(https://leetcode-cn.com/problems/word-break/)

给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。

说明：

拆分时可以重复使用字典中的单词。
你可以假设字典中没有重复的单词。

示例 1：

1
2
3

输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。

示例 2：

输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。
     注意你可以重复使用字典中的单词。

示例 3：

1 2	输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"] 输出: false

题解：

存一个首字母map，用递归的方法查找。超时。

bool wordBreakCore(string s, vector<string>& wordDict, int idx, unordered_map<char, vector<string> > &alphaMap){
    if(idx==s.size())
        return true;

    if(alphaMap.find(s[idx])==alphaMap.end())
        return false;

    bool find = false;
    int initIdx = idx;
    for (string str : alphaMap[s[idx]])
    {
        idx = initIdx;
        if (idx + str.size() > s.size())
            continue;
        int nxtIdx = idx + str.size();
        for (int i = 0; i < str.size(); i++)
        {
            if(str[i]!=s[idx])
                break;
            else
                idx++;
        }
        if(idx==nxtIdx)
            find = wordBreakCore(s, wordDict, idx, alphaMap);
        if(find)
            return true;
    }

    return find;
}

bool wordBreak(string s, vector<string>& wordDict){
    unordered_map<char, vector<string> > alphaMap;
    for (auto word : wordDict)
        alphaMap[word[0]].push_back(word);

    return wordBreakCore(s, wordDict, 0, alphaMap);
}

dp。
dp[i]=dp[j] && check(s[j..i−1])
其中 dp[i] 表示字符串 s 前 i 个字符组成的字符串 s[0..i-1] 是否能被空格拆分成若干个字典中出现的单词。check(s[j..i-1]) 表示子串 s[j..i-1] 是否出现在字典中。
可以记录set中单词的最大长度和最小长度，缩小j的遍历范围。但是不会减小时间复杂度

bool wordBreak(string s, vector<string>& wordDict){
    unordered_set<string> wordSet;
    int minLength = 0, maxLength = INT_MAX;
    for (string word : wordDict){
        wordSet.insert(word);
        minLength = word.size() > minLength ? minLength : word.size();
        maxLength = word.size() < maxLength ? maxLength : word.size();
    }

    vector<bool> dp(s.size() + 1);
    dp[0] = true;
    for (int i = 1; i <= s.size();i++){
        for (int j = max(0,i-maxLength); i-j>=minLength;j++){
            if(dp[j] && wordSet.find(s.substr(j,i-j))!=wordSet.end()){
                dp[i] = true;
                break;
            }
        }
    }
    return dp[s.size()];
}

时间复杂度：O(n^2)。n为字符串s的长度。
空间复杂度：O(max{m,n})。m为wordDict的长度，n为s的长度。

6月26日面试题 02.01. 移除重复节点（简单）

编写代码，移除未排序链表中的重复节点。保留最开始出现的节点。

示例1:

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

示例2:

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

题解：
用一个哈希表(unordered_set)保存已有元素。

ListNode* removeDuplicateNodes(ListNode* head) {
    if(head==nullptr || head->next==nullptr)
        return head;

    unordered_set<int> valSet;
    ListNode *lastNode = head;
    ListNode *cur = head->next;
    valSet.insert(head->val);
    while (cur != nullptr)
    {
        if(valSet.find(cur->val) == valSet.end()){//非重复节点
            valSet.insert(cur->val);
            lastNode->next = cur;
            lastNode = lastNode->next;
            cur = cur->next;
        }else{//重复节点
            cur = cur->next;
        }
    }
    lastNode->next = cur;//nullptr

    return head;
}

时间复杂度：O(n)
空间复杂度：O(n)

ps. 在不允许用额外空间的情况下，可以用两重循环。时间O(n^2) ，空间o(1)。

6月27日 41. 缺失的第一个正数

给你一个未排序的整数数组，请你找出其中没有出现的最小的正整数。

示例 1:

1 2	输入: [1,2,0] 输出: 3

示例 2:

1 2	输入: [3,4,-1,1] 输出: 2

示例 3:

1 2	输入: [7,8,9,11,12] 输出: 1

提示：

1	你的算法的时间复杂度应为O(n)，并且只能使用常数级别的额外空间。

题解：

排序之后用二分查找从1开始找，可以达到O(mlogn)的时间复杂度。m是缺失正整数的大小。
（代码略）

用O(n)的时间把数组存入unordered_set，在从1开始查找，时间复杂度为O(max{m,n})，m是缺失正整数的大小，n是数组的长度。但是就得用O(n)的空间复杂度。（不符合要求，但是还是通过了哈哈哈）

int firstMissingPositive(vector<int>& nums) {
    if(nums.empty())
        return 0;

    unordered_set<int> numSet;
    int maxNum = INT_MIN;
    for (int n : nums)
    {
        numSet.insert(n);
        maxNum = max(maxNum, n);
    }
    for (int i = 1; i < maxNum;i++){
        if(numSet.find(i)==numSet.end())
            return i;
    }

    return maxNum < 0 ? 1 : maxNum + 1;
}

如果没有缺失，数组从1开始存放元素，则nums[i]==i+1。可以在遍历的时候把元素从idx==0开始放正确位置对应的数，再次遍历时第一个元素与位置不对应的索引即是最小的正整数。

int firstMissingPositive(vector<int>& nums) {
    for (int i = 0; i < nums.size();i++){
        while(nums[i]!=i+1){
            if(nums[i]<=0 || nums[i]>nums.size() || nums[i] == nums[nums[i] - 1])
                //如果 nums[i] == nums[rightPos] 相等，就会无限交换下去。
                break;
            int rightPos = nums[i] - 1;//这个要在if后面，因为当nums[i]太大时，容易溢出
            nums[i] = nums[rightPos];
            nums[rightPos] = rightPos + 1;
        }
    }

    for (int i = 0; i < nums.size(); i++){
        if(nums[i] != (i+1))
            return i + 1;
    }
    return nums.size() + 1;
}

第29场双周赛（6月27日）

5432. 去掉最低工资和最高工资后的工资平均值（简单）

给你一个整数数组 salary ，数组里每个数都是唯一的，其中 salary[i] 是第 i 个员工的工资。
请你返回去掉最低工资和最高工资以后，剩下员工工资的平均值。

示例 1：

输入：salary = [4000,3000,1000,2000]
输出：2500.00000
解释：最低工资和最高工资分别是 1000 和 4000 。
去掉最低工资和最高工资以后的平均工资是 (2000+3000)/2= 2500

题解：

double average(vector<int>& salary) {
    int maxS = INT_MIN, minS = INT_MAX;
    int sum = 0;
    for(int s:salary){
        sum += s;
        maxS = max(maxS, s);
        minS = min(minS, s);
    }
    return (double)(sum - maxS - minS) / (salary.size() - 2);
}

5433. n 的第 k 个因子（中等）

给你两个正整数 n 和 k 。
如果正整数 i 满足 n % i == 0 ，那么我们就说正整数 i 是整数 n 的因子。
考虑整数 n 的所有因子，将它们升序排列。请你返回第 k 个因子。如果 n 的因子数少于 k ，请你返回 -1 。

示例 1：

1
2
3

输入：n = 12, k = 3
输出：3
解释：因子列表包括 [1, 2, 3, 4, 6, 12]，第 3 个因子是 3 。

题解：

int kthFactor(int n, int k) {
    vector<int> factors;
    for (int i = 1; i <= n; i++)
    {
        if(n%i==0)
            factors.push_back(i);
    }
    if(factors.size()<k)
        return -1;

    return factors[k - 1];
}

5434. 删掉一个元素以后全为 1 的最长子数组（中等）

给你一个二进制数组 nums ，你需要从中删掉一个元素。
请你在删掉元素的结果数组中，返回最长的且只包含 1 的非空子数组的长度。
如果不存在这样的子数组，请返回 0 。

示例 1：

1
2
3

输入：nums = [1,1,0,1]
输出：3
解释：删掉位置 2 的数后，[1,1,1] 包含 3 个 1 。

示例 2：

1
2
3

输入：nums = [0,1,1,1,0,1,1,0,1]
输出：5
解释：删掉位置 4 的数字后，[0,1,1,1,1,1,0,1] 的最长全 1 子数组为 [1,1,1,1,1] 。

示例 3：

1
2
3

输入：nums = [1,1,1]
输出：2
解释：你必须要删除一个元素。

示例 4：

1 2	输入：nums = [1,1,0,0,1,1,1,0,1] 输出：4

示例 5：

1 2	输入：nums = [0,0,0] 输出：0

题解：
找到0，之后双指针分别往前和往后直到碰到下一个0。

int longestSubarray(vector<int>& nums) {
    int n = nums.size();
    int sum = 0;
    for (int i = 0; i < n; ++i)
        sum += nums[i];
    if (sum == n)
        return n-1;
    int res = 0;
    for (int i = 0; i < n; ++i)
    {
        if (nums[i] == 1) continue;
        int L = i, R = i;
        while (L-1 >= 0 && nums[L-1] == 1) -- L;
        while (R+1 < n && nums[R+1] == 1) ++ R;
        res = max(res, R-L);
    }
    return res;
}

6月28日 209. 长度最小的子数组（中等）

给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的连续子数组，并返回其长度。如果不存在符合条件的连续子数组，返回 0。

示例:

1
2
3

输入: s = 7, nums = [2,3,1,2,4,3]
输出: 2
解释: 子数组 [4,3] 是该条件下的长度最小的连续子数组。

题解：
双指针。i是左边的指针，j是右边的指针。sum<s时，j++ ，sum>=s时，i++。

int minSubArrayLen(int s, vector<int>& nums) {
    if(nums.empty())
        return 0;
    int i = 0, j = 0, sum = nums[0], minSub = INT_MAX;
    while(j<nums.size()){
        if(sum<s){
            j++;
            if(j<nums.size())
                sum += nums[j];
        }else{
            minSub = min(minSub, j - i + 1);
            sum -= nums[i];
            i++;
        }
        if(minSub==1)
            return 1;
    }
    return minSub == INT_MAX ? 0 : minSub;
}

时间复杂度O(n)
空间复杂度O(1)

6月29日 215. 数组中的第K个最大元素（中等）

在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

示例 1:

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

示例 2:

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

说明:

1	你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。

题解：

排序。时间复杂度O(nlogn)。

int findKthLargest(vector<int> &nums, int k) {
        int size = nums.size();
        //默认的升序
        sort(begin(nums), end(nums));
        return nums[size - k];

        // 降序
        // sort(begin(nums), end(nums), greater<int>());
        // return nums[k-1];
    }

快排的partition函数（可以看这篇博客中的算法类例题——排序）。每次可以找到一个正确的位置i，当k>i时，在 i 的右边找；当k<i时，在 i 的左边找；当k==i时，直接输出nums[i]。

int Partition(vector<int> &arr, int start, int end){
    if(arr.size()<2 || start<0 || end>arr.size())
        return -1;

    int pivot = arr[start];  //除了选择第一个，也可以随机选择一个元素作为pivot
    while (start<end)
    {
        while(start<end && arr[end]>=pivot)
            end--;
        arr[start] = arr[end];
        while (start < end && arr[start] <= pivot)
            start++;
        arr[end] = arr[start];
    }
    arr[start] = pivot;
    return start;
}

int findKthLargest(vector<int>& nums, int k) {
    int len = nums.size();
    int left = 0;
    int right = len - 1;
    int target = len - k;

    while (left<right) {
        int index = Partition(nums, left, right);
        if (index == target) {
            return nums[index];
        } else if (index < target) {
            left = index + 1;
        } else {
            right = index - 1;
        }
    }
    return nums[left];
}

时间复杂度：O(n)。证明过程可以参考 算法导论 9.2：期望为线性的选择算法
空间复杂度：O(1)

6月30日剑指 Offer 09. 用两个栈实现队列

用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )

示例 1：

输入：
["CQueue","appendTail","deleteHead","deleteHead"]
[[],[3],[],[]]
输出：[null,null,3,-1]

题解：
一个栈入，一个栈出。当要插入数据时，直接插入入栈；当要取出数据时，如果出栈不为空，则从入栈依次取出放入出栈，直到入栈为空。这样就能保证后进先出。

class CQueue {
    stack<int> inputStack, outputStack;
public:
    CQueue() {
        while(!inputStack.empty())
            inputStack.pop();
        while(!outputStack.empty())
            outputStack.pop();
    }
    
    void appendTail(int value) {
        inputStack.push(value);
    }
    
    int deleteHead() {
        if(outputStack.empty()){
            while(!inputStack.empty()){
                outputStack.push(inputStack.top());
                inputStack.pop();
            }
        }
        if(outputStack.empty())
            return -1;
        else{
            int output = outputStack.top();
            outputStack.pop();
            return output;
        }
    }
};

6月1日 1431. 拥有最多糖果的孩子（简单）

6月2日 剑指Offer面试题64. 求1+2+…+n

6月3日 837. 新21点（中等）

6月4日 238. 除自身以外数组的乘积（中等）

6月5日 剑指Offer面试题29. 顺时针打印矩阵（简单）

6月6日 128. 最长连续序列（困难）

6月7日 126. 单词接龙 II（困难）

6月8日 990. 等式方程的可满足性（中等）

6月9日 剑指Offer面试题46. 把数字翻译成字符串（中等）

6月10日 回文数（简单）

6月11日 739. 每日温度（中等）

6月12日 15. 三数之和

6月13日 70. 爬楼梯（简单）

第28场双周赛 6.13

第193场周赛 6.14

6月14日 1300. 转变数组后最接近目标值的数组和（中等）

6月15日 14. 最长公共前缀（简单）

6月16日 297. 二叉树的序列化与反序列化（困难）

6月17日 1014. 最佳观光组合（中等）

6月18日 1028. 从先序遍历还原二叉树（困难）

6月19日 125. 验证回文串（简单）

6月20日 10. 正则表达式匹配（困难）

6月21日 124. 二叉树中的最大路径和（困难）

第194场周赛 6.21

5440. 数组异或操作

5441. 保证文件名唯一（中等）

5442. 避免洪水泛滥（中等）

6月22日 面试题 16.18. 模式匹配（中等）

6月23日 67. 二进制求和（简单）

6月24日 16. 最接近的三数之和（中等）

6月25日 [139. 单词拆分（中等）(https://leetcode-cn.com/problems/word-break/)

6月26日 面试题 02.01. 移除重复节点（简单）

6月27日 41. 缺失的第一个正数

第29场双周赛（6月27日）

6月28日 209. 长度最小的子数组（中等）

6月29日 215. 数组中的第K个最大元素（中等）

6月30日 剑指 Offer 09. 用两个栈实现队列

6月2日剑指Offer面试题64. 求1+2+…+n

6月5日剑指Offer面试题29. 顺时针打印矩阵（简单）

6月9日剑指Offer面试题46. 把数字翻译成字符串（中等）

6月10日回文数（简单）

6月22日面试题 16.18. 模式匹配（中等）

6月26日面试题 02.01. 移除重复节点（简单）

6月30日剑指 Offer 09. 用两个栈实现队列