• 06数据结构与算法刷题之【字符串】篇

    文章目录

    前言

    除了去年11月份以及今年近几月的算法刷题之外，只有在当时20年蓝桥杯准备的时候才刷过一些题，在当时就有接触到一些动归、递归回溯、贪心等等，不过那会也还是一知半解，做的题目也特别少，因为考虑到之后面试有算法题以及数据结构算法对于一个程序员十分重要，我也开始了刷题之路。

    我目前的学习数据结构与算法及刷题路径：

    1、学习数据结构的原理以及一些常见算法。

    2、代码随想录：跟着这个github算法刷题项目进行分类刷，在刷题前可以学习一下对应类别的知识点，而且这里面每道题都讲的很详细。

    3、牛客网高频面试101题：牛客网—面试必刷101题，在刷的过程中可以在leetcode同步刷一下。

    4、接下来就是力扣上的专栏《剑指offer II》、《程序员面试金典（第 6 版）》…有对应的精选题单来对着刷即可。

    5、大部分的高频面试、算法题刷完后，就可以指定力扣分类专栏进行一下刷题了。

    刚开始刷的时候真的是很痛苦的，想到去年一道题可能就需要好几小时，真的就很难受的，不过熬过来一切都会好起来，随着题量的增多，很多题目你看到就会知道使用什么数据结构或者算法来去求解，并且思考对应的时间空间复杂度，并寻求最优解，我们一起加油！

    我的刷题历程

    截止2022.8.18：

    1、牛客网101题(其中1题是平台案例有问题)：image-20220818095030215

    2、剑指offerII：image-20220818095104757

    力扣总记录数：image-20220818095148897

    加油加油！

    剑指offer

    剑指 Offer 58 - II. 左旋转字符串【简单】

    学习：leetcode题解、 代码随想录—题目：剑指Offer58-II.左旋转字符串

    题目链接：剑指 Offer 58 - II. 左旋转字符串

    题目内容：

    字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串"abcdefg"和数字2，该函数将返回左旋转两位得到的结果"cdefgab"。

示例 1：
输入: s = "abcdefg", k = 2
输出: "cdefgab"

示例 2：
输入: s = "lrloseumgh", k = 6
输出: "umghlrlose"

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9

    思路：

    1、翻转字符串

    思路：对原始字符数组进行操作，首先整体进行反转，之后对两个区间进行反转。

    代码：未申请额外空间，直接在原始串上操作

    public String reverseLeftWords(String s, int n) {
    //步骤1：整体进行反转，例如："lrloseumgh" => "hgmuesolrl"
    char[] chars = s.toCharArray();
    reverse(chars, 0, chars.length - 1);

    //步骤2：前后两个区间进行反转
    reverse(chars, 0, chars.length - 1 - n);//"hgmuesolrl" => "umghesolrl"
    reverse(chars, chars.length - n, chars.length - 1);//"umghesolrl" => "umghlrlose"
    return new String(chars);
}

/**
     * 反转字符数组指定范围内容：[begin,end]
     */
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];
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21

    image-20211023203115447

    该解法执行用时2ms，竟然只击败了49.27%，我看了下击败100%的题解，使用的substring与append拼接的方式，在下面NO3中有题解。

    2、字符数组

    思路：创建一个新的字符数组，依次填充即可。

    复杂度分析：时间复杂度O(n)

    public String reverseLeftWords(String s, int n) {
    char[] chars = new char[s.length()];
    int k = 0;
    //非左转的先遍历填充
    for (int i = n; i < s.length(); i++) {
        chars[k++] =  s.charAt(i);
    }
    //需左转的后遍历填充
    for (int i = 0; i < n; i++) {
        chars[k++] =  s.charAt(i);
    }
    return new String(chars);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13

    image-20211023212704661

    3、借助API（最高效）

    刚开始看到题解我也有点懵，用API反而效率更高啥情况，之后去研究了下，与底层实现有关。该题主要还是核心重点放在NO1题解的思路解法上。

    思路：其实与NO2思路填充完全一致，只不过这里使用API来进行字符串截取与拼接。

    • 为什么快？与substring有关，其底层使用的是System.arraycopy进行拷贝。①在NO2中写的for循环拷贝方式若是没有被编译器优化，就是遍历数组操作的字节码，接着执行引擎会根据这些字节码循环获取数组的每个元素再执行拷贝。②而System.arraycopy为JVM内部固有方法，通过手工编写汇编或其他优化方法来进行Java数组拷贝，该方式比for循环更高效尤其数组越大越明显。

    代码：

    public String reverseLeftWords(String s, int n) {
    StringBuilder strBuilder = new StringBuilder();
    strBuilder.append(s.substring(n));
    strBuilder.append(s.substring(0,n));
    return strBuilder.toString();
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    image-20211023213045898

    剑指 Offer 05. 替换空格【简单】

    学习：leetcode题解、 代码随想录—题目：剑指Offer 05.替换空格

    题目链接：剑指 Offer 05. 替换空格

    题目内容：请实现一个函数，把字符串 s 中的每个空格替换成"%20"。

    思路：

    1、双指针：

    思路： 对于字符串中空格=>“%20”，由一个字符填充为3个字符，普通解法就是遍历一遍的过程中遇到空白字符串先将后面的统一移动两个接着进行填充，该思路时间复杂度为O(n2)；

    所以这里我们使用双指针的方案，首先遍历一遍字符串确定其中有多少个空格对原始字符串进行扩容，紧接着来定义两个指针，一个指针指向原始字符串最后一个位置，另一个指针指向扩展之后最后一个位置，每次移动两个指针同时向前移动，若是左指针碰到空格，右指针进行%、0、2向前以前填充前进两步；若不是空格，右指针指向的值改为左指针当前指向的值，根据此规则不断重复即可！时间复杂度为O(n)。这里我直接引用 代码随想录—题目：剑指Offer 05.替换空格 中的思路图，十分推荐该博主的算法指南，十分清晰

    img

    public String replaceSpace(String s) {
    //扩充空间，空格数量2倍
    StringBuilder str = new StringBuilder();
    for (int i = 0; i < s.length(); i++) {
        if(s.charAt(i) == ' '){
            str.append("  ");
        }
    }
    //若是没有空格直接返回
    if(str.length() == 0){
        return s;
    }
    //有空格情况 定义两个指针
    int left = s.length() - 1;//左指针：指向原始字符串最后一个位置
    s += str.toString();
    int right = s.length()-1;//右指针：指向扩展字符串的最后一个位置
    char[] chars = s.toCharArray();
    while(left>=0){
        if(chars[left] == ' '){
            chars[right--] = '0';
            chars[right--] = '2';
            chars[right] = '%';
        }else{
            chars[right] = chars[left];
        }
        left--;
        right--;
    }
    return new String(chars);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30

    image-20211021230156983

    剑指 Offer 58 - I. 翻转单词顺序【简单】

    题目链接：剑指 Offer 58 - I. 翻转单词顺序

    题目内容：输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串"I am a student. “，则输出"student. a am I”。

    思路：

    1、从后往前排除空格法

    优化前(Stringbuilder拼接)：

    思路：从前往后进行遍历，遇到空格往后移动一步，遇到非空格先记录下当前索引，接着一直遍历到该单词的后一个位置，取出该单词最终进行拼接返回。

    代码：

    //"the sky is blue" => "blue is sky the"
public String reverseWords(String s) {
    StringBuilder str = new StringBuilder();
    int i = 0;
    //遍历字符串结束
    while(i<s.length()){
        //过滤空字符串
        while(i<s.length() && s.charAt(i) == ' '){i++;}
        if( i == s.length()){
            break;
        }
        int temp = i;
        while(i<s.length() && s.charAt(i) != ' '){i++;}
        String word =  s.substring(temp,i);
        str = new StringBuilder(word).append(" ").append(str);
    }
    if(str.length()>0){
        return str.substring(0,str.length() - 1);
    }
    return "";
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21

    image-20211022231502419

    这里直接使用了String的api来进行截取字符串操作，并且来进行合并多个单词时频繁创建StringBuilder，不仅仅影响时间还有空间复杂度。

    优化后(char[]，时间复杂度最优解)：

    思路：这里是从后往前进行遍历，首先遇到!=空格的先记录索引left，紧接着继续向前移动直到为邻接点或者=空格停止，此时我们就能够拿到对应单词的范围索引，将该单词取出依次存储到新字符数组中。

    代码：时间复杂度O(n)、空间复杂度O(n)

    • 这里是没有任何API进行调用的，纯对字符数组进行操作，所以比优化前的效果好很多

    代码：

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28

    image-20211022234501827

    No2：双反转+移位

    思路：并没有开辟新的数组或字符串来进行拼接，而是在原始字符数组上来进行操作。

    ①反转字符串 "the sky is blue "=> " eulb si yks eht"

    ②遍历" eulb si yks eht"，过程中先对某个单词进行反转再移位

    • 对第一个单词进行操作举例：" eulb si yks eht" =反转> " blue si yks eht" =移位> "blue si yks eht"

    代码：时间复杂度O(n)、空间复杂度O(1)

    /**
  * 空间复杂度O(1)解法
  */
public String reverseWords(String s) {
    //步骤1：字符串整体反转（此时其中的单词也都反转了）
    char[] initialArr = s.toCharArray();
    reverse(initialArr, 0, s.length() - 1);
    //步骤2：遍历循环字符串
    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];
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45

    image-20211023004402268

    No3：拆成多组字符串来进行拼接

    复杂度分析：时间复杂度O(n)，空间复杂度O(n)

    class Solution {

    //api方法：拆成多组，然后从后往前进行添加
    public String reverseWords(String s) {
        String[] str = s.trim().split(" ");
        StringBuilder b = new StringBuilder();
        for (int i = str.length - 1; i >= 0; i--) {
            //若是碰到空单词进行跳过
            if ("".equals(str[i])) {
                continue;
            }
            b.append(str[i]);
            if (i != 0) {
                b.append(" ");
            }
        }
        return b.toString();
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19

    剑指 Offer 67. 把字符串转换成整数【中等】

    题目链接：剑指 Offer 67. 把字符串转换成整数

    题目内容：

    写一个函数 StrToInt，实现把字符串转换成整数这个功能。不能使用 atoi 或者其他类似的库函数。
首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。
当我们寻找到的第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字组合起来，作为该整数的正负号；假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成整数。

该字符串除了有效的整数部分之后也可能会存在多余的字符，这些字符可以被忽略，它们对于函数不应该造成影响。

注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换。
在任何情况下，若函数不能进行有效的转换时，请返回 0。

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    思路：

    1、越界处理

    System.out.println(Integer.MAX_VALUE);//2147483647
System.out.println(Integer.MAX_VALUE + 1);//-2147483648
System.out.println(Integer.MIN_VALUE);//-2147483648
System.out.println(Integer.MIN_VALUE - 1);//2147483647

    • 1
    • 2
    • 3
    • 4

    复杂度分析：时间复杂度O(n)，空间复杂度O(1)

    在进行合并前来进行判断校验

    • 1
    class Solution {

    //注意点
    //1、截止到数字前只有负号或者空白字符才有效
    //2、若是第一个非空白字符或负号，那么无法有效转换数字
    //3、若是越界int类型，那么返回负数或正数的最大值
    //步骤：①去除空白字符。②确定第一个字符是否是正负数，不是直接返回。③来进行遍历，过程中需要去进行校验是否有越界情况
    //负数最小：-2147483648  正数最大：2147483647
    public int strToInt(String str) {
        //1、去除空格
        char[] arr = str.trim().toCharArray();
        if (arr == null || arr.length == 0) {
            return 0;
        }
        int sign = 1;
        int res = 0, bndry = Integer.MAX_VALUE / 10;//bndry是214748364
        int i = 1;//初始的遍历位置
        if (arr[0] == '-') {
            sign = -1;
        }else if (arr[0] != '+') {
            i = 0;
        }
        //开始进行遍历
        for (int j = i; j < arr.length; j++) {
            //若是非数字直接结束
            if (arr[j] < '0' || arr[j] > '9') {
                break;
            }
            //这里很巧妙，利用最后一位是否>'7'来表示是否越界
            if (res > bndry || (res == bndry && arr[j] > '7')) {
                return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
            }
            res = res * 10 + arr[j] - '0';
        }
        return sign * res;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37

    其中同样可以进行优化，针对于trim()我们来自己手写实现，将对应trim()行替换为下面的：

    if (str == null || str.length() == 0) {
    return 0;
}
char[] arr = str.toCharArray();
int i = 0; 
while (i < arr.length && arr[i] == ' ') {
    i++;
}
if (i == arr.length) {
    return 0;
}
i = i + 1;//进位1

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    完整的是：

    public int strToInt(String str) {
    if (str == null || str.length() == 0) {
        return 0;
    }
    //1、去除空格
    char[] arr = str.toCharArray();
    int i = 0;
    while (i < arr.length && arr[i] == ' ') {
        i++;
    }
    if (i == arr.length) {
        return 0;
    }
    i = i + 1;//进位1
    int sign = 1;
    int res = 0, bndry = Integer.MAX_VALUE / 10;//bndry是214748364
    if (arr[i - 1] == '-') {
        sign = -1;
    }else if (arr[i - 1] != '+') {
        i = i - 1;
    }
    //开始进行遍历
    for (int j = i; j < arr.length; j++) {
        //若是非数字直接结束
        if (arr[j] < '0' || arr[j] > '9') {
            break;
        }
        //这里很巧妙，利用最后一位是否>'7'来表示是否越界
        if (res > bndry || (res == bndry && arr[j] > '7')) {
            return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
        }
        res = res * 10 + arr[j] - '0';
    }
    return sign * res;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35

    剑指 Offer 20. 表示数值的字符串【中等】

    学习资料：视频-20. 表示数值的字符串、视频—剑指Offer20 表示数值的字符串

    题目链接：剑指 Offer 20. 表示数值的字符串

    题目内容：

    请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。
数值（按顺序）可以分成以下几个部分：

若干空格
一个 小数 或者 整数
（可选）一个 'e' 或 'E' ，后面跟着一个 整数
若干空格
小数（按顺序）可以分成以下几个部分：
（可选）一个符号字符（'+' 或 '-'）
下述格式之一：
至少一位数字，后面跟着一个点 '.'
至少一位数字，后面跟着一个点 '.' ，后面再跟着至少一位数字
一个点 '.' ，后面跟着至少一位数字
整数（按顺序）可以分成以下几个部分：

（可选）一个符号字符（'+' 或 '-'）
至少一位数字
部分数值列举如下：
["+100", "5e2", "-123", "3.1416", "-1E-16", "0123"]
部分非数值列举如下：
["12e", "1a3.14", "1.2.3", "+-5", "12e+5.4"]

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21

    思路：

    1、有限状态机

    2、遍历判断状态校验

    复杂度分析：时间复杂度O(n)；空间复杂度O(1)

    class Solution {

    //+-号：出现在第一个位置或者E or e后一个位置合法
    //.：前面不能出现.或者e
    //e or E：e之前不能出现e，且必须有数字。e之后必须要有数字（我们设置isNum=false即可）
    public boolean isNumber(String s) {
        //三个状态量
        boolean isNum = false;
        boolean isE = false;
        boolean isDot = false;
        //去除空格
        s = s.trim();
        char[] arr = s.toCharArray();
        for (int i = 0; i < arr.length; i++) {
            char ch = arr[i];
            //首先判断数字
            if (ch >= '0' && ch <= '9') {
                isNum = true;
            }else if (ch == '+' || ch == '-') { //判断 + - 号
                if (i != 0 && arr[i - 1] != 'e' && arr[i - 1] != 'E') {
                    return false;
                }
            }else if (ch == '.') { //判断.号
                if (isDot || isE) {
                    return false;
                }
                isDot = true;
            }else if (ch == 'e' || ch == 'E') { //判断e
                if (isE || !isNum) {
                    return false;
                }
                isE = true;
                isNum = false;//e之后必须要有数字，防止出现12e之类
            }else { //其他字符
                return false;
            }
        }
        return isNum;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40

    剑指 Offer 44. 数字序列中某一位的数字【中等】

    学习资料：面试题44. 数字序列中某一位的数字（迭代 + 求整 / 求余，清晰图解）

    题目链接：剑指 Offer 44. 数字序列中某一位的数字

    题目内容：数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中，第5位（从下标0开始计数）是5，第13位是1，第19位是4，等等。

    请写一个函数，求任意第n位对应的数字。

    思路：

    1、迭代求整（找规律）

    关键：start(新的n位数开始位置)、digit（位数）、count（当前位数有的个数）

    • 1

    复杂度分析：时间复杂度O(logn)；空间复杂度O(logn)

    class Solution {
    //范围      位数     数量
    //0-9        1       10
    //10-99      2       180
    //100-999    3       2700
    //start     digit    9 * start * digit
    //1、找到指定的数位   n = n - count
    //2、确定数字范围值   num = 10 + (n - 1) / digit
    //3、找到对应的索引   charAt((n - 1) % digit) - '0'   
    public int findNthDigit(int n) {
        int start = 1;
        long digit = 1;
        long count = 9;
        //1、确定数位，在哪个档n
        while (n > count) {
            n -= count;
            digit++;
            start *= 10;
            count = 9 * digit * start;
        }
        //2、求得实际的值
        long num = start + (n - 1) / digit;
        //3、确定指定的索引数字
        return Long.toString(num).charAt((int)((n - 1) % digit)) - '0';
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26

    数组中出现次数超过一半的数字（28）

    题目描述
    数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。

    程序代码：哈希表来进行存储计算。

    程序代码：

    //方式一：Map进行筛检法
//假设数组是非空的，并且给定的数组总是存在多数元素
/**
     * 执行用时：13 ms, 在所有 Java 提交中击败了20.01%的用户
     * 内存消耗：46.3 MB, 在所有 Java 提交中击败了16.10%的用户
     */
public int majorityElement(int[] nums) {
    if (nums == null || nums.length == 0){
        return 0;
    }
    if (nums.length == 1) {
        return nums[0];
    }
    Map<Integer,Integer> numsMap = new HashMap<>();
    for (int num : nums) {
        //判断是否有该key，有的话来进行判断当前值，没有的话进行赋值
        Integer value = numsMap.getOrDefault(num, 0);
        if (value == 0) {
            numsMap.put(num, 1);
        }else {
            //注意：数量是大于总数的二分之一
            if (value + 1 > nums.length / 2) {
                return num;
            }
            numsMap.put(num, value + 1);
        }
    }
    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29

    执行用时：13 ms, 在所有 Java 提交中击败了20.01%的用户

    内存消耗：46.3 MB, 在所有 Java 提交中击败了16.10%的用户

    //方式二：排序法
/**
     * 执行用时：2 ms, 在所有 Java 提交中击败了54.68%的用户
     * 内存消耗：44.6 MB, 在所有 Java 提交中击败了68.89%的用户
     */
public int majorityElement(int[] nums) {
    if (nums == null || nums.length == 0){
        return 0;
    }
    if (nums.length == 1) {
        return nums[0];
    }
    //O(logn)
    Arrays.sort(nums);
    int medium = nums.length / 2;
    if (nums[medium] == nums[medium - 1] || nums[medium] == nums[medium + 1]){  //奇、偶数情况
        return nums[medium];
    }
    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20

    最优解来了：O(n)

    注意后半段话：假设数组是非空的，并且给定的数组总是存在多数元素。题目给定案例是大于一半数字的。

    思路：既然要找出现次数大于一半元素，那么可以采用抵消法。

    //方式三：抵消法，数组必定存在多数
/**
     * 执行用时：1 ms, 在所有 Java 提交中击败了99.96%的用户
     * 内存消耗：44.7 MB, 在所有 Java 提交中击败了53.99%的用户
     */
public int majorityElement(int[] nums) {
    int curMaxNum = 0;
    int counts = 0;
    for (int i = 0; i < nums.length; i++) {
        if (counts == 0) {
            curMaxNum = nums[i];
        }
        //核心抵消思路
        if (nums[i] == curMaxNum) {
            counts++;
        }else{
            counts--;
        }
    }
    return curMaxNum;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21

    最小的K个数（29）

    题目描述

    输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。

    题解1：

    /**
     *  执行用时：6 ms, 在所有 Java 提交中击败了72.26%的用户
     *  内存消耗：42.5 MB, 在所有 Java 提交中击败了21.53%的用户
     */
//1、API调用排序法
//输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。
public int[] getLeastNumbers(int[] arr, int k) {
    if (arr == null || arr.length <= k){
        return arr;
    }
    //1、排序
    // Arrays.sort(int[]) 使用双轴快速排序算法,时间复杂度为0(logn)
    // Collections.sort(List) 是一种优化过的合并排序算法,时间复杂度是O(n)
    Arrays.sort(arr);
    //2、取出前k个数（优化：使用API取）
    //        int[] numArr = new int[k];
    //        for (int i = 0; i < k; i++) {
    //            numArr[i] = arr[i];
    //        }
    //        return numArr;
    return Arrays.copyOfRange(arr, 0, k);//[0，4)
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22

    其他思路：手写快排来进行测试

    效率最高方式：待探索，手写

    //执行用时：1 ms, 在所有 Java 提交中击败了100.00%的用户
//内存消耗：42.3 MB, 在所有 Java 提交中击败了30.04%的用户
// 快排 不用排全部/荷兰国旗快排
// 优先级队列（堆）
// 二叉搜索树
public int[] getLeastNumbers(int[] arr, int k) {
    quickSort(arr, k, 0, arr.length-1);
    return Arrays.copyOfRange(arr, 0, k);//使用API来优化进行复制
}
public void quickSort(int[] arr, int k, int lo, int hi){
    int res = partition(arr, lo, hi);
    if(k == res) return;
    else if(k < res){
        quickSort(arr, k, lo, res-1);
    }else{
        quickSort(arr, k, res+1, hi);
    }
}

public int partition(int[] nums, int lo, int hi){
    if(hi-lo < 1) return lo;
    int tmp = nums[lo];
    int l = lo;
    int r = hi;
    while(l < r){
        while(nums[r] >= tmp && l < r) r--;
        nums[l] = nums[r];
        while(nums[l] <= tmp && l < r) l++;
        nums[r] = nums[l];
    }
    nums[l] = tmp;
    return l;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33

    牛客网

    字符串变形【简单】

    题目链接：字符串变形

    题目内容：对于一个长度为 n 字符串，我们需要对它做一些变形。首先这个字符串中包含着一些空格，就像"Hello World"一样，然后我们要做的是把这个字符串中由空格隔开的单词反序，同时反转每个字符的大小写。

    思路1：①先反转整个字符串(按照相应的规则)。②然后再对整个字符串中的单词进行单独反转。

    复杂度分析：

    • 时间复杂度：O(n)
    • 空间复杂度：O(n)
    import java.util.*;

public class Solution {
    public String trans(String s, int n) {
        StringBuilder str = new StringBuilder();
        for (int i = n-1;i >=0;i--) {
            str.append(transfer(s.charAt(i)));
        }
        //1、获取到反转过后的字符串（按照相应的规则进行转换）
        String str1 = str.toString();
        //2、再对整个字符串中的各个单词来进行反转
        StringBuilder resStr = new StringBuilder();
        for(int i = 0;i < n;i++) {
            int j = i;
            while(j < n && str1.charAt(j) != ' ') {
                j++;
            }
            //获取到这个转换后的字符串
            StringBuilder reverseStr = new StringBuilder(str1.substring(i, j));
            resStr.append(reverseStr.reverse().toString());
            if (j < n && str1.charAt(j) == ' ') {
                resStr.append(' ');
            }
            i = j;
        }
        return resStr.toString();
    }
    
    //按照规则转换
    public char transfer(char ch) {
        if (ch >= 'a' && ch <= 'z') {
            ch -= 32; 
        }else if (ch >= 'A' && ch <= 'Z') {
            ch += 32;
        }
        return ch;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38

    思路2：利用栈来进行反转单词顺序。①遍历字符串，将所有单词取出依次入栈。②从栈中弹出不断的进行拼接（需要注意原始字符串初始最后为空格情况）。

    复杂度分析：

    • 时间复杂度：O(n)，遍历字符串+出栈的单词数量，差不多就是2n。
    • 空间复杂度：O(n)，使用了栈这个存储空间，存储了所有的单词。
    import java.util.*;

public class Solution {
    //利用栈来进行
    public String trans(String s, int n) {
        Stack<String> stack = new Stack<>();
        //遍历字符串
        for (int i = 0;i < s.length();i++) {
            //遍历得到某个单词
            int j = i;
            while (j < n && s.charAt(j) != ' ') {
                j++;
            }
            String subStr = s.substring(i, j);
            //入栈
            stack.push(replaceStr(subStr));
            i = j;
        }
        //使用StringBuilder来进行拼接
        StringBuilder builder = new StringBuilder();
        //**初始添加空格情况，举例："changlu abc "**
        if (s.charAt(n - 1) == ' ') {
            builder.append(' ');
        }
        while (!stack.isEmpty()) {
            builder.append(stack.pop());
            if (!stack.isEmpty()) {
                builder.append(" ");
            }
        }
        return builder.toString();
    }
    
    public String replaceStr(String str) {
        if (str == null || str.length() == 0) {
            return str;
        }
        char[] chars = str.toCharArray();
        for (int i = 0;i < str.length();i++) {
            chars[i] = transfer(chars[i]);
        }
        return new String(chars);
    }
    
    //按照规则转换
    public char transfer(char ch) {
        if (ch >= 'a' && ch <= 'z') {
            ch -= 32; 
        }else if (ch >= 'A' && ch <= 'Z') {
            ch += 32;
        }
        return ch;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54

    验证IP地址【中等】

    做题前知识点

    ipv4： 1、十进制数和点来表示，每个地址包含4个十进制数，其范围为 0 - 255。②使用.来分割。
	   2、IPv4 地址内的数不会以 0 开头，例如 172.16.254.01 是不合法。
ipv6: 1、8组16进制的数字来表示，每组表示 16 比特。
	  2、可以加入一些以 0 开头的数字，字母可以使用大写，也可以是小写。
	  3、通过:来分割

    • 1
    • 2
    • 3
    • 4
    • 5

    问题1：\\.表示什么意思？【ipv4校验】

    • 正则中一个单独的点表示任意字符，所有字符都作为分隔符当然不会有任何结果
    • \\.实际上被转义为两次，\在java中被转换为一个’‘字符，然后’.‘被传给正则，.表示对点字符进行转义，使.就表示字符’.',而不使用它在正则中的特殊意义

    问题2：.split(“,“, -1) 和 .split(“,“) 的区别？【ipv6校验】

    • 举例：String a="河南省，，金水区";
      • a.split(“,”) = [河南省,金水区 ]
      • 而a.split(",",-1) = [河南省, ,金水区 ]，即 .split(“,”, -1);会保存空值。

    做题

    题目链接：验证IP地址

    题目内容：编写一个函数来验证输入的字符串是否是有效的 IPv4 或 IPv6 地址。

    思路1：分割字符串比较法【推荐】

    复杂度分析：

    • 时间复杂度：O(n)
    • 空间复杂度：O(1)
    import java.util.*;


public class Solution {
    /**
     * 验证IP地址
     * @param IP string字符串 一个IP地址字符串
     * @return string字符串
     */
    public String solve (String IP) {
        if (isIPV4(IP)) {
            return "IPv4";
        }else if (isIPV6(IP)) {
            return "IPv6";
        }else {
            return "Neither";
        }
    }

    public boolean isIPV4(String IP) {
        //IP.length() > 15：提前结束。【最大：255.255.255.255】
        if (IP == null || IP.length() == 0 || IP.length() > 15) {
            return false;
        }
        //额外：校验最后一位是否为.的情况
        if (IP.charAt(IP.length() - 1) == '.') {
            return false;
        }
        String[] strs = IP.split("\\.");
        if (strs.length != 4) {
            return false;
        }
        //开始进行校验IPV4了
        for (String str : strs) {
            //判断是否字符串长度为0
            if (str.length() == 0) {
                return false;
            }
            //字符串长度>3（如2555）、第一位为o即总长度不为1个的情况（如：01）
            if (str.length() > 3 || (str.charAt(0) == '0' && str.length() != 1)) {
                return false;
            }
            //计算数字之和
            int num = 0;
            for (int i = 0; i < str.length(); i++) {
                num = num * 10 + str.charAt(i) - '0';
            }
            if (num < 0 || num > 255) {
                return false;
            }
        }
        return true;
    }
    
    //4*8+7=39
    public boolean isIPV6(String IP) {
        if (IP == null || IP.length() == 0 || IP.length() > 39) {
            return false;
        }
        //额外：校验最后一位是否为:的情况
        if (IP.charAt(IP.length() - 1) == ':') {
            return false;
        }
        String[] strs = IP.split(":", -1);//将::中间的空格也作为情况
        if (strs.length != 8) {
            return false;
        }
        for (String str : strs) {
            if (str.length() == 0 || str.length() > 4) {
                return false;
            }
             for (int i = 0; i < str.length(); i++) {
                char ch = str.charAt(i);
                //十六进制范围在a-f中
                boolean expr = (ch >= 'a' && ch <= 'f' ) || (ch >= 'A' && ch <= 'F') || (ch >= '0' && ch <= '9');
                if (!expr) {
                    return false;
                }
            }
        }
        return true;
    }
    
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84

    大数加法【中等】

    题目链接：大数加法

    题目内容：以字符串的形式读入两个数字，编写一个函数计算它们的和，以字符串形式返回。

    思路1：模拟法，通过从末尾来开始不断的以单位来进行计算，最终进行返回。

    复杂度分析：

    • 时间复杂度：O(n)。
    • 空间复杂度：O(1)。使用字符串s原本的字符数组来进行。
    import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 计算两个数之和
     * @param s string字符串 表示第一个整数
     * @param t string字符串 表示第二个整数
     * @return string字符串
     */
    //思路：字符串从后往前进行个位数相加。【错误思路：化为数字相加】
    public String solve (String s, String t) {
        if (s == null || t == null) {
            return s;
        }
        //假设s最长，t略短
        if (t.length() > s.length()) {
            String temp = s;
            s = t;
            t = temp;
        }
        char[] sArr = s.toCharArray();
        int sLength = sArr.length - 1;
        char[] tArr = t.toCharArray();
        int tLength = tArr.length - 1;
        //进位符
        int temp = 0;
        for (int i = sLength; i >= 0; i--) {
            //s的值
            int sVal = sArr[i] - '0';
            //t的值
            int tVal = 0;
            if (tLength >= 0) {
                tVal = tArr[tLength] - '0';
                tLength--;
            }
            int num = sVal + tVal + temp;
            //%求得的值放入到sArr数组中
            sArr[i] = (char)(num % 10 + '0');
            //更新进位符
            temp = num / 10;
        }
        String res = new String(sArr);
        //最终进位符情况，若是>0需要拼接
        if (temp > 0) {
            return temp + res;
        }
        return res;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51

    思路2：双指针法【推荐】，在leetcode中最快！

    复杂度分析：

    • 时间复杂度：O(n)。
    • 空间复杂度：O(n)。
    class Solution {
    /**
     * 双指针解法：时间复杂度为O(n)
     */
    public String addStrings(String num1, String num2) {
        StringBuilder str = new StringBuilder("");
        int i = num1.length() - 1,j = num2.length() - 1;
        int temp = 0;
        while (i >= 0 || j >= 0) {
            int n1 = i >= 0 ? num1.charAt(i) - '0' : 0;
            int n2 = j >= 0 ? num2.charAt(j) - '0' : 0;
            int sum = n1 + n2 + temp;
            temp = sum / 10;
            str.append(sum % 10);
            i--;
            j--;
        }
        if (temp == 1){
            str.append(1);
        }
        return str.reverse().toString();
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23

    最长公共前缀【中等】

    题目链接：最长公共前缀

    题目内容：给你一个大小为 n 的字符串数组 strs ，其中包含n个字符串 , 编写一个函数来查找字符串数组中的最长公共前缀，返回这个公共前缀。

    思路1：拿第一个元素，遍历其每个字符然后不断的与之后所有的单词来进行比较。

    复杂度分析：

    • 时间复杂度：O(m*n)。
    • 空间复杂度：O(1)
    import java.util.*;


public class Solution {
    /**
     * 
     * @param strs string字符串一维数组 
     * @return string字符串
     */
    public String longestCommonPrefix (String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        //拿第一个字符串来与后面的各个字符依次进行比较
        for (int i = 0; i < strs[0].length(); i++) {
            char ch = strs[0].charAt(i);
            for (int j = 1; j < strs.length; j++) {
                //条件1：第一个单词的长度是否>后面的单词。条件二：对应位置的字符是否符合。
                if (i > (strs[j].length() - 1) || strs[j].charAt(i) != ch) {
                    return strs[0].substring(0 , i);
                }
            }
        }
        return strs[0];
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26

    leetcode

    459. 重复的子字符串【简单】

    学习：leetcode题解、 代码随想录—459.重复的子字符串

    题目链接：459. 重复的子字符串

    题目内容：

    给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。

示例 1:
输入: s = "abab"
输出: true
解释: 可由子串 "ab" 重复两次构成。

示例 2:
输入: s = "aba"
输出: false

示例 3:
输入: s = "abcabcabcabc"
输出: true
解释: 可由子串 "abc" 重复四次构成。 (或子串 "abcabc" 重复两次构成。)

提示：
1 <= s.length <= 104
s 由小写英文字母组成

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19

    思路：

    1、整除比较法(初始思路)

    思路： 先自己想思路，有了思路直接code就行，当前提交没有看题解。

    核心点：一个子串重复多次构成、只含有小写英文字母、长度不超过10000
思路：
1、确定每次重复的个数，这是我们能够确定的。例如"abababab"，长度为8。那么每次重复个数情况有1、2、4。(for循环模一下即可判定)
2、直到重复个数之后就好办了，重新开个for循环从指定位置开始指定长度比较就ok，一旦一组比较下来都相同直接返回true，否则进行其他重复个数情况二次比较！

    • 1
    • 2
    • 3
    • 4

    代码：

    public boolean repeatedSubstringPattern(String s) {
    String subStr = "";
    for (int i = 1; i < s.length(); i++) {
        //每i个数能够成对出现
        if(s.length() % i == 0){
            subStr = s.substring(0,i);
            int j = i;
            for (; j < s.length(); j+=i) {
                if(!Objects.equals(subStr,s.substring(j,j+i))){
                    break;
                }
            }
            if(j == s.length()){
                return true;
            }
        }
    }
    return false;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19

    image-20211031202208437

    同样与这个思路一致，将直接取两个子串方式改为取两个指针来从左到右进行比较，看下是否有时间上的优化：

    • 注释的内容表示被替换了
    public boolean repeatedSubstringPattern(String s) {
    //        String subStr = "";
    for (int i = 1; i < s.length(); i++) {
        if(s.length() % i == 0){
            //                subStr = s.substring(0,i);
            int j = i;
            for (; j < s.length(); j+=i) {
                //左右指针比较
                //                    if(!Objects.equals(subStr,s.substring(j,j+i))){
                //                        break;
                //                    }
                /*******直接取子串=>左右连续对比*******/
                int subStrCur = 0;
                int jCur = j;
                while(subStrCur != i){
                    if(s.charAt(subStrCur) != s.charAt(jCur)){
                        break;
                    }
                    subStrCur++;
                    jCur++;
                }
                if(subStrCur != i){
                    break;
                }
                /**************/
            }
            if(j == s.length()){
                return true;
            }
        }
    }
    return false;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33

    image-20211101140019454

    效果感觉不咋地，反而比我们使用subString()取字符串来的效率高，现在去看下其他人题解。

    2、KMP解决（核心，重点掌握）

    思路：利用KMP算法求得next数组，接着通过next数组最后一个元素的指向的最长重复前缀位置来进行判断是否当前字符串是否为重复的子字符串。

    举例：
例1：s="abababab"  next[] = [-1, -1, 0, 1, 2, 3, 4, 5]
	next数组最后一个位置为5，指向原字符串中的倒数第三个，使用原字符串长度减去该位置-1，8-5-1=2，2就指的是对应子串的长度，接着使用字符串长度进行%,若是=0，表示其为重复子串。公式为：s.length() % (s.length() - targetPos - 1) == 0
	
例2：s="ababcddc" next=[-1, -1, 0, 1, -1, -1, -1, -1]
	最后位置为-1，直接判定没有重复字符串。

例3：s="ababcdab" next[] = [-1, -1, 0, 1, -1, -1, 0, 1]
	最后位置为1，同理代入，8%(8-1-1)=2，没有整%，所以直接判断没有

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9

    代码：时间复杂度O(n)

    public int getNext(String s) {
    //KMP求得next数组        
    int next[] = new int[s.length()];
    int j = -1;
    next[0] = -1;
    for (int i = 1; i < s.length(); i++) {
        while (j >= 0 && s.charAt(i) != s.charAt(j + 1)) {
            j = next[j];
        }
        if (s.charAt(i) == s.charAt(j + 1)) {
            j++;
        }
        next[i] = j;
    }
    return next[s.length() - 1];
}

public boolean repeatedSubstringPattern(String s) {
    //使用KMP取到最后一个元素重复元素前缀位置
    int targetPos = getNext(s);
    if (targetPos == -1) {
        return false;
    }
    if (s.length() % (s.length() - targetPos - 1) == 0) {
        return true;
    }
    return false;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28

    image-20211101143900259

    3、超级整除法（参考大佬）

    使用KMP最后的执行耗时才击败了62%的人，接着就去看了看大佬的代码，真的是特别特别巧妙！

    思路：相对于NO1的整除法，中间有很多没必要二次比较的情况，并且我是从小数重复串进行一一比对的，这里使用大数重复串比较，并且省去了一些没必要重复比较的情况。

    假设某个字符串长度为8，按照正常思路顺序，先取最长重复串长度为4个4个比较、失败取2个2个、失败再取1个1个。
其实后面的两次就是没有必要的，我们举个例子："abababac"
	①abab abac  (失败)
	②ab ab ab ac (失败)
	③a b a b a b b a c (失败)
仔细看第二步，假设它是重复串组成ab ab ab ab，那么就必然就有abab abab判断成功，那么①失败，下面的②③比较自然没有必要了。其规律就可以找到凡是某个最大子串匹配失败，那么其整除的情况(也就是②③)直接可以省略掉。

上面说明了没必要重复比较的情况，下面再举一个长度为6的例子："ababab"
	①aba bab (失败)
	②ab ab ab （成功）
对于该种情况，第②步是不用被省略的，因为第一组最大重复数量为3，其并不能整除2，那么对重复长度为2的自然会进行一一比较，这里就有一个问题，我们该如何进行比较？上面长度为6的有三组，难道要一个一个进行比？从大佬的代码中我又看到了解答，所有任意情况只要比较1次即可，对于②中取出abab abab这两个，刚开始我也贼蒙蔽，不过之后就感叹其妙的地方了。
重复长度2，第一组[0,6-2-1]=>[0,3] 第二组[2,6-1]=>[2-5],假设三组子字符串都先相同，那么任意两组之和也必然相同，借助这个要点，我们即可将多组比较化为2组比出结果。

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    代码：

    public boolean repeatedSubstringPattern2(String s) {
    int len = s.length();
    int parts = 2;//从2开始，之后取子串len/2、len/3，保证子串从最大长度开始进行比较重复
    int noRepeatLen = len;
    while (noRepeatLen > 1) {
        if (noRepeatLen % parts == 0) {
            int k = len / parts;//子串长度
            //取出两组进行比较
            if (Objects.equals(s.substring(0, len - k), s.substring(k))) {
                return true;
            }
            //去除重复的整除情况，在除数上进行操作
            noRepeatLen /= parts;
            while (noRepeatLen % parts == 0) {
                noRepeatLen /= parts;
            }
        }
        parts++;
    }
    return false;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21

    image-20211101182730440

    NO4、超简洁解法（看看就好）

    好家伙，两行解决？还是很妙的。举两个例子就可以看懂了。

    思路：

    ① s="abac" 不重复情况  "ababca"
 s+s = "abacabac"，去头去尾"bacaba"
② s="abab"
 s+s = "abababab"，去头去尾"bababa" √
③ s="aaaa"
 s+s = "aaaaaaaa"，去头去尾"aaaaaa" √
 
 这种方式很巧妙，通过拼接方式去头去尾看其中是否存在原字符串。若是有重复的必然拼接中有对应重复的！

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    代码：

    public boolean repeatedSubstringPattern(String s) {
    String str = s + s;
    return str.substring(1, str.length() - 1).contains(s);
}

    • 1
    • 2
    • 3
    • 4

    image-20211101185001905

    28. 实现 strStr()【简单】

    学习：leetcode题解、 代码随想录—28. 实现 strStr()

    题目链接：28. 实现 strStr()

    题目内容：

    实现 strStr() 函数。
给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回  -1 。

说明：
当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。
对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与 C 语言的 strstr() 以及 Java 的 indexOf() 定义相符。

示例 1：
输入：haystack = "hello", needle = "ll"
输出：2

示例 2：
输入：haystack = "aaaaa", needle = "bba"
输出：-1

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14

    思路：

    1、暴力匹配

    思路：从前往后进行匹配，中间会使用一个临时节点来进行保存已经匹配的内容进行。

    代码：

    public int strStr(String haystack, String needle) {
    if (haystack == null || needle == null || "".equals(needle)) {
        return 0;
    }

    for (int i = 0; i < haystack.length(); i++) {
        int j = i;
        int k = 0;
        //临时保存中间与needle第一个字符相同的
        int temp = -1;//若是下面没有匹配到就移动一格
        while (k < needle.length() && j < haystack.length() && haystack.charAt(j) == needle.charAt(k)) {
            if (j > i && haystack.charAt(j) == needle.charAt(0) && temp == -1) {
                temp = j;
            }
            j++;
            k++;
        }
        if (k == needle.length()) {
            return i;
        } else if (temp != -1) {
            i = temp - 1;
        }
    }
    return -1;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25

    image-20211023230050067

    2、KMP算法

    思路：若是查询的子串过长，不使用一些手段来过滤掉一些重复的操作就很容易超时。这里来使用KMP来获取前缀表并进行最长前后缀位置匹配，省略掉一些不需要重复进行比较的重复内容。

    代码：时间复杂度O(m+n)

    //构建前缀表
public void getNext(int[] next, String s) {
    if (next.length > 0) {
        int j = -1;
        next[0] = j;
        for (int i = 1; i < next.length; i++) {
            //j实际表示当前字符串是否带有前缀的标记，>0表示有，则将当前位置内容与原本前缀后一个元素是否相同，若是相同
            while (j >= 0 && s.charAt(i) != s.charAt(j + 1)) {
                j = next[j];
            }
            //用于进行更新当前前缀索引
            if (s.charAt(i) == s.charAt(j + 1)) {
                j++;
            }
            next[i] = j;
        }
    }
}

public int strStr(String haystack, String needle) {
    if (haystack == null || needle == null || "".equals(needle)) {
        return 0;
    }

    int[] next = new int[needle.length()];
    getNext(next, needle);

    //当前匹配的子串索引位置，之后比较都是需要索引位置+1进行判断
    int j = -1;
    for (int i = 0; i < haystack.length(); i++) {
        //根据前缀表来匹配最近的重复前缀位置
        while (j >= 0 && haystack.charAt(i) != needle.charAt(j + 1)) {
            j = next[j];
        }
        //haystack与needle指定位置比较，若是相同加一，说明该子串匹配通过
        if (haystack.charAt(i) == needle.charAt(j + 1)) {
            j++;
        }
        if (j == needle.length() - 1) {
            return (i - needle.length() + 1);
        }
    }
    return -1;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44

    image-20211024235447209

    344. 反转字符串【简单】

    学习：leetcode题解、 代码随想录—344.反转字符串

    题目链接：344. 反转字符串

    题目内容：

    编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 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
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14

    思路：

    1、双指针

    思路： 定义两个指针，分别指向第一个数及最后一个数，每次移动前先进行交换，交换后进行左右移动。

    复杂度分析：时间复杂度O(n)

    public void reverseString(char[] s) {
    for (int i = 0, j = s.length - 1; i < j; i++, j--) {
        char temp = s[i];
        s[i] = s[j];
        s[j] = temp;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    image-20211020224446038

    列举一些交换方法：

    //方式一：存储变量
char temp = s[i];
s[i] = s[j];
s[j] = temp;

//方式二：位运算  例如a=10,b=20  a=a^b=30 b=b^a=10 a=a^b=20
s[i] ^= s[j];
s[j] ^= s[i];
s[i] ^= s[j];

//方式三：加减法
s[i] += s[j];
s[j] = (char) (s[i]-s[j]);
s[i] = (char) (s[i]-s[j]);

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14

    541. 反转字符串 II【简单】

    学习： leetcode题解、 代码随想录—541. 反转字符串II

    题目链接：541. 反转字符串 II

    题目内容：

    给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。
如果剩余字符少于 k 个，则将剩余字符全部反转。
如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。
 
示例 1：
输入：s = "abcdefg", k = 2
输出："bacdfeg"

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11

    思路：

    1、递归

    思路：每次移动2*k，若是移动的位置在当前字符数组范围内对前k个进行反转，这是个循环过程。若是不在范围内，就要额外来处理两种情况。①剩余字符少于k个，剩余字符全部反转。②大于等于k个，小于2k个就反转前k个字符。详细可见代码

    public String reverseStr(String s, int k) {
    int curPos = 2 * k;
    char[] chars = s.toCharArray();
    //每次循环2*k个字符
    while (curPos <= s.length()) {
        reverse(chars, curPos - 2 * k, curPos - k - 1);
        curPos += 2 * k;
    }
    //判断是否有剩余字符
    if ((curPos - 2 * k) <= s.length()) {
        //剩余>=k <2*k情况，反转前面k个
        if (curPos - k <= s.length()) {
            reverse(chars, curPos - 2 * k, curPos - k - 1);
        } else {
            //反转剩余的全部
            reverse(chars, curPos - 2 * k, s.length() - 1);
        }

    }
    return new String(chars);
}

//反转字符串
public void reverse(char[] chars, int left, int right) {
    while (left < right) {
        chars[left] ^= chars[right];
        chars[right] ^= chars[left];
        chars[left++] ^= chars[right--];
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30

    image-20211021221127215

    415. 字符串相加【简单】

    题目链接：415. 字符串相加

    题目内容：

    给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和并同样以字符串形式返回。
你不能使用任何內建的用于处理大整数的库（比如 BigInteger）， 也不能直接将输入的字符串转换为整数形式。

示例 1：
输入：num1 = "11", num2 = "123"
输出："134"

示例 2：
输入：num1 = "456", num2 = "77"
输出："533"

示例 3：
输入：num1 = "0", num2 = "0"
输出："0"

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14

    思路：

    1、双指针解法

    /**
     * 双指针解法：时间复杂度为O(n)
     */
public String addStrings(String num1, String num2) {
    StringBuilder str = new StringBuilder("");
    int i = num1.length() - 1,j = num2.length() - 1;
    int temp = 0;
    while (i >= 0 || j >= 0) {
        int n1 = i >= 0 ? num1.charAt(i) - '0' : 0;
        int n2 = j >= 0 ? num2.charAt(j) - '0' : 0;
        int sum = n1 + n2 + temp;
        temp = sum / 10;
        str.append(sum % 10);
        i--;
        j--;
    }
    if (temp == 1){
        str.append(1);
    }
    return str.reverse().toString();
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21

    比较版本号【中等】

    题目地址：165. 比较版本号

    题目描述：给你两个版本号 version1 和 version2 ，请你比较它们。

    示例 1：
输入：version1 = "1.01", version2 = "1.001"
输出：0
解释：忽略前导零，"01" 和 "001" 都表示相同的整数 "1"

示例 2：
输入：version1 = "1.0", version2 = "1.0.0"
输出：0
解释：version1 没有指定下标为 2 的修订号，即视为 "0"

示例 3：
输入：version1 = "0.1", version2 = "1.1"
输出：-1
解释：version1 中下标为 0 的修订号是 "0"，version2 中下标为 0 的修订号是 "1" 。0 < 1，所以 version1 < version2

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    /**
 * 方式一：双指针移动法
 * 示例：version1 = "1.01", version2 = "1.001"
 *
 * 思路：双指针来进行移动，不断的求对应的值，最后进行比较。
 * 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
 * 内存消耗：39.5 MB, 在所有 Java 提交中击败了30.87%的用户
 */
public int compareVersion(String version1, String version2) {
    int v1Size= 0;
    int v2Size = 0;
    while (v1Size < version1.length() || v2Size < version2.length()) {
        int num1 = 0;
        while (v1Size < version1.length() && version1.charAt(v1Size) != '.') {
            num1 = num1 * 10 + (version1.charAt(v1Size) - '0');
            v1Size++;
        }
        int num2 = 0;
        while (v2Size < version2.length() && version2.charAt(v2Size) != '.') {
            num2 = num2 * 10 + (version2.charAt(v2Size) - '0');
            v2Size++;
        }
        if (num1 > num2) {
            return 1;
        }else if (num1 < num2) {
            return -1;
        }
        v1Size++;
        v2Size++;
    }
    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32

    最小覆盖字串（困难，双指针以及字符哈希）

    题目：76. 最小覆盖子串

    给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
注意：
对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
如果 s 中存在这样的子串，我们保证它是唯一的答案。

示例 1：

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
示例 2：

输入：s = "a", t = "a"
输出："a"
示例 3:

输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19

    解题：通过利用双指针来不断缩减范围来找出最小覆盖的字串。（通过字符哈希，以及左右指针进行移动来进行求解）

    public static void main(String[] args) {
    System.out.println(new 最小覆盖字串().minWindow("ABAACBAB", "ABC"));
}

/**
     * 滑动窗口解题：手写一遍
     * s = "ADOBECODEBANC", t = "ABC"  ======>  ans=3表示是否范围中有了，hash表来进行索引
     */
public String minWindow(String s, String t) {
    int[] hash = new int[128];
    char[] charS = s.toCharArray();
    char[] charT = t.toCharArray();
    for (char c : charT) {
        hash[c]--;
    }
    int ans = 0;//当前范围中命中的情况
    String result = "";
    for (int right = 0,left = 0; right < charS.length; right++) {
        hash[charS[right]]++;
        //当前命中
        if (hash[charS[right]] <= 0) {
            ans++;
        }
        //范围中有命中情况
        //1、缩减窗口范围
        while (ans == t.length() && hash[charS[left]] > 0) {
            hash[charS[left++]]--;
        }
        //2、来进行置换结果集
        if (ans == t.length()) {
            if (result.equals("")  || result.length() > (right - left + 1)) {
                result = s.substring(left, right + 1);
            }
        }
    }
    return result;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37

    其他

    判断字符串组中的元素能否构成目标字符串

    博客：判断“资源字符串”是否可以构成“目标字符串”

    题目：传入一个任意字符串和一个其他字符串，判断第二个字符串可不可以拆分开，构成第一个任意字符串。

    解题思路：字符哈希，将目标字符串中的所有字符加入到对应的组中，接着遍历源字符串中字符依次删除对应的桶，若是<0那么说明不匹配。

    /**
 * @ClassName 判断字符串组中的元素能否构成目标字符串
 * @Author ChangLu
 * @Date 4/18/2022 9:24 PM
 * @Description 大概意思就是传入一个任意字符串和一个其他字符串，判断第二个字符串可不可以拆分开，构成第一个任意字符串
 */
public class 判断字符串组中的元素能否构成目标字符串 {

    public static void main(String[] args) {
        System.out.println(new 判断字符串组中的元素能否构成目标字符串().canConstruct("aa", "aab"));
    }

    /**
     * canConstruct(“a”, “b”) -> false
     * canConstruct(“aa”, “ab”) -> false
     * canConstruct(“aa”, “aab”) -> true
     * 解题思路：字符哈希，时间复杂度O(n)。
     */
    public static boolean canConstruct(String str1, String str2) {
        if (str1.length() > str2.length()) {
            return false;
        }
        //来通过一个字符哈希来解决
        int[] charArr = new int[26];
        for (int i = 0; i < str2.length(); i++) {
            charArr[str2.charAt(i) - 'a']++;
        }
        for (int i = 0; i < str1.length(); i++) {
            charArr[str1.charAt(i) - 'a']--;
            if (charArr[str1.charAt(i) - 'a'] < 0) {
                return false;
            }
        }
        return true;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
  • 相关阅读:
    如何避免新车开发项目中的风险管理？
    【Pytorch实用教程】Pytorch中nn.Sequential的用法
    实现对python源码加密的方法
    MES生产管理系统与供应链协同管理
    【C++】vector的模拟实现不会怎么办？看过来
    Redis主从模式(一)----搭建主从结构并演示
    应用在手机触摸屏中的电容式触摸芯片
    ARM-A架构入门基础（一）预备知识
    【C】 初识C语言
    【数据结构】二叉树
  • 原文地址：https://blog.csdn.net/cl939974883/article/details/126400034