The problem is from a post on mitbbs: http://www.mitbbs.com/article_t/CS/31217531.html
For example, longest palindrome in “animal” is “ana”, then return 3. Longest palindrome of “sfinished” is “sinis”, so return 5.
This is actually a dp problem for longest common substring. We just easily find the longest common substring between “animal” with “lamina”, that will be the result.
Check my code on github: link
This problem is from G4G: http://www.geeksforgeeks.org/find-k-such-that-all-elements-in-kth-row-are-0-and-kth-column-are-1-in-a-boolean-matrix/
The problem ask us to find a number k, where the kth row of is all 0, kth column is all 1 too. The value of [k, k] can be either 0 or 1. Take below array as example:
The kth row/column should be 3:
The trick of this problem is that if there is an result, there is only one zero-row. There mustn’t be more than 1 rows. Look at below array, it has 2 all-zero rows(green ones). But it won’t has valid all-one column.
In this way, we just find the potential all-zero row. And we don’t even need to look at the all-one column. As long as we found an potential k, then we check if it is the result.
I gave out a finding process. When it arrives step 4, we are already able to eliminate column 0, 1 and row 0, 1. Then we go on start at row 2, column 2.
Find my code on github: link
This is the code from junmin, link. Our difference is that my code moves row faster than his code
LRU can be implemented by map and doubly-linked-list.
The key idea is that:
1. Maintain a head and tail, which is not null initially,
2. In Node, we store both key and value,
3. Create pickUp and setHead functions.
public class LRUCache {
class Node {
int key;
int val;
Node pre;
Node next;
public Node(int key, int val) {
this.key = key;
this.val = val;
}
}
int capacity;
HashMap<Integer, Node> hm;
Node head;
Node tail;
public LRUCache(int capacity) {
this.capacity = capacity;
this.hm = new HashMap<>();
this.head = new Node(-1, -1);
this.tail = new Node(-1, -1);
head.next = tail;
tail.pre = head;
}
public int get(int key) {
Node node = hm.get(key);
if (node == null) {
return -1;
}
pickNode(node);
setHead(node);
return node.val;
}
public void set(int key, int value) {
Node node = hm.get(key);
if (node != null) {
pickNode(node);
setHead(node);
node.val = value;
return;
}
node = new Node(key, value);
setHead(node);
hm.put(key, node);
if (hm.size() > capacity) {
hm.remove(tail.pre.key);
tail.pre.pre.next = tail;
tail.pre = tail.pre.pre;
return;
}
}
public void pickNode(Node node) {
node.pre.next = node.next;
node.next.pre = node.pre;
}
private void setHead(Node node) {
node.pre = head;
node.next = head.next;
head.next.pre = node;
head.next = node;
}
}