42. 接雨水
单调递减栈。
class Solution {
public int trap(int[] height) {
Deque<Integer> stack = new ArrayDeque<>();
int res = 0;
for (int i = 0; i < height.length; i++) {
while (!stack.isEmpty() && height[stack.peek()] < height[i]) {
int cur = stack.pop();
if (stack.isEmpty()) {
break;
}
int h = Math.min(height[stack.peek()], height[i]) - height[cur];
int w = i - stack.peek() - 1;
res += h * w;
}
stack.push(i);
}
return res;
}
}
4. 寻找两个正序数组的中位数
时间复杂度O(m+n)，空间复杂度O(m+n)
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int len1 = nums1.length, len2 = nums2.length;
int[] nums = new int[len1 + len2];
int pos = 0, p = 0, q = 0;
while (p < len1 && q < len2) {
if (nums1[p] > nums2[q]) {
nums[pos++] = nums2[q++];
} else {
nums[pos++] = nums1[p++];
}
}
while (p < len1) {
nums[pos++] = nums1[p++];
}
while (q < len2) {
nums[pos++] = nums2[q++];
}
return (nums[(len1 + len2 - 1) / 2] + nums[(len1 + len2) / 2]) / 2.0;
}
}
二分，时间复杂度Olog(m+n)
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int len1 = nums1.length, len2 = nums2.length;
int left = (len1 + len2 + 1) / 2;
int right = (len1 + len2 + 2) / 2;
return (findKth(nums1, 0, nums2, 0, left) + findKth(nums1, 0, nums2, 0, right)) / 2.0;
}
private int findKth(int[] nums1, int begin1, int[] nums2, int begin2, int k) {
if (begin1 >= nums1.length) {
return nums2[begin2 + k - 1];
}
if (begin2 >= nums2.length) {
return nums1[begin1 + k - 1];
}
if (k == 1) {
return Math.min(nums1[begin1], nums2[begin2]);
}
int mid1 = (begin1 + k / 2 - 1 < nums1.length) ? nums1[begin1 + k / 2 - 1] : Integer.MAX_VALUE;
int mid2 = (begin2 + k / 2 - 1 < nums2.length) ? nums2[begin2 + k / 2 - 1] : Integer.MAX_VALUE;
if (mid1 < mid2) {
return findKth(nums1, begin1 + k / 2, nums2, begin2, k - k / 2);
} else {
return findKth(nums1, begin1, nums2, begin2 + k / 2, k - k / 2);
}
}
}
25. K 个一组翻转链表
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode pre = dummy;
while (head != null) {
ListNode tail = pre;
for (int i = 0; i < k; i++) {
tail = tail.next;
if (tail == null) {
return dummy.next;
}
}
ListNode nextGroupHead = tail.next;
//翻转head到tail的链表
tail = head;//翻转之后头结点变成尾结点了
ListNode dummy2 = new ListNode(0);
dummy2.next = head;
for (int i = 0; i < k; i++) {
ListNode temp = head.next;
head.next = dummy2.next;
dummy2.next = head;
head = temp;
}
head = dummy2.next;
tail.next = nextGroupHead;//与下一组相连
pre.next = head;//与上一组相连
pre = tail;
head = nextGroupHead;
}
return dummy.next;
}
}
23. 合并K个升序链表
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
Queue<ListNode> pq = new PriorityQueue<>((o1, o2) -> o1.val - o2.val);
for (ListNode node : lists) {
if (node != null) {
pq.offer(node);
}
}
ListNode dummy = new ListNode(0);
ListNode cur = dummy;
while (!pq.isEmpty()) {
ListNode node = pq.poll();
cur.next = node;
if (node.next != null) {
pq.offer(node.next);
}
cur = cur.next;
}
return dummy.next;
}
}
124. 二叉树中的最大路径和
class Solution {
int res = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
dfs(root);
return res;
}
private int dfs(TreeNode root) {
if (root == null) {
return 0;
}
int left = Math.max(0, dfs(root.left));
int right = Math.max(0, dfs(root.right));
int sum = left + right + root.val;
res = Math.max(sum, res);
return root.val + Math.max(left, right);
}
}
72. 编辑距离
class Solution {
public int minDistance(String word1, String word2) {
int len1 = word1.length();
int len2 = word2.length();
int[][] dp = new int[len1 + 1][len2 + 1];
for (int i = 0; i <= len1; i++) {
dp[i][0] = i;
}
for (int j = 0; j <= len2; j++) {
dp[0][j] = j;
}
for (int i = 1; i <= len1; i++) {
for (int j = 1; j <= len2; j++) {
if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = 1 + Math.min(dp[i - 1][j], Math.min(dp[i][j - 1], dp[i - 1][j - 1]));
}
}
}
return dp[len1][len2];
}
}
440. 字典序的第K小数字
class Solution {
public int findKthNumber(int n, int k) {
int cur = 1;
while (k > 1) {
long curNum = 0;//以cur为根的树的总结点数
long first = cur;
long next = cur + 1;
while (first <= n) {
curNum += Math.min((long) (n + 1), next) - first;
first *= 10;
next *= 10;
}
if (curNum < k) {//结点数小于k，说明在右边的树中
cur++;
k -= curNum;
} else {//在cur的子树中
k--;
cur *= 10;
}
}
return cur;
}
}
32. 最长有效括号
class Solution {
public int longestValidParentheses(String s) {
if (s.length() == 0) {
return 0;
}
int res = 0;
int[] dp = new int[s.length()];
for (int i = 1; i < s.length(); i++) {
if (s.charAt(i) == ')') {
if (s.charAt(i - 1) == '(') {
dp[i] = (i - 2 >= 0 ? dp[i - 2] : 0) + 2;
} else {
int index = i - dp[i - 1] - 1;
if (index < 0) {
dp[i] = 0;
} else {
if (s.charAt(index) == ')') {
dp[i] = 0;
} else {
dp[i] = dp[i - 1] + 2 + (index - 1 >= 0 ? dp[index - 1] : 0);
}
}
}
} else {
dp[i] = 0;
}
res = Math.max(res, dp[i]);
}
return res;
}
}
精简：
class Solution {
public int longestValidParentheses(String s) {
int res = 0;
int[] dp = new int[s.length()];
for (int i = 1; i < s.length(); i++) {
if (s.charAt(i) == ')') {
if (s.charAt(i - 1) == '(') {
dp[i] = (i - 2 >= 0 ? dp[i - 2] : 0) + 2;
} else {
int index = i - dp[i - 1] - 1;
if (index >= 0 && s.charAt(index) == '(') {
dp[i] = dp[i - 1] + 2 + (index - 1 >= 0 ? dp[index - 1] : 0);
}
}
}
res = Math.max(res, dp[i]);
}
return res;
}
}
10. 正则表达式匹配
比较难理解的是p的第j个数是的情况
如果s的第i个数等于p的第j-1个数 或者 p的第j-1个数是 .
dp[i][j] = dp[i-1][j] // a 记为多个a
or dp[i][j] = dp[i][j-1] // a* 记为单个a
or dp[i][j] = dp[i][j-2] // a*记为空
否则
dp[i][j] = dp[i][j-2]
class Solution {
public boolean isMatch(String s, String p) {
int sLen = s.length();
int pLen = p.length();
boolean[][] dp = new boolean[sLen + 1][pLen + 1];
dp[0][0] = true;
for (int j = 2; j <= pLen; j++) {
if (p.charAt(j - 1) == '*') {
dp[0][j] = dp[0][j - 2];
}
}
for (int i = 1; i <= sLen; i++) {
for (int j = 1; j <= pLen; j++) {
if (s.charAt(i - 1) == p.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1];
} else if (p.charAt(j - 1) == '.') {
dp[i][j] = dp[i - 1][j - 1];
} else if (p.charAt(j - 1) == '*') {
if (s.charAt(i - 1) == p.charAt(j - 2) || p.charAt(j - 2) == '.') {
dp[i][j] = dp[i][j - 2] || dp[i - 1][j - 2] || dp[i - 1][j];
} else {
dp[i][j] = dp[i][j - 2];
}
}
}
}
return dp[sLen][pLen];
}
}
135. 分发糖果
class Solution {
public int candy(int[] ratings) {
if (ratings.length == 0) {
return 0;
}
int len = ratings.length;
int[] left = new int[len], right = new int[len];
Arrays.fill(left, 1);
Arrays.fill(right, 1);
for (int i = 1; i < len; i++) {
if (ratings[i] > ratings[i - 1]) {
left[i] = left[i - 1] + 1;
}
}
for (int i = len - 2; i >= 0; i--) {
if (ratings[i] > ratings[i + 1]) {
right[i] = right[i + 1] + 1;
}
}
int res = 0;
for (int i = 0; i < len; i++) {
res += Math.max(left[i], right[i]);
}
return res;
}
}
改进，用一个数组:
class Solution {
public int candy(int[] ratings) {
int[] res = new int[ratings.length];
Arrays.fill(res, 1);
for (int i = 1; i < ratings.length; i++) {
if (ratings[i] > ratings[i - 1]) {
res[i] = res[i - 1] + 1;
}
}
for (int i = ratings.length - 2; i >= 0; i--) {
if (ratings[i] > ratings[i + 1]) {
res[i] = Math.max(res[i], res[i + 1] + 1);
}
}
int sum = 0;
for (int i : res) {
sum += i;
}
return sum;
}
}
41. 缺失的第一个正数
class Solution {
public int firstMissingPositive(int[] nums) {
int len = nums.length;
for (int i = 0; i < nums.length; i++) {
while (nums[i] - 1 >= 0 && nums[i] - 1 < nums.length && nums[i] != nums[nums[i] - 1]) {
swap(i, nums[i] - 1, nums);
}
}
for (int i = 0; i < nums.length; i++) {
if (nums[i] != i + 1) {
return i + 1;
}
}
return len + 1;
}
private void swap(int a, int b, int[] nums) {
int temp = nums[a];
nums[a] = nums[b];
nums[b] = temp;
}
}
76. 最小覆盖子串
滑动窗口
class Solution {
public String minWindow(String s, String t) {
int[] need = new int[128];
int[] window = new int[128];
String res = "";
int minLen = Integer.MAX_VALUE;
int left = 0, right = 0;
int count = 0;
for (char c : t.toCharArray()) {
need[c]++;
}
while (right < s.length()) {
char c = s.charAt(right);
window[c]++;
if (need[c] > 0 && window[c] <= need[c]) {
count++;
}
while (count == t.length()) {
char ch = s.charAt(left);
window[ch]--;
if (need[ch] > 0 && window[ch] < need[ch]) {
count--;
}
if (right - left + 1 < minLen) {
minLen = right - left + 1;
res = s.substring(left, right + 1);
}
left++;
}
right++;
}
return res;
}
}
84. 柱状图中最大的矩形
单调递增栈。对于出栈的元素cur，当前遍历的元素i是右边第一个比它矮的柱子，栈顶元素peek是左边第一个比它矮的柱子，对于高为heights[cur]的最大矩形面积已可以计算，宽等于 i - stack.peek() - 1。
class Solution {
public int largestRectangleArea(int[] heights) {
int res = 0;
Deque<Integer> stack = new ArrayDeque<>();
int[] newHeights = new int[heights.length + 2];
newHeights[0] = newHeights[heights.length + 1] = 0;
System.arraycopy(heights, 0, newHeights, 1, heights.length);
heights = newHeights;
for (int i = 0; i < heights.length; i++) {
while (!stack.isEmpty() && heights[i] < heights[stack.peek()]) {
int cur = stack.pop();
int h = heights[cur];
int w = i - stack.peek() - 1;
res = Math.max(res, h * w);
}
stack.push(i);
}
return res;
}
}
128. 最长连续序列
class Solution {
int[] father;
int[] size;
int res = 1;
private void init() {
for (int i = 0; i < father.length; i++) {
father[i] = i;
size[i] = 1;
}
}
private int findFather(int x) {
while (father[x] != x) {
x = father[x];
}
return x;
}
private void union(int a, int b) {
int fA = findFather(a);
int fB = findFather(b);
if (fA != fB) {
father[fA] = fB;
size[fB] += size[fA];
res = Math.max(res, size[fB]);
}
}
public int longestConsecutive(int[] nums) {
if (nums.length == 0) {
return 0;
}
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
map.put(nums[i], i);
}
father = new int[nums.length];
size = new int[nums.length];
init();
for (int i : nums) {
if (map.containsKey(i + 1)) {
union(map.get(i), map.get(i + 1));
}
}
return res;
}
}
45. 跳跃游戏 II
class Solution {
public int jump(int[] nums) {
int res = 0;
int maxPos = 0;//当前最远可到达的位置
int end = 0;//当前要到达的位置
int curPos;//当前的位置
for (curPos = 0; curPos < nums.length - 1; curPos++) {
maxPos = Math.max(maxPos, curPos + nums[curPos]);
if (curPos == end) {
res++;
end = maxPos;
}
}
return res;
}
}
85. 最大矩形
转化成第84题。
class Solution {
private int cal(int[] heights) {
int[] newHeights = new int[heights.length + 2];
newHeights[0] = newHeights[heights.length + 1] = 0;
System.arraycopy(heights, 0, newHeights, 1, heights.length);
heights = newHeights;
Deque<Integer> stack = new ArrayDeque<>();
int res = 0;
for (int i = 0; i < heights.length; i++) {
while (!stack.isEmpty() && heights[i] < heights[stack.peek()]) {
int cur = stack.pop();
int h = heights[cur];
int w = i - stack.peek() - 1;
res = Math.max(res, h * w);
}
stack.push(i);
}
return res;
}
public int maximalRectangle(char[][] matrix) {
if (matrix.length == 0) {
return 0;
}
int[] heights = new int[matrix[0].length];
int res = 0;
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
if (matrix[i][j] == '0') {
heights[j] = 0;
} else {
heights[j]++;
}
}
res = Math.max(res, cal(heights));
}
return res;
}
}
51. N 皇后
class Solution {
List<List<String>> res = new ArrayList<>();
int[] arr;
boolean[] isVisited;
private boolean judge(int n) {
boolean flag = true;
label:
for (int i = 1; i <= n; i++) {//第i行的皇后和后面所有行的皇后判断是否在对角线上
for (int j = i + 1; j <= n; j++) {
if (Math.abs(i - j) == Math.abs(arr[i] - arr[j])) {
flag = false;
break label;
}
}
}
return flag;
}
private void dfs(int begin, int n) {
if (begin == n + 1) {
if (judge(n) == true) {
List<String> list = new ArrayList<>();
for (int i = 1; i <= n; i++) {
StringBuilder sb = new StringBuilder();
for (int j = 1; j <= n; j++) {
if (j == arr[i]) {
sb.append('Q');
} else {
sb.append('.');
}
}
list.add(sb.toString());
}
res.add(list);
}
return;
}
for (int i = 1; i <= n; i++) {
if (isVisited[i] == false) {
arr[begin] = i;
isVisited[i] = true;
dfs(begin + 1, n);
isVisited[i] = false;
}
}
}
public List<List<String>> solveNQueens(int n) {
arr = new int[n + 1];
isVisited = new boolean[n + 1];
dfs(1, n);
return res;
}
}
329. 矩阵中的最长递增路径
记忆化dfs:
由于同一个单元格对应的最长递增路径的长度是固定不变的，因此可以使用记忆化的方法进行优化。用矩阵memo作为缓存矩阵，已经计算过的单元格的结果存储到缓存矩阵中。
class Solution {
int[] dirX = {1, -1, 0, 0};
int[] dirY = {0, 0, 1, -1};
int[][] memo;
private int dfs(int i, int j, int[][] matrix) {
if (memo[i][j] != 0) {
return memo[i][j];
}
memo[i][j]++;
for (int k = 0; k < 4; k++) {
int newI = i + dirX[k];
int newJ = j + dirY[k];
if (newI >= 0 && newI < matrix.length && newJ >= 0 && newJ < matrix[0].length
&& matrix[newI][newJ] > matrix[i][j]) {
memo[i][j] = Math.max(memo[i][j], dfs(newI, newJ, matrix) + 1);
}
}
return memo[i][j];
}
public int longestIncreasingPath(int[][] matrix) {
if (matrix.length == 0) {
return 0;
}
memo = new int[matrix.length][matrix[0].length];
int res = 0;
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
res = Math.max(res, dfs(i, j, matrix));
}
}
return res;
}
}
297. 二叉树的序列化与反序列化
public class Codec {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
if (root == null) {
return "null";
}
StringBuilder res = new StringBuilder();
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 == null) {
res.append("null,");
continue;
} else {
res.append(front.val + ",");
q.offer(front.left);
q.offer(front.right);
}
}
}
res.deleteCharAt(res.length() - 1);
return res.toString();
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
if ("null".equals(data)) {
return null;
}
String[] splits = data.split(",");
TreeNode root = new TreeNode(Integer.parseInt(splits[0]));
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
for (int i = 1; i < splits.length; i++) {
TreeNode front = q.poll();
if (!"null".equals(splits[i])) {
front.left = new TreeNode(Integer.parseInt(splits[i]));
q.offer(front.left);
}
i++;
if (!"null".equals(splits[i])) {
front.right = new TreeNode(Integer.parseInt(splits[i]));
q.offer(front.right);
}
}
return root;
}
}
354. 俄罗斯套娃信封问题
class Solution {
private int lis(int[][] envelopes) {
int[] dp = new int[envelopes.length];
dp[0] = 1;
int res = 1;
for (int i = 1; i < envelopes.length; i++) {
dp[i] = 1;
for (int j = 0; j < i; j++) {
if (envelopes[j][1] < envelopes[i][1] && envelopes[j][0] < envelopes[i][0]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
res = Math.max(res, dp[i]);
}
return res;
}
public int maxEnvelopes(int[][] envelopes) {
if (envelopes.length == 0) {
return 0;
}
Arrays.sort(envelopes, (o1, o2) -> o1[0] - o2[0]);
return lis(envelopes);
}
}
剑指 Offer 51. 数组中的逆序对
归并排序代码：
public void mergeSort(int[] arr, int lo, int hi) {
if (lo >= hi) {
return;
}
int mid = lo + (hi - lo) / 2;
mergeSort(arr, lo, mid);
mergeSort(arr, mid + 1, hi);
int[] temp = new int[hi - lo + 1];
int i = lo, j = mid + 1, pos = 0;
while (i <= mid && j <= hi) {
temp[pos++] = arr[i] < arr[j] ? arr[i++] : arr[j++];
}
while (i <= mid) {
temp[pos++] = arr[i++];
}
while (j <= hi) {
temp[pos++] = arr[j++];
}
System.arraycopy(temp, 0, arr, lo, pos);
}
在并的过程中计算逆序对：
class Solution {
public int reversePairs(int[] nums) {
return mergeSort(nums, 0, nums.length - 1);
}
public int mergeSort(int[] arr, int lo, int hi) {
if (lo >= hi) {
return 0;
}
int mid = lo + (hi - lo) / 2;
int res = mergeSort(arr, lo, mid) + mergeSort(arr, mid + 1, hi);
int[] temp = new int[hi - lo + 1];
int i = lo, j = mid + 1, pos = 0;
while (i <= mid && j <= hi) {
res += arr[i] <= arr[j] ? 0 : mid + 1 - i;//arr[j]小，从i到mid的所有数与j构成逆序对f
temp[pos++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
}
while (i <= mid) {
temp[pos++] = arr[i++];
}
while (j <= hi) {
temp[pos++] = arr[j++];//此时arr[j]比左边的所有数都大了，不可能构成逆序对
}
System.arraycopy(temp, 0, arr, lo, pos);
return res;
}
}
460. LFU 缓存
239. 滑动窗口最大值
双端队列：
从队尾到队头以元素值递增的顺序保存数组的下标，队尾的数最小，队头的数最大。
addLast是往队尾加，addFirst是往队头加。
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int[] res = new int[nums.length - k + 1];
Deque<Integer> q = new ArrayDeque<>();
for (int i = 0; i < nums.length; i++) {
//如果队尾的数小于等于nums[i]，队尾出队。
while (!q.isEmpty() && nums[q.peekLast()] <= nums[i]) {
q.pollLast();
}
q.addLast(i);
if (q.peek() <= i - k) {//如果队头的值不在窗口内，队头出队
q.poll();
}
if (i - k + 1 >= 0) {
res[i - k + 1] = nums[q.peek()];//队头保存的是窗口中的最大值
}
}
return res;
}
}
726. 原子的数量
44. 通配符匹配
class Solution {
public boolean isMatch(String s, String p) {
int sLen = s.length();
int pLen = p.length();
boolean[][] dp = new boolean[sLen + 1][pLen + 1];
dp[0][0] = true;
for (int j = 1; j <= pLen; j++) {
if (p.charAt(j - 1) == '*') {
dp[0][j] = true;
} else {
break;
}
}
for (int i = 1; i <= sLen; i++) {
for (int j = 1; j <= pLen; j++) {
if (s.charAt(i - 1) == p.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1];
} else if (p.charAt(j - 1) == '?') {
dp[i][j] = dp[i - 1][j - 1];
} else if (p.charAt(j - 1) == '*') {
dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
}
}
}
return dp[sLen][pLen];
}
}
123. 买卖股票的最佳时机 III
class Solution {
public int maxProfit(int[] prices) {
if (prices.length == 0) {
return 0;
}
int[][][] dp = new int[prices.length][3][2];
for (int j = 1; j <= 2; j++) {
dp[0][j][1] = -prices[0];
}
for (int i = 1; i < prices.length; i++) {
for (int j = 1; j <= 2; j++) {
dp[i][j][1] = Math.max(dp[i - 1][j][1], dp[i - 1][j - 1][0] - prices[i]);
dp[i][j][0] = Math.max(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i]);
}
}
return dp[prices.length - 1][2][0];
}
}
97. 交错字符串
class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
int len1 = s1.length();
int len2 = s2.length();
if (len1 + len2 != s3.length()) {
return false;
}
//dp[i][j]代表s1的前i个字符与s2的前j个字符是否可以交错组成s3的前i+j个字符
boolean[][] dp = new boolean[len1 + 1][len2 + 1];
dp[0][0] = true;
for (int i = 1; i <= len1; i++) {
if (s1.charAt(i - 1) == s3.charAt(i - 1)) {
dp[i][0] = true;
} else {
break;
}
}
for (int j = 1; j <= len2; j++) {
if (s2.charAt(j - 1) == s3.charAt(j - 1)) {
dp[0][j] = true;
} else {
break;
}
}
for (int i = 1; i <= len1; i++) {
for (int j = 1; j <= len2; j++) {
if (s1.charAt(i - 1) == s3.charAt(i + j - 1) && dp[i - 1][j]) {
dp[i][j] = true;
} else if (s2.charAt(j - 1) == s3.charAt(i + j - 1) && dp[i][j - 1]) {
dp[i][j] = true;
}
}
}
return dp[len1][len2];
}
}
887. 鸡蛋掉落
public class Solution {
public int superEggDrop(int K, int N) {
// dp[i][j]：一共有 i 层楼梯的情况下，使用 j 个鸡蛋的最少实验的次数
// 注意：
// 1、i 表示的是楼层的大小，不是第几层的意思，例如楼层区间 [8, 9, 10] 的大小为 3，这一点是在状态转移的过程中调整的定义
// 2、j 表示可以使用的鸡蛋的个数，它是约束条件，我个人习惯放在后面的维度，表示消除后效性的意思
// 0 个楼层和 0 个鸡蛋的情况都需要算上去，虽然没有实际的意义，但是作为递推的起点，被其它状态值所参考
int[][] dp = new int[N + 1][K + 1];
// 由于求的是最小值，因此初始化的时候赋值为一个较大的数，9999 或者 i 都可以
for (int i = 0; i <= N; i++) {
Arrays.fill(dp[i], i);
}
// 初始化：填写下标为 0、1 的行和下标为 0、1 的列
// 第 0 行：楼层为 0 的时候，不管鸡蛋个数多少，都测试不出鸡蛋的 F 值，故全为 0
for (int j = 0; j <= K; j++) {
dp[0][j] = 0;
}
// 第 1 行：楼层为 1 的时候，0 个鸡蛋的时候，扔 0 次，1 个以及 1 个鸡蛋以上只需要扔 1 次
dp[1][0] = 0;
for (int j = 1; j <= K; j++) {
dp[1][j] = 1;
}
// 第 0 列：鸡蛋个数为 0 的时候，不管楼层为多少，也测试不出鸡蛋的 F 值，故全为 0
// 第 1 列：鸡蛋个数为 1 的时候，这是一种极端情况，要试出 F 值，最少次数就等于楼层高度（想想复杂度的定义）
for (int i = 0; i <= N; i++) {
dp[i][0] = 0;
dp[i][1] = i;
}
// 从第 2 行，第 2 列开始填表
for (int i = 2; i <= N; i++) {
for (int j = 2; j <= K; j++) {
for (int k = 1; k <= i; k++) {
// 碎了，就需要往低层继续扔：层数少 1 ，鸡蛋也少 1
// 不碎，就需要往高层继续扔：层数是当前层到最高层的距离差，鸡蛋数量不少
// 两种情况都做了一次尝试，所以加 1
dp[i][j] = Math.min(dp[i][j], Math.max(dp[k - 1][j - 1], dp[i - k][j]) + 1);
}
}
}
return dp[N][K];
}
}
public class Solution {
private int cal(int K, int T) {
if (T == 1 || K == 1) {
return T + 1;
}
return cal(K - 1, T - 1) + cal(K, T - 1);
}
public int superEggDrop(int K, int N) {
int T = 1;
while (cal(K, T) < N + 1) {
T++;
}
return T;
}
}
315. 计算右侧小于当前元素的个数
class Solution {
int[] res;
int[] index;//当前位置的数对应原数组的第几个位置
public List<Integer> countSmaller(int[] nums) {
res = new int[nums.length];
index = new int[nums.length];
for (int i = 0; i < index.length; i++) {
index[i] = i;
}
mergeSort(nums, 0, nums.length - 1);
List<Integer> r = Arrays.stream(res).boxed().collect(Collectors.toList());
return r;
}
private void mergeSort(int[] nums, int lo, int hi) {
if (lo >= hi) {
return;
}
int mid = lo + (hi - lo) / 2;
mergeSort(nums, lo, mid);
mergeSort(nums, mid + 1, hi);
int[] temp = new int[hi - lo + 1];
int[] tempindex = new int[hi - lo + 1];
int i = lo, j = mid + 1, pos = 0;
while (i <= mid && j <= hi) {
res[index[i]] += nums[i] <= nums[j] ? j - mid - 1 : 0;
tempindex[pos] = nums[i] <= nums[j] ? index[i] : index[j];
temp[pos++] = nums[i] <= nums[j] ? nums[i++] : nums[j++];
}
while (i <= mid) {
res[index[i]] += j - mid - 1;
tempindex[pos] = index[i];
temp[pos++] = nums[i++];
}
while (j <= hi) {
tempindex[pos] = index[j];
temp[pos++] = nums[j++];
}
System.arraycopy(tempindex, 0, index, lo, pos);
System.arraycopy(temp, 0, nums, lo, pos);
}
}
493. 翻转对
class Solution {
public int reversePairs(int[] nums) {
return mergeSort(nums, 0, nums.length - 1);
}
private int mergeSort(int[] nums, int lo, int hi) {
if (lo >= hi) {
return 0;
}
int mid = lo + (hi - lo) / 2;
int res = 0;
res += mergeSort(nums, lo, mid) + mergeSort(nums, mid + 1, hi);
int[] temp = new int[hi - lo + 1];
int i = lo, j = mid + 1, pos = 0;
//先单独统计，因为合并的时候统计不了
while (i <= mid && j <= hi) {
if ((long) nums[i] > 2 * (long) nums[j]) {
res += mid - i + 1;
j++;
} else {
i++;
}
}
i = lo;
j = mid + 1;
while (i <= mid && j <= hi) {
temp[pos++] = nums[i] <= nums[j] ? nums[i++] : nums[j++];
}
while (i <= mid) {
temp[pos++] = nums[i++];
}
while (j <= hi) {
temp[pos++] = nums[j++];
}
System.arraycopy(temp, 0, nums, lo, pos);
return res;
}
}
407. 接雨水 II
class Solution {
public int trapRainWater(int[][] heightMap) {
if (heightMap.length == 0) {
return 0;
}
Queue<int[]> pq = new PriorityQueue<>((o1, o2) -> o1[2] - o2[2]);
int row = heightMap.length;
int col = heightMap[0].length;
boolean[][] isVisited = new boolean[row][col];
int res = 0;
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (i == 0 || i == row - 1 || j == 0 || j == col - 1) {
pq.offer(new int[]{i, j, heightMap[i][j]});
isVisited[i][j] = true;
}
}
}
int[] dirX = {1, -1, 0, 0};
int[] dirY = {0, 0, 1, -1};
while (!pq.isEmpty()) {
int[] front = pq.poll();
for (int i = 0; i < 4; i++) {
int nx = front[0] + dirX[i];
int ny = front[1] + dirY[i];
if (nx >= 0 && nx < row && ny >= 0 && ny < col && isVisited[nx][ny] == false) {
if (heightMap[nx][ny] < front[2]) {
res += front[2] - heightMap[nx][ny];
}
pq.offer(new int[]{nx, ny, Math.max(heightMap[nx][ny], front[2])});
isVisited[nx][ny] = true;
}
}
}
return res;
}
}
295. 数据流的中位数
class MedianFinder {
Queue<Integer> maxHeap;
Queue<Integer> minHeap;
int size = 0;
/**
* initialize your data structure here.
*/
public MedianFinder() {
this.minHeap = new PriorityQueue<>();
this.maxHeap = new PriorityQueue<>((o1, o2) -> o2.compareTo(o1));
}
public void addNum(int num) {
size++;
maxHeap.add(num);
minHeap.add(maxHeap.poll());
if (size % 2 == 1) {
maxHeap.add(minHeap.poll());
}
}
public double findMedian() {
if (size % 2 == 1) {
return maxHeap.peek();
} else {
return (maxHeap.peek() + minHeap.peek()) / 2.0;
}
}
}
188. 买卖股票的最佳时机 IV
class Solution {
public int maxProfit(int k, int[] prices) {
if (prices.length == 0) {
return 0;
}
int[][][] dp = new int[prices.length][k + 1][2];
for (int j = k; j >= 1; j--) {
dp[0][j][1] = -prices[0];
}
for (int i = 1; i < prices.length; i++) {
for (int j = k; j >= 1; j--) {
dp[i][j][0] = Math.max(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i]);
dp[i][j][1] = Math.max(dp[i - 1][j][1], dp[i - 1][j - 1][0] - prices[i]);
}
}
return dp[prices.length - 1][k][0];
}
}
862. 和至少为 K 的最短子数组
312. 戳气球
class Solution {
public int maxCoins(int[] nums) {
int[] newNums = new int[nums.length + 2];
newNums[0] = newNums[nums.length + 1] = 1;//注意这里是1，不是0
System.arraycopy(nums, 0, newNums, 1, nums.length);
nums = newNums;
int[][] dp = new int[nums.length][nums.length];
for (int L = 3; L <= nums.length; L++) {
for (int i = 0; i + L - 1 < nums.length; i++) {
int j = i + L - 1;
for (int k = i + 1; k < j; k++) {
dp[i][j] = Math.max(dp[i][j], dp[i][k] + dp[k][j] + nums[i] * nums[k] * nums[j]);
}
}
}
return dp[0][nums.length - 1];
}
}
224. 基本计算器
class Solution {
Map<String, Integer> inPriority, outPriority;
public Solution() {
inPriority = new HashMap<>();//栈内优先级
outPriority = new HashMap<>();//栈外优先级
inPriority.put("#", 0);
inPriority.put("(", 1);
inPriority.put("*", 5);
inPriority.put("/", 5);
inPriority.put("+", 3);
inPriority.put("-", 3);
inPriority.put(")", 6);
outPriority.put("#", 0);
outPriority.put("(", 6);
outPriority.put("*", 4);
outPriority.put("/", 4);
outPriority.put("+", 2);
outPriority.put("-", 2);
outPriority.put(")", 1);
}
public int calculate(String s) {
List<String> infix = new ArrayList<>();//中缀表达式
boolean flag = false;
int num = 0;
for (char c : s.toCharArray()) {
if (c == ' ') {
continue;
} else if (Character.isDigit(c)) {
flag = true;
num = num * 10 + (c - '0');
} else {
if (flag == true) {
infix.add(String.valueOf(num));
flag = false;
num = 0;
}
infix.add(String.valueOf(c));
}
}
if (flag == true) {
infix.add(String.valueOf(num));
}
List<String> rpn = getRpn(infix);
return (int) cal(rpn);
}
//中缀表达式转后缀
public List<String> getRpn(List<String> infix) {
Deque<String> stack = new ArrayDeque<>();
stack.push("#");
List<String> rpn = new ArrayList<>();
for (String str : infix) {
if ("(".equals(str) || ")".equals(str) || "+".equals(str) || "-".equals(str) ||
"*".equals(str) || "/".equals(str)) {
if (comparePriority(stack.peek(), str) == 1) {
stack.push(str);
} else if (comparePriority(stack.peek(), str) == 0) {
stack.pop();
} else {
while (comparePriority(stack.peek(), str) == -1) {
String z = stack.pop();
rpn.add(z);
}
if (")".equals(str)) {
stack.pop();
} else {
stack.push(str);
}
}
} else {
rpn.add(str);
}
}
while (!stack.isEmpty()) {
rpn.add(stack.pop());
}
rpn.remove(rpn.size() - 1);
return rpn;
}
private int comparePriority(String in, String out) {
if (outPriority.get(out) > inPriority.get(in)) {
return 1;
} else if (outPriority.get(out) == inPriority.get(in)) {
return 0;
} else {
return -1;
}
}
//后缀表达式求值
public double cal(List<String> s) {
Deque<Double> stack = new ArrayDeque<>();
for (int i = 0; i < s.size(); i++) {
double a, b;
if (s.get(i).equals("+")) {
b = stack.pop();
a = stack.pop();
stack.push(a + b);
continue;
} else if (s.get(i).equals("-")) {
b = stack.pop();
a = stack.pop();
stack.push(a - b);
continue;
} else if (s.get(i).equals("*")) {
b = stack.pop();
a = stack.pop();
stack.push(a * b);
continue;
} else if (s.get(i).equals("/")) {
b = stack.pop();
a = stack.pop();
stack.push(a / b);
continue;
} else {
stack.push(Double.valueOf(s.get(i)));
}
}
return stack.peek();
}
}
403. 青蛙过河
dp[i]代表可以以大小为jumpsize的一跳跳到第i个位置的集合。
边界：
dp[0]的集合只有一个元素0，只需要0跳就可以到达第一个位置。
转移方程：
遍历集合，那么下一跳可以跳的步数为step-1 ~ step+1，判断可以到达的位置是否有石块，如果有，就把那个石块对应的集合增加这一跳的步数。
最后判断最后一个石头的集合是否为空即可。如果不为空，说明可以跳到这里来。
class Solution {
public boolean canCross(int[] stones) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < stones.length; i++) {
map.put(stones[i], i);
}
Set<Integer>[] dp = new HashSet[stones.length];
for (int i = 0; i < dp.length; i++) {
dp[i] = new HashSet<>();
}
dp[0].add(0);
for (int i = 0; i < stones.length; i++) {
for (int j : dp[i]) {
for (int step = j - 1; step <= j + 1; step++) {
if (step > 0 && map.containsKey(stones[i] + step)) {
dp[map.get(stones[i] + step)].add(step);
}
}
}
}
return dp[stones.length - 1].size() > 0;
}
}
679. 24 点游戏
class Solution {
private boolean dfs(List<Double> list) {
if (list.size() == 1) {
return Math.abs(list.get(0) - 24) < 1e-6;
}
for (int i = 0; i < list.size(); i++) {
for (int j = 0; j < list.size(); j++) {
if (i == j) {
continue;
}
List<Double> newList = new ArrayList<>();
for (int k = 0; k < list.size(); k++) {
if (k != i && k != j) {
newList.add(list.get(k));
}
}
for (int z = 0; z < 4; z++) {
if (z == 0) {
newList.add(list.get(i) + list.get(j));
} else if (z == 1) {
newList.add(list.get(i) - list.get(j));
} else if (z == 2) {
newList.add(list.get(i) * list.get(j));
} else if (z == 3) {
if (list.get(j) == 0) {
continue;
}
newList.add(list.get(i) / list.get(j));
}
if (dfs(newList)) {
return true;
} else {
newList.remove(newList.size() - 1);
}
}
}
}
return false;
}
public boolean judgePoint24(int[] nums) {
List<Double> list = new ArrayList<>();
for (int i : nums) {
list.add((double) i);
}
return dfs(list);
}
}
1044. 最长重复子串
class Solution {
long mod = (long)Math.pow(2, 37) - 1;
long a = 26;
int nums[];
int n;
public String longestDupSubstring(String S) {
nums = new int [S.length()];
for (int i = 0; i < S.length(); i ++) {
nums[i] = S.charAt(i) - 'a';
}
this.n = S.length();
int left = 1;
int right = n;
while (left != right) {
int mid = left + (right - left) / 2;
if (search(mid) != -1) left = mid + 1;
else right = mid;
}
int begin = search(left - 1);
if (begin != -1) return S.substring(begin, begin + left - 1);
return "";
}
public int search(int length) {
long cur = 0;
for (int i = 0; i < length; i ++) {
cur = (cur * a + nums[i]) % mod;
}
long aL = 1;
for (int i = 0; i < length; i++) {
aL = (aL * a ) % mod;
}
HashSet<Long> hs = new HashSet<>();
hs.add(cur);
for (int i = 1; i <= n - length; i ++) {
cur = (cur * a - aL * nums[i - 1] % mod + mod) % mod;
cur = (cur + nums[i + length - 1]) % mod;
if (hs.contains(cur)) return i;
hs.add(cur);
}
return -1;
}
}
410. 分割数组的最大值
dp[i][j]代表数组的前i个数分成m个子数组，和的最大值最小。
边界：
dp[0][0] = 0
转移方程：
class Solution {
public int splitArray(int[] nums, int m) {
int n = nums.length;
int[][] dp = new int[n + 1][m + 1];
for (int i = 0; i < dp.length; i++) {
Arrays.fill(dp[i], Integer.MAX_VALUE);
}
int[] preSum = new int[n + 1];
for (int i = 0; i < preSum.length - 1; i++) {
preSum[i + 1] = preSum[i] + nums[i];
}
dp[0][0] = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= Math.min(i, m); j++) {
for (int k = 0; k < i; k++) {
dp[i][j] = Math.min(dp[i][j], Math.max(dp[k][j - 1], preSum[i] - preSum[k]));
}
}
}
return dp[n][m];
}
}
网友评论