字母异位词
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
输入: s = "anagram", t = "nagaram"
输出: true
方法一：排序
public boolean isAnagram(String s, String t) {
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);
}
方法二：哈希表
public boolean isAnagram(String s, String t) {
if (s.length() != t.length()) {
return false;
}
int[] counter = new int[26];
for (int i = 0; i < s.length(); i++) {
counter[s.charAt(i) - 'a']++;
counter[t.charAt(i) - 'a']--;
}
for (int count : counter) {
if (count != 0) {
return false;
}
}
return true;
}
是否可以被空格拆分为一个或多个
给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。
public class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
Set<String> wordDictSet = new HashSet(wordDict);
boolean[] dp = new boolean[s.length() + 1];
dp[0] = true;
for (int i = 1; i <= s.length(); i++) {
for (int j = 0; j < i; j++) {
if (dp[j] && wordDictSet.contains(s.substring(j, i))) {
dp[i] = true;
break;
}
}
}
return dp[s.length()];
}
}
实现一个 Trie (前缀树)
包含 insert, search, 和 startsWith 这三个操作
class Trie {
private TrieNode root;
public Trie() {
root = new TrieNode();
}
public void insert(String word) {
TrieNode node = root;
for (int i = 0; i < word.length(); i++) {
char currentChar = word.charAt(i);
if (!node.containsKey(currentChar)) {
node.put(currentChar, new TrieNode());
}
node = node.get(currentChar);
}
node.setEnd();
}
private TrieNode searchPrefix(String word) {
TrieNode node = root;
for (int i = 0; i < word.length(); i++) {
char curLetter = word.charAt(i);
if (node.containsKey(curLetter)) {
node = node.get(curLetter);
} else {
return null;
}
}
return node;
}
public boolean search(String word) {
TrieNode node = searchPrefix(word);
return node != null && node.isEnd();
}
public boolean startsWith(String prefix) {
TrieNode node = searchPrefix(prefix);
return node != null;
}
}
第一个不重复的字符
给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。
方法一： 线性时间复杂度解法
class Solution {
public int firstUniqChar(String s) {
HashMap<Character, Integer> count = new HashMap<Character, Integer>();
int n = s.length();
// build hash map : character and how often it appears
for (int i = 0; i < n; i++) {
char c = s.charAt(i);
count.put(c, count.getOrDefault(c, 0) + 1);
}
// find the index
for (int i = 0; i < n; i++) {
if (count.get(s.charAt(i)) == 1)
return i;
}
return -1;
}
}
字符串反转
编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。
双指针
class Solution {
public void reverseString(char[] s) {
if(s == null || s.length == 0) return;
int left = 0;
int right = s.length-1;
while(left < right){ //奇数个的时候中间元素不动
char temp = s[left];
s[left] = s[right];
s[right] = temp;
left ++;
right --;
}
}
}
回文串验证
给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。
方法一：筛选 + 判断
最简单的方法是对字符串 s 进行一次遍历，并将其中的字母和数字字符进行保留
判断的方法有两种。一种是将字符串进行翻转，然后判断字符串是不是相同，第二种是使用双指针
class Solution {
public boolean isPalindrome(String 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));
}
}
StringBuffer sgood_rev = new StringBuffer(sgood).reverse();
return sgood.toString().equals(sgood_rev.toString());
}
}
左旋转字符串
字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串"abcdefg"和数字2，该函数将返回左旋转两位得到的结果"cdefgab"。
本题做法较多，本文主要介绍 “字符串切片” ， “列表遍历拼接” ， “字符串遍历拼接” 三种方法。
由于本题的多解法涉及到了 字符串为不可变对象 的相关概念，导致效率区别较大。因此，单列一节 三种方法的效率分析 ，望对各位有所帮助。
方法一：字符串切片
class Solution {
public String reverseLeftWords(String s, int n) {
return s.substring(n, s.length()) + s.substring(0, n);
}
}
方法二：列表遍历拼接
class Solution {
public String reverseLeftWords(String s, int n) {
StringBuilder res = new StringBuilder();
for(int i = n; i < s.length(); i++)
res.append(s.charAt(i));
for(int i = 0; i < n; i++)
res.append(s.charAt(i));
return res.toString();
}
}
方法三：字符串遍历拼接
class Solution {
public String reverseLeftWords(String s, int n) {
String res = "";
for(int i = n; i < s.length(); i++)
res += s.charAt(i);
for(int i = 0; i < n; i++)
res += s.charAt(i);
return res;
}
}
翻转单词顺序
输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串"I am a student. "，则输出"student. a am I"。
方法一：双指针
class Solution {
public String reverseWords(String s) {
s = s.trim(); // 删除首尾空格
int j = s.length() - 1, i = j;
StringBuilder res = new StringBuilder();
while(i >= 0) {
while(i >= 0 && s.charAt(i) != ' ') i--; // 搜索首个空格
res.append(s.substring(i + 1, j + 1) + " "); // 添加单词
while(i >= 0 && s.charAt(i) == ' ') i--; // 跳过单词间空格
j = i; // j 指向下个单词的尾字符
}
return res.toString().trim(); // 转化为字符串并返回
}
}
方法二：分割 + 倒序
class Solution {
public String reverseWords(String s) {
String[] strs = s.trim().split(" "); // 删除首尾空格，分割字符串
StringBuilder res = new StringBuilder();
for(int i = strs.length - 1; i >= 0; i--) { // 倒序遍历单词列表
if(strs[i].equals("")) continue; // 遇到空单词则跳过
res.append(strs[i] + " "); // 将单词拼接至 StringBuilder
}
return res.toString().trim(); // 转化为字符串，删除尾部空格，并返回
}
}
最长不含重复字符的子字符串
请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。
方法一：动态规划 + 哈希表
class Solution {
public int lengthOfLongestSubstring(String s) {
Map<Character, Integer> dic = new HashMap<>();
int res = 0, tmp = 0;
for(int j = 0; j < s.length(); j++) {
int i = dic.getOrDefault(s.charAt(j), -1); // 获取索引 i
dic.put(s.charAt(j), j); // 更新哈希表
tmp = tmp < j - i ? tmp + 1 : j - i; // dp[j - 1] -> dp[j]
res = Math.max(res, tmp); // max(dp[j - 1], dp[j])
}
return res;
}
}
方法二： 动态规划 + 线性遍历
class Solution {
public int lengthOfLongestSubstring(String s) {
Map<Character, Integer> dic = new HashMap<>();
int res = 0, tmp = 0;
for(int j = 0; j < s.length(); j++) {
int i = j - 1;
while(i >= 0 && s.charAt(i) != s.charAt(j)) i--; // 线性查找 i
tmp = tmp < j - i ? tmp + 1 : j - i; // dp[j - 1] -> dp[j]
res = Math.max(res, tmp); // max(dp[j - 1], dp[j])
}
return res;
}
}
方法三：双指针 + 哈希表
class Solution {
public int lengthOfLongestSubstring(String s) {
Map<Character, Integer> dic = new HashMap<>();
int i = -1, res = 0;
for(int j = 0; j < s.length(); j++) {
if(dic.containsKey(s.charAt(j)))
i = Math.max(i, dic.get(s.charAt(j))); // 更新左指针 i
dic.put(s.charAt(j), j); // 哈希表记录
res = Math.max(res, j - i); // 更新结果
}
return res;
}
}
把数字翻译成字符串
给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。
字符串的第 i 位置：
可以单独作为一位来翻译
如果第 i−1 位和第 i 位组成的数字在 10 到 25 之间，可以把这两位连起来翻译
class Solution {
public int translateNum(int num) {
String src = String.valueOf(num);
int p = 0, q = 0, r = 1;
for (int i = 0; i < src.length(); ++i) {
p = q;
q = r;
r = 0;
r += q;
if (i == 0) {
continue;
}
String pre = src.substring(i - 1, i + 1);
if (pre.compareTo("25") <= 0 && pre.compareTo("10") >= 0) {
r += p;
}
}
return r;
}
}
替换空格
将字符串转成char的数组，声明一个3倍长度的数组，遍历字符串数组当为空格时，添加%20
输入：s = "We are happy."
输出："We%20are%20happy."
由于每次替换从 1 个字符变成 3 个字符，使用字符数组可方便地进行替换。建立字符数组地长度为 s 的长度的 3 倍，这样可保证字符数组可以容纳所有替换后的字符。
public String replaceSpace(String s) {
int length = s.length();
char[] array = new char[length * 3];
int size = 0;
for (int i = 0; i < length; i++) {
char c = s.charAt(i);
if (c == ' ') {
array[size++] = '%';
array[size++] = '2';
array[size++] = '0';
} else {
array[size++] = c;
}
}
String newStr = new String(array, 0, size);
return newStr;
}
字符串的排列组合方式（决策树）
class Solution {
List<String> res = new LinkedList<>();
char[] c;
public String[] permutation(String s) {
c = s.toCharArray();
dfs(0);
return res.toArray(new String[res.size()]);
}
void dfs(int x) {
if(x == c.length - 1) {
res.add(String.valueOf(c)); // 添加排列方案
return;
}
HashSet<Character> set = new HashSet<>();
for(int i = x; i < c.length; i++) {
if(set.contains(c[i])) continue; // 重复，因此剪枝
set.add(c[i]);
swap(i, x); // 交换，将 c[i] 固定在第 x 位
dfs(x + 1); // 开启固定第 x + 1 位字符
swap(i, x); // 恢复交换
}
}
void swap(int a, int b) {
char tmp = c[a];
c[a] = c[b];
c[b] = tmp;
}
}
把字符串转换成整数
首部空格： 删除之即可；
符号位： 三种情况，即 '+'−'' , ''无符号" ；新建一个变量保存符号位，返回前判断正负即可。
非数字字符： 遇到首个非数字的字符时，应立即返回。
数字字符：
class Solution {
public int strToInt(String str) {
char[] c = str.trim().toCharArray();
if(c.length == 0) return 0;
int res = 0, bndry = Integer.MAX_VALUE / 10;
int i = 1, sign = 1;
if(c[0] == '-') sign = -1;
else if(c[0] != '+') i = 0;
for(int j = i; j < c.length; j++) {
if(c[j] < '0' || c[j] > '9') break;
if(res > bndry || res == bndry && c[j] > '7') return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
res = res * 10 + (c[j] - '0');
}
return sign * res;
}
}
数据压缩
输入："aabcccccaaa"
输出："a2b1c5a3"
public String compressString(String S) {
int N = S.length();
int i = 0;
StringBuilder sb = new StringBuilder();
while (i < N) {
int j = i;
while (j < N && S.charAt(j) == S.charAt(i)) {
j++;
}
sb.append(S.charAt(i));
sb.append(j - i);
i = j;
}
String res = sb.toString();
if (res.length() < S.length()) {
return res;
} else {
return S;
}
}
无重复子串最大长度
int lengthOfLongestSubstring(string s) {
// 哈希集合，记录每个字符是否出现过
unordered_set<char> occ;
int n = s.size();
// 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
int rk = -1, ans = 0;
// 枚举左指针的位置，初始值隐性地表示为 -1
for (int i = 0; i < n; ++i) {
if (i != 0) {
// 左指针向右移动一格，移除一个字符
occ.erase(s[i - 1]);
}
while (rk + 1 < n && !occ.count(s[rk + 1])) {
// 不断地移动右指针
occ.insert(s[rk + 1]);
++rk;
}
// 第 i 到 rk 个字符是一个极长的无重复字符子串
ans = max(ans, rk - i + 1);
}
return ans;
}
最大上升子序列
思想：
创建一个额外的数组，用于存放字串到当前位置的最大值
遍历数组，每次都和之前的数进行比较，获取最大字串，然后加1，
public int lengthOfLIS(int[] nums) {
if (nums.length == 0) {
return 0;
}
int[] dp = new int[nums.length]; // 创建一个额外的数组，用于存放字串到当前位置的最大值
dp[0] = 1; // 默认为1
int maxans = 1;
for (int i = 1; i < dp.length; i++) {
int maxval = 0;
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
maxval = Math.max(maxval, dp[j]); // 比较dp中值和mavl的值，取最大值
}
}
dp[i] = maxval + 1; // 当前值加1
maxans = Math.max(maxans, dp[i]);
}
return maxans;
}
字符串查找问题；
字符串查找问题---长字符串查找短字符串
String 1: ABCDEFGHLMNOPQRS
String 2: DCGSRQPOM
答案是true，所有在string2里的字母string1也都有。
解法，HashTable
查找某个字符或字符段在字符串中出现的次数
给一个数组，找出这样一些数，这个数左边的数都比它小，右边的数都比它大
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
1.双重遍历，两两相加
2.生成一个map集合，然后遍历nums，用target - nums 在map集合中是否存在，如果存在，则找到了
3.跟第二个相似，一次遍历，添加到map中的是target - nums[i] ,只要后续遍历中存在这样的key，就是找到了
给定一个未排序的整数数组，找出其中没有出现的最小的正整数。
新建一个数组，将元素插入到数组的对应位置，如果大于数组id直接舍弃，不存在的位置用0代替，范围位置id
寻找两个数组的中位数，排好序
分析：分治+二分查找
在两个有序数组中寻找k小的数
获取中位数的位置，两个数组和的一半
剪枝处理
特殊情况
分析完了正常的情况，那么就要分析一下特殊情况；
1)如果有一个数组是空的，直接返回另一个不为空的数组中的中位数
2)如果两个数组元素的个数相等，并且两个数组的中位数相等，直接返回其中一个中位数。
3)有可能在进行二分查找的时候出现了数组越界的情况，只需要定义一个最大值和一个最小值，这样可以按照正常的情况来处理了。
double findMedianSortedArrays(int nums1[], int nums2[]){
int m = m1.length;
int n = m2.length;
int k = (m+n) / 2;
if((m+n) %2 == 1){
return findKth(nums1,0,m-1,nums2,0,n-1,k+1);
}else{
return (findKth(nums1,0,m-1,nums2,0,n-1,k)+
findKth(nums1,0,m-1,nums2,0,n-1,k+1))/2.0
}
}
double findKth(int[] nums1,int l1,int h1,int[] nums2,int l2,int h2,int k){
int m = h1-l1+1;
int n = h2-l2+1;
if(m >n) {
return findKth(nums2,l2,h2,nums1,l1,h1,k);
}
if(m==0) {
return nums2[l2+k-1];
}
}
/*分清 起始位置 和 第几个元素 */
int findKthNumber(vector<int>& nums1,int i ,vector<int>& nums2,int j,int k){
if(i >= nums1.size()) return nums2[j+k-1];
if(j >= nums2.size()) return nums1[i+k-1];
//if(k ==1) return (double(nums1[i] + nums2[j]));wrong
if(k == 1) return min(nums1[i],nums2[j]);
//查找有没有k/2个元素的位置 i + k/2 -1
int midVal1 = (i+k/2-1 < nums1.size())?nums1[i+k/2-1]:INT_MAX;
int midVal2 = (j+k/2-1 < nums2.size())?nums2[j+k/2-1]:INT_MAX;
if(midVal1 < midVal2)
return findKthNumber(nums1,i+k/2,nums2,j,k-k/2);
else
return findKthNumber(nums1,i,nums2,j+k/2,k-k/2);
}
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int m = nums1.size(),n = nums2.size();
int left = (m+n+1)/2,right = (m+n+2)/2;
return (findKthNumber(nums1,0,nums2,0,left)+findKthNumber(nums1,0,nums2,0,right))/2.0;
}
}
如果没有排序
快速选择算法
随机选择一个数作为基准值，以基准值分成两个部分
如果基准值==k，那么基准值位置就是k
如果基准值小于k，就忘后搜索
如果基准值大于k，就往前搜索
public int findKthLargest(int[] nums, int k){
return quickSelect(nums,nums.length - 1,k);
}
int quickSelect(int[] nums,int low,int high,int k) {
int pivot = low;
for (int j = low; j < hight ; j++) {
if (nums[j] <= nums[high]) {
swap(nums,pivot++,j);
}
}
swap(nums,pivot,high);
}
void swap(int[] nums1, int[] nums2,int i, int j) {
int m = num.length;
if(i<m&&j<m){
swap(nums1,i,j);
}else if(i >=m && j>=m){
swap(nums2,i-m,j-m)
}else if (i <m && j >= m) {
int temp = nums1[i];
nums1[1] = nums2[j-m];
nums2[j-m] = temp;
}
}
void swap (int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
分布式大数据问题
每台服务器的复杂度限制
服务器之间通信的网络带宽限时