@TOC
字符串循环移位蕴含
编程之美 3.1
s1 = AABCD, s2 = CDAAReturn : true题解： 给定两个字符串 s1 和 s2，要求断定 s2 是否可能被 s1 做循环移位失去的字符串蕴含。
s1 进行循环移位的后果是 s1s1 的子字符串，因而只有判断 s2 是否是 s1s1 的子字符串即可。
字符串循环移位
编程之美 2.17
s = "abcd123" k = 3Return "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，立刻返回falseclass 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，不是返回falseclass 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 -> ao -> ro 映射到了两个字母如s = "ab", t = "cc"不同构a -> cb -> cc 被映射了两次反过来由 t 映射到 sc -> a c -> bc 映射到了两个字母因而须要验证 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)