LeetCode算法题

day01

1.二叉树的最近公共祖先

算法思想：递归+回溯。首先先使用先序遍历，遍历二叉树，在遍历的过程中，还需要保存节点的父节点val值，将遍历节点的val当作key，将父节点的val当作value存入一个Map集合，然后从需要查找最近公共祖先的两个节点中的某一个节点出发，回溯他的父节点，并将回溯路径存入Set集合，回溯完成后，从另一个节点回溯，如果回溯的过程中，某一个节点在set集合出现，那么该节点就是最近的公共祖先，否则为空。

代码如下：

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 null; } } class TreeNode{ int val; TreeNode left; TreeNode right; TreeNode(int x){ val = x; } }

2.每日温度

算法思想：定义一个栈，栈中存储未找到下一个更大温度的日期索引；遍历每个日期的温度，对当前遍历的日期索引：

1. 若栈不为空，且当前日期的温度 > 栈顶索引对应的温度，则循环弹出栈顶索引：
   • 计算 “当前索引 - 栈顶索引”（即栈顶索引对应的日期，需要等待的天数）；
   • 将该天数存入 ans 数组中与栈顶索引对应的位置；
2. 重复步骤 1，直到栈为空，或当前日期的温度 ≤ 栈顶索引对应的温度；
3. 将当前日期的索引压入栈中；遍历结束后，ans 数组中未被赋值的位置（无更大温度的日期）默认值为 0，直接返回 ans 数组。

   class Solution { public int[] dailyTemperatures(int[] temperatures) { int length = temperatures.length; int[] ans = new int[length]; Deque<Integer> stack = new LinkedList<Integer>(); for (int i = 0; i < length; i++) { int temperature = temperatures[i]; while (!stack.isEmpty() && temperature > temperatures[stack.peek()]) { int prevIndex = stack.pop(); ans[prevIndex] = i - prevIndex; } stack.push(i); } return ans; } }