[webdriver]

LeetCode (used to call i has 1337 code) is a social platform for preparing IT technical interviews. We strive to provide you with the best learning experience in preparing interviews for companies in the IT industry.

To be successful in a technical interview, we believe it is mainly repeating these three important steps:

Code. Read. Discuss.

We strive to provide you the LeetCode platform as the ultimate solution for preparing technical interviews.

1. Code -> Code solution using the Online Judge system.
2. Read -> Read high quality article featuring in-depth thought process. Also read other LeetCoders’ code.
3. Discuss -> Discuss your thoughts about the problem with other LeetCoders.

We hope that through our platform, you will grow into a LeetCoder. Not only will you be successful in all of your interviews, and most importantly, you will be a better coder in general !

This is Part 2 (Java Solution)

Part 1: www.westca.com/Forums/...inese.html

[webdriver]

S算法問題: Longest Palindromic Substring
問題描述:
Given a string S, find the longest palindromic substring in S.
You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

[webdriver]

算法問題推薦解法來了...

1. Time O(n^2), Space O(n^2)
2. Time O(n^2), Space O(n)
3. Time O(n^2), Space O(1) (actually much more efficient than 1 & 2)
4. Time O(n), Space O(n) (Manacher's Algorithm)

解法（Java）

代碼:

public class LongestPalindromicSubstring {    public String longestPalindrome(String s) {       int length = s.length();       String result = "";       for (int i = 0; i < length; i++) {          String ps = getPalindrome(s, i, i);          if (ps.length() > result.length()) {             result = ps;          }          ps = getPalindrome(s, i, i + 1);          if (ps.length() > result.length()) {             result = ps;          }       }       return result;    }    private String getPalindrome(String s, int l, int r) {       while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {          l--;          r++;       }       return s.substring(l + 1, r);    } }

[webdriver]

S算法問題: Longest Substring Without Repeating Characters
問題描述:
Given a string, find the length of the longest substring without repeating characters.
For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3.
For "bbbbb" the longest substring is "b", with the length of 1.

[webdriver]

算法問題推薦解法來了...

Pay attention when moving the 'start' pointer forward.

解法（Java）

代碼:

import java.util.HashMap; public class LongestSubstringWithoutRepeatingCharacters {    public int lengthOfLongestSubstring(String s) {       if (s.length() == 0)          return 0;       int i = 0, j = 0;       int result = 0;       HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();       while (j < s.length()) {          Integer c = new Integer(s.charAt(j));          if (!map.containsKey(c)) {             map.put(c, j);          } else {             int length = j - i;             if (result < length) {                result = length;             }             Integer index = map.get(c);             i = Math.max(i, index + 1);             map.put(c, j);          }          j++;       }       if (result < j - i)          return j - i;       else          return result;    } }

[webdriver]

==== 今天的學習很緊張 ====

[webdriver]

S算法問題: LowestCommonAncestorOfaBinarySearchTree
問題描述:

Lowest Common Ancestor of a Binary Search Tree (BST)

Given a binary search tree (BST), find the lowest common ancestor of two given nodes in the BST.


_______6______
\
___2__ ___8__
\ \
0 _4 7 9
\
3 5
Using the above tree as an example, the lowest common ancestor (LCA) of nodes 2 and 8 is 6.
But how about LCA of nodes 2 and 4? Should it be 6 or 2?

According to the definition of LCA on Wikipedia: ??The lowest common ancestor is defined between
two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a
node to be a descendant of itself).?? Since a node can be a descendant of itself, the LCA of 2 and
4 should be 2, according to this definition.

Hint:
A top-down walk from the root of the tree is enough.

[webdriver]

算法問題推薦解法來了...



解法（Java）

代碼:

public class LowestCommonAncestorOfaBinarySearchTree {    public TreeNode LCA(TreeNode root, TreeNode p, TreeNode q) {       if (root == null || p == null || q == null)          return null;       if (Math.max(p.val, q.val) < root.val)          return LCA(root.left, p, q);       if (Math.min(p.val, q.val) > root.val)          return LCA(root.right, p, q);       return root;    } }

[webdriver]

S算法問題: LowestCommonAncestorOfBinaryTree
問題描述:

Given a binary tree, find the lowest common ancestor of two given nodes in the tree.


_______3______
\
___5__ ___1__
\ \
6 _2 0 8
\
7 4
If you are not so sure about the definition of lowest common ancestor (LCA), please refer to my previous
post: Lowest Common Ancestor of a Binary Search Tree (BST) or the definition of LCA here. Using the tree
above as an example, the LCA of nodes 5 and 1 is 3. Please note that LCA for nodes 5 and 4 is 5.

Hint:
Top-down or bottom-up? Consider both approaches and see which one is more efficient.

[webdriver]

算法問題推薦解法來了...



解法（Java）

代碼:

public class LowestCommonAncestorOfBinaryTree {    public TreeNode LCA(TreeNode root, TreeNode p, TreeNode q) {       if (root == null)          return null;       if (root == p || root == q)          return root;       TreeNode left = LCA(root.left, p, q);       TreeNode right = LCA(root.right, p, q);       if (left != null && right != null)          return root;       return left != null ? left : right;    } }