当前位置：首页 > news >正文

LeetCode八月每日一题题解（个人记录打卡）

news 来源：原创 2024/4/28 3:10:46

文章目录

八月每日一题
- 1374. 生成每种字符都是奇数个的字符串
- 622. 设计循环队列
- 899. 有序队列
- 1403. 非递增顺序的最小子序列
- 623.在二叉树中增加一行
- 1408. 数组中的字符串匹配
- 636. 函数的独占时间（不会）
- 761. 特殊的二进制序列（不会）
- 1413. 逐步求和得到正数的最小值
- 640. 求解方程（不会）
- 1417重新格式化字符串
- 1282. 用户分组
- 768. 最多能完成排序的块 II
- 1422. 分割字符串的最大得分
- 641. 设计循环双端队列
- 1656. 设计有序流
- 1302. 层数最深叶子节点的和
- 1224. 最大相等频率（不会）
- 1450. 在既定时间做作业的学生人数
- 654. 最大二叉树
- 998. 最大二叉树 II
- 1455. 检查单词是否为句中其他单词的前缀
- 655. 输出二叉树
- 782. 变为棋盘(不会)
- 1460. 通过翻转子数组使两个数组相等
- 658. 找到 K 个最接近的元素
- 1464. 数组中两元素的最大乘积
- 662. 二叉树最大宽度
- 793. 阶乘函数后 K 个零(不会)
- 1470. 重新排列数组
- 946. 验证栈序列
- 总结

八月每日一题

1374. 生成每种字符都是奇数个的字符串

https://leetcode.cn/problems/generate-a-string-with-characters-that-have-odd-counts/

思路：如果为奇数返回一个b+奇数个a，若为偶数返回全部的a

class Solution {
public:
    string generateTheString(int n) {
   if(n%2!=0){
       return string(n,'a'); 
   }else{
       return 'b'+string(n-1,'a');
   }
    }
};

622. 设计循环队列

https://leetcode.cn/problems/design-circular-queue/

思路：数组模拟

在判断为空和为满的时候需要用一个空的位置进行标记
入队之前要检查是否为满
出队之前要检查是否为空
满的判断条件 front == (rear+1)%size
空的判断条件 rear == front
找队尾的条件 (rear - 1 + capacity) % capacity 而非 rear

class MyCircularQueue {
private:
int size;
vector<int> queue;
int rear;
int front;
public:
    MyCircularQueue(int k) {
        this->size = k+1;
        this->front=this->rear=0;
        queue = vector<int>(this->size);

    }
    
    bool enQueue(int value) {
     //插入之前判断是否满
     if(isFull())return false;
     queue[rear] = value;
     rear = (rear+1)%size;
     return true;

    }
    
    bool deQueue() {
        if(isEmpty())return false;
        front = (front+1) %size;
        return true;
    }
    
    int Front() {
   if(isEmpty())return -1;
   return queue[this->front];
    }
    
    int Rear() {
        if(isEmpty())return -1;
        // return queue[this->rear];
         return queue[(rear - 1 + size) % size];
    }
    
    bool isEmpty() {
        return this->rear == this->front;
    }
    
    bool isFull() {
        return this->front == (this->rear+1)%this->size;
    }
};

899. 有序队列

https://leetcode.cn/problems/orderly-queue/

思路：

如果k等于1，那么就找到所有移动过程中形成的字符串字典树最小的
如果k！=1，直接排序，得到字典树最小的

class Solution {
public:
    string orderlyQueue(string s, int k) {
       //

       if(k==1){
           string smallStr=s;
         
           for(int i=0;i<s.size();i++){
           s=s.substr(1)+s[0];
        smallStr = min(smallStr,s);
           }
           s=smallStr;
       }
       else{
            sort(s.begin(),s.end());
       }
       
      return s;
    }
};

1403. 非递增顺序的最小子序列

https://leetcode.cn/problems/minimum-subsequence-in-non-increasing-order/

思路：

根据题目要求，我们要尽可能是的找到的子序列的长度最小，同时如果长度相等，我们要找到一个长度相等情况下，元素之和最小的。

因此，根据这个条件我们可以对数组进行递减排序。

从前往后将遍历到的元素加入到res当中，比较当前res元素之和是否大于nums数组剩余的元素之和，如果大于就返回res，即找到一个符合题目条件的序列

class Solution {
public:
    vector<int> minSubsequence(vector<int>& nums) {
    //找到子序列，要大于剩余的
    //优先排序
    int n=nums.size();
     sort(nums.rbegin(),nums.rend());
    vector<int> res;
    for(int i=0;i<n;i++){
        res.push_back(nums[i]);
        int curNumLeft =accumulate(res.begin(),res.end(),0);
        int curNumRight = accumulate(nums.begin()+i+1,nums.end(),0);
        if(curNumLeft>curNumRight){
            return res;
        }
    }
     return res;
    }
   
};

623.在二叉树中增加一行

思路：dfs递归

/**
 * 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:
    TreeNode* addOneRow(TreeNode* root, int val, int depth) {
       if(root ==nullptr){return nullptr;}
       if(depth ==1){
           return new TreeNode(val,root,nullptr);
       }
       if(depth ==2){
           root->left =new TreeNode(val,root->left,nullptr);
           root->right = new TreeNode(val,nullptr,root->right);
       }else{
           root->left = addOneRow(root->left,val,depth-1);
           root->right = addOneRow(root->right,val,depth-1);
       }
       return root;

    }
};

思路：bfs广度遍历

/**
 * 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:
    TreeNode* addOneRow(TreeNode* root, int val, int depth) {
        //根据题目要求的第一个条件
        if(depth==1) return new TreeNode(val,root,nullptr);
        //用队列来模拟广度
        queue<TreeNode*> q;
        //先将根节点入队
        q.push(root);
        //h用于记录当前的高度
        for(int h=1;!q.empty();h++){
            //找到相应高度进行插入元素
            if(h==depth-1){
                while(!q.empty()){
                    //找到当前的根节点
                    TreeNode* cur=q.front();
                    //根节点出队
                    q.pop();
                    //为当前的根节点左右子树插入相应元素，并将原左右子树分配给现在插入的左右的两个元素的左边以及右边
                    cur->left =new TreeNode(val,cur->left,nullptr);
                    cur->right = new TreeNode(val,nullptr,cur->right);
                }
            }
            //如果没有找到当前的插入位置，就需要不断入队
            for(int i=q.size();i>0;i--){
                TreeNode* cur=q.front();
                q.pop();
                if(cur->left!=nullptr){ q.push(cur->left);}
                if(cur->right!=nullptr){q.push(cur->right);}
            }
        }
        return root;

    }
};

1408. 数组中的字符串匹配

https://leetcode.cn/problems/string-matching-in-an-array/

class Solution {
public:
    vector<string> stringMatching(vector<string>& words) {
        string s;
         vector<string> res;
        for(auto word:words){
            s+=" "+word;
        }
          for(auto word:words){
              if(s.find(word)!=s.rfind(word)){
                  res.push_back(word);
              }
          }
          return res;
    }
};

find() 正向查找要匹配字符串的第一个字符出现的位置

rfind()反向查找要匹配的字符串的第一个字符出现的位置

对于上面两个函数，若查找失败则会返回一个特殊标记npos，一般写做string::npos

首先将数组拼接成一个字符串以空格分隔
通过正向和反向查找字符串，如果通过正向和反向查找到得位置不是同一个位置，则说明时符合条件得（比如查找 as，正向查找得返回得结果为2，负向查找的结果为6 s为 " mass as … "）

636. 函数的独占时间（不会）

https://leetcode.cn/problems/exclusive-time-of-functions/

思路：

class Solution {
public:
    vector<int> exclusiveTime(int n, vector<string>& logs) {
        stack<pair<int, int>> st; // {idx, 开始运行的时间}
        vector<int> res(n, 0);
        for (auto& log : logs) {
            char type[10];
            int idx, timestamp;
            sscanf(log.c_str(), "%d:%[^:]:%d", &idx, type, &timestamp);
            if (type[0] == 's') {
                if (!st.empty()) {
                    res[st.top().first] += timestamp - st.top().second;
                    st.top().second = timestamp;
                }
                st.emplace(idx, timestamp);
            } else {
                auto t = st.top();
                st.pop();
                res[t.first] += timestamp - t.second + 1;
                if (!st.empty()) {
                    st.top().second = timestamp + 1;
                }
            }
        }
        return res;
    }
};

761. 特殊的二进制序列（不会）

https://leetcode.cn/problems/special-binary-string/)

思路就是：把 0，1 看成（）括号

class Solution {
public:
    string makeLargestSpecial(string s) {
       if(s.size()<2){return s;}
       int cnt =0,left =0;
       vector<string> subs;
       for(int i=0;i<s.size();i++){
           if(s[i]=='1'){cnt++;}
           else{
               --cnt;
               if(cnt==0){
                   subs.push_back("1"+makeLargestSpecial(s.substr(left+1,i-left-1))+"0");
                   left = i+1;
               }
           }
       }
         for(int i=0;i<subs.size();i++){
           cout<<subs[i]<<":";
       }
       cout<<"==="<<endl;
       sort(subs.begin(),subs.end(),greater<string>{});
       string ans = accumulate(subs.begin(),subs.end(),""s);
       for(int i=0;i<subs.size();i++){
           cout<<subs[i]<<":";
       }
       return ans;
    }
   
};

1413. 逐步求和得到正数的最小值

https://leetcode.cn/problems/minimum-value-to-get-positive-step-by-step-sum/

思路：贪心

题目要求所有累加和都要大于等于一，只要满足最小的累加和+startValue>=1即可那么startValue的最小值即为 1-sumMin

class Solution {
public:
    int minStartValue(vector<int>& nums) {
            int sum=0;int sumMin=0;
            for(int num:nums){
                sum+=num;
                sumMin = min(sum,sumMin);
            }
            //sumMin+startValue >=1;
            return  1-sumMin;
    }
};

640. 求解方程（不会）

https://leetcode.cn/problems/solve-the-equation

class Solution {
public:
    string solveEquation(string equation) {
        int factor = 0, val = 0;
        int index = 0, n = equation.size(), sign1 = 1; // 等式左边默认系数为正
        while (index < n) {
            if (equation[index] == '=') {
                sign1 = -1; // 等式右边默认系数为负
                index++;
                continue;
            }

            int sign2 = sign1, number = 0;
            bool valid = false; // 记录 number 是否有效
            if (equation[index] == '-' || equation[index] == '+') { // 去掉前面的符号
                sign2 = (equation[index] == '-') ? -sign1 : sign1;
                index++;
            }
            while (index < n && isdigit(equation[index])) {
                number = number * 10 + (equation[index] - '0');
                index++;
                valid = true;
            }

            if (index < n && equation[index] == 'x') { // 变量
                factor += valid ? sign2 * number : sign2;
                index++;
            } else { // 数值
                val += sign2 * number;
            }
        }

        if (factor == 0) {
            return val == 0 ? "Infinite solutions" : "No solution";
        }
        return string("x=") + to_string(-val / factor);
    }
};

1417重新格式化字符串

https://leetcode.cn/problems/reformat-the-string/

思路：

统计数字和字母分别有多少个字符，再用两个string，分别来存储字母和数字
如果两个字符串大小相差大于1，则说明根本无法满足题目进行交换
让字符大小大的先存（否则，比如covid2019，如果按照数字先存，则 2c0o1v9id,不符合要求，而是c2o0v1i9d符合要求），所以需要交换字符串，让一个字符串始终存放长的字符串，另一个存放短的
定义两个指针分别指向两个新的字符串，遍历追加到最终结果当中

class Solution {
public:
  string reformat(string s) {
    int cnt1 = 0;
    int cnt2 = 0;
    string str1 = "";
    string str2 = "";
    string res = "";
     //统计字母，数字字符串的大小，以及追加到两个数组当中国
    for (int i = 0; i < s.size(); i++) {
        if (isdigit(s[i])) { cnt1++; str1 += s[i]; }
        else if (isalpha(s[i])) { cnt2++; str2 += s[i]; }
    }
      //如果字母和数字的数字个数大于1，则无法满足题意格式化
    if (abs(cnt1 - cnt2) > 1)return "";
    int i = 0, j = 0;
    //始终确保str1是最长的那个，优先填充最长的那个
    if(str1.size()<str2.size()){
        string t;
        t = str1;
        str1=str2;
        str2=t;
    }
      //定义i，j分别指向数字，和字母的字符串。双指针操作
    while (i <str1.size()) {
    res+=str1[i];
    	//当j小于str2长度才进行追加（否则，可能后面无元素可以追加了）
        if (j < str2.size()) {
            res += str2[j];
        }
        i++;
        j++;
    }
      //返回结果
    return res;
}
};

1282. 用户分组

https://leetcode.cn/problems/group-the-people-given-the-group-size-they-belong-to/

思路：

首先需要理解groupSizes表示的是对应对应下标的人应该存在大小为多少的组里面（某个身份的人，应该睡在几人间）

题目最后要求的就是通过上述的划分，那些人应该睡在几人间（一人间睡那一个人，三人间睡哪三个人）

定义一个hashmap用于存储数组大小为x的存放哪几个人（可能超过了x大小，比如用例1）
接下来就需要对可能超过数组大小（房间人数）的这些人进行处理，分成几个房间（房间大小x）
最后将划分的结果存在最终的答案当中

class Solution {
public:
    vector<vector<int>> groupThePeople(vector<int>& groupSizes) {
        vector<vector<int>> res;
        unordered_map<int,vector<int>>mp;
        int i=0;
        //先按照组大小进行划分 ID为多少的存放在多大的组内
      for(i=0;i<groupSizes.size();i++){
           //cout<<groupSizes[i]<<":"<<i<<endl;
            mp[groupSizes[i]].push_back(i);
      }
     for (auto &[size, people] : mp) {
         //房间为size的 应该有几个（people长度可能超过size）
         int groupCount  = people.size()/size;
         //分为groupCount个组
         for(int i=0;i<groupCount;i++){
              vector<int> g; 
             //每一组的起始位置
             int start = i*size;
            
             for(int j=0;j<size;j++){
                 g.push_back(people[start+j]);
             }
             res.push_back(g);
         }
         cout<<size<<endl;
     }

         return res;
    }
   
};

768. 最多能完成排序的块 II

https://leetcode.cn/problems/max-chunks-to-make-sorted-ii/

思路：单调栈

如果当前元素小于栈顶元素，则用变量maxNum记录栈顶元素，如果栈不为空且栈顶元素大于当前元素，则出栈。同时将当前元素存入栈中，作为一个区间块的标记

class Solution {
public:
    int maxChunksToSorted(vector<int>& arr) {
        stack<int> st;
        st.push(arr[0]);
        int res=0;
        for(int i=1;i<arr.size();i++){
          if(arr[i]<st.top()){
              int maxNum = st.top();
              while(!st.empty() &&st.top()>arr[i]) st.pop();
              st.push(maxNum);
          }else{
              st.push(arr[i]);
          }
        }
        return st.size();
    }
};

1422. 分割字符串的最大得分

https://leetcode.cn/problems/maximum-score-after-splitting-a-string/

思路一：暴力

一个一个试分割点，将字符串分割为左右两边，在统计左边0的个数以及右边1的个数

最后取最大值

class Solution {
public:
    int maxScore(string s) {
        int res=0;
        int n = s.size();
        // //标记位置
        for(int i=1;i<n;i++){
            string strL = s.substr(0,i);
            string strR = s.substr(i,n);
            cout<<"strL:"<<strL<<"--------"<<"strR:"<<strR<<endl;
            int sum=0;
            for(int j=0;j<strL.size();j++){
                if(strL[j]=='0') sum++;
            }
            for(int j=0;j<strR.size();j++){
                if(strR[j]=='1') sum++;
            }
            res = max(res,sum);
        }

        return res;
    }
};

思路二：前缀和和后缀和

sumL统计i之前的0的个数

sumR统计i之后1的个数

每个位置分开的分数即为left[i] + right[i+1];
遍历取最大即可。

class Solution {
public:
    int maxScore(string s) {
 int n = s.length();
 int res=0;
        int sum =0;
        vector<int> sumL(n);
        vector<int> sumR(n);
        //统计前缀和 0 的个数
        for(int i=0;i<n;i++){
            if(s[i]=='0'){
                sum++;
                
            }
            sumL[i]+=sum;
        }
        sum =0;
    //统计后缀和 1 的个数
        for(int i=n-1;i>=0;i--){
            if(s[i]=='1'){
                sum++;
            }
            sumR[i]+=sum;
        }
            for(int i=0;i<n-1;i++){
             res = max(res,sumL[i]+sumR[i+1]);
                
            }
        return res;
    }
};

641. 设计循环双端队列

https://leetcode.cn/problems/design-circular-deque/

思路和前面 622设计循环队列类似的思路

class MyCircularDeque {
public:
 vector<int> element;
    int rear, front;
    int capacity;
    MyCircularDeque(int k) {
         rear=0;
         front=0;
         capacity = k+1;
        element = vector<int>(k+1);
    }
    
    bool insertFront(int value) {
        if(isFull())return false;
         front = (front-1+capacity)%capacity;
        element[front] = value;
        return true;
    }
    
    bool insertLast(int value) {
        if(isFull())return false;
        element[rear] = value;
        rear = (rear+1)%capacity;
          return true;
    }
    
    bool deleteFront() {
        if(isEmpty())return false;
          front = (front+1)%capacity;
          return true;
    }
    
    bool deleteLast() {
         if(isEmpty())return false;
            rear = (rear - 1 + capacity) % capacity;
          return true;
    }
    
    int getFront() {
         if(isEmpty())return -1;
         return element[front];
    }
    
    int getRear() {
 if(isEmpty())return -1;
   return element[(rear - 1 + capacity) % capacity];
    }
    
    bool isEmpty() {
        return rear ==front;
    }
    
    bool isFull() {
        return (rear+1)%capacity==front;
    }
};

1656. 设计有序流

https://leetcode.cn/problems/design-an-ordered-stream/

思路：

不管怎么样，都现在id下面先插入元素，如果说ptr指向的元素为空或者ptr超出了整个数组长度，直接返回结果。如果ptr指向的不为空且长度为超过整个数组的长度那么将当前ptr指向的加入到结果res当中，同时ptr指针往后移动。

class OrderedStream {
public:
    vector<string> v;
    int ptr=1;
    int id;
    OrderedStream(int n) {
        v=vector<string>(n+1);
    }
    
    vector<string> insert(int idKey, string value) {
         v[idKey] = value;
         vector<string> res;
         while (ptr < v.size() && !v[ptr].empty()) {
            res.push_back(v[ptr]);
            ++ptr;
        }
        return res;
        }

};

1302. 层数最深叶子节点的和

https://leetcode.cn/problems/deepest-leaves-sum/

思路:bfs

记录每一层结点之后，到了最后一层即为要求的结点之和。这里要注意sum的放置位置（要在每一层之前进行初始化操作）

/**
 * 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:
    int deepestLeavesSum(TreeNode* root) {
        int sum;
        queue<TreeNode* > q;
        if(root==nullptr){return 0;}
        //根结点先入队
        q.push(root);
        while(!q.empty()){\
            //每一层的总和 sum
            sum =0;
            //每一层结点的个数
            int curSize = q.size();
            for(int i=0;i<curSize;i++){
                TreeNode* t = q.front();
                q.pop();
                //计算当前一层结点之和
                sum+=t->val;
                if(t->left!=nullptr){q.push(t->left);}
                if(t->right!=nullptr){q.push(t->right);}
            }
            //打印每一层结点总和  （最后的和即为最深层的结点和）
              cout<<sum<<endl;
        }

        return sum;
    }
};

1224. 最大相等频率（不会）

https://leetcode.cn/problems/maximum-equal-frequency/

思路：

class Solution {
public:
    int maxEqualFreq(vector<int>& nums) {
        map<int,int> mp;
        map<int,vector<int>> mp2;
        int ans=1;
        for(int i=0;i<nums.size();i++){
            if(mp.find(nums[i])==mp.end()){
                mp.insert(pair<int,int>(nums[i],1));
                if(mp2.find(1)==mp2.end()){
                    vector<int> mid;
                    mid.push_back(nums[i]);
                    mp2.insert(pair<int,vector<int>>(1,mid));
                }
                else{
                    mp2[1].push_back(nums[i]);
                }
            }
            else{
                remove(mp2[mp[nums[i]]].begin(),mp2[mp[nums[i]]].end(),nums[i]);
                mp2[mp[nums[i]]].pop_back();
                if(mp2[mp[nums[i]]].size()==0){
                    // cout<<i<<"    &"<<mp2.size()<<endl;
                    mp2.erase(mp[nums[i]]);
                    // cout<<i<<"    &"<<mp2.size()<<endl;
                }
                int l=mp[nums[i]]++;
                if(mp2.find(l+1)==mp2.end()){
                    vector<int> mid;
                    mid.push_back(nums[i]);
                    mp2.insert(pair<int,vector<int>>(l+1,mid));
                }
                else{
                    mp2[l+1].push_back(nums[i]);
                }
            }
            // cout<<i<<endl;
            // for(map<int,vector<int>>::iterator it=mp2.begin();it!=mp2.end();it++){
                
            //     cout<<it->first<<"  "<<it->second.size()<<endl;
                
            // }
            // cout<<endl;
            if(mp2.size()==1){
                map<int,vector<int>>::iterator it=mp2.begin();
                if(it->first!=1&&it->second.size()!=1){
                    continue;
                }
                ans=max(ans,i);
            }
            else if(mp2.size()==2){
                // cout<<i<<endl;
                int pre;int now;int presize;int nowsize;
                for(map<int,vector<int>>::iterator it=mp2.begin();it!=mp2.end();it++){
                    if(it==mp2.begin()){
                        pre=it->first;presize=it->second.size();
                    }
                    else{
                        now=it->first;nowsize=it->second.size();
                    }
                }
                if(pre==1&&presize==1){
                    ans=max(ans,i);
                }
                if(now-pre==1&&nowsize==1){
                    ans=max(ans,i);
                }
            }
            else{
                continue;
            }
        }
        // for(map<int,int>::iterator it=mp.begin();it!=mp.end();it++){
        //     cout<<it->first<<"  "<<it->second<<endl;
        // }
        return ans+1;
    }
};

1450. 在既定时间做作业的学生人数

https://leetcode.cn/problems/number-of-students-doing-homework-at-a-given-time/

思路：

比较querTime是否在start[i]和end[i]当中即可（start和end数组在长度上一样的）

class Solution {
public:
    int busyStudent(vector<int>& startTime, vector<int>& endTime, int queryTime) {
        int res=0;
        int n = startTime.size();
        for(int i=0;i<n;i++){
            if(startTime[i]<=queryTime &&endTime[i]>=queryTime ){
                res++;
            }
        }
        return res;
    }
};

654. 最大二叉树

https://leetcode.cn/problems/maximum-binary-tree/

思路：递归

明确递归结束条件 l>r 表明当前数组已经无元素，返回nullptr
明确每一次递归的目的是找到当前数组段的最大值，并记录最大值的位置，方便递归左右段数组
递归左右段数组，构建为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:
    TreeNode* maxTree(vector<int>& nums,int left,int right){
        if(left>right){return nullptr;}
        //找出当前段中的最大结点
        int mid=left;
        int max=-1;
        for(int i=left;i<=right;i++){
            if(nums[i]>max){max = nums[i];mid = i;
            //cout<<mid<<endl;
            }
        }
        TreeNode * root = new TreeNode (nums[mid]);
        root->left = maxTree(nums,left,mid-1);
        root->right = maxTree(nums,mid+1,right);
        return root;

    }
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        return maxTree(nums,0,nums.size()-1);
       
    }
};

思路二单调栈

遍历数组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:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        deque<TreeNode* > q;
        int n =nums.size();
        for(int i=0;i<n;i++){
             TreeNode*  node=new TreeNode(nums[i]);
          
         while(!q.empty() &&nums[i]>q.front()->val){
             node->left = q.front();
             q.pop_front();
         }
         if(!q.empty()){
            // cout<< q.front()->val<<endl;
             q.front()->right = node;
         }
         // cout<<node->val<<endl;
         q.push_front(node);
        }
       
        return q.back();
      
    }
};

998. 最大二叉树 II

https://leetcode.cn/problems/maximum-binary-tree-ii/

1455. 检查单词是否为句中其他单词的前缀

https://leetcode.cn/problems/check-if-a-word-occurs-as-a-prefix-of-any-word-in-a-sentence/

思路：

遍历sentence 根据‘ ’来划分单词，然后通过当前单词是否与searchWord匹配。注意要对第一个单词特殊处理一下

class Solution {
public:
    int isPrefixOfWord(string sentence, string searchWord) {
        int ans = -1;
        int n =sentence.size();
        int  word_index =1;
        for(int i=0;i<n;i++){
            //是一个单词的标志
            if(sentence[i]==' '||i==0){
                //每一次单词的首位置
                int k =i+1;
               // cout<<k<<":"<<sentence[k]<<endl;
                int j=0;
                //当是第一个单词的时候，标志为0
                if(i==0) k=0;
                //循环对比单词是否和searchWord一致
                while(j<searchWord.size() &&k<sentence.size() &&searchWord[j]==sentence[k]){
                    k++;
                    j++;
                }
                //如果j已经走到头，就说明是该单词的前缀
                if(j==searchWord.size())return word_index;
                //记录是第几个单词
                word_index++;
            }
        }
        return -1;

    }
};

655. 输出二叉树

https://leetcode.cn/problems/print-binary-tree/

思路：

首先要知道二叉树的高度，才可以知道m，n 因此先算出高度h
有了h之后需要递归进行初始化二维数组，根据题目规则的后面几个条件可知，当此刻结点为r,c的位置的时候，左子结点在r+1，c - pow(2,h-r-1),右子结点在r+1，c + pow(2,h-r-1)
递归的初始r，c 分别为 0 (n-1)/2

class Solution {
public:
//计算树的高度
    int TreeHeight(TreeNode* root){
        if(root==nullptr)return 0;
        return max(TreeHeight(root->left),TreeHeight(root->right))+1;

    }
    //构建二维数组
     void bulidTree(vector<vector<string>> &res,TreeNode* root,int r,int c,const int& h){
         //此刻的结点应该存放的位置
         res[r][c] =to_string(root->val);
         //左子结点的位置
         if(root->left){bulidTree(res,root->left,r+1,c - pow(2,h-r-1),h);}
         右子结点的位置
         if(root->right){
           bulidTree(res,root->right,r+1,c + pow(2,h-r-1),h);
         }
    
     }
    vector<vector<string>> printTree(TreeNode* root) {
      //  m = h+1;  n = 2^(h+1)  -1    根结点位于res[0][(n-1)/2] 
       //根据高度 得出n m
       int h =TreeHeight(root)-1;
       //cout<<h<<endl;
       int m = TreeHeight(root);
       int n = pow(2,m)-1;
    vector<vector<string>>  res(m,vector<string>(n,""));
     bulidTree(res,root,0,(n-1)/2,h);
    return res;
    }
};

782. 变为棋盘(不会)

https://leetcode.cn/problems/transform-to-chessboard/

1460. 通过翻转子数组使两个数组相等

https://leetcode.cn/problems/make-two-arrays-equal-by-reversing-sub-arrays/

思路：

如果arr 长度是 11，那么只需判断arr 和 target 是否相同即可。因为此时翻转非空子数组的过程并不会改变数组，只需判断原数组是否相同即可。

如果 arr 长度大于 11，那么首先证明通过一次或二次翻转过程，可以实现数组 arr 中任意两个元素交换位置并且保持其他元素不动。如果想要交换两个相邻元素的位置，那么翻转这两个元素组成的子数组即可。如果想要交换两个非相邻元素的位置，那么首先翻转这两个元素及其中间所有元素组成的子数组，再翻转这两个元素中间的元素组成的子数组即可。这样下来，通过一次或二次翻转过程，即可交换数组中任意两个元素的位置。一旦一个数组中任意两个元素可以交换位置，那么这个数组就能实现任意重排。只需要arr 和 target 元素相同，arr 就能通过若干次操作变成 target。(自己补充：所以可以采用排序的方式进行)

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/make-two-arrays-equal-by-reversing-sub-arrays/solution/tong-guo-fan-zhuan-zi-shu-zu-shi-liang-g-dueo/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

class Solution {
public:
    bool canBeEqual(vector<int>& target, vector<int>& arr) {
       unordered_map<int, int> counts1, counts2;
        for (int num : target) {
            counts1[num]++;
        }
        for (int num : arr) {
            counts2[num]++;
        }
        if(counts1.size() !=counts2.size())return false;
        for(auto&[key,value]:counts1){
            //如果counts2 中不包含 counts1中的元素   或者 counts2中某个元素的个数不等于count1中某个元素的个数则肯定不能翻转成功
            if(!counts2.count(key) || counts2[key]!=value){return false;}
        }
        return true;
    }
};

class Solution {
public:
    bool canBeEqual(vector<int>& target, vector<int>& arr) {
        sort(arr.begin(),arr.end());
        sort(target.begin(),target.end());
        int n = target.size();
        for(int i=0;i<n;i++){
            if(arr[i]==target[i])continue;
            else{
                return false;
            }
        }
        return true;
    }
};

658. 找到 K 个最接近的元素

https://leetcode.cn/problems/find-k-closest-elements/

思路: 双指针

指针分别指向左边界和右边界最后需要删除数组长度-k长度的元素

具体删除是根据左指针和右指针位于x的距离而进行指针的移动操作进行的

class Solution {
public:
    vector<int> findClosestElements(vector<int>& arr, int k, int x) {
      int l=0,r=arr.size()-1;
      int deleteNum = arr.size()-k;
      while(deleteNum){
          
          if(abs(arr[l]-x)>abs(arr[r]-x)){
              l++;
          }else{
              r--;
          }
          deleteNum--;
      }
      return vector<int>(arr.begin()+l,arr.begin()+l+k);
    }
};

1464. 数组中两元素的最大乘积

https://leetcode.cn/problems/maximum-product-of-two-elements-in-an-array/

思路：

方法一：两重for循环遍历数组

方法二：通过sort函数排序，找到最大元素和次大的元素

方法三：直接通过一层遍历找到最大元素和次大的元素

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int max =-100;
        int n=nums.size();
        for(int i=0;i<n;i++){
            for(int j =i+1;j<n;j++){
                int x =(nums[i]-1)*(nums[j]-1);
                if(x>max){
                    max = x;
                }
            }
        }
        return max;
    }
};

class Solution {
public:
    int maxProduct(vector<int>& nums) {
          sort(nums.rbegin(), nums.rend());
        return (nums[0] - 1) * (nums[1] - 1);
    }
};

class Solution {
public:
    int maxProduct(vector<int>& nums) {
         int maxFirst=nums[0];
         int maxSecond = nums[1];
         if(maxFirst<maxSecond){
             swap(maxFirst,maxSecond);
         }
         for(int i=2;i<nums.size();i++){
             //如果当前遍历的元素比最大的还大。那么最大值更新，次大值更新为之前最大值
             if(nums[i]>maxFirst){
                 maxSecond = maxFirst;
                 maxFirst = nums[i];
                 
             }
             //如果当前元素比次大值大，则更新次大值即可
             else if(nums[i]>maxSecond){
                 maxSecond = nums[i];
               
             }
         }
         return (maxFirst-1)*(maxSecond-1);
    }
};

662. 二叉树最大宽度

https://leetcode.cn/problems/maximum-width-of-binary-tree/

思路：

793. 阶乘函数后 K 个零(不会)

https://leetcode.cn/problems/preimage-size-of-factorial-zeroes-function/

思路：

class Solution {
public:
    int zeta(long x) {
        int res = 0;
        while (x) {
            res += x / 5;
            x /= 5;
        }
        return res;
    }

    long long help(int k) {
        long long r = 5LL * k;
        long long l = 0;
        while (l <= r) {
            long long mid = (l + r) / 2;
            if (zeta(mid) < k) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return r + 1;
    }

    int preimageSizeFZF(int k) {
        return help(k + 1) - help(k);
    }
};

1470. 重新排列数组

https://leetcode.cn/problems/shuffle-the-array/

思路：

根据示例可以看出来数组是按照对半交叉进行重新组合的，只需要定义一个新的数组存储重新组合后的数组，两个指针分别指向0 和中间元素，不断添加两个指针指向的元素即可

class Solution {
public:
    vector<int> shuffle(vector<int>& nums, int n) {
    vector<int> res;
    int i=0,j=n;
    while(i<n &&j<=2*n-1){
        res.push_back(nums[i]);
        res.push_back(nums[j]);
        i++;
        j++;
    }
    return res;
    }
};

946. 验证栈序列

https://leetcode.cn/problems/validate-stack-sequences/

思路:

遍历pushed数组将其中的值依次进栈
每将pushed的元素入栈之后，如果栈不为空且栈顶元素和poped数组的当前元素相等，则栈顶元素出栈

class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        stack<int> s;
        int j=0;//指向poped的位置指针
        for(int i=0;i<pushed.size();i++){
            s.emplace(pushed[i]);
            while(!s.empty() && s.top()==popped[j]){
                s.pop();
                j++;
            }
        }
       return s.empty();
    }
};

总结

8月是在家的一个月，导师没有催我干活，也就开始刷题。也是在leetcode上成功打卡一个月的月份。也打了几场周赛（过路打卡的水平）

其中有些题目完全没有思路，有些看答案也不是很理解，先放在这里吧，等后面有空在研究研究。

在9月份期待还能够有时间坚持去刷题，在后续导师安排的qt项目上能够高质量完成界面，代码逻辑的设计，争取能够早点，高质量完成项目!