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

zengm321 发表于 2014-12-28 07:32
有些新题，不错啊

谢谢，最近发现不能编辑以前的帖子了，不知道是不是我不够级别。

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. }

复制代码

STACK
amazon oa 最新面试题

Validate statement
Given an input expression that can contain positive integers,

parenthesis or square brackets, return if the input is balanced. An

expression is considered balanced if it has the following form: (

expression ) OR [ expression ] and If expression is also balanced.

Input Format:
A string where characters could be either a number or ( ) [ ]

Output Format:
A boolean, true if the input is balanced, false otherwise.

Sample Input #1:
([5 2 ] 12 )

Sample Output #1:
true
Explanation:
The square brackets are correctly closed before the parenthesis


Sample Input #2:
40 [12 23 [4 5 ( 12 ) ) ]

Sample Output #2:
false

Explanation:
The second square bracket does not have a corresponding closing one, a

parenthesis appears instead.

Sample Input #3:
13 56 89 103

Sample Output #2:
true

Explanation:
The expression doesn't contain any ()[] and it is considered balanced.

1. public class ValidateStatement {
   
2. 
   
3.     static boolean isBalanced(String input) {
   
4.         if (input == null) {
   
5.             return true;
   
6.         }
   
7.         Stack<Character> stack = new Stack<Character>();
   
8.         Map<Character, Character> map = new HashMap<Character, Character>();
   
9.         map.put('(', ')');
   
10.         map.put('[', ']');
    
11.         for (int i = 0; i < input.length(); ++i) {
    
12.             char ch = input.charAt(i);
    
13.             if (ch == '(' || ch == '[') {
    
14.                 stack.push(ch);
    
15.             } else if (!Character.isDigit(ch) && !Character.isWhitespace(ch)) {
    
16.                 if (stack.isEmpty() || map.get(stack.peek()) == null
    
17.                         || !stack.pop().equals(ch)) {
    
18.                     return false;
    
19.                 }
    
20.             }
    
21.         }
    
22.         return stack.isEmpty();
    
23.     }
    
24. }

复制代码

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. }

复制代码

Validate Binary Search Tree

这道题，我用你的代码，但是把和int相关的都改成long，如

Long.MIN_VALUE 和 Long.MAX_VALUE
private boolean valid(TreeNode node, long low, long high)

也可以accept

--------------------------------

看了下已经有回复了~ 解释的比较清楚

楼主怎么最近不更新啦

刷了60多道了，更新慢了

helifort 发表于 2014-12-25 17:47
STRING
Longest Substring with At Most Two Distinct Characters

按照楼主的方法在eclipse上执行了一遍，结果不对

helifort 发表于 2014-12-25 19:22
ARRAY
Two Sum
github link

楼主的o(1)做法只能是sorted array吧，不过题目没有说是sorted的