k 是一个正整数，它的值小于或等于链表的长度。
如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
示例：
给你这个链表：1->2->3->4->5
当 k = 2 时，应当返回: 2->1->4->3->5
当 k = 3 时，应当返回: 3->2->1->4->5
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode reverseKGroup(ListNode head, int k) { ListNode dummy = new ListNode(-1); dummy.next = head; //前驱节点 ListNode pre = dummy; //后驱节点 ListNode end = dummy; while(end!=null){ //后移k个节点，到达翻转链表的末尾节点 for(int i=0;i<k&&end!=null;i++) end = end.next; //如果此时末尾节点为null，则说明长度不够，直接结束 if(end==null) break; //next节点保存后驱节点 ListNode next = end.next; //start指向翻转链表的开始 ListNode start = pre.next; //end指向翻转链表的结束，这里将end与之后的链表切断 end.next = null; //翻转之后的头节点由前驱节点的next指向，与前驱连上 pre.next = reverse(start); //翻转以后start节点为该翻转链表的末尾，指向后驱 start.next = next; //前驱节点后后驱节点都指向start pre = start; end = start; } return dummy.next; } private ListNode reverse(ListNode node){ ListNode pre = null; ListNode cur = node; while(cur!=null){ ListNode next = cur.next; cur.next = pre; pre = cur; cur=next; } return pre; } } 买卖股票的最佳时机 给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。
注意：你不能在买入股票前卖出股票。
示例 1:
输入: [7,1,5,3,6,4] 输出: 5 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。 示例 2:
输入: [7,6,4,3,1] 输出: 0 解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
class Solution { public int maxProfit(int[] prices) { //dp[i][k][0] = max(dp[i-1][k][0],dp[i-1][k][1]+prices[i]) //dp[i][k][1] = max(dp[i-1][k][1],dp[i-1][k-1][0]-prices[i]) //dp[i][0][0] = 0;不允许交易利润为0 //dp[i][0][1] = -infinity;不允许交易持有不可能发生 //dp[-1][k][0] = -infinity;时间从第0天开始，不可能为-1 //dp[-1][k][1] = -infinity;时间从第0天开始，不可能为-1 //带入k=1; dp[i][1][0] = max(dp[i-1][1][0],dp[i-1][1][1]+prices[i]); // dp[i]][1][1] = max(dp[i-1][1][1],dp[i-1][0][0]-prices[i]); //因为dp[i-1][0][0] = 0; 所以dp[i][1][1] = max(dp[i-1][1][1],-prices[i]); //与k无关 //最终的状态方程为 dp[i][0] = max(dp[i-1][0],dp[i-1][1]+prices[i]); // dp[i][1] = max(dp[i-1][1],-prices[i]); int n = prices.length; if(n==0) return 0; int dp_sum0 = 0; int dp_sum1 = Integer.MIN_VALUE; for(int i=0;i<n;i++){ // dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1]+prices[i]); dp_sum0 = Math.max(dp_sum0,dp_sum1+prices[i]); // dp[i][1] = Math.max(dp[i-1][1],-prices[i]); dp_sum1 = Math.max(dp_sum1,-prices[i]); } return dp_sum0; } } 三数之和 给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。注意：答案中不可以包含重复的三元组。
示例：
给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为： [ [-1, 0, 1], [-1, -1, 2] ]
class Solution { public List<List<Integer>> threeSum(int[] nums) { List<List<Integer>> ans = new ArrayList<>(); Arrays.sort(nums); for(int k=0;k<nums.length-2;k++){ if(nums[k]>0) break; if(k>0&&nums[k]==nums[k-1]) continue; int i = k+1; int j = nums.length-1; while(i<j){ int sum = nums[k]+nums[i]+nums[j]; if(sum>0){ while(i<j&&nums[j]==nums[--j]); }else if(sum<0){ while(i<j&&nums[i]==nums[++i]); }else if(sum==0){ List<Integer> list = new ArrayList<>(); list.add(nums[k]); list.add(nums[i]); list.add(nums[j]); ans.add(list); while(i<j&&nums[i]==nums[++i]); while(i<j&&nums[j]==nums[--j]); } } } return ans; } } 最小栈 设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。push(x) —— 将元素 x 推入栈中。 pop() —— 删除栈顶的元素。 top() —— 获取栈顶元素。 getMin() —— 检索栈中的最小元素。
示例:
输入： [“MinStack”,“push”,“push”,“push”,“getMin”,“pop”,“top”,“getMin”] [[],[-2],[0],[-3],[],[],[],[]]
输出： [null,null,null,null,-3,null,0,-2]
解释： MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); --> 返回 -3. minStack.pop(); minStack.top(); --> 返回 0. minStack.getMin(); --> 返回 -2.
class MinStack { Stack<Integer> st1 ; Stack<Integer> st2 ; /** initialize your data structure here. */ public MinStack() { st1 = new Stack<>(); st2 = new Stack<>(); } public void push(int x) { st1.push(x); if(st2.isEmpty()||st2.peek()>=x) st2.push(x); } public void pop() { if(st1.pop().equals(st2.peek())) st2.pop(); } public int top() { return st1.peek(); } public int getMin() { return st2.peek(); } } /** * Your MinStack object will be instantiated and called as such: * MinStack obj = new MinStack(); * obj.push(x); * obj.pop(); * int param_3 = obj.top(); * int param_4 = obj.getMin(); */ 二叉树中的最大路径和 给定一个非空二叉树，返回其最大路径和。本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。
示例 1:
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { int max = Integer.MIN_VALUE; public int maxPathSum(TreeNode root) { heper(root); return max; } private int heper(TreeNode root){ if(root==null) return 0; int left = Math.max(heper(root.left),0) ; int right = Math.max(heper(root.right),0); max = Math.max(max,root.val+left+right); return root.val+Math.max(left,right); } } 无重复字符的最长子串 给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。示例 1:
输入: “abcabcbb” 输出: 3 解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。 示例 2:
输入: “bbbbb” 输出: 1 解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。 示例 3:
输入: “pwwkew” 输出: 3 解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。 请注意，你的答案必须是 子串 的长度，“pwke” 是一个子序列，不是子串。
class Solution { public int lengthOfLongestSubstring(String s) { int max = 0; Map<Character,Integer> map = new HashMap<>(); int left = 0; for(int i=0;i<s.length();i++){ char c = s.charAt(i); if(map.containsKey(c)){ left = Math.max(left,map.get(c)+1); } map.put(c,i); max = Math.max(max,i-left+1); } return max; } } 合并两个有序数组 给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。说明:
初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。 你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。
示例:
输入: nums1 = [1,2,3,0,0,0], m = 3 nums2 = [2,5,6], n = 3
输出: [1,2,2,3,5,6]
class Solution { public void merge(int[] nums1, int m, int[] nums2, int n) { int index =m+n-1; m--; n--; while(m>=0&&n>=0){ if(nums1[m]>nums2[n]){ nums1[index--]=nums1[m--]; }else { nums1[index--] = nums2[n--]; } } while(n>=0){ nums1[index--] = nums2[n--]; } } } 将有序数组转换为二叉搜索树 将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
示例:
给定有序数组: [-10,-3,0,5,9],
一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：
0 / \-3 9 / / -10 5
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { int[] nums; public TreeNode sortedArrayToBST(int[] nums) { this.nums = nums; return heper(0,nums.length-1); } private TreeNode heper(int left,int right){ if(left>right) return null; int mid = left+(right-left)/2; TreeNode root = new TreeNode(nums[mid]); root.left = heper(left,mid-1); root.right = heper(mid+1,right); return root; } } 二叉树的最近公共祖先 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]
示例 1:
输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 输出: 3 解释: 节点 5 和节点 1 的最近公共祖先是节点 3。
/** * 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; } } 搜索旋转排序数组 假设按照升序排序的数组在预先未知的某个点上进行了旋转。( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -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
class Solution { public int search(int[] nums, int target) { if(nums.length==0) return -1; int left = 0; int right = nums.length-1; while(left<=right){ int mid = left+(right-left)/2; if(nums[mid]>nums[right]){ left=mid+1; }else if(nums[mid]<nums[right]){ right=mid; }else break; } int index = left; left = 0; right = index-1; while(left<=right){ int mid = left+(right-left)/2; if(nums[mid]==target) return mid; else if(nums[mid]<target){ left=mid+1; }else if(nums[mid]>target){ right=mid-1; } } left = index; right = nums.length-1; while(left<=right){ int mid = left+(right-left)/2; if(nums[mid]==target) return mid; else if(nums[mid]<target){ left=mid+1; }else if(nums[mid]>target){ right=mid-1; } } return -1; } } 零钱兑换 给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。示例 1:
输入: coins = [1, 2, 5], amount = 11 输出: 3 解释: 11 = 5 + 5 + 1 示例 2:
输入: coins = [2], amount = 3 输出: -1
class Solution { public int coinChange(int[] coins, int amount) { int[] dp = new int[amount+1]; for(int i=0;i<=amount;i++){ dp[i] = Integer.MAX_VALUE/2; } dp[0] = 0; for(int coin:coins){ for(int i=coin;i<=amount;i++){ dp[i] = Math.min(dp[i],dp[i-coin]+1); } } return dp[amount]==Integer.MAX_VALUE/2?-1:dp[amount]; } } 删除排序链表中的重复元素 给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。示例 1:
输入: 1->1->2 输出: 1->2 示例 2:
输入: 1->1->2->3->3 输出: 1->2->3
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode deleteDuplicates(ListNode head) { if(head==null||head.next==null) return head; ListNode ans = new ListNode(-1); ans.next = head; ListNode slow = ans.next; ListNode fast = slow.next; while(fast!=null){ while(fast!=null&&fast.val==slow.val){ fast = fast.next; } slow.next = fast; slow = fast; if(fast!=null) fast=fast.next; } return ans.next; } } 反转链表 反转一个单链表。示例:
输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL 进阶: 你可以迭代或递归地反转链表。你能否用两种方法解决这道题？
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode reverseList(ListNode head) { if(head==null||head.next==null) return head; ListNode pre = null; ListNode cur = head; while(cur!=null){ ListNode next = cur.next; cur.next = pre; pre=cur; cur = next; } return pre; } } 数组中的第K个最大元素 在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。示例 1:
输入: [3,2,1,5,6,4] 和 k = 2 输出: 5 示例 2:
输入: [3,2,3,1,2,4,5,5,6] 和 k = 4 输出: 4
class Solution { public int findKthLargest(int[] nums, int k) { int len = nums.length; int left = 0; int right = nums.length-1; int target = len-k; while(true){ int index = quick(nums,left,right); if(index==target){ return nums[index]; }else if(index>target){ right = index-1; }else if(index<target){ left = index+1; } } // return -1; } private int quick(int[] nums,int left ,int right){ int privot = nums[left]; int j = left; for(int i=left+1;i<=right;i++){ if(nums[i]<privot){ j++; swap(nums,i,j); } } swap(nums,left,j); return j; } private void swap(int[] nums,int index1,int index2){ int tmp = nums[index1]; nums[index1] = nums[index2]; nums[index2] = tmp; } } 合并区间 给出一个区间的集合，请合并所有重叠的区间。示例 1:
输入: [[1,3],[2,6],[8,10],[15,18]] 输出: [[1,6],[8,10],[15,18]] 解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6]. 示例 2:
输入: [[1,4],[4,5]] 输出: [[1,5]] 解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。
class Solution { public int[][] merge(int[][] intervals) { if(intervals==null||intervals.length==0||intervals[0].length==0) return intervals; Arrays.sort(intervals,(o1,o2)->{ return o1[0]==o2[0]?o2[1]-o1[1]:o1[0]-o2[0]; }); int end = intervals[0][1]; int start = intervals[0][0]; List<int[]> list = new ArrayList<>(); for(int i=1;i<intervals.length;i++){ if(end>=intervals[i][0]){ end = Math.max(end,intervals[i][1]); }else{ int[] tmp = new int[]{start,end}; list.add(tmp); start = intervals[i][0]; end = intervals[i][1]; } } if(list.size()==0){ int[] tmp = new int[]{start,end}; list.add(tmp); } if(list.get(list.size()-1)[1]!=end){ int[] tmp = new int[]{start,end}; list.add(tmp); } int[][] ans = new int[list.size()][2]; for(int i=0;i<list.size();i++){ ans[i][0]=list.get(i)[0]; ans[i][1] =list.get(i)[1]; } return ans; } } 二叉树的层序遍历 给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。 /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> ans = new ArrayList<>(); List<TreeNode> nodes = new ArrayList<>(); List<Integer> list = new ArrayList<>(); if(root==null) return ans; int count =0; nodes.add(root); while(nodes.size()!=0){ if(count==0){ ans.add(list); count = nodes.size(); list = new ArrayList<>(); } TreeNode tmp = nodes.remove(0); list.add(tmp.val); if(tmp.left!=null) nodes.add(tmp.left); if(tmp.right!=null) nodes.add(tmp.right); count--; } ans.add(list); ans.remove(0); return ans; } } 零钱兑换 II 给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。示例 1:
输入: amount = 5, coins = [1, 2, 5] 输出: 4 解释: 有四种方式可以凑成总金额: 5=5 5=2+2+1 5=2+1+1+1 5=1+1+1+1+1 示例 2:
输入: amount = 3, coins = [2] 输出: 0 解释: 只用面额2的硬币不能凑成总金额3。 示例 3:
输入: amount = 10, coins = [10] 输出: 1
class Solution { public int change(int amount, int[] coins) { int[] dp = new int[amount+1]; dp[0]=1; for(int coin:coins){ for(int i=1;i<=amount;i++){ if(coin<=i){ dp[i]+=dp[i-coin]; } } } return dp[amount]; } }剑指 Offer 09. 用两个栈实现队列 用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )
class CQueue { Stack<Integer> st1 ; Stack<Integer> st2 ; public CQueue() { st1 = new Stack<>(); st2 = new Stack<>(); } public void appendTail(int value) { st1.push(value); } public int deleteHead() { if(st2.isEmpty()){ while(!st1.isEmpty()) st2.push(st1.pop()); } if(st2.isEmpty()) return -1; return st2.pop(); } } /** * Your CQueue object will be instantiated and called as such: * CQueue obj = new CQueue(); * obj.appendTail(value); * int param_2 = obj.deleteHead(); */剑指 Offer 32 - III. 从上到下打印二叉树 III 请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public List<List<Integer>> levelOrder(TreeNode root) { Queue<TreeNode> nodes = new LinkedList<>(); List<List<Integer>> ans = new ArrayList<>(); if(root!=null) nodes.add(root); while(nodes.size()!=0){ LinkedList<Integer> tmp = new LinkedList<>(); for(int i=nodes.size();i>0;i--){ TreeNode node = nodes.poll(); if(ans.size()%2==0){ tmp.addLast(node.val); }else{ tmp.addFirst(node.val); } if(node.left!=null) nodes.add(node.left); if(node.right!=null) nodes.add(node.right); } ans.add(tmp); } return ans; } } 螺旋矩阵 给定一个包含 m x n 个元素的矩阵（m 行, n 列），请按照顺时针螺旋顺序，返回矩阵中的所有元素。 class Solution { int[] dx = {0,1,0,-1}; int[] dy = {1,0,-1,0}; public List<Integer> spiralOrder(int[][] matrix) { List<Integer> ans = new ArrayList<>(); int m = matrix.length; if(m==0) return ans; int n = matrix[0].length; boolean[][] isVisited = new boolean[m][n]; int sum = m*n; int x = 0; int y = 0; int index = 1; int duration = 0; ans.add(matrix[x][y]); isVisited[0][0]=true; while(index<sum){ x+=dx[duration]; y+=dy[duration]; if(x<0||x>=m||y<0||y>=n||isVisited[x][y]==true){ x-=dx[duration]; y-=dy[duration]; duration=(duration+1)%4; x+=dx[duration]; y+=dy[duration]; } ans.add(matrix[x][y]); isVisited[x][y]=true; index++; } return ans; } } 将每个元素替换为右侧最大元素 给你一个数组 arr ，请你将每个元素用它右边最大的元素替换，如果是最后一个元素，用 -1 替换。完成所有替换操作后，请你返回这个数组。
示例：
输入：arr = [17,18,5,4,6,1] 输出：[18,6,6,6,1,-1]
class Solution { public int[] replaceElements(int[] arr) { int len = arr.length; int[] ans = new int[len]; ans[len-1] = -1; int max = arr[len-1]; for(int i=len-2;i>=0;i--){ max = Math.max(max,arr[i+1]); ans[i] = max; } return ans; } } 接雨水 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。 class Solution { public int trap(int[] height) { int ans = 0; int len = height.length; int[] left_max = new int[len]; int[] right_max = new int[len]; for(int i=1;i<len;i++){ left_max[i] = Math.max(left_max[i-1],height[i-1]); } for(int i=len-2;i>=0;i--){ right_max[i] = Math.max(right_max[i+1],height[i+1]); } for(int i=1;i<len-1;i++){ int left = left_max[i]; int right = right_max[i]; int min = Math.min(left,right); if(min>height[i]) ans+=min-height[i]; } return ans; } } 从前序与中序遍历序列构造二叉树 根据一棵树的前序遍历与中序遍历构造二叉树。注意: 你可以假设树中没有重复的元素。
例如，给出
前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7]
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public TreeNode buildTree(int[] preorder, int[] inorder) { return buildTree(preorder,0,preorder.length-1,inorder,0,inorder.length-1); } private TreeNode buildTree(int[] preorder,int preStart,int preEnd,int[] inorder,int inStart,int inEnd){ if(preStart>preEnd) return null; int value = preorder[preStart]; TreeNode root = new TreeNode(value); int index = 0; for(int i=inStart;i<=inEnd;i++){ if(inorder[i]==value){ index =i; break; } } root.left = buildTree(preorder,preStart+1,preStart+index-inStart,inorder,inStart,index-1); root.right = buildTree(preorder,preStart+index-inStart+1,preEnd,inorder,index+1,inEnd); return root; } } 相交链表 编写一个程序，找到两个单链表相交的起始节点。 /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { ListNode pointA = headA; ListNode pointB = headB; while(pointA!=pointB){ pointA = pointA==null?headB:pointA.next; pointB = pointB==null?headA:pointB.next; } return pointA; } } 单词拆分 给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。说明：
拆分时可以重复使用字典中的单词。 你可以假设字典中没有重复的单词。 示例 1：
输入: s = “leetcode”, wordDict = [“leet”, “code”] 输出: true 解释: 返回 true 因为 “leetcode” 可以被拆分成 “leet code”。 示例 2：
输入: s = “applepenapple”, wordDict = [“apple”, “pen”] 输出: true 解释: 返回 true 因为 “applepenapple” 可以被拆分成 “apple pen apple”。 注意你可以重复使用字典中的单词。 示例 3：
输入: s = “catsandog”, wordDict = [“cats”, “dog”, “sand”, “and”, “cat”] 输出: false
class Solution { public boolean wordBreak(String s, List<String> wordDict) { Set<String> set = new HashSet<>(wordDict); boolean[] dp = new boolean[s.length()+1]; dp[0] = true; for(int i=1;i<=s.length();i++){ for(int j=0;j<i;j++){ if(dp[j]&&set.contains(s.substring(j,i))){ dp[i]=true; break; } } } return dp[s.length()]; } } 二进制求和 给你两个二进制字符串，返回它们的和（用二进制表示）。输入为 非空 字符串且只包含数字 1 和 0。
示例 1:
输入: a = “11”, b = “1” 输出: “100” 示例 2:
输入: a = “1010”, b = “1011” 输出: “10101”
class Solution { public String addBinary(String a, String b) { char[] aa = a.toCharArray(); char[] bb = b.toCharArray(); int len1 = aa.length; int len2 = bb.length; char[] ans = new char[len1+len2]; int len = len1+len2-1; int cf = 0; len1--; len2--; while(len1>=0&&len2>=0){ int num1 = aa[len1--]-'0'; int num2 = bb[len2--]-'0'; int sum = (num1+num2+cf)%2; cf = (num1+num2+cf)/2; ans[len--]=(char)('0'+sum); } while(len1>=0){ int num1 = aa[len1--]-'0'; int sum = (num1+cf)%2; cf = (num1+cf)/2; ans[len--]=(char)('0'+sum); } while(len2>=0){ int num2 = bb[len2--]-'0'; int sum = (num2+cf)%2; cf = (num2+cf)/2; ans[len--]=(char)('0'+sum); } if(cf>0){ ans[len--]='1'; } StringBuilder sb = new StringBuilder(); for(int i=0;i<ans.length;i++){ if(i==0){ while(i<ans.length-1&& ans[i]!='1') i++; } sb.append(ans[i]); } return sb.toString(); } } 二叉搜索树中第K小的元素 给定一个二叉搜索树，编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。说明： 你可以假设 k 总是有效的，1 ≤ k ≤ 二叉搜索树元素个数
/** * 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 kthSmallest(TreeNode root, int k) { LinkedList<TreeNode> stack = new LinkedList<TreeNode>(); while (true) { while (root != null) { stack.add(root); root = root.left; } root = stack.removeLast(); if (--k == 0) return root.val; root = root.right; } } } 括号生成 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。 class Solution { List<String> ans = new ArrayList<>(); public List<String> generateParenthesis(int n) { String st = ""; dfs(st,n,0,0); return ans; } private void dfs(String st, int n, int left,int right) { if(left==n){ while(st.length()<2*n){ st+=")"; } ans.add(new String(st)); return; } if(left<n){ dfs(st+"(",n,left+1,right); } if(right<left){ dfs(st+")",n,left,right+1); } } }