# LeetCode | 刷题日志

2017年是不幸且值得纪念的，从年初三番之行到年中公司变故再到8月的重大失利，逼着我做出改变。建立这个博客受到Lexi的启发，用于督促和分享。

# 653. Two Sum IV – Input is a BST

Given a Binary Search Tree and a target number, return true if there exist two elements in the BST such that their sum is equal to the given target. Example 1: Input: 5 / \ 3 6 / \ \ 2 4 7 Target = 9 Output: True Example 2: Input: 5 / \ 3 6 / \ \ 2 4 7 Target = 28 Output: False   /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public boolean findTarget(TreeNode root, int k) { if(root == null) return false; HashSet map = new HashSet(); return checkk(root,k,map); } public boolean checkk(TreeNode root, int k,HashSet map){ if(root == null) return false; if(map.contains(k-root.val)) return true; map.add(root.val); return checkk(root.left,k,map) || checkk(root.right,k,map); } }

# 112. Path Sum

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum. For example: Given the below binary tree and sum = 22, 5 / \ 4 8 / / \ 11 13 4 / \ \ 7 2 1 return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22. /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public boolean hasPathSum(TreeNode root, int sum) { if(root == null) return false; if(root.val == sum && root.left ==null && root.right == null) return true; return hasPathSum(root.left,sum-root.val) || hasPathSum(root.right,sum-root.val); } }

# 110. Balanced Binary Tree

Given a binary tree, determine if it is height-balanced. For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.   /** * 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; if(deep(0,root) == -99) return false; return true; } public int deep(int deep, TreeNode root){ if(root == null){ return deep-1; } int l = deep(deep+1,root.left); int r = deep(deep+1,root.right); if(Math.abs(l-r) >1){ return -99; } return l>r?l:r; } }

# 270. Closest Binary Search Tree Value

Given a non-empty binary search tree and a target value, find the value in the BST that is closest to the target. Note: Given target value is a floating point. You are guaranteed to have only one unique value in the BST that is closest to the target. /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public int closestValue(TreeNode root, double target) { double abs = Math.abs(target-root.val); int res = 0; while(root != null){ if(abs>= Math.abs(target-root.val)){ res = root.val; abs = Math.abs(target-root.val); } if(target<root.val) root = root.left; else root = root.right; } return res; } }

# 100. Same Tree

Given two binary trees, write a function to check if they are equal or not. Two binary trees are considered equal if they are structurally identical and the nodes have the same value. /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public boolean isSameTree(TreeNode p, TreeNode q) { if(q == null && p == null) return true; if(!checks(p,q)) return false; Queue<TreeNode> nodesp = new LinkedList<TreeNode>(); nodesp.add(p); Queue<TreeNode> nodesq = new LinkedList<TreeNode>(); nodesq.add(q); while(!nodesp.isEmpty()){ int n = nodesp.size(); while(n>0){ TreeNode currp = nodesp.poll(); TreeNode currq = nodesq.poll(); if(currq.val != currp.val) return false; if(!checks(currq.right,currp.right)) return false; if(!checks(currq.left,currp.left)) return false; if(currp.left != null){ nodesp.add(currp.left); nodesq.add(currq.left); } if(currp.right != null){ nodesp.add(currp.right); nodesq.add(currq.right); } n–; } } return true; } public boolean checks(TreeNode p, TreeNode q){ if(q == null && p == null) return true; if((q ==null && p != null) || (p ==null && q != null)) return false; int a =p.val; int b = q.val; if(p.val != q.val) return false; return true; } }

# 107. Binary Tree Level Order Traversal II

Given a binary tree, return the bottom-up level order traversal of its nodes’ values. (ie, from left to right, level by level from leaf to root). For example: Given binary tree [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7 return its bottom-up level order traversal as: [ [15,7], [9,20], [3] ]   /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public List<List<Integer>> levelOrderBottom(TreeNode root) { Queue<TreeNode> nodes = new LinkedList<TreeNode>(); List<List<Integer>> res = new LinkedList(); if(root == null) return res; nodes.add(root); while(!nodes.isEmpty()){ List<Integer> sub = new LinkedList(); int num = nodes.size(); for(int i=0;i<num;i++){ TreeNode curr = nodes.poll(); sub.add(curr.val); if(curr.left != null) nodes.add(curr.left); if(curr.right != null) nodes.add(curr.right); } res.add(0,sub); } return res; } }

# 257. Binary Tree Paths

Given a binary tree, return all root-to-leaf paths. For example, given the following binary tree: 1 / \ 2 3 \ 5 All root-to-leaf paths are: [“1->2->5”, “1->3″] 这道题直接DFS过 /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public List<String> binaryTreePaths(TreeNode root) { List<String> res= new ArrayList<String>(); if(root != null){ DFS(root,””,res); } return res; } public void DFS(TreeNode root, String val, List<String> res){ if(root.left == null && root.right == null){ res.add(val+root.val); } if(root.left != null){ DFS(root.left, val+ root.val+”->”,res); } if(root.right != null){ DFS(root.right, val+ root.val+”->”,res); } } }

# 400. Nth Digit

Find the nth digit of the infinite integer sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, … Note: n is positive and will fit within the range of a 32-bit signed integer (n < 231). Example 1: Input: 3 Output: 3 Example 2: Input: 11 Output: 0 Explanation: The 11th digit of the sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, … is a 0, which is part of the number 10.  思路： 这道题其实停费脑子的，先要找到区间，然后找到位置 class Solution { public int findNthDigit(int n) { if(n<10) return n; long num = 9; int count = 1; while(n > count * num){ n -= num * count; count ++; num *= 10; } long res = num/9 + (n-1)/count; return Integer.parseInt(String.valueOf(res).substring((n-1)%count, (n-1)%count+1)); } }

# 645. Set Mismatch

The set S originally contains numbers from 1 to n. But unfortunately, due to the data error, one of the numbers in the set got duplicated to another number in the set, which results in repetition of one number and loss of another number. Given an array nums representing the data status of this set after the error. Your task is to firstly find the number occurs twice and then find the number that is missing. Return them in the form of an array. Example 1: Input: nums = [1,2,2,4] Output: [2,3] Note: The given array size will in the range [2, 10000]. The given array’s numbers won’t have any order. 这道题看上去容易，但是写起来有点难度，用了取巧的方法，其实还有个高阶的办法（自遍历），之后题目在写。 class Solution { public int[] findErrorNums(int[] nums) { HashSet set = new HashSet(); int[] res = new int[2]; int sum = nums.length*(nums.length+1)/2; for(int i=1;i<=nums.length;i++){ if(!set.add(nums[i-1])){ res[0] = nums[i-1]; } sum -= nums[i-1]; } res[1] = sum+res[0]; return res; } }

# 202. Happy Number

Write an algorithm to determine if a number is “happy”. A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers. Example: 19 is a happy number 12 + 92 = 82 82 + 22 = 68 62 + 82 = 100 12 + 02 + 02 = 1 class Solution { public boolean isHappy(int n) { HashSet set = new HashSet(); int re; while(set.add(n)){ int sum =0; while(n>0){ re = n%10; sum += re * re; n /= 10; } if(sum ==1) return true; n = sum; } return n==1; } }