算法_每日一题(9.7)

每日一题_打卡9.7

1. leetcode344. 反转字符串 ✫

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。

不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

这道题很简单，双指针格式练手，为下一题做铺垫

class Solution {
    public void reverseString(char[] s) {
        int left =0,right = s.length-1;
        while(left<right){
            char temp = s[right];
            s[right] = s[left];
            s[left] = temp;
            left++;
            right--;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

官方答案：
双指针：一前一后。如果nums[i]为0，则会i,j表示的数会交换

class Solution {
    public void moveZeroes(int[] nums) {
       int j=0;
       if(nums == null){
           return;
       }
       for(int i = 0;i<nums.length;i++){
           if(nums[i] !=0){
               int temp = nums[i];
               nums[i] = nums[j];
               nums[j++] = temp; 
           }
       }
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

2. leetcode557. 反转字符串中的单词 III ★

给定一个字符串 s ，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。

示例 1：

输入：s = “Let’s take LeetCode contest” 输出：“s’teL ekat edoCteeL tsetnoc”
示例 2:

输入： s = “God Ding” 输出：“doG gniD”

提示：

1 <= s.length <= 5 * 104 s 包含可打印的 ASCII 字符。 s 不包含任何开头或结尾空格。 s 里 至少
有一个词。 s 中的所有单词都用一个空格隔开。

这个题是在上个题基础上增添更多的实现，这里的话我借鉴了上一个题，还是使用双指针反转
split()方法：分隔字符串
split(" “) 仅分隔一个空格
split(”\t") 分隔空格
split(“\s”) 正则表达式：表示匹配惹你有空白字符，+表示匹配一次或多次
split(“\s+”) 分隔一个或者多个空格
下面是我自己的做法，耗费的时间空间都很大

class Solution {
    public String reverseWords(String s) {
        StringBuffer b = new StringBuffer(s);
        String c = b.reverse().toString();
        String a[] = c.split(" ");
        reverse(a);
        String m ="";
        for(int i = 0;i<a.length;i++){
            if(i==a.length-1){
                m+=a[i];
            }else{
                m+=a[i]+" ";
            }
        }
        return m;
    }
    public void reverse(String [] a){
        int left =0,right =a.length-1;
        while(left<right){
            String d = a[left];
            a[left]= a[right];
            a[right] = d;
            left++;
            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

官方的解答：
通过i的位置变化，来记下空格的位置，然后再倒着存瑞StringBuffer中，以此类推

class Solution {
public string reverseWords(string s) {
        string ret;
        int length = s.length();
        int i = 0; 
        while (i < length) {
            int start = i;
            while (i < length && s[i] != ' ') {
                i++;
            }
            for (int p = start; p < i; p++) {
                ret.push_back(s[start + i - 1 - p]);
            }
            while (i < length && s[i] == ' ') {
                i++;
                ret.push_back(' ');
            }
        }
        return ret;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21