3. 无重复字符的最长子串
滑动窗口：
使用left记录窗口左端的位置，right记录窗口右端的位置。使用hashset记录窗口内的字符，不断的移动右窗口的值，当窗口内出现重复元素时，移动左窗口，保证窗口内没有重复的元素。记录窗口的最大值即可。
class Solution {
public int lengthOfLongestSubstring(String s) {
Set<Character> set = new HashSet<>();
int res = 0;
int left = 0, right = 0;
while (right < s.length()) {
if (set.add(s.charAt(right)) == false) {
while (s.charAt(left) != s.charAt(right)) {
set.remove(s.charAt(left));
left++;
}
left++;
}
res = Math.max(res, right - left + 1);
right++;
}
return res;
}
}
2. 两数相加
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);
ListNode cur = dummy;
int carry = 0;
while (l1 != null || l2 != null || carry != 0) {
int a = l1 == null ? 0 : l1.val;
int b = l2 == null ? 0 : l2.val;
int sum = a + b + carry;
ListNode node = new ListNode(sum % 10);
cur.next = node;
cur = node;
carry = sum / 10;
if (l1 != null) {
l1 = l1.next;
}
if (l2 != null) {
l2 = l2.next;
}
}
return dummy.next;
}
}
5. 最长回文子串
class Solution {
public String longestPalindrome(String s) {
int res = 1;
int len = s.length();
boolean[][] dp = new boolean[len][len];
for (int i = 0; i < len; i++) {
dp[i][i] = true;
if (i < len - 1 && s.charAt(i) == s.charAt(i + 1)) {
dp[i][i + 1] = true;
res = 2;
}
}
for (int L = 3; L <= len; L++) {
for (int i = 0; i + L - 1 < len; i++) {
int j = i + L - 1;
if (s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1]) {
dp[i][j] = true;
res = L;
}
}
}
for (int i = 0; i + res - 1 < len; i++) {
if (dp[i][i + res - 1]) {
return s.substring(i, i + res);
}
}
return null;
}
}
15. 三数之和
回溯超时：
class Solution {
List<List<Integer>> res = new ArrayList<>();
List<Integer> temp = new ArrayList<>();
private void dfs(int begin, int sum, int k, int[] nums) {
if (sum > 0 || k > 3) {
return;
}
if (sum == 0 && k == 3) {
res.add(new ArrayList<>(temp));
return;
}
for (int i = begin; i < nums.length; i++) {
if (i - 1 >= begin && nums[i] == nums[i - 1]) {
continue;
}
temp.add(nums[i]);
dfs(i + 1, sum + nums[i], k + 1, nums);
temp.remove(temp.size() - 1);
}
}
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
dfs(0, 0, 0, nums);
return res;
}
}
排序+双指针：
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
int len = nums.length;
List<List<Integer>> res = new ArrayList<>();
for (int i = 0; i < len - 2; i++) {
if (i - 1 >= 0 && nums[i] == nums[i - 1]) {
continue;
}
int lo = i + 1, hi = len - 1;
int target = -nums[i];
while (lo < hi) {
int sum = nums[lo] + nums[hi];
if (sum > target) {
hi--;
} else if (sum < target) {
lo++;
} else {
res.add(Arrays.asList(nums[i], nums[lo], nums[hi]));
lo++;
hi--;
while (lo < nums.length && nums[lo] == nums[lo - 1]) {
lo++;
}
while (hi > i && nums[hi] == nums[hi + 1]) {
hi--;
}
}
}
}
return res;
}
}
146. LRU 缓存机制
class LRUCache {
class DLinkedNode {
int key;
int value;
DLinkedNode next;
DLinkedNode pre;
public DLinkedNode() {
}
public DLinkedNode(int key, int value) {
this.key = key;
this.value = value;
}
}
Map<Integer, DLinkedNode> cache;
int capacity;
int size = 0;
DLinkedNode head;
DLinkedNode tail;
public LRUCache(int capacity) {
this.capacity = capacity;
this.cache = new HashMap<>();
this.head = new DLinkedNode();
this.tail = new DLinkedNode();
head.next = tail;
tail.pre = head;
}
public int get(int key) {
if (cache.containsKey(key)) {
DLinkedNode node = cache.get(key);
moveToHead(node);
return node.value;
} else {
return -1;
}
}
public void put(int key, int value) {
DLinkedNode node = cache.get(key);
if (node != null) {
node.value = value;
moveToHead(node);
} else {
node = new DLinkedNode(key, value);
addToHead(node);
size++;
cache.put(key, node);
if (size > capacity) {
DLinkedNode remove = removeTail();
cache.remove(remove.key);
size--;
}
}
}
private void moveToHead(DLinkedNode node) {
removeNode(node);
addToHead(node);
}
private void addToHead(DLinkedNode node) {
node.next = head.next;
node.next.pre = node;
head.next = node;
node.pre = head;
}
private void removeNode(DLinkedNode node) {
node.next.pre = node.pre;
node.pre.next = node.next;
}
private DLinkedNode removeTail() {
DLinkedNode node = tail.pre;
removeNode(node);
return node;
}
}
11. 盛最多水的容器
暴力法：
class Solution {
public int maxArea(int[] height) {
int res = 0;
for (int i = 0; i < height.length - 1; i++) {
for (int j = i + 1; j < height.length; j++) {
res = Math.max(res, Math.min(height[i], height[j]) * (j - i));
}
}
return res;
}
}
双指针：
class Solution {
public int maxArea(int[] height) {
int res = 0;
int lo = 0;
int hi = height.length - 1;
while (lo < hi) {
if (height[lo] < height[hi]) {
res = Math.max(res, height[lo] * (hi - lo));
lo++;
} else {
res = Math.max(res, height[hi] * (hi - lo));
hi--;
}
}
return res;
}
}
33. 搜索旋转排序数组
class Solution {
public int search(int[] nums, int target) {
int lo = 0;
int hi = nums.length - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (nums[mid] == target) {
return mid;
}
if (nums[mid] < nums[lo]) {//右边有序
if (nums[mid] < target && nums[hi] >= target) {//target在右侧
lo = mid + 1;
} else {
hi = mid - 1;
}
} else {//左边有序
if (nums[mid] > target && nums[lo] <= target) {//target在左侧
hi = mid - 1;
} else {
lo = mid + 1;
}
}
}
return -1;
}
}
46. 全排列
class Solution {
List<List<Integer>> res = new ArrayList<>();
List<Integer> temp = new ArrayList<>();
boolean[] isVisited;
private void dfs( int[] nums) {
if (temp.size() == nums.length) {
res.add(new ArrayList<>(temp));
return;
}
for (int i = 0; i < nums.length; i++) {
if (isVisited[i] == false) {
temp.add(nums[i]);
isVisited[i] = true;
dfs(nums);
isVisited[i] = false;
temp.remove(temp.size() - 1);
}
}
}
public List<List<Integer>> permute(int[] nums) {
isVisited = new boolean[nums.length];
dfs(nums);
return res;
}
}
56. 合并区间
class Solution {
//判断两个区间是否有交集
private boolean judge(int[] a, int[] b) {
return Math.max(a[0], b[0]) <= Math.min(a[1], b[1]);
}
public int[][] merge(int[][] intervals) {
List<int[]> res = new ArrayList<>();
Arrays.sort(intervals, (o1, o2) -> o1[0] - o2[0]);
int[] temp = intervals[0];
for (int i = 1; i < intervals.length; i++) {
if (judge(temp, intervals[i])) {
temp[0] = Math.min(temp[0], intervals[i][0]);
temp[1] = Math.max(temp[1], intervals[i][1]);
} else {
res.add(temp);
temp = intervals[i];
}
}
res.add(temp);
return res.toArray(new int[res.size()][]);
}
}
31. 下一个排列
从右往左找到第一个不是增序的数，再从右往左找到第一个比它大的数，交换两个数，然后将后面的数转置。
class Solution {
public void nextPermutation(int[] nums) {
int i = nums.length - 2;
while (i >= 0 && nums[i] >= nums[i + 1]) {
i--;
}
int j = nums.length - 1;
if (i >= 0) {
while (j > i && nums[j] <= nums[i]) {
j--;
}
swap(i, j, nums);
}
reverse(i + 1, nums.length - 1, nums);
}
private void reverse(int a, int b, int[] nums) {
while (a < b) {
swap(a, b, nums);
a++;
b--;
}
}
private void swap(int a, int b, int[] nums) {
int temp = nums[a];
nums[a] = nums[b];
nums[b] = temp;
}
}
215. 数组中的第K个最大元素
class Solution {
public int findKthLargest(int[] nums, int k) {
Queue<Integer> minHeap = new PriorityQueue<>();
for (int i : nums) {
minHeap.offer(i);
if (minHeap.size() > k) {
minHeap.poll();
}
}
return minHeap.peek();
}
}
199. 二叉树的右视图
class Solution {
public List<Integer> rightSideView(TreeNode root) {
if (root == null) {
return new ArrayList<>();
}
List<Integer> res = new ArrayList<>();
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
while (!q.isEmpty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
TreeNode front = q.poll();
if (front.left != null) {
q.offer(front.left);
}
if (front.right != null) {
q.offer(front.right);
}
if (i == size - 1) {
res.add(front.val);
}
}
}
return res;
}
}
200. 岛屿数量
dfs:
class Solution {
boolean[][] isVisited;
int[] dirX = {1, -1, 0, 0};
int[] dirY = {0, 0, 1, -1};
private void dfs(int i, int j, char[][] grid) {
isVisited[i][j] = true;
for (int k = 0; k < 4; k++) {
int newI = i + dirX[k];
int newJ = j + dirY[k];
if (newI >= 0 && newI < grid.length && newJ >= 0 && newJ < grid[0].length &&
grid[newI][newJ] == '1' && isVisited[newI][newJ] == false) {
dfs(newI, newJ, grid);
}
}
}
public int numIslands(char[][] grid) {
int res = 0;
isVisited = new boolean[grid.length][grid[0].length];
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if (grid[i][j] == '1' && isVisited[i][j] == false) {
dfs(i, j, grid);
res++;
}
}
}
return res;
}
}
93. 复原IP地址
class Solution {
List<String> res = new ArrayList<>();
List<String> temp = new ArrayList<>();
private void dfs(int begin, String s) {
if (temp.size() > 4) {
return;
}
if (temp.size() == 4 && begin == s.length()) {
StringBuilder sb = new StringBuilder();
for (String str : temp) {
sb.append(str);
sb.append('.');
}
sb.deleteCharAt(sb.length() - 1);
res.add(sb.toString());
return;
}
for (int i = begin; i < begin + 3 && i < s.length(); i++) {
String sub = s.substring(begin, i + 1);
if (sub.length() > 1 && sub.charAt(0) == '0') {
continue;
}
if (sub.length() == 3 && Integer.parseInt(sub) > 255) {
continue;
}
temp.add(sub);
dfs(i + 1, s);
temp.remove(temp.size() - 1);
}
}
public List<String> restoreIpAddresses(String s) {
dfs(0, s);
return res;
}
}
102. 二叉树的层序遍历
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
if (root == null) {
return new ArrayList<>();
}
List<List<Integer>> res = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
List<Integer> list = new ArrayList<>();
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode front = queue.poll();
list.add(front.val);
if (front.left != null) {
queue.offer(front.left);
}
if (front.right != null) {
queue.offer(front.right);
}
}
res.add(new ArrayList<>(list));
}
return res;
}
}
22. 括号生成
class Solution {
List<String> res = new ArrayList<>();
StringBuilder temp = new StringBuilder();
private void dfs(int left, int right, int n) {
if (right > left || left > n) {
return;
}
if (right == n) {
res.add(temp.toString());
return;
}
temp.append('(');
dfs(left + 1, right, n);
temp.deleteCharAt(temp.length() - 1);
temp.append(')');
dfs(left, right + 1, n);
temp.deleteCharAt(temp.length() - 1);
}
public List<String> generateParenthesis(int n) {
dfs(0, 0, n);
return res;
}
}
148. 排序链表
class Solution {
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode slow = head;
ListNode fast = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode newHead = slow.next;
slow.next = null;
ListNode left = sortList(head);
ListNode right = sortList(newHead);
return merge(left, right);
}
private ListNode merge(ListNode node1, ListNode node2) {
if (node1 == null) {
return node2;
}
if (node2 == null) {
return node1;
}
if (node1.val < node2.val) {
node1.next = merge(node1.next, node2);
return node1;
} else {
node2.next = merge(node1, node2.next);
return node2;
}
}
}
19. 删除链表的倒数第 N 个结点
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode p = dummy;
ListNode q = dummy;
for (int i = 0; i < n; i++) {
q = q.next;
}
while (q.next != null) {
p = p.next;
q = q.next;
}
p.next = p.next.next;
return dummy.next;
}
}
105. 从前序与中序遍历序列构造二叉树
class Solution {
private TreeNode build(int preL, int preR, int inL, int inR, int[] preOrder, int[] inOrder) {
if (preL > preR) {
return null;
}
int rootVal = preOrder[preL];
TreeNode root = new TreeNode(rootVal);
int index;
for (index = inL; index <= inR; index++) {
if (inOrder[index] == rootVal) {
break;
}
}
int leftNum = index - inL;
root.left = build(preL + 1, preL + leftNum, inL, inL + leftNum, preOrder, inOrder);
root.right = build(preL + leftNum + 1, preR, index + 1, inR, preOrder, inOrder);
return root;
}
public TreeNode buildTree(int[] preorder, int[] inorder) {
return build(0, preorder.length - 1, 0, inorder.length - 1, preorder, inorder);
}
}
54. 螺旋矩阵
class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
int L = 0;
int R = matrix[0].length - 1;
int U = 0;
int D = matrix.length - 1;
List<Integer> res = new ArrayList<>();
while (true) {
for (int j = L; j <= R; j++) {
res.add(matrix[U][j]);
}
U++;
if (U > D) {
break;
}
for (int i = U; i <= D; i++) {
res.add(matrix[i][R]);
}
R--;
if (L > R) {
break;
}
for (int j = R; j >= L; j--) {
res.add(matrix[D][j]);
}
D--;
if (U > D) {
break;
}
for (int i = D; i >= U; i--) {
res.add(matrix[i][L]);
}
L++;
if (L > R) {
break;
}
}
return res;
}
}
103. 二叉树的锯齿形层序遍历
class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
if (root == null) {
return new ArrayList<>();
}
List<List<Integer>> res = new ArrayList<>();
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
int flag = 1;
while (!q.isEmpty()) {
int size = q.size();
List<Integer> list = new ArrayList<>();
for (int i = 0; i < size; i++) {
TreeNode front = q.poll();
list.add(front.val);
if (front.left != null) {
q.offer(front.left);
}
if (front.right != null) {
q.offer(front.right);
}
}
if (flag == 1) {
res.add(list);
} else {
Collections.reverse(list);
res.add(list);
}
flag = -flag;
}
return res;
}
}
143. 重排链表
class Solution {
public ListNode reverse(ListNode node) {
ListNode dummy = new ListNode(0);
while (node != null) {
ListNode next = node.next;
node.next = dummy.next;
dummy.next = node;
node = next;
}
return dummy.next;
}
public void reorderList(ListNode head) {
if (head == null) {
return;
}
ListNode slow = head, fast = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode newNode = slow.next;
slow.next = null;
newNode = reverse(newNode);
while (newNode != null) {
ListNode temp = newNode.next;
newNode.next = head.next;
head.next = newNode;
head = newNode.next;
newNode = temp;
}
}
}
300. 最长递增子序列
class Solution {
public int lengthOfLIS(int[] nums) {
int res = 1;
int[] dp = new int[nums.length];
dp[0] = 1;
for (int i = 1; i < nums.length; i++) {
dp[i] = 1;
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
res = Math.max(res, dp[i]);
}
return res;
}
}
24. 两两交换链表中的节点
class Solution {
public ListNode swapPairs(ListNode head) {
if (head == null) {
return null;
}
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode cur = dummy;
while (cur.next != null && cur.next.next != null) {
ListNode node1 = cur.next;
ListNode node2 = cur.next.next;
cur.next = node2;
node1.next = node2.next;
node2.next = node1;
cur = node1;
}
return dummy.next;
}
}
322. 零钱兑换
动态规划：
dp[i]代表凑出金额为i所需最少的硬币数。 初始都赋为amount+1 ，如果最终dp[i]的值是amount+1，说明无法凑出。
边界:
dp[0] = 0
转移方程：
从所有硬币中选择一个硬币j，只要这个硬币j的金额小于等于i，dp[i]就等于dp[i-coins[j]] + 1。 遍历所有的硬币，dp[i]等于其中最小的那个。
最终答案就是dp[amount]。
class Solution {
public int coinChange(int[] coins, int amount) {
int[] dp = new int[amount + 1];
Arrays.fill(dp, amount + 1);
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
for (int j = 0; j < coins.length; j++) {
if (coins[j] <= i) {
dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
}
}
}
return dp[amount] > amount ? -1 : dp[amount];
}
}
78. 子集
class Solution {
List<List<Integer>> res = new ArrayList<>();
List<Integer> temp = new ArrayList<>();
private void dfs(int begin, int[] nums) {
if (begin == nums.length) {
return;
}
for (int i = begin; i < nums.length; i++) {
temp.add(nums[i]);
res.add(new ArrayList<>(temp));
dfs(i + 1, nums);
temp.remove(temp.size() - 1);
}
}
public List<List<Integer>> subsets(int[] nums) {
res.add(new ArrayList<>());
dfs(0, nums);
return res;
}
}
79. 单词搜索
class Solution {
int[] dirX = {1, -1, 0, 0};
int[] dirY = {0, 0, 1, -1};
boolean[][] isVisited;
private boolean dfs(int i, int j, int begin, char[][] board, String word) {
if (begin == word.length() - 1) {
return board[i][j] == word.charAt(begin);
}
if (board[i][j] != word.charAt(begin)) {
return false;
}
isVisited[i][j] = true;
for (int k = 0; k < 4; k++) {
int newI = i + dirX[k];
int newJ = j + dirY[k];
if (newI >= 0 && newI < board.length && newJ >= 0 && newJ < board[0].length && isVisited[newI][newJ] == false && dfs(newI, newJ, begin + 1, board, word)) {
return true;
}
}
isVisited[i][j] = false;
return false;
}
public boolean exist(char[][] board, String word) {
isVisited = new boolean[board.length][board[0].length];
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
if (dfs(i, j, 0, board, word)) {
return true;
}
}
}
return false;
}
}
94. 二叉树的中序遍历
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
Deque<TreeNode> stack = new ArrayDeque<>();
while (root != null || !stack.isEmpty()) {
while (root != null) {
stack.push(root);
root = root.left;
}
root = stack.pop();
res.add(root.val);
root = root.right;
}
return res;
}
}
198. 打家劫舍
class Solution {
public int rob(int[] nums) {
if (nums.length == 0) {
return 0;
}
int p = 0, q = nums[0], res = nums[0];
for (int i = 1; i < nums.length; i++) {
res = Math.max(q, p + nums[i]);
p = q;
q = res;
}
return res;
}
}
221. 最大正方形
class Solution {
public int maximalSquare(char[][] matrix) {
int res = 0;
int m = matrix.length;
int n = matrix[0].length;
int[][] dp = new int[m][n];
for (int i = 0; i < m; i++) {
dp[i][0] = matrix[i][0] == '1' ? 1 : 0;
res = Math.max(res, dp[i][0]);
}
for (int j = 0; j < n; j++) {
dp[0][j] = matrix[0][j] == '1' ? 1 : 0;
res = Math.max(res, dp[0][j]);
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
if (matrix[i][j] == '1') {
dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1])) + 1;
res = Math.max(dp[i][j], res);
}
}
}
return res * res;
}
}
236. 二叉树的最近公共祖先
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null || p == root || q == root) {
return root;
}
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
if (left == null && right == null) {
return null;
} else if (left == null) {
return right;
} else if (right == null) {
return left;
} else {
return root;
}
}
}
98. 验证二叉搜索树
class Solution {
long pre = Long.MIN_VALUE;
boolean res = true;
private void inOrder(TreeNode root) {
if (root == null) {
return;
}
inOrder(root.left);
if (root.val > pre) {
pre = root.val;
} else {
res = false;
}
inOrder(root.right);
}
public boolean isValidBST(TreeNode root) {
inOrder(root);
return res;
}
}
347. 前 K 个高频元素
class Solution {
public int[] topKFrequent(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<>();
Set<Integer> set = new HashSet<>();
for (int num : nums) {
set.add(num);
map.put(num, map.getOrDefault(num, 0) + 1);
}
Queue<Integer> pq = new PriorityQueue<>((o1, o2) -> map.get(o1) - map.get(o2));
for (int i : set) {
pq.offer(i);
if (pq.size() > k) {
pq.poll();
}
}
int[] res = new int[k];
for (int i = k-1; i >= 0; i--) {
res[i] = pq.poll();
}
return res;
}
}
64. 最小路径和
class Solution {
public int minPathSum(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
int[][] dp = new int[m][n];
dp[0][0] = grid[0][0];
for (int i = 1; i < m; i++) {
dp[i][0] = dp[i - 1][0] + grid[i][0];
}
for (int j = 1; j < n; j++) {
dp[0][j] = dp[0][j - 1] + grid[0][j];
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
}
}
return dp[m - 1][n - 1];
}
}
6. Z 字形变换
class Solution {
public String convert(String s, int numRows) {
if (numRows == 1) {
return s;
}
List<List<Character>> res = new ArrayList<>();
for (int i = 0; i < numRows; i++) {
res.add(new ArrayList<>());
}
int dir = 0;//0向下，1向上
int cur = 0;//当前行数
for (char c : s.toCharArray()) {
res.get(cur).add(c);
if (cur == 0) {
dir = 0;
}
if (cur == numRows - 1) {
dir = 1;
}
cur += dir == 0 ? 1 : -1;
}
StringBuilder sb = new StringBuilder();
for (List<Character> list : res) {
for (char c : list) {
sb.append(c);
}
}
return sb.toString();
}
}
445. 两数相加 II
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
Deque<Integer> stack1 = new ArrayDeque<>();
Deque<Integer> stack2 = new ArrayDeque<>();
while (l1 != null) {
stack1.push(l1.val);
l1 = l1.next;
}
while (l2 != null) {
stack2.push(l2.val);
l2 = l2.next;
}
ListNode dummy = new ListNode(0);
int carry = 0;
while (!stack1.isEmpty() || !stack2.isEmpty() || carry != 0) {
int a = stack1.isEmpty() ? 0 : stack1.pop();
int b = stack2.isEmpty() ? 0 : stack2.pop();
int sum = a + b + carry;
ListNode node = new ListNode(sum % 10);
node.next = dummy.next;
dummy.next = node;
carry = sum / 10;
}
return dummy.next;
}
}
739. 每日温度
class Solution {
public int[] dailyTemperatures(int[] T) {
int[] res = new int[T.length];
Deque<Integer> stack = new ArrayDeque<>();
for (int i = 0; i < T.length; i++) {
while (!stack.isEmpty() && T[i] > T[stack.peek()]) {
int cur = stack.pop();
res[cur] = i - cur;
}
stack.push(i);
}
return res;
}
}
240. 搜索二维矩阵 II
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int m = matrix.length;
int n = matrix[0].length;
int i = m - 1;
int j = 0;
while (i >= 0 && j < n) {
if (matrix[i][j] == target) {
return true;
} else if (matrix[i][j] > target) {
i--;
} else {
j++;
}
}
return false;
}
}
96. 不同的二叉搜索树
class Solution {
public int numTrees(int n) {
if (n < 1) {
return 0;
}
int[] dp = new int[n + 1];
dp[0] = 1;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
for (int j = 1; j <= i; j++) {
dp[i] += dp[j - 1] * dp[i - j];
}
}
return dp[n];
}
}
39. 组合总和
class Solution {
List<List<Integer>> res = new ArrayList<>();
List<Integer> temp = new ArrayList<>();
private void dfs(int begin, int[] candidates, int target) {
if (target == 0) {
res.add(new ArrayList<>(temp));
return;
}
if (candidates[begin] > target || begin == candidates.length) {
return;
}
for (int i = begin; i < candidates.length; i++) {
temp.add(candidates[i]);
dfs(i, candidates, target - candidates[i]);
temp.remove(temp.size() - 1);
}
}
public List<List<Integer>> combinationSum(int[] candidates, int target) {
Arrays.sort(candidates);
dfs(0, candidates, target);
return res;
}
}
113. 路径总和 II
class Solution {
List<List<Integer>> res = new ArrayList<>();
List<Integer> temp = new ArrayList<>();
private void dfs(TreeNode root, int targetSum) {
if (root == null) {
return;
}
temp.add(root.val);
targetSum -= root.val;
if (root.left == null && root.right == null && targetSum == 0) {
res.add(new ArrayList<>(temp));
}
dfs(root.left, targetSum);
dfs(root.right, targetSum);
temp.remove(temp.size() - 1);
}
public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
dfs(root, targetSum);
return res;
}
}
695. 岛屿的最大面积
class Solution {
boolean[][] isVisited;
int[] dirX = {1, -1, 0, 0};
int[] dirY = {0, 0, 1, -1};
int count = 0;
private void dfs(int i, int j, int[][] grid) {
count++;
isVisited[i][j] = true;
for (int k = 0; k < 4; k++) {
int newI = i + dirX[k];
int newJ = j + dirY[k];
if (newI >= 0 && newI < grid.length && newJ >= 0 && newJ < grid[0].length && isVisited[newI][newJ] == false
&& grid[newI][newJ] == 1) {
dfs(newI, newJ, grid);
}
}
}
public int maxAreaOfIsland(int[][] grid) {
if (grid.length == 0) {
return 0;
}
int res = 0;
int m = grid.length;
int n = grid[0].length;
isVisited = new boolean[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1 && isVisited[i][j] == false) {
dfs(i, j, grid);
res = Math.max(res, count);
count = 0;
}
}
}
return res;
}
}
55. 跳跃游戏
class Solution {
public boolean canJump(int[] nums) {
int maxPos = 0;
for (int i = 0; i < nums.length; i++) {
if (maxPos < i) {
return false;
}
maxPos = Math.max(maxPos, i + nums[i]);
}
return true;
}
}
144. 二叉树的前序遍历
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
if (root == null) {
return new ArrayList<>();
}
List<Integer> res = new ArrayList<>();
Deque<TreeNode> stack = new ArrayDeque<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
res.add(node.val);
if (node.right != null) {
stack.push(node.right);
}
if (node.left != null) {
stack.push(node.left);
}
}
return res;
}
}
71. 简化路径
class Solution {
public String simplifyPath(String path) {
Deque<String> stack = new ArrayDeque<>();
for (String s : path.split("/")) {
if (".".equals(s) || "".equals(s)) {
continue;
} else if ("..".equals(s)) {
if (!stack.isEmpty()) {
stack.pop();
}
} else {
stack.push(s);
}
}
String res = "";
while (!stack.isEmpty()) {
res = "/" + stack.pop() + res;
}
return "".equals(res) ? "/" : res;
}
}
309. 最佳买卖股票时机含冷冻期
class Solution {
public int maxProfit(int[] prices) {
if (prices.length == 0) {
return 0;
}
int[][] dp = new int[prices.length][2];
dp[0][1] = -prices[0];
for (int i = 1; i < prices.length; i++) {
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
dp[i][1] = Math.max(dp[i - 1][1], (i - 2 >= 0 ? dp[i - 2][0] : 0) - prices[i]);
}
return dp[prices.length - 1][0];
}
}
34. 在排序数组中查找元素的第一个和最后一个位置
class Solution {
public int lowwerBound(int[] nums, int target) {
int lo = 0;
int hi = nums.length;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (nums[mid] >= target) {
hi = mid;
} else {
lo = mid + 1;
}
}
return lo;
}
public int upperBound(int[] nums, int target) {
int lo = 0;
int hi = nums.length;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (nums[mid] > target) {
hi = mid;
} else {
lo = mid + 1;
}
}
return lo;
}
public int[] searchRange(int[] nums, int target) {
if (nums.length == 0) {
return new int[]{-1, -1};
}
int a = lowwerBound(nums, target);
if (a == nums.length || nums[a] != target) {
return new int[]{-1, -1};
} else {
int b = upperBound(nums, target);
return new int[]{a, b - 1};
}
}
}
82. 删除排序链表中的重复元素 II
class Solution {
public ListNode deleteDuplicates(ListNode head) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode cur = dummy;
while (cur.next != null && cur.next.next != null) {
if (cur.next.val == cur.next.next.val) {
ListNode temp = cur.next;
while (temp.next != null && temp.next.val == temp.val) {
temp = temp.next;
}
cur.next = temp.next;
} else {
cur = cur.next;
}
}
return dummy.next;
}
}
394. 字符串解码
class Solution {
public String decodeString(String s) {
StringBuilder res = new StringBuilder();
Deque<Character> stack = new ArrayDeque<>();
for (char c : s.toCharArray()) {
if (c == '[') {
stack.push(c);
} else if (c == ']') {
StringBuilder sb = new StringBuilder();
while (stack.peek() != '[') {
sb.append(stack.pop());
}
stack.pop();
sb.reverse();
int num = 0;
int product = 1;
while (!stack.isEmpty() && Character.isDigit(stack.peek())) {
num += (stack.pop() - '0') * product;
product *= 10;
}
for (int i = 0; i < num; i++) {
for (char ch : sb.toString().toCharArray()) {
stack.push(ch);
}
}
} else if (Character.isDigit(c)) {
stack.push(c);
} else {
stack.push(c);
}
}
while (!stack.isEmpty()) {
res.append(stack.pop());
}
res.reverse();
return res.toString();
}
}
17. 电话号码的字母组合
class Solution {
String[] map = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
List<String> res = new ArrayList<>();
StringBuilder temp = new StringBuilder();
private void dfs(int begin, String digits) {
if (begin == digits.length()) {
res.add(temp.toString());
return;
}
for (char c : map[digits.charAt(begin) - '0'].toCharArray()) {
temp.append(c);
dfs(begin + 1, digits);
temp.deleteCharAt(temp.length() - 1);
}
}
public List<String> letterCombinations(String digits) {
if ("".equals(digits)) {
return new ArrayList<>();
}
dfs(0, digits);
return res;
}
}
48. 旋转图像
class Solution {
private void transpose(int[][] matrix) {
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < i; j++) {
int temp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = temp;
}
}
}
private void reverseCol(int[][] matrix) {
for (int i = 0; i < matrix.length; i++) {
int lo = 0;
int hi = matrix.length - 1;
while (lo < hi) {
int temp = matrix[i][lo];
matrix[i][lo] = matrix[i][hi];
matrix[i][hi] = temp;
lo++;
hi--;
}
}
}
public void rotate(int[][] matrix) {
transpose(matrix);
reverseCol(matrix);
}
}
134. 加油站
class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
int totalGas = 0;//总油量
int curGas = 0;//当前油量
int start = 0;//出发时加油站编号
for (int i = 0; i < cost.length; i++) {
totalGas += gas[i] - cost[i];
curGas += gas[i] - cost[i];
if (curGas < 0) {
start = i + 1;
curGas = 0;
}
}
if (totalGas < 0) {
return -1;
} else {
return start;
}
}
}
面试题 16.25. LRU 缓存
class LRUCache {
class DLinkedNode {
int key;
int value;
DLinkedNode next;
DLinkedNode pre;
public DLinkedNode() {
}
public DLinkedNode(int key, int value) {
this.key = key;
this.value = value;
}
}
Map<Integer, DLinkedNode> cache;
DLinkedNode head;
DLinkedNode tail;
int capacity;
int size;
public LRUCache(int capacity) {
this.capacity = capacity;
this.size = 0;
this.cache = new HashMap<>();
head = new DLinkedNode();
tail = new DLinkedNode();
head.next = tail;
tail.pre = head;
}
private void moveToHead(DLinkedNode node) {
remove(node);
addToHead(node);
}
private void addToHead(DLinkedNode node) {
node.next = head.next;
head.next.pre = node;
head.next = node;
node.pre = head;
}
private void remove(DLinkedNode node) {
node.next.pre = node.pre;
node.pre.next = node.next;
}
public int get(int key) {
DLinkedNode node = cache.get(key);
if (node == null) {
return -1;
} else {
moveToHead(node);
return node.value;
}
}
public void put(int key, int value) {
DLinkedNode node = cache.get(key);
if (node == null) {
node = new DLinkedNode(key, value);
addToHead(node);
cache.put(key, node);
size++;
if (size > capacity) {
DLinkedNode del = tail.pre;
cache.remove(del.key);
remove(del);
size--;
}
} else {
node.value = value;
moveToHead(node);
}
}
}
50. Pow(x, n)
class Solution {
private double quickPow(double x, int n) {
double res = 1;
while (n != 0) {
if (n % 2 == 1) {
res *= x;
}
x *= x;
n >>= 1;
}
return res;
}
public double myPow(double x, int n) {
if (n >= 0) {
return quickPow(x, n);
} else {
return 1 / quickPow(x, -n);
}
}
}
142. 环形链表 II
若是环形链表，当快慢指针相遇时，再设一个指针从头结点出发，与慢指针一起每次走一步，当这个指针与慢指针相遇时就是环的入口。
public class Solution {
public ListNode detectCycle(ListNode head) {
if (head == null) {
return null;
}
ListNode slow = head;
ListNode fast = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
ListNode p = head;
while (p != slow) {
p = p.next;
slow = slow.next;
}
return p;
}
}
return null;
}
}
139. 单词拆分
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
Set<String> set = new HashSet<>(wordDict);
boolean[] dp = new boolean[s.length()];
if (set.contains(String.valueOf(s.charAt(0)))) {
dp[0] = true;
}
for (int i = 1; i < s.length(); i++) {
if (set.contains(s.substring(0, i + 1))) {
dp[i] = true;
continue;
}
for (int j = 0; j < i; j++) {
if (dp[j] == true && set.contains(s.substring(j + 1, i + 1))) {
dp[i] = true;
break;
}
}
}
return dp[s.length() - 1];
}
}
424. 替换后的最长重复字符
维护一个滑动窗口，然后保证窗口大小减去出现次数最多的字符的字数之差小于等于k即符合，窗口可继续扩张，否则就不符合题意，右移左指针。
class Solution {
public int characterReplacement(String s, int k) {
int[] count = new int[26];
int left = 0;
int right = 0;
int maxCount = 0;//出现次数最多的字符的出现次数
int res = 0;
while (right < s.length()) {
count[s.charAt(right) - 'A']++;
maxCount = Math.max(maxCount, count[s.charAt(right) - 'A']);
if (right - left + 1 - maxCount > k) {
count[s.charAt(left) - 'A']--;
left++;
}
right++;
res = Math.max(res, right - left);
}
return res;
}
}
62. 不同路径
class Solution {
public int uniquePaths(int m, int n) {
int[][] dp = new int[m][n];
for (int i = 0; i < m; i++) {
dp[i][0] = 1;
}
for (int j = 1; j < n; j++) {
dp[0][j] = 1;
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
return dp[m - 1][n - 1];
}
}
287. 寻找重复数
class Solution {
public int findDuplicate(int[] nums) {
Set<Integer> set = new HashSet<>();
for (int i : nums) {
if (!set.add(i)) {
return i;
}
}
return -1;
}
}
91. 解码方法
class Solution {
public int numDecodings(String s) {
int[] dp = new int[s.length()];
if (s.charAt(0) == '0') {
dp[0] = 0;
} else {
dp[0] = 1;
}
for (int i = 1; i < s.length(); i++) {
if (s.charAt(i) == '0') {
if (s.charAt(i - 1) == '0' || s.charAt(i - 1) >= '3') {
return 0;
} else {
dp[i] = i - 2 >= 0 ? dp[i - 2] : 1;
}
} else if (s.charAt(i) >= '1' && s.charAt(i) <= '6') {
if (s.charAt(i - 1) >= '1' && s.charAt(i - 1) <= '2') {
dp[i] = (i - 2 >= 0 ? dp[i - 2] : 1) + dp[i - 1];
} else {
dp[i] = dp[i - 1];
}
} else {
if (s.charAt(i - 1) == '1') {
dp[i] = (i - 2 >= 0 ? dp[i - 2] : 1) + dp[i - 1];
} else {
dp[i] = dp[i - 1];
}
}
}
return dp[s.length() - 1];
}
}
1143. 最长公共子序列
class Solution {
public int longestCommonSubsequence(String text1, String text2) {
int len1 = text1.length();
int len2 = text2.length();
int[][] dp = new int[len1 + 1][len2 + 1];
for (int i = 1; i <= len1; i++) {
for (int j = 1; j <= len2; j++) {
if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
}
}
}
return dp[len1][len2];
}
}
207. 课程表
class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
List<Integer>[] G = new ArrayList[numCourses];
for (int i = 0; i < G.length; i++) {
G[i] = new ArrayList<>();
}
int[] inDegree = new int[numCourses];
for (int[] arr : prerequisites) {
int pre = arr[1];
int next = arr[0];
G[pre].add(next);
inDegree[next]++;
}
Queue<Integer> q = new LinkedList<>();
for (int i = 0; i < numCourses; i++) {
if (inDegree[i] == 0) {
q.offer(i);
}
}
int num = 0;
while (!q.isEmpty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
int front = q.poll();
num++;
for (int next : G[front]) {
inDegree[next]--;
if (inDegree[next] == 0) {
q.offer(next);
}
}
}
}
return num == numCourses;
}
}
剑指 Offer 38. 字符串的排列
class Solution {
boolean[] isVisited;
List<String> res = new ArrayList<>();
StringBuilder temp = new StringBuilder();
private void dfs(char[] chars) {
if (temp.length() == chars.length) {
res.add(temp.toString());
return;
}
for (int i = 0; i < chars.length; i++) {
if (i - 1 >= 0 && chars[i] == chars[i - 1] && isVisited[i - 1] == false) {
continue;
}
if (isVisited[i] == false) {
isVisited[i] = true;
temp.append(chars[i]);
dfs(chars);
isVisited[i] = false;
temp.deleteCharAt(temp.length() - 1);
}
}
}
public String[] permutation(String s) {
isVisited = new boolean[s.length()];
char[] chars = s.toCharArray();
Arrays.sort(chars);
dfs(chars);
String[] arr = new String[res.size()];
for (int i = 0; i < res.size(); i++) {
arr[i] = res.get(i);
}
return arr;
}
}
114. 二叉树展开为链表
class Solution {
public void flatten(TreeNode root) {
if (root == null) {
return;
}
TreeNode cur = root;
while (cur != null) {
if (cur.left != null) {
TreeNode left = cur.left;
TreeNode pre = left;
while (pre.right != null) {
pre = pre.right;
}
pre.right = cur.right;
cur.right = left;
cur.left = null;
}
cur = cur.right;
}
}
}
递归：
class Solution {
public void flatten(TreeNode root) {
if (root == null) {
return;
}
TreeNode cur = root;
flatten(cur.left);
TreeNode right = cur.right;
cur.right = cur.left;
cur.left = null;
while (cur.right != null) {
cur = cur.right;
}
flatten(right);
cur.right = right;
}
}
162. 寻找峰值
class Solution {
public int findPeakElement(int[] nums) {
int lo = 0, hi = nums.length - 1;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (nums[mid] > nums[mid + 1]) {
hi = mid;
} else {
lo = mid + 1;
}
}
return lo;
}
}
152. 乘积最大子数组
class Solution {
public int maxProduct(int[] nums) {
if (nums.length == 0) {
return 0;
}
int res = nums[0];
int[] dpMax = new int[nums.length];
int[] dpMin = new int[nums.length];
dpMax[0] = dpMin[0] = nums[0];
for (int i = 1; i < nums.length; i++) {
dpMax[i] = Math.max(nums[i], Math.max(dpMax[i - 1] * nums[i], dpMin[i - 1] * nums[i]));
dpMin[i] = Math.min(nums[i], Math.min(dpMax[i - 1] * nums[i], dpMin[i - 1] * nums[i]));
res = Math.max(res, dpMax[i]);
}
return res;
}
}
560. 和为K的子数组
class Solution {
public int subarraySum(int[] nums, int k) {
int[] preSum = new int[nums.length];
preSum[0] = nums[0];
for (int i = 1; i < nums.length; i++) {
preSum[i] = preSum[i - 1] + nums[i];
}
int res = 0;
for (int i = 0; i < nums.length; i++) {
for (int j = i; j < nums.length; j++) {
if (preSum[j] - (i - 1 >= 0 ? preSum[i - 1] : 0) == k) {
res++;
}
}
}
return res;
}
}
剑指 Offer 07. 重建二叉树
class Solution {
private TreeNode build(int preL, int preR, int inL, int inR, int[] preorder, int[] inorder) {
if (preL > preR) {
return null;
}
int rootVal = preorder[preL];
TreeNode root = new TreeNode(rootVal);
int index;//根结点在中序遍历中的位置
for (index = inL; index <= inR; index++) {
if (inorder[index] == rootVal) {
break;
}
}
int numLeft = index - inL;//左子树的结点个数
root.left = build(preL + 1, preL + numLeft, inL, index - 1, preorder, inorder);
root.right = build(preL + 1 + numLeft, preR, index + 1, inR, preorder, inorder);
return root;
}
public TreeNode buildTree(int[] preorder, int[] inorder) {
return build(0, preorder.length - 1, 0, inorder.length - 1, preorder, inorder);
}
}
179. 最大数
