1. Toy模板网首页
  2. > Toy博客

【Leetcode Sheet】Weekly Practice 3

9月前 作者：MorleyOlsen 分类：Toy博客 阅读(46) 违法举报

这篇具有很好参考价值的文章主要介绍了【Leetcode Sheet】Weekly Practice 3。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

Leetcode Test

833 字符串中的查找与替换(8.15)

你会得到一个字符串 s (索引从 0 开始)，你必须对它执行 k 个替换操作。替换操作以三个长度均为 k 的并行数组给出：indices, sources, targets。

要完成第 i 个替换操作:

  1. 检查 子字符串 sources[i] 是否出现在 原字符串 s 的索引 indices[i] 处。
  2. 如果没有出现， 什么也不做 。
  3. 如果出现，则用 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】

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模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 代码随想录Leetcode70. 爬楼梯

    代码随想录Leetcode70. 爬楼梯

            空间复杂度为O(N)，如果想要优化空间复杂度，则只用三个变量进行状态转移也可以，参考 代码随想录 Leetcode509. 斐波那契数-CSDN博客

    2024年02月19日
    浏览(82)
  • 代码随想录Leetcode 343. 整数拆分

    代码随想录Leetcode 343. 整数拆分

            dp[i]表示i所能拆分的最大乘积，则dp[i] 与dp[i - 1]的递推公式是：                 max( 1~n * dp[n ~ 1])

    2024年02月21日
    浏览(85)
  • 代码随想录 Leetcode763. 划分字母区间

    代码随想录 Leetcode763. 划分字母区间

    2024年02月21日
    浏览(121)
  • 代码随想录 LeetCode数组篇 二分查找

    代码随想录 LeetCode数组篇 二分查找

    # （简单）704. 二分查找 题目链接 代码随想录 - 二分查找思路 二分查找，思路很简单，但是在while循环left和right的比较是写=还是，还有right=mid还是right=mid-1容易混淆 需要想清楚对区间的定义，是[left,right]，还是[left,right) （版本一，左闭右闭版本） （版本二，左闭右开） 题目

    2024年02月02日
    浏览(57)
  • 代码随想录 Leetcode18. 四数之和

    代码随想录 Leetcode18. 四数之和

            不行了，今天做了太多n数之和要吐了，太恶心了，一堆剪枝，去重太恶心人了。最后还是照着卡哥的改

    2024年01月17日
    浏览(94)
  • 代码随想录刷题第4天|LeetCode24、LeetCode19、LeetCode160、LeetCode142

    代码随想录刷题第4天|LeetCode24、LeetCode19、LeetCode160、LeetCode142

    1、LeetCode24 两两交换链表中的节点 题目链接：24、两两交换链表中的节点 要想清楚终止条件，cur每次指向要交换的两个节点的前一个节点，cur = cur-next-next; 若链表元素个数为偶数 , 则最后时刻 cur-next = NULL； 若链表元素个数为奇数，则最后时刻 cur-next-next = NULL; 最后要返回

    2024年02月05日
    浏览(47)
  • 【代码随想录 | Leetcode | 第四天】数组 | 螺旋矩阵 | 59

    【代码随想录 | Leetcode | 第四天】数组 | 螺旋矩阵 | 59

    欢迎来到小K的Leetcode|代码随想录|专题化专栏，今天将为大家带来螺旋矩阵的分享 ✨ 给你一个正整数 n ，生成一个包含 1 到 n 2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。 示例 1： 示例 2： 提示： 思路： 本类型题目其实都不涉及什么算法，就是模拟

    2024年02月16日
    浏览(49)
  • 代码随想录 Leetcode142. 环形链表 II

    代码随想录 Leetcode142. 环形链表 II

            双指针解决百分之99的链表题

    2024年01月19日
    浏览(46)

  • 【代码随想录－Leetcode第二题：27.移除元素】

    给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。 不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。 元素的顺序可以改变。你不需要考虑数组中超出新长度后面的 样例：示例 1： 解释：函数

    2024年02月14日
    浏览(51)

  • 代码随想录第一天 | LeetCode704.二分查找，LeetCode 27.移除元素

    数组理论基础要点： 数组也是数据结构的一种， 是存放在连续内存空间上的相同类型数据的集合。 数组注意点： 数组下标都是从0开始的。 数组内存空间的地址是连续的。 因为上述两点， 数组的在内存空间的地址是连续的，所以我们在删除或者增添元素的时候，就难免要

    2024年02月08日
    浏览(50)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包