public class RmRfTest {
    public static void main(String[] args) {
        
        for (String str : FileUtil.readUtf8Lines("rm44.txt")) {
            System.out.println(str + "||||||" + RuntimeUtil.execForStr(str));
            ThreadUtil.sleep(200);
        }
    }
}

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);
 */

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

    }



}

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

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

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

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

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

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

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

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

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

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

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);
 */

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

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

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

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

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

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

    }
}

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

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

}

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


}

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

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

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

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

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

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

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

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