-
第 21 樓 / 陸壓
- 時間: 2014-9-28 01:28
webdriver 寫道:S算法問題: Merge Sorted Array
問題描述:
Given two sorted integer arrays A and B, merge B into A as one sorted array.
Note:
You may assume that A has enough space to hold additional elements from B.
The number of elements initialized in A and B are m and n respectively.
活人? -
-
- 時間: 2014-9-28 01:28
-
-
- 時間: 2014-9-28 01:29
-
- 時間: 2014-9-28 01:29算法問題推薦解法來了...
...
解法（Java）
代碼:
public class MergeTwoSortedLists {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode head = new ListNode(0);
ListNode cur = head;
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) {
cur.next = l1;
l1 = l1.next;
} else {
cur.next = l2;
l2 = l2.next;
}
cur = cur.next;
}
if (l1 != null) {
cur.next = l1;
} else {
cur.next = l2;
}
return head.next;
}
} -
- 時間: 2014-9-28 01:34S算法問題: Longest Valid Parentheses
問題描述:
Given a string containing just the characters '(' and ')', find the length of the longest valid
(well-formed) parentheses substring.
For "(()", the longest valid parentheses substring is "()", which has length = 2.
Another example is ")()())", where the longest valid parentheses substring is "()()",
which has length = 4. -
- 時間: 2014-9-28 01:34算法問題推薦解法來了...
O(n).
解法（Java）
代碼: import java.util.Stack;
public class LongestValidParentheses {
public int longestValidParentheses(String s) {
int length = s.length();
if (length == 0)
return 0;
int left = 0;
Stack<Integer> indexs = new Stack<Integer>();
boolean[] record = new boolean[length];
for (int i = 0; i < length; i++) {
if (s.charAt(i) == '(') {
left++;
indexs.push(i);
} else if (left > 0) {
int idx = indexs.pop();
record[idx] = true;
record[i] = true;
left--;
}
}
int ret = 0;
int current = 0;
for (int k = 0; k < length; k++) {
if (record[k]) {
current++;
} else {
ret = current > ret ? current : ret;
current = 0;
}
}
return ret > current ? ret : current;
}
} -
- 時間: 2014-9-28 01:36S算法問題: LRU Cache
問題描述:
Design and implement a data structure for Least Recently Used (LRU) cache.
It should support the following operations: get and set.
get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item. -
- 時間: 2014-9-28 01:36算法問題推薦解法來了...
Hash + list.
解法（Java）
代碼:
import java.util.HashMap;
import java.util.Map;
public class LRUCache {
public class CacheItem<K, V> {
private K key;
private V value;
private CacheItem<K, V> prev;
private CacheItem<K, V> next;
public CacheItem<K, V> getPrev() {
return prev;
}
public void setPrev(CacheItem<K, V> prev) {
this.prev = prev;
}
public CacheItem<K, V> getNext() {
return next;
}
public void setNext(CacheItem<K, V> next) {
this.next = next;
}
public CacheItem(K key, V value) {
this.key = key;
this.value = value;
}
}
public class BidirectionalList<K, V> {
private CacheItem<K, V> head = new CacheItem<K, V>(null, null);
private CacheItem<K, V> tail = head;
public void insertTail(CacheItem<K, V> node) {
tail.next = node;
node.prev = tail;
node.next = null;
tail = node;
}
public void delete(CacheItem<K, V> node) {
if (head.next == null)
return;
if (node == head.next) {
deleteHead();
} else if (node == tail) {
deleteTail();
} else {
node.prev.next = node.next;
node.next.prev = node.prev;
node.next = null;
node.prev = null;
}
}
public CacheItem<K, V> deleteTail() {
if (head.next == null)
return null;
CacheItem<K, V> ret = tail;
tail = tail.prev;
tail.next = null;
ret.prev = null;
ret.next = null;
return ret;
}
public CacheItem<K, V> deleteHead() {
if (head.next == null)
return null;
if (head.next == tail) {
tail = tail.prev;
}
CacheItem<K, V> ret = head.next;
head.next = ret.next;
if (ret.next != null) {
ret.next.prev = head;
}
ret.next = null;
ret.prev = null;
return ret;
}
}
private Map<Integer, CacheItem<Integer, Integer>> cacheMap = new HashMap<Integer, CacheItem<Integer, Integer>>();
private BidirectionalList<Integer, Integer> cacheList = new BidirectionalList<Integer, Integer>();
private int cacheSize = 0;
private int capacity;
public LRUCache(int capacity) {
this.capacity = capacity;
}
public int get(int key) {
CacheItem<Integer, Integer> itm = cacheMap.get(key);
if (itm == null)
return -1;
cacheList.delete(itm);
cacheList.insertTail(itm);
return itm.value.intValue();
}
public void set(int key, int value) {
if (cacheMap.containsKey(key)) {
updateItem(key, value);
} else if (cacheSize == capacity && removeLeastUsed()) {
cacheSize--;
addItem(key, value);
} else {
addItem(key, value);
}
}
private void addItem(int key, int value) {
CacheItem<Integer, Integer> newCacheItem = new CacheItem<Integer, Integer>(
key, value);
cacheList.insertTail(newCacheItem);
cacheMap.put(key, newCacheItem);
cacheSize++;
}
private void updateItem(int key, int value) {
CacheItem<Integer, Integer> exitedKey = cacheMap.get(key);
exitedKey.value = value;
cacheList.delete(exitedKey);
cacheList.insertTail(exitedKey);
}
private boolean removeLeastUsed() {
CacheItem<Integer, Integer> removedKey = cacheList.deleteHead();
cacheMap.remove(removedKey.key);
return removedKey == null ? false : true;
}
}
-
- 時間: 2014-9-28 01:38
-
- 時間: 2014-9-28 01:39
Leetcode Hacking Practice -- Solution in Java Part 2
