CodeTop 100（更新中）

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:
输入: s = “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。

示例 2:
输入: s = “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。

示例 3:
输入: s = “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，“pwke” 是一个子序列，不是子串。

提示：
0 <= s.length <= 5 * 104
s 由英文字母、数字、符号和空格组成

class Solution {public int lengthOfLongestSubstring(String s) {boolean[] boolArr = new boolean[128];int left = 0;int right = 0;int distance = 0;int max = 0;while(right < s.length()) {if(!boolArr[s.charAt(right)]) {boolArr[s.charAt(right)] = true;right ++;continue;}distance = right - left;max = Math.max(max, distance);while(boolArr[s.charAt(right)]) {boolArr[s.charAt(left ++)] = false;}}distance = right - left;return Math.max(max, distance);}
}

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例 2：
输入：head = [1,2]
输出：[2,1]

示例 3：
输入：head = []
输出：[]

提示：
链表中节点的数目范围是 [0, 5000]
-5000 <= Node.val <= 5000

class Solution {public ListNode reverseList(ListNode head) {if(head == null) {return head;}ListNode cur = head;ListNode pre = null;while(cur != null) {ListNode next = cur.next;//当前节点的下一个指向前一个节点cur.next = pre;//pre向前移动pre = cur;//cur向前移动cur = next;}return pre;}
}

请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
实现 LRUCache 类：
LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。
函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

示例：
输入
[“LRUCache”, “put”, “put”, “get”, “put”, “get”, “put”, “get”, “get”, “get”]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]

解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1); // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2); // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1); // 返回 -1 (未找到)
lRUCache.get(3); // 返回 3
lRUCache.get(4); // 返回 4

提示：
1 <= capacity <= 3000
0 <= key <= 10000
0 <= value <= 105
最多调用 2 * 105 次 get 和 put

class LRUCache {private int capacity;private Map<Integer, Integer> map = new LinkedHashMap<>();public LRUCache(int capacity) {this.capacity = capacity;}public int get(int key) {if (map.containsKey(key)) {int val = map.get(key);map.remove(key);map.put(key,val);return val;}return -1;}public void put(int key, int value) {if (map.containsKey(key)) {map.remove(key);}else if (map.size() == capacity){Iterator<Map.Entry<Integer, Integer>> iterator = map.entrySet().iterator();iterator.next();iterator.remove();}map.put(key,value);}
}

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1:
输入: [3,2,1,5,6,4], k = 2
输出: 5

示例 2:
输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4

提示：
1 <= k <= nums.length <= 105
-104 <= nums[i] <= 104

import java.util.Collections;
class Solution {public int findKthLargest(int[] nums, int k) {quickSort(nums, 0, nums.length - 1);return nums[nums.length - k];}public void quickSort(int[] nums, int left, int right) {if(left < right) {int i = left, j = right;int baseNum = nums[left];while(i < j) {while(i < j && baseNum <= nums[j]) {j --;}nums[i] = nums[j];while(i < j && baseNum >= nums[i]) {i ++;}nums[j] = nums[i];}nums[i] = baseNum;quickSort(nums, left, i);quickSort(nums, i + 1, right);}}
}

给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。
k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

示例 1：
输入：head = [1,2,3,4,5], k = 2
输出：[2,1,4,3,5]

示例 2：
输入：head = [1,2,3,4,5], k = 3
输出：[3,2,1,4,5]

提示：
链表中的节点数目为 n
1 <= k <= n <= 5000
0 <= Node.val <= 1000

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode reverseKGroup(ListNode head, int k) {Deque<ListNode> stack = new ArrayDeque<>();ListNode dummy = new ListNode(0);ListNode p = dummy;while(true) {int count = 0;ListNode cur = head;while(cur != null && count < k) {stack.add(cur);cur = cur.next;count ++;}if(count != k) {p.next = head;break;}while(!stack.isEmpty()) {p.next = stack.pollLast();p = p.next;}p.next = cur;head = cur;}return dummy.next;}
}

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请
你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。

示例 1：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。

示例 2：
输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。

示例 3：
输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0

提示：
3 <= nums.length <= 3000
-105 <= nums[i] <= 105

class Solution {public List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> result = new ArrayList<>();Arrays.sort(nums);int lenght = nums.length;//数组大小小于3或者数组第一个数大于0，直接退出if(nums == null || lenght < 3 || nums[0] > 0) {return result;}for(int i=0; i<lenght; i++) {  //保证下一个数和前一个数不相同if(i > 0 && nums[i] == nums[i - 1]) {continue;}//从当前数字后一个数开始向后找int left = i + 1; //从最后一个数向前找int right = lenght - 1;while(left < right) {//三数之和int sum = nums[i] + nums[left] + nums[right];if(sum == 0) {result.add(Arrays.asList(nums[i], nums[left], nums[right]));//如果left后一个数和left相等，则向后移动一个。循环去重while(left < right && nums[left] == nums[left + 1]) {left ++;} //如果right的前一个和right相等，则向前移动一个。循环去重while(left < right && nums[right] == nums[right - 1]) {right --;}//left从移动之后的后一个开始left ++;right --;} else if(sum < 0) {//如果sum小于0，则往后移动，因为left后面的数字比left大left ++;} else {right --;}}}return result;}
}

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组 是数组中的一个连续部分。

示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

示例 2：
输入：nums = [1]
输出：1

示例 3：
输入：nums = [5,4,-1,7,8]
输出：23

提示：
1 <= nums.length <= 105
-104 <= nums[i] <= 104

class Solution {public int maxSubArray(int[] nums) {int n = nums.length;int[] dp = new int[n];dp[0] = nums[0];int maxSum = dp[0];for (int i = 1; i < n; i++) {dp[i] = Math.max(dp[i - 1], 0) + nums[i];maxSum = Math.max(maxSum, dp[i]);}return maxSum;}
}

给你一个整数数组 nums，请你将该数组升序排列。

示例 1：
输入：nums = [5,2,3,1]
输出：[1,2,3,5]

示例 2：
输入：nums = [5,1,1,2,0,0]
输出：[0,0,1,1,2,5]

提示：
1 <= nums.length <= 5 * 104
-5 * 104 <= nums[i] <= 5 * 104

//快速排序
class Solution {public int[] sortArray(int[] nums) {quickSort(nums, 0, nums.length - 1);return nums;}public void quickSort(int[] nums, int left, int right) {if(left < right) {int i = left, j = right;int baseNum = nums[left];while(i < j) {while(i < j && baseNum <= nums[j]) {j --;}nums[i] = nums[j];while(i < j && baseNum >= nums[i]) {i ++;}nums[j] = nums[i];}nums[i] = baseNum;quickSort(nums, left, i);quickSort(nums, i + 1, right);}}
}

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例 1：
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

示例 2：
输入：l1 = [], l2 = []
输出：[]

示例 3：
输入：l1 = [], l2 = [0]
输出：[0]

提示：
两个链表的节点数目范围是 [0, 50]
-100 <= Node.val <= 100
l1 和 l2 均按 非递减顺序 排列

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode mergeTwoLists(ListNode list1, ListNode list2) {ListNode newNode = new ListNode(-1);ListNode cur = newNode;while(list1 != null && list2 != null) {if(list1.val <= list2.val) {cur.next = list1;list1 = list1.next;} else {cur.next = list2;list2 = list2.next;}cur = cur.next;}cur.next = list1 == null ? list2 : list1;return newNode.next;}
}

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。

示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：
输入：nums = [3,2,4], target = 6
输出：[1,2]

示例 3：
输入：nums = [3,3], target = 6
输出：[0,1]

提示：
2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
只会存在一个有效答案

class Solution {public int[] twoSum(int[] nums, int target) {int[] result = new int[2];Map<Integer, Integer> map = new HashMap<>();for(int i=0; i<nums.length; i++) {int key = target - nums[i];if(map.containsKey(key)) {result[0] = map.get(key);result[1] = i;return result;} else {map.put(nums[i], i);}}return result;}
}

给你一个字符串 s，找到 s 中最长的回文子串。

如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

示例 1：
输入：s = “babad”
输出：“bab”
解释：“aba” 同样是符合题意的答案。

示例 2：
输入：s = “cbbd”
输出：“bb”

提示：
1 <= s.length <= 1000
s 仅由数字和英文字母组成

//暴力解法
public class Solution {public String longestPalindrome(String s) {int len = s.length();if (len < 2) {return s;}int maxLen = 1;int begin = 0;// s.charAt(i) 每次都会检查数组下标越界，因此先转换成字符数组char[] charArray = s.toCharArray();// 枚举所有长度大于 1 的子串 charArray[i..j]for (int i = 0; i < len - 1; i++) {for (int j = i + 1; j < len; j++) {if (j - i + 1 > maxLen && validPalindromic(charArray, i, j)) {maxLen = j - i + 1;begin = i;}}}return s.substring(begin, begin + maxLen);}/*** 验证子串 s[left..right] 是否为回文串*/private boolean validPalindromic(char[] charArray, int left, int right) {while (left < right) {if (charArray[left] != charArray[right]) {return false;}left++;right--;}return true;}
}//动态规划。
//状态转移方程 dp[i][j] = s[i] == s[j] and dp[i + 1][j - 1]
//边界 dp[i][i] = true;
public class Solution {public String longestPalindrome(String s) {// 特殊用例判断int len = s.length();if (len < 2) {return s;}int maxLen = 1;int begin = 0;// dp[i][j] 表示 s[i, j] 是否是回文串boolean[][] dp = new boolean[len][len];char[] charArray = s.toCharArray();for (int i = 0; i < len; i++) {dp[i][i] = true;}for (int j = 1; j < len; j++) {for (int i = 0; i < j; i++) {if (charArray[i] != charArray[j]) {dp[i][j] = false;} else {//j-1 - (i+1) + 1 < 2 => j - i < 3if (j - i < 3) {dp[i][j] = true;} else {dp[i][j] = dp[i + 1][j - 1];}}// 只要 dp[i][j] == true 成立，就表示子串 s[i..j] 是回文，此时记录回文长度和起始位置if (dp[i][j] && j - i + 1 > maxLen) {maxLen = j - i + 1;begin = i;}}}return s.substring(begin, begin + maxLen);}
}

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]

示例 2：
输入：root = [1]
输出：[[1]]

示例 3：
输入：root = []
输出：[]

提示：
树中节点数目在范围 [0, 2000] 内
-1000 <= Node.val <= 1000

/*** 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 List<List<Integer>> levelOrder(TreeNode root) {if(root == null) {return new ArrayList<>();}List<List<Integer>> result = new ArrayList<>();LinkedList<TreeNode> queue = new LinkedList<>();queue.add(root);while(!queue.isEmpty()) {List<Integer> tempList = new ArrayList<>();//因为queue里的元素会变化，所以不能直接放到for循环里int size = queue.size();//原先队列有几个元素，就循环几次for(int i=0; i<size; i++) {TreeNode node  = queue.remove();tempList.add(node.val);if(node.left != null) {queue.add(node.left);}if(node.right != null) {queue.add(node.right);}}result.add(tempList);}return result;}
}

整数数组 nums 按升序排列，数组中的值 互不相同 。
在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。
给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

示例 1：
输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4

示例 2：
输入：nums = [4,5,6,7,0,1,2], target = 3
输出：-1

示例 3：
输入：nums = [1], target = 0
输出：-1

提示：
1 <= nums.length <= 5000
-104 <= nums[i] <= 104
nums 中的每个值都 独一无二
题目数据保证 nums 在预先未知的某个下标上进行了旋转
-104 <= target <= 104

public int search(int[] nums, int target) {if (nums == null || nums.length == 0) {return -1;}int start = 0;int end = nums.length - 1;int mid;while (start <= end) {mid = start + (end - start) / 2;if (nums[mid] == target) {return mid;}//前半部分有序,注意此处用小于等于if (nums[start] <= nums[mid]) {//target在前半部分if (target >= nums[start] && target < nums[mid]) {end = mid - 1;} else {start = mid + 1;}} else {if (target <= nums[end] && target > nums[mid]) {start = mid + 1;} else {end = mid - 1;}}}return -1;}

给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。

示例 1：
输入：grid = [
[“1”,“1”,“1”,“1”,“0”],
[“1”,“1”,“0”,“1”,“0”],
[“1”,“1”,“0”,“0”,“0”],
[“0”,“0”,“0”,“0”,“0”]
]
输出：1

示例 2：
输入：grid = [
[“1”,“1”,“0”,“0”,“0”],
[“1”,“1”,“0”,“0”,“0”],
[“0”,“0”,“1”,“0”,“0”],
[“0”,“0”,“0”,“1”,“1”]
]
输出：3

提示：
m == grid.length
n == grid[i].length
1 <= m, n <= 300
grid[i][j] 的值为 ‘0’ 或 ‘1’

class Solution {public int numIslands(char[][] grid) {int rows = grid.length;int cols = grid[0].length;int islandNum = 0;for(int r=0; r<rows; r++) {for(int c=0; c<cols; c++) {if(grid[r][c] == '1') {islandNum ++;dfs(grid, r, c);}}}return islandNum;}public void dfs(char[][] grid, int r, int c) {int rows = grid.length;int cols = grid[0].length;if(r >= rows || c >= cols || r < 0 || c < 0 || grid[r][c] == '0') {return;}grid[r][c] = '0';dfs(grid, r -1, c);dfs(grid, r + 1, c);dfs(grid, r, c + 1);dfs(grid, r, c - 1);}
}

给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。

示例 1：
输入：s = “()”
输出：true

示例 2：
输入：s = “()[]{}”
输出：true

示例 3：
输入：s = “(]”
输出：false

提示：
1 <= s.length <= 104
s 仅由括号 ‘()[]{}’ 组成

class Solution {public boolean isValid(String s) {if(s == null || "".equals(s)) {return false;}Deque<Character> stack = new LinkedList<>();for(int i=0; i<s.length(); i++) {char c = s.charAt(i);if(c == '(') {stack.push(')');} else if(c == '{') {stack.push('}');} else if(c == '[') {stack.push(']');} else if(stack.isEmpty() || stack.peek() != c) {//如果第一个是右括号，或者栈顶的右括号和现在的右括号不匹配return false;} else {//有括号匹配的情况stack.pop();}}return stack.isEmpty();}
}

给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 true 。 否则，返回 false 。

示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：
输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：
输入：head = [1], pos = -1
输出：false
解释：链表中没有环。

提示：
链表中节点的数目范围是 [0, 104]
-105 <= Node.val <= 105
pos 为 -1 或者链表中的一个 有效索引 。

//set解法
public class Solution {public boolean hasCycle(ListNode head) {Set<ListNode> set = new HashSet<>();ListNode cur = head;while(cur != null) {if(!set.contains(cur)) {set.add(cur);} else {return true;}cur = cur.next;}return false;}
}//快慢指针解法
public class Solution {public boolean hasCycle(ListNode head) {if(head == null || head.next == null) {return false;}ListNode fast = head.next;ListNode slow = head;while(fast != slow) {if(fast == null || fast.next == null) {return false;}slow = slow.next;fast = fast.next.next;}return true;}
}

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

示例 1：
输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

示例 2：
输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 没有交易完成, 所以最大利润为 0。

提示：
1 <= prices.length <= 105
0 <= prices[i] <= 104

class Solution {public int maxProfit(int[] prices) {int min = prices[0];int maxDiff = 0;for(int i=1; i<prices.length; i++) {if(prices[i] < min) {min = prices[i];} else if(prices[i] - min > maxDiff) {maxDiff = prices[i] - min;}}return maxDiff;}
}

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1：
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2：
输入：nums = [0,1]
输出：[[0,1],[1,0]]

示例 3：
输入：nums = [1]
输出：[[1]]

提示：
1 <= nums.length <= 6
-10 <= nums[i] <= 10
nums 中的所有整数 互不相同

class Solution {public List<List<Integer>> permute(int[] nums) {List<List<Integer>> result = new ArrayList<>();boolean[] visitedArr = new boolean[nums.length];backtrace(result, nums, new ArrayList<>(), visitedArr);return result; }private void backtrace(List<List<Integer>> result, int[] nums, List<Integer> tempList, boolean[] visitedArr) {if(tempList.size() == nums.length) {result.add(new ArrayList<>(tempList));return;}for(int i=0; i<nums.length; i++) {if(visitedArr[i]) {continue;}tempList.add(nums[i]);visitedArr[i] = true;backtrace(result, nums, tempList, visitedArr);visitedArr[i] = false;tempList.remove(tempList.size() - 1);}}
}

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

示例 1：
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。

示例 2：
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出：5
解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。

示例 3：
输入：root = [1,2], p = 1, q = 2
输出：1

提示：
树中节点数目在范围 [2, 105] 内。
-109 <= Node.val <= 109
所有 Node.val 互不相同 。
p != q
p 和 q 均存在于给定的二叉树中。

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode(int x) { val = x; }* }*/
class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if(root == null || root == p || root == q) {return root;}TreeNode left = lowestCommonAncestor(root.left, p, q);TreeNode right = lowestCommonAncestor(root.right, p, q);if(left == null) {return right;}if(right == null) {return left;}return root;}
}

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

示例 1：
输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]
解释：需要合并 [1,2,3] 和 [2,5,6] 。
合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。

示例 2：
输入：nums1 = [1], m = 1, nums2 = [], n = 0
输出：[1]
解释：需要合并 [1] 和 [] 。
合并结果是 [1] 。

示例 3：
输入：nums1 = [0], m = 0, nums2 = [1], n = 1
输出：[1]
解释：需要合并的数组是 [] 和 [1] 。
合并结果是 [1] 。
注意，因为 m = 0 ，所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。

提示：
nums1.length == m + n
nums2.length == n
0 <= m, n <= 200
1 <= m + n <= 200
-109 <= nums1[i], nums2[j] <= 109

class Solution {public void merge(int[] nums1, int m, int[] nums2, int n) {int i = m - 1;int j = n - 1;int index = nums1.length - 1;while(i >= 0 && j >= 0) {if(nums1[i] >= nums2[j]) {nums1[index--] = nums1[i--];} else {nums1[index--] = nums2[j--];}}while(i >= 0) {nums1[index--] = nums1[i--];}while(j >= 0) {nums1[index--] = nums2[j--];}}
}

给你一个字符串 s ，请你反转字符串中 单词 的顺序。
单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。
返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。

注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。

示例 1：
输入：s = “the sky is blue”
输出：“blue is sky the”

示例 2：
输入：s = " hello world "
输出：“world hello”
解释：反转后的字符串中不能存在前导空格和尾随空格。

示例 3：
输入：s = “a good example”
输出：“example good a”
解释：如果两个单词间有多余的空格，反转后的字符串需要将单词间的空格减少到仅有一个。

提示：
1 <= s.length <= 104
s 包含英文大小写字母、数字和空格 ’ ’
s 中 至少存在一个 单词

class Solution {public String reverseWords(String s) {List<String> strList = Arrays.stream(s.split(" ")).filter(str -> !str.equals("") && !str.equals(" ")).map(String::trim).collect(Collectors.toList());Collections.reverse(strList);return String.join(" ", strList);}
}

给你一个二叉树的根节点 root ， 检查它是否轴对称。

示例 1：
输入：root = [1,2,2,3,4,4,3]
输出：true

示例 2：
输入：root = [1,2,2,null,3,null,3]
输出：false

提示：
树中节点数目在范围 [1, 1000] 内
-100 <= Node.val <= 100

/*** 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 isSymmetric(root.left, root.right);}private boolean isSymmetric(TreeNode leftNode, TreeNode rightNode) {if(leftNode == null && rightNode == null) {return true;}if(leftNode  == null || rightNode == null || leftNode.val != rightNode.val) {return false;}//左左子节点的val和右右子节点的val相等，且左右子节点的val等于右左子节点的val，则是对称二叉树return isSymmetric(leftNode.left, rightNode.right) && isSymmetric(leftNode.right, rightNode.left);}
}

给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。

示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：true

示例 2：
输入：root = [1,2,2,3,3,null,null,4,4]
输出：false

示例 3：
输入：root = []
输出：true

提示：
树中的节点数在范围 [0, 5000] 内
-104 <= Node.val <= 104

/*** 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 isBalanced(TreeNode root) {if(root == null) {return true;}return Math.abs(getDepth(root.left) - getDepth(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);}private int getDepth(TreeNode root) {if(root == null) {return 0;}return Math.max(getDepth(root.left), getDepth(root.right)) + 1;}
}

给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

示例 1：
输入：root = [1,null,2,3]
输出：[1,2,3]

示例 2：
输入：root = []
输出：[]

示例 3：
输入：root = [1]
输出：[1]

示例 4：
输入：root = [1,2]
输出：[1,2]

示例 5：
输入：root = [1,null,2]
输出：[1,2]

提示：
树中节点数目在范围 [0, 100] 内
-100 <= Node.val <= 100

/*** 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 {private List<Integer> resultList = new ArrayList<>();public List<Integer> preorderTraversal(TreeNode root) {if(root == null) {return resultList;}resultList.add(root.val);resultList = preorderTraversal(root.left);resultList = preorderTraversal(root.right);return resultList;}
}

给定一个二叉树 root ，返回其最大深度。
二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：3

示例 2：
输入：root = [1,null,2]
输出：2

提示：
树中节点的数量在 [0, 104] 区间内。
-100 <= Node.val <= 100

/*** 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 int maxDepth(TreeNode root) {if(root == null) {return 0;}return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;}
}

给你一个二叉树的根节点 root ，树中每个节点都存放有一个 0 到 9 之间的数字。
每条从根节点到叶节点的路径都代表一个数字：
例如，从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123 。
计算从根节点到叶节点生成的 所有数字之和 。
叶节点 是指没有子节点的节点。

示例 1：
输入：root = [1,2,3]
输出：25
解释：
从根到叶子节点路径 1->2 代表数字 12
从根到叶子节点路径 1->3 代表数字 13
因此，数字总和 = 12 + 13 = 25

示例 2：
输入：root = [4,9,0,5,1]
输出：1026
解释：
从根到叶子节点路径 4->9->5 代表数字 495
从根到叶子节点路径 4->9->1 代表数字 491
从根到叶子节点路径 4->0 代表数字 40
因此，数字总和 = 495 + 491 + 40 = 1026

提示：
树中节点的数目在范围 [1, 1000] 内
0 <= Node.val <= 9
树的深度不超过 10

/*** 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 int sumNumbers(TreeNode root) {return dfs(root, 0);}private int dfs(TreeNode root, int prevSum) {if(root == null) {return 0;}int sum = prevSum * 10 + root.val;if(root.left == null && root.right == null) {return sum;} else {return dfs(root.left, sum) + dfs(root.right, sum);}}
}

给你一棵二叉树的根节点，返回该树的 直径 。
二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。
两节点之间路径的 长度 由它们之间边数表示。

示例 1：
输入：root = [1,2,3,4,5]
输出：3
解释：3 ，取路径 [4,2,1,3] 或 [5,2,1,3] 的长度。

示例 2：
输入：root = [1,2]
输出：1

提示：
树中节点数目在范围 [1, 104] 内
-100 <= Node.val <= 100

/*** 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 {int ans;public int diameterOfBinaryTree(TreeNode root) {ans = 1;dfs(root);// 返回最大直径（减去1是因为题目定义的直径是边的数量）return ans - 1;}private int dfs(TreeNode root) {if(root == null) {return 0;}int leftDepth = dfs(root.left);int rightDepth = dfs(root.right);ans = Math.max(ans, leftDepth + rightDepth + 1);return Math.max(leftDepth, rightDepth) + 1;}
}

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下：
节点的左子树只包含 小于 当前节点的数。
节点的右子树只包含 大于 当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

示例 1：
输入：root = [2,1,3]
输出：true

示例 2：
输入：root = [5,1,4,null,null,3,6]
输出：false
解释：根节点的值是 5 ，但是右子节点的值是 4 。

提示：
树中节点数目范围在[1, 104] 内
-231 <= Node.val <= 231 - 1

/*** 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 dfs(root, Long.MIN_VALUE, Long.MAX_VALUE);}private boolean dfs(TreeNode root, long min, long max) {if(root == null) {return true;}if(root.val <= min || root.val >= max) {return false;}return dfs(root.left, min, root.val) && dfs(root.right, root.val, max);}
}

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。
你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。

示例 1：
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[[7,4,1],[8,5,2],[9,6,3]]

示例 2：
输入：matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
输出：[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]

提示：
n == matrix.length == matrix[i].length
1 <= n <= 20
-1000 <= matrix[i][j] <= 1000

class Solution {public void rotate(int[][] matrix) {int m = matrix.length, n = matrix[0].length;for(int i=0; i<m; i++) {for(int j=0; j<i; j++) {int temp = matrix[i][j];matrix[i][j] = matrix[j][i];matrix[j][i] = temp;}}int left = 0;int right = m - 1;while(left < right) {for(int i=0; i<m; i++) {int temp = matrix[i][left];matrix[i][left] = matrix[i][right];matrix[i][right] = temp;}left ++;right --;}}
}

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
对于给定的输入，保证和为 target 的不同组合数少于 150 个。

示例 1：
输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。

示例 2：
输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]

示例 3：
输入: candidates = [2], target = 1
输出: []

提示：
1 <= candidates.length <= 30
2 <= candidates[i] <= 40
candidates 的所有元素 互不相同
1 <= target <= 40

class Solution {private List<List<Integer>> resultList = new ArrayList<>();public List<List<Integer>> combinationSum(int[] candidates, int target) {LinkedList<Integer> combine = new LinkedList<Integer>();dfs(candidates, 0, target, combine);return resultList;}private void dfs(int[] candidates, int index, int target, LinkedList<Integer> pathList) {if(candidates.length == index) {return;}if (target == 0) {resultList.add(new ArrayList<Integer>(pathList));return;}//直接跳过dfs(candidates, index + 1, target, pathList);if(target - candidates[index] < 0) {return;}// 选择当前数pathList.add(candidates[index]);dfs(candidates, index, target - candidates[index], pathList);pathList.pollLast();}
}

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。

示例 1：
输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。

示例 2：
输入：grid = [[1,2,3],[4,5,6]]
输出：12

提示：
m == grid.length
n == grid[i].length
1 <= m, n <= 200
0 <= grid[i][j] <= 200

class Solution {public int minPathSum(int[][] grid) {int m = grid.length;   // 获取矩阵的行数int n = grid[0].length;   // 获取矩阵的列数int[][] dp = new int[m][n];   // 创建一个与矩阵大小相同的二维数组，用于存储最小路径和// 遍历整个矩阵计算最小路径和for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (i == 0 && j == 0) {   // 如果是起点位置dp[i][j] = grid[i][j];   // 最小路径和就是起点的值} else if (i > 0 && j > 0) {   // 如果不是第一行和第一列的位置dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];// 当前位置的最小路径和等于上方格子和左方格子的最小路径和中较小的那个值加上当前位置的值} else if (i > 0) {   // 如果是第一列的位置dp[i][j] = dp[i - 1][j] + grid[i][j];// 当前位置的最小路径和等于上方格子的最小路径和加上当前位置的值} else if (j > 0) {   // 如果是第一行的位置dp[i][j] = dp[i][j - 1] + grid[i][j];// 当前位置的最小路径和等于左方格子的最小路径和加上当前位置的值}}}return dp[m - 1][n - 1];   // 返回右下角位置的最小路径和作为结果}
}

给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
叶子节点 是指没有子节点的节点。

示例 1：
输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：[[5,4,11,2],[5,8,4,5]]

示例 2：
输入：root = [1,2,3], targetSum = 5
输出：[]

示例 3：
输入：root = [1,2], targetSum = 0
输出：[]

提示：
树中节点总数在范围 [0, 5000] 内
-1000 <= Node.val <= 1000
-1000 <= targetSum <= 1000

/*** 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 {private List<List<Integer>> resultList = new ArrayList<>();LinkedList<Integer> pathList = new LinkedList<>();public List<List<Integer>> pathSum(TreeNode root, int targetSum) {dfs(root, targetSum);return resultList;}private void dfs(TreeNode root, int targetSum) {if(root == null) {return;}targetSum -= root.val;pathList.add(root.val);if(root.left == null && root.right == null && targetSum == 0) {resultList.add(new ArrayList<>(pathList));}dfs(root.left, targetSum);dfs(root.right, targetSum);//回溯，删叶子节点的值pathList.pollLast();}
}

给定方法 rand7 可生成 [1,7] 范围内的均匀随机整数，试写一个方法 rand10 生成 [1,10] 范围内的均匀随机整数。
你只能调用 rand7() 且不能调用其他方法。请不要使用系统的 Math.random() 方法。
每个测试用例将有一个内部参数 n，即你实现的函数 rand10() 在测试时将被调用的次数。请注意，这不是传递给 rand10() 的参数。

示例 1:
输入: 1
输出: [2]

示例 2:
输入: 2
输出: [2,8]

示例 3:
输入: 3
输出: [3,8,10]

提示:
1 <= n <= 105

class Solution extends SolBase {public int rand10() {int num;do {int row = Rand7();int col = Rand7();        num = (row - 1) * 7 + col; // 将二维坐标转换为一维坐标            } while (num > 40); // 如果生成的数大于40，则重新生成        return (num % 10) + 1; // 将数映射到 [1, 10] 范围内}
}

给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

示例 1：
输入：s = “3[a]2[bc]”
输出：“aaabcbc”

示例 2：
输入：s = “3[a2[c]]”
输出：“accaccacc”

示例 3：
输入：s = “2[abc]3[cd]ef”
输出：“abcabccdcdcdef”

示例 4：
输入：s = “abc3[cd]xyz”
输出：“abccdcdcdxyz”

提示：
1 <= s.length <= 30
s 由小写英文字母、数字和方括号 ‘[]’ 组成
s 保证是一个 有效 的输入。
s 中所有整数的取值范围为 [1, 300]

class Solution {int index = 0;public String decodeString(String s) {if(s == null || s == "") {return "";}Stack<String> stack = new Stack<>(); while(index < s.length()) {char c = s.charAt(index);if(Character.isDigit(c)) {StringBuilder sb = new StringBuilder();while(Character.isDigit(s.charAt(index))) {sb.append(String.valueOf(s.charAt(index ++)));}stack.push(sb.toString());}else if(Character.isLetter(c) || c == '[') {stack.push(String.valueOf(s.charAt(index ++)));} else {index ++;LinkedList<String> subList = new LinkedList<String>();while(!"[".equals(stack.peek())) {subList.addLast(stack.pop());}Collections.reverse(subList);// 左括号出栈stack.pop();// 此时栈顶为当前 subList 对应的字符串应该出现的次数int repTime = Integer.parseInt(stack.pop());StringBuffer sb = new StringBuffer();String subStr = String.join("", subList);while(repTime -- > 0) {sb.append(subStr);}stack.push(sb.toString());}}return String.join("", stack);}
}

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

示例 1：
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]

示例 2：
输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]

示例 3：
输入：nums = [], target = 0
输出：[-1,-1]

提示：
0 <= nums.length <= 105
-109 <= nums[i] <= 109
nums 是一个非递减数组
-109 <= target <= 109

class Solution {public int[] searchRange(int[] nums, int target) {if(nums == null || nums.length == 0) {return new int[]{-1, -1};}LinkedList<Integer> list = new LinkedList<>();for(int i=0; i<nums.length; i++) {if(nums[i] == target) {list.add(i);}}if(list.size() == 0) {return new int[]{-1, -1};}return new int[]{list.get(0), list.get(list.size() - 1)};}
}

在一个由 ‘0’ 和 ‘1’ 组成的二维矩阵内，找到只包含 ‘1’ 的最大正方形，并返回其面积。

示例 1：
输入：matrix = [[“1”,“0”,“1”,“0”,“0”],[“1”,“0”,“1”,“1”,“1”],[“1”,“1”,“1”,“1”,“1”],[“1”,“0”,“0”,“1”,“0”]]
输出：4

示例 2：
输入：matrix = [[“0”,“1”],[“1”,“0”]]
输出：1

示例 3：
输入：matrix = [[“0”]]
输出：0

提示：
m == matrix.length
n == matrix[i].length
1 <= m, n <= 300
matrix[i][j] 为 ‘0’ 或 ‘1’

class Solution {public int maximalSquare(char[][] matrix) {int maxSide = 0;if(matrix == null || matrix.length == 0 || matrix[0].length == 0) {return maxSide;}int rows = matrix.length, cols = matrix[0].length;int[][] dp = new int[rows][cols];for(int i=0; i<rows; i++) {for(int j=0; j<cols; j++) {if(matrix[i][j] == '1') {if(i == 0 || j == 0) {dp[i][j] = 1;} else {dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;}maxSide = Math.max(maxSide, dp[i][j]);}}}return maxSide * maxSide;}
}

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：
每行的元素从左到右升序排列。
每列的元素从上到下升序排列。

示例 1：
输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
输出：true

示例 2：
输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20
输出：false

提示：
m == matrix.length
n == matrix[i].length
1 <= n, m <= 300
-109 <= matrix[i][j] <= 109
每行的所有元素从左到右升序排列
每列的所有元素从上到下升序排列
-109 <= target <= 109

class Solution {public boolean searchMatrix(int[][] matrix, int target) {if(matrix == null || matrix.length == 0) {return false;}int m = 0;int n = matrix[0].length - 1;while(m < matrix.length && n >= 0) {if(matrix[m][n] == target) {return true;} else if(matrix[m][n] > target) {n --;} else {m ++;}}return false;}
}

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

示例 1：
输入：head = [1,2,2,1]
输出：true

示例 2：
输入：head = [1,2]
输出：false

提示：
链表中节点数目在范围[1, 105] 内
0 <= Node.val <= 9

class Solution {public boolean isPalindrome(ListNode head) {ListNode cur = head;StringBuilder sb = new StringBuilder();while(cur != null) {sb.append(cur.val);cur = cur.next;}    return sb.toString().equals(sb.reverse().toString());}
}

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。
叶子节点 是指没有子节点的节点。

示例 1：
输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出：true
解释：等于目标和的根节点到叶节点路径如上图所示。

示例 2：
输入：root = [1,2,3], targetSum = 5
输出：false
解释：树中存在两条根节点到叶子节点的路径：
(1 --> 2): 和为 3
(1 --> 3): 和为 4
不存在 sum = 5 的根节点到叶子节点的路径。

示例 3：
输入：root = [], targetSum = 0
输出：false
解释：由于树是空的，所以不存在根节点到叶子节点的路径。

提示：
树中节点的数目在范围 [0, 5000] 内
-1000 <= Node.val <= 1000
-1000 <= targetSum <= 1000

/*** 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 hasPathSum(TreeNode root, int targetSum) {return dfs(root, targetSum);}private boolean dfs(TreeNode node, int targetSum) {if(node == null) {return false;}if(node.left == null && node.right == null && targetSum - node.val == 0) {return true;}return dfs(node.left, targetSum - node.val) || dfs(node.right, targetSum - node.val);}
}

峰值元素是指其值严格大于左右相邻值的元素。
给你一个整数数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。
你可以假设 nums[-1] = nums[n] = -∞ 。
你必须实现时间复杂度为 O(log n) 的算法来解决此问题。

示例 1：
输入：nums = [1,2,3,1]
输出：2
解释：3 是峰值元素，你的函数应该返回其索引 2。

示例 2：
输入：nums = [1,2,1,3,5,6,4]
输出：1 或 5
解释：你的函数可以返回索引 1，其峰值元素为 2；或者返回索引 5， 其峰值元素为 6。

提示：
1 <= nums.length <= 1000
-231 <= nums[i] <= 231 - 1
对于所有有效的 i 都有 nums[i] != nums[i + 1]

class Solution {public int findPeakElement(int[] nums) {int left = 0, right = nums.length - 1;while(left < right) {int mid = (left + right) / 2;if(nums[mid] > nums[mid + 1]) {right = mid;} else {left = mid + 1;}}return left;}
}