package com.demo.s22;

import java.util.ArrayList;
import java.util.List;

/**
 * 括号生成
 * 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
 */
public class Solution {
    public List<String> generateParenthesis(int n) {
        //定义结果list
        List<String> ans = new ArrayList<String>();
        //回溯法
        backtrack(ans, new StringBuilder(), 0, 0, n);
        return ans;
    }

    public void backtrack(List<String> ans, StringBuilder cur, int open, int close, int max) {
        //如果长度够了 就添加到list 返回  max是括号对数
        if (cur.length() == max * 2) {
            ans.add(cur.toString());
            return;
        }
        //open 左括号个数 close 右括号个数
        //如果 左括号个数没有到最大值
        if (open < max) {
            //就再拼接一个左括号
            cur.append('(');
            //递归 继续拼接
            backtrack(ans, cur, open + 1, close, max);
            //开始回溯 每次减去一个左括号
            cur.deleteCharAt(cur.length() - 1);
        }
        //如果 右括号个数没有到最大值
        if (close < open) {
            cur.append(')');
            backtrack(ans, cur, open, close + 1, max);
            //开始回溯 每次减去一个左括号
            cur.deleteCharAt(cur.length() - 1);
        }
    }


}

package com.demo.s215;

/**
 * 215. 数组中的第K个最大元素
 * 给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
 *
 * 请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
 *
 * 你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/kth-largest-element-in-an-array
 */
public class Solution {
    /**
     * 堆排序问题
     */
    public int findKthLargest(int[] nums, int k) {
        //定义堆的大小
        int heapSize = nums.length;
        //初始构建大顶堆，大小为全部的数组长度
        buildMaxHeap(nums, heapSize);
        //大顶堆每次去掉最大的元素
        for (int i = nums.length - 1; i >= nums.length - k + 1; --i) {
            //去掉最大元素
            swap(nums, 0, i);
            --heapSize;
            //构建一个次小堆
            maxHeapify(nums, 0, heapSize);
        }
        return nums[0];
    }
    //构建大顶堆
    public void buildMaxHeap(int[] a, int heapSize) {
        //复杂度 heapSize / 2
        for (int i = heapSize / 2; i >= 0; --i) {
            maxHeapify(a, i, heapSize);
        }
    }
    //大顶堆
    public void maxHeapify(int[] a, int i, int heapSize) {
        //左子节点  右子节点， 根
        int l = i * 2 + 1, r = i * 2 + 2, largest = i;
        //堆 大小范围内， 如果 左子节点 > 根
        if (l < heapSize && a[l] > a[largest]) {
            // 根为左子节点
            largest = l;
        }
        //堆 大小范围内， 如果 右子节点 > 根
        if (r < heapSize && a[r] > a[largest]) {
            // 根为右子节点
            largest = r;
        }
        // 根被替换
        if (largest != i) {
            // 执行移动操作
            swap(a, i, largest);
            //重新构建
            maxHeapify(a, largest, heapSize);
        }
    }

    public void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

}

package com.demo.s21;

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

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
public class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        //递归终止条件
        if(list1 == null) {
            return list2;
        }
        //递归终止条件
        if(list2 == null) {
            return list1;
        }
        //从小到大排列
        if(list1.val <= list2.val) {
            //合并子链表
            list1.next = mergeTwoLists(list1.next, list2);
            return list1;
        } else {
            list2.next = mergeTwoLists(list2.next, list1);
            return list2;
        }

    }
}

package com.demo.s206;

/**
 * 206. 反转链表
 * 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
 */
class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

public class Solution {

    public ListNode reverseList(ListNode head) {
        //前置节点 后一个节点指向的节点，初始的前置节点为null
        ListNode pre = null;
        //当前节点，从head开始遍历
        ListNode cur = head;
        //当前节点不为null
        while(cur != null) {
            //下一个节点先存中间变量
            ListNode t = cur.next;
            //下一个节点指向前一个节点
            cur.next = pre;
            //当前节点称为前置节点
            pre = cur;
            //下一个节点为当前节点
            cur = t;
        }
        return pre;
    }

}

package com.demo.s200;

public class Solution {
}

package com.demo.s20;

import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

/**
 * 有效的括号
 * 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
 *
 * 有效字符串需满足：
 *
 * 左括号必须用相同类型的右括号闭合。
 * 左括号必须以正确的顺序闭合。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/valid-parentheses
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution {
    public boolean isValid(String s) {
        //根据入参判断 不能为奇数
        if(s.length() % 2 != 0) {
            return false;
        }
        //符号对
        Map<Character, Character> pairs = new HashMap();
        pairs.put('(', ')');
        pairs.put('[', ']');
        pairs.put('{', '}');
        //字符串转字符数组
        char[] charr =s.toCharArray();
        //放入栈中判断
        Deque<Character> stack = new LinkedList();
        for(int i = 0; i< charr.length ; i++) {
            //如果为左侧符号， 符号对key中一定存在，则压栈
            if(pairs.containsKey(charr[i])) {
                stack.push(pairs.get(charr[i]));
                //如果符号对key中不存在，栈中有元素，且栈顶符号等于当前符号，则弹栈
            } else if(stack.size()!=0 && stack.peek() == charr[i]){
                stack.pop();
                continue;
            } else {
                return false;
            }

        }
        return stack.size() == 0;
    }
}

package com.demo.s2;

/**
 * 给你两个非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
 *
 * 请你将两个数相加，并以相同形式返回一个表示和的链表。
 *
 * 你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/add-two-numbers
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution {
    /**
     * 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; }
    }

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        //新建结果链表
        ListNode head = new ListNode();
        //记录当前节点 方便后面移动
        ListNode cur = head;
        //相加 > 10 进一位 进位的值
        int carray = 0;
        //判断结束条件
        while(l1 != null || l2 != null || carray!=0) {
            // 对应位相加的和
            int sum = 0;
            //l1各位已经加完了， l2 还没有结束
            if(l1 == null && l2 != null) {
                sum = l2.val;
                l2 = l2.next;
                //l2各位已经加完了， l1 还没有结束
            } else if(l2 == null && l1 != null) {
                sum = l1.val;
                l1 = l1.next;
                //l1 l2 对应位置有值则相加
            } else if(l2 != null && l1 != null){
                sum = l1.val + l2.val;
                l1 = l1.next;
                l2 = l2.next;
            }
            //接到结果链表链表后面
            cur.next = new ListNode((sum + carray) % 10);
            //需要进一位的保存在变量carray
            carray = (sum + carray) / 10;
            cur = cur.next;
        }
        return head.next;
    }
    public static void main(String[] args) {

    }
}

package com.demo.s199;


import java.util.*;

/**
 * 给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
 *
 *
 */

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;
    }
}

public class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> ret = new ArrayList<>();
        if(root == null) {
            return ret;
        }

        int max_dep = -1;
        //右分支视图按层输出
        Map<Integer,Integer> rightViewAtDepth = new HashMap<Integer, Integer>();
        //节点压栈
        Stack<TreeNode> nodeStack = new Stack<>();
        nodeStack.push(root);
        //深度压栈
        Stack<Integer> depthStack = new Stack<>();
        depthStack.push(0);
        while(nodeStack.size() != 0 ) {
            //节点弹栈
            TreeNode node = nodeStack.pop();
            //深度弹栈
            Integer dep = depthStack.pop();
            if(node != null) {
                //最大深度
                max_dep = Math.max(dep, max_dep);
                //右视图未遍历到该层，第一次遍历到的一定是右节点
                if(!rightViewAtDepth.containsKey(dep)) {
                    //存入视图
                    rightViewAtDepth.put(dep, node.val);
                }
                //左节点压栈
                nodeStack.push(node.left);
                //右节点压栈
                nodeStack.push(node.right);
                //层数存入深度栈
                depthStack.push(dep + 1);
                //层数存入深度栈
                depthStack.push(dep + 1);
            }
        }

        //遍历深度
        for(int i = 0 ;i <= max_dep; i++) {
            Integer val = rightViewAtDepth.get(i);
            ret.add(val);
        }
        return ret;
    }
}

package com.demo.s19;

/**
 * 删除链表的倒数第 N 个结点
 * 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
 */
class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
public class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dum = new ListNode(0, head);
        int cnt = 0;
        while(head != null) {
            cnt++;
            head = head.next;
        }

        head = dum;
        for(int i = 1; i< cnt-n + 1; i++) {
            head = head.next;
        }
        head.next = head.next.next;
        return dum.next;
    }
}

package com.demo.s18;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 四数之和
 * 给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：
 *
 * 0 <= a, b, c, d < n
 * a、b、c 和 d 互不相同
 * nums[a] + nums[b] + nums[c] + nums[d] == target
 * 你可以按 任意顺序 返回答案 。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/4sum
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> quadruplets = new ArrayList<List<Integer>>();
        if (nums == null || nums.length < 4) {
            return quadruplets;
        }
        Arrays.sort(nums);
        int length = nums.length;
        for (int i = 0; i < length - 3; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            if (nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) {
                break;
            }
            if (nums[i] + nums[length - 3] + nums[length - 2] + nums[length - 1] < target) {
                continue;
            }
            for (int j = i + 1; j < length - 2; j++) {
                if (j > i + 1 && nums[j] == nums[j - 1]) {
                    continue;
                }
                if (nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) {
                    break;
                }
                if (nums[i] + nums[j] + nums[length - 2] + nums[length - 1] < target) {
                    continue;
                }
                int left = j + 1, right = length - 1;
                while (left < right) {
                    int sum = nums[i] + nums[j] + nums[left] + nums[right];
                    if (sum == target) {
                        quadruplets.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
                        while (left < right && nums[left] == nums[left + 1]) {
                            left++;
                        }
                        left++;
                        while (left < right && nums[right] == nums[right - 1]) {
                            right--;
                        }
                        right--;
                    } else if (sum < target) {
                        left++;
                    } else {
                        right--;
                    }
                }
            }
        }
        return quadruplets;
    }
}