- 75. 颜色分类
class Solution {
public void sortColors(int[] nums) {
int lastZero = -1, firstTwo = nums.length;
int curr = 0;
while (curr < firstTwo) {
// 红色
if (nums[curr] == 0) {
// 与lastZero的下一位进行交换
swap(nums, curr, lastZero + 1);
lastZero++;
// 防止curr是0
curr++;
}
// 白色
else if (nums[curr] == 1) {
curr++;
} else {
// 与firstTwo的前一位进行交换
swap(nums, curr, firstTwo - 1);
firstTwo--;
}
}
}
private void swap(int[] nums, int i, int j) {
if (i == j) return;
nums[i] = nums[i] ^ nums[j];
nums[j] = nums[i] ^ nums[j];
nums[i] = nums[i] ^ nums[j];
}
}
- 76. 最小覆盖子串
class Solution {
/**
* 滑动窗口
*/
public String minWindow(String s, String t) {
// 异常判断
if (s == null || t == null || s.length() == 0 || t.length() == 0) return "";
// 用来存储t中每个字符出现的次数
Map<Character, Integer> ht = new HashMap<>();
// 用来当前窗口中每个字符出现的次数
Map<Character, Integer> hs = new HashMap<>();
// 遍历进行记录
for (char c : t.toCharArray()) {
ht.put(c, ht.getOrDefault(c, 0) + 1);
}
String answer = "";
int minLen = Integer.MAX_VALUE;
int n = s.length();
// 如果出现过了就移动
int end = 0;
// 记录匹配了几次
int matched = 0;
for (int start = 0; start < n; start++) {
// 不是每一个字符都匹配上
while (end < n && matched < ht.size()) {
char ch = s.charAt(end);
hs.put(ch, hs.getOrDefault(ch, 0) + 1);
// 如果出现的次数是一样的代表匹配上了
if (hs.get(ch).equals(ht.getOrDefault(ch, 0))) {
matched++;
}
// 没有匹配上,右指针往右边移动一
end++;
}
// 如果匹配完t中所有出现的字符之后
if (matched == ht.size()) {
if (end - start < minLen) {
minLen = end - start;
answer = s.substring(start, end);
}
}
// 左指针移动回去
char ch = s.charAt(start);
hs.put(ch, hs.get(ch) - 1);
if (hs.get(ch).equals(ht.getOrDefault(ch, 0) - 1)) {
matched--;
}
}
return answer;
}
}
- 78. 子集
class Solution {
LinkedList<List<Integer>> pathList = new LinkedList<>();
LinkedList<Integer> path = new LinkedList<>();
public List<List<Integer>> subsets(int[] nums) {
backtrack(nums, 0);
return pathList;
}
private void backtrack(int[] nums, int start) {
pathList.add(new LinkedList<>(path));
while (start < nums.length) {
path.add(nums[start]);
backtrack(nums, start + 1);
path.removeLast();
start++;
}
}
}
- 79. 单词搜索
int m;
int n;
int w;
char[] letters;
char[][] board;
boolean[][] visited;
/**
* 回溯法
*/
public boolean exist(char[][] board, String word) {
this.m = board.length;
this.n = board[0].length;
this.w = word.length();
this.letters = word.toCharArray();
this.board = board;
this.visited = new boolean[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
// 0 是word里的index
boolean res = backtrack(i, j, 0);
if (res) return true;
}
}
return false;
}
private boolean backtrack(int i, int j, int wordIndex) {
if (wordIndex >= w) return true;
if (i < 0 || j < 0 || i >= m || j >= n || letters[wordIndex] != board[i][j] || visited[i][j]) return false;
// 访问过了就不能再去看了
visited[i][j] = true;
boolean res = backtrack(i + 1, j, wordIndex + 1) || backtrack(i, j + 1, wordIndex + 1)
||
backtrack(i - 1, j, wordIndex + 1) || backtrack(i, j - 1, wordIndex + 1);
visited[i][j] = false;
return res;
}
- 84. 柱状图中最大的矩形
- 85. 最大矩形
- 94. 二叉树的中序遍历
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
/**
* 递归
* 判断左子树和右子树是否是对称的
* 左边右子树=右边的左子树&&左边的左子树=右边的右子树
*/
public boolean isSymmetric(TreeNode root) {
if (root == null) return true;
// 检查两棵子树是否对称
return check(root.left, root.right);
}
private boolean check(TreeNode left, TreeNode right) {
if (left == null && right == null) return true;
if (left == null || right == null) return false;
// 两个根节点需要相同
if (left.val != right.val) return false;
// 左右子节点需要对称相同
return check(left.right, right.left) && check(left.left, right.right);
}
}
- 96. 不同的二叉搜索树
class Solution {
/**
* 1 ~ n
* [1,i-1] i [i+1,n]
* f(n) = sum( f(i-1) * f(n-i) )
*/
public int numTrees(int n) {
int[] dp = new int[n + 1];
dp[0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= i - 1; j++) {
dp[i] += dp[j] * dp[i - 1 - j ];
}
}
return dp[n];
}
}
- 98. 验证二叉搜索树
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
/**
* 节点的左子树只包含 小于 当前节点的数。
* 节点的右子树只包含 大于 当前节点的数。
* 所有左子树和右子树自身必须也是二叉搜索树。
*/
public boolean isValidBST(TreeNode root) {
return isValid(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
private boolean isValid(TreeNode root, long minValue, long maxValue) {
if (root == null) return true;
if (root.left != null) {
// 左节点的值必须大于最小值,小于根节点
if (root.left.val > minValue && root.left.val < root.val) {
boolean valid = isValid(root.left, minValue, root.val);
if (!valid) return false;
} else {
return false;
}
}
if (root.right != null) {
if (root.right.val < maxValue && root.right.val > root.val) {
boolean valid = isValid(root.right, root.val, maxValue);
if (!valid) return false;
} else {
return false;
}
}
return true;
}
}
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public boolean isValidBST(TreeNode root) {
return isValid(root, null, null);
}
// 以 root 为根的子树节点必须满足 max.val > root.val > min.val
private boolean isValid(TreeNode root, TreeNode min, TreeNode max) {
if (root == null) return true;
if (min != null && min.val >= root.val) return false;
if (max != null && max.val <= root.val) return false;
return isValid(root.left, min, root) && isValid(root.right, root, max);
}
}
- 101. 对称二叉树
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
/**
* 递归
* 判断左子树和右子树是否是对称的
* 左边右子树=右边的左子树&&左边的左子树=右边的右子树
*/
public boolean isSymmetric(TreeNode root) {
if (root == null) return true;
// 检查两棵子树是否对称
return check(root.left, root.right);
}
private boolean check(TreeNode left, TreeNode right) {
if (left == null && right == null) return true;
if (left == null || right == null) return false;
// 两个根节点需要相同
if (left.val != right.val) return false;
// 左右子节点需要对称相同
return check(left.right, right.left) && check(left.left, right.right);
}
}
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）