## [LintCode] Segment Tree Build

public SegmentTreeNode build(int start, int end) { // write your code here if(start > end) return null; SegmentTreeNode root = new SegmentTreeNode(start, end); // root if(start < end) { int mid = start + (end – start) / 2; root.left = build(start, mid); root.right = build(mid+1, end); } return root; }

## [LintCode] Triangle Count

public int triangleCount(int S[]) { // write your code here int res = 0; if(S.length == 0 || S == null) return res; Arrays.sort(S); for(int i = S.length – 1; i > 0; i–) { int l = 0; int r = i – 1; while(l < r) { if(S[l] + S[r] > S[i]){ res […]

## [LintCode] Convert Sorted Array to Binary Search Tree With Minimal Height

public TreeNode sortedArrayToBST(int[] A) { // write your code here return rec(A,0, A.length – 1); } public TreeNode rec(int[] A, int start, int end) { if(start > end) return null; int mid = start + (end – start) / 2; TreeNode root = new TreeNode(A[mid]); root.left = rec(A,start,mid-1); root.right = rec(A,mid+1, end); return root; }

## [LintCode] Reverse Integer

public int reverseInteger(int n) { // Write your code here int num = Math.abs(n); int res = 0; while(num != 0) { if(res > (Integer.MAX_VALUE – num%10) / 10) return 0; // corn case; res = res*10 + num %10; num /= 10; } return n > 0 ? res : -res; }

public String addBinary(String a, String b) { // int carry=0; // String result=””; // int i=0; // int alen=a.length(); // int blen=b.length(); // while(i<alen||i<blen||carry!=0){ // int x=(i<alen)?((a.charAt(alen-1-i)==’1′)?1:0):0; // int y=(i<blen)?((b.charAt(blen-1-i)==’1′)?1:0):0; // result=(x+y+carry)%2+result; // carry=(x+y+carry)/2; // i++; int carry = 0; String res = “”; int i = 0; int aLen = a.length(); int bLen = […]

## [LintCode] Valid Palindrome

public boolean isPalindrome(String s) { // Write your code here if(s.length() == 0 || s == null) return true; s = s.toLowerCase(); s = s.trim(); int i = 0; int j = s.length() – 1; while(i <= j) { while(i <= j && !((s.charAt(i) <= ‘z’ && s.charAt(i) >= ‘a’) || (s.charAt(i) >= ‘0’ && […]

## [LintCode] Merge Intervals

public List<Interval> merge(List<Interval> intervals) { // write your code here List<Interval> res= new ArrayList<Interval>(); if(intervals.size() == 0 || intervals == null) return res; Collections.sort(intervals, new IntervalComparator()); Interval first = intervals.get(0); for(int i = 1; i < intervals.size(); i++) { Interval cur = intervals.get(i); if(cur.start <= first.end) { first.end = Math.max(cur.end, first.end); }else{ res.add(first); first = […]

## [LintCode] Subtree

public boolean isSubtree(TreeNode T1, TreeNode T2) { // write your code here if(T2 == null) return true; else if(T1 == null) return false; else return isSameTree(T1, T2) || isSubtree(T1.left, T2) || isSubtree(T1.right, T2); } public boolean isSameTree(TreeNode T1, TreeNode T2) { if(T1 == null && T2 == null) return true; if(T1 == null || T2 […]

## [LintCode] Length of Last Word

public int lengthOfLastWord(String s) { // Write your code here if(s == null || s.length() == 0) return 0; for(int i = s.length()-1; i >=0; i–) { if(s.charAt(i) != ‘ ‘) { int res = 0; while(i >=0 && s.charAt(i) != ‘ ‘ ){ res++; i–; } return res; } } return 0; }

## [LintCode] Find the Missing Number

public int findMissing(int[] nums) { // write your code here if(nums.length == 0 || nums == null) return 0; int missing = 0; int n = nums.length; for(int i = 0; i <= n; i++) { missing^=i; } // xor [0,n] for(int i : nums) missi raneng ^= i;//xor i, i in nums return missing; […]