- Longest Substring Without Repeating Characters
雖然這是一個hash table的題目盛卡，但是我的第一反應是用一個長為26的array來儲存已經(jīng)出現(xiàn)過的character信息的方法婿奔。但是我又想使用two pointer的方法，所以必須在挪動pointer的時候要知道start要挪向哪里叉橱。而只用array來記錄信息的話只能記住在某個區(qū)間character出現(xiàn)的次數(shù)，無法記住character出現(xiàn)的位置查邢。
所以還是必須使用hash table的方法鄙才，用key來記錄character，value來記錄這個character最后出現(xiàn)的位置择吊。
class Solution {
public int lengthOfLongestSubstring(String s) {
// key: character; value: the last appear index
Map<Character, Integer> map = new HashMap<>();
int maxCount = 0, count = 0, start = 0;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (map.containsKey(c)) {
int pos = map.get(c);
if (pos >= start) {
maxCount = Math.max(maxCount, count);
count = i - pos;
start = pos + 1;
} else {
count++;
}
} else {
count++;
}
map.put(c, i);
}
maxCount = Math.max(maxCount, count);
return maxCount;
}
}
- Copy List with Random Pointer
LinkedList的deep copy問題
這題想法挺簡單的李根。先在每個node后面復制這個node，得到A -> A' -> B -> B'這種形式几睛，在加上random node房轿，最后把兩個list分隔開。
但是實現(xiàn)過程中還是有很多坑的所森，因為是copy問題囱持，所以最后的結果中不能將最初的list破壞。
/*
// Definition for a Node.
class Node {
public int val;
public Node next;
public Node random;
public Node() {}
public Node(int _val,Node _next,Node _random) {
val = _val;
next = _next;
random = _random;
}
};
*/
class Solution {
public Node copyRandomList(Node head) {
if (head == null) {
return head;
}
// copy each node
Node ptr = head;
while (ptr != null) {
Node newNode = new Node(ptr.val);
Node next = ptr.next;
ptr.next = newNode;
newNode.next = next;
ptr = next;
}
// add random to the new copied node
ptr = head;
while (ptr != null) {
ptr.next.random = (ptr.random == null)? null: ptr.random.next;
ptr = ptr.next.next;
}
// seperate these two node
Node new_head = head.next, old_head = head;
Node res = new_head;
while (old_head != null && old_head.next.next != null) {
old_head.next = new_head.next;
new_head.next = new_head.next.next;
old_head = old_head.next;
new_head = new_head.next;
}
old_head.next = null;
return res;
}
}
- Happy Number
這道題很明顯應當用recursion的解法焕济，但recursion需要base case纷妆，在這里bestcase 最小的即使單個數(shù)字，因此現(xiàn)自己計算個位數(shù)是否是happy number作為base case晴弃。
class Solution {
public boolean isHappy(int n) {
if (n <= 0) {
return false;
}
// recursion
// base case: when n < 10, only when n = 1 or 7 it is happy number
if (n < 10) {
if (n == 1 || n == 7) {
return true;
}
return false;
}
int sum = 0;
while (n > 0) {
sum += (n%10)*(n%10);
n /= 10;
}
return isHappy(sum);
}
}
