代码随想录算法训练营Day08|344.反转字符串、541. 反转字符串II、卡码网:替换数字、151.翻转字符串里的单词、卡码网:右旋字符串

文章目录

  • 一、344.反转字符串
    • 1. 双指针法
  • 二、541. 反转字符串II
    • 1. 字符串解法
  • 三、卡码网:替换数字
  • 四、151.翻转字符串里的单词
    • 1.使用库函数
    • 2.自行编写函数
    • 3.创建字符数组填充
    • 3.双反转+移位
  • 五、卡码网:右旋字符串
    • 1. 自行编写函数
  • 总结


一、344.反转字符串

题目描述: 编写一个函数,其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。
不要给另外的数组分配额外的空间,你必须原地修改输入数组、使用 O ( 1 ) O(1) O(1) 的额外空间解决这一问题。

1. 双指针法

  • 时间复杂度: O ( n ) O(n) O(n)
  • 空间复杂度: O ( 1 ) O(1) O(1)

反转字符串

// 写法1
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;
        }
    }
}
// 写法2
class Solution {
    public void reverseString(char[] s) {
        int l = 0;
        int r = s.length - 1;
        while (l < r) {
            s[l] ^= s[r];  //构造 a ^ b 的结果,并放在 a 中
            s[r] ^= s[l];  //将 a ^ b 这一结果再 ^ b ,存入b中,此时 b = a, a = a ^ b
            s[l] ^= s[r];  //a ^ b 的结果再 ^ a ,存入 a 中,此时 b = a, a = b 完成交换
            l++;
            r--;
        }
    }
}

异或运算符(⊕)具有以下性质:
自反性:对于任何数a,有 a ⊕ a = 0 a\oplus a=0 aa=0
结合律:对于任何数a、b和c,有 a ⊕ ( b ⊕ c ) a\oplus (b\oplus c) a(bc)= ( a ⊕ b ) ⊕ c (a\oplus b)\oplus c (ab)c
交换律:对于任何数a和b,有a ⊕ b = b ⊕ a。
同一律:对于任何数a,有a ⊕ 0 = a。
零元律:对于任何数a,有 a ⊕ a = 0 a\oplus a=0 aa=0
写法2 进行了 XOR 操作,具体过程用数学公式如下:
假设 a = s [ l ] a=s[l] a=s[l], b = s [ r ] b=s[r] b=s[r],那么经过 XOR 操作后有:
a = a ⊕ b a=a\oplus b a=ab,
b = a ⊕ b = ( a ⊕ b ) ⊕ b = a ⊕ ( b ⊕ b ) = a b=a\oplus b=(a\oplus b)\oplus b=a\oplus (b\oplus b)=a b=ab=(ab)b=a(bb)=a,
a = b ⊕ a = a ⊕ ( a ⊕ b ) = ( a ⊕ a ) ⊕ b = b a=b\oplus a=a\oplus(a\oplus b)=(a\oplus a)\oplus b=b a=ba=a(ab)=(aa)b=b

二、541. 反转字符串II

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

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

1. 字符串解法

  • 时间复杂度: O ( n ) O(n) O(n)
  • 空间复杂度: O ( 1 ) O(1) O(1) O ( n ) O(n) O(n)
// 写法1
class Solution {
    public String reverseStr(String s, int k) {
        int n = s.length();
        char[] arr = s.toCharArray();
        for (int i = 0; i < n; i += 2 * k) {
            reverse(arr, i, Math.min(i + k, n) - 1);
        } 
        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--;
        }
    }
}
// 写法2
class Solution {
    public String reverseStr(String s, int k) {
        char[] ch = s.toCharArray();
        for (int i = 0; i < ch.length; i += 2 * k) {
            int start = i;
            // 这里判断尾数够不够k个来取end指针的位置
            int end = Math.min(ch.length - 1, start + k - 1);
            // 用异或运算反转
            while (start < end) {
                ch[start] ^= ch[end];
                ch[end] ^= ch[start];
                ch[start] ^= ch[end];
                start++;
                end--;
            }
        }
        return new String(ch);
    }
}

三、卡码网:替换数字

题目描述: 给定一个字符串 s,它包含小写字母和数字字符,请编写一个函数,将字符串中的字母字符保持不变,而将每个数字字符替换为number。

先预先给数组扩容带填充后的大小,然后在从后向前进行操作。

  • 时间复杂度: O ( n ) O(n) O(n)
  • 空间复杂度: O ( 1 ) O(1) O(1)
import java.util.Scanner;
class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String s = in.nextLine();
        int r = s.length() - 1;
        String str = "";
        for (int i = 0; i <= r; i++) {
            if (s.charAt(i) < '0' || s.charAt(i) > '9') {
                str += s.charAt(i);
            } else {
                str += "number";
            }
        }
        System.out.println(str);
    }
}

四、151.翻转字符串里的单词

题目描述: 给定一个字符串,逐个翻转字符串中的每个单词。

总体思路:移除多余空格 >>> 将整个字符串反转 >>> 将每个单词反转

1.使用库函数

split分割 >>> reverse 反转 >>> join拼接

  • 时间复杂度: O ( n ) O(n) O(n)
  • 空间复杂度: O ( n ) O(n) O(n)

使用库函数

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);
    }
}

2.自行编写函数

首先得把字符串转化成其他可变的数据结构,同时还需要在转化的过程中去除空格。

  • 时间复杂度: O ( n ) O(n) O(n)
  • 空间复杂度: O ( n ) O(n) O(n)

自定义函数

class Solution {
    public String reverseWords(String s) {
        // 1.去除首尾及中间多余空格
        StringBuilder sb = removeSpace(s);
        // 2.反转整个字符串
        reverseString(sb, 0, sb.length() - 1);
        // 3.反转各个单词
        reverseEachWord(sb);
        return sb.toString();
    }

    private StringBuilder removeSpace(String s) {
        int start = 0;
        int end = s.length() - 1;
        while (s.charAt(start) == ' ') start++;
        while (s.charAt(end) == ' ') end--;
        StringBuilder sb = new StringBuilder();
        while (start <= end) {
            char c = s.charAt(start);
            if (c != ' ' || sb.charAt(sb.length() - 1) != ' ') {
                sb.append(c);
            }
            start++;
        }
        return sb;
    }

    // 反转字符串指定区间[start, end]的字符
    public void reverseString(StringBuilder sb, int start, int end) {
        while (start < end) {
            char temp = sb.charAt(start);
            sb.setCharAt(start, sb.charAt(end));
            sb.setCharAt(end, temp);
            start++;
            end--;
        }
    }

    private void reverseEachWord(StringBuilder sb) {
        int start = 0;
        int end = 1;
        int n = sb.length();
        while(start < n) {
            while(end < n && sb.charAt(end) != ' ') {
                end++;
            }
            reverseString(sb, start, end - 1);
            start = end + 1;
            end = start + 1;
        }
    }
}

3.创建字符数组填充

  • 时间复杂度: O ( n ) O(n) O(n)
class Solution {
    public String reverseWords(String s) {
        //源字符数组
        char[] initialArr = s.toCharArray();
        //新字符数组
        char[] newArr = new char[initialArr.length+1];//下面循环添加"单词 ",最终末尾的空格不会返回
        int newArrPos = 0;
        //i来进行整体对源字符数组从后往前遍历
        int i = initialArr.length-1;
        while(i>=0){
            while(i>=0 && initialArr[i] == ' '){i--;}  //跳过空格
            //此时i位置是边界或!=空格,先记录当前索引,之后的while用来确定单词的首字母的位置
            int right = i;
            while(i>=0 && initialArr[i] != ' '){i--;} 
            //指定区间单词取出(由于i为首字母的前一位,所以这里+1,),取出的每组末尾都带有一个空格
            for (int j = i+1; j <= right; j++) {
                newArr[newArrPos++] = initialArr[j];
                if(j == right){
                    newArr[newArrPos++] = ' ';//空格
                }
            }
        }
        //若是原始字符串没有单词,直接返回空字符串;若是有单词,返回0-末尾空格索引前范围的字符数组(转成String返回)
        if(newArrPos == 0){
            return "";
        }else{
            return new String(newArr,0,newArrPos-1);
        }
    }
}

3.双反转+移位

在原数组上进行反转

  • 空间复杂度: O ( 1 ) O(1) O(1)
class Solution {
    /**
     * 思路:
     *	①反转字符串  "the sky is blue " => " eulb si yks eht"
     *	②遍历 " eulb si yks eht",每次先对某个单词进行反转再移位
     *	   这里以第一个单词进行为演示:" eulb si yks eht" ==反转=> " blue si yks eht" ==移位=> "blue si yks eht"
     */
    public String reverseWords(String s) {
        //步骤1:字符串整体反转(此时其中的单词也都反转了)
        char[] initialArr = s.toCharArray();
        reverse(initialArr, 0, s.length() - 1);
        int k = 0;
        for (int i = 0; i < initialArr.length; i++) {
            if (initialArr[i] == ' ') {
                continue;
            }
            int tempCur = i;
            while (i < initialArr.length && initialArr[i] != ' ') {
                i++;
            }
            for (int j = tempCur; j < i; j++) {
                if (j == tempCur) { //步骤二:二次反转
                    reverse(initialArr, tempCur, i - 1);//对指定范围字符串进行反转,不反转从后往前遍历一个个填充有问题
                }
                //步骤三:移动操作
                initialArr[k++] = initialArr[j];
                if (j == i - 1) { //遍历结束
                    //避免越界情况,例如=> "asdasd df f",不加判断最后就会数组越界
                    if (k < initialArr.length) {
                        initialArr[k++] = ' ';
                    }
                }
            }
        }
        if (k == 0) {
            return "";
        } else {
            //参数三:以防出现如"asdasd df f"=>"f df asdasd"正好凑满不需要省略空格情况
            return new String(initialArr, 0, (k == initialArr.length) && (initialArr[k - 1] != ' ') ? k : k - 1);
        }
    }

    public void reverse(char[] chars, int begin, int end) {
        for (int i = begin, j = end; i < j; i++, j--) {
            chars[i] ^= chars[j];
            chars[j] ^= chars[i];
            chars[i] ^= chars[j];
        }
    }
}

五、卡码网:右旋字符串

题目描述: 字符串的右旋转操作是把字符串尾部的若干个字符转移到字符串的前面。给定一个字符串 s 和一个正整数 k,请编写一个函数,将字符串中的后面 k 个字符移到字符串的前面,实现字符串的右旋转操作。
例如,对于输入字符串 “abcdefg” 和整数 2,函数应该将其转换为 “fgabcde”。

1. 自行编写函数

整体思路:通过 整体倒叙,把两段子串顺序颠倒,两个段子串里的的字符在倒叙一把,负负得正,这样就不影响子串里面字符的顺序了。

图1
图2

// 写法1
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = Integer.parseInt(in.nextLine());
        String s = in.nextLine();

        int len = s.length();  //获取字符串长度
        char[] chars = s.toCharArray();
        reverseString(chars, 0, len - 1);  //反转整个字符串
        reverseString(chars, 0, n - 1);  //反转前一段字符串,此时的字符串首尾尾是0,n - 1
        reverseString(chars, n, len - 1);  //反转后一段字符串,此时的字符串首尾尾是n,len - 1
        
        System.out.println(chars);

    }

    public static void reverseString(char[] ch, int start, int end) {
        //异或法反转字符串,参照题目 344.反转字符串的解释
        while (start < end) {
            ch[start] ^= ch[end];
            ch[end] ^= ch[start];
            ch[start] ^= ch[end];
            start++;
            end--;
        }
    }
}

如果先局部反转,那么先反转的子串长度就是 len - n。

图3
图4

// 写法2
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = Integer.parseInt(in.nextLine());
        String s = in.nextLine();

        int len = s.length();  //获取字符串长度
        char[] chars = s.toCharArray();
        reverseString(chars, 0, len - n - 1);  //反转前一段字符串,此时的字符串首尾是0,len - n - 1
        reverseString(chars, len - n, len - 1);  //反转后一段字符串,此时的字符串首尾是len - n,len - 1
        reverseString(chars, 0, len - 1);  //反转整个字符串

        System.out.println(chars);

    }

    public static void reverseString(char[] ch, int start, int end) {
        //异或法反转字符串,参照题目 344.反转字符串的解释
        while (start < end) {
            ch[start] ^= ch[end];
            ch[end] ^= ch[start];
            ch[start] ^= ch[end];
            start++;
            end--;
        }
    }
}

总结

以上就是今天学习的内容,不得不说库函数真的很节省代码量,然而对于初学者来说,构建函数更容易掌握底层原理。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/301885.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【软件测试】白盒测试 / 逻辑覆盖法

《语句覆盖法》 使程序中的每个可执行语句至少执行一次 所有的可执行语句得到执行语句覆盖测试是较弱的一种测试发现错误能力最弱的逻辑覆盖 《判定覆盖法》 使每一个判定获得每一种可能的结果至少一次 每个判定得到真值和假值判断覆盖法满足了语句覆盖&#xff0c;因此比语…

【AI视野·今日Sound 声学论文速览 第四十期】Wed, 3 Jan 2024

AI视野今日CS.Sound 声学论文速览 Wed, 3 Jan 2024 Totally 4 papers &#x1f449;上期速览✈更多精彩请移步主页 Daily Sound Papers Auffusion: Leveraging the Power of Diffusion and Large Language Models for Text-to-Audio Generation Authors Jinlong Xue, Yayue De…

十一、工具盒类(MyQQ)(Qt5 GUI系列)

目录 ​编辑 一、设计需求 二、实现代码 三、代码解析 四、总结 一、设计需求 抽屉效果是软件界面设计中的一种常用形式&#xff0c;可以以一种动态直观的方式在有限大小的界面上扩展出更多的功能。本例要求实现类似 QQ 抽屉效果。 二、实现代码 #include "dialog.…

2024年第二届语言、创新教育与文化交流国际学术会议(CLEC 2024)

2024年第二届语言、创新教育与文化交流国际学术会议(CLEC 2024) 2024 2nd International Conference on Language, Innovative Education and Cultural Communication 为迎接知识经济时代的挑战&#xff0c;创新教育被用来培养学生的创新精神与能力。知识的普遍性使得创新教育…

CSS同时使用背景图和渐变色

CSS同时使用背景图和渐变色 需求代码实现完整写法 需求 一个盒子&#xff0c;在拥有渐变色的前提下还需要同时拥有背景图层 类似如下的效果 代码实现 首先我们按照常规的写css的方式来写 <div class"box"></div>.box{width: 300px;height: 120px;bo…

「网络安全术语解读」SARIF详解

引言&#xff1a;什么是SARIF&#xff1f;它的产生背景是什么&#xff1f;SARIF主要包含哪些内容&#xff1f;使用SARIF有哪些好处&#xff1f; 1. SARIF简介 SARIF&#xff08;Static Analysis Results Interchange Format &#xff0c;静态分析结果交换格式&#xff09;是一…

jenkins 自由风格部署vue项目,参数化构建vue项目

1. 丢弃旧的构建 2. 是否需要install 3. git 4. 配置node16: 5. 脚本&#xff1a; 脚本&#xff1a; #进入Jenkins工作空间下项目目录 cd /var/lib/jenkins/workspace/你的任务名称 node -v #检测node版本&#xff08;此条命令非必要&#xff09; npm -v #检测npm版本&#x…

电力系统中的交流负载箱

交流负载箱是电力系统中的一种重要设备&#xff0c;主要用于模拟实际的电力负载&#xff0c;以便对电力系统进行各种性能测试和分析。在电力系统的设计和运行过程中&#xff0c;交流负载箱起着至关重要的作用。 交流负载箱的主要功能是模拟实际的电力负载&#xff0c;包括电阻、…

开源内容管理框架Drupal在Docker本地部署并实现公网远程访问

&#x1f49d;&#x1f49d;&#x1f49d;欢迎来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学…

2024--Django平台开发-Django知识点(四)

1.知识回顾 创建项目&#xff1a;新项目、别人项目、新版版、老版本 项目目录&#xff08;v1.0版本&#xff09; 路由系统 常见路由编写加粗样式 /index/ 函数 /index/<str:v1> 函数 re_path(ryy/(\d{4})-(\d{2})-(\d{2})/, views.yy), re_path(ryy/(?…

python炒股自动化(0),申请券商API接口

上次发了量化交易接口的区别&#xff0c;发现很多人根本不知道券商提供的API交易接口&#xff0c;这里补充一篇&#xff0c;关于券商接口的介绍。 现在市面上可以给个人账户接入的股票交易接口&#xff0c;用的最多的也就是QMT和Ptrade&#xff0c;以前接入量化交易需要机构或…

Mac上修复Gitee报错 Oauth: Access token is expired

一. 背景&#xff1a; 最近在gitee上拉了两次项目&#xff0c;两次使用的邮箱密码不一致&#xff08;换绑邮箱&#xff09;&#xff0c;第一次在idea中拉取后端项目&#xff0c;第二次在webstorm中拉取前端项目&#xff0c;出现该异常&#xff0c;记录下解决方案 二. 错误回显…

nodejs版本管理工具nvm的安装与使用

提示&#xff1a;nodejs版本管理工具nvm的安装与使用 文章目录 前言一、安装二、淘宝镜像配置三、安装所需版本的nodejs四、切换nodejs版本五、参考文档总结 前言 需求&#xff1a;新建一个vue3项目&#xff0c;&#xff0c;提示写法错误 查原因为node版本过低 随着技术更新迭…

24年初级会计报名注意事项及报名详细流程,快查收,错过再等一年

&#x1f369;初级会计报名正在进行中&#xff0c;报考的政策咱们了解了&#xff0c;那么报考流程&#xff0c;大家也先熟悉一下&#xff0c;&#x1f9c1;咱们报名就不会手忙脚乱咯&#x1f942; &#x1f9ca;具体有以下几步&#xff1a;#新手帮扶计划# 1️⃣登录全国资格评…

误删除的备忘录恢复方法是什么?备忘录不小心删除了怎么找回?

有不少小伙伴在使用手机的过程中&#xff0c;想要随手记录一些琐事或容易忘记的事情&#xff0c;使用手机系统备忘录或便签等记事工具是非常便捷的。不过在日积月累的使用过程中&#xff0c;备忘录中记录的内容就会越来越多&#xff0c;为了高效使用它&#xff0c;就需要定期删…

如何快速制作网址的静态码?网址二维码在线制作的简单技巧

现在很多人会将网址转换成静态二维码来使用&#xff0c;一个原因是扫码更符合现在人们的生活习惯&#xff0c;二来是采用二维码图片来做传播能够有效的节省制作者的成本&#xff0c;而且容易更快的完成网址内容的传播&#xff0c;所以将网址生成二维码的方法现在应用非常的广泛…

啊哈c语言——5.9逻辑挑战11(猜数游戏)

计算机会随机地给出0&#xff5e;99之间的一个整数&#xff0c;你能否猜出这个数呢&#xff1f;每猜一次&#xff0c;计算机都会告诉你猜的数是大了还是小了&#xff0c;直到你猜出这个数为止。 首先我们需要解决的第一个问题就是如何让计算机随机地产生一个整数&#xff0c;这…

Oracle11.2.0.4从RMAN备份中快速恢复单个表的方法

文章目录 前言一、查询所要恢复的表所涉及的表空间二、创建用于恢复的数据库三、恢复步骤1.恢复控制文件2.修改redo日志名称3.表空间恢复4.表空间recover5.查询数据 前言 由于用户误操作导致某表中的数据错乱&#xff0c;导致业务不能正常使用&#xff0c;现需要将该表恢复到一…

结队编程 - 华为OD统一考试

OD统一考试 题解: Java / Python / C++ 题目描述 某部门计划通过结队编程来进行项目开发,已知该部门有 N 名员工,每个员工有独一无二的职级,每三个员工形成一个小组进行结队编程,结队分组规则如下: 从部门中选出序号分别为 i、j、k 的3名员工,他们的职级分别为 level[…

APP加固技术及其应用

文章目录 引言 APP加固的概念 APP加固的方案 APP加固在实际开发中的应用 总结 引言 在移动应用开发过程中&#xff0c;APP加固技术起到了非常重要的作用。APP加固是将apk文件进行混淆加密&#xff0c;以防止别人反编译获取我们的源码和资源文件。目前市场上主流的APP加固…