class Solution{
Map<Integer,TreeNode> parent = new HashMap<Integer,TreeNode>();
Set<Integer> visited = new HashSet<Integer>();
public void dfs(TreeNode root){
if(root.left!=null){
parent.put(root.left.val,root);
dfs(root.left);
}
if(root.right!=null){
parent.put(root.right.val,root);
dfs(root.right);
}
}
public TreeNode lowestCommonAncestor(TreeNode root,TreeNode p,TreeNode q){
dfs(root);
while(p != null){
visited.add(p.val);
p = parent.get(p.val);
}
while (q!=null){
if(visited.contains(q.val)){
return q;
}
q=parent.get(q.val);
}
return
}
}https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/
public int longestConsecutive(int[] nums) {
if (nums.length == 0) return 0;
// 首次遍历，与邻居结盟
UnionFind uf = new UnionFind(nums);
for (int v : nums)
uf.union(v, v + 1); // uf.union() 结盟
// 二次遍历，记录领队距离
int max = 1;
for (int v : nums)
max = Math.max(max, uf.find(v) - v + 1); // uf.find() 查找领队
return max;
}
class UnionFind {
private int count;
private Map<Integer, Integer> parent; // (curr, leader)
UnionFind(int[] arr) {
parent = new HashMap<>();
for (int v : arr)
parent.put(v, v); // 初始时，各自为战，自己是自己的领队
count = parent.size(); // 而非 arr.length，因可能存在同 key 的情况
// 感谢 [@icdd](/u/icdd/) 同学的指正
}
// 结盟
void union(int p, int q) {
// 不只是 p 与 q 结盟，而是整个 p 所在队伍 与 q 所在队伍结盟
// 结盟需各领队出面，而不是小弟出面
Integer rootP = find(p), rootQ = find(q);
if (rootP == rootQ) return;
if (rootP == null || rootQ == null) return;
// 结盟
parent.put(rootP, rootQ); // 谁大听谁
// 应取 max，而本题已明确 p < q 才可这么写
// 当前写法有损封装性，算法题可不纠结
count--;
}
// 查找领队
Integer find(int p) {
if (!parent.containsKey(p))
return null;
// 递归向上找领队
int root = p;
while (root != parent.get(root))
root = parent.get(root);
// 路径压缩：扁平化管理，避免日后找领队层级过深
while (p != parent.get(p)) {
int curr = p;
p = parent.get(p);
parent.put(curr, root);
}
return root;
}
}[java] 排序/集合/哈希表/并查集 - 最长连续序列 - 力扣（LeetCode） (leetcode-cn.com)
class Solution{
public int minDistance(String s1,String s2){
int m = s1.length(),n = s2.length();
int[][] dp = new int[m+1][n+1];
//base case，从一个k变到某字符串的操作数目就是该字符串的长度
for(int i = 1;i<=m;i++){
dp[i][0] = i;
}
for(int j = 1;j<=n;j++){
dp[0][j] = j;
}
//自底向上，开始求解
for(int i = 1;i<=m;i++){
for(int j = 1;j<=n;j++){
//i和j表示的分别是s1和s2的各个前i/j长度的字串
if(s1.charAt(i-1)==s2.charAt(j-1)){
//两字符相等，直接跳过当前字符
dp[i][j] = dp[i-1][j-1];
}else{
//两字符不相等，去试增删替三种情况，求个最小值
dp[i][j] = min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1]);
}
}
}
return dp[m][n];
}
int min(int a, int b, int c) {
return Math.min(a, Math.min(b, c));
}
}public int maxProfit(int[] prices){
int len = prices.length;
if(len<2){
return 0;
}
//二维数组，第一格表示第几天，第二格表示是否持有股票
int[][] dp = new int[len][2];
//0:持有
//1:不持有
//base case
dp[0][0] = 0;
dp[0][1] = -prices[0];
//迭代
for(int i = 1;i<len;i++){
//第i天不持有股票的最大利润是前一天持有股票今天卖掉的钱和前一天不持有股票的最大利润，二者中的较大者。
dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1] + prices[i]);
//第i天持有股票的最大利润是前一天持有股票的最大利润和前一天不持有股票但是今天买入股票的钱，二者中的较大者。
dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0] - prices[i]);
}
//最后一天不持有股票
return dp[len-1][0];
}// 有效括号的最长长度
// 子串问题：严格以每个结尾计算个答案，最终答案必在其中
public static int longestValidParentheses(String s) {
if (s == null || s.length() < 2) return 0;
int[] dp = new int[s.length()]; // dp[i]：严格以i位置结尾，形成的有效括号子串最长长度是多少
int max = 0; // 最终的答案
// dp[0] = 0; // 默认
for (int i = 1; i < s.length(); i++) {
// if (s.charAt(i) == '(') dp[i] = 0; 以左括号结尾，无效
if (s.charAt(i) == ')') {
int preLen = dp[i - 1]; // 前面已经形成的有效括号长度
int pre = i - 1 - preLen; // 寻找与当前的右括号相匹配的左括号位置：前面有效括号长度再往前一个位置
if (pre >= 0 && s.charAt(pre) == '(') { // 如果寻找到左括号：前面有效括号长度再往前一个位置是左括号
dp[i] = dp[i-1] + 2; // 可以与当前的右括号闭合，有效长度增加2
// 【注意】此时，需要再往前看下，是否还有有效长度，如果有，合并过来
// 例如："()(()())" 当前在计算最后一个位置时，dp[7]已经等于 dp[6]+2 = 4+2
// 但需要再往前看一眼，dp[1]还有有效长度，合并过来 dp[7] = 4+2+2
// 那是否还需要再往前看？
// 不需要了，因为，如果前面还有有效长度，其长度肯定已经合并到dp[2]上了
// 因此，每次只需要再往前多看一眼就可以
if (pre-1 >= 0) {
dp[i] += dp[pre-1];
}
}
max = Math.max(max, dp[i]); // 严格以每个结尾抓一个答案，最终答案必在其中
}
}
return max;
}https://leetcode-cn.com/problems/longest-valid-parentheses
使用Map维护运算的优先级。
class Solution {
// 使用 map 维护一个运算符优先级
// 这里的优先级划分按照「数学」进行划分即可
Map<Character, Integer> map = new HashMap<>(){{
put('-', 1);
put('+', 1);
put('*', 2);
put('/', 2);
put('%', 2);
put('^', 3);
}};
public int calculate(String s) {
// 将所有的空格去掉
s = s.replaceAll(" ", "");
char[] cs = s.toCharArray();
int n = s.length();
// 存放所有的数字
Deque<Integer> nums = new ArrayDeque<>();
// 为了防止第一个数为负数，先往 nums 加个 0
nums.addLast(0);
// 存放所有「非数字以外」的操作
Deque<Character> ops = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
char c = cs[i];
if (c == '(') {
ops.addLast(c);
} else if (c == ')') {
// 计算到最近一个左括号为止
while (!ops.isEmpty()) {
if (ops.peekLast() != '(') {
calc(nums, ops);
} else {
ops.pollLast();
break;
}
}
} else {
if (isNumber(c)) {
int u = 0;
int j = i;
// 将从 i 位置开始后面的连续数字整体取出，加入 nums
while (j < n && isNumber(cs[j])) u = u * 10 + (cs[j++] - '0');
nums.addLast(u);
i = j - 1;
} else {
if (i > 0 && (cs[i - 1] == '(' || cs[i - 1] == '+' || cs[i - 1] == '-')) {
nums.addLast(0);
}
// 有一个新操作要入栈时，先把栈内可以算的都算了
// 只有满足「栈内运算符」比「当前运算符」优先级高/同等，才进行运算
// wht：确保同优先级的操作只有一个，且栈内表达式的优先级至少是递增的，这样可以安全c
while (!ops.isEmpty() && ops.peekLast() != '(') {
char prev = ops.peekLast();
if (map.get(prev) >= map.get(c)) {
calc(nums, ops);
} else {
break;
}
}
ops.addLast(c);
}
}
}
// 将剩余的计算完
while (!ops.isEmpty()) calc(nums, ops);
return nums.peekLast();
}
void calc(Deque<Integer> nums, Deque<Character> ops) {
if (nums.isEmpty() || nums.size() < 2) return;
if (ops.isEmpty()) return;
int b = nums.pollLast(), a = nums.pollLast();
char op = ops.pollLast();
int ans = 0;
if (op == '+') ans = a + b;
else if (op == '-') ans = a - b;
else if (op == '*') ans = a * b;
else if (op == '/') ans = a / b;
else if (op == '^') ans = (int)Math.pow(a, b);
else if (op == '%') ans = a % b;
nums.addLast(ans);
}
boolean isNumber(char c) {
return Character.isDigit(c);
}
}基本计算器Ⅲ