代码随想录 ╰半橙微兮° 2024-02-22 09:15 5阅读 0赞 ## 前言 ## 代码随想录算法训练营day08 -------------------- ## 一、Leetcode 344.反转字符串 ## ### 1.题目 ### 编写一个函数,其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。 不要给另外的数组分配额外的空间,你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。 示例 1: 输入:s = \["h","e","l","l","o"\] 输出:\["o","l","l","e","h"\] 示例 2: 输入:s = \["H","a","n","n","a","h"\] 输出:\["h","a","n","n","a","H"\] 提示: css 复制代码 `1 <= s.length <= 105 s[i] 都是 ASCII 码表中的可打印字符` 来源:力扣(LeetCode) 链接:[leetcode.cn/problems/re…][leetcode.cn_problems_re] ### 2.解题思路 ### 方法一:双指针 思路与算法 对于长度为 N 的待被反转的字符数组,我们可以观察反转前后下标的变化,假设反转前字符数组为 s\[0\] s\[1\] s\[2\] ... s\[N - 1\],那么反转后字符数组为 s\[N - 1\] s\[N - 2\] ... s\[0\]。比较反转前后下标变化很容易得出 s\[i\] 的字符与 s\[N - 1 - i\] 的字符发生了交换的规律,因此我们可以得出如下双指针的解法: css 复制代码 `将 left 指向字符数组首元素,right 指向字符数组尾元素。 当 left < right: 交换 s[left] 和 s[right]; left 指针右移一位,即 left = left + 1; right 指针左移一位,即 right = right - 1。 当 left >= right,反转结束,返回字符数组即可。` ### 3.代码实现 ### java 复制代码 `class Solution { public void reverseString(char[] s) { int n = s.length; for (int left = 0, right = n - 1; left < right; ++left, --right) { char tmp = s[left]; s[left] = s[right]; s[right] = tmp; } } }` ## 二、Leetcode 剑指Offer 05.替换空格 ## ### 1.题目 ### 请实现一个函数,把字符串 s 中的每个空格替换成"%20"。 示例 1: 输入:s = "We are happy." 输出:"We%20are%20happy." 来源:力扣(LeetCode) 链接:[leetcode.cn/problems/ti…][leetcode.cn_problems_ti] ### 2.解题思路 ### 方法一:字符数组 由于每次替换从 1 个字符变成 3 个字符,使用字符数组可方便地进行替换。建立字符数组地长度为 s 的长度的 3 倍,这样可保证字符数组可以容纳所有替换后的字符。 matlab 复制代码 `获得 s 的长度 length 创建字符数组 array,其长度为 length * 3 初始化 size 为 0,size 表示替换后的字符串的长度 从左到右遍历字符串 s 获得 s 的当前字符 c 如果字符 c 是空格,则令 array[size] = '%',array[size + 1] = '2',array[size + 2] = '0',并将 size 的值加 3 如果字符 c 不是空格,则令 array[size] = c,并将 size 的值加 1 遍历结束之后,size 的值等于替换后的字符串的长度,从 array 的前 size 个字符创建新字符串,并返回新字符串` ### 3.代码实现 ### java 复制代码 `class Solution { public String replaceSpace(String s) { int length = s.length(); char[] array = new char[length * 3]; int size = 0; for (int i = 0; i < length; i++) { char c = s.charAt(i); if (c == ' ') { array[size++] = '%'; array[size++] = '2'; array[size++] = '0'; } else { array[size++] = c; } } String newStr = new String(array, 0, size); return newStr; } }` ## 三、Leetcode 151.翻转字符串里的单词 ## ### 1.题目 ### 给你一个字符串 s ,请你反转字符串中 单词 的顺序。 单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。 返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。 注意:输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中,单词间应当仅用单个空格分隔,且不包含任何额外的空格。 示例 1: 输入:s = "the sky is blue" 输出:"blue is sky the" 示例 2: 输入:s = " hello world " 输出:"world hello" 解释:反转后的字符串中不能存在前导空格和尾随空格。 示例 3: 输入:s = "a good example" 输出:"example good a" 解释:如果两个单词间有多余的空格,反转后的字符串需要将单词间的空格减少到仅有一个。 提示: matlab 复制代码 `1 <= s.length <= 104 s 包含英文大小写字母、数字和空格 ' ' s 中 至少存在一个 单词` 来源:力扣(LeetCode) 链接:[leetcode.cn/problems/re…][leetcode.cn_problems_re 1] ### 2.解题思路 ### 方法一:使用语言特性 思路和算法 很多语言对字符串提供了 split(拆分),reverse(翻转)和 join(连接)等方法,因此我们可以简单的调用内置的 API 完成操作: perl 复制代码 `使用 split 将字符串按空格分割成字符串数组; 使用 reverse 将字符串数组进行反转; 使用 join 方法将字符串数组拼成一个字符串。` ### 3.代码实现 ### java 复制代码 `class Solution { public String reverseWords(String s) { // 除去开头和末尾的空白字符 s = s.trim(); // 正则匹配连续的空白字符作为分隔符分割 List<String> wordList = Arrays.asList(s.split("\\s+")); Collections.reverse(wordList); return String.join(" ", wordList); } }` ## 四、Leetcode 剑指Offer58-II.左旋转字符串 ## ### 1.题目 ### 字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如,输入字符串"abcdefg"和数字2,该函数将返回左旋转两位得到的结果"cdefgab"。 示例 1: 输入: s = "abcdefg", k = 2 输出: "cdefgab" 示例 2: 输入: s = "lrloseumgh", k = 6 输出: "umghlrlose" 限制: matlab 复制代码 `1 <= k < s.length <= 10000` 来源:力扣(LeetCode) 链接:[leetcode.cn/problems/zu…][leetcode.cn_problems_zu] ### 2.解题思路 ### 方法二:列表遍历拼接 算法流程: scss 复制代码 `新建一个 list(Python)、StringBuilder(Java) ,记为 resres ; 先向 resres 添加 “第 n+1n+1 位至末位的字符” ; 再向 resres 添加 “首位至第 nn 位的字符” ; 将 resres 转化为字符串并返回。` ### 3.代码实现 ### java 复制代码 `class Solution { public String reverseLeftWords(String s, int n) { StringBuilder res = new StringBuilder(); for(int i = n; i < s.length(); i++) res.append(s.charAt(i)); for(int i = 0; i < n; i++) res.append(s.charAt(i)); return res.toString(); } }` 作者:东离与糖宝 链接:https://juejin.cn/post/7232228935865040953 来源:稀土掘金 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。 [leetcode.cn_problems_re]: https://link.juejin.cn?target=https%3A%2F%2Fleetcode.cn%2Fproblems%2Freverse-string [leetcode.cn_problems_ti]: https://link.juejin.cn?target=https%3A%2F%2Fleetcode.cn%2Fproblems%2Fti-huan-kong-ge-lcof [leetcode.cn_problems_re 1]: https://link.juejin.cn?target=https%3A%2F%2Fleetcode.cn%2Fproblems%2Freverse-words-in-a-string [leetcode.cn_problems_zu]: https://link.juejin.cn?target=https%3A%2F%2Fleetcode.cn%2Fproblems%2Fzuo-xuan-zhuan-zi-fu-chuan-lcof
相关 代码随想录 前言 代码随想录算法训练营day08 -------------------- 一、Leetcode 344.反转字符串 1.题目 编写一个函数,其作用是 ╰半橙微兮°/ 2024年02月22日 09:15/ 0 赞/ 6 阅读
相关 代码随想录 前言 代码随想录算法训练营day06 -------------------- 一、哈希表基础知识 【 [代码随想录][Link 1]】 【[菜鸟教 桃扇骨/ 2024年02月22日 09:14/ 0 赞/ 20 阅读
相关 代码随想录 前言 代码随想录算法训练营day39 -------------------- 一、Leetcode 62.不同路径 1.题目 一个机器人位于一个 m x 女爷i/ 2024年02月22日 04:39/ 0 赞/ 35 阅读
相关 代码随想录 前言 代码随想录算法训练营day37 -------------------- 一、Leetcode 968.监控二叉树 v 1.题目 给定一个二叉树,我 朱雀/ 2024年02月22日 04:38/ 0 赞/ 51 阅读
相关 代码随想录 前言 代码随想录算法训练营day37 -------------------- 一、Leetcode 968.监控二叉树 v 1.题目 给定一个二叉树,我 叁歲伎倆/ 2024年02月22日 04:37/ 0 赞/ 20 阅读
相关 代码随想录 前言 代码随想录算法训练营day39 -------------------- 一、Leetcode 62.不同路径 1.题目 一个机器人位于一个 m x 左手的ㄟ右手/ 2024年02月22日 02:29/ 0 赞/ 7 阅读
相关 代码随想录 前言 代码随想录算法训练营day37 -------------------- 一、Leetcode 968.监控二叉树 v 1.题目 给定一个二叉树,我 旧城等待,/ 2024年02月22日 02:28/ 0 赞/ 28 阅读
相关 代码随想录 前言 代码随想录算法训练营day36 -------------------- 一、Leetcode 738.单调递增的数字 1.题目 当且仅当每个相邻位 r囧r小猫/ 2024年02月22日 02:27/ 0 赞/ 9 阅读
相关 代码随想录 前言 代码随想录算法训练营day35 -------------------- 一、Leetcode 860.柠檬水找零 1.题目 在柠檬水摊上,每一杯柠 朱雀/ 2024年02月22日 02:26/ 0 赞/ 61 阅读
相关 代码随想录 一、Leetcode 122.买卖股票的最佳时机II 1.题目 给你一个整数数组 prices ,其中 prices\[i\] 表示某支股票第 i 天的价格。 在 清疚/ 2024年02月22日 02:24/ 0 赞/ 34 阅读
还没有评论,来说两句吧...