LeetCode 刷题贴 JAVA代码，每日更新

此贴用于刷题训练，保证每日更新，包括cleencode新题在内所有leetcode题目
You have solved 24 / 169 problems.

ARRAY

• Missing Ranges
• Two Sum
• Two Sum II
  

BINARY TREE

• Validate Binary Search Tree
• Maximum Depth of Binary Tree
• Minimum Depth of Binary Tree
  

DP

• Edit Distance
• Longest Palindromic Substring
  

LINKED LIST

• Add Two Numbers
• Merge Two Sorted Lists
• Swap Nodes in Pairs
• Merge K Sorted Linked Lists
  

MATH

• Palindrome Number
• Plus One
• Reverse Integer
  

STRING

• String to Integer
• Valid Palindrome
• Longest Palindromic Substring
• Longest Substring with At Most Two Distinct Characters
• Longest Substring Without Repeating Characters
• One Edit Distance
• Read N Characters Given Read4
• Reverse Words in a String
• Rotate String
• Implement strStr()
• Valid Number
  

BINARY TREE
Validate Binary Search Tree
Given a binary tree, determine if it is a valid Binary Search Tree (BST).
Solution:
Time: O(n)
Space: O(n) stack space
Code:

1. public class ValidateBinarySearchTree {
   
2.     public boolean isValidBST(TreeNode root) {
   
3.         return valid(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
   
4.     }
   
5. 
   
6.     private boolean valid(TreeNode node, int low, int high) {
   
7.         if (node == null) {
   
8.             return true;
   
9.         }
   
10.         if (node.val > low && node.val < high) {
    
11.             return valid(node.left, low, node.val)
    
12.                     && valid(node.right, node.val, high);
    
13.         } else {
    
14.             return false;
    
15.         }
    
16.     }
    
17. }

复制代码

今天提交的这个代码，本人看不出啥问题，但是OJ没有过，失败的case是
67 / 74 test cases passed.

Input:	{2147483647}
Output:	false
Expected:	true

请大神指示，哪里有问题。

flyaway25 发表于 2014-12-25 00:46
bst里面的node不能相等，那个返回true的逻辑还应该是>和

是的，疏忽疏忽
我要表达的意思是这段代码只要input里面有2147483647或-2147483648就会fail

DP
Longest Palindromic Substring

Time: O(n^2)
Space: O(n)

github link

1. public class LongestPalindromicSubstring {
   
2.     /*
   
3.     * DP
   
4.     * Time: O(n^2)
   
5.     * Space: O(n)
   
6.     * */
   
7.     public String longestPalindrome(String s) {
   
8.         if (s == null || s.length() == 0) {
   
9.             return null;
   
10.         }
    
11.         String result = "";
    
12.         int maxLen = 0;
    
13.         boolean[][] isPalin = isPalindrome(s);
    
14.         for (int i = 0; i < s.length(); i++) {
    
15.             for (int j = i; j < s.length(); j++) {
    
16.                 if (isPalin[i][j]) {
    
17.                     if (j - i + 1 > maxLen) {
    
18.                         maxLen = j - i + 1;
    
19.                         result = s.substring(i, j + 1);
    
20.                     }
    
21. 
    
22.                 }
    
23.             }
    
24.         }
    
25.         return result;
    
26.     }
    
27. 
    
28.     private boolean[][] isPalindrome(String s) {
    
29.         boolean[][] dp = new boolean[s.length()][s.length()];
    
30.         for (int i = 0; i < s.length() - 1; i++) {
    
31.             dp[i][i] = true;
    
32.             if (s.charAt(i) == s.charAt(i + 1)) {
    
33.                 dp[i][i + 1] = true;
    
34.             }
    
35.         }
    
36.         dp[s.length() - 1][s.length() - 1] = true;
    
37.         for (int i = s.length() - 3; i >= 0; i--) {
    
38.             for (int j = i + 2; j < s.length(); j++) {
    
39.                 if (dp[i + 1][j - 1] && s.charAt(i) == s.charAt(j)) {
    
40.                     dp[i][j] = true;
    
41.                 } else {
    
42.                     dp[i][j] = false;
    
43.                 }
    
44.             }
    
45.         }
    
46.         return dp;
    
47.     }
    
48. }

复制代码

LINKED LIST
Amazon oa最新面试题

List manipulation
Write a function that receives a link list of integers and manipulates the nodes by merging the first and second half of the list. For example, given a list with nodes L1->L2->L3->R1->R2->R3, the function will rearrange the nodes to produce L1->R1->L2->R2->L3->R3.
The code for reading input and writing output is provided along with a method stub.  Please complete the method to produce the correct output.  You have the ability to create your own test cases.  If you would like to do so, the input and output formats are listed below.

Input Format:
Line 1: Number of elements in the list.
Line 2 to N+1: A node value per line starting with the root value.

Output Format:
The values rearranged, starting with root. One value per line.

Sample Input #1:
4
1
2
3
4

Sample Output #00:
1
3
2
4

Sample Input #01:
5
10
20
30
40
50

Sample Output #01:
10
30
20
40
50

1. public class ListManipulation {
   
2.     static LinkedListNode manipulateList(LinkedListNode root) {
   
3.         if (root == null || root.next == null) {
   
4.             return root;
   
5.         }
   
6.         LinkedListNode mid = getMid(root);
   
7.         LinkedListNode half = mid.next;
   
8.         mid.next = null;
   
9.         LinkedListNode cur1 = root, cur2 = half;
   
10.         while (cur1 != null) {
    
11.             LinkedListNode next1 = cur1.next, next2 = cur2.next;
    
12.             cur1.next = cur2;
    
13.             //if next1 == null, cur2.next will not be changed.
    
14.             if (next1 != null) {
    
15.                 cur2.next = next1;
    
16.             }
    
17.             cur1 = next1;
    
18.             cur2 = next2;
    
19.         }
    
20.         return root;
    
21. 
    
22.     }
    
23. 
    
24.     static LinkedListNode getMid(LinkedListNode root) {
    
25.         LinkedListNode slow = root, fast = root.next.next;
    
26.         while (fast != null && fast.next != null) {
    
27.             slow = slow.next;
    
28.             fast = fast.next.next;
    
29.         }
    
30.         return slow;
    
31.     }
    
32. }

复制代码

if (node.val > low && node.val < high) {
换成>=和<=

Freetymekiyan 发表于 2014-12-25 12:48
if (node.val > low && node.val < high) {
换成>=和

谢谢大神指点，不过，改成>= <=之后还是没过测试，失败的例子如下。貌似相等的就应该是false

64 / 74 test cases passed.
Status: Wrong Answer
Submitted: 0 minutes ago
Input:        {1,1}
Output:        true
Expected:        false

helifort 发表于 2014-12-25 00:23
谢谢大神指点，不过，改成>=

Sorry node.val是要在low和high的range当中
我的意思其实是，Integer.MAX_VALUE和Integer.MIN_VALUE也可以是node的值
看input是Integer.MAX_VALUE，你的code直接会返回false

helifort 发表于 2014-12-25 13:23
谢谢大神指点，不过，改成>=

bst里面的node不能相等，那个返回true的逻辑还应该是>和<。把那个input的low和high换成null试试，然后里面加个判定只有在low和high不是null的情况下比较大小。

另一个O(n)时间复杂度的方法，就是用in order 的方式遍历BST，判断遍历的节点是单调递增的，需要定义一个全局变量存放前缀节点。
Time: O(n)
Space: O(n)

code:

1. public class Solution {
   
2.     private TreeNode prev;
   
3.     public boolean isValidBST(TreeNode root) {
   
4.         prev = null;
   
5.         return isIncreasing(root);
   
6.     }
   
7. 
   
8.     private boolean isIncreasing(TreeNode node) {
   
9.         if (node == null) {
   
10.             return true;
    
11.         }
    
12.         if (isIncreasing(node.left)) {
    
13.             if (prev != null && prev.val >= node.val) {
    
14.                 return false;
    
15.             }
    
16.             prev = node;
    
17.             return isIncreasing(node.right);
    
18.         }
    
19.         return false;
    
20.     }
    
21. }

复制代码

这段代码OJ成功了

flyaway25 发表于 2014-12-25 13:46
bst里面的node不能相等，那个返回true的逻辑还应该是>和

谢谢fly大神，这次对了，因为测试case是int最大值

code:

1. public class Solution {
   
2.     public boolean isValidBST(TreeNode root) {
   
3.         return valid(root, null, null);
   
4.     }
   
5. 
   
6.     private boolean valid(TreeNode node, Integer left, Integer right) {
   
7.         if (node == null) {
   
8.             return true;
   
9.         }
   
10.         if ((left == null || left < node.val) && (right == null || right > node.val)) {
    
11.             return valid(node.left, left, (Integer)node.val)
    
12.                     && valid(node.right, (Integer)node.val, right);
    
13.         }
    
14.         return false;
    
15.     }
    
16. }

复制代码

Freetymekiyan 发表于 2014-12-25 13:38
Sorry node.val是要在low和high的range当中
我的意思其实是，Integer.MAX_VALUE和Integer.MIN_VALUE也可 ...

对，明白了。

BINARY TREE

Maximum Depth of Binary Tree

O(n) runtime, O(log n) space – Recursion:

1. public int maxDepth(TreeNode root) {
   
2.     if (root == null) {
   
3.         return 0;
   
4.     }
   
5.     return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
   
6. }

复制代码