代码随想录算法训练营day08 | leetcode 344.反转字符串/541. 反转字符串II / 剑指Offer05.替换空格/151.翻转字符串里的单词/剑指Offer58-II.左旋转字符串

基础知识

// String -> char[]

char[] string=s.toCharArray();

// char[] -> String

String.valueOf(string)

注意replace replaceAll区别，都是全局匹配替换，不过replaceAll是正则匹配

LeetCode 344.反转字符串

分析1.0

基础的前后指针元素互换

class Solution {

    public void reverseString(char[] s) {

        if(s==null){

            return;

        }

        int len=s.length;

        if(len==0 || len==1){

            return;

        }

        int left=0, right=len-1;

        while(left<right){

            char temp=s[right];

            s[right]=s[left];

            s[left]=temp;

            left++;

            right--;

        }

        return;

    }

}

LeetCode 541. 反转字符串II

分析1.0

涉及多次反转，考虑写一个根据索引反转字符串的函数，反转部分之后，考虑剩下的元素个数；

String -> StringBuilder 或者采用字符数组的方式处理

class Solution {

    public String reverseStr(String s, int k) {

        int len=s.length();

        if(s==null){

            return null;

        }

        char[] string=s.toCharArray();

        int endIndex=len-1;

        int startIndex=0;

        while(startIndex<=endIndex){

            //System.out.println("start position: "+startIndex);

            int gap=endIndex-startIndex+1;

            //System.out.println("gap: "+gap);

            if(gap<k){

                reverse(string, startIndex, endIndex);

                break;

            }else if(gap<2*k && gap>=k){

                reverse(string, startIndex, startIndex+k-1);

                break;

            }else{

                reverse(string, startIndex, startIndex+k-1);

                startIndex=startIndex+2*k;

            }

            //System.out.println(string);

        }

        return String.valueOf(string);

    }

    public void reverse(char[] s, int left, int right){

        while(left<right){

            char temp=s[left];

            s[left]=s[right];

            s[right]=temp;

            left++;

            right--;

        }

    }

}

LeetCode

分析1.0

直接用了API

class Solution {

    public String replaceSpace(String s) {

        return s.replace(" ","%20");

    }

}

LeetCode 151.翻转字符串里的单词

分析1.0

遍历，遍历过程中去除多余空格，将获得的一个一个单词采用尾插法加入List<StringBuilder>,最后再使用空格拼接

获取单词首指针、检查合法性、获取尾指针

class Solution {

    public String reverseWords(String s) {

        if(s==null){

            return null;

        }

        // s=s.trim();

        ArrayDeque<String> stack = new ArrayDeque();

        int len=s.length();

        int leftIndex=0, rightIndex=0;

        while(leftIndex<len){

            // 获取s中每个单词的起始索引

            while(leftIndex<len && s.charAt(leftIndex)==' '){

                    leftIndex++;

            }

            // 这里要注意跳出

            if(leftIndex>=len){

                break;

            }

            rightIndex=leftIndex;

            while(rightIndex<len && s.charAt(rightIndex)!=' '){

                rightIndex++;

            }// 此时rightIndex指向某个单词的最后一个字符的索引的后面的空格

            String temp=s.substring(leftIndex, rightIndex);

            System.out.println("----"+temp);

            stack.push(temp);

            leftIndex=rightIndex;

        }

        StringBuilder ans = new StringBuilder();

        while(!stack.isEmpty()){

            ans.append(stack.pop())

               .append(" ");

        }

        // return ans.toString().trim(); 二者都行

        return ans.substring(0, ans.length()-1);

    }

}

失误

每次获取一个单词前都要检查当前额left指针是否超过了s的长度

substring() 要小写 subString()是错的

分析2.0

反转s，再反转所有的单词

采用trim()方法去除收尾多余空格，再用replaceAll()

LeetCode 剑指Offer58-II.左旋转字符串

分析1.0

相当于逻辑左移所有字符串元素，左移个数如果是元素个数的倍数，那就不移动，即要将移动次数对字符串长度取余，再向左移动，增加字符串空间，取余后的索引为n的元素为新的首元素，将原字符串截断后拼接即可

class Solution {

    public String reverseLeftWords(String s, int n) {

        int len=s.length();

        n=n%len;

        String s1=s.substring(0,n);

        String s2=s.substring(n,len);

        return s2+s1;

    }

}

分析2.0

反转两个局部，再整体反转

总结

数组长度 arr.length 字符串长度 s.length()
双指针-前后指针、快慢指针、滑动窗口降低时间复杂度利器
工具：Arrays、Collections、队列、栈(逆序好帮手)、哈希表/map
substring() 要小写 subString()是错的
s.trim().replaceAll("\\s+", " ") 去除收尾多余空格并将字符串内多余空格变成一个空格

常用变量名增量更新

size、val、ans、cnt、cur、pre、next、left、right、index、gap、tar、res、src、len、start、end

巴特西

代码随想录算法训练营day08 | leetcode 344.反转字符串/541. 反转字符串II / 剑指Offer05.替换空格/151.翻转字符串里的单词/剑指Offer58-II.左旋转字符串

基础知识

LeetCode 344.反转字符串

LeetCode 541. 反转字符串II

LeetCode

LeetCode 151.翻转字符串里的单词

LeetCode 剑指Offer58-II.左旋转字符串

分析2.0

总结

常用变量名增量更新

最新文章

热门文章