Monotonic Stack
PB 739. Daily Temperatures
temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]
因为要找变暖的日子，也就是温度比现在大的，stack每次遇到新的element，stack里边所有比cur小的数都要pop出去，新元素就是他们要的日子
class Solution {
public int[] dailyTemperatures(int[] temperatures) {
Deque<Integer> stack = new ArrayDeque<>();
int[] res = new int[temperatures.length];
for (int i = 0; i < temperatures.length; i++) {
// 注意，易错点 判断stack为空 和后边判断的是temperatures的值，不是index比大小
while(!stack.isEmpty() && temperatures[i] > temperatures[stack.peekLast()]) {
int index = stack.pollLast();
res[index] = i - index;
}
stack.offerLast(i);
}
return res;
}
}
PB 901. Online Stock Span
class StockSpanner {
Deque<int[]> stack;
public StockSpanner() {
stack = new ArrayDeque<>();
}
public int next(int price) {
int res = 1;
// 注意是大于等于
while(!stack.isEmpty() && price >= stack.peekLast()[0]) {
res += stack.pollLast()[1];
}
stack.offerLast(new int[] {price, res});
return res;
}
}
interval
PB 435. Non-overlapping Intervals
DP问题，可以用贪心做，也可以DP。
以起始时间排序，尽可能多的遍历所有case
class Solution {
public int eraseOverlapIntervals(int[][] intervals) {
if (intervals.length == 0) {
return 0;
}
Arrays.sort(intervals, new Comparator<int[]>() {
public int compare(int[] interval1, int[] interval2) {
return interval1[0] - interval2[0];
}
});
int n = intervals.length;
int[] f = new int[n];
Arrays.fill(f, 1);
for (int i = 1; i < n; ++i) {
for (int j = 0; j < i; ++j) {
if (intervals[j][1] <= intervals[i][0]) {
f[i] = Math.max(f[i], f[j] + 1);
}
}
}
return n - Arrays.stream(f).max().getAsInt();
}
}
PB 452. Minimum Number of Arrows to Burst Balloons
class Solution {
public int findMinArrowShots(int[][] points) {
if (points.length == 0) {
return 0;
}
// *********************** 用Long
Arrays.sort(points, (a, b) -> Long.compare(a[1], b[1]));
int res = 1;
int end = points[0][1];
for (int i = 1; i < points.length; i++) {
if (points[i][0] > end) {
res++;
end = points[i][1];
}
}
return res;
}
}
Trie Tree
PB 208. Implement Trie (Prefix Tree)
A trie (pronounced as “try”) or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker.
Implement the Trie class:
Trie() Initializes the trie object. void insert(String word) Inserts the string word into the trie. boolean search(String word) Returns true if the string word is in the trie (i.e., was inserted before), and false otherwise. boolean startsWith(String prefix) Returns true if there is a previously inserted string word that has the prefix prefix, and false otherwise.
1 <= word.length, prefix.length <= 2000 word and prefix consist only of lowercase English letters. At most 3 * 104 calls in total will be made to insert, search, and startsWith.
class Trie {
Map<Character, Trie> childs;
boolean isEndOfWord;
public Trie() {
this.childs = new HashMap<>();
this.isEndOfWord = false;
}
public void insert(String word) {
Trie currentNode = this;
for (char ch : word.toCharArray()) {
if (!currentNode.childs.containsKey(ch)) {
currentNode.childs.put(ch, new Trie());
}
currentNode = currentNode.childs.get(ch);
}
currentNode.isEndOfWord = true;
}
public boolean search(String word) {
Trie currentNode = this;
for (char ch : word.toCharArray()) {
if (!currentNode.childs.containsKey(ch)) {
return false;
}
currentNode = currentNode.childs.get(ch);
}
// 注意不可以用currentNode.childs.size() == 0来判断
return currentNode.isEndOfWord;
}
public boolean startsWith(String prefix) {
Trie currentNode = this;
for (char ch : prefix.toCharArray()) {
if (!currentNode.childs.containsKey(ch)) {
return false;
}
currentNode = currentNode.childs.get(ch);
}
return true;
}
}
// or official result:
class Trie {
private Trie[] children;
private boolean isEnd;
public Trie() {
children = new Trie[26];
isEnd = false;
}
public void insert(String word) {
Trie node = this;
for (int i = 0; i < word.length(); i++) {
char ch = word.charAt(i);
int index = ch - 'a';
if (node.children[index] == null) {
node.children[index] = new Trie();
}
node = node.children[index];
}
node.isEnd = true;
}
public boolean search(String word) {
Trie node = searchPrefix(word);
return node != null && node.isEnd;
}
public boolean startsWith(String prefix) {
return searchPrefix(prefix) != null;
}
private Trie searchPrefix(String prefix) {
Trie node = this;
for (int i = 0; i < prefix.length(); i++) {
char ch = prefix.charAt(i);
int index = ch - 'a';
if (node.children[index] == null) {
return null;
}
node = node.children[index];
}
return node;
}
}
PB 1268. Search Suggestions System
You are given an array of strings products and a string searchWord.
Design a system that suggests at most three product names from products after each character of searchWord is typed. Suggested products should have common prefix with searchWord. If there are more than three products with a common prefix return the three lexicographically minimums products.
Return a list of lists of the suggested products after each character of searchWord is typed.
Example 1:
Input: products = [“mobile”,”mouse”,”moneypot”,”monitor”,”mousepad”], searchWord = “mouse” Output: [[“mobile”,”moneypot”,”monitor”],[“mobile”,”moneypot”,”monitor”],[“mouse”,”mousepad”],[“mouse”,”mousepad”],[“mouse”,”mousepad”]] Explanation: products sorted lexicographically = [“mobile”,”moneypot”,”monitor”,”mouse”,”mousepad”]. After typing m and mo all products match and we show user [“mobile”,”moneypot”,”monitor”]. After typing mou, mous and mouse the system suggests [“mouse”,”mousepad”].
class TrieNode {
Map<Character, TrieNode> children;
List<String> words;
public TrieNode() {
this.children = new HashMap<>();
this.words = new ArrayList<>();
}
}
class Solution {
public List<List<String>> suggestedProducts(String[] products, String searchWord) {
TrieNode root = new TrieNode();
for (String word : products) {
addWord(root, word);
}
List<List<String>> ans = new ArrayList<>();
TrieNode cur = root;
boolean flag = false;
for (char ch : searchWord.toCharArray()) {
if (flag || !cur.children.containsKey(ch)) {
ans.add(new ArrayList<>());
flag = true;
} else {
cur = cur.children.get(ch);
ans.add(new ArrayList<>(cur.words));
}
}
return ans;
}
// 推荐至多三个，所以每次sort后保留三个
private void addWord(TrieNode root, String word) {
TrieNode cur = root;
for (char ch : word.toCharArray()) {
cur.children.putIfAbsent(ch, new TrieNode());
cur = cur.children.get(ch);
cur.words.add(word);
Collections.sort(cur.words);
if (cur.words.size() > 3) {
cur.words.remove(cur.words.size() - 1);
}
}
}
}
Graph DFS
PB 841. Keys and Rooms
There are n rooms labeled from 0 to n - 1 and all the rooms are locked except for room 0. Your goal is to visit all the rooms. However, you cannot enter a locked room without having its key.
When you visit a room, you may find a set of distinct keys in it. Each key has a number on it, denoting which room it unlocks, and you can take all of them with you to unlock the other rooms.
Given an array rooms where rooms[i] is the set of keys that you can obtain if you visited room i, return true if you can visit all the rooms, or false otherwise.
Input: rooms = [[1,3],[3,0,1],[2],[0]] Output: false Explanation: We can not enter room number 2 since the only key that unlocks it is in that room.
class Solution {
public boolean canVisitAllRooms(List<List<Integer>> rooms) {
boolean[] visit = new boolean[rooms.size()];
visitRooms(rooms, visit, 0);
for (boolean v : visit) {
if (!v) return false;
}
return true;
// Deque<Integer> keys = new ArrayDeque();
// keys.offerLast(0);
}
public void visitRooms(List<List<Integer>> rooms, boolean[] visit, int location) {
if (visit[location]) return;
visit[location] = true;
for (Integer room : rooms.get(location)) {
visitRooms(rooms, visit, room);
}
}
}
PB 547. Number of Provinces
There are n cities. Some of them are connected, while some are not. If city a is connected directly with city b, and city b is connected directly with city c, then city a is connected indirectly with city c.
A province is a group of directly or indirectly connected cities and no other cities outside of the group.
You are given an n x n matrix isConnected where isConnected[i][j] = 1 if the ith city and the jth city are directly connected, and isConnected[i][j] = 0 otherwise.
Return the total number of provinces.
isConnected = [[1,1,0],[1,1,0],[0,0,1]] output = 2
class Solution {
public int findCircleNum(int[][] isConnected) {
boolean[] visit = new boolean[isConnected.length];
int res = 0;
for (int i = 0; i < isConnected.length; i++) {
if (!visit[i]) {
res++;
findCities(isConnected, visit, i);
}
}
return res;
}
public void findCities(int[][] isConnected, boolean[] visit, int location) {
if (visit[location]) return;
visit[location] = true;
for (int i = 0; i < isConnected[location].length; i++) {
if (isConnected[location][i] == 1 && !visit[i]) {
findCities(isConnected, visit, i);
}
}
}
}
PB 1466. Reorder Routes to Make All Paths Lead to the City Zero
There are n cities numbered from 0 to n - 1 and n - 1 roads such that there is only one way to travel between two different cities (this network form a tree). Last year, The ministry of transport decided to orient the roads in one direction because they are too narrow.
Roads are represented by connections where connections[i] = [ai, bi] represents a road from city ai to city bi.
This year, there will be a big event in the capital (city 0), and many people want to travel to this city.
Your task consists of reorienting some roads such that each city can visit the city 0. Return the minimum number of edges changed.
It’s guaranteed that each city can reach city 0 after reorder.
Solution:
题目给定一张由 n 个点（使用 0 到 n−1 编号），n−1 条边构成的有向图，如果忽略边的方向，就变成了一棵树。我们需要改变某些边的方向使得每个点都可以访问到 0 号点。
如果忽略边的方向，将每条有向边以及其反向边加入到图中，那么从任意一点出发都能到达 0 号点。路径上可能会经过反向边，我们需要变更与之对应的原边的方向。需要变更的次数即为答案。
以每个点为起点进行搜索的代价会很大，因此我们考虑从 0 出发去遍历其他点（可以使用深度优先搜索或者广度优先搜索，本题解使用深度优先搜索），原来我们需要统计反向边的数量，现在需要统计原方向边的数量。
具体而言，我们使用 1 标记原方向的边，使用 0 标记反向边。然后从 0 号点开始遍历，访问到某个新的点时，所经过的边被 1 标记，就令答案加 1。最终统计得到的答案就是我们需要变更方向的最小路线数。
理解:将图形拆解为
1 - 2
/
0 - 3 - 4
对于0来说,实际上计算的是0-1-2和0-3-4的cost之和
class Solution {
public int minReorder(int n, int[][] connections) {
List<int[]>[] e = new List[n];
for (int i = 0; i < n; i++) {
e[i] = new ArrayList<int[]>();
}
for (int[] edge : connections) {
e[edge[0]].add(new int[]{edge[1], 1});
e[edge[1]].add(new int[]{edge[0], 0});
}
int[] res = new int[] {0};
dfs(0, -1, e, res);
return res[0];
}
public void dfs(int x, int parent, List<int[]>[] e, int[] res) {
for (int[] edge : e[x]) {
if (edge[0] == parent) {
continue;
}
res[0]+= edge[1];
dfs(edge[0], x, e, res);
}
}
}
PB 399. Evaluate Division
You are given an array of variable pairs equations and an array of real numbers values, where equations[i] = [Ai, Bi] and values[i] represent the equation Ai / Bi = values[i]. Each Ai or Bi is a string that represents a single variable.
You are also given some queries, where queries[j] = [Cj, Dj] represents the jth query where you must find the answer for Cj / Dj = ?.
Return the answers to all queries. If a single answer cannot be determined, return -1.0.
Note: The input is always valid. You may assume that evaluating the queries will not result in division by zero and that there is no contradiction.
Note: The variables that do not occur in the list of equations are undefined, so the answer cannot be determined for them.
Input: equations = [[“a”,”b”],[“b”,”c”]], values = [2.0,3.0], queries = [[“a”,”c”],[“b”,”a”],[“a”,”e”],[“a”,”a”],[“x”,”x”]] Output: [6.00000,0.50000,-1.00000,1.00000,-1.00000]
class Node {
String value;
Map<String, Double> edges;
Node(String value) {
this.value = value;
this.edges = new HashMap<>();
}
}
class Solution {
public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
Map<String, Node> nodeMap = new HashMap<>();
for (int i = 0; i < equations.size(); i++) {
List<String> equation = euqations[i];
Node first = nodeMap.computeIfAbsent(equation.get(0), new Node(equation.get(0)));
Node sec = nodeMap.computeIfAbsent(equation.get(1), new Node(equation.get(1)));
if (!first.edges.containsKey(sec.value)) {
first.edges.put(sec.value, values[i]);
}
if (!sec.edges.containsKey(first.value)) {
sec.edges.put(first.value, 1 / values[i]);
}
}
double[] res = new double[queries.size()];
for (int i = 0; i < queries.size(); i++) {
Set<String> visit = new HashSet<>();
res[i] = dfs(nodeMap, queries.get(i)[0], queries.get(i)[1], visit);
}
return res;
}
public double dfs(Map<String, Node> nodeMap, String cur, String destination, Set<String> visit) {
if (cur == destination) {
return 1;
}
Node cur = nodeMap.get(cur);
visit.add(cur.value);
for (Map.Entry<String, Double> edge : cur.edges.entrySet()) {
if (!visit.contains(edge.getKey())) {
double res = edge.getValue() * dfs(nodeMap, edge.getKey(), destination, visit);
if (res > 0) return res;
}
}
return -1;
}
}
class Solution {
public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
Map<String, Map<String, Double>> graph = new HashMap<>();
// Step 1: Build the graph
for (int i = 0; i < equations.size(); i++) {
String numerator = equations.get(i).get(0);
String denominator = equations.get(i).get(1);
double value = values[i];
graph.computeIfAbsent(numerator, k -> new HashMap<>()).put(denominator, value);
graph.computeIfAbsent(denominator, k -> new HashMap<>()).put(numerator, 1.0 / value);
}
double[] result = new double[queries.size()];
// Step 2: Process each query
for (int i = 0; i < queries.size(); i++) {
String numerator = queries.get(i).get(0);
String denominator = queries.get(i).get(1);
if (!graph.containsKey(numerator) || !graph.containsKey(denominator)) {
result[i] = -1.0;
} else {
Set<String> visited = new HashSet<>();
result[i] = dfs(graph, numerator, denominator, 1.0, visited);
}
}
return result;
}
private static double dfs(Map<String, Map<String, Double>> graph, String current, String target, double product, Set<String> visited) {
if (current.equals(target)) {
return product;
}
visited.add(current);
Map<String, Double> neighbors = graph.get(current);
for (String neighbor : neighbors.keySet()) {
if (!visited.contains(neighbor)) {
double result = dfs(graph, neighbor, target, product * neighbors.get(neighbor), visited);
if (result != -1.0) {
return result;
}
}
}
return -1.0;
}
}
PB 1926. Nearest Exit from Entrance in Maze
You are given an m x n matrix maze (0-indexed) with empty cells (represented as ‘.’) and walls (represented as ‘+’). You are also given the entrance of the maze, where entrance = [entrancerow, entrancecol] denotes the row and column of the cell you are initially standing at.
In one step, you can move one cell up, down, left, or right. You cannot step into a cell with a wall, and you cannot step outside the maze. Your goal is to find the nearest exit from the entrance. An exit is defined as an empty cell that is at the border of the maze. The entrance does not count as an exit.
Return the number of steps in the shortest path from the entrance to the nearest exit, or -1 if no such path exists.
Input: maze = [[”+”,”+”,”.”,”+”],[”.”,”.”,”.”,”+”],[”+”,”+”,”+”,”.”]], entrance = [1,2] Output: 1
class Solution {
public int nearestExit(char[][] maze, int[] entrance) {
int[] xDirect = new int[] {0, 0, 1, -1};
int[] yDirect = new int[] {1, -1, 0, 0};
Deque<int[]> queue = new ArrayDeque<>();
queue.offerLast(entrance);
maze[entrance[0]][entrance[1]] = '+';
int step = 0;
while(!queue.isEmpty()) {
int size = queue.size();
while(!queue.isEmpty() && size-- > 0) {
int[] cur = queue.pollFirst();
for (int i = 0; i < 4; i++) {
int x = cur[0] + xDirect[i];
int y = cur[1] + yDirect[i];
if (x >= 0 && x < maze.length && y >=0 && y < maze[0].length && maze[x][y] == '.') {
if (x == 0 || x == maze.length - 1 || y ==0 || y == maze[0].length - 1) {
return step + 1;
}
queue.offerLast(new int[] {x, y});
maze[x][y] = '+';
}
}
}
step++;
}
return -1;
}
}