[数据结构与算法] LeetCode刷题第七天

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> LeetCode刷题第七天 -> 正文阅读

[数据结构与算法]LeetCode刷题第七天

LeetCode 344

看到题目的第一想法
使用双指针的方式，交换前后字符即可
看完题解后的想法
采用双指针

class Solution {
    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;
        }
    }
}

遇到的困难
无

LeetCode 541

看到题目的第一想法
对不同的类型分别进行处理，首先剥离出一个翻转字符串的函数，然后分别对前2K的前K个进行翻转，大于k的翻转不足2K，翻转前k，不足k的，全部翻转，这样的话条件变复杂
看完题解后的想法
每次向前遍历的时候不要挨个挨个遍历，可以直接跳跃2k，然后判断前k翻转，之后不足k的到尾部了，全部翻转即可

class Solution {
    public void reverSubString(char[] arr, int start, int end){
        for(int i=start,j=end;i<j;i++,j--){
            char temp=arr[i];
            arr[i]=arr[j];
            arr[j]=temp;
        }
    }
    public String reverseStr(String s, int k) {
        char[] c = s.toCharArray();
        for(int i=0;i<s.length();i+=(2*k)){
            if(i+k<=s.length()){
                reverSubString(c,i,i+k-1);
                continue;
            }
            reverSubString(c,i,c.length-1); //不足k
        }
        return new String(c);
    }
}

遇到的困难
每次向前翻转2K个，并且不足k的时候说明到字符串末尾，然后这时候直接执行后面的语句即可，之前的只要大于k的就翻转前k个即可。

LeetCode 剑指05

看到题目的第一想法
重新定义一个新的数组，因为每次都要进行替换，也就是长度要加2，因为多余了两个。然后再判断的时候如果等于‘ ’就替换，不等于就直接赋值，这样的做法首先定义了一个多余的存储空间。

class Solution {
    public String replaceSpace(String s) {
        char[] arr=s.toCharArray();
        int lengthArr=arr.length;
        for(int i=0;i<arr.length;i++){
            if(arr[i]==' '){
                lengthArr+=2;
            }
        }
        char[] result=new char[lengthArr];
        for(int i=result.length-1,j=arr.length-1;j<i;i--,j--){
            if(arr[j]!=' '){
                result[i]=arr[j];
            }else{
                result[i--]='0';
                result[i--]='2';
                result[i]='%';
            }
        }
        return new String(result);
    }
}

看完题解后的想法
用思路是一样的，都是从后往前赋值，这样避免了从前往后造成的依次往后排，但是这里使用的是StringBuilder，并且，如果出现了‘ ’，然后Stringbuilder加上了两个空格，然后把这两个空格转成字符串并添加到原来字符串的后面，这样相当于还是在原来的字符串上进行操作。类似于

"I am"
"I am  "
    | |
    i j

class Solution {
    public String replaceSpace(String s) {
        StringBuilder sb=new StringBuilder();
        for(int i=0;i<s.length();i++){
            if(s.charAt(i)==' '){
                sb.append("  ");
            }
        }
        int oldlength=s.length();
        s+=sb.toString();
        char[] arr=s.toCharArray();
        for(int i=oldlength-1,j=arr.length-1;i<j;i--,j--){
            if(arr[i]!=' '){
                arr[j]=arr[i];
            }else{
                arr[j--]='0';
                arr[j--]='2';
                arr[j]='%';
            }
        }
        return new String(arr);
    }
}

遇到的困难
StringBuilder使用来添加两个空格字符串，并且要想到在同一个字符数组上操作。

LeetCode 151

看到题目的第一想法
一个是去除多余的空格，然后翻转这个字符串，再针对每个单词进行翻转。但是这里对于空格去除不清楚

class Solution {
    public String reverseWords(String s) {
        char[] arr=s.toCharArray();
        String s1=minusSpaces(arr);

    }
    public String minusSpaces(char[] arr){
        int count=arr.length;
        for(int i=0,j=arr.length-1;i<j;i++,j--){
            while(arr[i]==' ' || arr[j]==' '){
                count--;
            }
        }
    }
    public void reverseStr(char[] arr, int start, int end){
        for(int i=start,j=end;i<j;i++,j--){
            char temp=arr[i];
            arr[i]=arr[j];
            arr[j]=temp;
        }
    }
}

看完题解后的想法
思路上一样，对于空格的去除可以使用双指针的方式，去除所有空格，然后给每一个单词后分别加上空格。（参考数组部分的去除元素），然后在翻转每一个单词的时候注意，遇到空格翻转空格之前的，然后把Start指针放到空格后第一个。

class Solution {
    public char[] removeSpace(char[] chars) {
        int slow = 0;
        for (int fast = 0; fast < chars.length; fast++) {
            //先用 fast 移除所有空格
            if (chars[fast] != ' ') {
                //在用 slow 加空格。 除第一个单词外，单词末尾要加空格
                if (slow != 0)
                    chars[slow++] = ' ';
                //fast 遇到空格或遍历到字符串末尾，就证明遍历完一个单词了
                while (fast < chars.length && chars[fast] != ' ')
                    chars[slow++] = chars[fast++];
            }
        }
        //相当于 c++ 里的 resize()
        char[] newChars = new char[slow];
        System.arraycopy(chars, 0, newChars, 0, slow); 
        return newChars;
    }
    public void reversestr(char[] a,int start, int end){
        for(int i=start,j=end;i<j;i++,j--){
            char c=a[i];
            a[i]=a[j];
            a[j]=c;
        }
    }
    public void reverseEachWord(char[] chars) {
        int start = 0;
        //end <= s.length() 这里的 = ，是为了让 end 永远指向单词末尾后一个位置，这样 reverse 的实参更好设置
        for (int end = 0; end <= chars.length; end++) {
            // end 每次到单词末尾后的空格或串尾,开始反转单词
            if (end == chars.length || chars[end] == ' ') {
                reversestr(chars, start, end - 1);
                start = end + 1;
            }
        }
    }
    public String reverseWords(String s) {
        char[] arr = s.toCharArray();
        char[] result = removeSpace(arr);
        reversestr(result,0,result.length-1);
        reverseEachWord(result);
        return new String(result);
    }
}

遇到的困难
去除空格操作不清楚

LeetCode 剑指58

看到题目的第一想法
把前面的n个元素添加到末尾，然后去除前面n个元素重新开始并把这个字符串返回。

class Solution {
    public String reverseLeftWords(String s, int n) {
        if(s=="" || n==0){
            return s;
        }
        StringBuilder sb = new StringBuilder();
        StringBuilder sb1 = new StringBuilder();
        sb.append(s);
        int i=0;
        for(;i<n;i++){
            sb.append(s.charAt(i));
        }
        String s1=sb.toString();
        for(;i<s1.length();i++){
            sb1.append(s1.charAt(i));
        }
        return sb1.toString();
    }
}

看完题解后的想法

先翻转前n个，然后翻转剩下的，最后翻转整体的就是我们想要的结果

class Solution {
    public String reverseLeftWords(String s, int n) {
        StringBuilder sb = new StringBuilder();
        sb.append(s);
        revereStr(sb,0,n-1);
        revereStr(sb,n,s.length()-1);
        revereStr(sb,0,s.length()-1);
        return sb.toString();
    }
    //这里要用StringBuilder来接收不能使用String
    public void revereStr(StringBuilder sb, int start, int end){
        for(int i=start,j=end;i<j;i++,j--){
            char temp=sb.charAt(i);
            sb.setCharAt(i,sb.charAt(j));//注意这里交换要用setCharAt不能直接用charAt去进行交换，因为获取的是常数不是变量
            sb.setCharAt(j,temp);
        }
    }
}