翻转字符串的相关题目

摘要：一题目描述空格分隔，逐个反转二题目描述三题目描述当然也可以用的做，不过用双指针更快。

LeetCode: 557. Reverse Words in a String III

Given a string, you need to reverse the order of characters in each word within a sentence while still preserving whitespace and initial word order.

Example 1:

Input: "Let"s take LeetCode contest"

Output: "s"teL ekat edoCteeL tsetnoc"

Note: In the string, each word is separated by single space and there will not be any extra space in the string.

空格分隔，逐个反转

class Solution {
    public String reverseWords(String s) {
        
        String[] ss = s.split(" ");
        StringBuilder sb = new StringBuilder();
        int n = ss.length;
        
        for (int i = 0; i < n - 1; i++) {
            sb.append(reverse(ss[i]) + " ");
        }
        sb.append(reverse(ss[n - 1]));
        
        return sb.toString();
    }
    
    public String reverse(String str) {
        StringBuilder sb = new StringBuilder(str);
        return sb.reverse().toString();
    }
}
    

LeetCode: 541. Reverse String II

Given a string and an integer k, you need to reverse the first k characters for every 2k characters counting from the start of the string. If there are less than k characters left, reverse all of them. If there are less than 2k but greater than or equal to k characters, then reverse the first k characters and left the other as original.

Example:

Input: s = "abcdefg", k = 2

Output: "bacdfeg"

Restrictions:

The string consists of lower English letters only.

Length of the given string and k will in the range [1, 10000]

class Solution {
    public String reverseStr(String s, int k) {
        
        int n = s.length();
        int i = 0, j = n - 1;
        char[] c = s.toCharArray();
        
        while (i < n) {
            j = Math.min(i + k - 1, n - 1);
            reverse(c, i, j);
            i += 2 * k;
        }
        
        return new String(c);
        
    }
    
    public void reverse(char[] c, int i, int j) {
        while (i < j) {
            char temp = c[i];
            c[i] = c[j];
            c[j] = temp;
            i++;
            j--;
        }
    }
}

LeetCode: 344. Reverse String

Write a function that takes a string as input and returns the string reversed.

Example:

Given s = "hello", return "olleh".

当然也可以用 StringBuilder 的 reverse 做，不过用双指针更快。

class Solution {
    public String reverseString(String s) {
        
        int len = s.length();
        int left = 0, right = len - 1;
        char[] c = s.toCharArray();
        
        while(left < right) {
            char temp = c[left];
            c[left] = c[right];
            c[right] = temp;
            left++;
            right--;
        }
        
        return new String(c);
        
    }
}

LeetCode: 345. Reverse Vowels of a String

Write a function that takes a string as input and reverse only the vowels of a string.

Example 1:

Given s = "hello", return "holle".

Example 2:

Given s = "leetcode", return "leotcede".

Note:

The vowels does not include the letter "y".

同样地，双指针，注意考虑 vowel 的大小写

class Solution {
    public String reverseVowels(String s) {
        // a e i o u
        int len = s.length();
        int left = 0, right = len - 1;
        char[] c = s.toCharArray();
        
        while(left < right) {
            if (isVowel(c[left]) && isVowel(c[right])) {
                char temp = c[left];
                c[left] = c[right];
                c[right] = temp;
                left++;
                right--;
            } else if (!isVowel(c[left]))
                left++;
            else right--;
        }
        
        return new String(c);
    }
    
    public boolean isVowel(char c) {
        return c == "a" || c == "A"
           || c == "e" || c == "E"
           || c == "i" || c == "I"
           || c == "o" || c == "O"
           || c == "u" || c == "U";
    }
}

LeetCode: 11. Container With Most Water

Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container and n is at least 2.

首先理解题意，就是找一个最大的容器容纳最多的水，这个容器由两个板子组成，每个 an 在数组中的值就是这个板子的高度，画一下图就更清晰了。

[2,1,2] 模拟画图 ≡ω≡

|   |
| | |     板子...
--------- x轴
0 1 2     数组下标

然后抽象出来就是求 (j - i) * Math.min(height[i], height[j]) 的最大值

暴力算法很容易想到，但是会超时

有一种 O(n) 的做法，但是不是很好理解，discuss 里有比较清楚的讲解 Yet another way to see what happens in the O(n) algorithm-algorithm)

我理解的核心思想是突破那个短板，如果左边的短，就移动左边的板子，如果右边的短，就移动右边的板子，看能不能形成更大的容器。

class Solution {
    public int maxArea(int[] height) {
        
        int n = height.length;
        int max = 0;
        int i = 0, j = n - 1;
        
        while (i < j) {
            max = Math.max(max, Math.min(height[i], height[j]) * (j - i));
            if (height[i] < height[j])
                i++;
            else
                j--;
        }
        
        return max;
    }
}