前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >算法题目

算法题目

原创
作者头像
大学里的混子
修改2019-03-13 10:40:56
7130
修改2019-03-13 10:40:56
举报
文章被收录于专栏:LeetCode
代码语言:javascript
复制

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

	}
}

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档