给定一个只包括 ‘(’，’)’，’{’，’}’，’[’，’]’ 的字符串，判断字符串是否有效。有效字符串需满足： 左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 注意空字符串可被认为是有效字符串。
public boolean isValid(String s) { Stack<Character> a=new Stack<>(); char ch[]=s.toCharArray(); // for(char c: s.toCharArray()){ for (int i = 0; i <s.length() ; i++) { if(ch[i]=='(')a.push(')'); else if(ch[i]=='[')a.push(']'); else if(ch[i]=='{')a.push('}'); //注意先判断是否为空，在判断c是否和栈中元素相等 // 第一种情况:([{}])1 第二种情况:([{[]}]1 else if(a.isEmpty()||ch[i]!=a.pop()) return false; } // } return a.isEmpty(); }请判断一个链表是否为回文链表。 示例 1: 输入: 1->2 输出: false 示例 2: 输入: 1->2->2->1 输出: true 进阶： 你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
// need n extra space public static boolean isPalindrome1(Node head) { Stack<Node> stack = new Stack<Node>(); Node cur = head; while (cur != null) { stack.push(cur); cur = cur.next; } while (head != null) { if (head.value != stack.pop().value) { return false; } head = head.next; } return true; } // need n/2 extra space public static boolean isPalindrome2(Node head) { if (head == null || head.next == null) { return true; } Node right = head.next; Node cur = head; while (cur.next != null && cur.next.next != null) { right = right.next; cur = cur.next.next; } Stack<Node> stack = new Stack<Node>(); while (right != null) { stack.push(right); right = right.next; } while (!stack.isEmpty()) { if (head.value != stack.pop().value) { return false; } head = head.next; } return true; } // need O(1) extra space public static boolean isPalindrome3(Node head) { if (head == null || head.next == null) { return true; } Node n1 = head; Node n2 = head; while (n2.next != null && n2.next.next != null) { // find mid node n1 = n1.next; // n1 -> mid n2 = n2.next.next; // n2 -> end } n2 = n1.next; // n2 -> right part first node n1.next = null; // mid.next -> null Node n3 = null; while (n2 != null) { // right part convert n3 = n2.next; // n3 -> save next node n2.next = n1; // next of right node convert n1 = n2; // n1 move n2 = n3; // n2 move } n3 = n1; // n3 -> save last node n2 = head;// n2 -> left first node boolean res = true; while (n1 != null && n2 != null) { // check palindrome if (n1.value != n2.value) { res = false; break; } n1 = n1.next; // left to mid n2 = n2.next; // right to mid } n1 = n3.next; n3.next = null; while (n1 != null) { // recover list n2 = n1.next; n1.next = n3; n3 = n1; n1 = n2; } return res; }给你一个嵌套的整型列表。请你设计一个迭代器，使其能够遍历这个整型列表中的所有整数。列表中的每一项或者为一个整数，或者是另一个列表。其中列表的元素也可能是整数或是其他列表。 示例 1: 输入: [[1,1],2,[1,1]] 输出: [1,1,2,1,1] 解释: 通过重复调用 next 直到 hasNext 返回 false，next 返回的元素的顺序应该是: [1,1,2,1,1]。
给定一个二叉树，返回其节点值自底向上的层次遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
LinkedList<TreeNode> q=new LinkedList<>(); List<List<Integer>> res=new LinkedList<>(); public List<List<Integer>> levelOrderBottom(TreeNode root) { if(root==null) return res; q.offer(root); while(!q.isEmpty()){ List<Integer> list=new LinkedList<>(); int n=q.size(); for(int i=0;i<n;i++){ TreeNode temp=q.poll(); list.add(temp.val); if(temp.left!=null) q.offer(temp.left); if(temp.right!=null) q.offer(temp.right); } //插在res头部 res.add(0,list); } return res; }给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
LinkedList<TreeNode> q=new LinkedList<>(); LinkedList<List<Integer>> res=new LinkedList<>(); public List<List<Integer>> zigzagLevelOrder(TreeNode root) { if(root==null) return res; q.add(root); while(!q.isEmpty()){ LinkedList<Integer> list=new LinkedList<>(); int n=q.size(); for(int i=0;i<n;i++){ TreeNode temp=q.poll(); int count=res.size(); if(count%2==0) list.addLast(temp.val); else list.addFirst(temp.val); if(temp.left!=null) q.offer(temp.left); if(temp.right!=null) q.offer(temp.right); } res.add(list); } return res; }给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, …）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。 示例 1: 输入: n = 12 输出: 3 解释: 12 = 4 + 4 + 4. 示例 2: 输入: n = 13 输出: 2 解释: 13 = 4 + 9.
给定一个非空的整数数组，返回其中出现频率前 k 高的元素。 示例 1: 输入: nums = [1,1,1,2,2,3], k = 2 输出: [1,2] 示例 2: 输入: nums = [1], k = 1 输出: [1]
解法一:暴力(O(nlogn)) 解法二：最小堆 (O(nlogk)) 题目最终需要返回的是前 kkk 个频率最大的元素，可以想到借助堆这种数据结构，对于 kkk 频率之后的元素不用再去处理，进一步优化时间复杂度。 具体操作为： 借助 哈希表 来建立数字和其出现次数的映射，遍历一遍数组统计元素的频率维护一个元素数目为 k的最小堆每次都将新的元素与堆顶元素（堆中频率最小的元素）进行比较 如果新的元素的频率比堆顶端的元素大，则弹出堆顶端的元素，将新的元素添加进堆中 最终，堆中的 kkk 个元素即为前 kkk 个高频元素 class Solution { public List<Integer> topKFrequent(int[] nums, int k) { // 使用字典，统计每个元素出现的次数，元素为键，元素出现的次数为值 HashMap<Integer,Integer> map = new HashMap(); for(int num : nums){ if (map.containsKey(num)) { map.put(num, map.get(num) + 1); } else { map.put(num, 1); } } // 遍历map，用最小堆保存频率最大的k个元素 PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>() { @Override public int compare(Integer a, Integer b) { return map.get(a) - map.get(b); } }); for (Integer key : map.keySet()) { if (pq.size() < k) { pq.add(key); } else if (map.get(key) > map.get(pq.peek())) { pq.remove(); pq.add(key); } } // 取出最小堆中的元素 List<Integer> res = new ArrayList<>(); while (!pq.isEmpty()) { res.add(pq.remove()); } return res; } }给你一个链表数组，每个链表都已经按升序排列。 请你将所有链表合并到一个升序链表中，返回合并后的链表。 示例 1： 输入：lists = [[1,4,5],[1,3,4],[2,6]] 输出：[1,1,2,3,4,4,5,6] 解释：链表数组如下： [ 1->4->5, 1->3->4, 2->6 ] 将它们合并到一个有序链表中得到。 1->1->2->3->4->4->5->6 示例 2： 输入：lists = [] 输出：[]
public ListNode mergeKLists(ListNode[] lists) { ListNode res=null; for(ListNode l:lists) res= combinTwoLists(res,l); return res; } public ListNode combinTwoLists(ListNode l1,ListNode l2){ if(l1==null) return l2; if(l2==null) return l1; if(l1.val<=l2.val) { l1.next=combinTwoLists(l1.next,l2); return l1; } else{ l2.next=combinTwoLists(l1,l2.next); return l2; } }