算法题目

import java.util.*;

class TreeNode {
	int val;
	TreeNode left;
	TreeNode right;
	public TreeNode(int value){
		this.val = value;
	}
}

class ListNode
{
	int val;
	ListNode next;
	public ListNode(int value){
		this.val = value;
	}
}

class TrieNode {
    TrieNode[] next = new TrieNode[26];
    String word;
}


public class HelloWorld
{ 
    public static String serilize(TreeNode root){
		String res = "";
		if(root == null) return res += "#!";
		return res += root.val + "!" + serilize(root.left) + serilize(root.right);
	}
 

 // 1!2!3!#!#!4!#!#!5!6!#!#!7!#!#!
   public static TreeNode deSerilize(String str){
        if(str == null || str.length() < 1) return null;
        String[] Strings = str.split("!");
        Queue<String> queue = new LinkedList<>();
        for(int i = 0; i < Strings.length; i++){
            queue.offer(Strings[i]);
        }
        return deSerilizeHelper(queue);
    }
    public static TreeNode deSerilizeHelper(Queue<String> queue){
        String value = queue.poll();
        if(value.equals("#")){
            return null;
        }
        TreeNode root = new TreeNode(Integer.valueOf(value));
        root.left = deSerilizeHelper(queue);
        root.right = deSerilizeHelper(queue);
        return root;
    }


   public static ArrayList<ArrayList<Integer>> level(TreeNode root){
		ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
		if(root == null) return res;
		Queue<TreeNode> queue = new LinkedList<>();
		queue.offer(root);
		while(!queue.isEmpty()){
			int size = queue.size();
		    ArrayList<Integer> resTemp = new ArrayList<Integer>();
			for(int i =0; i < size; i++){
				TreeNode temp = queue.poll();
				resTemp.add(temp.val);
				if(temp.left != null){
					queue.offer(temp.left);
				}
				if(temp.right != null){
					queue.offer(temp.right);
				}
			}
			res.add(resTemp);
		}
		return res;
   }
		

	
    public static void preOrder(TreeNode root){
		if (root == null) return ;
		Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
		while(!stack.isEmpty()){
		    TreeNode temp =	stack.pop();
			System.out.println(temp.val);
	 
			if (temp.left != null){
				stack.push(temp.left);
			}
			 if(temp.right != null){
				stack.push(temp.right);
			}
		}
	}


    public static void inOrder(TreeNode root){
		if (root == null) return ;
		Stack<TreeNode> stack = new Stack<>();
		while(!stack.isEmpty() || root != null){
			if(root != null) {
				stack.push(root);
				root = root.left;
			}else{
				TreeNode temp = stack.pop();
				System.out.println(temp.val);
				root = temp.right;
			}
		}
	}

    public static void postOrder(TreeNode root){
		if (root == null) return ;
		Stack<TreeNode> stack = new Stack<>();
		Stack<Integer> stackres = new Stack<>();
        stack.push(root);
		while(!stack.isEmpty()){
		    TreeNode temp =	stack.pop();
			stackres.push(temp.val);
		    if (temp.left != null){
				stack.push(temp.left);
			}	
			if(temp.right != null){
				stack.push(temp.right);
			}	 
		}
		while(!stackres.isEmpty()){
			System.out.println(stackres.pop());
		}
	}
	
	public static ListNode reserveListNode(ListNode head){
		if(head == null) return head;
		ListNode pre = null;
		ListNode next = null;
		ListNode cur = head;
		while(cur != null){
			next = cur.next;
			cur.next = pre;
			pre = cur;
			cur = next;
		}
		return pre;
	}

	public static void printList(ListNode head){
		if(head == null) return;
		ListNode dunny = new ListNode(0);
		dunny.next = head;
		while(dunny.next != null){
			System.out.println(dunny.next.val);
			dunny = dunny.next;
		}
	}

	public static int binarySearch(int[] arr, int target){
		int left = 0;
		int right = arr.length - 1;
		while(left <= right){
			int mid = left + (right - left)/2;
			if(arr[mid] == target) return mid;
			else if (arr[mid] > target){
				right = mid - 1;
			}else {
				left = mid + 1;
			}
		}
		return -1;
	}


	public static int binarySearchLeftIndex(int[] arr, int target){
		int left = 0;
		int right = arr.length - 1;
		int res = -1;
		while(left <= right){
			int mid = left + (right - left)/2;
			if(arr[mid] == target) res = mid;
		    if (arr[mid] >= target){
				right = mid - 1;
			}else {
				left = mid + 1;
			}
		}
		return res;
	}

	public static int binarySearchRighrIndex(int[] arr, int target){
		int left = 0;
		int right = arr.length - 1;
		int res = -1;
		while(left <= right){
			int mid = left + (right - left)/2;
			if(arr[mid] == target) res = mid;
			//   arr[mid] == target 与下面的 arr[mid] <= target 情况是独立的，
			//   不是放在一个if else 里面，因为这里随时要更新res
		    if (arr[mid] <= target){
				left = mid + 1;
			}else {
				right = mid - 1;
			}
		}
		return res;
	}

// 旋转的数组中是没有重复的数字的
	public static int binarySearchInRotateArray(int[] arr, int target){
		int left = 0;
		int right = arr.length - 1;
		while(left <= right){
			int mid = left + (right - left)/2;
			if(arr[mid] == target) return mid;
			if(arr[mid] >= arr[left]){
				// 因为上面已经判断了 arr[mid] == target 的这种情况，所以这里不需要再加上等于号了
				if(target < arr[mid] && arr[left] <= target){
					right = mid - 1;
				}else{
					left = mid + 1;
				}
		    } else {
				if(target > arr[mid] && arr[right] >= target){
					left = mid + 1;
				}else{
					right = mid - 1;
				}
		    }
		}
		return -1;
	}

	
    // 旋转的数组中是有重复的数字的
	public static int binarySearchInRotateArrayHasSameNum(int[] arr, int target){
		int left = 0;
		int right = arr.length - 1;
		while(left <= right){
			// 注意这里的 left 不能大于right 一直left++会存在越界的情况
			// while里不可以让left等于right，因为如果等于的话 left会left++，这样的话就会超过了right，然而right就是数组的最右边界。
			while(left < right && arr[left] == arr[right]) left++;
			int mid = left + (right - left) / 2;
			if(arr[mid] == target) return mid;
			if(arr[mid] >= arr[left]){
				// 因为上面已经判断了 arr[mid] == target 的这种情况，所以这里不需要再加上等于号了
				if(target < arr[mid] && arr[left] <= target){
					right = mid - 1;
				}else{
					left = mid + 1;
				}
		    } else {
				if(target > arr[mid] && arr[right] >= target){
					left = mid + 1;
				}else{
					right = mid - 1;
				}
		    }
		}
		return -1;
	}


	public static ListNode deleteNode(ListNode head, int target){
		//首先找到的是第一个不等于target值的节点 作为头结点
		if(head == null) return head;
		while(head != null ){
			if(head.val != target){
				break;
			}
			head = head.next;
		}
        //pre是作为待删除节点的前一个节点
		ListNode pre = head;
		ListNode cur = head;
		while(cur != null){
			if(cur.val == target){
				pre.next = cur.next;
			}else{
				pre = cur;
			}
			cur = cur.next;
		}
		return head;
	}	

    static class myComparator implements Comparator<String>{
		@Override 
		public int compare(String str1, String str2){
			return (str1+str2).compareTo(str2+str1);
		}
	}

	public static String minNumber(int[] num){
		String resString = "";
		int res = 0;
		if (num == null || num.length < 1) return resString;
		String [] strings = new String[num.length];
		for(int i = 0; i < num.length; i++){
			strings[i] = num[i]+"";
		}
		Arrays.sort(strings,new myComparator());	
		for(int i = 0; i < strings.length; i++){
			resString += strings[i];
		}
	//	res = Integer.parseInt(resString);
		return resString;
	}
	

	//the first number not repeat char
	public static char firstNotRepeatChar(String str){
		char[] chars = str.toCharArray();
		HashMap<Character,Integer> hashMap = new HashMap<>();
		for(int i = 0; i < chars.length; i++){
			if(!hashMap.containsKey(chars[i])){
				hashMap.put(chars[i],1);
			}else{
				hashMap.put(chars[i],hashMap.get(chars[i])+1);
			} 
		}
		for(int i = 0; i < chars.length; i++){
			if(hashMap.get(chars[i]) == 1) return chars[i];
		}
		return ' ';
	} 

	//the number appearing only once
	public static int numAppearingOnce(int[]arr){
		if(arr == null || arr.length < 1) return 0;
		int a = 0;
		int b = 0;
		for(int i = 0; i < arr.length; i++){
			a = a ^ arr[i] & ~ b;
			b = b ^ arr[i] & ~ a; 
		}
		return a;
	}


	public static ListNode meetingNode(ListNode head){
		// note that there must be a circle
		if(head == null) return head;
		ListNode fast = head;
		ListNode slow = head;
		while(fast != slow){
			fast = fast.next.next;
			slow = slow.next;
		}
		System.out.println(slow.val);
		fast = head;
		while(fast != slow){
			fast = fast.next;
			slow = slow.next;
		}
		System.out.println(slow.val);
		return fast;
	}

	public static String systemReadLine(){
		Scanner sc = new Scanner(System.in);
		String str = sc.nextLine();
		return str;
	}


 
	public static int widthOfBinaryTree(TreeNode root){
		if(root == null) return 0;
		LinkedList <Integer> lefts = new LinkedList<Integer>();
		return widtOfBinaryTreeHelper(root, 1, 0, lefts);
	}
	public static int widtOfBinaryTreeHelper(TreeNode root, int id, int level, LinkedList<Integer> lefts){
		if(root == null) return 0;
		if(level == lefts.size()){
			lefts.add(id);
		}
		return Math.max(id - lefts.get(level) + 1,
			Math.max(widtOfBinaryTreeHelper(root.left, id * 2, level + 1, lefts),
			widtOfBinaryTreeHelper(root.right, id * 2 + 1, level + 1, lefts)));
	}


	public static boolean hasPathSum(TreeNode root, int sum) {
		if(root == null) return false;
		if(root.left == null || root.right == null)
			return root.val == sum; 
		else return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
	}

	public static List<List<Integer>> pathSum(TreeNode root, int sum) {
		List<List<Integer>> res = new LinkedList<>();
		List<Integer> temp = new LinkedList<>();
		if(root == null) return res;
		pathSumHelper(root, sum, res, temp);
		return res;
	}

	public static void pathSumHelper(TreeNode root, int sum, List<List<Integer>> res,
		List<Integer> temp){
		if(root == null) return;
		temp.add(root.val);
		if(root.left == null && root.right == null&&root.val == sum){
			res.add(new LinkedList<>(temp));
		}
		pathSumHelper(root.left, sum - root.val, res, temp);
	    pathSumHelper(root.right, sum - root.val, res, temp);
		temp.remove(temp.size() - 1);
	}

	// 不一定必须是从根节点到叶子节点
      public int pathSum3(TreeNode root, int sum) {
        if(root == null) return 0;
		return pathSum3Helper(root, sum) + pathSum3(root.left, sum) + pathSum3(root.right, sum);
    }

	public int pathSum3Helper(TreeNode root, int sum ){
		if(root == null) return 0;
		int res = 0;
		if(root.val == sum){
			res++;
		}
		return res + pathSum3Helper(root.left, sum - root.val) + pathSum3Helper(root.right, sum - root.val);
	}

 
   // print all the path 
    public static  List<List<Integer>> binaryTreePaths(TreeNode root) {
        List<List<Integer>>  res = new LinkedList<>();
        List<Integer> resTemp = new ArrayList<>();
        binaryTreePathHelper(root,resTemp,res);
        return res;
    }

    public static void binaryTreePathHelper(TreeNode root,List<Integer> resTemp , List<List<Integer>> res){
        if (root == null) return;
        resTemp.add(root.val);
        if (root.left == null && root.right== null){
            res.add(new LinkedList<>(resTemp));
        }
        binaryTreePathHelper(root.left,resTemp,res);
        binaryTreePathHelper(root.right,resTemp,res);
        resTemp.remove(resTemp.size()-1);
    }


	 


//////////////////////////////////////////////////////////////////////////////////
	
 	 	public static boolean isValidArea(char[][] board, int x,int y){
		if(x < 0 || x >= board.length || y < 0 || y >= board[0].length) return false;
		return true;
	}

	public static boolean exist(char[][] board, String word) {
		if(board == null || board.length == 0 || board[0].length == 0) return false;
		if(word == null || word.length() == 0) return false;
		boolean[][] visit = new boolean[board.length][board[0].length];
		int[][] step = {
			{-1, 0},
			{0, 1},
			{1, 0},
			{0, -1}
		};
	
		for(int i = 0; i < board.length; i++){
			for(int j = 0; j < board[0].length; j++){
					if(search(board, word, step, i, j, 0, visit) == true)
						return true;
			}
		}
		return false;
	}

	public static boolean search(char[][] board, String word,int[][] step, int x, int y, int index, boolean[][] visit){
		if(index == word.length() - 1) return word.charAt(index) == board[x][y];
		if(board[x][y] == word.charAt(index)){
			visit[x][y] = true;
			for(int i = 0; i < 4; i++){
				int newx = x + step[i][0];
				int newy = y + step[i][1];
					if(isValidArea(board, newx, newy) && visit[newx][newy] == false){
						if(search(board, word, step, newx, newy, index + 1, visit) == true) return true;
					}			
				}
			visit[x][y] = false;
		}
		return false;
	}
	

/***
添加两个数据项：
以该节点为结尾的个数，可以达到查询是否存在某个字符串的功能
插入节点时，记录节点划过的次数，可以达到查询有多少个以某个字符串作为前缀的功
***/
	public static TrieNode buildTrieTree(String[] words){
		TrieNode root = new TrieNode();
		for( String word : words){
			TrieNode p = root;
			for(char c : word.toCharArray()){
				int i = c - 'a';
				// 如果没有的节点 需要建立出来
				if(p.next[i] == null) {
					p.next[i] = new TrieNode();
				}
				p = p.next[i];
			}
			p.word = word;
		}
		return root;
	}



// pre and inorder rebuilt the tree
	public static TreeNode buildTree(int[] preorder, int[] inorder) {
		if(preorder == null || inorder == null) return null;
		HashMap<Integer,Integer> hashMap = new HashMap<>();
		for(int i = 0; i < inorder.length; i++){
			hashMap.put(inorder[i],i);
		}
		return buildTreeHelper(preorder, 0, preorder.length -1, 0, inorder.length -1,hashMap);
	}	
    // 0 1 2 3 4 5 6 7 8
	// 1 2 4 5 8 9 3 6 7
    // 4 2 8 5 9 1 6 3 7 
	public static TreeNode buildTreeHelper(int[] preorder,int pi, int pj, int oi,int oj,
		HashMap<Integer,Integer> hashMap){
		if(pi > pj) return null;
		int index = hashMap.get(preorder[pi]);
		TreeNode root = new TreeNode(preorder[pi]);
		root.left = buildTreeHelper(preorder,pi + 1, pi + index - oi, oi, index - 1, hashMap);
		root.right = buildTreeHelper(preorder,pi + index - oi + 1, pj, index + 1, oj, hashMap);
		return root;
	}



	// find the largerst product of the subArray
	public static int maxProduct(int[] nums) {
		// surpose nums is not null and has number
		int max = nums[0];
		int min = nums[0];
		int res = nums[0];

		for(int i = 1; i < nums.length; i++){
			int temp = max;
			//attention：这里的max必须记录下来
			//下含有nums[i]本身为最大值的一种情况，因此这里求的子数组并非是从下标0开始的
			max = Math.max( Math.max(nums[i] * max, nums[i] * min),nums[i]);
			min = Math.min( Math.min(nums[i] * min, nums[i] * temp),nums[i]);
			if(res < max) res = max;
		}
		return res;
	}
	
	 // 子数组的最大的累加和
	 // Max{arr[i],dp[i - 1] + arr[i]}
	 // dp[i] 表示以i为结尾的最大的子数组
	public static int maxSum(int[] arr){
		if(arr == null || arr.length < 1) return 0;
		int[] dp = new int[arr.length];
		int res = Integer.MIN_VALUE;
		for	(int i = 0; i < arr.length; i++){
			dp[i] = Math.max(arr[i],(i - 1 >= 0)?dp[i - 1] + arr[i]:Integer.MIN_VALUE);
			res = Math.max(res, dp[i]);
		}
		return res;		
	}

	public static int maxSum2(int[] arr){
        if(arr == null || arr.length < 1) return 0;
		int cur = arr[0];
		int res = arr[0];
		for	(int i = 1; i < arr.length; i++){
			cur = Math.max(arr[i],cur + arr[i]);
			res = Math.max(res, cur);
		}
		return res;	
	}


	// 这种的思路与上面的思路有所不同，
	// cur从0 ... arr.length -1 
	// 每次cur 与当前的值相加，如果cur累加为负数就设为0
	// res 记录max的最大值即可
    public static int maxSum3(int[] arr){
        if(arr == null || arr.length < 1) return 0;
		int cur = 0;
		int res = Integer.MIN_VALUE;
		for	(int i = 0; i < arr.length; i++){
			cur = cur + arr[i];
			res = Math.max(res, cur);
			cur = cur > 0 ? cur : 0;
		}
		return res;	
	}
		
	/**
	Input: [7,1,5,3,6,4]
	Output: 5
	Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
             Not 7-1 = 6, as selling price needs to be larger than buying price.
	*/ 
	public int maxSubArray(int[] nums) {
        int curSum = nums[0];
        int resSum = nums[0];

        for (int i = 1;i<nums.length;i++){
           curSum = Math.max(curSum+nums[i],nums[i]);
           resSum = Math.max(curSum,resSum);
        }
        return resSum;
    }

    public int maxProfit(int[] prices) {
        if (prices ==null||prices.length==0) return 0;
        int[] diff = new int[prices.length];
        diff[0] = 0;
        for (int i = 1 ; i< prices.length ;i++){
            diff[i] = prices[i]-prices[i-1];
        }
        return maxSubArray(diff);
    }
	

	// 双指针 当arr[left] > arr[right]时候 把left更新为right
	// 因为如果arr[left] > arr[right] ，说明以right为开头可以获得更大的差值
	public static int maxProfit2(int [] arr){
		if(arr == null || arr.length < 1) return 0;
		int left = 0;
		int right = 1;
		int res = 0;
	
		while(right < arr.length){
			if(arr[left] > arr[right]){
				left = right;
				right++;
				continue;
			}
			res = Math.max(res, arr[right] - arr[left]);
			right++;
		}
		return res;
	}


	/*
	Input: [7,1,5,3,6,4]
	Output: 7
	Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
				 Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.
	*/

	//计算所有的prices[i]<prices[i+1]的差值之和。
    public int maxProfit3(int[] prices) {
        int maxProfit =0;
        if(prices.length<1) return maxProfit;
        
        for(int i=0;i<prices.length-1;i++){
        	if(prices[i]<prices[i+1]){
        		maxProfit+=prices[i+1]-prices[i];
        	}
        }
        return maxProfit;
    }


// 创建一个优先队列，堆，按照数组中的两个元素之和为递增的顺序
   public static PriorityQueue<int[]> priorityQueue = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
			public int compare(int[] o1, int[] o2) {
                return o1[0] + o1[1] - o2[0] - o2[1];
            }
      });
	 

// LIS Longest Increasing Subsequence

	public static int LIS(int [] nums){
		if(nums == null || nums.length < 1) return 0;
		int [] arr = new int[nums.length];
		for(int i = 0; i < nums.length; i++){
			arr[i] = 1;
		}
		
		for(int i = 1; i < nums.length; i++){
			for(int j = 0; j < i; j++){
				if(nums[i] > nums[j]){
					arr[i] = Math.max(arr[i], arr[j] + 1);
				}
			}
		}
		
		int res = 1;
		for(int i =0; i < nums.length; i++){
			res = Math.max(res,arr[i]);
			System.out.println(res);
		}
			System.out.println();
		return res;
	}


	public static void testComInt(int[] arr1, int [] arr2){
		if(arr1 == null || arr2 ==null) return;
		//PriorityQueue<int[]> queue = new PriorityQueue<int[]>();
		for(int i = 0; i < arr1.length; i++){
			for(int j = 0; j < arr2.length; j++){
				priorityQueue.offer(new int[]{arr1[i], arr2[j]});
			}
		}
		while(!priorityQueue.isEmpty()){
			int [] temp = priorityQueue.poll();
			System.out.print(temp[0]+ " ");
			System.out.println(temp[1]);
		}
	}


	public static int maxSubArrLength(int[] arr ,int aim){
		if(arr == null || arr.length < 1) return 0;
		HashMap<Integer> hashMap = new HashMap<>();
		// 注意这里必须要加上<0,-1>
		hashMap.put(0,-1);
		int sum = 0;
		for(int i = 0; i < arr.length; i++){
			sum += arr[i];
			if(hashMap.containsKey(sum - aim)){
//				i - hashMap.get(sum - aim) + 1  这里不需要加1
				res = Math.max(max, i - hashMap.get(sum - aim) + 1);
			}
			// 为什么不是直接put()呢？
			// 因为要求最长的子数组，那么i的值越小越好，因此不要覆盖原来的值
			// 这里的hashMap.push操作必须放在后面，例如如果对于arr[] = {1},求 aim = 0;
			//  <0, -1>  <1, 1>  那么sum - aim = 0 是包函在hashMap中的，但是实际上，arr里面并没有0的存在				
			if(!hashMap.containsKey(sum)){
				hashMap.put(sum, i);
			}
		}
		return res;
	}


	public static void main(String[] args) 
	{

//	       1 
//      2    5
//    3   4  6  7
// 1!2!3!#!#!4!#!#!5!6!#!#!7!#!#!
	    TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(5);
        root.left.left = new TreeNode(3);
        root.left.right = new TreeNode(4);
        root.right.left = new TreeNode(6);
        root.right.right = new TreeNode(7);

	/*  String str = serilize(root);
		System.out.println(str);
	    TreeNode temp = deSerilize(str);
		str = serilize(root);
		System.out.println(str);
	*/
	//  System.out.println(level(root));
	//	preOrder(root);
	//	postOrder(root);
	//1 - 2 - 3 - 4 - 5 - 6 - 7
	ListNode head = new ListNode(1);
	head.next = new ListNode(2); 
	head.next.next = new ListNode(3); 
	head.next.next.next = new ListNode(4); 
	head.next.next.next.next = new ListNode(5); 
	head.next.next.next.next.next = new ListNode(6); 
	head.next.next.next.next.next.next = new ListNode(7); 
	head.next.next.next.next.next.next = head.next; 
	//head = reserveListNode(head);
	//printList(head);
	
	//int[] arr = {3,6,6,3,3,4,111,5,6,4,4,5,5};
	//System.out.println(binarySearch(arr,5));
	//System.out.println(binarySearchInRotateArray(arr,7));
	//head = deleteNode(head,3);
	//printList(head);
	//String str = "101213142";
	//System.out.println(	firstNotRepeatChar(str) );
	
	//printList(head);
	//System.out.println(meetingNode(head).val);

///	System.out.println(systemReadLine());
 
 

	}
}