一 挑战字符串
1 无重复字符的最长子串（见leetcode bug free）
2 最长公共前缀（见leetcode bug free）
3 字符串的排列
给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。
示例1:
输入: s1 = "ab" s2 = "eidbaooo"
输出: True
解释: s2 包含 s1 的排列之一 ("ba"). 示例2:
输入: s1= "ab" s2 = "eidboaoo"
输出: False
analyse：
滑动窗口
code：
class Solution {
public boolean checkInclusion(String s1, String s2) {
if (s1 == null || s2 == null || s1.length() > s2.length()) {
return false;
}
int[] map1 = new int[26];
int[] map2 = new int[26];
int i = 0;
int j = 0;
while (j < s1.length()) {
char c1 = s1.charAt(j);
char c2 = s2.charAt(j);
map1[c1 - 'a'] += 1;
map2[c2 - 'a'] += 1;
j++;
}
j = s1.length() - 1;
while (j < s2.length()) {
if (arrayEqual(map1, map2)) {
return true;
}
j++;
i++;
if (j < s2.length()) {
char new_c = s2.charAt(j);
char old_c = s2.charAt(i - 1);
map2[new_c - 'a'] += 1;
map2[old_c - 'a'] -= 1;
}
}
return false;
}
public boolean arrayEqual(int[] a, int[] b) {
for (int i = 0; i < a.length; i++) {
if (a[i] != b[i]) {
return false;
}
}
return true;
}
}4 字符串相乘
两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。不能直接将字符串转化为大整数求乘积。
示例 1: 输入: num1 = "2", num2 = "3"
输出: "6"
示例 2: 输入: num1 = "123", num2 = "456"
输出: "56088"
说明： num1 和 num2 的长度小于110。
num1 和 num2 只包含数字 0-9。
num1 和 num2 均不以零开头，除非是数字 0 本身。
不能使用任何标准库的大数类型（比如 BigInteger）或直接将输入转换为整数来处理。
analyse：
要求结果里的第k个数字（k从0开始，k为0时表示个位，1表示十位），需要将满足i + j = k的所有数字乘积累加，再加上carry。（i和j分别为num1和num2的第i和第j个数字，定义同k）
code：
class Solution {
public String multiply(String num1, String num2) {
if (num1 == null || num2 == null || num1.length() == 0 || num2.length() == 0) {
return null;
}
if (num1.equals("0") || num2.equals("0")) {
return "0";
}
int m = num1.length();
int n = num2.length();
StringBuilder sb = new StringBuilder();
int k = 0;
int carry = 0;
while (k <= m + n - 2) {
int sum = 0;
for (int i = 0; i <= Math.min(k, m - 1); i++) {
int j = k - i;
if (j >= n) {
continue;
}
int digit1 = num1.charAt(m - i - 1) - '0';
int digit2 = num2.charAt(n - j - 1) - '0';
sum += digit1 * digit2;
}
sum += carry;
sb.append(String.valueOf(sum % 10));
carry = sum / 10;
k++;
}
if (carry != 0) {
String cs = String.valueOf(carry);
String r_cs = (new StringBuilder(cs)).reverse().toString();
sb.append(r_cs);
}
return sb.reverse().toString();
}
}5 反转字符串
给定一个字符串，逐个翻转字符串中的每个单词。
示例 1： 输入: "the sky is blue"
输出: "blue is sky the"
示例 2： 输入: " hello world! "
输出: "world! hello"
解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
示例 3： 输入: "a good example"
输出: "example good a"
解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。 说明： 无空格字符构成一个单词。
输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
analyse:
几个要点：
（1）定义两个指针p1,p2，p1指向待填充元素的位置，p2往后扫。
（2）如何保证开头的空格被去掉：当p1为0时，p2扫到空格不加入。
（3）如何保证单词间的空格只剩一个: 当p1 - 1为空格时，p2扫到空格不加入。
（4）如何实现单词反转：实现一个字符串反转的方法。每次往前加入一个空格时，就反转一下上一个加入的单词。最后还要对整体反转一遍。
（5）如何保证末尾的空格被去掉：扫完一遍后，检查p1-1是否为空格，是就p--。不是记得反转一下最后一个单词。
code：
class Solution {
public String reverseWords(String s) {
if (s == null || s.length() == 0) {
return "";
}
char[] sa = s.toCharArray();
int p = 0;
int last_word_start = 0;
for (int i = 0; i < sa.length; i++) {
char c = sa[i];
if (c == ' ') {
if (p == 0 || sa[p - 1] == ' ') {
continue;
}
reverse(sa, last_word_start, p - 1);
sa[p++] = c;
last_word_start = p;
} else {
sa[p++] = c;
}
}
if (p > 0 && sa[p - 1] == ' ') {
p--;
} else {
reverse(sa, last_word_start, p - 1);
}
reverse(sa, 0, p - 1);
return new String(sa, 0, p);
}
public void reverse(char[] sa, int start, int end) {
while (start < end) {
char tmp = sa[start];
sa[start] = sa[end];
sa[end] = tmp;
start++;
end--;
}
}
}6 简化路径
题目太长
以 Unix 风格给出一个文件的绝对路径，你需要简化它。或者换句话说，将其转换为规范路径。 在 Unix 风格的文件系统中，一个点（.）表示当前目录本身；此外，两个点 （..） 表示将目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。更多信息请参阅：Linux / Unix中的绝对路径 vs 相对路径 请注意，返回的规范路径必须始终以斜杠 / 开头，并且两个目录名之间必须只有一个斜杠 /。最后一个目录名（如果存在）不能以 / 结尾。此外，规范路径必须是表示绝对路径的最短字符串。 示例 1： 输入："/home/"
输出："/home"
解释：注意，最后一个目录名后面没有斜杠。
示例 2： 输入："/../"
输出："/"
解释：从根目录向上一级是不可行的，因为根是你可以到达的最高级。
示例 3： 输入："/home//foo/"
输出："/home/foo"
解释：在规范路径中，多个连续斜杠需要用一个斜杠替换。
示例 4： 输入："/a/./b/../../c/"
输出："/c"
示例 5： 输入："/a/../../b/../c//.//"
输出："/c"
示例 6： 输入："/a//b////c/d//././/.."
输出："/a/b/c"
analyse：
先根据“/”split，遍历split后的每个元素，用一个栈来搞，
code：
class Solution {
public String simplifyPath(String path) {
Stack<String> s = new Stack<String>();
String[] dirs = path.split("/");
for (String dir : dirs) {
if (dir.equals("") || dir.equals(".")) {
continue;
} else if (dir.equals("..")) {
if (!s.isEmpty()) {
s.pop();
}
} else {
s.push(dir);
}
}
if (s.isEmpty()) {
return "/";
}
List<String> dir_list = new ArrayList<String>();
while (!s.isEmpty()) {
dir_list.add(s.pop());
}
StringBuilder sb = new StringBuilder();
for (int i = dir_list.size() - 1; i >= 0; i--) {
sb.append("/");
sb.append(dir_list.get(i));
}
return sb.toString();
}
}7 复原IP地址
给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。(ip格式：只能是四段，每段值范围在0~255，除0外不能以0开头)。
示例: 输入: "25525511135"
输出: ["255.255.11.135", "255.255.111.35"]
analyse:
dfs
code：
class Solution {
public List<String> restoreIpAddresses(String s) {
List<String> res = new ArrayList<String>();
helper(res, s, 0, "", 0);
return res;
}
public void helper(List<String> res, String s, int index, String cur, int count) {
if (count == 4) {
if (index >= s.length()) {
res.add(cur.substring(0, cur.length() - 1));
} else {
return;
}
}
for (int i = index; i < s.length(); i++) {
if (i - index > 2) {
break;
}
String p = s.substring(index, i + 1);
int pv = Integer.parseInt(p);
if (pv > 255 || (p.charAt(0) == '0' && p.length() > 1)) {
continue;
}
helper(res, s, i + 1, cur + p + ".", count + 1);
}
}
}二 数组与排序
1 岛屿的最大面积
给定一个包含了一些 0 和 1的非空二维数组 grid , 一个 岛屿 是由四个方向 (水平或垂直) 的 1 (代表土地) 构成的组合。你可以假设二维矩阵的四个边缘都被水包围着。
找到给定的二维数组中最大的岛屿面积。(如果没有岛屿，则返回面积为0。)
示例 1: [[0,0,1,0,0,0,0,1,0,0,0,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,1,1,0,1,0,0,0,0,0,0,0,0],
[0,1,0,0,1,1,0,0,1,0,1,0,0],
[0,1,0,0,1,1,0,0,1,1,1,0,0],
[0,0,0,0,0,0,0,0,0,0,1,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,0,0,0,0,0,0,1,1,0,0,0,0]]
对于上面这个给定矩阵应返回 6。注意答案不应该是11，因为岛屿只能包含水平或垂直的四个方向的‘1’。 示例 2: [[0,0,0,0,0,0,0,0]]
对于上面这个给定的矩阵, 返回 0。 注意: 给定的矩阵grid 的长度和宽度都不超过 50。
analyse：
并查集
code：
class Solution {
int[] father;
int[] size;
int max_size;
public int maxAreaOfIsland(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
father = new int[m * n];
size = new int[m * n];
max_size = 0;
for (int i = 0; i < m * n; i++) {
father[i] = i;
size[i] = 1;
}
int[] dx = {0, 0, -1, -1};
int[] dy = {1, -1, 0, 0};
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
int index = i * n + j;
if (grid[i][j] == 0) {
continue;
}
max_size = Math.max(1, max_size);
for (int k = 0; k < 4; k++) {
int nx = i + dx[k];
int ny = j + dy[k];
if (nx >= 0 && nx < m && ny >= 0
&& ny < n && grid[nx][ny] == 1) {
union(index, nx * n + ny);
}
}
}
}
return max_size;
}
public int find(int a) {
if (father[a] == a) {
return a;
}
return father[a] = find(father[a]);
}
public void union(int a, int b) {
int root_a = find(a);
int root_b = find(b);
if (root_a != root_b) {
father[root_a] = root_b;
size[root_b] += size[root_a];
max_size = Math.max(max_size, size[root_b]);
}
}
}2 最长连续递增序列
给定一个未经排序的整数数组，找到最长且连续的的递增序列。
示例 1: 输入: [1,3,5,4,7]
输出: 3
解释: 最长连续递增序列是 [1,3,5], 长度为3。
尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的，因为5和7在原数组里被4隔开。
示例 2: 输入: [2,2,2,2,2]
输出: 1
解释: 最长连续递增序列是 [2], 长度为1。
注意：数组长度不会超过10000。
analyse:
遍历即可
code：
class Solution {
public int findLengthOfLCIS(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int start = 0;
int res = 1;
for (int i = 1; i < nums.length; i++) {
if (nums[i - 1] >= nums[i]) {
start = i;
}
res = Math.max(res, i - start + 1);
}
return res;
}
}3 最长连续序列
给定一个未排序的整数数组，找出最长连续序列的长度。
示例: 输入: [100, 4, 200, 1, 3, 2]
输出: 4
解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。
analyse:
带size的并查集和hash表
code：
class Solution {
int[] father;
int[] size;
int max_size;
public int longestConsecutive(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
father = new int[nums.length];
size = new int[nums.length];
max_size = 1;
for (int i = 0; i < nums.length; i++) {
father[i] = i;
size[i] = 1;
}
for (int i = 0; i < nums.length; i++) {
if (map.containsKey(nums[i])) {
continue;
}
if (map.containsKey(nums[i] - 1)) {
union(map.get(nums[i] - 1), i);
}
if (map.containsKey(nums[i] + 1)) {
union(map.get(nums[i] + 1), i);
}
map.put(nums[i], i);
}
return max_size;
}
public int find(int a) {
if (father[a] == a) {
return a;
}
return father[a] = find(father[a]);
}
public void union(int a, int b) {
int root_a = find(a);
int root_b = find(b);
if (root_a != root_b) {
father[root_a] = root_b;
size[root_b] += size[root_a];
max_size = Math.max(size[root_b], max_size);
}
}
}4 朋友圈
班上有 N 名学生。其中有些人是朋友，有些则不是。他们的友谊具有是传递性。如果已知 A 是 B 的朋友，B 是 C 的朋友，那么我们可以认为 A 也是 C 的朋友。所谓的朋友圈，是指所有朋友的集合。 给定一个 N * N 的矩阵 M，表示班级中学生之间的朋友关系。如果M[i][j] = 1，表示已知第 i 个和 j 个学生互为朋友关系，否则为不知道。你必须输出所有学生中的已知的朋友圈总数。 示例 1: 输入:
[[1,1,0],
[1,1,0],
[0,0,1]]
输出: 2
说明：已知学生0和学生1互为朋友，他们在一个朋友圈。
第2个学生自己在一个朋友圈。所以返回2。
示例 2: 输入:
[[1,1,0],
[1,1,1],
[0,1,1]]
输出: 1
说明：已知学生0和学生1互为朋友，学生1和学生2互为朋友，所以学生0和学生2也是朋友，所以他们三个在一个朋友圈，返回1。
注意： N 在[1,200]的范围内。
对于所有学生，有M[i][i] = 1。
如果有M[i][j] = 1，则有M[j][i] = 1。
analyse：
即求无向图的连通块数量，bfs或并查集
code：
class Solution {
public int findCircleNum(int[][] M) {
Set<Integer> set = new HashSet<Integer>();
int count = 0;
int n = M.length;
for (int i = 0; i < n; i++) {
if (set.contains(i)) {
continue;
}
count++;
Queue<Integer> q = new LinkedList<Integer>();
q.offer(i);
set.add(i);
while (!q.isEmpty()) {
int cur = q.poll();
for (int j = 0; j < n; j++) {
if (M[cur][j] == 1 && !set.contains(j)) {
q.offer(j);
set.add(j);
}
}
}
}
return count;
}
}class Solution {
int[] father;
int count;
public int findCircleNum(int[][] M) {
int n = M.length;
father = new int[n];
count = n;
for (int i = 0; i < n; i++) {
father[i] = i;
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (M[i][j] == 1) {
union(i, j);
}
}
}
return count;
}
public int find(int a) {
if (father[a] == a) {
return a;
}
return father[a] = find(father[a]);
}
public void union(int a, int b) {
int root_a = find(a);
int root_b = find(b);
if (root_a != root_b) {
father[root_a] = root_b;
count--;
}
}
}5 合并区间（见leetcode bug free）
6 接雨水
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
analyse：
两个指针指向两边已经灌完水的柱子，灌水的时候从两边往中间灌，哪边低就先灌哪边。
code：
class Solution {
public int trap(int[] height) {
if (height == null || height.length <= 2) {
return 0;
}
int i = 0;
int j = height.length - 1;
int res = 0;
int left = 0;
int right = 0;
while (i + 1 < j) {
if (height[i] + left < height[j] + right) {
left = Math.max(height[i] + left - height[i + 1], 0);
res += left;
i++;
} else {
right = Math.max(height[j] + right - height[j - 1], 0);
res += right;
j--;
}
}
return res;
}
}7 第k个排列
给出集合 [1,2,3,…,n]，其所有元素共有 n! 种排列。 按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下： "123"
"132"
"213"
"231"
"312"
"321"
给定 n 和 k，返回第 k 个排列。 说明： 给定 n 的范围是 [1, 9]。
给定 k 的范围是[1, n!]。
示例 1: 输入: n = 3, k = 3
输出: "213"
示例 2: 输入: n = 4, k = 9
输出: "2314"
analyse：
递归。首先把1~n加入到list中，求第一个数时，设i = k - 1， 应该找list.get(i / (n - 1)!)，然后list删除这个数，i设为i % (n - 1)!。类似的接下来去找第2~n个数。
code：
class Solution {
public String getPermutation(int n, int k) {
int factorial = 1;
List<Integer> numbers = new ArrayList<Integer>();
for (int i = 1; i <= n; i++) {
factorial *= i;
numbers.add(i);
}
StringBuilder sb = new StringBuilder();
helper(sb, k - 1, numbers, factorial / n);
return sb.toString();
}
public void helper(StringBuilder sb, int i, List<Integer> numbers, int factorial) {
int num_index = i / factorial;
sb.append(numbers.get(num_index));
numbers.remove(num_index);
if (numbers.size() == 0) {
return;
}
helper(sb, i % factorial, numbers, factorial / numbers.size());
}
} 四 动态和贪心
1 最大正方形（见leetcode bug free）
2 俄罗斯套娃信封问题
给定一些标记了宽度和高度的信封，宽度和高度以整数对形式 (w, h) 出现。当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。 请计算最多能有多少个信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。 说明:
不允许旋转信封。 示例: 输入: envelopes = [[5,4],[6,4],[6,7],[2,3]]
输出: 3
解释: 最多信封的个数为 3, 组合为: [2,3] => [5,4] => [6,7]。
analyse:
先把信封按宽度从小到大排序，dp状态dp[i]表示为第i个信封为最外层信封时的最大信封数。
code：
class Solution {
public int maxEnvelopes(int[][] envelopes) {
if (envelopes == null || envelopes.length == 0) {
return 0;
}
List<Pair> list = new ArrayList<Pair>();
for (int i = 0; i < envelopes.length; i++) {
list.add(new Pair(envelopes[i][0], envelopes[i][1]));
}
Comparator<Pair> c = new Comparator<Pair>() {
public int compare(Pair e1, Pair e2) {
return e1.w - e2.w;
}
};
Collections.sort(list, c);
int[] dp = new int[envelopes.length];
int res = 1;
for (int i = 0; i < dp.length; i++) {
Pair cur = list.get(i);
dp[i] = 1;
for (int j = 0; j < i; j++) {
Pair last = list.get(j);
if (cur.w > last.w && cur.h > last.h) {
dp[i] = Math.max(dp[i], 1 + dp[j]);
}
}
res = Math.max(res, dp[i]);
}
return res;
}
}
class Pair {
int w;
int h;
Pair(int w, int h) {
this.w = w;
this.h = h;
}
}五 数据结构
1 全O(1)的数据结构
实现一个数据结构支持以下操作： Inc(key) - 插入一个新的值为 1 的 key。或者使一个存在的 key 增加一，保证 key 不为空字符串。
Dec(key) - 如果这个 key 的值是 1，那么把他从数据结构中移除掉。否者使一个存在的 key 值减一。如果这个 key 不存在，这个函数不做任何事情。key 保证不为空字符串。
GetMaxKey() - 返回 key 中值最大的任意一个。如果没有元素存在，返回一个空字符串""。
GetMinKey() - 返回 key 中值最小的任意一个。如果没有元素存在，返回一个空字符串""。
挑战：以 O(1) 的时间复杂度实现所有操作。
analyse:
（1）两个map
map1存key到count的映射关系
map2存count到DoubleListNode的映射关系 （2）DoubleListNode
存对应的count，以及该count对应哪些key，以及prev和next （3）插入key时，做以下几件事：
a 更新map1，更新后假设该key的频次为count
b 找到count - 1对应的节点，记该节点为prev
c 删除prev中该key
d 假设prev的next节点的val不是count，需要新建一个节点，插入到prev后面
f prev.next加入key
g 假设prev中key数量已经被删除到0了，则删除prev这个节点（如果当前count为1则不删除） （4）删除key：类似于（3）
（5）getMaxKey
获取tail.prev.keys中的任意一个元素
（6）getMinKey
获取head.next.keys中的任意一个元素
code：
class AllOne {
Map<String, Integer> map1;
Map<Integer, DoubleListNode> map2;
DoubleListNode head;
DoubleListNode tail;
public AllOne() {
map1 = new HashMap<String, Integer>();
map2 = new HashMap<Integer, DoubleListNode>();
head = new DoubleListNode(0, new HashSet<String>());
tail = new DoubleListNode(0, new HashSet<String>());
head.next = tail;
tail.prev = head;
map2.put(0, head);
}
public void inc(String key) {
if (!map1.containsKey(key)) {
map1.put(key, 0);
}
map1.put(key, map1.get(key) + 1);
int count = map1.get(key);
DoubleListNode prev = map2.get(count - 1);
prev.keys.remove(key);
if (prev.next.val != count) {
DoubleListNode new_n = new DoubleListNode(count, new HashSet<String>());
map2.put(count, new_n);
insertAfterPos(prev, new_n);
}
prev.next.keys.add(key);
if (prev.keys.size() == 0 && count != 1) {
deleteNode(prev);
map2.remove(count - 1);
}
}
public void dec(String key) {
if (!map1.containsKey(key)) {
return;
}
int count = map1.get(key) - 1;
map1.remove(key);
DoubleListNode next = map2.get(count + 1);
next.keys.remove(key);
for (String s : map1.keySet()) {
System.out.println(s);
}
if(count != 0) {
map1.put(key, count);
if (next.prev.val != count) {
DoubleListNode new_n = new DoubleListNode(count, new HashSet<String>());
map2.put(count, new_n);
insertBeforePos(next, new_n);
}
next.prev.keys.add(key);
}
if (next.keys.size() == 0) {
deleteNode(next);
map2.remove(count + 1);
}
}
public String getMaxKey() {
if (map1.size() == 0) {
return "";
}
return tail.prev.keys.iterator().next();
}
public String getMinKey() {
if (map1.size() == 0) {
return "";
}
return head.next.keys.iterator().next();
}
private void deleteNode(DoubleListNode node) {
DoubleListNode prev = node.prev;
DoubleListNode next = node.next;
prev.next = next;
next.prev = prev;
}
private void insertAfterPos(DoubleListNode pos, DoubleListNode node) {
DoubleListNode pos_next = pos.next;
pos.next = node;
pos_next.prev = node;
node.prev = pos;
node.next = pos_next;
}
private void insertBeforePos(DoubleListNode pos, DoubleListNode node) {
DoubleListNode pos_prev = pos.prev;
pos.prev = node;
pos_prev.next = node;
node.prev = pos_prev;
node.next = pos;
}
}
class DoubleListNode {
int val;
Set<String> keys;
DoubleListNode next;
DoubleListNode prev;
DoubleListNode(int val, Set<String> keys) {
this.val = val;
this.keys = keys;
}
}六 扩展练习
1 平方根
实现 int sqrt(int x) 函数
analyse：
二分，注意用long防止溢出
code：
class Solution {
public int mySqrt(int x) {
long start = 0;
long end = x;
while (start + 1 < end) {
long mid = (start + end) / 2;
if (mid * mid <= x) {
start = mid;
} else {
end = mid;
}
}
if (end * end <= x) {
return (int)end;
}
return (int)start;
}
}