This is the LeetCode List for LeetCode CN
一开始想刷Grind-75找不到题直接跳转的页面，想着一边刷一边整理出来！
题库来自GRIND-75 点击题目即可跳转到LeetCode CN页面！
点击序号可以看到我的Java题解！如有问题欢迎提出！
#Grind-75题目整理 附JAVA代码+注释
class Solution {
// 定义一个方法，接受一个整数数组和一个目标值，返回两个加起来等于目标值的数的索引
public int[] twoSum(int[] nums, int target) {
// 创建一个哈希表来存储数组中每个元素及其索引
HashMap<Integer,Integer> map= new HashMap<>();
// 遍历数组中的每个元素
for(int i = 0;i<nums.length;i++){
// 如果当前元素与哈希表中已有的某个元素的和等于目标值
if(map.containsKey(target-nums[i])){
// 返回当前元素的索引和那个已有元素的索引
return new int[]{i,map.get(target-nums[i])};
}
// 如果不满足上述条件，则将当前元素及其索引添加到哈希表中
map.put(nums[i],i);
}
// 如果遍历完数组后没有找到满足条件的元素对，则返回一个空数组
return new int[0];
}
}时间复杂度：O(n)
空间复杂度：O(n)
class Solution {
// 定义一个方法，接受一个字符串作为参数，返回一个布尔值表示括号是否有效
public boolean isValid(String s) {
// 使用双端队列来存储期望匹配的右括号
Deque<Character> dq = new LinkedList<>();
// 遍历字符串中的每个字符
for(int i = 0;i<s.length();i++){
// 获取当前字符
char c = s.charAt(i);
// 如果是左括号'('，则将对应的右括号')'加入队列
if(c == '('){
dq.offerLast(')');
// 如果是左括号'{'，则将对应的右括号'}'加入队列
}else if(c == '{'){
dq.offerLast('}');
// 如果是左括号'['，则将对应的右括号']'加入队列
}else if(c == '['){
dq.offerLast(']');
}else{
// 如果不是左括号，检查队列是否为空或当前字符是否不等于队列中的最后一个字符
// 如果是，则说明括号无法匹配，返回false
if(dq.isEmpty()||dq.pollLast()!=c){
return false;
}
}
}
// 遍历完成后，检查队列是否为空，为空则说明所有括号都正确匹配，返回true
return dq.isEmpty();
}
}时间复杂度：O(n)
空间复杂度：O(n)
class Solution {
// 定义一个方法，接受两个已排序的链表作为参数，返回一个合并后的已排序链表
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
// 创建一个哑节点（dummy node）和一个当前节点指针，均指向哑节点
ListNode dummy = new ListNode(0), cur = dummy;
// 当两个链表都非空时循环
while(list1 !=null && list2 !=null){
// 如果list1的当前节点的值小于或等于list2的当前节点的值
if(list1.val<=list2.val){
// 将cur的下一个节点指向list1的当前节点
cur.next = list1;
// 移动list1的指针到下一个节点
list1 = list1.next;
}else{
// 否则，将cur的下一个节点指向list2的当前节点
cur.next = list2;
// 移动list2的指针到下一个节点
list2 = list2.next;
}
// 移动cur到它的下一个节点
cur = cur.next;
}
// 循环结束后，如果list1或list2中有一个还有剩余节点，直接连接到cur的下一个节点
cur.next = list1==null?list2:list1;
// 返回合并后链表的头节点，即哑节点的下一个节点
return dummy.next;
}
}时间复杂度：O(n+m)
空间复杂度：O(1)
class Solution {
// 定义一个方法，接受一个整数数组prices作为参数，返回可以获得的最大利润
public int maxProfit(int[] prices) {
// 初始化利润为0
int profit = 0;
// 初始化最低价格为整数的最大值
int lowest = Integer.MAX_VALUE;
// 遍历价格数组
for(int i = 0;i<prices.length;i++){
// 如果当前价格小于已记录的最低价格，则更新最低价格
if(prices[i]<lowest)lowest = prices[i];
// 计算当前价格与最低价格之间的差值作为当前可能的利润
int sum = prices[i]-lowest;
// 如果当前可能的利润大于已记录的最大利润，则更新最大利润
if(profit<sum)profit = sum;
}
// 返回记录的最大利润
return profit;
}
}时间复杂度：O(n)
空间复杂度：O(1)
class Solution {
// 定义一个方法，接受一个字符串作为参数，返回一个布尔值表示该字符串是否为回文串
public boolean isPalindrome(String s) {
// 使用正则表达式去除所有非字母数字字符，然后转换为小写
s = s.replaceAll("[^a-zA-Z0-9]","").toLowerCase();
// 初始化左指针为0
int left = 0;
// 初始化右指针为字符串长度减1
int right = s.length()-1;
// 当左指针不大于右指针时，执行循环
while(left<=right){
// 比较左右指针对应的字符，如果不相等，返回false
if(s.charAt(left)!=s.charAt(right))return false;
// 左指针右移
left++;
// 右指针左移
right--;
}
// 如果所有对应位置的字符都相等，说明是回文串，返回true
return true;
}
}时间复杂度：O(n)
空间复杂度：O(n)
class Solution {
// 定义一个方法，接受一棵二叉树的根节点作为参数，返回翻转后的二叉树的根节点
public TreeNode invertTree(TreeNode root) {
// 如果根节点为空，则直接返回null
if(root == null){
return root;
}
// 递归翻转左子树，结果存储在left中
TreeNode left = invertTree(root.left);
// 递归翻转右子树，结果存储在right中
TreeNode right = invertTree(root.right);
// 将翻转后的左子树赋值给根节点的右子节点
root.left = right;
// 将翻转后的右子树赋值给根节点的左子节点
root.right = left;
// 返回翻转后的根节点
return root;
}
}时间复杂度：o(n)
空间复杂度：0{h} h为树高度
class Solution {
// 定义一个方法，接受两个字符串s和t作为参数，返回一个布尔值表示这两个字符串是否为字谜
public boolean isAnagram(String s, String t) {
// 使用HashMap来存储字符串s中每个字符及其出现的次数
HashMap<Character,Integer> map = new HashMap<>();
// 遍历字符串s
for(int i = 0;i<s.length();i++){
char c = s.charAt(i);
// 如果map中不包含当前字符，则将其加入map，并设置计数为1
if(!map.containsKey(c)){
map.put(c,1);
}else {
// 如果map中包含当前字符，则将其计数加1
map.put(c,map.get(c)+1);
}
}
// 遍历字符串t
for(int i = 0;i<t.length();i++){
char c = t.charAt(i);
// 如果map中不包含当前字符，说明t中有s中没有的字符，返回false
if(!map.containsKey(c)){
return false;
}
// 如果当前字符计数为1，则从map中移除该字符
if(map.get(c)-1 == 0){
map.remove(c);
}else{
// 否则，将该字符的计数减1
map.put(c,map.get(c)-1);
}
}
// 如果map为空，说明s和t完全匹配，返回true；否则返回false
return map.isEmpty();
}
}时间复杂度：O(m+n)
空间复杂度：O(m)
class Solution {
// 定义一个方法，接受一个有序整数数组nums和一个目标值target作为参数，返回目标值在数组中的索引
public int search(int[] nums, int target) {
// 初始化左指针为0
int left = 0;
// 初始化右指针为数组长度
int right = nums.length;
// 当左指针小于右指针时，执行循环
while(left<right){
// 计算中间位置的索引
int middle = (left+right)/2;
// 如果中间位置的值小于目标值，则将左指针移动到中间位置的右侧
if(nums[middle]<target)left = middle+1;
// 如果中间位置的值大于目标值，则将右指针移动到中间位置
else if(nums[middle]>target)right = middle;
// 如果中间位置的值等于目标值，则返回中间位置的索引
else return middle;
}
// 如果循环结束还没有找到目标值，则返回-1
return -1;
}
}时间复杂度：O(logn)
空间复杂度：o(1)
class Solution {
// 主函数，接受一个二维数组表示的图像、起始像素的行列坐标以及新的颜色值
public int[][] floodFill(int[][] image, int sr, int sc, int color) {
// 获取起始像素的颜色
int x = image[sr][sc];
// 调用辅助函数进行填充
fillHelper(image, sr, sc, color, x);
// 返回填充后的图像
return image;
}
// 辅助递归函数，用于填充颜色
private void fillHelper(int[][] image, int row, int col, int color,int target){
// 检查当前位置是否超出图像边界、颜色是否与目标颜色不同、或者已经是新颜色
if(row<0 || row>=image.length || col<0 || col>=image[0].length || image[row][col]!=target || image[row][col]==color) return;
// 如果当前像素颜色与目标颜色相同，更新为新颜色
if(image[row][col] == target) image[row][col] = color;
// 对当前像素的四个方向分别递归调用填充函数
fillHelper(image, row+1, col, color, target);
fillHelper(image, row-1, col, color, target);
fillHelper(image, row, col+1, color, target);
fillHelper(image, row, col-1, color, target);
}
}时间复杂度：O(n)
空间复杂度：O(n)
class Solution {
// 定义一个方法，接受一棵二叉搜索树的根节点以及两个节点作为参数，返回这两个节点的最低公共祖先
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
// 如果根节点的值介于p和q的值之间（包含等于的情况），则根节点就是最低公共祖先
if(root.val <= p.val && root.val >= q.val || root.val <= q.val && root.val >= p.val){
return root;
}
// 如果根节点的值大于p和q的值，说明最低公共祖先在左子树中
if(root.val > p.val && root.val > q.val){
return lowestCommonAncestor(root.left, p, q);
}else{
// 否则，最低公共祖先在右子树中
return lowestCommonAncestor(root.right, p, q);
}
}
}时间复杂度：O(h)
空间复杂度：O(h)
class Solution {
// 主函数，接受树的根节点root，返回一个布尔值表示树是否为平衡二叉树
public boolean isBalanced(TreeNode root) {
// 如果根节点为空，则认为是平衡的
if(root == null) return true;
// 使用深度优先搜索算法计算左子树的高度
int left = dfs(root.left);
// 使用深度优先搜索算法计算右子树的高度
int right = dfs(root.right);
// 检查当前节点的左右子树的高度差是否不超过1，并递归地对左右子树进行同样的检查
return Math.abs(left - right) <= 1 && isBalanced(root.left) && isBalanced(root.right);
}
// 辅助函数dfs，用于计算树的高度
private int dfs(TreeNode root){
// 如果节点为空，返回高度0
if(root == null) {
return 0;
}
// 计算当前节点的左右子树的高度的最大值，然后加1（加上当前节点的高度）
return Math.max(dfs(root.left), dfs(root.right)) + 1;
}
}时间复杂度：O(NlogN)
空间复杂度：O(N)
public class Solution {
// 主函数，接受链表头节点head，返回一个布尔值表示链表是否有环
public boolean hasCycle(ListNode head) {
// 如果头节点为空，或者头节点的下一个节点为空，则链表没有环
if(head == null || head.next == null) return false;
// 初始化慢指针为头节点，快指针为头节点的下一个节点
ListNode temp1 = head, temp2 = head.next;
// 当慢指针和快指针不相遇时，进行循环
while(temp1 != temp2){
// 如果快指针到达链表末尾（null）或快指针的下一个节点为null，则链表没有环
if(temp2 == null || temp2.next == null) return false;
// 慢指针前进一步
temp1 = temp1.next;
// 快指针前进两步
temp2 = temp2.next.next;
}
// 如果慢指针和快指针相遇，说明链表有环
return true;
}
}时间复杂度：O(n)
空间复杂度：O(1)
class MyQueue {
// 使用两个栈temp1和temp2来实现队列
Stack<Integer> temp1;
Stack<Integer> temp2;
// 构造函数初始化两个栈
public MyQueue() {
temp1 = new Stack<>();
temp2 = new Stack<>();
}
// 入队操作
public void push(int x) {
// 将temp2中所有元素弹出并压入temp1，保持新元素在temp2底部
while(!temp2.isEmpty()){
temp1.push(temp2.pop());
}
// 将新元素压入temp2
temp2.push(x);
}
// 出队操作，返回并移除队首元素
public int pop() {
// 将temp1中所有元素弹出并压入temp2，使temp2顶部的元素为队首元素
while(!temp1.isEmpty()){
temp2.push(temp1.pop());
}
// 弹出并返回temp2顶部元素，即队首元素
return temp2.pop();
}
// 获取队首元素，不移除
public int peek() {
// 与pop操作相同，但不移除temp2顶部元素
while(!temp1.isEmpty()){
temp2.push(temp1.pop());
}
// 返回temp2顶部元素，即队首元素
return temp2.peek();
}
// 判断队列是否为空
public boolean empty() {
// 如果temp1和temp2都为空，则队列为空
return temp1.isEmpty() && temp2.isEmpty();
}
}时间复杂度：O(n)
空间复杂度：O(n)
public class Solution extends VersionControl {
// 定义方法firstBadVersion，接受一个整数n，表示版本数量，返回第一个错误版本的编号
public int firstBadVersion(int n) {
// 初始化左边界为1（版本编号从1开始）
int left = 1;
// 初始化右边界为n
int right = n;
// 当左边界小于右边界时，执行循环
while(left<right){
// 使用无符号右移操作符来防止整数溢出，计算中间位置
int middle = (left+right)>>>1;
// 如果中间版本是错误版本，则将右边界移动到中间位置
if(isBadVersion(middle))right = middle;
else left = middle + 1; // 否则，将左边界移动到中间位置的右侧
}
// 当左边界等于右边界时，找到了第一个错误版本，返回左边界（或右边界）
return left;
}
}时间复杂度：O(logn)
空间复杂度：o(1)
class Solution {
// 定义方法canConstruct，接受两个字符串ransomNote和magazine，返回一个布尔值表示是否可以从magazine构造出ransomNote
public boolean canConstruct(String ransomNote, String magazine) {
// 创建一个长度为26的数组，用于记录每个字母的出现次数
int[] c = new int[26];
// 遍历magazine字符串，统计每个字母的出现次数
for(int i = 0; i < magazine.length(); i++){
c[magazine.charAt(i) - 'a']++;
}
// 遍历ransomNote字符串，对应字母的出现次数减1
for(int i = 0; i < ransomNote.length(); i++){
c[ransomNote.charAt(i) - 'a']--;
// 如果某个字母的出现次数小于0，说明无法用magazine构造出ransomNote，返回false
if(c[ransomNote.charAt(i) - 'a'] < 0) return false;
}
// 如果ransomNote中的每个字母都能在magazine中找到足够的数量，返回true
return true;
}
}时间复杂度：O(m+n)
空间复杂度：O(1)
class Solution {
// 定义方法climbStairs，接受一个整数n表示台阶总数，返回爬到楼顶的方法总数
public int climbStairs(int n) {
// 创建一个数组dp，长度为n+1，用于存储到达每一级台阶的方法数
int[] dp = new int[n+1];
// 初始化：到达第0级台阶有1种方法，到达第1级台阶也有1种方法
dp[0] = 1;
dp[1] = 1;
// 从第2级台阶开始计算到达每一级台阶的方法数
for(int i = 2; i < dp.length; i++){
// 到达第i级台阶的方法数等于到达第i-1级台阶的方法数加上到达第i-2级台阶的方法数
dp[i] = dp[i-1] + dp[i-2];
}
// 返回到达第n级台阶的方法数
return dp[n];
}
}时间复杂度：O(n)
空间复杂度：O(n)
class Solution {
// 定义方法longestPalindrome，接受一个字符串s，返回可以构成的最长回文的长度
public int longestPalindrome(String s) {
// 创建一个HashMap来统计每个字符出现的次数
HashMap<Character,Integer> map = new HashMap<>();
// 遍历字符串s，统计每个字符的出现次数
for(int i = 0; i < s.length(); i++){
char c = s.charAt(i);
if(map.containsKey(c)){
// 如果字符已经出现过，次数加1
int temp = map.get(c) + 1;
map.put(c, temp);
}else{
// 如果是首次出现，计数为1
map.put(c, 1);
}
}
// 初始化最长回文长度为0
int ans = 0;
// 创建一个标志位，记录是否有奇数次出现的字符
boolean even = false;
// 遍历map中所有的值（即字符的出现次数）
for(int temp : map.values()){
if(temp % 2 == 0){
// 如果字符出现偶数次，全部计入回文长度
ans += temp;
}else{
// 如果字符出现奇数次，减一后的偶数部分计入回文长度
ans += temp - 1;
even = true;
}
}
// 如果有奇数次出现的字符，最长回文长度可以额外加一
return even == true ? ans + 1 : ans;
}
}时间复杂度：O(n)
空间复杂度：O(n)
class Solution {
// 定义方法reverseList，接受链表的头节点head，返回反转后的链表的头节点
public ListNode reverseList(ListNode head) {
// 初始化当前节点为头节点，前一个节点为null
ListNode cur = head, prev = null;
// 遍历链表直到当前节点为null
while(cur != null){
// 临时存储当前节点的下一个节点
ListNode temp = cur.next;
// 将当前节点的next指向前一个节点，实现反转
cur.next = prev;
// 前一个节点移动到当前节点
prev = cur;
// 当前节点移动到下一个节点
cur = temp;
}
// 当遍历完成时，prev指向原链表的最后一个节点，即反转后链表的头节点
return prev;
}
}时间复杂度：O(n)
空间复杂度：O(1)
class Solution {
public int majorityElement(int[] nums) {
// 初始化num为数组的第一个元素，index为1，表示当前数字的出现次数
int num = nums[0], index = 1;
// 遍历数组中的每个元素
for(int i = 1; i < nums.length; i++){
// 如果当前元素等于num，index加一
if(nums[i] == num) index++;
else index--; // 如果不等，index减一
// 如果index为-1，说明当前num不可能是多数元素，更换num为当前元素，并重置index为1
if(index == -1){
num = nums[i];
index = 1;
}
}
// 返回最后确定的num，即多数元素
return num;
}
}时间复杂度：O(n)
空间复杂度：O(1)
class Solution {
// 定义方法addBinary，接受两个二进制字符串a和b，返回它们的和
public String addBinary(String a, String b) {
// 使用StringBuilder构建最终的二进制和字符串
StringBuilder sb = new StringBuilder();
// 获取a和b的长度
int alen = a.length(), blen = b.length(), diff = Math.abs(alen - blen);
// 如果a比b长，给b前面填充0；如果b比a长，给a前面填充0
if(alen > blen) b = fill(b, diff);
else if(blen > alen) a = fill(a, diff);
// 初始化进位为0
int inc = 0;
// 从后向前遍历a和b，进行逐位相加
for(int i = a.length() - 1; i >= 0; i--){
if((a.charAt(i) - '0') + (b.charAt(i) - '0') + inc > 2){
sb.append('1');
inc = 1;
}else if((a.charAt(i) - '0') + (b.charAt(i) - '0') + inc == 2){
sb.append(0);
inc = 1;
}else{
int temp = (a.charAt(i) - '0') + (b.charAt(i) - '0') + inc;
sb.append(temp);
inc = 0;
}
}
// 如果最后还有进位，再加一个1
if(inc == 1){
sb.append('1');
}
// 反转StringBuilder得到最终结果，并转换为字符串返回
return sb.reverse().toString();
}
// 定义方法fill，用于给字符串x前面填充num个0
private String fill(String x, int num){
while(num > 0){
x = '0' + x;
num--;
}
return x;
}
}时间复杂度：O(n)
空间复杂度：O(n)
class Solution {
// 定义全局变量ans来记录二叉树的直径
int ans = 0;
// 主函数，接受一棵二叉树的根节点，返回这棵树的直径
public int diameterOfBinaryTree(TreeNode root) {
// 调用深度优先搜索函数dfs，从根节点开始遍历
dfs(root);
// 返回遍历过程中计算得到的最大直径
return ans;
}
// 深度优先搜索函数，用于计算树中每个节点为根的子树的最大深度，并更新全局变量ans
private int dfs(TreeNode root){
// 如果节点为空，则返回0
if(root == null){
return 0;
}
// 递归计算左子树的最大深度
int left = dfs(root.left);
// 递归计算右子树的最大深度
int right = dfs(root.right);
// 更新全局变量ans为当前最大值和通过当前节点的路径长度的最大值
ans = Math.max(ans, left + right);
// 返回当前节点的最大深度
return Math.max(left, right) + 1;
}
}时间复杂度：O(n)
空间复杂度：O(n)
class Solution {
// 定义方法middleNode，接受链表的头节点head，返回链表的中间节点
public ListNode middleNode(ListNode head) {
// 初始化两个指针，都指向头节点
ListNode slow = head, fast = head;
// 当快指针没有到达链表末尾时，循环继续
while(fast != null && fast.next != null){
// 慢指针每次移动一个节点
slow = slow.next;
// 快指针每次移动两个节点
fast = fast.next.next;
}
// 当快指针到达链表末尾时，慢指针所在的节点就是链表的中间节点
return slow;
}
}时间复杂度：O(n)
空间复杂度：O(1)
class Solution {
// 定义方法maxDepth，接受一棵二叉树的根节点，返回这棵树的最大深度
public int maxDepth(TreeNode root) {
// 如果节点为空，则该树的深度为0
if(root == null) return 0;
// 递归地计算左子树和右子树的最大深度，取较大值，然后加上当前节点自身的深度1
return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}
}时间复杂度：O(n)
空间复杂度：O(n)
class Solution {
// 定义方法containsDuplicate，接受一个整数数组nums，返回一个布尔值表示数组中是否包含重复元素
public boolean containsDuplicate(int[] nums) {
// 创建一个HashSet用于存储遍历过程中的元素
HashSet<Integer> set = new HashSet<>();
// 遍历数组中的每个元素
for(int i = 0; i < nums.length; i++){
// 尝试将元素添加到HashSet中，如果添加失败（即已存在该元素），则返回true
if(!set.add(nums[i])) return true;
}
// 如果遍历完成后没有发现重复元素，则返回false
return false;
}
}时间复杂度：O(n)
空间复杂度：O(n)
class Solution {
// 定义方法maxSubArray，接受一个整数数组nums，返回该数组的最大子数组和
public int maxSubArray(int[] nums) {
// 初始化ans为数组的第一个元素，sum也为第一个元素。ans记录最大子数组和，sum记录以当前元素为结束点的最大子数组和
int ans = nums[0], sum = nums[0];
// 从数组的第二个元素开始遍历
for(int i = 1; i < nums.length; i++){
// 更新sum为当前元素与sum加上当前元素的较大值，即决定是否将当前元素加入前一个子数组中
sum = Math.max(nums[i], sum + nums[i]);
// 使用sum更新ans，确保ans始终是找到的最大子数组和
ans = Math.max(sum, ans);
}
// 返回最大子数组和
return ans;
}
}时间复杂度：
空间复杂度：
class Solution {
public int[][] insert(int[][] intervals, int[] newInterval) {
// 创建一个结果列表，用于存储最终的区间列表
List<int[]> result = new ArrayList<>();
for (int[] interval : intervals) {
// 如果新区间在当前区间之前结束，将新区间添加到结果列表，并更新新区间为当前区间
if (newInterval[1] < interval[0]) {
result.add(newInterval);
newInterval = interval;
// 如果新区间与当前区间重叠，合并这两个区间
} else if (newInterval[0] <= interval[1]) {
newInterval = new int[]{Math.min(newInterval[0], interval[0]), Math.max(newInterval[1], interval[1])};
} else {
// 如果新区间在当前区间之后开始，将当前区间添加到结果列表
result.add(interval);
}
}
// 将最后处理的新区间（可能已合并了多个区间）添加到结果列表
result.add(newInterval);
// 将结果列表转换为数组并返回
return result.toArray(new int[result.size()][]);
}
}时间复杂度：O(n)
空间复杂度：O(n)
class Solution {
public int[][] updateMatrix(int[][] mat) {
int m = mat.length, n = mat[0].length; // 矩阵的行数和列数
int[][] ans = new int[m][n]; // 存储答案的矩阵
boolean[][] visited = new boolean[m][n]; // 记录位置是否已访问
Queue<int[]> que = new LinkedList<>(); // BFS的队列
// 初始化：将所有0的位置加入队列并标记为已访问
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
if(mat[i][j] == 0){
que.add(new int[]{i, j});
visited[i][j] = true;
}
}
}
// 四个可能的移动方向
int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
// 广度优先搜索
while(!que.isEmpty()){
int[] temp = que.poll();
int row = temp[0], col = temp[1];
for(int[] dir : dirs){
int rowN = row + dir[0], colN = col + dir[1];
// 检查邻居是否在矩阵范围内且未被访问
if(rowN < 0 || rowN >= m || colN < 0 || colN >= n || visited[rowN][colN]) continue;
que.add(new int[]{rowN, colN});
ans[rowN][colN] = ans[row][col] + 1; // 更新邻居的距离
visited[rowN][colN] = true; // 标记邻居为已访问
}
}
return ans; // 返回答案矩阵
}
}时间复杂度：
空间复杂度：
class Solution {
public int[][] kClosest(int[][] points, int k) {
// 创建一个优先队列，按照点到原点距离的平方进行排序
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> (a[0]*a[0] + a[1]*a[1]) - (b[0]*b[0] + b[1]*b[1]));
// 将所有点加入到优先队列中
for(int[] point : points) pq.add(point);
// 创建一个结果数组，用于存放距离原点最近的k个点
int[][] ans = new int[k][2];
// 从优先队列中取出k个距离最近的点
for(int i = 0; i < k; i++) ans[i] = pq.poll();
return ans; // 返回结果数组
}
}时间复杂度：O(n log n)
空间复杂度：O(n)
class Solution {
public int lengthOfLongestSubstring(String s) {
// 创建一个HashSet用于存储当前窗口中的字符
HashSet<Character> set = new HashSet<>();
// 初始化左边界
int left = 0;
// 初始化答案，即最长无重复字符子串的长度
int ans = 0;
// 右边界从0开始，遍历字符串
for(int right = 0; right < s.length(); right++){
// 如果当前字符已经在HashSet中，说明遇到了重复字符
// 需要将左边界右移，同时从HashSet中移除左边界指向的字符，直到窗口中没有重复字符
while(set.contains(s.charAt(right))){
set.remove(s.charAt(left));
left++;
}
// 将当前字符添加到HashSet中
set.add(s.charAt(right));
// 更新答案，即当前窗口的长度（right - left + 1）与之前记录的最长长度中的较大值
ans = Math.max(ans, right - left + 1);
}
// 返回最长无重复字符子串的长度
return ans;
}
}时间复杂度：O(n)
空间复杂度：O(min(m,n))
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums); // 对数组进行排序
List<List<Integer>> ans = new ArrayList<>(); // 创建结果列表
// 遍历数组，但最后两个元素可以不考虑，因为我们会用j和k指针来检查剩下的元素
for(int i = 0; i < nums.length - 2; i++){
// 如果当前数字大于0，则之后的三数之和一定大于0，因为数组已经排序
if(nums[i] > 0) break;
// 跳过重复元素
if(i > 0 && nums[i] == nums[i - 1]) continue;
int j = i + 1, k = nums.length - 1; // 设置双指针
while(j < k){
int sum = nums[i] + nums[j] + nums[k]; // 计算三数之和
if(sum < 0){
// 和小于0，增加j
while(j < k && nums[j] == nums[++j]);
}else if(sum > 0){
// 和大于0，减少k
while(j < k && nums[k] == nums[--k]);
}else{
// 和为0，添加到结果列表
ans.add(new ArrayList<Integer>(Arrays.asList(nums[i], nums[j], nums[k])));
// 跳过重复元素
while(j < k && nums[j] == nums[++j]);
while(j < k && nums[k] == nums[--k]);
}
}
}
return ans; // 返回结果
}
}时间复杂度：O(n^2)
空间复杂度：O(n)
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
// 使用一个双端队列来存储每一层的节点
Deque<TreeNode> dq = new LinkedList<>();
// 首先将根节点加入队列
dq.offerLast(root);
// 创建一个列表来存储最终的遍历结果
List<List<Integer>> ans = new LinkedList<>();
// 如果根节点为空，则直接返回空的结果列表
if(root == null) return ans;
// 当队列不为空时，继续遍历
while(!dq.isEmpty()){
// 获取当前层的节点数量
int size = dq.size();
// 创建一个列表来存储当前层的所有节点值
List<Integer> path = new LinkedList<>();
// 遍历当前层的每个节点
while(size > 0){
// 从队列中取出一个节点
TreeNode temp = dq.pollFirst();
// 将该节点的值添加到当前层的列表中
path.add(temp.val);
// 如果该节点有左子节点，将左子节点加入队列
if(temp.left != null) dq.offerLast(temp.left);
// 如果该节点有右子节点，将右子节点加入队列
if(temp.right != null) dq.offerLast(temp.right);
// 处理完一个节点，当前层剩余节点数减1
size--;
}
// 将当前层的节点值列表添加到结果列表中
ans.add(path);
}
// 返回遍历结果
return ans;
}
}时间复杂度：O(n)
空间复杂度：O(n)
class Solution {
// 定义一个解决方案类
public Node cloneGraph(Node node) {
// 定义一个公共方法来克隆给定的图
HashMap<Node,Node> map = new HashMap<>();
// 创建一个哈希图用于存储原节点和克隆节点的映射
return dfs(node,map);
// 使用深度优先搜索克隆图，并返回克隆的根节点
}
private Node dfs(Node node,HashMap<Node,Node> map){
// 定义一个私有方法进行深度优先搜索
if(node==null)return null;
// 如果节点为空，则返回null
if(map.containsKey(node)) return map.get(node);
// 如果节点已经被访问过，返回其克隆节点
Node clone = new Node(node.val,new ArrayList<>());
// 创建一个新的克隆节点，包含节点值但不包含邻居
map.put(node,clone);
// 在哈希图中记录原节点和克隆节点的映射
for(Node neighbor:node.neighbors) clone.neighbors.add(dfs(neighbor,map));
// 遍历每个邻居节点，递归克隆，并添加到克隆节点的邻居列表中
return clone;
// 返回克隆节点
}
}时间复杂度：O(n+m)
空间复杂度：O(n)
class Solution {
// 定义解决方案类
public int evalRPN(String[] tokens) {
// 评估逆波兰表示式的函数
Deque<String> dq = new LinkedList<>();
// 使用双端队列作为栈
for(String token:tokens){
// 遍历每个令牌
if(token.equals("+")||token.equals("-")||token.equals("*")||token.equals("/")){
// 如果令牌是操作符
String second = dq.pollLast();
// 弹出栈顶元素作为第二个操作数
String first = dq.pollLast();
// 弹出栈顶元素作为第一个操作数
int lst = Integer.parseInt(first);
// 将第一个操作数转换为整数
int snd = Integer.parseInt(second);
// 将第二个操作数转换为整数
int cal = 0;
// 初始化结果变量
switch(token){
// 根据操作符进行计算
case "+":
cal = lst+snd;
// 执行加法
break;
case "-":
cal = lst-snd;
// 执行减法
break;
case "*":
cal = lst*snd;
// 执行乘法
break;
case "/":
cal = lst/snd;
// 执行除法
break;
}
dq.offerLast(String.valueOf(cal));
// 将计算结果转换为字符串并压回栈中
}else{
dq.offerLast(token);
// 如果令牌是数字，则直接压入栈中
}
}
return Integer.parseInt(dq.peek());
// 返回栈顶元素（最终结果）并将其转换为整数
}
}时间复杂度：O(n)
空间复杂度：O(n)
class Solution {
// 定义解决方案类
public boolean canFinish(int numCourses, int[][] prerequisites) {
// 检查是否可以完成所有课程的函数
List<List<Integer>> map = new ArrayList<>();
// 创建邻接列表表示课程图
for(int i = 0;i<numCourses;i++){
map.add(new ArrayList<>());
// 初始化邻接列表
}
int[] visited = new int[numCourses];
// 创建访问数组，跟踪课程是否被访问过
for(int i = 0;i<prerequisites.length;i++){
map.get(prerequisites[i][1]).add(prerequisites[i][0]);
// 填充邻接列表，表明课程间的依赖关系
}
for(int i = 0;i<numCourses;i++){
if(!dfs(map,visited,i))return false;
// 如果存在不能完成的课程，则返回false
}
return true;
// 所有课程都可以完成，返回true
}
private boolean dfs(List<List<Integer>> map, int[] visited, int i){
// 深度优先搜索函数，用于检测图中是否存在环
if(visited[i] == 1) return false;
// 如果当前节点在此次搜索中已被访问，表示存在环，返回false
if(visited[i] == -1) return true;
// 如果当前节点在之前的搜索中已被访问且没有发现环，无需再次访问
visited[i] = 1;
// 标记当前节点为正在访问
for(Integer j: map.get(i)){
// 遍历当前节点的所有邻接节点
if(!dfs(map,visited,j)) return false;
// 如果在递归过程中发现环，返回false
}
visited[i] = -1;
// 标记当前节点访问完成，没有发现环
return true;
// 返回true，表示当前节点所在路径没有环
}
}时间复杂度：O(n)
空间复杂度：O(n)
class Trie {
// Trie节点定义
private Trie[] children;
// 存放子节点的数组，表示26个英文字母
private boolean isEnd;
// 标记该节点是否为某个单词的结束
public Trie() {
// Trie构造函数
children = new Trie[26];
// 初始化子节点数组
isEnd = false;
// 初始化为非结束节点
}
public void insert(String word) {
// 插入单词到Trie树中
Trie node = this;
// 从根节点开始
for(int i = 0;i<word.length();i++){
// 遍历单词的每个字符
char c = word.charAt(i);
// 获取当前字符
int index = c-'a';
// 计算字符对应的索引
if(node.children[index]==null){
// 如果对应子节点不存在，则创建新的Trie节点
node.children[index] = new Trie();
}
node = node.children[index];
// 移动到对应的子节点
}
node.isEnd = true;
// 标记单词结束的节点
}
public boolean search(String word) {
// 搜索整个单词
Trie node = searchPrefix(word);
// 使用searchPrefix方法查找单词的前缀
return node != null && node.isEnd;
// 如果节点存在且为结束节点，则表示单词存在
}
public boolean startsWith(String prefix) {
// 检查是否存在以prefix为前缀的单词
return searchPrefix(prefix) != null;
// 只需检查prefix是否能被搜索到
}
private Trie searchPrefix(String prefix){
// 私有方法，用于搜索前缀
Trie node = this;
// 从根节点开始
for(int i = 0;i<prefix.length();i++){
// 遍历前缀的每个字符
char c = prefix.charAt(i);
// 获取当前字符
int index = c-'a';
// 计算字符对应的索引
if(node.children[index] == null){
// 如果对应子节点不存在，则返回null
return null;
}
node = node.children[index];
// 移动到对应的子节点
}
return node;
// 返回最后的节点，该节点对应前缀的最后一个字符
}
}时间复杂度：O(n) n为字符长度
空间复杂度：O(n)
class Solution {
public int coinChange(int[] coins, int amount) {
// dp[i]表示组成金额i所需的最少硬币数量
int[] dp = new int[amount + 1];
// 初始化dp数组，除了dp[0]为0（表示金额为0时不需要硬币）之外，其余设置为一个大数amount+1，表示初始状态下，金额i无法被凑齐
Arrays.fill(dp, amount + 1);
dp[0] = 0;
// 外层循环遍历所有硬币
for(int i = 0; i < coins.length; i++) {
// 内层循环从当前硬币面额开始到总金额
for(int j = coins[i]; j <= amount; j++) {
// 如果当前金额减去当前硬币面额的结果不是初始的大数，说明当前金额减去该硬币面额是可以被凑齐的
if(dp[j - coins[i]] != amount + 1) {
// 更新dp[j]为：不使用当前硬币凑齐金额j，和使用当前硬币凑齐金额j的最少硬币数量之间的较小值
dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);
}
}
}
// 如果dp[amount]仍然是初始设置的大数amount+1，说明金额amount无法被凑齐，返回-1；否则返回dp[amount]
return dp[amount] == amount + 1 ? -1 : dp[amount];
}
}时间复杂度：O(m*n)
空间复杂度：O(m)
class Solution {
public int[] productExceptSelf(int[] nums) {
int n = nums.length;
// 如果数组为空，直接返回一个空数组
if(n == 0) return new int[0];
// 创建答案数组，初始大小为n
int[] ans = new int[n];
// 初始化ans[0]为1，因为计算除了自身元素外的乘积时，第一个元素左侧没有其他元素
ans[0] = 1;
// 临时变量，用于计算右侧元素的乘积
int temp = 1;
// 第一遍循环：计算当前元素左侧所有元素的乘积
for(int i = 1; i < n; i++) {
ans[i] = nums[i - 1] * ans[i - 1];
}
// 第二遍循环：计算当前元素右侧所有元素的乘积，并与左侧乘积相乘得到最终结果
for(int i = n - 2; i >= 0; i--) {
temp *= nums[i + 1]; // 更新右侧乘积
ans[i] *= temp; // 左侧乘积与右侧乘积相乘
}
return ans;
}
}时间复杂度：O(n)
空间复杂度：O(1)
class MinStack {
// 主栈，用于存储所有元素
Stack<Integer> stack;
// 辅助栈，栈顶元素是当前栈中的最小元素
Stack<Integer> temp;
public MinStack() {
// 初始化两个栈
stack = new Stack<>();
temp = new Stack<>();
}
public void push(int val) {
// 将元素推入主栈
stack.push(val);
// 如果辅助栈为空，或者辅助栈的栈顶元素大于等于要推入的值，则将该值也推入辅助栈
if(temp.isEmpty() || temp.peek() >= val) temp.push(val);
}
public void pop() {
// 弹出主栈顶的元素，如果该元素与辅助栈顶的元素相等，也弹出辅助栈顶的元素
if(stack.pop().equals(temp.peek())) temp.pop();
}
public int top() {
// 返回主栈顶的元素，即最后一个入栈的元素
return stack.peek();
}
public int getMin() {
// 返回辅助栈顶的元素，即当前栈中的最小元素
return temp.peek();
}
}时间复杂度：O(1)
空间复杂度：O(n)
class Solution {
public boolean isValidBST(TreeNode root) {
// 调用辅助函数，初始化时，根节点的值应该在最小值和最大值之间
return isValidHelper(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
// 辅助递归函数，用于验证当前节点是否满足二叉搜索树的条件
private boolean isValidHelper(TreeNode root, long lower, long upper) {
// 如果当前节点为空，按照定义，空树是有效的二叉搜索树
if (root == null) return true;
// 如果当前节点的值不在(lower, upper)的范围内，则不是有效的二叉搜索树
if (root.val <= lower || root.val >= upper) return false;
// 递归检查左子树，更新上界；递归检查右子树，更新下界
// 对于左子树，所有节点的值必须小于当前节点的值
// 对于右子树，所有节点的值必须大于当前节点的值
return isValidHelper(root.left, lower, root.val) && isValidHelper(root.right, root.val, upper);
}
}时间复杂度：O(n)
空间复杂度：O(n)
class Solution {
boolean[][] visited; // 用于记录网格中的每个位置是否被访问过
int ans; // 用于计数岛屿数量
public int numIslands(char[][] grid) {
visited = new boolean[grid.length][grid[0].length]; // 初始化访问记录数组
ans = 0; // 初始化岛屿数量为0
// 遍历整个网格
for(int i = 0; i < grid.length; i++) {
for(int j = 0; j < grid[0].length; j++) {
// 如果当前位置是陆地并且没有被访问过
if(grid[i][j] == '1' && !visited[i][j]) {
dfs(grid, i, j); // 从当前位置开始进行深度优先搜索
ans++; // 搜索结束后，岛屿数量加1
}
}
}
return ans;
}
int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; // 用于表示上下左右四个方向的移动
private void dfs(char[][] grid, int row, int col) {
// 检查当前位置是否越界或已经被访问过，或者是水域
if(row < 0 || row >= grid.length || col < 0 || col >= grid[0].length || visited[row][col] || grid[row][col] == '0')
return;
visited[row][col] = true; // 标记当前位置已被访问
// 遍历四个方向进行深度优先搜索
for(int[] direction : directions) {
int rowN = row + direction[0];
int colN = col + direction[1];
dfs(grid, rowN, colN); // 对当前位置的四个方向递归调用DFS
}
}
}时间复杂度：O(mn)
空间复杂度：O(mn)
class Solution {
public int orangesRotting(int[][] grid) {
int fresh = 0, ans = 0; // fresh记录新鲜橘子数量，ans记录所需时间
Deque<int[]> dq = new LinkedList<>(); // 使用双端队列存储腐烂橘子的位置
// 初始化fresh和dq
for(int i = 0; i < grid.length; i++) {
for(int j = 0; j < grid[0].length; j++) {
if(grid[i][j] == 1) fresh++;
if(grid[i][j] == 2) dq.offerLast(new int[]{i, j});
}
}
// 如果没有新鲜橘子，返回0；如果没有腐烂橘子而有新鲜橘子，返回-1
if(fresh == 0) return 0;
else if(dq.isEmpty()) return -1;
int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; // 代表四个方向
while(!dq.isEmpty()) {
int size = dq.size();
while(size > 0) {
int[] temp = dq.pollFirst();
for(int[] direction : directions) {
int rowN = direction[0] + temp[0];
int colN = direction[1] + temp[1];
// 如果位置不合法或者不是新鲜橘子，跳过
if(rowN < 0 || rowN >= grid.length || colN < 0 || colN >= grid[0].length || grid[rowN][colN] != 1) continue;
// 使新鲜橘子腐烂，并加入队列
dq.offer(new int[]{rowN, colN});
grid[rowN][colN] = 2;
fresh--;
}
size--;
}
ans++;
}
// 如果还有新鲜橘子，返回-1；否则返回所需时间，减1是因为最后一轮腐烂后不需要额外时间
return fresh == 0 ? ans - 1 : -1;
}
}时间复杂度：O(n*m)
空间复杂度：O(n*m)
class Solution {
public int search(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int middle = left + (right - left) / 2;
if (target == nums[middle]) return middle; // 找到目标值，返回索引
// 判断中点是在旋转数组的左半部分还是右半部分
if (nums[left] <= nums[middle]) {
// 中点在左半部分，此时左半部分是有序的
if (nums[left] <= target && nums[middle] > target) right = middle - 1; // 目标在左半部分的有序区间中
else left = middle + 1; // 否则，目标在右半部分
} else {
// 中点在右半部分，此时右半部分是有序的
if (nums[right] >= target && nums[middle] < target) left = middle + 1; // 目标在右半部分的有序区间中
else right = middle - 1; // 否则，目标在左半部分
}
}
return -1; // 未找到目标值
}
}时间复杂度：O(logn)
空间复杂度：O(1)
class Solution {
List<List<Integer>> ans; // 存放最终结果的列表
List<Integer> path; // 用于存放当前的组合路径
public List<List<Integer>> combinationSum(int[] candidates, int target) {
path = new ArrayList<>(); // 初始化路径
ans = new ArrayList<>(); // 初始化答案列表
Arrays.sort(candidates); // 对候选数组进行排序，有助于后续优化
backTrack(candidates, target, 0, 0); // 开始回溯
return ans; // 返回结果
}
private void backTrack(int[] candidates, int target, int sum, int index) {
// 如果当前路径之和等于目标值，则复制当前路径到答案中
if (sum == target) {
ans.add(new ArrayList<>(path));
return;
}
// 遍历每个可能的选择
for (int i = index; i < candidates.length; i++) {
// 如果当前总和加上候选数字超过目标值，则无需继续探索
if (sum + candidates[i] > target) return;
// 否则，选择当前数字，加入路径
sum += candidates[i];
path.add(candidates[i]);
// 继续探索，注意，由于数字可以重复使用，下一次探索的起点仍然是i
backTrack(candidates, target, sum, i);
// 回溯，撤销选择
path.remove(path.size() - 1);
sum -= candidates[i];
}
}
}时间复杂度：
空间复杂度：
class Solution {
List<List<Integer>> ans = new ArrayList<>(); // 存放所有的排列结果
List<Integer> path = new ArrayList<>(); // 用于构建当前的排列
public List<List<Integer>> permute(int[] nums) {
// 初始时，将nums中的所有元素添加到path中
for (int num : nums) {
path.add(num);
}
// 从第0个位置开始深度优先搜索
dfs(0);
return ans; // 返回所有排列的结果
}
private void dfs(int index) {
// 当索引到达path的最后一个元素时，将当前路径添加到答案中
if (index == path.size() - 1) {
ans.add(new ArrayList<>(path));
return;
}
// 遍历当前索引到末尾的所有元素，尝试将它们放到当前位置index，并继续递归
for (int i = index; i < path.size(); i++) {
swap(i, index); // 将当前索引的元素与后面的元素交换
dfs(index + 1); // 递归处理下一个位置
swap(i, index); // 撤销之前的交换操作，回溯
}
}
// 用于交换path中两个位置的元素
private void swap(int x, int y) {
int temp = path.get(x);
path.set(x, path.get(y));
path.set(y, temp);
}
}时间复杂度：O(n!)
空间复杂度：O(n)
class Solution {
public int[][] merge(int[][] intervals) {
// 首先根据每个区间的起始位置排序
Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
List<int[]> lst = new ArrayList<>(); // 存储合并后的区间
// 初始化第一个区间的起始和结束位置
int left = intervals[0][0], right = intervals[0][1];
// 遍历每个区间
for (int i = 1; i < intervals.length; i++) {
// 如果当前区间的起始位置小于等于上一个区间的结束位置，则说明它们重叠
if (intervals[i][0] <= right) {
// 更新合并后区间的结束位置为当前区间结束位置和上一个区间结束位置的较大值
right = Math.max(right, intervals[i][1]);
} else {
// 如果不重叠，先将前一个区间添加到结果列表中
lst.add(new int[]{left, right});
// 然后更新起始和结束位置为当前区间的值
left = intervals[i][0];
right = intervals[i][1];
}
}
// 添加最后一个区间到结果列表
lst.add(new int[]{left, right});
// 将列表转换为数组形式返回
int[][] ans = new int[lst.size()][];
for (int i = 0; i < ans.length; i++) {
ans[i] = lst.get(i);
}
return ans;
}
}时间复杂度：O(nlogn)
空间复杂度：O(n)
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
// 如果树为空，或者根节点等于p或q，直接返回根节点
if(root == null || root.val == p.val || root.val == q.val) return root;
// 在左子树中查找p和q的最低公共祖先
TreeNode left = lowestCommonAncestor(root.left, p, q);
// 在右子树中查找p和q的最低公共祖先
TreeNode right = lowestCommonAncestor(root.right, p, q);
// 如果左子树为空，说明p和q都不在左子树中，返回右子树的结果
if(left == null) return right;
// 如果右子树为空，说明p和q都不在右子树中，返回左子树的结果
else if(right == null) return left;
// 如果左右子树的返回值都不为空，说明当前节点就是p和q的最低公共祖先
return root;
}
}时间复杂度：O(n)
空间复杂度：O(h)
class TimeMap {
// 使用HashMap存储每个键，每个键对应一个TreeMap来按时间戳排序存储值
HashMap<String, TreeMap<Integer, String>> map;
public TimeMap() {
map = new HashMap<>();
}
public void set(String key, String value, int timestamp) {
// 如果key不存在，创建新的TreeMap并关联到key
map.putIfAbsent(key, new TreeMap<>());
// 将时间戳和值添加到对应的TreeMap中
map.get(key).put(timestamp, value);
}
public String get(String key, int timestamp) {
TreeMap<Integer, String> tm = map.getOrDefault(key, new TreeMap<>());
// 找到小于等于给定时间戳的最大时间戳的条目
Map.Entry<Integer, String> entry = tm.floorEntry(timestamp);
// 如果条目存在，返回对应的值，否则返回空字符串
return entry != null ? entry.getValue() : "";
}
}时间复杂度：O(logT)
空间复杂度：O(logT)
class Solution {
public List<List<String>> accountsMerge(List<List<String>> accounts) {
// 邮箱到其账户ID的映射
HashMap<String, Integer> emailToId = new HashMap<>();
int n = accounts.size();
// 初始化并查集
UnionFind myUnion = new UnionFind(n);
for(int i = 0; i < n; i++) {
int num = accounts.get(i).size();
for(int j = 1; j < num; j++) {
String curEmail = accounts.get(i).get(j);
// 将当前邮箱与账户ID关联，如果已存在，则合并
if(!emailToId.containsKey(curEmail)) emailToId.put(curEmail, i);
else myUnion.union(i, emailToId.get(curEmail));
}
}
// ID到邮箱列表的映射，用于聚合并查集中合并的账户的所有邮箱
Map<Integer, List<String>> idToEmails = new HashMap<>();
for(Map.Entry<String, Integer> entry : emailToId.entrySet()) {
int id = myUnion.find(entry.getValue());
List<String> emails = idToEmails.getOrDefault(id, new ArrayList<>());
emails.add(entry.getKey());
idToEmails.put(id, emails);
}
// 构建结果
List<List<String>> res = new ArrayList<>();
for(Map.Entry<Integer, List<String>> entry : idToEmails.entrySet()) {
List<String> emails = entry.getValue();
Collections.sort(emails);
List<String> tmp = new ArrayList<>();
tmp.add(accounts.get(entry.getKey()).get(0));
tmp.addAll(emails);
res.add(tmp);
}
return res;
}
}
class UnionFind {
int[] parent;
public UnionFind(int n){
parent = new int[n];
for(int i = 0; i < n; i++) {
parent[i] = i; // 初始时，每个节点的父节点是它自己
}
}
public void union(int index1, int index2){
parent[find(index2)] = find(index1); // 合并两个集合
}
public int find(int index){
if(parent[index] != index) {
parent[index] = find(parent[index]); // 路径压缩
}
return parent[index];
}
}时间复杂度：O(nlogn)
空间复杂度：O(n)
冒泡排序
class Solution {
public void sortColors(int[] nums) {
int len = nums.length;
if(len < 2) return; // 如果数组长度小于2，则不需要排序
int zero = 0, two = len, i = 0; // 初始化三个指针，zero指向下一个0的插入位置，two指向下一个2的插入位置，i用于遍历数组
while(i < two) {
if(nums[i] == 0) {
// 如果当前数字是0，那么将其与zero指向的位置交换，并将zero和i指针都向右移
swap(nums, i, zero);
zero++;
i++;
} else if(nums[i] == 1) {
// 如果当前数字是1，不需要交换，i指针向右移
i++;
} else {
// 如果当前数字是2，将其与two指针左侧的位置交换，然后two指针左移
two--;
swap(nums, two, i);
// 注意这里不移动i指针，因为交换过来的数还没有被检查
}
}
}
private void swap(int[] nums, int x, int y){
// 交换数组中两个位置的元素
int temp = nums[x];
nums[x] = nums[y];
nums[y] = temp;
}时间复杂度：O(n)
空间复杂度：O(1)
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
// 将wordDict转换成HashSet以提高查找效率
Set<String> wordDictSet = new HashSet(wordDict);
// dp数组用于记录字符串s的前i个字符能否被wordDict中的单词组成
boolean[] dp = new boolean[s.length() + 1];
dp[0] = true; // 空字符串默认是可以被组成的
// 外层循环遍历字符串s的所有字符
for(int i = 1; i <= s.length(); i++) {
// 内层循环尝试将字符串分割成两部分，j为分割点
for(int j = 0; j < i; j++) {
// 如果s的前j个字符可以被组成且j到i的子字符串在wordDict中，则s的前i个字符也可以被组成
if(dp[j] && wordDictSet.contains(s.substring(j, i))) {
dp[i] = true;
break; // 找到一种分割方式后即可停止
}
}
}
// 返回整个字符串s能否被wordDict中的单词组成
return dp[s.length()];
}
}时间复杂度：O(n^2)
空间复杂度：O(n)
class Solution {
public boolean canPartition(int[] nums) {
int sum = 0;
// 计算数组的总和
for(int num : nums) sum += num;
// 如果总和为奇数，则不可能分割成两个和相等的子集
if(sum % 2 == 1) return false;
// 目标和为总和的一半
int target = sum / 2;
// dp数组，dp[j]存储数组nums中的元素是否可以组成总和为j的子集
int[] dp = new int[target + 1];
// 遍历数组中的每一个元素
for(int i = 0; i < nums.length; i++) {
// 从target开始向下遍历，避免重复计算
for(int j = target; j >= nums[i]; j--) {
// 更新dp[j]，比较不加入当前元素和加入当前元素后的总和
dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
}
}
// 如果dp[target]等于target，则表示可以找到和为target的子集
return dp[target] == target;
}
}时间复杂度：O(n*target)
空间复杂度：P(target)
class Solution {
public int myAtoi(String s) {
// 去除字符串开头的空格，并转换为字符数组
char[] c = s.trim().toCharArray();
// 如果字符串为空，返回0
if(c.length == 0) return 0;
// 定义边界值，用于后面判断整数是否溢出
int boundary = Integer.MAX_VALUE / 10;
// pos用于标记正负，1为正，-1为负
int pos = 1;
// x用于标记开始转换的位置
int x = 1;
// 初始化结果为0
int res = 0;
// 判断正负号
if(c[0] == '-') pos = -1;
else if(c[0] != '+') x = 0;
// 从第一个数字字符或符号字符的下一位开始遍历
for(int i = x; i < c.length; i++) {
// 如果当前字符不是数字，则停止转换
if(c[i] < '0' || c[i] > '9') break;
// 如果整数部分将要溢出，返回整数的最大值或最小值
if(res > boundary || res == boundary && c[i] > '7')
return pos == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
// 将当前数字字符转换为整数，并累加到结果中
res = res * 10 + (c[i] - '0');
}
// 根据正负号返回最终结果
return pos * res;
}
}时间复杂度：O(n)
空间复杂度：O(n )
class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> ans = new ArrayList<>(); // 存放螺旋遍历的结果
int l = 0, r = matrix[0].length-1, u = 0, d = matrix.length-1; // 初始化左、右、上、下边界
while(true) {
for(int i = l; i <= r; i++) ans.add(matrix[u][i]); // 向右遍历
if(++u > d) break; // 上边界下移，如果上边界超过下边界，则遍历结束
for(int i = u; i <= d; i++) ans.add(matrix[i][r]); // 向下遍历
if(--r < l) break; // 右边界左移，如果右边界超过左边界，则遍历结束
for(int i = r; i >= l; i--) ans.add(matrix[d][i]); // 向左遍历
if(--d < u) break; // 下边界上移，如果下边界超过上边界，则遍历结束
for(int i = d; i >= u; i--) ans.add(matrix[i][l]); // 向上遍历
if(++l > r) break; // 左边界右移，如果左边界超过右边界，则遍历结束
}
return ans; // 返回结果
}
}时间复杂度：O(n)
空间复杂度：O(n)
class Solution {
// 存储所有子集的结果列表
List<List<Integer>> ans = new ArrayList<>();
// 用于存储当前递归路径的子集
List<Integer> path = new ArrayList<>();
public List<List<Integer>> subsets(int[] nums) {
// 从数组的第一个元素开始递归
dfs(nums, 0);
return ans;
}
private void dfs(int[] nums, int index) {
// 如果索引超过数组长度，直接返回
if(index > nums.length) return;
// 将当前路径添加到结果列表中
ans.add(new ArrayList<>(path));
// 遍历当前索引之后的所有元素
for(int i = index; i < nums.length; i++) {
// 将当前元素添加到路径中
path.add(nums[i]);
// 递归调用dfs，索引为下一个元素
dfs(nums, i + 1);
// 回溯，移除路径中最后一个元素
path.remove(path.size() - 1);
}
}
}时间复杂度：O(2^n * n)
空间复杂度：O(n)
class Solution {
List<Integer> ans = new ArrayList<>(); // 存储二叉树的右视图
public List<Integer> rightSideView(TreeNode root) {
dfs(root, 0); // 从根节点开始深度优先搜索
return ans; // 返回结果列表
}
private void dfs(TreeNode root, int depth) {
if(root == null) return; // 如果节点为空，则返回
// 如果当前深度等于结果列表的大小，说明这是这一层遇到的第一个节点
if(ans.size() == depth) ans.add(root.val);
// 首先遍历右子树，确保右侧的节点先被访问
dfs(root.right, depth + 1);
// 然后遍历左子树
dfs(root.left, depth + 1);
}
}时间复杂度：O(n)
空间复杂度：O(n)
class Solution {
public String longestPalindrome(String s) {
String ans = ""; // 用于存储最长的回文子串
// dp数组，dp[i][j]表示子串s[i...j]是否是回文
boolean[][] dp = new boolean[s.length()][s.length()];
// 从字符串末尾开始遍历到开头，确保正确的状态转移
for (int i = s.length() - 1; i >= 0; i--) {
for (int j = i; j < s.length(); j++) {
// 检查当前子串是否为回文
// 条件：字符相等且（子串长度小于3或者去掉头尾后的子串为回文）
if (s.charAt(i) == s.charAt(j) && (j - i < 3 || dp[i + 1][j - 1])) {
dp[i][j] = true;
// 如果这个回文子串比已找到的回文子串长，更新ans
if (j - i > ans.length() - 1) {
ans = s.substring(i, j + 1);
}
}
}
}
return ans;
}
}时间复杂度：O(n^2)
空间复杂度：O(n^2)
class Solution {
public int uniquePaths(int m, int n) {
int[][] dp = new int[m][n]; // dp[i][j]表示到达i,j位置的唯一路径数
// 初始化边界条件，第一行和第一列的路径数为1
for(int i = 0; i < dp.length; i++) {
Arrays.fill(dp[i], 1);
}
// 通过状态转移方程计算每个位置的唯一路径数
for(int i = 1; i < m; i++) {
for(int j = 1; j < n; j++) {
// 到达当前位置的路径数为上方和左侧位置的路径数之和
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
// 返回到达右下角位置的唯一路径数
return dp[m - 1][n - 1];
}
}时间复杂度：O(m*n)
空间复杂度：O(m*n)
class Solution {
// 定义一个全局变量map存储中序遍历数组中值到索引的映射
HashMap<Integer, Integer> map;
public TreeNode buildTree(int[] preorder, int[] inorder) {
map = new HashMap<>();
// 填充map，便于快速查找中序遍历中元素的索引
for(int i = 0; i < inorder.length; i++) {
map.put(inorder[i], i);
}
// 构建并返回二叉树
return buildMyTree(preorder, 0, preorder.length - 1, 0, inorder.length - 1);
}
private TreeNode buildMyTree(int[] preorder, int preStart, int preEnd, int inStart, int inEnd) {
// 如果前序或中序的开始位置大于结束位置，则子树为空
if (preStart > preEnd || inStart > inEnd) return null;
// 根据前序遍历的第一个元素创建根节点
TreeNode node = new TreeNode(preorder[preStart]);
// 在中序遍历中找到根节点的位置，以分割树的左右子树
int inRootIndex = map.get(preorder[preStart]);
// 计算左子树的大小
int leftTreeSize = inRootIndex - inStart;
// 递归构建左子树
TreeNode left = buildMyTree(preorder, preStart + 1, preStart + leftTreeSize, inStart, inRootIndex - 1);
// 递归构建右子树
TreeNode right = buildMyTree(preorder, preStart + leftTreeSize + 1, preEnd, inRootIndex + 1, inEnd);
// 将左右子树连接到根节点
node.left = left;
node.right = right;
return node;
}
}时间复杂度：O(n)
空间复杂度：O(n)
class Solution {
public int maxArea(int[] height) {
// 初始化左右指针
int left = 0, right = height.length - 1;
// 用于存储最大面积
int res = 0;
// 当左指针小于右指针时循环
while(left < right) {
// 计算当前的面积，并更新最大面积res
res = height[left] < height[right] ?
Math.max(res, (right - left) * height[left++]) : // 如果左边的高度小于右边的高度，移动左指针
Math.max(res, (right - left) * height[right--]); // 否则，移动右指针
}
// 返回最大的面积
return res;
}
}时间复杂度：O(n)
空间复杂度：O(1)
class Solution {
List<String> ans = new ArrayList<>(); // 用于存储所有可能的字母组合
public List<String> letterCombinations(String digits) {
if (digits == null || digits.length() == 0) {
return ans; // 如果输入为空，直接返回空列表
}
// 映射数字到对应的字母
HashMap<Integer, String> map = new HashMap<>();
map.put(2, "abc");
map.put(3, "def");
map.put(4, "ghi");
map.put(5, "jkl");
map.put(6, "mno");
map.put(7, "pqrs");
map.put(8, "tuv");
map.put(9, "wxyz");
// 开始回溯
backTracking(digits, map, 0);
return ans;
}
StringBuilder temp = new StringBuilder(); // 用于构建当前的字母组合
private void backTracking(String digits, HashMap<Integer, String> map, int index){
if(index >= digits.length()){
ans.add(temp.toString()); // 如果当前索引已经超过了数字字符串的长度，将当前组合添加到答案中
return;
}
// 获取当前数字对应的所有字母
String x = map.get(digits.charAt(index) - '0');
for(int i = 0; i < x.length(); i++){
temp.append(x.charAt(i)); // 将当前字母加到组合中
backTracking(digits, map, index + 1); // 递归构建后续的字母组合
temp.deleteCharAt(temp.length() - 1); // 回溯，移除最后一个字母，尝试下一个可能的字母
}
}
}时间复杂度：O(3^N * 4^M)
空间复杂度：O(N)
class Solution {
public boolean exist(char[][] board, String word) {
// 遍历二维数组的每个起始点
for(int i = 0; i < board.length; i++){
for(int j = 0; j < board[0].length; j++){
// 如果当前字符与单词首字母匹配，开始深度优先搜索（DFS）
if(board[i][j] == word.charAt(0)){
if(dfs(board, word, i, j, 0)) return true;
}
}
}
return false; // 搜索所有路径后仍未找到，返回 false
}
// 定义上下左右四个方向的偏移量
int[][] directions = {{1,0},{-1,0},{0,1},{0,-1}};
private boolean dfs(char[][] board, String word, int row, int col, int index){
// 检查边界条件或当前字符是否不匹配
if(row < 0 || row >= board.length || col < 0 || col >= board[0].length
|| board[row][col] != word.charAt(index)) return false;
// 匹配到单词最后一个字符，说明找到单词，返回 true
if(index == word.length()-1 && board[row][col] == word.charAt(index)) return true;
// 临时标记当前字符为已访问（防止重复搜索）
board[row][col] = '\\';
// 向四个方向递归搜索
boolean found = false;
for(int[] direction : directions){
int rowN = row + direction[0];
int colN = col + direction[1];
if(dfs(board, word, rowN, colN, index + 1)) found = true;
}
// 回溯：恢复当前字符原有状态
board[row][col] = word.charAt(index);
return found; // 返回搜索结果
}
}时间复杂度：O(N * M * 4^S)
空间复杂度：O(S) S代表单词长度
class Solution {
public List<Integer> findAnagrams(String s, String p) {
// 如果s的长度小于p，则直接返回空列表
if(s.length() < p.length()) return new ArrayList<>();
// 将字符串p转化为字符数组
char[] c = p.toCharArray();
// 用于存储字符串p中字符的频率
HashMap<Character, Integer> map = new HashMap<>();
// 初始化map
for(char temp : c) {
map.put(temp, map.getOrDefault(temp, 0) + 1);
}
// 定义左右指针，有效匹配的字符种类数量
int left = 0, right = 0, valid = 0;
// 存放结果的列表
List<Integer> ans = new ArrayList<>();
// 临时用于存储当前窗口内字符的频率
HashMap<Character, Integer> temp = new HashMap<>();
// 开始滑动窗口
while(right < s.length()) {
// 如果当前字符在p中，更新temp中的频率，并检查是否匹配
if(map.containsKey(s.charAt(right))) {
temp.put(s.charAt(right), temp.getOrDefault(s.charAt(right), 0) + 1);
if(temp.get(s.charAt(right)).equals(map.get(s.charAt(right)))) valid++;
}
// 扩大窗口
right++;
// 当窗口大小等于p长度时，检查是否找到了一个解
while(right - left >= p.length()) {
if(valid == map.size()) ans.add(left); // 如果有效匹配数量等于map的大小，说明找到了一个解
char lChar = s.charAt(left);
// 缩小窗口
left++;
// 如果左侧字符在p中，更新temp频率，并可能更新有效匹配数量
if(map.containsKey(lChar)) {
if(map.get(lChar).equals(temp.get(lChar))) valid--;
temp.put(lChar, temp.get(lChar) - 1);
}
}
}
return ans;
}
}时间复杂度：O(n+m)
空间复杂度：O(m)
class Solution {
private int[] rootHeights; // 以每个节点为根时树的高度
private int[] h; // 每个节点为根的子树的最大高度
List<Integer>[] neighbors; // 邻接表表示的图
int minHeight; // 最小树高
public List<Integer> findMinHeightTrees(int n, int[][] edges) {
// 初始化邻接表
neighbors = new ArrayList[n];
for (int i = 0; i < n; i++) {
neighbors[i] = new ArrayList<>();
}
// 构造邻接表
for (int[] edge : edges) {
int x = edge[0];
int y = edge[1];
neighbors[x].add(y);
neighbors[y].add(x);
}
// 初始化h数组
h = new int[n];
dfsFirst(0, -1); // 第一遍dfs计算每个节点的高度
// 初始化rootHeights数组和最小高度
rootHeights = new int[n];
minHeight = n;
dfsSecond(0, -1); // 第二遍dfs根据换根DP思想计算每个节点作为根的树的高度
// 寻找高度最小的树的根节点
List<Integer> ans = new ArrayList<>();
for (int i = 0; i < n; i++) {
if (rootHeights[i] == minHeight) ans.add(i);
}
return ans;
}
// 第一次DFS遍历计算每个节点作为根的子树的最大高度
private int dfsFirst(int node, int past) {
int height = 1; // 节点本身的高度
for (int child : neighbors[node]) {
if (child == past) continue; // 跳过父节点
height = Math.max(height, dfsFirst(child, node) + 1); // 计算最大高度
}
h[node] = height;
return height;
}
// 第二次DFS遍历根据换根DP思想更新每个节点作为根的树的高度
private void dfsSecond(int node, int past) {
int maxHeight = 0, secondHeight = 0; // 当前节点的最大和次大子树高度
for (int child : neighbors[node]) {
if (h[child] > maxHeight) {
secondHeight = maxHeight;
maxHeight = h[child];
} else if (h[child] > secondHeight) {
secondHeight = h[child];
}
}
rootHeights[node] = maxHeight + 1; // 更新当前节点作为根的树的高度
minHeight = Math.min(minHeight, rootHeights[node]); // 更新最小高度
for (int child : neighbors[node]) {
if (child == past) continue;
h[node] = (h[child] == maxHeight ? secondHeight : maxHeight) + 1; // 换根
dfsSecond(child, node); // 递归子节点
}
}
}时间复杂度：O(n)
空间复杂度：O(n)
class Solution {
public int leastInterval(char[] tasks, int n) {
// table记录每个任务的数量
int[] table = new int[26];
// mode记录出现次数最多的任务的数量
int mode = 0;
// count记录出现次数最多的任务的种类数
int count = 0;
for (char task : tasks) {
table[task - 'A']++; // 计算每个任务的数量
mode = Math.max(mode, table[task - 'A']); // 更新出现次数最多的任务的数量
}
for (int temp : table) {
if (temp == mode) count++; // 统计有多少种任务的数量等于mode
}
// 核心逻辑：
// 如果按照任务种类交替执行，最少需要的时间为(mode-1)*(n+1)+count
// 但如果任务种类较少，按此方法计算的时间可能小于tasks的总长度，此时应返回tasks的长度
return Math.max(tasks.length, (mode - 1) * (n + 1) + count);
}
}时间复杂度：O(n)
空间复杂度：O(1)
class LRUCache {
// 定义双向链表的节点类
private static class Node {
int key, value;
Node prev, next;
Node(int k, int v){
key = k;
value = v;
}
}
// 缓存容量
private final int capacity;
// 哑节点作为双向链表的头部和尾部
private final Node dummy = new Node(0,0);
// 哈希表，用于O(1)时间内找到键对应的节点
private final Map<Integer,Node> keyToNode = new HashMap<>();
public LRUCache(int capacity) {
this.capacity = capacity;
// 初始化哑节点的前驱和后继指向自己，形成环
dummy.prev = dummy;
dummy.next = dummy;
}
public int get(int key) {
// 获取键对应的节点，若不存在返回-1
Node node = getNode(key);
return node == null ? -1 : node.value;
}
public void put(int key, int value) {
// 尝试获取节点，若存在则更新值
Node node = getNode(key);
if(node != null){
node.value = value;
return;
}
// 创建新节点，加入哈希表和双向链表的头部
node = new Node(key, value);
keyToNode.put(key, node);
pushFront(node);
// 如果超出容量，移除最近最少使用的节点
if(keyToNode.size() > capacity){
Node backNode = dummy.prev;
keyToNode.remove(backNode.key);
remove(backNode);
}
}
// 获取节点，如果存在则移动到双向链表头部表示最近使用
private Node getNode(int key){
if(!keyToNode.containsKey(key)) return null;
Node node = keyToNode.get(key);
remove(node);
pushFront(node);
return node;
}
// 从双向链表中移除节点
private void remove(Node node){
node.next.prev = node.prev;
node.prev.next = node.next;
}
// 将节点加入到双向链表头部
private void pushFront(Node node){
node.prev = dummy;
node.next = dummy.next;
dummy.next.prev = node;
dummy.next = node;
}
}时间复杂度：O(1)
空间复杂度：O(n)
class Solution {
int res = 0; // 用于存储第k小的元素的值
int k; // 目标是找到第k小的元素
public int kthSmallest(TreeNode root, int k) {
this.k = k; // 初始化k值
dfs(root); // 从根节点开始深度优先搜索
return res; // 返回结果
}
private void dfs(TreeNode root){
if(root == null) return; // 如果节点为空，则返回
dfs(root.left); // 先递归访问左子树
if(k == 0) return; // 如果已经找到第k小的元素，则提前返回
if(--k == 0) res = root.val; // 找到第k小的元素，存储其值
dfs(root.right); // 最后递归访问右子树
}
}时间复杂度：O(n)
空间复杂度：O(n)
class Solution {
public String minWindow(String s, String t) {
// 如果s的长度小于t的长度，直接返回空字符串
if (s.length() < t.length()) return "";
int leftP = 0, rightP = 0; // 定义滑动窗口的左右指针
int ans = Integer.MAX_VALUE; // 存储最小窗口的长度
int leftA = 0, rightA = 0; // 存储最小窗口的起始和结束位置
int countT = t.length(); // t中剩余需要匹配的字符数量
int[] count = new int[128]; // 哈希表，记录t中每个字符出现的次数
// 初始化哈希表
for (int i = 0; i < t.length(); i++) count[t.charAt(i)]++;
// 扩大窗口
while (rightP < s.length()) {
// 如果当前字符在t中，减少对应的需要匹配的数量
if (count[s.charAt(rightP++)]-- > 0) countT--;
// 当窗口中包含了所有t的字符时，尝试缩小窗口
while (countT == 0) {
// 更新最小窗口
if (rightP - leftP < ans) {
ans = rightP - leftP;
leftA = leftP;
rightA = rightP;
}
// 如果左边的字符是t中的字符，增加对应的需要匹配的数量
if (count[s.charAt(leftP++)]++ == 0) {
countT++;
}
}
}
// 返回最小窗口的字符串，如果没有找到符合条件的窗口返回空字符串
return ans == Integer.MAX_VALUE ? "" : s.substring(leftA, rightA);
}
}时间复杂度：O(n)
空间复杂度：O(1)
public class Codec {
// 将二叉树编码为字符串
public String serialize(TreeNode root) {
// 若节点为空，用"null,"表示
if(root == null) return "null,";
// 先序遍历（根-左-右），使用逗号分隔值
String word = root.val + ",";
String left = serialize(root.left);
String right = serialize(root.right);
// 拼接字符串
return word + left + right;
}
// 将字符串解码为二叉树
public TreeNode deserialize(String data) {
// 使用队列按顺序存储节点值
Queue<String> nodes = new LinkedList<>(Arrays.asList(data.split(",")));
return buildTree(nodes);
}
// 使用队列构建二叉树
private TreeNode buildTree(Queue<String> nodes) {
String val = nodes.poll(); // 弹出队列头部的值作为节点值
// 若值为"null"，表示该处节点为空
if (val.equals("null")) return null;
// 否则，创建新节点
TreeNode root = new TreeNode(Integer.parseInt(val));
// 递归构建左右子树
root.left = buildTree(nodes);
root.right = buildTree(nodes);
return root;
}
}时间复杂度：O(n)
空间复杂度：O(n)
class Solution {
public int trap(int[] height) {
Deque<Integer> dq = new LinkedList<>(); // 使用双端队列作为单调栈
int current = 0, ans = 0; // current用于遍历height数组，ans用于累计雨水量
while (current < height.length) {
// 当栈不为空且当前高度大于栈顶高度时，说明找到了一个低洼处
while (!dq.isEmpty() && height[current] > height[dq.peekLast()]) {
int h = height[dq.pollLast()]; // 获取低洼的高度
if (dq.isEmpty()) { // 如果栈空了，说明没有左边界
break;
}
int w = current - dq.peekLast() - 1; // 计算宽度
int min = Math.min(height[dq.peekLast()], height[current]); // 计算低洼两边较低的高度
ans += w * (min - h); // 根据木桶原理，可存水量由较短的边决定
}
dq.offerLast(current); // 将当前索引压入栈中
current++; // 移动到下一个位置
}
return ans; // 返回累计的雨水量
}
}时间复杂度：O(n)
空间复杂度：O(n)
class MedianFinder {
// 大根堆，存放所有小于当前中位数的元素
PriorityQueue<Integer> pqB = new PriorityQueue<>((a, b) -> a - b);
// 小根堆，存放所有大于当前中位数的元素
PriorityQueue<Integer> pqS = new PriorityQueue<>((a, b) -> b - a);
public MedianFinder() {
// 构造方法，初始化数据结构
}
public void addNum(int num) {
// 获取两个堆的大小
int lenS = pqS.size(), lenB = pqB.size();
// 如果两个堆大小相等，优先放入小根堆
if (lenS == lenB) {
// 直接放入小根堆或者先在大根堆中筛选后放入小根堆
if (pqB.isEmpty() || num <= pqB.peek()) {
pqS.add(num);
} else {
pqS.add(pqB.poll());
pqB.add(num);
}
} else {
// 两个堆大小不等，优先放入大根堆
if (pqS.peek() <= num) {
pqB.add(num);
} else {
pqB.add(pqS.poll());
pqS.add(num);
}
}
}
public double findMedian() {
// 获取两个堆的大小
int lenS = pqS.size(), lenB = pqB.size();
// 根据堆的大小决定如何计算中位数
if (lenS > lenB) return pqS.peek();
// 堆大小相等时，取两个堆顶元素的平均值
return (pqS.peek() + pqB.peek()) / 2.0;
}
}时间复杂度：O(logn)
空间复杂度：O(1)
class Solution {
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
Deque<String> dq = new LinkedList<>(); // 使用队列实现广度优先搜索
HashSet<String> set = new HashSet<>(wordList); // 用于快速判断单词是否在wordList中
HashSet<String> set2 = new HashSet<>(); // 记录已访问过的单词，避免重复访问
int ans = 0; // 用于记录转换序列的长度
dq.offer(beginWord); // 将起始单词加入队列
set2.add(beginWord); // 将起始单词标记为已访问
while(!dq.isEmpty()){ // 当队列非空时循环
int size = dq.size(); // 获取当前层的宽度
ans++; // 开始新一轮的转换，长度加1
while(size > 0){ // 遍历当前层的所有单词
String temp = dq.poll(); // 取出一个单词进行转换尝试
// 尝试修改当前单词的每一个位置
for(int i = 0; i < temp.length(); i++){
for(int j = 'a'; j <= 'z'; j++){ // 尝试每一个可能的字符
String tem = temp.substring(0, i) + (char)j + temp.substring(i + 1); // 生成新的单词
// 如果新单词在wordList中且未被访问过
if(set.contains(tem) && !set2.contains(tem)){
if(tem.equals(endWord)) return ans + 1; // 如果新单词就是目标单词，返回当前序列长度加1
dq.offer(tem); // 将新单词加入队列，以便下一轮转换
set2.add(tem); // 标记新单词为已访问
}
}
}
size--; // 当前层待处理单词减少
}
}
return 0; // 如果无法转换到目标单词，返回0
}
}时间复杂度：O(N*M^2)
空间复杂度：P(N)
class Solution {
public int calculate(String s) {
Deque<Integer> dq = new ArrayDeque<>(); // 存储数字
Deque<Character> op = new ArrayDeque<>(); // 存储操作符
s = s.replaceAll(" ",""); // 去除所有空格
dq.addLast(0); // 为了处理首位是负数的情况
char[] cs = s.toCharArray(); // 将字符串转为字符数组，便于处理
for(int i = 0; i < cs.length; i++){
char c = cs[i];
if(c == '(') op.addLast(c); // 遇到左括号，直接入栈
else if(c == ')'){
// 遇到右括号，计算到最近的一个左括号为止
while(!op.isEmpty()){
char temp = op.peekLast();
if(temp != '('){
calc(dq, op);
}else{
op.pollLast(); // 弹出左括号
break;
}
}
}else{
if(isNum(c)) { // 如果是数字，解析整个数字
int u = 0, j = i;
while(j < s.length() && isNum(cs[j])) u = u * 10 + (cs[j++] - '0');
dq.addLast(u);
i = j - 1; // 更新i，跳过整个数字
}else{
// 处理负数的情况
if(i > 0 && (cs[i-1] == '(' || cs[i-1] == '+' || cs[i-1] == '-')) dq.addLast(0);
// 计算栈顶的操作符（如果有必要的话）
while(!op.isEmpty() && op.peekLast() != '(') calc(dq, op);
op.addLast(c); // 当前操作符入栈
}
}
}
// 计算剩余的操作
while(!op.isEmpty()) calc(dq, op);
return dq.peekLast(); // 最后栈中剩下的就是结果
}
// 执行一次计算
private void calc(Deque<Integer> dq, Deque<Character> op) {
if(dq.isEmpty() || dq.size() < 2 || op.isEmpty()) return;
int b = dq.pollLast(), a = dq.pollLast(); // 弹出两个数字
char c = op.pollLast(); // 弹出一个操作符
// 根据操作符进行计算，计算结果入栈
dq.addLast(c == '+' ? a + b : a - b);
}
// 判断字符是否为数字
private boolean isNum(char c) {
return Character.isDigit(c);
}
}时间复杂度：O(n)
空间复杂度：O(n)
class Solution {
public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
int n = startTime.length; // 工作数量
// 将工作按结束时间排序
int[][] jobs = new int[n][];
for(int i = 0; i < n; i++) {
jobs[i] = new int[]{startTime[i], endTime[i], profit[i]};
}
Arrays.sort(jobs, (a, b) -> a[1] - b[1]);
// dp[i]表示处理到第i个工作时的最大收益
int[] dp = new int[n + 1];
for(int i = 0; i < n; i++) {
// 使用二分查找找到不与当前工作冲突的最近的工作
int j = search(jobs, i, jobs[i][0]);
// 更新dp表，选择做当前工作和不做当前工作的最大收益
dp[i + 1] = Math.max(dp[i], dp[j + 1] + jobs[i][2]);
}
// 返回处理完所有工作后的最大收益
return dp[n];
}
// 二分查找不与当前工作冲突的最近的工作的索引
private int search(int[][] jobs, int index, int upper) {
int left = -1; // 初始化左边界
while(left + 1 < index) {
int mid = (left + index) >>> 1; // 计算中点
if(jobs[mid][1] <= upper) left = mid; // 调整左边界
else index = mid; // 调整右边界
}
return left; // 返回不冲突工作的最大索引
}
}时间复杂度：O(nlogn)
空间复杂度：O(n)
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
// 使用优先队列，根据节点的值排序
PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> a.val - b.val);
// 将k个链表的头节点加入优先队列
for(ListNode list : lists) {
if(list != null) {
pq.offer(list);
}
}
// 创建一个虚拟头节点，简化链表操作
ListNode dummy = new ListNode();
ListNode cur = dummy;
// 当优先队列非空时循环
while(!pq.isEmpty()) {
// 弹出最小的节点，并将其连接到结果链表上
ListNode temp = pq.poll();
// 如果该节点的下一个节点非空，则将下一个节点加入优先队列
if(temp.next != null) {
pq.offer(temp.next);
}
// 将弹出的节点连接到当前链表的末尾
cur.next = temp;
cur = cur.next;
}
// 返回合并后的链表头节点
return dummy.next;
}
}时间复杂度：O(nlogk)
空间复杂度：O(n)
class Solution {
public int largestRectangleArea(int[] heights) {
// 扩展数组，前后各添加一个高度为0的柱子，简化边界情况的处理
int[] newH = new int[heights.length + 2];
newH[0] = 0; // 数组前端添加一个高度为0的柱子
// 将原数组中的高度拷贝到新数组中，保留了前后的0高度柱子
for(int i = 1; i < newH.length - 1; i++) {
newH[i] = heights[i - 1];
}
// 更新heights指向新的数组
heights = newH;
// 使用单调栈来存储柱子的索引，栈内的柱子高度从栈底到栈顶单调递增
Deque<Integer> stack = new ArrayDeque<>();
stack.push(0); // 初始化栈，放入一个高度为0的柱子的索引
int ans = 0; // 用于记录最大矩形的面积
// 遍历所有的柱子
for(int i = 1; i < heights.length; i++) {
// 当前柱子的高度大于栈顶柱子的高度时，直接入栈
if(heights[i] > heights[stack.peek()]) stack.push(i);
// 当前柱子的高度等于栈顶柱子的高度时，替换栈顶元素
else if(heights[i] == heights[stack.peek()]){
stack.pop();
stack.push(i);
} else {
// 当前柱子的高度小于栈顶柱子的高度时，计算栈顶柱子能构成的最大矩形面积
while(heights[i] < heights[stack.peek()]){
int mid = stack.pop(), left = stack.peek(), right = i;
int w = right - left - 1; // 计算宽度
int h = heights[mid]; // 高度
ans = Math.max(ans, w * h); // 更新最大矩形面积
}
stack.push(i);
}
}
return ans; // 返回最大矩形面积
}
}时间复杂度：O(n)
空间复杂度：O(n)