Cyc2018
1、字符串循环移位包含
//思路：s1s1包含s2即可
public boolean strCycleMoveInclude(String s1, String s2) {
s1 = s1.concat(s1);
return s1.contains(s2);
}
2、字符串循环移位
// 分两段分别旋转，最后全部旋转
public String moveKstr(String s, int k) {
int len = s.length();
if (len <= 1) return s;
k = k % len;
char[] chars = s.toCharArray();
reverse(chars, 0, len - k - 1);
reverse(chars, len - k, len - 1);
reverse(chars, 0, len - 1);
return new String(chars);
}
public void reverse(char[] chars, int start, int end) {
if (end - start <= 0) {
return;
}
while (start < end) {
char c = chars[start];
chars[start] = chars[end];
chars[end] = c;
start++;
end--;
}
}
3、字符串的单词翻转
// 先单个单词反转，然后整个字符串反转
public String stringReverse(String s) {
int len = s.length();
char[] chars = s.toCharArray();
int left = 0;
for (int right = 0; right < len; right++) {
if (chars[right] == ' ') {
reverse(chars, left, right - 1);
left = right + 1;
}
}
reverse(chars, left, len - 1);
reverse(chars, 0, len - 1);
return new String(chars);
}
public void reverse(char[] chars, int start, int end) {
if (end - start <= 0) {
return;
}
while (start < end) {
char c = chars[start];
chars[start] = chars[end];
chars[end] = c;
start++;
end--;
}
}
4、两个字符串包含的字符是否完全相等, L424
// 思路：利用字符频率数组来判断是否字符数量相等
class Solution {
public boolean isAnagram(String s, String t) {
int[] freq = new int[26];
if (s.length() != t.length())
return false;
for (int i = 0; i < s.length(); i++) {
freq[s.charAt(i) - 'a']++;
}
for (int i = 0; i < s.length(); i++) {
freq[t.charAt(i) - 'a']--;
if (freq[t.charAt(i) - 'a'] < 0) {
return false;
}
}
return true;
}
}
5、计算一组字符集合可以组成的回文字符串的最大长度, L409
// 思路：统计频率，取每个字符的最大偶数数量相加
class Solution {
public int longestPalindrome(String s) {
int[] freq = new int[256];
for(int i = 0; i < s.length(); i++) {
freq[s.charAt(i)]++;
}
int sum = 0;
for (int num : freq) {
sum += num - num % 2;
}
if (sum < s.length()) { // 注意判断是否要加上1，和判断方式
sum++;
}
return sum;
}
}
6、字符串同构, L205
// 思路：有映射关系的字符，位置是一样的，可以通过记录上一次字符出现的位置来判断是否同构
class Solution {
public boolean isIsomorphic(String s, String t) {
int[] sPost = new int[256];
int[] tPost = new int[256];
for (int i = 0; i < s.length(); i++) {
int sc = s.charAt(i);
int tc = t.charAt(i);
if (sPost[sc] != tPost[tc]) {
return false;
}
sPost[sc] = i + 1;
tPost[tc] = i + 1;
}
return true;
}
}
// 思路：利用两个map完成双映射关系
// 注意：通过一个map完成可能会出现两个不同的字符映射到同一个字符上
class Solution1 {
public boolean isIsomorphic(String s, String t) {
Map<Character, Character> mapSt = new HashMap<>();
Map<Character, Character> mapTs = new HashMap<>();
for (int i = 0; i < s.length(); i++) {
char sc = s.charAt(i);
char tc = t.charAt(i);
if (!mapSt.containsKey(sc)) {
mapSt.put(sc, tc);
} else {
if (mapSt.get(sc) != tc) return false;
}
if (!mapTs.containsKey(tc)) {
mapTs.put(tc, sc);
} else {
if (mapTs.get(tc) != sc) return false;
}
}
return true;
}
}
7、回文子字符串个数, L647
// 思路：每个字符串从中心向外扩张，判断是否是回文子串，分为奇偶情况考虑就考虑全了
// 收获：合理设置变量可以极大的方便编程，如这里的start，end
class Solution {
public int countSubstrings(String s) {
int cnt = 0;
for (int i = 0; i < s.length(); i++) {
cnt += cntSub(s, i, i) + cntSub(s, i, i + 1);
}
return cnt;
}
public int cntSub(String s, int start, int end) {
int cnt = 0;
while(start >= 0 && end < s.length() && s.charAt(start) == s.charAt(end)) {
cnt++;
start--;
end++;
}
return cnt;
}
}
8、判断一个整数是否是回文数，L8
class Solution {
public boolean isPalindrome(int x) {
if (x == 0) {
return true;
}
if (x < 0 || x % 10 == 0) {
return false;
}
int right = 0;
while (x > right) {
right = right * 10 + x % 10;
x /= 10;
}
return x == right || x == right / 10;
}
}
- 统计二进制字符串中连续 1 和连续 0 数量相同的子字符串个数, L696
// 对上一种解法的改进，用一个preCnt变量去减少空间使用和循环次数
class Solution {
public int countBinarySubstrings(String s) {
List<Integer> cnt = new ArrayList<>();
int left = 0;
int preCnt = 0;
int res = 0;
for (int right = 1; right < s.length(); right++) {
if (s.charAt(right - 1) != s.charAt(right)) {
res += Math.min(preCnt, right - left);
preCnt = right - left;
left = right;
}
}
res += Math.min(preCnt, s.length() - left);
return res;
}
}
// 思路：把字符串分组，然后相邻字符串的子串个数为Math.min(a ,b);
class Solution1 {
public int countBinarySubstrings(String s) {
List<Integer> cnt = new ArrayList<>();
// 先分组
int left = 0;
for (int right = 1; right < s.length(); right++) {
if (s.charAt(right) != s.charAt(right-1)) {
cnt.add(right - left);
left = right;
}
}
cnt.add(s.length() - left);
// 然后计算结果
int res = 0;
for (int i = 1; i < cnt.size(); i++) {
res += Math.min(cnt.get(i-1), cnt.get(i));
}
return res;
}
}
Carl
1、反转字符串，L344
class Solution {
public void reverseString(char[] s) {
int n = s.length;
if (n <= 1) return;
for (int left = 0, right = n - 1; left < right; left++, right--) {
char tmp = s[left];
s[left] = s[right];
s[right] = tmp;
}
}
}
2、反转字符串II，L541
class Solution {
public String reverseStr(String s, int k) {
int n = s.length();
int start = 0;
int end = k - 1;
char[] chars = s.toCharArray();
while (end < n) {
reverse(chars, start, end);
start += 2 * k;
end += 2 * k;
}
if (n + k > end) { // 注意这里的条件，无需更多的判断
reverse(chars, start, n - 1);
}
return new String(chars);
}
public void reverse(char[] s, int start, int end) {
for (;start < end; start++, end--) {
char tmp = s[start];
s[start] = s[end];
s[end] = tmp;
}
}
}
3、替换空格 剑指Offer 05
// 用一个StringBuilder完成即可
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("%20");
} else {
sb.append(s.charAt(i));
}
}
return sb.toString();
}
}
4、翻转字符串里的单词, L151
class Solution {
public String reverseWords(String s) {
s = s.trim();
StringBuilder sb = new StringBuilder();
int left = 0;
int right = 0;
int indexOfSb = 0;
for (; right < s.length(); right++) {
if (s.charAt(right) == ' ') {
if (s.charAt(left) == ' ') {
left++;
} else {
sb.append(s.substring(left, right));
reverse(sb, indexOfSb, indexOfSb + right - left - 1);
sb.append(' ');
indexOfSb += right - left + 1;
left = right + 1;
}
}
}
sb.append(s.substring(left, right));
reverse(sb, indexOfSb, indexOfSb + right - left - 1);
reverse(sb, 0, indexOfSb + right - left - 1);
return sb.toString();
}
public void reverse(StringBuilder sb, int start, int end) {
while(start < end) {
char tmp = sb.charAt(start);
sb.setCharAt(start, sb.charAt(end));
sb.setCharAt(end, tmp);
start++;
end--;
}
}
}
5、KMP
// KMP算法
class Solution {
public int strStr(String haystack, String needle) {
int[] next = getNextArr(needle);
int index = 0;
for (int i = 0; i < haystack.length(); i++) {
while (index > 0 && haystack.charAt(i) != needle.charAt(index)) {
index = next[index - 1];
}
if (haystack.charAt(i) != needle.charAt(index)) {
index++;
}
if (index == needle.length()) {
return i - needle.length() + 1;
}
}
return -1;
}
public int[] getNextArr(String needle) {
int[] next = new int[needle.length()];
next[0] = 0;
int j = 0;
for (int i = 1; i < next.length; i++) {
while (j > 0 && needle.charAt(j) != needle.charAt(i)) {
j = next[j - 1];
}
if (needle.charAt(j) == needle.charAt(i)) {
j++;
next[i] = j;
}
}
return next;
}
}
