文章目录
- 八月每日一题
- 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, ×tamp);
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项目上能够高质量完成界面，代码逻辑的设计，争取能够早点，高质量完成项目!