public ListNode detectCycle(ListNode head) {
ListNode pos = head;
HashSet<ListNode> set = new HashSet<>();
while (pos != null){
if (set.contains(pos)){
return pos;
}else {
set.add(pos);
}
pos = pos.next;
}
return null;
}
public ListNode sortList(ListNode head) {
if (head == null || head.next == null){
return head;
}
ListNode fast = head.next;
ListNode slow = head;
while (fast != null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
}
ListNode tmp = slow.next;
slow.next = null;
ListNode left = sortList(head);
ListNode right = sortList(tmp);
ListNode h = new ListNode(0);
ListNode res = h;
while (left != null && right != null){
if (left.val < right.val){
h.next = left;
left = left.next;
}else {
h.next = right;
right = right.next;
}
h = h.next;
}
h.next = left != null ? left : right;
return res.next;
}
private Stack<Integer> stack;
private Stack<Integer> minStack;
public MinStack() {
stack = new Stack<>();
minStack = new Stack<>();
}
public void push(int val) {
stack.push(val);
if (minStack.empty()){
minStack.push(val);
}else {
int top = minStack.peek();
if (val <= top){
minStack.push(val);
}
}
}
public void pop() {
int val = stack.pop();
if (!minStack.empty()){
int top = minStack.peek();
if (val == top){
minStack.pop();
}
}
}
public int top() {
if (stack.empty()){
return -1;
}else {
return stack.peek();
}
}
public int getMin() {
if (minStack.empty()){
return -1;
}else {
return minStack.peek();
}
}
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
HashSet<ListNode> set = new HashSet<>();
ListNode tmp = headA;
while (tmp != null){
set.add(tmp);
tmp = tmp.next;
}
tmp = headB;
while (tmp != null){
if (set.contains(tmp)){
return tmp;
}
tmp = tmp.next;
}
return null;
}
private int[] memo;
public int rob(int[] nums){
memo = new int[nums.length];
Arrays.fill(memo,-1);
return dp(nums,0);
}
private int dp(int[] nums, int i) {
if (i >= nums.length){
return 0;
}
if (memo[i] != -1){
return memo[i];
}
int res = Math.max(dp(nums,i+1),nums[i] + dp(nums,i+2));
memo[i] = res;
return res;
}
public int numIslands(char[][] grid) {
int res = 0;
int m = grid.length,n = grid[0].length;
for (int i = 0; i < m; i++){
for (int j = 0; j < n; j++){
if (grid[i][j] == '1'){
res++;
dfs(grid,i,j);
}
}
}
return res;
}
private void dfs(char[][] grid, int i, int j) {
int m = grid.length,n = grid[0].length;
if (i < 0 || j < 0 || i >= m || j >= n){
return;
}
if (grid[i][j] == '0'){
return;
}
grid[i][j] = '0';
dfs(grid,i+1,j);
dfs(grid,i,j+1);
dfs(grid,i-1,j);
dfs(grid,i,j-1);
}
public ListNode reverseList(ListNode head) {
ListNode pre = null;
ListNode cur = head;
while (cur != null){
ListNode curNext = cur.next;
cur.next = pre;
pre = cur;
cur = curNext;
}
return pre;
}
public int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> pq = new PriorityQueue<>();
for (int e : nums){
pq.offer(e);
if (pq.size() > k){
pq.poll();
}
}
return pq.peek();
}v
public int maximalSquare(char[][] matrix) {
int m = matrix.length, n = matrix[0].length;
int[][] dp = new int[m][n];
for (int i = 0; i < m; i++){
dp[i][0] = matrix[i][0] - '0';
}
for (int j = 0; j < n; j++){
dp[0][j] = matrix[0][j] - '0';
}
for (int i = 1; i < m; i++){
for (int j = 1; j < n; j++){
if (matrix[i][j] == '0'){
continue;
}
dp[i][j] = Math.min(Math.min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1]) + 1;
}
}
int len = 0;
for (int i = 0; i < m; i++){
for (int j = 0; j < n; j++){
len = Math.max(len,dp[i][j]);
}
}
return len*len;
}
// 定义：将以 root 为根的这棵二叉树翻转，返回翻转后的二叉树的根节点
TreeNode invertTree(TreeNode root) {
if (root == null) {
return null;
}
// 利用函数定义，先翻转左右子树
TreeNode left = invertTree(root.left);
TreeNode right = invertTree(root.right);
// 然后交换左右子节点
root.left = right;
root.right = left;
// 和定义逻辑自恰：以 root 为根的这棵二叉树已经被翻转，返回 root
return root;
}
public boolean isPalindrome(ListNode head) {
ListNode slow,fast;
slow = fast = head;
while (fast != null && fast.next != null){
slow = slow.next;
fast = fast.next.next;
}
if (fast != null){
slow = slow.next;
}
ListNode left = head;
ListNode right = reverse(slow);
while (right != null){
if (left.val != right.val){
return false;
}
left = left.next;
right = right.next;
}
return true;
}
private ListNode reverse(ListNode head) {
ListNode pre = null;
ListNode cur = head;
while (cur != null){
ListNode curNext = cur.next;
cur.next = pre;
pre = cur;
cur = curNext;
}
return pre;
}?
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null){
return null;
}
if (root == p || root == q){
return root;
}
TreeNode left = lowestCommonAncestor(root.left,p,q);
TreeNode right = lowestCommonAncestor(root.right,p,q);
if (left != null && right !=null){
return root;
}
if (left == null && right == null){
return null;
}
return left == null ? right : left;
}
public int[] productExceptSelf(int[] nums) {
int n = nums.length;
//从左到右的前缀积
int[] prefix = new int[n];
prefix[0] = nums[0];
for (int i = 1; i < nums.length; i++){
prefix[i] = prefix[i-1] * nums[i];
}
//从右到左的前缀积
int[] suffix = new int[n];
suffix[n-1] = nums[n-1];
for (int i = n - 2; i >= 0; i--){
suffix[i] = suffix[i+1] * nums[i];
}
int[] res = new int[n];
res[0] = suffix[1];
res[n-1] = prefix[n-2];
for (int i = 1; i < n - 1; i++){
res[i] = prefix[i-1] * suffix[i+1];
}
return res;
}
?
LinkedList<Integer> q = new LinkedList<>();
public void push(int n){
//将小于n的元素全部删除
while (!q.isEmpty() && q.getLast() < n){
q.pollLast();
}
//将n加入尾部
q.addLast(n);
}
public int max(){
return q.getFirst();
}
public void pop(int n){
if (n == q.getFirst()){
q.pollFirst();
}
}
}
public int[] maxSlidingWindow(int[] nums, int k) {
SingQueue window = new SingQueue();
List<Integer> res = new ArrayList<>();
for (int i = 0; i < nums.length; i++){
if (i < k - 1){
//填满窗口的前k-1
window.push(nums[i]);
}else {
//窗口向前滑动，加入数字
window.push(nums[i]);
res.add(window.max());
window.pop(nums[i-k+1]);
}
}
int[] arr = new int[res.size()];
for (int i = 0; i < res.size(); i++){
arr[i] = res.get(i);
}
return arr;
}
public int numSquares(int n) {
int[] f = new int[n+1];
for (int i = 1; i <= n; i++){
int minn = Integer.MAX_VALUE;
for (int j = 1; j * j <= i; j++){
minn = Math.min(minn,f[i - j*j]);
}
f[i] = minn + 1;
}
return f[n];
}
public void moveZeroes(int[] nums) {
// 去除 nums 中的所有 0
// 返回去除 0 之后的数组长度
int p = removeElement(nums, 0);
// 将 p 之后的所有元素赋值为 0
for (; p < nums.length; p++) {
nums[p] = 0;
}
}
// 双指针技巧，复用 [27. 移除元素] 的解法。
int removeElement(int[] nums, int val) {
int fast = 0, slow = 0;
while (fast < nums.length) {
if (nums[fast] != val) {
nums[slow] = nums[fast];
slow++;
}
fast++;
}
return slow;
}
public int lengthOfLIS(int[] nums) {
int[] dp = new int[nums.length];
Arrays.fill(dp,1);
for (int i = 0; i < nums.length; i++){
for (int j = 0; j < i; j++){
if (nums[i] > nums[j]){
dp[i] = Math.max(dp[i],dp[j] + 1);
}
}
}
int res = 0;
for (int i = 0; i < dp.length; i++){
res = Math.max(res,dp[i]);
}
return res;
}
public int maxProfit(int[] prices) {
int n = prices.length;
int[][] dp = new int[n][2];
for (int i = 0; i < n; i++) {
if (i - 1 == -1) {
// base case 1
dp[i][0] = 0;
dp[i][1] = -prices[i];
continue;
}
if (i - 2 == -1) {
// base case 2
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
// i - 2 小于 0 时根据状态转移方程推出对应 base case
dp[i][1] = Math.max(dp[i - 1][1], -prices[i]);
// dp[i][1]
// = max(dp[i-1][1], dp[-1][0] - prices[i])
// = max(dp[i-1][1], 0 - prices[i])
// = max(dp[i-1][1], -prices[i])
continue;
}
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
dp[i][1] = Math.max(dp[i - 1][1], dp[i - 2][0] - prices[i]);
}
return dp[n - 1][0];
}
public int maxCoins(int[] nums) {
int n = nums.length;
// 添加两侧的虚拟气球
int[] points = new int[n + 2];
points[0] = points[n + 1] = 1;
for (int i = 1; i <= n; i++) {
points[i] = nums[i - 1];
}
// base case 已经都被初始化为 0
int[][] dp = new int[n + 2][n + 2];
// 开始状态转移
// i 应该从下往上
for (int i = n; i >= 0; i--) {
// j 应该从左往右
for (int j = i + 1; j < n + 2; j++) {
// 最后戳破的气球是哪个？
for (int k = i + 1; k < j; k++) {
// 择优做选择
dp[i][j] = Math.max(
dp[i][j],
dp[i][k] + dp[k][j] + points[i] * points[j] * points[k]
);
}
}
}
return dp[0][n + 1];
}
int[] memo;
public int coinChange(int[] coins, int amount) {
memo = new int[amount+1];
Arrays.fill(memo,-2);
return dp(coins,amount);
}
private int dp(int[] coins, int amount) {
if (amount == 0){
return 0;
}
if (amount < 0){
return -1;
}
if (memo[amount] != -2){
return memo[amount];
}
int res = Integer.MAX_VALUE;
for (int coin : coins){
int subProblen = dp(coins,amount-coin);
if (subProblen == -1){
continue;
}
res = Math.min(res,subProblen+1);
}
memo[amount] = (res == Integer.MAX_VALUE) ? -1 : res;
return memo[amount];
}
HashMap<TreeNode,Integer> memo = new HashMap<>();
public int rob(TreeNode root) {
if (root == null){
return 0;
}
if (memo.containsKey(root)){
return memo.get(root);
}
int do_it = root.val + (root.left == null ? 0 : rob(root.left.left) + rob(root.left.right)) +
(root.right == null ? 0 : rob(root.right.left) + rob(root.right.right));
int not_it = rob(root.left) + rob(root.right);
int res = Math.max(do_it,not_it);
memo.put(root,res);
return res;
}
public int[] countBits(int n) {
int[] bits = new int[n+1];
for (int i = 0; i <= n; i++){
bits[i] = countOne(i);
}
return bits;
}
private int countOne(int x) {
int ones = 0;
while (x > 0){
x &= (x-1);
ones++;
}
return ones;
}
public int[] topKFrequent(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int num : nums) {
map.put(num, map.getOrDefault(num, 0) + 1);
}
// int[] 的第一个元素代表数组的值，第二个元素代表了该值出现的次数
PriorityQueue<int[]> queue = new PriorityQueue<int[]>(new Comparator<int[]>() {
public int compare(int[] m, int[] n) {
return m[1] - n[1];
}
});
for (Map.Entry<Integer,Integer> entry : map.entrySet()){
int num = entry.getKey(),count = entry.getValue();
if (queue.size() == k){
if (queue.peek()[1] < count){
queue.poll();
queue.offer(new int[]{num,count});
}
}else {
queue.offer(new int[]{num,count});
}
}
int[] ret = new int[k];
for (int i = 0; i < k; i++){
ret[i] = queue.poll()[0];
}
return ret;
}
public String decodeString(String s) {
StringBuilder sb = new StringBuilder();
int multi = 0;
LinkedList<Integer> stack_multi = new LinkedList<>();
LinkedList<String> stack_res = new LinkedList<>();
for (Character c : s.toCharArray()){
if (c == '['){
stack_multi.add(multi);
stack_res.addLast(sb.toString());
multi = 0;
sb = new StringBuilder();
}else if (c == ']'){
StringBuilder tmp = new StringBuilder();
int cur_multi = stack_multi.removeLast();
for (int i = 0; i < cur_multi;i++){
tmp.append(sb);
}
sb = new StringBuilder(stack_res.removeLast() + tmp);
}else if (c >= '0' && c <= '9'){
multi = multi*10 + Integer.parseInt(c + "");
}else {
sb.append(c);
}
}
return sb.toString();
}
public int[][] reconstructQueue(int[][] people) {
//按数组第一个元素进行降序，按第二个元素进行升序
Arrays.sort(people, new Comparator<int[]>() {
@Override
public int compare(int[] person1, int[] person2){
if (person1[0] != person2[0]){
//第一个元素不相等时，第一个元素降序
return person2[0] - person1[0];
}else{
//第一个元素相等时，第二个元素升序
return person1[1] - person2[1];
}
}
});
//新建一个list,用于保存结果集
List<int[]> list = new LinkedList<>();
for (int i = 0; i < people.length; i++) {
if (list.size() > people[i][1]){
//结果集中元素个数大于第i个人前面应有的人数时，将第i个人插入到结果集的 people[i][1]位置
list.add(people[i][1],people[i]);
}else{
//结果集中元素个数小于等于第i个人前面应有的人数时，将第i个人追加到结果集的后面
list.add(list.size(),people[i]);
}
}
//将list转化为数组，然后返回
return list.toArray(new int[list.size()][]);
}
public boolean canPartition(int[] nums) {
int sum = 0;
for (int num : nums) sum += num;
// 和为奇数时，不可能划分成两个和相等的集合
if (sum % 2 != 0) return false;
int n = nums.length;
sum = sum / 2;
boolean[][] dp = new boolean[n + 1][sum + 1];
// base case
for (int i = 0; i <= n; i++)
dp[i][0] = true;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= sum; j++) {
if (j - nums[i - 1] < 0) {
// 背包容量不足，不能装入第 i 个物品
dp[i][j] = dp[i - 1][j];
} else {
// 装入或不装入背包
dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]];
}
}
}
return dp[n][sum];
}
HashMap<Integer,Integer> map = new HashMap<>();
int preSum,targetSum;
int res = 0;
public int pathSum(TreeNode root, int targetSum) {
if (root == null){
return 0;
}
this.preSum = 0;
this.targetSum = targetSum;
this.map.put(0,1);
traverse(root);
return res;
}
private void traverse(TreeNode root) {
if (root == null){
return;
}
//前序遍历位置
preSum += root.val;
res += map.getOrDefault(preSum-targetSum,0);
map.put(preSum,map.getOrDefault(preSum,0)+1);
traverse(root.left);
traverse(root.right);
map.put(preSum,map.get(preSum) -1);
preSum -= root.val;
}
public List<Integer> findAnagrams(String s, String p) {
HashMap<Character,Integer> window_map = new HashMap<>();
HashMap<Character,Integer> p_map = new HashMap<>();
for (int i = 0; i < p.length(); i++){
char c1 = p.charAt(i);
p_map.put(c1,p_map.getOrDefault(c1,0) +1);
}
int left,right,count;
left = right = count = 0;
ArrayList<Integer> res = new ArrayList<>();
while (right < s.length()){
char c = s.charAt(right);
right++;
if (p_map.containsKey(c)){
window_map.put(c,window_map.getOrDefault(c,0)+1);
if (window_map.get(c).equals(p_map.get(c))){
count++;
}
}
while (right - left == p.length()) {
if (count == p_map.size()) {
res.add(left);
}
char d = s.charAt(left);
left++;
if (p_map.containsKey(d)) {
if (window_map.get(d).equals(p_map.get(d))) {
count--;
}
window_map.put(d, window_map.getOrDefault(d, 0) - 1);
}
}
}
return res;
}
public List<Integer> findDisappearedNumbers(int[] nums) {
int length = nums.length;
HashSet<Integer> set = new HashSet<>();
for (int i = 0; i < nums.length; i++){
set.add(nums[i]);
}
List<Integer> list = new LinkedList<>();
for (int i = 1; i <= length; i++){
if (!set.contains(i)){
list.add(i);
}
}
return list;
}
public int hammingDistance(int x, int y) {
int s = x ^ y,ret = 0;
while (s != 0){
s &= s -1;
ret++;
}
return ret;
}
public int findTargetSumWays(int[] nums, int target) {
if (nums.length == 0){
return 0;
}
return dp(nums,0,target);
}
HashMap<String,Integer> map = new HashMap<>();
private int dp(int[] nums, int i, int target) {
if (i == nums.length){
if (target == 0){
return 1;
}
return 0;
}
String key = i+","+target;
if (map.containsKey(key)){
return map.get(key);
}
int result = dp(nums,i+1,target - nums[i]) + dp(nums,i+1,target + nums[i]);
map.put(key,result);
return result;
}
public TreeNode convertBST(TreeNode root) {
traverse(root);
return root;
}
int sum = 0;
private void traverse(TreeNode root) {
if (root == null){
return;
}
traverse(root.right);
sum += root.val;
root.val = sum;
traverse(root.left);
}
int max = 0;
public int diameterOfBinaryTree(TreeNode root) {
maxDepth(root);
return max;
}
private int maxDepth(TreeNode root) {
if (root == null){
return 0;
}
int leftMax = maxDepth(root.left);
int rightMax = maxDepth(root.right);
max = Math.max(max,leftMax+rightMax);
return 1 + Math.max(leftMax,rightMax);
}
public int subarraySum(int[] nums, int k) {
int count = 0,pre = 0;
HashMap<Integer,Integer> map = new HashMap<>();
map.put(0,1);
for (int i = 0; i < nums.length; i++){
pre += nums[i];
if (map.containsKey(pre-k)){
count+=map.get(pre - k);
}
map.put(pre,map.getOrDefault(pre,0)+1);
}
return count;
}
public int findUnsortedSubarray(int[] nums) {
int length = nums.length;
int leftDiff = -1;
int rightDiff = -1;
int max = nums[0];
int min = nums[length-1];
for (int i = 0; i < length; i++){
if (nums[i] < max){
rightDiff = i;
}else {
max = nums[i];
}
int index = length - 1 - i;
if (nums[index] > min){
leftDiff = index;
}else {
min = nums[index];
}
}
return leftDiff != -1 ? rightDiff - leftDiff + 1 : 0;
}
public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
if (root1 == null){
return root2;
}
if (root2 == null){
return root1;
}
root1.val += root2.val;
root1.left = mergeTrees(root1.left,root2.left);
root1.right = mergeTrees(root1.right,root2.right);
return root1;
}
public int countSubstrings(String s) {
int sum = 0;
int n = s.length();
for (int i = 0; i < n; i++){
for (int j = 0; j <= 1; j++){
int l = i;
int r = i+j;
while (l>=0 && r <n && s.charAt(l--)== s.charAt(r++)){
sum++;
}
}
}
return sum;
}
public int[] dailyTemperatures(int[] temperatures) {
int length = temperatures.length;
int[] ans = new int[length];
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < length; i++){
int tem = temperatures[i];
while (!stack.isEmpty() && tem > temperatures[stack.peek()]){
int pre = stack.pop();
ans[pre] = i - pre;
}
stack.push(i);
}
return ans;
}
