leetcode算法

LRU缓存

https://leetcode-cn.com/problems/lru-cache-lcci/

class LRUCache extends LinkedHashMap<Integer, Integer> {
    private int capacity;
    public LRUCache(int capacity) {
       super(capacity,0.75f,true);
       this.capacity=capacity;
    }
    
    public int get(int key) {
       return super.getOrDefault(key,-1);
    }
    
    public void put(int key, int value) {
        super.put(key, value);
    }
    @Override
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
        return size() > capacity; 
    }
 

}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */

---

46全排列

给定一个 没有重复 数字的序列，返回其所有可能的全排列。

https://leetcode-cn.com/problems/permutations/

class Solution {
    List<List<Integer>> results = new ArrayList<>();
    public List<List<Integer>> permute(int[] nums) {
        LinkedList<Integer> result = new LinkedList<Integer>();
        backtrack(nums,result);
        return results;
    }

    public void backtrack(int[] nums,LinkedList<Integer> result){
        if(result.size() == nums.length) {
            results.add(new LinkedList(result));
            return;
        }

        for(int i=0;i<nums.length;i++){
            if(result.contains(nums[i])) continue;
            result.add(nums[i]);
            backtrack(nums,result);
            result.removeLast();
        }

    }



}

---

78子集

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

https://leetcode-cn.com/problems/subsets/

class Solution {
   List<List<Integer>> results = new ArrayList<>();
    public List<List<Integer>> subsets(int[] nums) {
        LinkedList<Integer> result = new LinkedList<Integer>();
       
        backtrack(nums,result,0);
        return results;
    }

    public void backtrack(int[] nums,LinkedList<Integer> result,int start){


        for(int i=start;i<nums.length;i++){
            result.add(nums[i]);
            backtrack(nums,result,i+1);
            result.removeLast();
        }
       results.add(new LinkedList(result));
    }
}

494目标和

https://leetcode-cn.com/problems/target-sum/solution/

双指针类型， 二叉树的路径和 ，左节点是加，右节点是减

class Solution {
    int count=0;
    public int findTargetSumWays(int[] nums, int S) {
       backtrack(nums,S,0);
        return count;
    }

    public void backtrack(int[] nums,int S,int start){
        if (S==0 && nums.length==start ){
            count++;
            return;
        }
        if (start < nums.length){
            backtrack(nums,S+nums[start],start+1);
            backtrack(nums,S-nums[start],start+1);
        }
    }
}

26删除有序数组中的重复项

https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/

双指针类型

//输入：nums = [0,0,1,1,1,2,2,3,3,4]输出：5, nums = [0,1,2,3,4]

class Solution {
    public int removeDuplicates(int[] nums) {
        //双指针
        if (nums.length<2) return nums.length;
        int slow=0,fast=1;
        while (fast<nums.length){
            if (nums[fast] == nums[slow]){
                fast++;
            } else {
                nums[++slow]=nums[fast++];
            }
        }
        return slow+1;
    }
}

24 两两交换链表中的节点

给定 1->2->3->4, 你应该返回 2->1->4->3.

https://leetcode-cn.com/problems/swap-nodes-in-pairs/

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) {
           return reverseKGroup(head,2);
    }

    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode temp = head;
//       先用temp找到3的位置，不足，就返回head不反转
        for(int i=1;i<k && temp!=null;i++){
            temp=temp.next;
        }
        if (temp == null) return head;
//        用t2记录记录4的位置，把三四断开
        ListNode  t2 = temp.next;
        temp.next=null;
//        反转前部分，头部设置为newHead，此时head在3的位置了
        ListNode newHead = reListNode(head);
//        把1-2-3与后面的连接起来，后面的继续递归：head.next=reverseKGroup(t2,k);
        head.next=reverseKGroup(t2,k);
        return newHead;
    }

    private ListNode reListNode(ListNode head){
        ListNode next=null;
        ListNode pre=null;
        while (head!=null){
            next=head.next;
            head.next=pre;
            pre=head;
            head=next;

        }
        return pre;
    }
}

110. 平衡二叉树

给定一个二叉树，判断它是否是高度平衡的二叉树。

https://leetcode-cn.com/problems/balanced-binary-tree/

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isBalanced(TreeNode root) {
         if(root==null) return true;
         int l= getH(root.left);
         int r=getH(root.right);
         int abs =Math.abs(l-r);
         if(abs>1) return false;
         return isBalanced(root.left) && isBalanced(root.right);
    }
    public int getH(TreeNode root){
        if(root==null) return 0;
        int left = getH(root.left);
        int right = getH(root.right);
        int result = left>right?left+1:right+1;
        return result;
    }
}

53. 最大子序和

class Solution {
    public int maxSubArray(int[] nums) {
        //贪心算法， 前i-1个最大值是max，第i-1个前连续最大值为sum
        if(nums.length<1) return Integer.MIN_VALUE;
        int sum=nums[0]; //前i-1个最大值
        int max=sum;
        for(int i=1;i<nums.length;i++){
          if(sum<0){
        	  sum=nums[i];
          }else{
        	  sum+=nums[i];
          }
          max=Math.max(sum, max);
        }
        
        return max;
    }
}

25. K 个一组翻转链表

/**
 * 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 temp = head;
        for(int i=1;i<k && temp!=null;i++){
            temp=temp.next;
        }
        if (temp == null) return head;
        ListNode  t2 = temp.next;
        temp.next=null;
        ListNode newHead = reListNode(head);
        head.next=reverseKGroup(t2,k);
        return newHead;
    }

    private ListNode reListNode(ListNode head){
        ListNode next=null;
        ListNode pre=null;
        while (head!=null){
            next=head.next;
            head.next=pre;
            pre=head;
            head=next;

        }
        return pre;
    }
}

451. 根据字符出现频率排序

https://leetcode-cn.com/problems/sort-characters-by-frequency/

class Solution {
    public String frequencySort(String s) {
        TreeMap<Character,Integer> map =new TreeMap<Character, Integer>();
        char[] chars =s.toCharArray();
        for (char num : chars){
            if (map.containsKey(num)){
                map.put(num,map.get(num)+1);
            }else {
                map.put(num,1);
            }
        }

        List<Map.Entry<Character, Integer>> list = new ArrayList<Map.Entry<Character, Integer>>(map.entrySet());

        Collections.sort(list,new Comparator<Map.Entry<Character,Integer>>() {
            @Override
            public int compare(Map.Entry<Character, Integer> o1, Map.Entry<Character, Integer> o2) {
                return o2.getValue().compareTo(o1.getValue());
            }
        });
        StringBuilder sb = new StringBuilder();
        for (int i=0;i<list.size();i++){
            Map.Entry<Character,Integer> entry =list.get(i);
            int value=entry.getValue();
            while (value-->0) sb.append(entry.getKey());
        }
        return sb.toString();
    }
}

347. 前 K 个高频元素

https://leetcode-cn.com/problems/top-k-frequent-elements/

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
         int[] result = new int[k];
         TreeMap<Integer,Integer> map =new TreeMap<Integer, Integer>();
        for (int num : nums){
             if (map.containsKey(num)){
                 map.put(num,map.get(num)+1);
             }else {
                 map.put(num,1);
             }
         }

        List<Map.Entry<Integer, Integer>> list = new ArrayList<Map.Entry<Integer, Integer>>(map.entrySet());

        Collections.sort(list,new Comparator<Map.Entry<Integer,Integer>>() {
            @Override
            public int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2) {
                return o2.getValue().compareTo(o1.getValue());
            }
        });
         for(int i=0;i<k;i++){
             result[i] = list.get(i).getKey();
         }
         return  result;
    }
}

414. 第三大的数

https://leetcode-cn.com/problems/third-maximum-number/

class Solution {
    public int thirdMax(int[] nums) {
        PriorityQueue<Integer> queue = new PriorityQueue<Integer>();
        for (int num :nums){
            if (!queue.contains(num)){
                queue.add(num);
            }
            if (queue.size()>3) queue.poll();
        }

        if(queue.size()<3){
            while (queue.size()>1) queue.poll();
            return queue.peek();
        }else{
            return queue.peek();
        }
        
    }
}

703. 数据流中的第K大元素

https://leetcode-cn.com/problems/kth-largest-element-in-a-stream/

class KthLargest {
    private PriorityQueue<Integer> queue;
    private int k;
    public KthLargest(int k, int[] nums) {
       queue = new PriorityQueue<Integer>(k);
       this.k=k;
       for (int num :nums){
           queue.add(num);
           if (queue.size()>k) queue.poll();
       }
    }
    
    public int add(int val) {
        queue.add(val);
        if (queue.size()>k) queue.poll();
        return queue.peek();
    }
}

/**
 * Your KthLargest object will be instantiated and called as such:
 * KthLargest obj = new KthLargest(k, nums);
 * int param_1 = obj.add(val);
 */

---

第 k 个数

有些数的素因子只有 3，5，7，请设计一个算法找出第 k 个数。注意，不是必须有这些素因子，而是必须不包含其他的素因子。例如，前几个数按顺序应该是 1，3，5，7，9，15，21。

https://leetcode-cn.com/problems/get-kth-magic-number-lcci\

class Solution {
    public int getKthMagicNumber(int k) {
        Queue<Long> queue = new PriorityQueue();
        HashSet<Long> set = new HashSet<Long>();
        queue.add(1l);
        while (true){
            Long temp=queue.poll();
            if (!set.contains(temp)){
                set.add(temp);
                queue.add(temp*3);
                queue.add(temp*5);
                queue.add(temp*7);
            }
            if (set.size()==k) return temp.intValue();
        }
    }
}

215. 数组中的第K个最大元素

在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> queue = new PriorityQueue();
        for (int num : nums){
            queue.add(num);
            if (queue.size()>k) queue.poll();
        }
        return queue.peek();
    }
}

121. 买卖股票的最佳时机

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。

注意：你不能在买入股票前卖出股票。
https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock

class Solution {
    public int maxProfit(int[] prices) {
    	if(prices.length<1) return 0;
    	int max=0; //前i个最大利润
    	int minI=prices[0];//前i-1个最小值
    	for(int i = 1 ;i < prices.length ;i++){
    		minI=minI<prices[i]?minI:prices[i];
    		max=max>prices[i]-minI? max :prices[i]-minI;
    	}
    	
		return max;
    }
}

122. 买卖股票的最佳时机 II

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii

class Solution {
    public int maxProfit(int[] prices) {
        if(prices.length<2) return 0;
    	int max=0; //相邻利润的总和
    	for(int i = 1 ;i < prices.length ;i++){
    		max=prices[i]-prices[i-1]>0?max+prices[i]-prices[i-1]:max;
    	}
		return max;
    }
}

70. 爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

class Solution {
    public int climbStairs(int n) {
          	if(n<1) return 0;
    	else if(n==1) return 1;
    	else if(n==2) return 2;
    	else if(n==3) return 3;
    	else{
    	  int[] dp = new int[n];
    	  dp[0]=1;
    	  dp[1]=2;
    	  dp[2]=3;
    	  for(int i=3;i<n;i++){
    		  dp[i]=dp[i-1]+dp[i-2];
    	  }
    	  return dp[n-1];
    	}
    	
    }
}

跳水板

你正在使用一堆木板建造跳水板。有两种类型的木板，其中长度较短的木板长度为shorter，长度较长的木板长度为longer。你必须正好使用k块木板。编写一个方法，生成跳水板所有可能的长度。

返回的长度需要从小到大排列。
链接：https://leetcode-cn.com/problems/diving-board-lcci

class Solution {
    public int[] divingBoard(int shorter, int longer, int k) {
    	if(k==0){
    		return new int[]{};
    	}else if(shorter == longer ||k==0){
    		return new int[]{shorter*k};
    	}else{
    		TreeSet<Integer> set = new TreeSet<Integer>();
    		for(int i=1;i<=k;i++){
    			int t=k-i;
    			set.add(i*shorter+t*longer);
                set.add(t*shorter+i*longer);
    		}
            
    		int[] result = new int[set.size()];
    		Iterator<Integer> iterator=set.iterator();
    		int i=0;
    		while(iterator.hasNext()){
    			result[i++]=iterator.next();
    		}
    		return result;
    		
    	}

    }
}

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

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/

class Solution {
    public int lengthOfLongestSubstring(String s) {
    	int maxLen=1;
    	if(s.length()<1) return 0;
    	else if(s.length()==1) return 1;
    	
    	for(int i=0;i<s.length()-1;i++){//从第一个开始
    		List<Character> list=new ArrayList<Character>();
    		list.add(s.charAt(i));
    		//i开始的 n个不重复的子序列
    		for(int j=i+1;j<s.length();j++){
    			if(list.contains(s.charAt(j))){
    				break;
    			}else{
    				list.add(s.charAt(j));
    			}
    		}
    		
    		maxLen=maxLen>list.size()?maxLen:list.size();
    		
    	}
		return maxLen;
        
    }
}

20. 有效的括号

给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
链接：https://leetcode-cn.com/problems/valid-parentheses

class Solution {
    public boolean isValid(String s) {
    	int len = s.length();
    	//个数是单数，就闭合不了
    	if(len%2==1) return false;
    	Stack<Character> stack = new Stack<Character>();
    	for(int i=0 ; i < len ; i++){
    		char ch = s.charAt(i);
    		if(ch=='(' || ch=='{' || ch=='['){
    			stack.add(ch);
    		}else{
    			//判断栈顶元素是否匹配
    			if(stack.isEmpty()) return false;
    				
    			char topC = stack.pop();
    			if( topC =='(') topC=')';
    			   else if(topC=='{') topC='}';
    			   else if(topC=='[') topC=']';
    			
    			if(topC!=ch) return false;
    		}
    		
    	}
    	if(stack.isEmpty())
		   return true;
    	else return false;
        
    }

}

32. 最长有效括号

给定一个只包含 ‘(‘ 和 ‘)’ 的字符串，找出最长的包含有效括号的子串的长度。

class Solution {
    public int longestValidParentheses(String s) {
    	int max = 0;
    	Stack<Integer> stack = new Stack<Integer>();
    	stack.add(-1);
    	for(int i=0;i<s.length();i++ ){
    		char ch = s.charAt(i);
    		if(ch == '(') {
    			stack.add(i);
    		}else{
    			
    		    stack.pop();
    		    if(stack.isEmpty()) stack.add(i);

    			max = Math.max(max, i-stack.peek());
    		}
    	}
    			
		return max;
        
    }


}

链表求和

输入：(7 -> 1 -> 6) + (5 -> 9 -> 2)，即617 + 295
输出：2 -> 1 -> 9，即912

输入：(6 -> 1 -> 7) + (2 -> 9 -> 5)，即617 + 295
输出：9 -> 1 -> 2，即912

https://leetcode-cn.com/problems/sum-lists-lcci/submissions/

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    	if(l1 == null) return l2;
    	else if(l2 == null) return l1;
    	else{
    		int forward =0;
    		ListNode head = null,p = null;
    		boolean first =true;
    		while(l1 !=null || l2 !=null){
    			if(l1!=null) {
    				forward +=l1.val;
    				l1=l1.next;
    			}
    			if(l2!=null) {
    				forward +=l2.val;
    				l2=l2.next;
    			}
                if(first){
        			p= new ListNode(forward%10);
        			forward/=10;
        			head=p;
        			first=false;
                }else{
        			p.next= new ListNode(forward%10);
        			forward/=10;
        			p=p.next;
                }
    			
    		}
    		if(forward>0) p.next=new ListNode(forward);
    		return head;
    	}
    } 
    
}   

540. 有序数组中的单一元素

给定一个只包含整数的有序数组，每个元素都会出现两次，唯有一个数只会出现一次，找出这个数。

class Solution {
    public int singleNonDuplicate(int[] nums) {
        for(int i=0;i<nums.length-1;i+=2){
            if(nums[i]!=nums[i+1]){
                return nums[i];
            }
        }
       return nums[nums.length-1];
    }
}

455. 分发饼干

假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。对每个孩子 i ，都有一个胃口值 gi ，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j ，都有一个尺寸 sj 。如果 sj >= gi ，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。

输入: [1,2,3], [1,1]

输出: 1

解释:
你有三个孩子和两块小饼干，3个孩子的胃口值分别是：1,2,3。
虽然你有两块小饼干，由于他们的尺寸都是1，你只能让胃口值是1的孩子满足。
所以你应该输出1。
链接：https://leetcode-cn.com/problems/assign-cookies

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int gi=0,si=0;
        while(gi<g.length&&si<s.length){
        	if(g[gi]<=s[si]){//满足
        		gi++;
        		si++;
        	}else{
        		si++;
        	}
        }
        return gi;
    }
}

452. 用最少数量的箭引爆气球

输入:
[[10,16], [2,8], [1,6], [7,12]]

输出:
2

解释:
对于该样例，我们可以在x = 6（射爆[2,8],[1,6]两个气球）和 x = 11（射爆另外两个气球）。
链接：https://leetcode-cn.com/problems/minimum-number-of-arrows-to-burst-balloons

class Solution {
    public int findMinArrowShots(int[][] points) {
    	if(points.length<1) return 0;
        Arrays.sort(points, (a,b) ->(a[1]-b[1]));
        int count=1;
        int temp=points[0][1];
        for(int i=1;i<points.length;i++){
        	if(temp>=points[i][0]){
        		continue;
        	}
        	
        	temp=points[i][1];
        	count++;
        }
         return count;
    }
}

605. 种花问题

输入: flowerbed = [1,0,0,0,1], n = 1
输出: True

输入: flowerbed = [1,0,0,0,1], n = 2
输出: False

数组内已种好的花不会违反种植规则。
输入的数组长度范围为 [1, 20000]。
n 是非负整数，且不会超过输入数组的大小。

class Solution {
    public boolean canPlaceFlowers(int[] flowerbed, int n) {
     	for(int i=0;i<flowerbed.length;i++){
    		if(flowerbed[i]==1) continue;
    		int pre=i>0?flowerbed[i-1]:0;
    		int next=(i+1)<flowerbed.length?flowerbed[i+1]:0;
    		if(pre==0&&next==0){
    			n--;
    			if(n<=0) return true;
    			flowerbed[i]=1;
    			
    		}
    	}
        return n<=0?true:false;
    }
}

665. 非递减数列

输入: nums = [4,2,3]
输出: true
解释: 你可以通过把第一个4变成1来使得它成为一个非递减数列。

输入: nums = [4,2,1]
输出: false
解释: 你不能在只改变一个元素的情况下将其变为非递减数列。

class Solution {
    public boolean checkPossibility(int[] nums) {
    	int count=0;
    	for(int i=1;i<nums.length;i++){
    		if(nums[i-1]>nums[i]){
    			count++;
    			if(i-2>=0&&nums[i-2]>nums[i]){
    				 nums[i]=nums[i-1];
    			}
    			else{
    				nums[i-1]=nums[i];
    			}
    			
    		}
    	}
    	
        return count<=1;
    }
}

392. 判断子序列

示例 1:
s = “abc”, t = “ahbgdc”

返回 true.

示例 2:
s = “axc”, t = “ahbgdc”

返回 false.
链接：https://leetcode-cn.com/problems/is-subsequence

class Solution {
    public boolean isSubsequence(String s, String t) {
       int i=0,j=0,sl=s.length(),tl=t.length();
       while(i<sl&&j<tl){
    	   if(s.charAt(i)==t.charAt(j)){
    		   i++;
    	   }
    	   j++;
       }
    	   
      return i==sl;  
    }
}

763. 划分字母区间

输入：S = “ababcbacadefegdehijhklij”
输出：[9,7,8]
解释：
划分结果为 “ababcbaca”, “defegde”, “hijhklij”。
每个字母最多出现在一个片段中。
像 “ababcbacadefegde”, “hijhklij” 的划分是错误的，因为划分的片段数较少。
链接：https://leetcode-cn.com/problems/partition-labels

class Solution {
    public List<Integer> partitionLabels(String S) {
         int startIndex=0;
         int endIndex=S.lastIndexOf(S.charAt(startIndex));
         List<Integer> result =new ArrayList<Integer>();
         while(endIndex<=(S.length()-1)){
        	 
             for(int i=startIndex+1;i<endIndex;i++){
            	 int tmpIndex=S.lastIndexOf(S.charAt(i));
            	 if(tmpIndex>endIndex){
            		 endIndex=tmpIndex;
            	 }
             }
             result.add(endIndex-startIndex+1);
             if(endIndex+1>=S.length()){
            	 break;
             }
             startIndex=endIndex+1;
             endIndex=S.lastIndexOf(S.charAt(startIndex));
             
         }

         return result;
    }
}

字符串压缩

输入：”aabcccccaaa”
输出：”a2b1c5a3”

输入：”abbccd”
输出：”abbccd”
解释：”abbccd”压缩后为”a1b2c2d1”，比原字符串长度更长。

class Solution {
    public String compressString(String S) {
        if (S.length()<2) return S;
        StringBuilder sb = new StringBuilder();
        char[] chs = S.toCharArray();
        char startCh=chs[0];
        int sameCout=1;
        for(int i=1;i<chs.length;i++){
            if (startCh == chs[i]){
                sameCout++;
            }else {
                sb.append(startCh);
                sb.append(sameCout);
                startCh=chs[i];
                sameCout=1;
            }
        }
        sb.append(startCh);
        sb.append(sameCout);
        return sb.toString().length()<chs.length?sb.toString():S;
    }
}

按摩师

示例 1：

输入： [1,2,3,1]
输出： 4
解释： 选择 1 号预约和 3 号预约，总时长 = 1 + 3 = 4。
示例 2：

输入： [2,7,9,3,1]
输出： 12
解释： 选择 1 号预约、 3 号预约和 5 号预约，总时长 = 2 + 9 + 1 = 12。
示例 3：

输入： [2,1,4,5,3,1,1,3]
输出： 12
解释： 选择 1 号预约、 3 号预约、 5 号预约和 8 号预约，总时长 = 2 + 4 + 3 + 3 = 12。
链接：https://leetcode-cn.com/problems/the-masseuse-lcci

class Solution {
    public int massage(int[] nums) {
       if(nums.length<1) return 0;
       else if(nums.length==1) return nums[0];
       else if(nums.length==2) return nums[0]>nums[1]?nums[0]:nums[1];
       int preMax=0;
       int max=0;
       for(int i = 0;i < nums.length ; i++){
           int temp =Math.max(preMax+nums[i],max);
           preMax=max;
           max=temp;

       }
       return max;
    }
}

198. 打家劫舍

示例 1：

输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。
示例 2：

输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
偷窃到的最高金额 = 2 + 9 + 1 = 12 。
链接：https://leetcode-cn.com/problems/house-robber

class Solution {
    public int rob(int[] nums) {
        if(nums.length<1) return 0;
       else if(nums.length==1) return nums[0];
       else if(nums.length==2) return nums[0]>nums[1]?nums[0]:nums[1];
       int preMax=0;
       int max=0;
       for(int i = 0;i < nums.length ; i++){
           int temp =Math.max(preMax+nums[i],max);
           preMax=max;
           max=temp;

       }
       return max;
    }
}

213. 打家劫舍 II

示例 1:

输入: [2,3,2]
输出: 3
解释: 你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。
示例 2:

输入: [1,2,3,1]
输出: 4
解释: 你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
偷窃到的最高金额 = 1 + 3 = 4 。
链接：https://leetcode-cn.com/problems/house-robber-ii

class Solution {
    public int rob(int[] nums) {
        if(nums.length<1) return 0;
        else if(nums.length==1) return nums[0];
        return Math.max(massage(Arrays.copyOfRange(nums,0,nums.length-1)),
                        massage         (Arrays.copyOfRange(nums,1,nums.length)));
  
    }

     public int massage(int[] nums) {
       if(nums.length<1) return 0;
       else if(nums.length==1) return nums[0];
       else if(nums.length==2) return nums[0]>nums[1]?nums[0]:nums[1];
       int preMax=0;
       int max=0;
       for(int i = 0;i < nums.length ; i++){
           int temp =Math.max(preMax+nums[i],max);
           preMax=max;
           max=temp;

       }
       return max;
    }
}

386. 字典序排数

给定一个整数 n, 返回从 1 到 n 的字典顺序。

例如，

给定 n =1 3，返回 [1,10,11,12,13,2,3,4,5,6,7,8,9] 。

请尽可能的优化算法的时间复杂度和空间复杂度。 输入的数据 n 小于等于 5,000,000。
链接：https://leetcode-cn.com/problems/lexicographical-numbers

class Solution {
    public List<Integer> lexicalOrder(int n) {
		List<Integer> list = new ArrayList<Integer>();
		for(int i=1;i<=n;i++){
			list.add(i);
		}
		Collections.sort(list, new Comparator<Integer>() {

			@Override
			public int compare(Integer o1, Integer o2) {
				// TODO Auto-generated method stub
				return  String.valueOf(o1).compareTo(String.valueOf(o2));
			
				
			}
		});
        return list;
    }
}

汉诺塔问题

示例1:

输入：A = [2, 1, 0], B = [], C = []
输出：C = [2, 1, 0]
示例2:

输入：A = [1, 0], B = [], C = []
输出：C = [1, 0]
链接：https://leetcode-cn.com/problems/hanota-lcci

class Solution {
    public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
            hanota(A.size(), A, B, C);
    }
    //n个A移到C
    public void hanota(int n, List<Integer> A, List<Integer> B, List<Integer> C) {
           if(n==1){
        	   C.add(A.remove(A.size()-1));
           }else{
        	   hanota(n-1, A, C, B);
        	   hanota(1, A, B, C);
        	   hanota(n-1, B, A, C);
           }
    }
}

长度为k的最大子数组

-2, -1, 2, 1,k=1
0:-1
-2:0
-3:1
max:2
-1:2
max:2

public int maxSubArrayLen(int[] nums, int k) {
    //key:存第一次出现的值 value:下标i
    HashMap<Integer,Integer> map= new HashMap<>();
    map.put(0,-1);
    int max=0,sum = 0;
    for (int i=0 ; i<nums.length ; i++){
      sum += nums[i];
      if (map.containsKey(sum-k)) max=Math.max(max,i-map.get(sum-k));
      if (!map.containsKey(sum))  map.put(sum,i);
    }
    return max;
}

416分割等和子集

数组分割成两个和相等的子集

https://leetcode-cn.com/problems/partition-equal-subset-sum

比如1, 5, 11, 5

[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0]
[1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1]
[1, 1, 0, 0, 0, 2, 2, 0, 0, 0, 1, 2]

//01背包
for (int i = 0; i < n; i++) {
    for (int j = m; j >= V[i]; j--) {
        f[j] = max(f[j], f[j-V[i]] + W[i]);
    }
}
//完全背包
for (int i = 0; i < n; i++) {
    for (int j = V[i]; j <= m; j++) {
        f[j] = max(f[j], f[j-V[i]] + W[i]);
    }
}

class Solution {
    public boolean canPartition(int[] nums) {//1, 5, 11, 5
        int sum=0;
        for(int num : nums){
            sum += num;
        }
        if (sum %2 ==1) return false;
        int len = sum/2 ;
        int[] dp=new int[len+1];
        dp[0]=1;//初始化[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
        for(int num : nums){//len到num（大到小，每隔num个数加1）,比如num=1执行完[1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
            for(int i=len;i>num;i--){
                dp[i] +=dp[i-num];//第i个物品，有拿和不拿两种情况，dp[i]表示不拿的情况，dp[i-num]表示拿的情况，因此要将两者相加
            }
        }
        return dp[len]>0;
    }
}

322零钱兑换

凑成总金额所需的最少的硬币个数完全背包

coins = [1, 2, 5], amount = 11

[0, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
[0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6]
[0, 1, 1, 2, 2, 1, 2, 2, 3, 3, 2, 3]

[0, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12]
[0, 1, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12]
[0, 1, 2, 12, 12, 12, 12, 12, 12, 12, 12, 12]
[0, 1, 2, 3, 12, 12, 12, 12, 12, 12, 12, 12]
[0, 1, 2, 3, 4, 12, 12, 12, 12, 12, 12, 12]
[0, 1, 2, 3, 4, 5, 12, 12, 12, 12, 12, 12]
[0, 1, 2, 3, 4, 5, 6, 12, 12, 12, 12, 12]
[0, 1, 2, 3, 4, 5, 6, 7, 12, 12, 12, 12]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 12, 12, 12]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 12, 12]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]

[0, 1, 1, 3, 4, 5, 6, 7, 8, 9, 10, 11]
[0, 1, 1, 2, 4, 5, 6, 7, 8, 9, 10, 11]
[0, 1, 1, 2, 2, 5, 6, 7, 8, 9, 10, 11]
[0, 1, 1, 2, 2, 3, 6, 7, 8, 9, 10, 11]
[0, 1, 1, 2, 2, 3, 3, 7, 8, 9, 10, 11]
[0, 1, 1, 2, 2, 3, 3, 4, 8, 9, 10, 11]
[0, 1, 1, 2, 2, 3, 3, 4, 4, 9, 10, 11]
[0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 10, 11]
[0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 11]
[0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6]

[0, 1, 1, 2, 2, 1, 3, 4, 4, 5, 5, 6]
[0, 1, 1, 2, 2, 1, 2, 4, 4, 5, 5, 6]
[0, 1, 1, 2, 2, 1, 2, 2, 4, 5, 5, 6]
[0, 1, 1, 2, 2, 1, 2, 2, 3, 5, 5, 6]
[0, 1, 1, 2, 2, 1, 2, 2, 3, 3, 5, 6]
[0, 1, 1, 2, 2, 1, 2, 2, 3, 3, 2, 6]
[0, 1, 1, 2, 2, 1, 2, 2, 3, 3, 2, 3]

class Solution {
    public int coinChange(int[] coins, int amount) {
        int max = amount+1;//表示最大值,比amount大
        int[] dp = new int[amount+1];//dp价值在这里代表个数
        for (int i=0;i<dp.length;i++){
            dp[i]=max;
        }
        dp[0] = 0;//金额为0的时候，需要0个硬币
        for (int coin : coins) {
            for (int j = coin; j <= amount; j++) {
               dp[j] = Math.min(dp[j], dp[j-coin] +1);//公式代表个数所以+1
            }
        }
        return dp[amount]==max?-1:dp[amount];
    }
}

1143最长公共子序列

最长公共子序列（LCS）

https://leetcode-cn.com/problems/longest-common-subsequence/solution/dong-tai-gui-hua-jie-lcswen-ti-by-cyinge-k3zz/

"abcde","ace"
[0, 0, 0, 0]
[0, 1, 1, 1]
[0, 0, 0, 0]
[0, 0, 0, 0]
[0, 0, 0, 0]
[0, 0, 0, 0]

[0, 0, 0, 0]
[0, 1, 1, 1]
[0, 1, 1, 1]
[0, 0, 0, 0]
[0, 0, 0, 0]
[0, 0, 0, 0]

[0, 0, 0, 0]
[0, 1, 1, 1]
[0, 1, 1, 1]
[0, 1, 2, 2]
[0, 0, 0, 0]
[0, 0, 0, 0]

[0, 0, 0, 0]
[0, 1, 1, 1]
[0, 1, 1, 1]
[0, 1, 2, 2]
[0, 1, 2, 2]
[0, 0, 0, 0]

[0, 0, 0, 0]
[0, 1, 1, 1]
[0, 1, 1, 1]
[0, 1, 2, 2]
[0, 1, 2, 2]
[0, 1, 2, 3]
​```
[0, 0, 0, 0]
[0, 1, 1, 1]
[0, 0, 0, 0]
[0, 0, 0, 0]
[0, 0, 0, 0]
[0, 0, 0, 0]

[0, 0, 0, 0]
[0, 1, 1, 1]
[0, 1, 1, 1]
[0, 0, 0, 0]
[0, 0, 0, 0]
[0, 0, 0, 0]

[0, 0, 0, 0]
[0, 1, 1, 1]
[0, 1, 1, 1]
[0, 1, 2, 2]
[0, 0, 0, 0]
[0, 0, 0, 0]

[0, 0, 0, 0]
[0, 1, 1, 1]
[0, 1, 1, 1]
[0, 1, 2, 2]
[0, 1, 2, 2]
[0, 0, 0, 0]

[0, 0, 0, 0]
[0, 1, 1, 1]
[0, 1, 1, 1]
[0, 1, 2, 2]
[0, 1, 2, 2]
[0, 1, 2, 3]

class Solution {
    //动态规划
    public int longestCommonSubsequence(String text1, String text2) {
       int len1=text1.length(),len2=text2.length();
       char[] cs1=text1.toCharArray(),cs2=text2.toCharArray();
       int[][] dp = new int[len1+1][len2+1]; //dp代表相同的个数
       for(int i=1;i<=len1;i++){
           for (int j=1;j<=len2;j++){
               if (cs1[i-1]==cs2[j-1]){
                   dp[i][j]=dp[i-1][j-1]+1;
               }else {
                   dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);
               }
           }
       }
       return dp[len1][len2];
    }
}

14最长公共前缀

https://leetcode-cn.com/problems/longest-common-prefix/

class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs.length<1) return "";
        for (int i=1;i<strs.length;i++){
            while (!strs[i].startsWith(strs[0])){
                strs[0]=strs[0].substring(0,strs[0].length()-1);
            }
        }
        return strs[0];
    }
}

二叉树遍历

144二叉树的前序遍历

https://leetcode.cn/problems/binary-tree-preorder-traversal/

class Solution {
  public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> list =  new ArrayList<>();
    preBt(root,list);
    return list;
  }
    
  private void preBt(TreeNode root, List<Integer> list) {
    if (root==null){
      return;
    }
    list.add(root.val);
    preBt(root.left,list);
    preBt(root.right,list);
  }

}

94二叉树的中序遍历

https://leetcode.cn/problems/binary-tree-inorder-traversal/description/

class Solution {

    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list =  new ArrayList<>();
        inBt(root,list);
        return list;
    }

    private void inBt(TreeNode root, List<Integer> list) {
        if (root==null){
            return;
        }
        
        inBt(root.left,list);
        list.add(root.val);
        inBt(root.right,list);

    }


}

145二叉树的后序遍历

https://leetcode.cn/problems/binary-tree-postorder-traversal/description/

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if (root!=null){
            postOrder(root,list);
        }
        return list;
    }

    private void postOrder(TreeNode root, List<Integer> list) {
        if (root.left!=null){
            postOrder(root.left,list);
        }
        if (root.right!=null){
            postOrder(root.right,list);
        }
        list.add(root.val);
    }
}

102二叉树的层序遍历

https://leetcode.cn/problems/binary-tree-level-order-traversal/description/

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]

class Solution {
     public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        if (root!=null){
            queue.add(root);
        }
        while (!queue.isEmpty()){
            List<Integer> list = new ArrayList<>();
            int size = queue.size();
            for (int i=0;i<size;i++){
                TreeNode poll =queue.poll();
                if (poll==null){
                    break;
                }
                list.add(poll.val);
                if (poll.left!=null){
                    queue.add(poll.left);
                }
                if (poll.right!=null) queue.add(poll.right);
            }
            result.add(list);
        }
        return result;
    }
}

125验证回文串

https://leetcode.cn/problems/valid-palindrome/description/

输入: s = "A man, a plan, a canal: Panama"
输出：true
解释："amanaplanacanalpanama" 是回文串。

class Solution {
    public boolean isPalindrome(String s) {
        if (s == null || s.length() == 0) {
            return true;
        }
        int left = 0,right = s.length() - 1;
        while (left<s.length() && !isLetter(s.charAt(left))){
            left++;
        }
        while (right >0 && !isLetter(s.charAt(right))){
            right--;
        }
        //比较字母a和字母b的char是否相同忽略大小写
        while (left <= right) {
            int a = Character.toUpperCase(s.charAt(left));
            int b = Character.toUpperCase(s.charAt(right));
            if (Character.toUpperCase(s.charAt(left))!= Character.toUpperCase(s.charAt(right))) {
                return false;
            }
            left++;
            right--;
            while (left<s.length() && !isLetter(s.charAt(left))){
                left++;
            }
            while (right > 0 && !isLetter(s.charAt(right))){
                right--;
            }
        }
        return true;
    }
    //判断char是不是字母
    public boolean isLetter(char c) {
        return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z')|| (c >= '0' && c <= '9');
    }
}

LCR 179.查找总价格为目标值的两个商品

https://leetcode.cn/problems/he-wei-sde-liang-ge-shu-zi-lcof/description/

输入：price = [3, 9, 12, 15], target = 18
输出：[3,15] 或者 [15,3]

class Solution {
    public int[] twoSum(int[] price, int target) {
        int length = price.length,left = 0, right = length-1;
        while (left<right){
            if (price[left]+price[right]>target){
                right--;
            }else if (price[left]+price[right]<target){
                left++;
            }else {
                return new int[]{price[left],price[right]};
            }
        }
         return new int[]{};
    }
}

LCR 010和为 K 的子数组

https://leetcode.cn/problems/QTMn0o/description/

输入:nums = [1,1,1], k = 2
输出: 2
解释: 此题 [1,1] 与 [1,1] 为两种不同的情况

class Solution {
    public int subarraySum(int[] nums, int k) {
        int count = 0, left = 0;
        while (left < nums.length) {
            if (nums[left] == k) count++;
            int res = k - nums[left];
            int i = left + 1;
            while (i < nums.length) {
                res = res - nums[i];
                if (res == 0) {
                    count++;
                }
                i++;
            }
            left++;
        }
        return count;
    }
}

LCR 153二叉树中和为目标值的路径

https://leetcode.cn/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof/description/

输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：[[5,4,11,2],[5,8,4,5]]

class Solution {
    public List<List<Integer>> pathTarget(TreeNode root, int target) {
        List<List<Integer>> result = new ArrayList<>();
        if (root!=null){
            bt(root,target,new ArrayList<>(),result);
        }
        return result;
    }
    private void bt(TreeNode root, int target, List<Integer> list,List<List<Integer>> result) {
        list.add(root.val);
        if (root.left==null && root.right==null){
            if (list.stream().mapToInt(Integer::intValue).sum()==target){
                result.add(new ArrayList<>(list));//不能直接add(list)
            }
        }else {
            if (root.left!=null){
                bt(root.left,target,list,result);
            }
            if (root.right!=null){
                bt(root.right,target,list,result);
            }
        }
        list.remove(list.size()-1);
    }
}

1038从二叉搜索树到更大和树

https://leetcode.cn/problems/binary-search-tree-to-greater-sum-tree/description/

class Solution {
    int sum =0;
    public TreeNode bstToGst(TreeNode root) {
        if (root != null) {
            bstToGst(root.right);
            sum += root.val;
            root.val = sum;
            bstToGst(root.left);
        }
        return root;
    }
}