涉密项目单位网站建设流程,wordpress主题破解下载,正规网站建设价格费用,怎么做装修网站Leetcode Test
1670 设计前中后队列(11.28)
请你设计一个队列#xff0c;支持在前#xff0c;中#xff0c;后三个位置的 push 和 pop 操作。
请你完成 FrontMiddleBack 类#xff1a;
FrontMiddleBack() 初始化队列。void pushFront(int val) 将 val 添加到队列的 最前…Leetcode Test
1670 设计前中后队列(11.28)
请你设计一个队列支持在前中后三个位置的 push 和 pop 操作。
请你完成 FrontMiddleBack 类
FrontMiddleBack() 初始化队列。void pushFront(int val) 将 val 添加到队列的 最前面 。void pushMiddle(int val) 将 val 添加到队列的 正中间 。void pushBack(int val) 将 val 添加到队里的 最后面 。int popFront() 将 最前面 的元素从队列中删除并返回值如果删除之前队列为空那么返回 -1 。int popMiddle() 将 正中间 的元素从队列中删除并返回值如果删除之前队列为空那么返回 -1 。int popBack() 将 最后面 的元素从队列中删除并返回值如果删除之前队列为空那么返回 -1 。
请注意当有 两个 中间位置的时候选择靠前面的位置进行操作。比方说
将 6 添加到 [1, 2, 3, 4, 5] 的中间位置结果数组为 [1, 2, **6**, 3, 4, 5] 。从 [1, 2, **3**, 4, 5, 6] 的中间位置弹出元素返回 3 数组变为 [1, 2, 4, 5, 6] 。
提示
1 val 109最多调用 1000 次 pushFront pushMiddle pushBack popFront popMiddle 和 popBack 。
【双端队列】1670. 设计前中后队列 - 力扣LeetCode
class FrontMiddleBackQueue {dequeint left;dequeint right;void balance(){if(left.size()right.size()){//move the last of left to the head of rightright.push_front(left.back());left.pop_back();}else if(right.size()left.size()1){//move the head of right to the last of leftleft.push_back(right.front());right.pop_front();}}
public://初始化FrontMiddleBackQueue() {//}//val加到队列最前面void pushFront(int val) {left.push_front(val);balance();}//val加到队列正中间void pushMiddle(int val) {if(left.size()right.size()){left.push_back(val);}else{right.push_front(val);}balance();}//val加到队列最后面void pushBack(int val) {right.push_back(val);balance();}//返回最前面的valueint popFront() {if(right.empty()){return -1;}int val;if(left.empty()){valright.front();right.pop_front();}else{valleft.front();left.pop_front();}balance();return val;}//返回正中间的valueint popMiddle() {if(right.empty()){return -1;}int val;if(left.size()right.size()){valleft.back();left.pop_back();}else{valright.front();right.pop_front();}balance();return val;}//返回最后面的valueint popBack() {if(right.empty()){return -1;}int valright.back();right.pop_back();balance();return val;}
};/*** Your FrontMiddleBackQueue object will be instantiated and called as such:* FrontMiddleBackQueue* obj new FrontMiddleBackQueue();* obj-pushFront(val);* obj-pushMiddle(val);* obj-pushBack(val);* int param_4 obj-popFront();* int param_5 obj-popMiddle();* int param_6 obj-popBack();*/2336 无限集中的最小数字(11.29)
现有一个包含所有正整数的集合 [1, 2, 3, 4, 5, ...] 。
实现 SmallestInfiniteSet 类
SmallestInfiniteSet() 初始化 SmallestInfiniteSet 对象以包含 所有 正整数。int popSmallest() 移除 并返回该无限集中的最小整数。void addBack(int num) 如果正整数 num 不 存在于无限集中则将一个 num 添加 到该无限集中。
提示
1 num 1000最多调用 popSmallest 和 addBack 方法 共计 1000 次
【有序集合】
class SmallestInfiniteSet {int thres1;setint s;
public://初始化SmallestInfiniteSet() { }//移除 并返回该无限集中的最小整数。int popSmallest() {//如果比thres小的单独值不存在则弹出thresif(s.empty()){int tthres;thres;return t;}//否则记录set中的起始值并弹出else{int t*s.begin();s.erase(s.begin());return t;}}//如果正整数num不存在于infinite则添加void addBack(int num) {if(numthres){//如果num小于最小阈值则添加num否则表示num一定在阈值后面的集合中s.insert(num);}}
};/*** Your SmallestInfiniteSet object will be instantiated and called as such:* SmallestInfiniteSet* obj new SmallestInfiniteSet();* int param_1 obj-popSmallest();* obj-addBack(num);*/1657 确定两个字符串是否接近(11.30)
如果可以使用以下操作从一个字符串得到另一个字符串则认为两个字符串 接近 操作 1交换任意两个现有字符。 例如a**b**cd**e** - a**e**cd**b** 操作 2将一个现有字符的每次出现转换为另一个现有字符并对另一个字符执行相同的操作。 例如**aa**c**abb** - **bb**c**baa**所有 a 转化为 b 而所有的 b 转换为 a
你可以根据需要对任意一个字符串多次使用这两种操作。
给你两个字符串word1 和 word2 。如果 word1 和 word2 接近 就返回 true 否则返回 false 。
提示
1 word1.length, word2.length 105word1 和 word2 仅包含小写英文字母
【hash】
int cmp(void *a,void *b){return *(int*)a-*(int*)b;
}bool closeStrings(char* word1, char* word2) {int n1strlen(word1),n2strlen(word2);if(n1!n2) return 0;int *hash1(int*)malloc(sizeof(int)*26);int *hash2(int*)malloc(sizeof(int)*26);for(int i0;i26;i){hash1[i]0;}for(int i0;i26;i){hash2[i]0;}//hash countingfor(int i0;in1;i){hash1[word1[i]-a];}for(int i0;in2;i){hash2[word2[i]-a];}//existing words judgefor(int i0;i26;i){if(hash1[i]!0 hash2[i]0){return 0;}else if(hash1[i]0 hash2[i]!0){return 0;}}//sort arrayqsort(hash1,26,sizeof(int),cmp);qsort(hash2,26,sizeof(int),cmp);//comparefor(int i0;i26;i){if(hash1[i]!hash2[i]){return 0;}}return 1;
}2661 找出叠涂元素(12.1)
给你一个下标从 0 开始的整数数组 arr 和一个 m x n 的整数 矩阵 mat 。arr 和 mat 都包含范围 [1m * n] 内的 所有 整数。
从下标 0 开始遍历 arr 中的每个下标 i 并将包含整数 arr[i] 的 mat 单元格涂色。
请你找出 arr 中在 mat 的某一行或某一列上都被涂色且下标最小的元素并返回其下标 i 。
提示
m mat.lengthn mat[i].lengtharr.length m * n1 m, n 1051 m * n 1051 arr[i], mat[r][c] m * narr 中的所有整数 互不相同mat 中的所有整数 互不相同
【hash counting】
int firstCompleteIndex(int* arr, int arrSize, int** mat, int matSize, int* matColSize){int lenarrSize,mmatSize,nmatColSize[0];int *row(int*)malloc(sizeof(int)*(len1));int *col(int*)malloc(sizeof(int)*(len1));//record the row and col of each figurefor(int i0;ilen1;i){row[i]-1;col[i]-1;}int *checkrow(int*)malloc(sizeof(int)*m);int *checkcol(int*)malloc(sizeof(int)*n);for(int i0;im;i){checkrow[i]n;}for(int i0;in;i){checkcol[i]m;}//每行有n个数每列有m个数//hash record the rowcol of each figurefor(int i0;im;i){for(int j0;jn;j){int figmat[i][j];row[fig]i;col[fig]j;}}int ret-1;for(int i0;ilen;i){int temparr[i];//temps position should add to hashint temprowrow[temp];int tempcolcol[temp];checkrow[temprow]--;checkcol[tempcol]--;if(checkrow[temprow]0 || checkcol[tempcol]0){reti;break;}}return ret;
}1094 拼车(12.2)
车上最初有 capacity 个空座位。车 只能 向一个方向行驶也就是说不允许掉头或改变方向
给定整数 capacity 和一个数组 trips , trip[i] [numPassengersi, fromi, toi] 表示第 i 次旅行有 numPassengersi 乘客接他们和放他们的位置分别是 fromi 和 toi 。这些位置是从汽车的初始位置向东的公里数。
当且仅当你可以在所有给定的行程中接送所有乘客时返回 true否则请返回 false。
提示
1 trips.length 1000trips[i].length 31 numPassengersi 1000 fromi toi 10001 capacity 105
【hash计数】
bool carPooling(int** trips, int tripsSize, int* tripsColSize, int capacity) {//capacity个空座位//trips[i] 0旅客数量 1上车位置 2下车位置int *check(int*)malloc(sizeof(int)*1001);for(int i0;i1001;i){check[i]0;}bool flag1;for(int i0;itripsSize;i){int starttrips[i][1];int endtrips[i][2];int numtrips[i][0];while(startend){check[start]num;if(check[start]capacity){flag0;break;}start;}if(flag0){break;}}return flag;
}【差分】1094. 拼车 - 力扣LeetCode
bool carPooling(int **trips, int tripsSize, int *tripsColSize, int capacity) {//找到最大的time为开辟数组做准备int toMax 0;for (int i 0; i tripsSize; i) {if (toMax trips[i][2]) {toMax trips[i][2];}}//开辟数组并初始化diff的值int *diff malloc(sizeof(int) * (toMax 1));memset(diff, 0, sizeof(int) * (toMax 1));for (int i 0; i tripsSize; i) {diff[trips[i][1]] trips[i][0];diff[trips[i][2]] - trips[i][0];}int count 0;for (int i 0; i toMax; i) {count diff[i];if (count capacity) {return false;}}free(diff);return true;
}1423 可获得的最大点数(12.3)
几张卡牌 排成一行每张卡牌都有一个对应的点数。点数由整数数组 cardPoints 给出。
每次行动你可以从行的开头或者末尾拿一张卡牌最终你必须正好拿 k 张卡牌。
你的点数就是你拿到手中的所有卡牌的点数之和。
给你一个整数数组 cardPoints 和整数 k请你返回可以获得的最大点数。
提示
1 cardPoints.length 10^51 cardPoints[i] 10^41 k cardPoints.length
【滑动窗口】滑动不需要的格子总量 - 不需要的
int maxScore(int* cardPoints, int cardPointsSize, int k) {int ncardPointsSize,sum0,windown-k;//初始化取最左侧的k个数字作为窗口的sumfor(int i0;iwindow;i){sumcardPoints[i];}int tempsum,minsumsum;for(int iwindow;in;i){//增加一个右侧的值减去一个左侧的值sumcardPoints[i]-cardPoints[i-window];minsumfmin(minsum,sum);tempcardPoints[i];}return temp-minsum;
}【滑动窗口】滑动需要的格子直接计算需要的
int maxScore(int* cardPoints, int cardPointsSize, int k) {//start or end, pick a card, total kint ncardPointsSize,maxsum0;//初始化滑左侧k个for(int i0;ik;i){maxsumcardPoints[i];}//每次从右侧滑动最末尾的一个进来然后从左侧弹出一个走int newsummaxsum;for(int i0;ik;i){newsumcardPoints[n-i-1];newsum-cardPoints[k-i-1];maxsumfmax(maxsum,newsum);}return maxsum;
}1038 从二叉搜索树到更大和树(12.4)
给定一个二叉搜索树 root (BST)请将它的每个节点的值替换成树中大于或者等于该节点值的所有节点值之和。
提醒一下 二叉搜索树 满足下列约束条件
节点的左子树仅包含键 小于 节点键的节点。节点的右子树仅包含键 大于 节点键的节点。左右子树也必须是二叉搜索树。
提示
树中的节点数在 [1, 100] 范围内。0 Node.val 100树中的所有值均 不重复 。
**注意**该题目与 538: https://leetcode-cn.com/problems/convert-bst-to-greater-tree/ 相同
【反序中序遍历】
/*** Definition for a binary tree node.* struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* };*/
int sum;struct TreeNode* dfs(struct TreeNode* root){if(root){dfs(root-right);sumroot-val;root-valsum;dfs(root-left);}return root;
}struct TreeNode* bstToGst(struct TreeNode* root) {sum0;dfs(root);return root;
}【Morris遍历】
struct TreeNode* getSuccessor(struct TreeNode* node) {struct TreeNode* succ node-right;while (succ-left ! NULL succ-left ! node) {succ succ-left;}return succ;
}struct TreeNode* bstToGst(struct TreeNode* root) {int sum 0;struct TreeNode* node root;while (node ! NULL) {if (node-right NULL) {sum node-val;node-val sum;node node-left;} else {struct TreeNode* succ getSuccessor(node);if (succ-left NULL) {succ-left node;node node-right;} else {succ-left NULL;sum node-val;node-val sum;node node-left;}}}return root;
}
