学校网站建设招标文件,wordpress js代码编辑器插件,ps网站首页设计,加强网站编辑队伍建设Leetcode Test
833 字符串中的查找与替换(8.15)
你会得到一个字符串 s (索引从 0 开始)#xff0c;你必须对它执行 k 个替换操作。替换操作以三个长度均为 k 的并行数组给出#xff1a;indices, sources, targets。
要完成第 i 个替换操作:
检查 子字符串 sources[i] 是否…Leetcode Test
833 字符串中的查找与替换(8.15)
你会得到一个字符串 s (索引从 0 开始)你必须对它执行 k 个替换操作。替换操作以三个长度均为 k 的并行数组给出indices, sources, targets。
要完成第 i 个替换操作:
检查 子字符串 sources[i] 是否出现在 原字符串 s 的索引 indices[i] 处。如果没有出现 什么也不做 。如果出现则用 targets[i] 替换 该子字符串。
例如如果 s abcd indices[i] 0 , sources[i] ab targets[i] eee 那么替换的结果将是 eeecd 。
所有替换操作必须 同时 发生这意味着替换操作不应该影响彼此的索引。测试用例保证元素间不会重叠 。
例如一个 s abc indices [0,1] sources [abbc] 的测试用例将不会生成因为 ab 和 bc 替换重叠。
在对 s 执行所有替换操作后返回 *结果字符串 。*
子字符串 是字符串中连续的字符序列。
提示
1 s.length 1000k indices.length sources.length targets.length1 k 1000 indices[i] s.length1 sources[i].length, targets[i].length 50s 仅由小写英文字母组成sources[i] 和 targets[i] 仅由小写英文字母组成
【随手题解】833. 字符串中的查找与替换 - 力扣LeetCode
char * findReplaceString(char * s, int* indices, int indicesSize, char ** sources, int sourcesSize, char ** targets, int targetsSize){int lenindicesSize;int *indicemark(int*)malloc(sizeof(int)*len);for(int i0;ilen;i){indicemark[i]0;}for(int i0;ilen;i){ //handle current indicesint nstrlen(sources[i]); //len of string sources[i]int cnt0; //count for charbool flag1;for(int jindices[i];jindices[i]n;j){if(s[j]!sources[i][cnt]){flag0;break;}cnt;}if(flag1){ //match successindicemark[i]1;}}int sizestrlen(s);for(int i0;ilen;i){sizestrlen(targets[i]);}char *result(char*)malloc(sizeof(char)*(size));int left0,right0;while(leftstrlen(s)){int check0,number-1;for(int i0;ilen;i){if(leftindices[i] indicemark[i]1){ //如果left是indice的序号且已经确定需要替换check1;numberi;//标记是indices中的哪一个序号break;}}if(check0){//not targetresult[right]s[left];}else{//targetint templenstrlen(targets[number]);for(int k0;ktemplen;k){result[right]targets[number][k];}leftstrlen(sources[number]);number-1;}}result[right]\0;return result;
}【官方题解】
1按照下标排序 模拟我的代码只是没有排序indices[]…吧
static int cmp(const void *a, const void *b) {return ((int *)a)[1] - ((int *)b)[1];
}
//正常的cmp排序写法char * findReplaceString(char * s, int* indices, int indicesSize, char ** sources, int sourcesSize, char ** targets, int targetsSize) {int n strlen(s), m indicesSize;//重新定义长度精简变量int ops[m][2]; //标记indice对应的字符串序号和本身的序号int sourcesLen[sourcesSize];for (int i 0; i m; i) {ops[i][0] i;ops[i][1] indices[i];}for (int i 0; i sourcesSize; i) {sourcesLen[i] strlen(sources[i]); //初始化sourceslen数组}qsort(ops, m, sizeof(ops[0]), cmp); //排序ops中的对应字符串序号char *ans (char *)calloc(1024, sizeof(char));int pt 0, pos 0;for (int i 0; i n;) {while (pt m indices[ops[pt][0]] i) {pt;}bool succeed false;while (pt m indices[ops[pt][0]] i) {if (strncmp(s i, sources[ops[pt][0]], sourcesLen[ops[pt][0]]) 0) {succeed true;break;}pt;}if (succeed) {pos sprintf(ans pos, %s, targets[ops[pt][0]]);i sourcesLen[ops[pt][0]];} else {ans[pos] s[i];i;}}return ans;
}2哈希表 模拟用纯c写哈希表就是去世…
typedef struct {int key;struct ListNode *list;UT_hash_handle hh;
} HashItem;struct ListNode *creatListNode(int val) {struct ListNode *obj (struct ListNode *)malloc(sizeof(struct ListNode));obj-val val;obj-next NULL;return obj;
}void freeLinkList(struct ListNode *list) {while (list) {struct ListNode *curr list;list list-next;free(curr);}
}HashItem *hashFindItem(HashItem **obj, int key) {HashItem *pEntry NULL;HASH_FIND_INT(*obj, key, pEntry);return pEntry;
}bool hashAddItem(HashItem **obj, int key, int val) {HashItem *pEntry hashFindItem(obj, key);if (pEntry) {struct ListNode *node creatListNode(val);node-next pEntry-list;pEntry-list node;} else {HashItem *pEntry (HashItem *)malloc(sizeof(HashItem));pEntry-key key;pEntry-list creatListNode(val);HASH_ADD_INT(*obj, key, pEntry);}return true;
}void hashFree(HashItem **obj) {HashItem *curr NULL, *tmp NULL;HASH_ITER(hh, *obj, curr, tmp) {HASH_DEL(*obj, curr);freeLinkList(curr-list);free(curr);}
}char * findReplaceString(char * s, int* indices, int indicesSize, char ** sources, int sourcesSize, char ** targets, int targetsSize) {int n strlen(s), m indicesSize;HashItem *ops NULL;for (int i 0; i m; i) {hashAddItem(ops, indices[i], i);}char *ans (char *)calloc(n * 50 1, sizeof(char));int pos 0;for (int i 0; i n;) {bool succeed false;HashItem *pEntry hashFindItem(ops, i);if (pEntry) {for (struct ListNode *node pEntry-list; node; node node-next) {int pt node-val;if (!strncmp(s i, sources[pt], strlen(sources[pt]))) {succeed true;pos sprintf(ans pos, %s, targets[pt]);i strlen(sources[pt]);break;}}}if (!succeed) {ans[pos] s[i];}}hashFree(ops);return ans;
}2682 找出转圈游戏输家(8.16)
n 个朋友在玩游戏。这些朋友坐成一个圈按 顺时针方向 从 1 到 n 编号。从第 i 个朋友的位置开始顺时针移动 1 步会到达第 (i 1) 个朋友的位置1 i n而从第 n 个朋友的位置开始顺时针移动 1 步会回到第 1 个朋友的位置。
游戏规则如下
第 1 个朋友接球。
接着第 1 个朋友将球传给距离他顺时针方向 k 步的朋友。然后接球的朋友应该把球传给距离他顺时针方向 2 * k 步的朋友。接着接球的朋友应该把球传给距离他顺时针方向 3 * k 步的朋友以此类推。
换句话说在第 i 轮中持有球的那位朋友需要将球传递给距离他顺时针方向 i * k 步的朋友。
当某个朋友第 2 次接到球时游戏结束。
在整场游戏中没有接到过球的朋友是 输家 。
给你参与游戏的朋友数量 n 和一个整数 k 请按升序排列返回包含所有输家编号的数组 answer 作为答案。
提示
1 k n 50
【直接模拟】
/*** Note: The returned array must be malloced, assume caller calls free().*/int* circularGameLosers(int n, int k, int* returnSize){int *answer(int*)malloc(sizeof(int)*n);int *fetch(int*)malloc(sizeof(int)*n);for(int i0;in;i){fetch[i]0; //initialize for catching ballsanswer[i]0;}int cnt0,place0,count1;while(1){fetch[place]1; //标记接球if(fetch[place]1){ //接到第二次球break;}place(placecount*k)%n; //传给下一个人count;}for(int i0;in;i){if(fetch[i]0){ //如果是输家answer[cnt]i1;}}*returnSizecnt;return answer;
}1444 切皮萨的方案数(8.17)
给你一个 rows x cols 大小的矩形披萨和一个整数 k 矩形包含两种字符 A 表示苹果和 . 表示空白格子。你需要切披萨 k-1 次得到 k 块披萨并送给别人。
切披萨的每一刀先要选择是向垂直还是水平方向切再在矩形的边界上选一个切的位置将披萨一分为二。如果垂直地切披萨那么需要把左边的部分送给一个人如果水平地切那么需要把上面的部分送给一个人。在切完最后一刀后需要把剩下来的一块送给最后一个人。
请你返回确保每一块披萨包含 至少 一个苹果的切披萨方案数。由于答案可能是个很大的数字请你返回它对 10^9 7 取余的结果。
提示
1 rows, cols 50rows pizza.lengthcols pizza[i].length1 k 10pizza 只包含字符 A 和 . 。
【动态规划方程】 d p [ k ] [ i ] [ j ] ∑ ( d p [ k − 1 ] [ i i ] [ j ] ) ∑ ( d p [ k − 1 ] [ i ] [ j j ] ) dp[k][i][j]∑(dp[k-1][ii][j])∑(dp[k-1][i][jj]) dp[k][i][j]∑(dp[k−1][ii][j])∑(dp[k−1][i][jj])
$$ apples[i][j](pizza[i][j]A)apples[i1][j]apples[i][j1]−apples[i1][j1]dp[k][i][j] i ′
i1 ∑ m
(dp[k−1][i ′
][j]) j ′
j1 ∑ n
(dp[k−1][i][j ′
]) $$
int ways(char ** pizza, int pizzaSize, int k){int mod1e97,mpizzaSize,nstrlen(pizza[0]);int apples[m1][n1]; //记录矩形苹果个数int dp[k1][m1][n1]; //记录dp迭代memset(apples,0,sizeof(apples));memset(dp,0,sizeof(dp));// preprocessingfor(int im-1;i0;i--){for(int jn-1;j0;j--){apples[i][j](pizza[i][j] A)apples[i][j1]apples[i1][j]-apples[i1][j1];// 坐标右下方矩形中的苹果数量dp[1][i][j]apples[i][j]0 ? 1 : 0;//当前坐标右下方的披萨是否符合题目条件}}for(int ki2;kik;ki){ //ki切割次数一共k-1次for(int i0;im;i){ for(int j0;jn;j){ //遍历矩阵dp[ki][i][j]0; //初始化第i次切割//horizontalfor(int i2i1;i2m;i2){ //遍历水平切割if(apples[i][j]apples[i2][j]){ //如果i坐标的右下苹果数【严格大于】i2坐标的dp[ki][i][j]dp[ki-1][i2][j]; //dp自增i2对应值dp[ki][i][j]dp[ki][i][j]%mod; //取余}}//verticalfor(int j2j1;j2n;j2){ //遍历垂直切割if(apples[i][j]apples[i][j2]){ //如果j坐标的右下苹果数【严格大于】j2坐标的dp[ki][i][j]dp[ki-1][i][j2]; //dp自增j2对应值dp[ki][i][j]dp[ki][i][j]%mod; //取余}}}}}return dp[k][0][0]; //返回【00】的结果
}1388 3n块披萨(8.18)
给你一个披萨它由 3n 块不同大小的部分组成现在你和你的朋友们需要按照如下规则来分披萨
你挑选 任意 一块披萨。Alice 将会挑选你所选择的披萨逆时针方向的下一块披萨。Bob 将会挑选你所选择的披萨顺时针方向的下一块披萨。重复上述过程直到没有披萨剩下。
每一块披萨的大小按顺时针方向由循环数组 slices 表示。
请你返回你可以获得的披萨大小总和的最大值。
提示
1 slices.length 500slices.length % 3 01 slices[i] 1000
【状态转移方程】 d p [ i ] [ j ] m a x ( d p [ i − 2 ] [ j − 1 ] s l i c e s [ i ] , d p [ i − 1 ] [ j ] ) dp[i][j]max(dp[i−2][j−1]slices[i],dp[i−1][j]) dp[i][j]max(dp[i−2][j−1]slices[i],dp[i−1][j]) 给一个长度为3n的环状序列你可以在其中选择n个数并且任意两个数不能相邻求这n个数的最大值
环状序列——2次dp第一次去掉第一个数第二次去掉最后一个数
int max(int a,int b){return (ab ? a : b);
}int handle(int* slices, int slicesSize){int nnslicesSize; int n(nn1)/3; //需要间隔取的数目int dp[nn][n1]; //dp数组表示在前i个数中选择了j个不相邻的数的最大和//(最大和)//初始化for(int i0;inn;i){for(int j0;jn;j){ dp[i][j]INT_MIN; //赋值为-∞}}dp[0][0]0; //从编号0之前选择0个数dp[0][1]slices[0]; //从编号0之前选择1个数dp[1][0]0; //从编号1之前选择0个数dp[1][1]fmax(slices[0],slices[1]); //从编号1之前选择1个数0号和1号的最大值//迭代for(int i2;inn;i){ dp[i][0]0; //j0时始终赋值为0for(int j1;jn;j){ //从需要取1个数开始遍历dp[i][j]max(dp[i-1][j],slices[i]dp[i-2][j-1]);//状态转移方程结果2个情况//最终取两个情况的最大值作为最大和//情况1选择了第i个数那么第i-1不可以被选择需要在前i-2个里面选择j-1个//dp[i][j]slices[i]dp[i-2][j-1]即最大和当前数字前一个最大和//情况2没选择第i个数那么需要在前i-1个里面选择j个//dp[i][j]dp[i-1][j]}}return dp[nn-1][n];
}int maxSizeSlices(int* slices, int slicesSize){//给一个长度为3n的环状序列你可以在其中选择n个数并且任意两个数不能相邻求这n个数的最大值。//环状序列——2次dp第一次去掉第一个数第二次去掉最后一个数int nnslicesSize;return fmax(handle(slices1,nn-1),handle(slices,nn-1));
}2235 两整数相加(8.19) 严重怀疑官方在安慰人 it appears to be convincing we are not that stupid but… it is humiliating. 给你两个整数 num1 和 num2返回这两个整数的和。
int sum(int num1, int num2){return(num1 num2);
}2236 判断根结点是否等于子结点之和(8.20) a humiliating problem, too 给你一个 二叉树 的根结点 root该二叉树由恰好 3 个结点组成根结点、左子结点和右子结点。
如果根结点值等于两个子结点值之和返回 true 否则返回 false 。
提示
树只包含根结点、左子结点和右子结点-100 Node.val 100
/*** Definition for a binary tree node.* struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* };*/bool checkTree(struct TreeNode* root){return (root-val (root-left-val root-right-val));
}2337 移动片段得到字符串(8.21)
给你两个字符串 start 和 target 长度均为 n 。每个字符串 仅 由字符 L、R 和 _ 组成其中
字符 L 和 R 表示片段其中片段 L 只有在其左侧直接存在一个 空位 时才能向 左 移动而片段 R 只有在其右侧直接存在一个 空位 时才能向 右 移动。字符 _ 表示可以被 任意 L 或 R 片段占据的空位。
如果在移动字符串 start 中的片段任意次之后可以得到字符串 target 返回 true 否则返回 false 。
提示
n start.length target.length1 n 105start 和 target 由字符 L、R 和 _ 组成
【双指针——i和j】
bool canChange(char * start, char * target){int nstrlen(start);int i0,j0;while(in jn){//跳过所有_while(in start[i]_){i;}while(jn target[j]_){j;}//当前字符不匹配if(start[i]!target[j]){return 0;}//如果当前字符是L且i小于j 或 当前字符是R且i大于jif((start[i]L ij) || (start[i]R ij)){return 0;}//移动至下一个位置i;j;}//j走到头了导致while结束while(in){if(start[i]!_){ //出现额外的字符_return 0;}i;}//i走到头了导致while结束while(jn){if(target[j]!_){ 出现额外的字符_return 0;}j;}return 1;
}【灵神c】
class Solution {
public:bool canChange(string start, string target) {auto s start, t target;//L和R无法互相穿透去掉_后应该相同s.erase(remove(s.begin(), s.end(), _), s.end());t.erase(remove(t.begin(), t.end(), _), t.end());if (s ! t) return false;//双指针遍历for (int i 0, j 0; i start.length(); i) {//移动到第一个字母if (start[i] _) continue;while (target[j] _)j;//如果ij则一定匹配相对位置//如果L且ij不能移动//如果R且ij不能移动if (i ! j (start[i] L) (i j))return false;j;//跳过当前字母进入下一次循环}return true;}
};
