卷进大厂系列之LeetCode刷题笔记：反转链表II（简单）

学算法，刷力扣，加油卷，进大厂！

题目描述

力扣题目链接

给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。

• 如果剩余字符少于 k 个，则将剩余字符全部反转。
• 如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。

示例 1：

输入：s = "abcdefg", k = 2输出："bacdfeg"

示例 2：

输入：s = "abcd", k = 2输出："bacd"

提示：

• 1 <= s.length <= 104
• s 仅由小写英文组成
• 1 <= k <= 104

涉及知识点

这是一道在反转链表的基础上改进的题目，只不过改过之后还是没有什么难度，毕竟单纯的使用数组，对大家 来说还是比较简单的。所以，我们依然可以使用数组的一些特征来解决这道题目。

• 数组是存储在连续内存空间的相同类型数据的集合
• 数组下标都是从0开始
• 数组在内存空间的地址都是连续的
• 字符串也是一种数组

那么根据题目，我们可以提炼的关键点：

• 每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符
• 如果剩余字符少于 k 个，则将剩余字符全部反转
• 如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样

解决这道题目我们只需要理解题意，即我们反转的字符并不是全部，而且某一部分，那解决这道题目就需要我们根据2k这个计数来确定需要反转的部分。

题目解答

Java题解一

思路分析

• 首先我们需要把字符串放入数组，方便操作
• 然后根据每次增加量为2k，进行循环遍历数组
• 接着在上一步遍历的2k内，根据要求进行反转（前面说到的关键点）
• 可以将反转数组单独写成一个方法
• 最后需要把数组转化成字符串输出

代码实现

class Solution {    public String reverseStr(String s, int k) {  //把s放入数组 char[] arr = s.toCharArray(); //循环，每次增加量为2k for (int i = 0; i < arr.length; i += 2 * k) {     reverse(arr, i, Math.min(i + k, arr.length) - 1);//在2k内调用数组内反转，里面包含判断条件 } return new String(arr); //再转回字符串    }      public void reverse(char[] arr, int left, int right) { //整个字符串的反转（上一个题目详细注释） while (left < right) {     char temp = arr[left];     arr[left] = arr[right];     arr[right] = temp;     left++;     right--; }    } }