1.反轉問題

1.1 反轉字符串

原題：力扣344.

要求原地修改。

public void reverseString(char[] s) {if (s == null || s.length() == 0) {return;}int n = s.length;for (int left = 0, right = n - 1; left < right; left++, right--) {char temp = s[left];s[left] = s[right];s[right] = temp;}
}

1.2 K個一組反轉

原題：力扣541.

public String reverseStr(String s, int k) {if (s == null || s.length() == 0) {return s;}int n = s.length();char[] arr = s.toCharArray();for (int i = 0; i < n; i += 2 * k) {reverse(arr, i, Math.min(i + k, n) - 1);}return new String(arr);
}
public void reverse(char[] arr, int left, int right) {while (left < right) {char temp = arr[left];arr[left] = arr[right];arr[right] = temp;left++;right--;}
}

1.3 僅僅反轉字母

原題：力扣917.

1.轉換為數組，使用雙指針，兩個都指向字母就互換位置，否則就移動不是指向字母的指針。

class Solution {public String reverseOnlyLetters(String s) {if (s == null || s.length() == 0) {return s;}int left = 0, right = s.length() - 1;char[] arr = s.toCharArray();while (left < right) {if (Character.isLetter(arr[left]) && Character.isLetter(arr[right])) {char temp =  arr[left];arr[left] = arr[right];arr[right] = temp;left++;right--;} else if (Character.isLetter(arr[left])) {right--;} else if (Character.isLetter(arr[right])) {left++;} else {left++;right--;}}return new String(arr);}
}

2.使用棧。

class Solution {public String reverseOnlyLetters(String s) {Stack<Character> letters = new Stack();for (char c : s.toCharArray()) {if (Character.isLetter(c)) {letters.push(c);}}StringBuilder ans = new StringBuilder();for (char c : s.toCharArray()) {if (Character.isLetter(c)) {ans.append(letters.pop());} else {ans.append(c);}}return ans.toString();}
}

3.維護一個指針從后向前遍歷數組，需要字母的時候使用。

class Solution {public String reverseOnlyLetters(String s) {if (s == null || s.length() == 0) {return s;}StringBuilder ans = new StringBuilder();int j = s.length() - 1;for (int i = 0; i < s.length(); i++) {if (Character.isLetter(s.charAt(i))) {while (!Character.isLetter(s.charAt(j))) {j--;}ans.append(s.charAt(j--));} else {ans.append(s.charAt(i));}}return ans.toString();}
}

1.4 反轉字符串里的單詞

原題：力扣151.

1.調用API。

public String reverseWords(String s) {if (s == null || s.length() == 0) {return s;}s = s.trim();List<String> wordList = Arrays.asList(s.split("\\s+"));Collections.reverse(wordList);return String.join(" ", wordList);
}

2.自己實現。

class Solution {public String reverseWords(String s) {StringBuilder sb = trimSpaces(s);reverse(sb, 0, sb.length() - 1);reverseEachWord(sb);return sb.toString();}public StringBuilder trimSpaces(String s) {int left = 0, right = s.length() - 1;while (left <= right && s.charAt(left) == ' ') {left++;}while (left <= right && s.charAt(right) == ' ') {right--;}StringBuilder sb = new StringBuilder();while (left <= right) {char c = s.charAt(left);if (c != ' ') {sb.append(c);} else if (sb.charAt(sb.length() - 1) != ' ') {sb.append(c);}left++;}return sb;}// 將整個字符串進行翻轉public void reverse(StringBuilder sb ,int left, int right) {while (left < right) {char temp = sb.charAt(left);// String 沒有這個方法，但是 StringBuilder 和 StringBuffer 可以使用// 將指定索引處修改為指定的 char 類型值sb.setCharAt(left++, sb.charAt(right));sb.setCharAt(right--, temp);}}// 針對每個單詞進行翻轉public void reverseEachWord(StringBuilder sb) {int n = sb.length();int start = 0, end = 0;while (start < n) {while (end < n && sb.charAt(end) != ' ') {end++;}reverse(sb, start, end - 1);start = end + 1;end++;}}
}

2.驗證回文串

原題：力扣125.

public boolean isPalindrome(String s) {if (s == null || s.length() == 0) {return s;}StringBuffer sgood = new StringBuffer();int length = s.length();for (int i = 0; i < length; i++) {char ch = s.charAt(i);if (Character.isLetterOrDigit(ch) {sgood.append(Character.toLowerCase(ch));}}int n = sgood.length();int left = 0, right = n - 1;while (left < right) {if (sgood.charAt(left) != sgood.charAt(right)) {return false;}left++;right--;}return true;
}

3.字符串中的第一個唯一字符

原題：力扣387.

public int firstUniqChar(String s) {if (s == null || s.length() == 0) {return 0;}Map<Character, Integer> frequency = new HashMap<>();for (int i = 0; i < s.length(); i++) {char ch = s.charAt(i);frequency.put(ch, frequency.getOrDefault(ch, 0) + 1);}for (int i = 0; i < s.length(); i++) {if (frequency.get(s.charAt(i)) == 1) {return i;}}return -1;
}

4.判定是否互為字符重排

原題：力扣242.

只需要判斷字符種類以及每個種類出現的次數是否相同，相同則可以重排。

public boolean checkPermutation(String s1, String s2) {if (s1.length() != s2.length()) {return false;}char[] s1Chars = s1.toCharArray();Map<Character, Integer> s1Map = getMap(s1);Map<Character, Integer> s2Map = getMap(s2);for (char s1Char : s1Chars) {if (!s2Map.containsKey(s1Char) || (int)s2Map.get(s1Char) != (int)s1Map.get(s1Char)) {return false;}}return true;
}public Map<Character, Integer> getMap(String str) {Map<Character, Integer> map = new HashMap<>();char[] chars = str.toCharArray();for (char aChar : chars) {map.put(aChar, map.getOrDefault(aChar, 0) + 1);}return map;
}

如果對您有幫助，請點贊關注支持我，謝謝！?
如有錯誤或者不足之處，敬請指正！?
個人主頁：星不易 ?
算法通關村專欄：不易|算法通關村 ?