@TOC
字符串循环移位蕴含
编程之美 3.1
s1 = AABCD, s2 = CDAA
Return : true题解： 给定两个字符串 s1 和 s2，要求断定 s2 是否可能被 s1 做循环移位失去的字符串蕴含。
s1 进行循环移位的后果是 s1s1 的子字符串，因而只有判断 s2 是否是 s1s1 的子字符串即可。
字符串循环移位
编程之美 2.17
s = "abcd123" k = 3
Return "123abcd"题解：
将字符串向右循环挪动 k 位。
将 abcd123 中的 abcd 和 123 独自翻转，失去 dcba321，而后对整个字符串进行翻转，失去 123abcd。
字符串中单词的翻转
程序员代码面试指南
s = "I am a student"
Return "student a am I"题解：
将每个单词翻转，而后将整个字符串翻转。
242. 无效的字母异位词 * (简略)
给定两个字符串 s 和 t，编写一个函数来判断 t 是否是 s 的字母异位词。
示例 1:
输出: s = "anagram", t = "nagaram"
输入: true
示例 2:
输出: s = "rat", t = "car"
输入: false阐明:
你能够假如字符串只蕴含小写字母。
进阶:
如果输出字符串蕴含 unicode 字符怎么办？你是否调整你的解法来应答这种状况？
题解：
1. 转换为数组再排序
将两个字符串排序，字母异位词排序后截然不同。
首先判断长度是否相等，不相等间接返回 false;
class Solution {public boolean isAnagram(String s, String t) {
// 长度不相等，立刻返回 false
if (s.length() != t.length()) {return false;}
// 字符串转化为数组
char[] str1 = s.toCharArray();
char[] str2 = t.toCharArray();
// 数组排序
Arrays.sort(str1);
Arrays.sort(str2);
// 数组比拟
return Arrays.equals(str1, str2);
}
}工夫复杂度 O(nlogn)
空间复杂度 O(1): 空间取决于排序实现，如果应用 heapsort，通常须要 O(1) 辅助空间。留神，在 Java 中，toCharArray() 制作了一个字符串的拷贝，所以它破费 O(n) 额定的空间，然而咱们疏忽了这一复杂性剖析，因为：这依赖于语言的细节。这取决于函数的设计形式。例如，能够将函数参数类型更改为 char[]。
2. 桶计数
// 字母桶计数 ver1:
// 若两个字符串长度不等，立刻返回 false
// 先对 s 中字符计数
// 对 t 中字符计数，t 中相应字符计数减 1，若某个字母计数小于 0，立刻返回 false
class Solution {public boolean isAnagram(String s, String t) {int[] table = new int[26];
if (s.length() != t.length()){return false;}
// s 中的字符计数
for (int i= 0; i<s.length(); i++){table[s.charAt(i)-'a']++;
}
// s 计数根底上，t 中相应字符计数减 1
for (int i = 0; i<t.length(); i++){table[t.charAt(i) - 'a']--;
if (table[t.charAt(i) - 'a'] < 0) // 若某一个字符计数小于 0 时，立刻返回 false
return false;
}
return true;
}
}
// 字母桶计数 ver2:
// 若两个字符串长度不等，立刻返回 false
// 先对 s 中字符计数
// 查看字母表是否每个字符计数为 0，不是返回 false
class Solution {public boolean isAnagram(String s, String t) {int[] table = new int[26];
if (s.length() != t.length()){return false;}
// s 中的字符计数
for (int i= 0; i<s.length(); i++){table[s.charAt(i)-'a']++;
table[t.charAt(i)-'a']--;
}
// s 计数根底上，t 中相应字符计数减 1
for (int i = 0; i<26; i++){if (table[i]!=0)
return false;
}
return true;
}
}工夫复杂度 O(n)
空间复杂度 O(1)
409. 最长回文串
给定一个蕴含大写字母和小写字母的字符串，找到通过这些字母结构成的最长的回文串。
在结构过程中，请留神辨别大小写。比方 “Aa” 不能当做一个回文字符串。
留神:
假如字符串的长度不会超过 1010。
示例 1:
输出:
"abccccdd"
输入:
7解释:
咱们能够结构的最长的回文串是 ”dccaccd”, 它的长度是 7。
题解：
对于回文字符串，最多只有一个字符的个数是 1 个，其余字符必为偶数个
用一个桶统计每个呈现的字符的个数。
某字母个数为偶数个，加上该字母个数
某字母个数为奇数个，加上该字母的个数再减 1
若后果长度小于原字符串长度：后果长度再加 1
class Solution {public int longestPalindrome(String s) {
int res = 0;
// 大写和小写字母之间有 6 个其余字符，因而数组大小：52+6
int[] bucket = new int[58];
for (int i = 0; i<s.length(); i++){bucket[s.charAt(i) - 'A'] ++;
}
int flag = 0;
for (int x: bucket){res += x - (x & 1); // 取 x 的最大偶数个，若 x 为奇数，则减 1
}
// 若后果长度比 s 长度小，再加上一个字母的长度
return res<s.length()? res+1: res;}
}工夫复杂度 O(n)
空间复杂度 O(1)
5. 最长回文子串
给定一个字符串 s，找到 s 中最长的回文子串。你能够假如 s 的最大长度为 1000。
示例 1：
输出: "babad"
输入: "bab"
留神: "aba" 也是一个无效答案。示例 2：
输出: "cbbd"
输入: "bb"// 核心扩大
class Solution {public String longestPalindrome(String s) {if (s == null || s.length() < 2) {return s;}
int max_len = 1;
int start = 0;
int n = s.length();
for(int i = 0; i<n; i++){
int left = i-1;
int right = i+1;
while(left>=0 && s.charAt(left) == s.charAt(i)){left--;}
while (right<n && s.charAt(right) == s.charAt(i)){right++;}
while(left>=0 && right<n && s.charAt(left) == s.charAt(right)){
left--;
right++;
}
if (right-left-1 > max_len){
max_len = right-left-1;
start = left+1;
}
}
return s.substring(start, start+max_len);
}
}工夫复杂度 O(n^2)
空间复杂度 O(1)
647. 回文子串
给定一个字符串，你的工作是计算这个字符串中有多少个回文子串。
具备不同开始地位或完结地位的子串，即便是由雷同的字符组成，也会被视作不同的子串。
示例 1：
输出："abc"
输入：3
解释：三个回文子串: "a", "b", "c"示例 2：
输出："aaa"
输入：6
解释：6 个回文子串: "a", "a", "a", "aa", "aa", "aaa"提醒：
输出的字符串长度不会超过 1000。
205. 同构字符串
给定两个字符串 s 和 t，判断它们是否是同构的。
如果 s 中的字符能够被替换失去 t，那么这两个字符串是同构的。
所有呈现的字符都必须用另一个字符替换，同时保留字符的程序。两个字符不能映射到同一个字符上，但字符能够映射本人自身。
示例 1:
输出: s = "egg", t = "add"
输入: true示例 2:
输出: s = "foo", t = "bar"
输入: false示例 3:
输出: s = "paper", t = "title"
输入: true阐明:
你能够假如 s 和 t 具备雷同的长度。
题解：
1. 两个哈希表
依据题意，s 惟一地映射到 t，且 t 惟一地映射到 s.
如 s = "foo", t = "bar" 不同构
o -> a
o -> r
o 映射到了两个字母如 s = "ab", t = "cc" 不同构
a -> c
b -> c
c 被映射了两次
反过来由 t 映射到 s
c -> a
c -> b
c 映射到了两个字母因而须要验证 s->t 成立，且 t->s 成立
class Solution {public boolean isIsomorphic(String s, String t) {Map<Character, Character> map1 = new HashMap<>(); //s->t
Map<Character, Character> map2 = new HashMap<>(); //t->s
for (int i = 0; i < s.length(); i++){//map1 中不蕴含 s[i]的映射, map2 也不蕴含 t[i]的映射，则将 s[i]<->t[i] 退出映射表中
if (!map1.containsKey(s.charAt(i)) && !map2.containsKey(t.charAt(i))){map1.put(s.charAt(i), t.charAt(i));
map2.put(t.charAt(i), s.charAt(i));
}
else{// 若 map1 中存在 s[i]的映射，但 s[i]-/>t[i], 返回 false
if (map1.containsKey(s.charAt(i)) && map1.get(s.charAt(i)) != t.charAt(i))
return false;
// 若 map1 中存在 t[i]的映射，但 t[i]-/>t[i], 返回 false
else if (map2.containsKey(t.charAt(i)) && map2.get(t.charAt(i))!= s.charAt(i))
return false;
}
}
return true;
}
}工夫复杂度 O(n)
空间复杂度 O(n)
2. 一个哈希表
s -> t 与 t -> s 两个方向分次进行
class Solution {public boolean isIsomorphic(String s, String t) {return help(s, t) && help(t, s);
}
public boolean help(String s, String t){Map<Character, Character> map = new HashMap<>();
for (int i = 0; i< s.length(); i++){char ch1 = s.charAt(i);
char ch2 = t.charAt(i);
if (!map.containsKey(ch1)){map.put(ch1, ch2);
}
else if (map.get(ch1) != ch2)
return false;
}
return true;
}
}工夫复杂度 O(n)
空间复杂度 O(n)
9. 回文数
判断一个整数是否是回文数。回文数是斧正序（从左向右）和倒序（从右向左）读都是一样的整数。
示例 1:
输出: 121
输入: true示例 2:
输出: -121
输入: false
解释: 从左向右读, 为 -121。从右向左读, 为 121-。因而它不是一个回文数。示例 3:
输出: 10
输入: false
解释: 从右向左读, 为 01。因而它不是一个回文数。进阶:
你能不将整数转为字符串来解决这个问题吗？
题解：
1. 数字转化为字符串
2. 将整个数字翻转
回文数翻转后和原来的数相等。
翻转的形式：
revertedNum = revertedNum*10 + temp%10;
temp = temp/10;
class Solution {
public boolean isPalindrome(int x) {if (x<0 || ( x%10 == 0 && x!=0)){ // 留神边界条件
return false;
}
int temp = x;
int revertedNum = 0;
while (temp > 0){
revertedNum = revertedNum*10 + temp%10;
temp = temp/10;
}
return x == revertedNum;
}}
工夫复杂度 O(log10(n))
空间复杂度 O(1)
**3. 翻转一半的数 **
翻转了一半时：x < revertedNum
同时留神，当原数有奇数位数时，翻转后的数会多一位，只有再除以 10 而后比拟即可。最初留神边界条件。- 当 x 为正数时，不是回文数
- 当 x 非 0，但最初一位为 0 时，不是回文数class Solution {
public boolean isPalindrome(int x) {if (x<0 || ( x%10 == 0 && x!=0)){ // 留神边界条件
return false;
}
int revertedNum = 0;
while (x > revertedNum){
revertedNum = revertedNum*10 + x%10;
x = x/10;
}
return x == revertedNum || x == revertedNum/10;
}}
工夫复杂度 O(log10(n))
空间复杂度 O(1)
***
## 696. 计数二进制子串
> 给定一个字符串 s，计算具备雷同数量 0 和 1 的非空 (间断) 子字符串的数量，并且这些子字符串中的所有 0 和所有 1 都是组合在一起的。反复呈现的子串要计算它们呈现的次数。** 示例 1 :**
输出: “00110011”
输入: 6
解释: 有 6 个子串具备雷同数量的间断 1 和 0：“0011”，“01”，“1100”，“10”，“0011”和“01”。
> 请留神，一些反复呈现的子串要计算它们呈现的次数。另外，“00110011”不是无效的子串，因为所有的 0（和 1）没有组合在一起。** 示例 2 :**输出: “10101”
输入: 4
解释: 有 4 个子串：“10”，“01”，“10”，“01”，它们具备雷同数量的间断 1 和 0。
** 留神：**
s.length 在 1 到 50,000 之间。s 只蕴含“0”或“1”字符。** 题解：**
**1. 按字符分组 **
将字符串 `s` 转换为 `arr` 数组示意字符串中雷同字符间断块的长度。例如，如果 s=“11000111000000”，则 arr=[2，3，3，6]。- `'0' * k + '1' * k` 或 `'1' * k + '0' * k` 模式的每个二进制字符串，有 k 个子串。- 对于相邻的两个字符块，`arr[i-1]` 和 `arr[i]` 的子串个数为 `min(arr[i-1], arr[i])`
// 按字符分组
class Solution {
public int countBinarySubstrings(String s) {
int res = 0;
int n = s.length();
if (n == 0 || n == 1){return res;}
// 按字符分组，寄存到 arr 中
int[] arr = new int[n];
arr[0] = 1;
int index = 0;
for (int i = 1; i < s.length(); i++){if (s.charAt(i) == s.charAt(i-1)){arr[index]++;
}else{arr[++index] = 1;
}
}
// 计算每个相邻字符块的字串个数
for (int i = 1; i<n; i++){res += Math.min(arr[i], arr[i-1]);
}
return res;
}}
工夫复杂度 O(n)
空间复杂度 O(n)
**2. 线性扫描 **
时时记录后果
class Solution {
public int countBinarySubstrings(String s) {int n = 0, pre = 0, curr = 1, len = s.length()-1;
for (int i = 0; i < len; ++i) {if (s.charAt(i) == s.charAt(i+1))
curr++;
else{
pre = curr;
curr = 1;
}
if (pre >= curr)
++n;
}
return n;
}}
工夫复杂度 O(n)
空间复杂度 O(1)