【刷题】leetcode 1544.整理字符串

2024-02-27 19:04

本文主要是介绍【刷题】leetcode 1544.整理字符串,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

在这里插入图片描述

刷题

  • 1544.整理字符串
    • 思路一(模拟栈速解版)
    • 思路二 (原地算法巧解版)
    • 思路三(C++栈版)
  • Thanks♪(・ω・)ノ谢谢阅读!!!
  • 下一篇文章见!!!

1544.整理字符串

来看题目描述
在这里插入图片描述
我看到本题的第一想法是双指针法,但是我所构想的逻辑无法达到目的,具体来说我采用前后指针,依次前进,然后满足条件就跳过,这样就导致会忽略许多满足的结构,就让我十分头疼,调试了半天还是不行,甚至想要使用三指针,四指针…服啦!结果表明都是不行的。下面来一起看看正确解法吧

思路一(模拟栈速解版)

这个和括号匹配问题很像,把字符串依次入栈,然后满足条件的就一起消除,主要就用到栈的压栈操作和取栈顶操作。这样一 一匹配就能达到要求。来看图解:
在这里插入图片描述
按照栈的方法很快速的就解决了问题,所以选择真的大于努力,这个问题选择栈就能快速解决,要是使用多指针就深陷泥潭了,来看代码实现:

char* makeGood(char* s) {if (*s == '\0') return s;if (*(s + 1) == '\0') return s;int top = 0;// 使用栈的思想char* ret = (char*)malloc(sizeof(char) * 100);char* cur = s;ret[top] = ' ';//依次入栈 并检查是否与栈顶元素符合条件while (*cur != '\0') {if (abs(ret[top] - *cur) == abs('A' - 'a')) {ret[top] = '\0';top--;cur++;}else {top++;ret[top] = *cur;cur++;}}//切记数组结尾加入 ‘\0’ret[++top] = '\0';return ret + 1;
}

来看效果:
在这里插入图片描述
顺利通过!!! 大声欢呼:过啦!!!!!!!

思路二 (原地算法巧解版)

这个思路十分奇妙的一个算法,空间复杂度为O(1),可以说是非常非常牛了。
那具体是如何操作的呢???

  1. 首先定义双指针 i j 分别指向头和头的下一个位置。
  2. 设置循环,j 遍历到尾结束。
  3. 开始判断,如果不满足条件 (互不为大小写并且 i 不等于-1)则 s[++i] = s[ j++ ] (关键一步)否则 i–。
  4. 依次往复,就可以完成任务。

只看思路似乎迷迷糊糊,这是如何做到的???下面我们来图解一下:
在这里插入图片描述
我们来逐步分析:
首先为什么这样可以做到整理字符串?
该操作类似于原地删除,一旦符合条件,i-- j++ 直接把他们就跳过了,然后如果不满足条件,就将 j 指向的内容拷贝到 i 位置,
然后继续判断。这样就可以完成操作了。
其次是为什么要加入i == -1 ???
因为会遇到前面全部被删除的情况,所以要加入i == -1。
来看代码实现:

char * makeGood(char * s){int i = 0, j = 1;//开始遍历while(j < strlen(s)){if(i == -1 ||  abs(s[i] - s[j]) != abs('A' - 'a')){s[++i] = s[j++];}//相当于删除元素else{i--;j++;}}s[++i] = '\0';return s;
}

来看效果:
在这里插入图片描述
非常好!!! 过啦!!!!!!!

思路三(C++栈版)

我们来看C++栈的写法,思路与思路一致:

void dfs(struct TreeNode *node, bool *color) {color[node->val] = true;if (node->left ) dfs(node->left , color);if (node->right) dfs(node->right, color);
}
int numColor(struct TreeNode* root){bool *color = (bool *)calloc(1, sizeof(bool) * 1001);int ans = 0;dfs(root, color);for (int i = 1; i < 1001; ++ i)if (color[i]) ++ ans;return ans;
}作者:_G_
链接:https://leetcode.cn/problems/sZ59z6/solutions/2580610/shen-du-you-xian-sou-suo-by-admiring-men-2rzv/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

思路很舒畅~

Thanks♪(・ω・)ノ谢谢阅读!!!

下一篇文章见!!!

这篇关于【刷题】leetcode 1544.整理字符串的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/753312

相关文章

MySQL字符串常用函数详解

《MySQL字符串常用函数详解》本文给大家介绍MySQL字符串常用函数,本文结合实例代码给大家介绍的非常详细,对大家学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录mysql字符串常用函数一、获取二、大小写转换三、拼接四、截取五、比较、反转、替换六、去空白、填充MySQL字符串常用函数一、

Python自动化批量重命名与整理文件系统

《Python自动化批量重命名与整理文件系统》这篇文章主要为大家详细介绍了如何使用Python实现一个强大的文件批量重命名与整理工具,帮助开发者自动化这一繁琐过程,有需要的小伙伴可以了解下... 目录简介环境准备项目功能概述代码详细解析1. 导入必要的库2. 配置参数设置3. 创建日志系统4. 安全文件名处

MySQL 迁移至 Doris 最佳实践方案(最新整理)

《MySQL迁移至Doris最佳实践方案(最新整理)》本文将深入剖析三种经过实践验证的MySQL迁移至Doris的最佳方案,涵盖全量迁移、增量同步、混合迁移以及基于CDC(ChangeData... 目录一、China编程JDBC Catalog 联邦查询方案(适合跨库实时查询)1. 方案概述2. 环境要求3.

SpringSecurity整合redission序列化问题小结(最新整理)

《SpringSecurity整合redission序列化问题小结(最新整理)》文章详解SpringSecurity整合Redisson时的序列化问题,指出需排除官方Jackson依赖,通过自定义反序... 目录1. 前言2. Redission配置2.1 RedissonProperties2.2 Red

MySQL 多列 IN 查询之语法、性能与实战技巧(最新整理)

《MySQL多列IN查询之语法、性能与实战技巧(最新整理)》本文详解MySQL多列IN查询,对比传统OR写法,强调其简洁高效,适合批量匹配复合键,通过联合索引、分批次优化提升性能,兼容多种数据库... 目录一、基础语法:多列 IN 的两种写法1. 直接值列表2. 子查询二、对比传统 OR 的写法三、性能分析

Javaee多线程之进程和线程之间的区别和联系(最新整理)

《Javaee多线程之进程和线程之间的区别和联系(最新整理)》进程是资源分配单位,线程是调度执行单位,共享资源更高效,创建线程五种方式:继承Thread、Runnable接口、匿名类、lambda,r... 目录进程和线程进程线程进程和线程的区别创建线程的五种写法继承Thread,重写run实现Runnab

Python中反转字符串的常见方法小结

《Python中反转字符串的常见方法小结》在Python中,字符串对象没有内置的反转方法,然而,在实际开发中,我们经常会遇到需要反转字符串的场景,比如处理回文字符串、文本加密等,因此,掌握如何在Pyt... 目录python中反转字符串的方法技术背景实现步骤1. 使用切片2. 使用 reversed() 函

Spring IoC 容器的使用详解(最新整理)

《SpringIoC容器的使用详解(最新整理)》文章介绍了Spring框架中的应用分层思想与IoC容器原理,通过分层解耦业务逻辑、数据访问等模块,IoC容器利用@Component注解管理Bean... 目录1. 应用分层2. IoC 的介绍3. IoC 容器的使用3.1. bean 的存储3.2. 方法注

MySQL 删除数据详解(最新整理)

《MySQL删除数据详解(最新整理)》:本文主要介绍MySQL删除数据的相关知识,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录一、前言二、mysql 中的三种删除方式1.DELETE语句✅ 基本语法: 示例:2.TRUNCATE语句✅ 基本语

MySQL查询JSON数组字段包含特定字符串的方法

《MySQL查询JSON数组字段包含特定字符串的方法》在MySQL数据库中,当某个字段存储的是JSON数组,需要查询数组中包含特定字符串的记录时传统的LIKE语句无法直接使用,下面小编就为大家介绍两种... 目录问题背景解决方案对比1. 精确匹配方案(推荐)2. 模糊匹配方案参数化查询示例使用场景建议性能优