LeetCode

与LeetCode的相爱相杀，在解题中找到编程的乐趣，记录解题思路与你共同探讨；

Ps：Num+数字为LeetCode中相应题目编号

用回溯法解决问题三部曲:

画递归树
对递归树编码
找出终止条件，回溯

[toc]

一二叉树类

Num 113:路径总和

/**
*题目描述：给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。
**/
class Solution {
    List<List<Integer>> ans_path = new ArrayList<>();
    List<Integer> node_path = new ArrayList<>();       
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        path_sum(root,sum);
        return ans_path;
    }
    //整体思路：回溯,先序遍历思想，根左右
    public void path_sum(TreeNode root,int sum){
        if(root==null)//空结点直接处理
            return ;
        node_path.add(root.val);
        if(root.left==null&&root.right==null){//叶子节点
            if(sum==root.val){//当前值等于路径值
                ans_path.add(new ArrayList<>(node_path));
            }
        }
        sum-=root.val;
        if(root.left!=null)
            path_sum(root.left,sum);
        if(root.right!=null)
             path_sum(root.right,sum);
        node_path.remove(node_path.size()-1);//回溯
    }
}

Num 129:根节点到叶子节点之和

1	/**
2	* 题目描述:给定一个二叉树，它的每个结点都存放一个 0-9 的数字，每条从根到叶子节点的路径都代表一个数字。
3	* 输入: [1,2,3]
4	* 1
5	* / \
6	* 2 3
7	* 输出: 25
8	* 解释:
9	* 从根到叶子节点路径 1->2 代表数字 12.
10	* 从根到叶子节点路径 1->3 代表数字 13.
11	* 因此，数字总和 = 12 + 13 = 25.
12	**/
13	class Solution {
14	int ans = 0;
15	public int sumNumbers(TreeNode root) {
16	sumNumber(root,0);
17	return ans;
18	}
19	//先序遍历思想
20	public void sumNumber(TreeNode root,int sum){
21	if(root==null)
22	return ;
23	if(root.left==null&&root.right==null){//叶子节点,值直接返回
24	ans += 10*sum+root.val;
25	}
26	sumNumber(root.left,10*sum+root.val);
27	sumNumber(root.right,10*sum+root.val);
28	}
29	}

Num 701: 二叉搜索树的插入操作

class Solution {
      //迭代法
        public TreeNode insertIntoBST(TreeNode root, int val) {
            TreeNode cur = root, p = root;
            while (cur != null) {
                p = cur;
                if (cur.val < val) 
                    cur = cur.right;
                else 
                    cur = cur.left;
            }
            TreeNode new_code = new TreeNode(val);
            if (p.val < val) 
                p.right = new_code;
            else
                p.left = new_code;
            return root;
        }
        //递归法，函数终止条件,插入新节点
        public TreeNode insertIntoBST(TreeNode root, int val) {
            if (root == null)
                return new TreeNode(val);
            if (root.val > val)
                root.left = insertIntoBST(root.left, val);
            else
                root.right = insertIntoBST(root.right, val);
            return root;
        }
}

Num230 :二叉搜索树的第k小个元素

/** 题目描述:给定一个二叉搜索树，编写一个函数 kthSmallest 来查找其中第 k 个最小的元素
* 输入: root = [3,1,4,null,2], k = 1
*   3
* / \
* 1   4
* \
*   2
* 输出: 1
**/
class Solution {
    int ans =0,count=0;
    public int kthSmallest(TreeNode root, int k) {
        kthSmallests(root,k);
        return ans;
    }
    //中序遍历思想
    public void kthSmallests(TreeNode root,int k){
        if(root ==null)
            return ;
        kthSmallests(root.left,k);
        if(++count==k){
            ans = root.val;
            return;
        }
        kthSmallests(root.right,k);
    }
}

Num 687: 最大同值路径

/**题目描述:给定一个二叉树，找到最长的路径，这个路径中的每个节点具有相同值。 这条路径可以经过也可以不经过根节点
输入：         5       输出  ： 2
             / \
            4   5
           / \   \
          1   1   5
**/
class Solution {
    /** 三种情况: 1 在左子树中 2 在右子树中 3 左+根+右
    	递归思路:从根节点出发，依次遍历左、右子树,用left、right表示值
    	(1) 左子树不为空且值与根相等, 加1 ，否则当前左子树的值为0，右子树同理
    	(2) 用max记录当前最大值
    	(3) 递归返回值为当前左右子树中路径较大的值
    **/
    int max = 0;
    public int longestUnivaluePath(TreeNode root) {
        longestUnivaluePaths(root);
        return max;
    }
    public int  longestUnivaluePaths(TreeNode root){
        if(root==null)
            return 0;
        int left = longestUnivaluePaths(root.left);
        int right = longestUnivaluePaths(root.right);
        if(root.left!=null&&root.val==root.left.val)
            left= left + 1;
        else  left = 0;
        if(root.right!=null&&root.val==root.right.val)
            right=right+1;
        else  right = 0;
        max = Math.max(max,left+right);
        return Math.max(left,right);
    }
}

Num124 二叉树最大路径和

/**题目描述:给定一个非空二叉树，返回其最大路径和。本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。
	输入: [-10,9,20,null,null,15,7]
           -10
           / \
          9  20
            /  \
           15   7
    输出: 42
**/
class Solution {
    //1 根+左+右
    //2 左+根  3右+根 4 根
    int ans = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        maxPathSums(root);
        return ans;
    }
    public int maxPathSums(TreeNode root){
        if(root==null)
            return 0;
        int left_val = Math.max(maxPathSums(root.left),0);//负数直接用0代替
        int right_val =Math.max(maxPathSums(root.right),0);
        ans =Math.max(root.val+left_val+right_val,ans);
        return root.val+Math.max(left_val,right_val);
    }
}

二链表类

Num148:链表排序

/**
*题目描述：在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序
*输入: 4->2->1->3
*输出: 1->2->3->4
**/
class Solution {
    //归并排序思想
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null)//递归出口，只有一个节点或者没有节点
            return head;
        ListNode mid_node = get_mid_node(head);//得到中间节点
        ListNode right_head = mid_node.next;
        mid_node.next = null;
        return merge_List(sortList(head), sortList(right_head));
    }
    public ListNode get_mid_node(ListNode head) {//找链表的中间节点，快慢指针法
        if (head == null || head.next == null)
            return head;
        ListNode low_node = head, fast_node = head;
        while (fast_node.next != null && fast_node.next.next != null) {
            low_node = low_node.next;
            fast_node = fast_node.next.next;
        }
        return low_node;
    }
    public ListNode merge_List(ListNode p, ListNode q) {//合并p,q两个有序链表
        ListNode cur_p = p, cur_q = q, head;
        if (p.val < q.val) {
            head = p;
            cur_p = cur_p.next;
        } else {
            head = q;
            cur_q = cur_q.next;
        }
        ListNode cur = head;
        while (cur_q != null && cur_p != null) {
            if (cur_q.val < cur_p.val) {
                cur.next = cur_q;
                cur_q = cur_q.next;
                cur = cur.next;
            } else {
                cur.next = cur_p;
                cur_p = cur_p.next;
                cur = cur.next;
            }
        }
        if (cur_p != null)
            cur.next = cur_p;
        if (cur_q != null)
            cur.next = cur_q;
        return head;
    }
}

Num 92:反转部分链表

/**
*题目描述:反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
*输入: 1->2->3->4->5->NULL, m = 2, n = 4
*输出: 1->4->3->2->5->NULL
**/
class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
      ListNode root = new ListNode(0);
      ListNode cur = head,root_cur = root;
      int index = 1;
      while(index!=m){ //小于m的节点，尾插法
        root_cur.next = cur;
        root_cur=root_cur.next;
        cur=cur.next;
        index++;
      }
      ListNode temp = cur;//暂存当前节点的尾部，记录大于n之后的元素的前驱
      root_cur.next=null;
      //头插法
      while(index<=n){
          head = cur.next;
          cur.next=root_cur.next;
          root_cur.next =cur;
          cur = head;
         index++;
      }
      root_cur = temp;
      if(cur!=null)//n之后的直接插入
            root_cur.next = c;
      return root.next;  
    }
}

Num61: 旋转链表

/**	题目描述:给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数
	输入: 1->2->3->4->5->NULL, k = 2
	输出: 4->5->1->2->3->NULL
**/
class Solution {
    /** 分情况讨论：
        1 head ==null ||k%listnode.size()==0 直接返回结果
        2 找到链表的倒数第k个节点，将链表的前size-k个节点插入到链表的末尾
    **/
    public ListNode rotateRight(ListNode head, int k) {
        if(head==null)
            return head;
        int list_size = 0;
        ListNode cur =head;
        while(cur!=null){
            list_size++;
            cur=cur.next;
        }//求链表大小
        k = k%list_size;
        if(k==0)
            return head;
        ListNode k_node_last = find_last_k(head,k);//找到倒数第k个节点
        cur = k_node_last;
        while(cur.next!=null){
            cur=cur.next;
        }//到链表末尾
        while(head!=k_node_last){//前size-k个节点插入到后面
            cur.next = head;
            cur =head;
            head= head.next;
        }
        cur.next =null;//末尾指向空结点
        return k_node_last;
    }
    public ListNode find_last_k(ListNode head,int k){//找到倒数第k个节点
        ListNode cur=head,pre =head;
        int index = 0;
        while(++index<k){
            cur =cur.next;
        }
        while(cur.next!=null){
            pre =pre.next;
            cur =cur.next;
        }
        return pre;
    }

Num 86 :分割链表

1	/** 题目描述:给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。
2	* 输入: head = 1->4->3->2->5->2, x = 3
3	* 输出: 1->2->2->4->3->5
4	*/
5	class Solution {
6	/**
7	* 1 小于x的存到一个链表root中
8	* 2 大于等于x的放在原链表中
9	* 3 1-->2
10	**/
11	public ListNode partition(ListNode head, int x) {
12	if(head==null)
13	return head;
14	ListNode root = new ListNode(0);
15	ListNode cur = root,p = head,pre_p=head;
16	while(p!=null){
17	if(p.val<x){//小于x，赋值给新节点，并在原链表中删除该节点
18	ListNode temp =p.next;
19	if(p==head)//考虑首节点小于x,直接移动head
20	head = head.next;
21	else
22	pre_p.next = p.next;//删除p
23	cur.next = p;
24	cur = p;//尾插法插入小于x的节点到root中
25	p = temp;
26	}
27	else{//>=x,直接后移
28	pre_p = p;
29	p = p.next;
30	}
31	}
32	cur.next = head;//合并
33	return root.next;
34	}
35	}

Num114 二叉树转为链表

/**题目描述:给定一个二叉树，原地将它展开为链表。
例如，Input     Output   
    1  			1-2-3-4-5-6
   / \
  2   5
 / \   \
3   4   6
**/
class Solution {
    public void flatten(TreeNode root) {
       while(root!=null){
           //找到左孩子的最右边叶节点
           if(root.left==null)
                root=root.right;
            else{
                TreeNode last_right_node = root.left;//记录左孩子最右节点
                while(last_right_node.right!=null)
                    last_right_node=last_right_node.right;
                last_right_node.right = root.right;//将根节点的右子树插入到根的左孩子的最右节点
                root.right = root.left;//将最子树插入到根的右子树中
                root.left = null;//根的左孩子置为null
                root = root.right;
            }//end else
       }//end while
    }
   }
/**也可以用先序遍历思想，用栈保存右孩子
用一个变量保存上次遍历的节点，遍历一个节点将该节点放入pre的右子树中
左子树置为null**/

三数组类

数组类题目和树类题目大部分皆可用回溯思想解决问题，特此总结了一套回溯题目的写法模板。

借用全排列示意图(来源:https://leetcode-cn.com/problems/permutations/solution/hui-su-suan-fa-python-dai-ma-java-dai-ma-by-liweiw/)

   List<List<Integer>> res = new HashSet<>();
   public List<List<Integer>> findSubsequences(int[] nums) {
       List<Integer> tmp = new ArrayList<>();
       dfs(nums,0,tmp);
       return new ArrayList<>(res);
      }
public void dfs(int [] nums,int index,List<Integer> tmp){
       if(){//.....递归终止条件
       	return;
       }
       for(int i=index;i<nums.length;i++){
           tmp.add(nums[i]);//处理当前节点的需求
           dfs(nums,index*,tmp);//根据题目要求来选择index*
           tmp.remove(tmp.size()-1);//回溯
       }
   }

Num560:和位k的子数组

1	/**
2	*给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数
3	* Input:[3,4,7,2,-3,1,4,2] k = 7
4	* Output:4
5	**/
6	class Solution {
7	public int subarraySum(int[] nums, int k) {
8	HashMap<Integer,Integer> map = new HashMap<>();//key:累计和 value:出现的次数
9	map.put(0,1);//解决数组从第0个元素开始选择
10	int ans = 0,sum = 0;
11	for(int i=0;i<nums.length;i++){
12	sum+=nums[i];
13	//k = sum-(sum-k)
14	if(map.containsKey(sum-k)){//map中包含sum-k,即：当前的累计和sum减去sum-k的累计和等于k
15	ans+=map.get(sum-k);
16	}
17	map.put(sum,map.getOrDefault(sum,0)+1);
18	}
19	return ans;
20	}

Num1 两数之和

/**题目描述： 给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
Input: nums = [2, 7, 11, 15], target = 9
Output: [0, 1] **/
class Solution {
    public int[] twoSum(int[] nums, int target) {
     //Hashmap:key:元素值,value:数组下标
     HashMap<Integer,Integer> map = new HashMap<>();
     int[] res = new int[2];
     for(int i=0;i<nums.length;i++){
        if(map.containsKey(target-nums[i])){
            res[0]= i;
            res[1] =map.get(target-nums[i]);
            return res;
        }
        map.put(nums[i],i);
     }
    return res;
   }
}

Num15 三数之和

1	/**题目描述:给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组
2	Input:nums = [-1, 0, 1, 2, -1, -4]
3	Output: [[-1, 0, 1], [-1, -1, 2]]
4	**/
5	class Solution {
6	public List<List<Integer>> threeSum(int[] nums) {
7	List<List<Integer>> res =new ArrayList<>();
8	Arrays.sort(nums);
9	for(int k =0;k<nums.length-2;k++){
10	if(nums[k]>0) break;//值>0，则后面的值皆大于0，直接跳过
11	if(k>0&&nums[k]==nums[k-1]) continue;//跳过相同的值，因为此前已经将此值出现的结果存入,防止重复
12	int i = k+1,j= nums.length-1;//i指向k+1,j指向最后一个元素
13	while(i<j){
14	int sum = nums[k]+nums[i]+nums[j];
15	if(sum==0){
16	res.add(new ArrayList<>(Arrays.asList(nums[k], nums[i], nums[j])));
17	while(i<j&&nums[i]==nums[++i]);
18	while(i<j&&nums[j]==nums[--j]);
19	}
20	else if(sum<0){//小于0,i++,滤掉重复
21	while(i<j&&nums[i]==nums[++i]);
22	}
23	else//大于0,j--,滤掉重复
24	while(i<j&&nums[j]==nums[--j]);
25	}
26	}
27	return res;
28	}
29	}

Num18：四数之和

/**	题目描述:给定一个包含 n 个整数的数组 nums 和一个目标值 target
    判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？
    找出所有满足条件且不重复的四元组。
    Input:  nums = [1, 0, -1, 0, -2, 2],target = 0
    OutPut: [[-1,  0, 0, 1],  [-2, -1, 1, 2],  [-2,  0, 0, 2]]
**/
class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        //与三数之和类似,固定两个值,双指针指向固定两个值后的第一个和最后一个
        List<List<Integer>> res =new ArrayList<>();
        Arrays.sort(nums);
        HashSet<List<Integer>> set = new HashSet<>();
        for(int i = 0;i<nums.length-3;i++){//固定第一个值
            for(int j = i+1;j<nums.length-2;j++){//固定第二个值
                int left = j+1,right =nums.length-1;
                while(left<right){
                    int sum = nums[i]+nums[j]+nums[left]+nums[right];
                    if(sum<target)   left++;//小于target,left右移一位
                    else if(sum>target) right--;//大于target，right左移一位
                    else{
                        set.add(Arrays.asList(nums[i],nums[j],nums[left],nums[right]));//值存入set中,判断结果重复
                        left++;right--;
                    }
                }//end while
            }//end for j
        }//end for i
        res.addAll(set);
        return res;
    }
}

Num39 组合总和

// 回溯思想，三部曲
//1. 画递归树 2. 对递归树编码 3. 找出终止条件，回溯
class Solution {
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        if(candidates.length==0)
            return res;
        List<Integer> temp = new ArrayList<>();
        dfs(temp,candidates,target,0);
        return res;
    }
    public void dfs(List<Integer> temp, int [] candidates,int target,int begin){//为避免重复，每次从begin位置开始
            if(target<0)
                return;
            else if(target==0)
                res.add(new ArrayList<>(temp));
            else{
                for(int i=begin;i<candidates.length;i++){
                    temp.add(candidates[i]);
                    dfs(temp,candidates,target-candidates[i],i);
                    temp.remove(temp.size()-1);
                }
            }
    }
}

Num40 组合总和II

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        if(candidates.length==0)
            return res;
        List<Integer> temp = new ArrayList<>();
        Arrays.sort(candidates);//排序
        dfs(temp,candidates,target,0);
        return res;
    }
    public void dfs(List<Integer> temp, int [] candidates,int target,int begin){
            if(target<0)
                return;
            else if(target==0)
                res.add(new ArrayList<>(temp));
            else{
                for(int i=begin;i<candidates.length&&target-candidates[i]>=0;i++){
                    //排序后，相邻的元素[l,r]的解包含[l+1,r]的解
                    if(i!=begin&&candidates[i]==candidates[i-1]) continue;
                    temp.add(candidates[i]);
                    dfs(temp,candidates,target-candidates[i],i+1);//不能重复使用元素，故从i+1开始遍历
                    temp.remove(temp.size()-1);
               }
            }
    }
}

Num78 子集

//回溯
class Solution {
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> subsets(int[] nums) {
        if(nums.length==0)
            return res;
        List<Integer> temp = new ArrayList<>();
        res.add(new ArrayList<>(temp));
        dfs(temp,nums,0);
        return res;
    }
    public void dfs(List<Integer>temp, int [] nums,int start){
        if(start==nums.length)
            return;
        for(int i=start;i<nums.length;i++){
            temp.add(nums[i]);
            res.add(new ArrayList<>(temp));
            dfs(temp,nums,i+1);
            temp.remove(temp.size()-1);
        }
    }
}

1	// 以[1,2,3]为例用temp依次获取ans中的值，初始ans=[[]],记录当前ans的大小len并遍历，再依次在temp中加入当前nums[i]值后放入ans
2	/**(1)len=1,temp=[],加入nums[0],temp=[1],放入ans中,ans=[[],[1]]
3	(2) len=2,temp可以取[]和[1],加入nums[1],temp为[2]和[1,2],ans=[[],[1],[2],[1,2]]
4	(3) len =4 ,temp可以取[]、[1]、[2]、[1,2],依次加入nums[2],temp为[3]、[1,3]、[2,3]和[1,2,3],ans=[[]、[1]、[2]、[1,2],[3],[1,3],[2,3],[1,2,3]]
5	**/,
6	public List<List<Integer>> subsets(int[] nums) {
7	List<List<Integer>> ans = new ArrayList<>();
8	ans.add(new ArrayList<>());
9	for(int i =0;i<nums.length;i++){
10	List<Integer> temp;
11	int len = ans.size();//获取此时ans的长度
12	for(int j = 0;j<len;j++){
13	temp = new ArrayList<>(ans.get(j));//实例化中ans的每个值
14	temp.add(nums[i]);//加入当前值
15	ans.add(new ArrayList<>(temp));//放进ans中
16	}
17	}
18	return ans;
19	}

/**位运算
 * 求数组的所有子集
 * 位运算的思想 ，长度为n的数组共有2^n个子集，按1取数
 * 如5=101，即可以取第一个数和第3个数
 * 7=111，可以取第1、2、3个数
 */
private static ArrayList<ArrayList<Integer>> getSubset(ArrayList<Integer> list) {
        if (list.size() > 0) {
            ArrayList<ArrayList<Integer>> result = new ArrayList<>();
            for (int i = 1; i < Math.pow(2, list.size()); i++) {//长度为n的数组共有2^n个子集
                ArrayList<Integer> temp = new ArrayList<>();
                int index = i;//获取当前位
                for (int j = 0; j < list.size(); j++) {//n位数，二进制位共有n位，每位代表一个数
                    if ((index & 1) == 1) {
                        temp.add(list.get(j));
                    }
                    index >>= 1;
                }
                result.add(temp);
            }
            return result;
        } else {
            return null;
        }
    }

Num491 递增子序列

//回溯基本套路
class Solution {
   Set<List<Integer>> res = new HashSet<>();
   public List<List<Integer>> findSubsequences(int[] nums) {
       List<Integer> tmp = new ArrayList<>();
       dfs(nums,0,tmp);
       return new ArrayList<>(res);
      }
   public void dfs(int[] nums, int index, List<Integer> tmp) {
       if (tmp.size() > 1)//一次递归结束条件
           res.add(new ArrayList<>(tmp));
       for (int i = index; i < nums.length; i++) {
           if (!tmp.isEmpty() && nums[i] < tmp.get(tmp.size() - 1)) continue;
           tmp.add(nums[i]);
           dfs(nums, i + 1, tmp);
           tmp.remove(tmp.size() - 1);
       }
   }
}

Num1543 和为s的连续正数序列

//滑动窗口思想，维持一个[left,right)的滑动窗口
public int[][] findContinuousSequence(int target) { 
     List<int []> ans = new ArrayList<>();
     int left = 1,right=1;//左闭右开
     int sum = 0;//求和
     while (left <= target / 2) {
         if (sum < target) {//和小于target,right++;
             sum += right;
             right++;
         } else if (sum > target) {//和大于target，left--
             sum -= left;
             left++;
         } else {//等于，赋值
             int[] res = new int[right - left];
             for (int i = left; i < right; i++) {
                 res[i - left] = i;
             }
             ans.add(res);
             sum -= left;//复制完之后注意将总和减去left并将left右移一位
             left++;
         }
     }
     return ans.toArray(new int[ans.size()][]);
 }

Num698 划分k个相等的子集

//1求和 sum%k!=0 false;
//2 每项和为sum/k;
//3 转化为找出数组中和为target的子数组个数是否等于k
public boolean canPartitionKSubsets(int[] nums, int k) {
    int sum = 0, max = 0;
    for (int i = 0; i < nums.length; i++) {
        sum += nums[i];
        max = Math.max(max, nums[i]);
    }
    if (sum % k != 0 || max > sum / k)//sum%k!=0,或者最大值大于target,不能划分为k个子集
        return false;
    int target = sum / k;
    //一次遍历过程中，visited[i]只有在未被访问时才能被应用
    boolean[] visited = new boolean[nums.length];
    return dfs(nums, 0, 0, target, k, visited);
}
public boolean dfs(int[] nums, int start, int sum, int target, int k, boolean[] visited) {
    if (k == 0)//找到了k子集,返回true    
        return true;
    if (sum == target)//找到了其中一个子集，继续找下一个，k-1
        return dfs(nums, 0, 0, target, k - 1, visited);
    for (int i = start; i < nums.length; i++) {
        if (!visited[i] && sum + nums[i] <= target) {
            visited[i] = true;
            if (dfs(nums, start + 1, sum + nums[i], target, k, visited))//如果某次递归找到了k个子集，直接返回true
                return true;
            visited[i] = false;
        }
    }
    return false;
}

Num137 只出现一次的数字II

算例：

1	/**
2	假如例子是 1 2 6 1 1 2 2 3 3 3
3	1: 0 0 1
4	2: 0 1 0
5	6: 1 1 0
6	1: 0 0 1
7	1: 0 0 1
8	2: 0 1 0
9	2: 0 1 0
10	3: 0 1 1
11	3: 0 1 1
12	3: 0 1 1
13	第四列： 1001100111 有 6 个 1
14	第三列： 0110011111 有 7 个 1
15	第二列： 0010000 有 1 个 1
16	我们只需要把是 3 的倍数的对应列写 0，不是 3 的倍数的对应列写 1
17	也就是 1 1 0,也就是 6。
18	**/

1	//位运算思想
2	/**
3	1 对每一个数字的每一bit位进行累加
4	2 若当前bit位出现1的次数为3的倍数，说明包含该bit位的数字均出现过3次
5	3 否则该数字仅出现1次，对结果进行或运算，最终bit位1出现的次数不为3的倍数的总和即为所求的值
6	**/
7	public int singleNumber(int[] nums) {
8	int ans = 0;
9	for(int i=0;i<32;i++){
10	int cnt = 0;
11	for(int j=0;j<nums.length;j++){
12	cnt += (nums[j]>>>i&1)==1?1:0;
13	}
14	if(cnt%3!=0)
15	ans=ans\|1<<i;
16	}
17	return ans;
18	}

//位运算优化
public int singleNumber(int[] nums) {
	int one=0,two=0,three=0;
    for(int num:nums){
        //代表相应bit位出现1次数为2
        two|=one&num;
        //代表相应bit位出现次数为1
        one ^=num;
        //代表相应bit位出现次数为3
        three =one&two;
        //将出现次数为3bit位变成0
        one &=~three;
        two &=~three;
    }
    return one;
}

四字符串类

Num 3 无重复字符的最长子串

/**给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。
Input:	abcabcbb		bbbbb		pwwkew
Output:		3			 1			  3
**/
class Solution {
    //滑动窗口思想，每一个map中记录每个字符出现的位置
    public int lengthOfLongestSubstring(String s) {
        HashMap<Character,Integer> map =new HashMap<>();
        int res = 0;
        for(int i =0,left=0;i<s.length();i++){
            if(map.containsKey(s.charAt(i))){//已经含有该字符，更新left的位置
                left = Math.max(map.get(s.charAt(i)),left); 
            }
            res = Math.max(res,i-left+1);
            map.put(s.charAt(i),i+1);
        }
        return res;
    }
}

Num42 最长有效括号

//我的解法,效率低
 public int longestValidParentheses(String s) {
       Stack<Integer> stack = new Stack<>();
        List<Integer> list =new ArrayList<>();
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == ')') {
                if (!stack.isEmpty()) {
                    list.add(stack.peek());//添加(的下标
                    list.add(i);
                    stack.pop();
                }
            } else{
                stack.add(i);
            }
        }
        Collections.sort(list);
        //问题转化为求list两个数连续相差1的最大长度问题
        int res = 0, tmp = 0;
        for (int i = 1; i < list.size(); i++) {
            if (list.get(i) - list.get(i - 1) == 1) {
                if (tmp == 0)
                    tmp++;
                tmp++;
                
            } else {
                res = Math.max(res, tmp);
                tmp = 0;
            }
        }
        res = Math.max(res, tmp);
        return res;
    }

1	//栈的另一种解法,直接在出栈时求出最大长度
2	public int longestValidParentheses(String s) {
3	int res = 0;
4	Stack<Integer> stack = new Stack<>();
5	stack.push(-1);
6	for (int i = 0; i < s.length(); i++) {
7	if (s.charAt(i) == '(')//'(' 直接入当前(所在下标
8	stack.push(i);
9	else {//=')'直接出栈
10	stack.pop();
11	if (stack.isEmpty()) {//若此时栈中为空，代表之前所有的括号均以匹配完成，将当前下标入栈(与刚开始放入-1类似)
12	stack.push(i);
13	} else//若此时栈中拥有元素，更新最大长度
14	//比较res与(i-当前栈顶元素)即当前最大有效长度
15	res = Math.max(res, i - stack.peek());
16	}
17	}
18	return res;
19	}

1	//动态规划思想
2	public int longestValidParentheses(String s) {
3	int res = 0;
4	int[] dp = new int[s.length()];
5	for (int i = 1; i < s.length(); i++) {
6	if (s.charAt(i) == ')') {
7	if (s.charAt(i - 1) == '(') {//...(),前一个是( ,...的长度加上当前匹配上的括号长度
8	dp[i] = (i >= 2 ? dp[i - 2] + 2 : 2);
9	}
10	//需要找到i-1-dp[i-1],即前一个)所匹配的(前面的一个字符是不是()有效长度的
11	//如"()()(())" ,i=7时,i-1-dp[i-1]=4 s.charAt(4)='('，此时可以匹配为有效长度
12	else if (i - dp[i - 1] > 0 && s.charAt(i - dp[i - 1] - 1) == '(') {
13	//1((2)3) ，dp[i-1] 对应2,dp[i-2-dp[i-1]]对应1,+2对应3
14	dp[i] = (i - dp[i - 1] > 1 ? dp[i - dp[i - 1] - 2] : 0) + dp[i - 1] + 2;
15	}
16	res = Math.max(dp[i], res);
17	}
18	}
19	return res;
20	}
21	//reference: https://leetcode.wang/leetCode-32-Longest-Valid-Parentheses.html

Num22 括号生成

//DFS
 List<String> res = new ArrayList<>();
public List<String> generateParenthesis(int n) {
    String str="";
    dfs(n,0,0,str);
    return res;
}
public void dfs(int n,int left,int right,String str){
    if(left==n&&right==n){//左右括号均达到数量
        res.add(str);
        return;
    }
    if(left<right)//当前左括号数量少于右括号数量，剪枝
        return;
    if(left<n)
        dfs(n,left+1,right,str+"(");
    if(right<n)
        dfs(n,left,right+1,str+")");
}

1	/**
2	*题目描述：给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。
3	**/
4	class Solution {
5	List<List<Integer>> ans_path = new ArrayList<>();
6	List<Integer> node_path = new ArrayList<>();
7	public List<List<Integer>> pathSum(TreeNode root, int sum) {
8	path_sum(root,sum);
9	return ans_path;
10	}
11	//整体思路：回溯,先序遍历思想，根左右
12	public void path_sum(TreeNode root,int sum){
13	if(root==null)//空结点直接处理
14	return ;
15	node_path.add(root.val);
16	if(root.left==null&&root.right==null){//叶子节点
17	if(sum==root.val){//当前值等于路径值
18	ans_path.add(new ArrayList<>(node_path));
19	}
20	}
21	sum-=root.val;
22	if(root.left!=null)
23	path_sum(root.left,sum);
24	if(root.right!=null)
25	path_sum(root.right,sum);
26	node_path.remove(node_path.size()-1);//回溯
27	}
28	}

1	class Solution {
2	//迭代法
3	public TreeNode insertIntoBST(TreeNode root, int val) {
4	TreeNode cur = root, p = root;
5	while (cur != null) {
6	p = cur;
7	if (cur.val < val)
8	cur = cur.right;
9	else
10	cur = cur.left;
11	}
12	TreeNode new_code = new TreeNode(val);
13	if (p.val < val)
14	p.right = new_code;
15	else
16	p.left = new_code;
17	return root;
18	}
19	//递归法，函数终止条件,插入新节点
20	public TreeNode insertIntoBST(TreeNode root, int val) {
21	if (root == null)
22	return new TreeNode(val);
23	if (root.val > val)
24	root.left = insertIntoBST(root.left, val);
25	else
26	root.right = insertIntoBST(root.right, val);
27	return root;
28	}
29	}

1	/** 题目描述:给定一个二叉搜索树，编写一个函数 kthSmallest 来查找其中第 k 个最小的元素
2	* 输入: root = [3,1,4,null,2], k = 1
3	* 3
4	* / \
5	* 1 4
6	* \
7	* 2
8	* 输出: 1
9	**/
10	class Solution {
11	int ans =0,count=0;
12	public int kthSmallest(TreeNode root, int k) {
13	kthSmallests(root,k);
14	return ans;
15	}
16	//中序遍历思想
17	public void kthSmallests(TreeNode root,int k){
18	if(root ==null)
19	return ;
20	kthSmallests(root.left,k);
21	if(++count==k){
22	ans = root.val;
23	return;
24	}
25	kthSmallests(root.right,k);
26	}
27	}

1	/**题目描述:给定一个二叉树，找到最长的路径，这个路径中的每个节点具有相同值。这条路径可以经过也可以不经过根节点
2	输入： 5 输出： 2
3	/ \
4	4 5
5	/ \ \
6	1 1 5
7	**/
8	class Solution {
9	/** 三种情况: 1 在左子树中 2 在右子树中 3 左+根+右
10	递归思路:从根节点出发，依次遍历左、右子树,用left、right表示值
11	(1) 左子树不为空且值与根相等, 加1 ，否则当前左子树的值为0，右子树同理
12	(2) 用max记录当前最大值
13	(3) 递归返回值为当前左右子树中路径较大的值
14	**/
15	int max = 0;
16	public int longestUnivaluePath(TreeNode root) {
17	longestUnivaluePaths(root);
18	return max;
19	}
20	public int longestUnivaluePaths(TreeNode root){
21	if(root==null)
22	return 0;
23	int left = longestUnivaluePaths(root.left);
24	int right = longestUnivaluePaths(root.right);
25	if(root.left!=null&&root.val==root.left.val)
26	left= left + 1;
27	else left = 0;
28	if(root.right!=null&&root.val==root.right.val)
29	right=right+1;
30	else right = 0;
31	max = Math.max(max,left+right);
32	return Math.max(left,right);
33	}
34	}

1	/**题目描述:给定一个非空二叉树，返回其最大路径和。本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。
2	输入: [-10,9,20,null,null,15,7]
3	-10
4	/ \
5	9 20
6	/ \
7	15 7
8	输出: 42
9	**/
10	class Solution {
11	//1 根+左+右
12	//2 左+根 3右+根 4 根
13	int ans = Integer.MIN_VALUE;
14	public int maxPathSum(TreeNode root) {
15	maxPathSums(root);
16	return ans;
17	}
18	public int maxPathSums(TreeNode root){
19	if(root==null)
20	return 0;
21	int left_val = Math.max(maxPathSums(root.left),0);//负数直接用0代替
22	int right_val =Math.max(maxPathSums(root.right),0);
23	ans =Math.max(root.val+left_val+right_val,ans);
24	return root.val+Math.max(left_val,right_val);
25	}
26	}

1	/**
2	*题目描述：在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序
3	*输入: 4->2->1->3
4	*输出: 1->2->3->4
5	**/
6	class Solution {
7	//归并排序思想
8	public ListNode sortList(ListNode head) {
9	if (head == null \|\| head.next == null)//递归出口，只有一个节点或者没有节点
10	return head;
11	ListNode mid_node = get_mid_node(head);//得到中间节点
12	ListNode right_head = mid_node.next;
13	mid_node.next = null;
14	return merge_List(sortList(head), sortList(right_head));
15	}
16	public ListNode get_mid_node(ListNode head) {//找链表的中间节点，快慢指针法
17	if (head == null \|\| head.next == null)
18	return head;
19	ListNode low_node = head, fast_node = head;
20	while (fast_node.next != null && fast_node.next.next != null) {
21	low_node = low_node.next;
22	fast_node = fast_node.next.next;
23	}
24	return low_node;
25	}
26	public ListNode merge_List(ListNode p, ListNode q) {//合并p,q两个有序链表
27	ListNode cur_p = p, cur_q = q, head;
28	if (p.val < q.val) {
29	head = p;
30	cur_p = cur_p.next;
31	} else {
32	head = q;
33	cur_q = cur_q.next;
34	}
35	ListNode cur = head;
36	while (cur_q != null && cur_p != null) {
37	if (cur_q.val < cur_p.val) {
38	cur.next = cur_q;
39	cur_q = cur_q.next;
40	cur = cur.next;
41	} else {
42	cur.next = cur_p;
43	cur_p = cur_p.next;
44	cur = cur.next;
45	}
46	}
47	if (cur_p != null)
48	cur.next = cur_p;
49	if (cur_q != null)
50	cur.next = cur_q;
51	return head;
52	}
53	}

1	/**
2	*题目描述:反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
3	*输入: 1->2->3->4->5->NULL, m = 2, n = 4
4	*输出: 1->4->3->2->5->NULL
5	**/
6	class Solution {
7	public ListNode reverseBetween(ListNode head, int m, int n) {
8	ListNode root = new ListNode(0);
9	ListNode cur = head,root_cur = root;
10	int index = 1;
11	while(index!=m){ //小于m的节点，尾插法
12	root_cur.next = cur;
13	root_cur=root_cur.next;
14	cur=cur.next;
15	index++;
16	}
17	ListNode temp = cur;//暂存当前节点的尾部，记录大于n之后的元素的前驱
18	root_cur.next=null;
19	//头插法
20	while(index<=n){
21	head = cur.next;
22	cur.next=root_cur.next;
23	root_cur.next =cur;
24	cur = head;
25	index++;
26	}
27	root_cur = temp;
28	if(cur!=null)//n之后的直接插入
29	root_cur.next = c;
30	return root.next;
31	}
32	}

1	/** 题目描述:给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数
2	输入: 1->2->3->4->5->NULL, k = 2
3	输出: 4->5->1->2->3->NULL
4	**/
5	class Solution {
6	/** 分情况讨论：
7	1 head ==null \|\|k%listnode.size()==0 直接返回结果
8	2 找到链表的倒数第k个节点，将链表的前size-k个节点插入到链表的末尾
9	**/
10	public ListNode rotateRight(ListNode head, int k) {
11	if(head==null)
12	return head;
13	int list_size = 0;
14	ListNode cur =head;
15	while(cur!=null){
16	list_size++;
17	cur=cur.next;
18	}//求链表大小
19	k = k%list_size;
20	if(k==0)
21	return head;
22	ListNode k_node_last = find_last_k(head,k);//找到倒数第k个节点
23	cur = k_node_last;
24	while(cur.next!=null){
25	cur=cur.next;
26	}//到链表末尾
27	while(head!=k_node_last){//前size-k个节点插入到后面
28	cur.next = head;
29	cur =head;
30	head= head.next;
31	}
32	cur.next =null;//末尾指向空结点
33	return k_node_last;
34	}
35	public ListNode find_last_k(ListNode head,int k){//找到倒数第k个节点
36	ListNode cur=head,pre =head;
37	int index = 0;
38	while(++index<k){
39	cur =cur.next;
40	}
41	while(cur.next!=null){
42	pre =pre.next;
43	cur =cur.next;
44	}
45	return pre;
46	}

1	/**题目描述:给定一个二叉树，原地将它展开为链表。
2	例如，Input Output
3	1 1-2-3-4-5-6
4	/ \
5	2 5
6	/ \ \
7	3 4 6
8	**/
9	class Solution {
10	public void flatten(TreeNode root) {
11	while(root!=null){
12	//找到左孩子的最右边叶节点
13	if(root.left==null)
14	root=root.right;
15	else{
16	TreeNode last_right_node = root.left;//记录左孩子最右节点
17	while(last_right_node.right!=null)
18	last_right_node=last_right_node.right;
19	last_right_node.right = root.right;//将根节点的右子树插入到根的左孩子的最右节点
20	root.right = root.left;//将最子树插入到根的右子树中
21	root.left = null;//根的左孩子置为null
22	root = root.right;
23	}//end else
24	}//end while
25	}
26	}
27	/**也可以用先序遍历思想，用栈保存右孩子
28	用一个变量保存上次遍历的节点，遍历一个节点将该节点放入pre的右子树中
29	左子树置为null**/

1	List<List<Integer>> res = new HashSet<>();
2	public List<List<Integer>> findSubsequences(int[] nums) {
3	List<Integer> tmp = new ArrayList<>();
4	dfs(nums,0,tmp);
5	return new ArrayList<>(res);
6	}
7	public void dfs(int [] nums,int index,List<Integer> tmp){
8	if(){//.....递归终止条件
9	return;
10	}
11	for(int i=index;i<nums.length;i++){
12	tmp.add(nums[i]);//处理当前节点的需求
13	dfs(nums,index,tmp);//根据题目要求来选择index
14	tmp.remove(tmp.size()-1);//回溯
15	}
16	}

1	/**题目描述：给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。
2	Input: nums = [2, 7, 11, 15], target = 9
3	Output: [0, 1] **/
4	class Solution {
5	public int[] twoSum(int[] nums, int target) {
6	//Hashmap:key:元素值,value:数组下标
7	HashMap<Integer,Integer> map = new HashMap<>();
8	int[] res = new int[2];
9	for(int i=0;i<nums.length;i++){
10	if(map.containsKey(target-nums[i])){
11	res[0]= i;
12	res[1] =map.get(target-nums[i]);
13	return res;
14	}
15	map.put(nums[i],i);
16	}
17	return res;
18	}
19	}

1	/** 题目描述:给定一个包含 n 个整数的数组 nums 和一个目标值 target
2	判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？
3	找出所有满足条件且不重复的四元组。
4	Input: nums = [1, 0, -1, 0, -2, 2],target = 0
5	OutPut: [[-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2]]
6	**/
7	class Solution {
8	public List<List<Integer>> fourSum(int[] nums, int target) {
9	//与三数之和类似,固定两个值,双指针指向固定两个值后的第一个和最后一个
10	List<List<Integer>> res =new ArrayList<>();
11	Arrays.sort(nums);
12	HashSet<List<Integer>> set = new HashSet<>();
13	for(int i = 0;i<nums.length-3;i++){//固定第一个值
14	for(int j = i+1;j<nums.length-2;j++){//固定第二个值
15	int left = j+1,right =nums.length-1;
16	while(left<right){
17	int sum = nums[i]+nums[j]+nums[left]+nums[right];
18	if(sum<target) left++;//小于target,left右移一位
19	else if(sum>target) right--;//大于target，right左移一位
20	else{
21	set.add(Arrays.asList(nums[i],nums[j],nums[left],nums[right]));//值存入set中,判断结果重复
22	left++;right--;
23	}
24	}//end while
25	}//end for j
26	}//end for i
27	res.addAll(set);
28	return res;
29	}
30	}

1	// 回溯思想，三部曲
2	//1. 画递归树 2. 对递归树编码 3. 找出终止条件，回溯
3	class Solution {
4	List<List<Integer>> res = new ArrayList<>();
5	public List<List<Integer>> combinationSum(int[] candidates, int target) {
6	if(candidates.length==0)
7	return res;
8	List<Integer> temp = new ArrayList<>();
9	dfs(temp,candidates,target,0);
10	return res;
11	}
12	public void dfs(List<Integer> temp, int [] candidates,int target,int begin){//为避免重复，每次从begin位置开始
13	if(target<0)
14	return;
15	else if(target==0)
16	res.add(new ArrayList<>(temp));
17	else{
18	for(int i=begin;i<candidates.length;i++){
19	temp.add(candidates[i]);
20	dfs(temp,candidates,target-candidates[i],i);
21	temp.remove(temp.size()-1);
22	}
23	}
24	}
25	}

1	//回溯
2	class Solution {
3	List<List<Integer>> res = new ArrayList<>();
4	public List<List<Integer>> subsets(int[] nums) {
5	if(nums.length==0)
6	return res;
7	List<Integer> temp = new ArrayList<>();
8	res.add(new ArrayList<>(temp));
9	dfs(temp,nums,0);
10	return res;
11	}
12	public void dfs(List<Integer>temp, int [] nums,int start){
13	if(start==nums.length)
14	return;
15	for(int i=start;i<nums.length;i++){
16	temp.add(nums[i]);
17	res.add(new ArrayList<>(temp));
18	dfs(temp,nums,i+1);
19	temp.remove(temp.size()-1);
20	}
21	}
22	}

1	/**位运算
2	* 求数组的所有子集
3	* 位运算的思想，长度为n的数组共有2^n个子集，按1取数
4	* 如5=101，即可以取第一个数和第3个数
5	* 7=111，可以取第1、2、3个数
6	*/
7	private static ArrayList<ArrayList<Integer>> getSubset(ArrayList<Integer> list) {
8	if (list.size() > 0) {
9	ArrayList<ArrayList<Integer>> result = new ArrayList<>();
10	for (int i = 1; i < Math.pow(2, list.size()); i++) {//长度为n的数组共有2^n个子集
11	ArrayList<Integer> temp = new ArrayList<>();
12	int index = i;//获取当前位
13	for (int j = 0; j < list.size(); j++) {//n位数，二进制位共有n位，每位代表一个数
14	if ((index & 1) == 1) {
15	temp.add(list.get(j));
16	}
17	index >>= 1;
18	}
19	result.add(temp);
20	}
21	return result;
22	} else {
23	return null;
24	}
25	}

1	//回溯基本套路
2	class Solution {
3	Set<List<Integer>> res = new HashSet<>();
4	public List<List<Integer>> findSubsequences(int[] nums) {
5	List<Integer> tmp = new ArrayList<>();
6	dfs(nums,0,tmp);
7	return new ArrayList<>(res);
8	}
9	public void dfs(int[] nums, int index, List<Integer> tmp) {
10	if (tmp.size() > 1)//一次递归结束条件
11	res.add(new ArrayList<>(tmp));
12	for (int i = index; i < nums.length; i++) {
13	if (!tmp.isEmpty() && nums[i] < tmp.get(tmp.size() - 1)) continue;
14	tmp.add(nums[i]);
15	dfs(nums, i + 1, tmp);
16	tmp.remove(tmp.size() - 1);
17	}
18	}
19	}

1	//滑动窗口思想，维持一个[left,right)的滑动窗口
2	public int[][] findContinuousSequence(int target) {
3	List<int []> ans = new ArrayList<>();
4	int left = 1,right=1;//左闭右开
5	int sum = 0;//求和
6	while (left <= target / 2) {
7	if (sum < target) {//和小于target,right++;
8	sum += right;
9	right++;
10	} else if (sum > target) {//和大于target，left--
11	sum -= left;
12	left++;
13	} else {//等于，赋值
14	int[] res = new int[right - left];
15	for (int i = left; i < right; i++) {
16	res[i - left] = i;
17	}
18	ans.add(res);
19	sum -= left;//复制完之后注意将总和减去left并将left右移一位
20	left++;
21	}
22	}
23	return ans.toArray(new int[ans.size()][]);
24	}

1	//1求和 sum%k!=0 false;
2	//2 每项和为sum/k;
3	//3 转化为找出数组中和为target的子数组个数是否等于k
4	public boolean canPartitionKSubsets(int[] nums, int k) {
5	int sum = 0, max = 0;
6	for (int i = 0; i < nums.length; i++) {
7	sum += nums[i];
8	max = Math.max(max, nums[i]);
9	}
10	if (sum % k != 0 \|\| max > sum / k)//sum%k!=0,或者最大值大于target,不能划分为k个子集
11	return false;
12	int target = sum / k;
13	//一次遍历过程中，visited[i]只有在未被访问时才能被应用
14	boolean[] visited = new boolean[nums.length];
15	return dfs(nums, 0, 0, target, k, visited);
16	}
17	public boolean dfs(int[] nums, int start, int sum, int target, int k, boolean[] visited) {
18	if (k == 0)//找到了k子集,返回true
19	return true;
20	if (sum == target)//找到了其中一个子集，继续找下一个，k-1
21	return dfs(nums, 0, 0, target, k - 1, visited);
22	for (int i = start; i < nums.length; i++) {
23	if (!visited[i] && sum + nums[i] <= target) {
24	visited[i] = true;
25	if (dfs(nums, start + 1, sum + nums[i], target, k, visited))//如果某次递归找到了k个子集，直接返回true
26	return true;
27	visited[i] = false;
28	}
29	}
30	return false;
31	}

1	//位运算优化
2	public int singleNumber(int[] nums) {
3	int one=0,two=0,three=0;
4	for(int num:nums){
5	//代表相应bit位出现1次数为2
6	two\|=one&num;
7	//代表相应bit位出现次数为1
8	one ^=num;
9	//代表相应bit位出现次数为3
10	three =one&two;
11	//将出现次数为3bit位变成0
12	one &=~three;
13	two &=~three;
14	}
15	return one;
16	}

1	/**给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。
2	Input: abcabcbb bbbbb pwwkew
3	Output: 3 1 3
4	**/
5	class Solution {
6	//滑动窗口思想，每一个map中记录每个字符出现的位置
7	public int lengthOfLongestSubstring(String s) {
8	HashMap<Character,Integer> map =new HashMap<>();
9	int res = 0;
10	for(int i =0,left=0;i<s.length();i++){
11	if(map.containsKey(s.charAt(i))){//已经含有该字符，更新left的位置
12	left = Math.max(map.get(s.charAt(i)),left);
13	}
14	res = Math.max(res,i-left+1);
15	map.put(s.charAt(i),i+1);
16	}
17	return res;
18	}
19	}

一 二叉树类

Num 113:路径总和

Num 129:根节点到叶子节点之和

Num 701: 二叉搜索树的插入操作

Num230 :二叉搜索树的第k小个元素

Num 687: 最大同值路径

Num124 二叉树最大路径和

二 链表类

Num148:链表排序

Num 92:反转部分链表

Num61: 旋转链表

Num 86 :分割链表

Num114 二叉树转为链表

三 数组类

Num560:和位k的子数组

Num1 两数之和

Num15 三数之和

Num18：四数之和

Num39 组合总和

Num40 组合总和II

Num78 子集

Num491 递增子序列

Num1543 和为s的连续正数序列

Num698 划分k个相等的子集

Num137 只出现一次的数字II

四 字符串类

Num 3 无重复字符的最长子串

Num42 最长有效括号

Num22 括号生成

一二叉树类

二链表类

三数组类

四字符串类

1	//我的解法,效率低
2	public int longestValidParentheses(String s) {
3	Stack<Integer> stack = new Stack<>();
4	List<Integer> list =new ArrayList<>();
5	for (int i = 0; i < s.length(); i++) {
6	if (s.charAt(i) == ')') {
7	if (!stack.isEmpty()) {
8	list.add(stack.peek());//添加(的下标
9	list.add(i);
10	stack.pop();
11	}
12	} else{
13	stack.add(i);
14	}
15	}
16	Collections.sort(list);
17	//问题转化为求list两个数连续相差1的最大长度问题
18	int res = 0, tmp = 0;
19	for (int i = 1; i < list.size(); i++) {
20	if (list.get(i) - list.get(i - 1) == 1) {
21	if (tmp == 0)
22	tmp++;
23	tmp++;
24
25	} else {
26	res = Math.max(res, tmp);
27	tmp = 0;
28	}
29	}
30	res = Math.max(res, tmp);
31	return res;
32	}

1	//DFS
2	List<String> res = new ArrayList<>();
3	public List<String> generateParenthesis(int n) {
4	String str="";
5	dfs(n,0,0,str);
6	return res;
7	}
8	public void dfs(int n,int left,int right,String str){
9	if(left==n&&right==n){//左右括号均达到数量
10	res.add(str);
11	return;
12	}
13	if(left<right)//当前左括号数量少于右括号数量，剪枝
14	return;
15	if(left<n)
16	dfs(n,left+1,right,str+"(");
17	if(right<n)
18	dfs(n,left,right+1,str+")");
19	}