代码随想录刷题笔记(DAY 8)

发布时间:2024年01月04日

今日总结:最后一道题解决的比较糟糕,后续会补上新解法,今天还是将中心放在了前端。

Day 8

01. 反转字符串(No. 344)

题目链接

代码随想录题解

1.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”]

提示:

  • 1 <= s.length <= 105
  • s[i] 都是 ASCII 码表中的可打印字符
1.2 笔记

非常简单的一道题目,而且题目给的就是一个 char 数组,简单的回顾一下反转的写法

char temp = s[left];
s[left] = s[right];
s[right] = temp;

反转的次数为 s.length / 2 向下取整,写出代码

1.3 代码
class Solution {
    public void reverseString(char[] s) {
        int n = s.length / 2;
        int left = 0;
        int right = s.length - 1;
        while (n-- > 0) {
            char temp = s[left];
            s[left] = s[right];
            s[right] = temp;
            left++;
            right--;
        }
    }
}

02. 反转字符串 II(No. 541)

题目链接

代码随想录题解

2.1 题目

给定一个字符串 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
2.2 笔记

这道题比前面那个复杂的多,有很多条件需要考虑,我们先来尝试读懂题意:

我们可以声明两个指针,这两个指针表明一个 [nk, n2k] 的范围,这个范围不断向后移动,每次出现一次这个范围我们就将前 k 个元素反转。

比如第一次反转的是 [0, k] 第二次是 [2k + 1, 3k]

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

前面的都很好理解,就是当最后一个 2k 跃出数组的时候(比如上图的 8k),对于这一组的 7k 就要分两种情况了

  • 如果 7k 也在数组外的话,我们就将 6k + 1 到数组结尾的内容全部反转
  • 否则就只反转 [6k + 1, 7k]的部分。

看了上面的步骤,我们需要一个函数,能够将我们指定起点到指定终点的内容执行反转,有了上题的经验,这个应该很容易写出来

    public void reverseCharArrayByIndex(int indexLeft, int indexRight) {
        // 反转在范围内的下标
        int length = (indexRight - indexLeft + 1) / 2;
        while (length-- > 0) {
            char temp = x[indexLeft];
            x[indexLeft] = x[indexRight];
            x[indexRight] = temp;
            indexLeft++;
            indexRight--;
        }
    }

接下来,就要用两个指针去遍历了,第一个指针right每次移动 2k 的距离,第二个指针指向的是 right - 2k + 1 的位置这个 +1 就是我们上面比如 2k + 1 中要加的这个 1,是为了更新范围的。

循环结束的时间就是当我们发现 right 跃出数组的时候,这时候我们就可以对上面出现的两种情况来分别求解了

2.3 代码
class Solution {
    char[] x;
    public String reverseStr(String s, int k) {
        x = s.toCharArray();
        int left = 0; // k 处的下标
        int right = (2 * k - 1); // 2k 处的下标
        int n = 1;// 记录是第几个 2k
        while (true) {
            // 表示遍历到终点了
            if (right >= x.length - 1) {
                // 最后一次处理放在循环结束后做
                break;
            }
            reverseCharArrayByIndex(left, left + k - 1);
            n++; // 表明下一次
            right = n * 2 * k - 1;
            left = right - 2 * k + 1;            
        }
        if (x.length - left > k) {
            reverseCharArrayByIndex(left, left + k - 1);
        } else {
            reverseCharArrayByIndex(left, x.length - 1);
        }
        return String.valueOf(x);
    }
    public void reverseCharArrayByIndex(int indexLeft, int indexRight) {
        // 反转在范围内的下标
        int length = (indexRight - indexLeft + 1) / 2;
        while (length-- > 0) {
            char temp = x[indexLeft];
            x[indexLeft] = x[indexRight];
            x[indexRight] = temp;
            indexLeft++;
            indexRight--;
        }
    }
}

03. 反转字符串中的单词

题目链接

代码随想录题解

3.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”
解释:如果两个单词间有多余的空格,反转后的字符串需要将单词间的空格减少到仅有一个。

提示:

  • 1 <= s.length <= 104
  • s 包含英文大小写字母、数字和空格 ' '
  • s至少存在一个 单词
3.2 笔记

这道题目目前只是做出了一个解法,时间复杂度很高,我这里先将这个方法讲述一下,后面学到新方法会补上。

我们先利用 split 函数将字符串按照空格分割,得到一个数组,然后我们会得到一个新的数组,这个数组中可能包含空字符串。

我们对这个新的字符串数组进行反转,

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

这时可能会有疑惑,这里面不相干的元素不会影响我们反转吗?

我们假想一个数组,在里面随意添加好多不相干的元素,将这个数组反转之后把不相干的元素去掉,结果和直接反转数组效果是一样的。

反转后依次取出元素,如果里面的不是 “” 空字符串我们就将它前面加上空格,再拼接到结果字符串中

为什么是前面呢?

因为可以规避最后一个元素后面多加一个空格的情况,转化为处理第一位多加空格的情况,只需要返回一个 res.substring(1); 即可,而不是要写 res.substring(0, res.length - 1);

3.3 代码
class Solution {
    public String reverseWords(String s) {
        String[] words = s.split(" ");
        int n = words.length / 2;
        int left = 0;
        int right = words.length - 1;
        String res = "";
        while (n-- > 0) {
            String temp = words[left];
            words[left] = words[right];
            words[right] = temp;
            left++;
            right--;
        }
        for (int i = 0; i < words.length; i++) {
            if (words[i] != "") {
                res += " " + words[i];
            }            
        }
        return res.substring(1);
    }
}
文章来源:https://blog.csdn.net/weixin_74895237/article/details/135375559
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。