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 = ["ab","bc"]
的测试用例将不会生成,因为"ab"
和"bc"
替换重叠。
在对 s 执行所有替换操作后返回 *结果字符串 。*
子字符串 是字符串中连续的字符序列。
提示:
1 <= s.length <= 1000
k == indices.length == sources.length == targets.length
1 <= k <= 100
0 <= indices[i] < s.length
1 <= sources[i].length, targets[i].length <= 50
-
s
仅由小写英文字母组成 -
sources[i]
和targets[i]
仅由小写英文字母组成
【随手题解】833. 字符串中的查找与替换 - 力扣(LeetCode)
char * findReplaceString(char * s, int* indices, int indicesSize, char ** sources, int sourcesSize, char ** targets, int targetsSize){
int len=indicesSize;
int *indicemark=(int*)malloc(sizeof(int)*len);
for(int i=0;i<len;i++){
indicemark[i]=0;
}
for(int i=0;i<len;i++){
//handle current indices
int n=strlen(sources[i]);
//len of string sources[i]
int cnt=0;
//count for char
bool flag=1;
for(int j=indices[i];j<indices[i]+n;j++){
if(s[j]!=sources[i][cnt]){
flag=0;
break;
}
cnt++;
}
if(flag==1){
//match success
indicemark[i]=1;
}
}
int size=strlen(s);
for(int i=0;i<len;i++){
size+=strlen(targets[i]);
}
char *result=(char*)malloc(sizeof(char)*(size));
int left=0,right=0;
while(left<=strlen(s)){
int check=0,number=-1;
for(int i=0;i<len;i++){
if(left==indices[i] && indicemark[i]==1){
//如果left是indice的序号且已经确定需要替换
check=1;
number=i;
//标记是indices中的哪一个序号
break;
}
}
if(check==0){
//not target
result[right++]=s[left++];
}
else{
//target
int templen=strlen(targets[number]);
for(int k=0;k<templen;k++){
result[right++]=targets[number][k];
}
left+=strlen(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 i=0;i<n;i++){
fetch[i]=0; //initialize for catching balls
answer[i]=0;
}
int cnt=0,place=0,count=1;
while(1){
fetch[place]+=1; //标记接球
if(fetch[place]>1){ //接到第二次球
break;
}
place=(place+count*k)%n; //传给下一个人
count++;
}
for(int i=0;i<n;i++){
if(fetch[i]==0){ //如果是输家
answer[cnt++]=i+1;
}
}
*returnSize=cnt;
return answer;
}
1444 切皮萨的方案数(8.17)
给你一个 rows x cols
大小的矩形披萨和一个整数 k
,矩形包含两种字符: 'A'
(表示苹果)和 '.'
(表示空白格子)。你需要切披萨 k-1
次,得到 k
块披萨并送给别人。
切披萨的每一刀,先要选择是向垂直还是水平方向切,再在矩形的边界上选一个切的位置,将披萨一分为二。如果垂直地切披萨,那么需要把左边的部分送给一个人,如果水平地切,那么需要把上面的部分送给一个人。在切完最后一刀后,需要把剩下来的一块送给最后一个人。
请你返回确保每一块披萨包含 至少 一个苹果的切披萨方案数。由于答案可能是个很大的数字,请你返回它对 10^9 + 7 取余的结果。
提示:
1 <= rows, cols <= 50
rows == pizza.length
cols == pizza[i].length
1 <= k <= 10
-
pizza
只包含字符'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[i+1][j]+apples[i][j+1]−apples[i+1][j+1]dp[k][i][j]=
i
′
=i+1
∑
m
(dp[k−1][i
′
][j])+
j
′
=j+1
∑
n
(dp[k−1][i][j
′
])
$$
int ways(char ** pizza, int pizzaSize, int k){
int mod=1e9+7,m=pizzaSize,n=strlen(pizza[0]);
int apples[m+1][n+1]; //记录矩形苹果个数
int dp[k+1][m+1][n+1]; //记录dp迭代
memset(apples,0,sizeof(apples));
memset(dp,0,sizeof(dp));
// preprocessing
for(int i=m-1;i>=0;i--){
for(int j=n-1;j>=0;j--){
apples[i][j]=(pizza[i][j] == 'A')+apples[i][j+1]+apples[i+1][j]-apples[i+1][j+1];
// 坐标右下方矩形中的苹果数量
dp[1][i][j]=apples[i][j]>0 ? 1 : 0;
//当前坐标右下方的披萨,是否符合题目条件
}
}
for(int ki=2;ki<=k;ki++){ //ki,切割次数,一共k-1次
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){ //遍历矩阵
dp[ki][i][j]=0; //初始化第i次切割
//horizontal
for(int i2=i+1;i2<m;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; //取余
}
}
//vertical
for(int j2=j+1;j2<n;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]; //返回【0,0】的结果
}
1388 3n块披萨(8.18)
给你一个披萨,它由 3n 块不同大小的部分组成,现在你和你的朋友们需要按照如下规则来分披萨:
- 你挑选 任意 一块披萨。
- Alice 将会挑选你所选择的披萨逆时针方向的下一块披萨。
- Bob 将会挑选你所选择的披萨顺时针方向的下一块披萨。
- 重复上述过程直到没有披萨剩下。
每一块披萨的大小按顺时针方向由循环数组 slices
表示。
请你返回你可以获得的披萨大小总和的最大值。
提示:
1 <= slices.length <= 500
slices.length % 3 == 0
1 <= 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 (a>b ? a : b);
}
int handle(int* slices, int slicesSize){
int nn=slicesSize;
int n=(nn+1)/3; //需要间隔取的数目
int dp[nn][n+1]; //dp数组,表示在前i个数中选择了j个不相邻的数的最大和
//(最大和!!!!!!!!)
//初始化
for(int i=0;i<nn;i++){
for(int j=0;j<=n;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 i=2;i<nn;i++){
dp[i][0]=0; //j=0时,始终赋值为0
for(int j=1;j<=n;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 nn=slicesSize;
return fmax(handle(slices+1,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.length
1 <= n <= 105
-
start
和target
由字符'L'
、'R'
和'_'
组成
【双指针——i和j】文章来源:https://www.toymoban.com/news/detail-673676.html
bool canChange(char * start, char * target){
int n=strlen(start);
int i=0,j=0;
while(i<n && j<n){
//跳过所有'_'
while(i<n && start[i]=='_'){
i++;
}
while(j<n && target[j]=='_'){
j++;
}
//当前字符不匹配
if(start[i]!=target[j]){
return 0;
}
//如果当前字符是L且i小于j 或 当前字符是R且i大于j
if((start[i]=='L' && i<j) || (start[i]=='R' && i>j)){
return 0;
}
//移动至下一个位置
i++;
j++;
}
//j走到头了导致while结束
while(i<n){
if(start[i]!='_'){ //出现额外的字符'_'
return 0;
}
i++;
}
//i走到头了导致while结束
while(j<n){
if(target[j]!='_'){ 出现额外的字符'_'
return 0;
}
j++;
}
return 1;
}
【灵神c++】文章来源地址https://www.toymoban.com/news/detail-673676.html
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++;
//如果i==j,则一定匹配(相对位置)
//如果L且i<j,不能移动
//如果R且i>j,不能移动
if (i != j && (start[i] == 'L') == (i < j))
return false;
++j;//跳过当前字母,进入下一次循环
}
return true;
}
};
到了这里,关于【Leetcode Sheet】Weekly Practice 3的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!