发表于 | 分类于

Design and implement a data structure for Least Frequently Used (LFU) cache. It should support the following operations: get and put.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
put(key, value) - Set or insert the value if the key is not already present. When the cache reaches its capacity, it should invalidate the least frequently used item before inserting a new item. For the purpose of this problem, when there is a tie (i.e., two or more keys that have the same frequency), the least recently used key would be evicted.

Follow up:
Could you do both operations in O(1) time complexity?

Example:

1
2
3
4
5
6
7
8
9
10
11
12
LFUCache cache = new LFUCache( 2 /* capacity */ );
cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // returns 1
cache.put(3, 3);    // evicts key 2
cache.get(2);       // returns -1 (not found)
cache.get(3);       // returns 3.
cache.put(4, 4);    // evicts key 1.
cache.get(1);       // returns -1 (not found)
cache.get(3);       // returns 3
cache.get(4);       // returns 4

解法1：

1
2

发表于 | 分类于

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

For example,
S = “ADOBECODEBANC”
T = “ABC”
Minimum window is “BANC”.

Note:
If there is no such window in S that covers all characters in T, return the empty string “”.

If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.

解法1： Sliding Window

直接用Sliding Window的模板来做。维护一个map来存每一个字符出现的次数,用一个指针start记录substring的左边界然后遍历就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class Solution {
    public String minWindow(String s, String t) {
        // sliding window problem
        if (t == null || t.length() == 0) {
            return "";
        }
        if (s == null || s.length() == 0) {
            return "";
        }
        //
        Map<Character, Integer> map = new HashMap<>();
        for (char ch : t.toCharArray()) {
            map.put(ch, map.getOrDefault(ch, 0) + 1);
        }
        int count = t.length();
        int start = 0;
        int minLen = Integer.MAX_VALUE;
        String res = "";
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (map.containsKey(ch)) {
                map.put(ch, map.get(ch) - 1);   // decrease by one
                if (map.get(ch) >= 0) {
                    count--;
                }
                while (count == 0) {
                    // update result string
                    int len = i - start + 1;
                    if (len < minLen) {
                        minLen = len;
                        res = s.substring(start, i + 1);
                    }
                    char temp = s.charAt(start);
                    if (map.containsKey(temp)) {
                        map.put(temp, map.get(temp) + 1);
                        if (map.get(temp) > 0) {
                            count++;
                        }
                    }
                    start++;    // move start
                }
            }
        }
        return res;
    }
}

发表于 | 分类于

Validate if a given string is numeric.

Some examples:
“0” => true
“ 0.1 “ => true
“abc” => false
“1 a” => false
“2e10” => true
Note: It is intended for the problem statement to be ambiguous. You should gather all requirements up front before implementing one.

Update (2015-02-10):
The signature of the C++ function had been updated. If you still see your function signature accepts a const char * argument, please click the reload button to reset your code definition.

解法1： DFA

第一次遇到可以用DFA(finite automata)做的题，终于学到的理论知识也有可以用的地方了。
用dfa做的时候的点在于首先要换出图，然后识别出valid的state,最后判断一下是否落在state中就可以了。实现起来比较简单。
chart

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
    public boolean isNumber(String s) {
        if (s == null || s.length() == 0 || s.trim().length() == 0) {
            return false;
        }
        s = s.trim();
        int state = 1;
        boolean hasNum = false;
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (Character.isDigit(ch)) {
                hasNum = true;
                if (state <= 3) {
                    state = 3;
                } else if (state <= 5) {
                    state = 5;
                } else if (state <= 8) {
                    state = 8;
                }
            } else if (ch == '.') {
                if (state < 3) state = 4;
                else if (state == 3) state = 5;
                else return false;
            } else if (ch == 'e') {
                if (state == 3) state = 6;
                else if (state == 5) state = 6;
                else return false;
            } else if (ch == '+' || ch == '-') {
                if (state == 1) state = 2;
                else if (state == 6) state = 7;
                else return false;
            } else {
                return false;
            }
        }
        return state == 3 || state == 5 || state == 8;
    }
}

发表于 | 分类于

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.

解法1： DP

用一个array,dp[i]表示的是0 … i子串里lvp。首先如果要valid,那么最后一个字符一定是). 这就是说我们只需要在看到)的时候判断一下当前最长的子串。
那么可以得到如下的推算公式。
如果i字符是(，那么如果i-1是(,则代表有一个valid的子串，dp[i] = dp[i - 2] + 2
如果i字符是)，那么先要看i - 1位置的最长子串，然后看这个子串的前一个字符是否是(，如果是那么我们又凑满了一个valid的子串。
dp[i] = dp[i - 1] + dp[i - dp[i - 1] - 2] + 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int longestValidParentheses(String s) {
        int res = 0;
        int[] dp = new int[s.length()];
        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) == ')') {
                if (s.charAt(i - 1) == '(') {
                    dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
                } else if (i > dp[i - 1] && s.charAt(i - dp[i - 1] - 1) == '(') {
                    dp[i] = dp[i - 1] + (i - dp[i - 1] >= 2 ? dp[i - dp[i - 1] - 2]: 0) + 2;
                }
            }
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}

解法２: Stack

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
    public int longestValidParentheses(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        Stack<Integer> stack = new Stack<>();
        int start = -1;
        int res = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                stack.push(i);
            } else {
                if (!stack.isEmpty()) {
                    stack.pop();
                    if (stack.isEmpty()) {
                        res = Math.max(res, i - start);
                    } else {
                        res = Math.max(res, i - stack.peek());
                    }
                } else {
                    start = i;  // because if a string starts with ) it will never become valid
                }
            }
        }
        return res;
    }
}

发表于 | 分类于

You are given a string, s, and a list of words, words, that are all of the same length. Find all starting indices of substring(s) in s that is a concatenation of each word in words exactly once and without any intervening characters.

For example, given:
s: “barfoothefoobarman”
words: [“foo”, “bar”]

You should return the indices: [0,9].
(order does not matter).

解法1： HashMap ＋　一次遍历　

用HashMap记录每一个word出现的次数，然后对每一个起始点进行遍历。
复杂度应该是O(NL), N是字符串的长度，L是字符串数组的个数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    public static List<Integer> findSubstring(String S, String[] L) {
        List<Integer> res = new ArrayList<Integer>();
        if (S == null || L == null || L.length == 0) return res;
        int len = L[0].length(); // length of each word
        Map<String, Integer> map = new HashMap<String, Integer>(); // map for L
        for (String w : L) map.put(w, map.containsKey(w) ? map.get(w) + 1 : 1);
        for (int i = 0; i <= S.length() - len * L.length; i++) {
            Map<String, Integer> copy = new HashMap<String, Integer>(map);
            for (int j = 0; j < L.length; j++) { // checkc if match
                String str = S.substring(i + j*len, i + j*len + len); // next word
                if (copy.containsKey(str)) { // is in remaining words
                    int count = copy.get(str);
                    if (count == 1) copy.remove(str);
                    else copy.put(str, count - 1);
                    if (copy.isEmpty()) { // matches
                        res.add(i);
                        break;
                    }
                } else break; // not in L
            }
        }
        return res;
    }
}

发表于 | 分类于

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

You may not alter the values in the nodes, only nodes itself may be changed.

Only constant memory is allowed.

For example,
Given this linked list: 1->2->3->4->5

For k = 2, you should return: 2->1->4->3->5

For k = 3, you should return: 3->2->1->4->5

解法1： O(N)

考点是基本的linkedlist操作，每次找出一个要反转的subList的头的前一个node和他的尾巴node,反转了之后再把新subList接回原来的list就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null) return null;
        if (k <= 1) return head;
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode tail = dummy;
        while (tail != null && tail.next != null) {
            int count = 0;
            // first find the end of the sub list
            ListNode subHead = tail;
            while (tail != null && count < k) {
                ++count;
                tail = tail.next;
            }
            // tail point to the end of the subList
            if (tail == null) break;
            ListNode next = tail.next;
            tail.next = null;
            ListNode subRealHead = subHead.next;
            ListNode temp = reverse(subRealHead);
            subHead.next = temp;    // connect the new head to front
            subRealHead.next = next;    // connect the new tail to end
            tail = subRealHead; // set tail to be the last element in the current subList
        }
        return dummy.next;
    }
    private ListNode reverse(ListNode head) {
        ListNode prev = null;
        while (head != null) {
            ListNode next = head.next;
            head.next = prev;
            prev = head;
            head = next;
        }
        return prev;
    }
}

发表于 | 分类于

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

解法1： PriorityQueue, O(NlogM)

M是queue的长度，N是所有node的总数。
一个简单的PriorityQueue的应用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return null;
        }
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        Queue<ListNode> queue = new PriorityQueue<>((a,b) -> a.val - b.val);
        for (int i = 0; i < lists.length; i++) {
            if (lists[i] != null) {
                queue.offer(lists[i]);            
            }
        }
        while (!queue.isEmpty()) {
            ListNode next = queue.poll();
            tail.next = next;
            tail = tail.next;
            // add another node if exist
            if (next.next != null) {
                queue.offer(next.next);
            }
        }
        return dummy.next;
    }
}

发表于 | 分类于

Implement regular expression matching with support for ‘.’ and ‘*’.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
'.' Matches any single character.
'*' Matches zero or more of the preceding element.
The matching should cover the entire input string (not partial).
The function prototype should be:
bool isMatch(const char *s, const char *p)
Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true

解法1： DP O(MN)

这题一开始拿到没想到可以用DP。如果从基础的递归开始思考的话会比较容易一点往dp的方向上想。
而dp的状态方程也不太好想。
参考了YouTube上的这个视频,讲的还是比较清楚的。
首先，dp[i][j]表示的是前i个字符和前j个字符是否能match。
那么如果s[i] == p[j]，又或者当前的pattern是”.”, 则可以轻松得出dp[i][j] = dp[i - 1][j - 1]
如果是,那么就稍微麻烦一点。
这里可以考虑的是两种情况：
一个是不match前面的字符，这种情况下可以得到dp[i][j] = dp[i][j - 2]
另外一个是match一个或者多个前面的字符，但是这种情况需要满足s[i] = p[j - 1].
那么怎么表示match呢？可以的做法就是把当前s的位置的字符删除，变成s[i - 1]再和p[i]尝试match.
举一个例子：aa 和a*。　如果在match第二个a的时候，可以退化成比较a和a*。而这个结果已经有了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
    public boolean isMatch(String s, String p) {
        if (s == null && p == null) return true;
        if (s == null || p == null) return false;
        if (s.length() == 0 && p.length() == 0) return true;
        int m = s.length();
        int n = p.length();
        boolean[][] dp = new boolean[m + 1][n + 1];
        dp[0][0] = true;
        for (int i = 2; i <= n; i++) {
            if (p.charAt(i - 1) == '*') {
                dp[0][i] = dp[0][i - 2];
            }
        }
        for (int i = 1; i <=m ; i++) {
            for (int j = 1; j <= n; j++) {
                if (p.charAt(j - 1) == '.' || (p.charAt(j - 1) == s.charAt(i - 1))) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else if (p.charAt(j - 1) == '*') {
                    dp[i][j] = dp[i][j - 2];    // zero match of the previous value
                    if (p.charAt(j - 2) == '.' || p.charAt(j - 2) == s.charAt(i - 1)) {
                        dp[i][j] |= dp[i - 1][j];
                    }
                } else {
                    dp[i][j] = false;
                }
            }
        }
        return dp[m][n];
    }
}

发表于 | 分类于

A character in UTF8 can be from 1 to 4 bytes long, subjected to the following rules:

For 1-byte character, the first bit is a 0, followed by its unicode code.
For n-bytes character, the first n-bits are all one’s, the n+1 bit is 0, followed by n-1 bytes with most significant 2 bits being 10.
This is how the UTF-8 encoding would work:

1
2
3
4
5
6
7
Char. number range  |        UTF-8 octet sequence
   (hexadecimal)    |              (binary)
--------------------+---------------------------------------------
0000 0000-0000 007F | 0xxxxxxx
0000 0080-0000 07FF | 110xxxxx 10xxxxxx
0000 0800-0000 FFFF | 1110xxxx 10xxxxxx 10xxxxxx
0001 0000-0010 FFFF | 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx

Given an array of integers representing the data, return whether it is a valid utf-8 encoding.

Note:
The input is an array of integers. Only the least significant 8 bits of each integer is used to store the data. This means each integer represents only 1 byte of data.

Example 1:

1
2
3
4
data = [197, 130, 1], which represents the octet sequence: 11000101 10000010 00000001.
Return true.
It is a valid utf-8 encoding for a 2-bytes character followed by a 1-byte character.

Example 2:

1
2
3
4
5
6
data = [235, 140, 4], which represented the octet sequence: 11101011 10001100 00000100.
Return false.
The first 3 bits are all one's and the 4th bit is 0 means it is a 3-bytes character.
The next byte is a continuation byte which starts with 10 and that's correct.
But the second continuation byte does not start with 10, so it is invalid.

解法1：

按照规则来。用一个变量存储当前还需要几个连续的以10开头的byte。
要注意的是在设置mask的时候，需要用0B11100000去判断最初的两个数字是否是11

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Solution {
	public boolean validUtf8(int[] data) {
		int varCharLeft = 0;
		for (int b: data) {
			if (varCharLeft == 0) {
                // 要差一位来判断到底有几个1在数字里面，不然不知道到底是有几位。
                // 判断到3的原因是unicode最多是4个byte
				if ((b & 0b10000000) == 0)  varCharLeft = 0;
				else if ((b & 0b11100000) == 0b11000000)  varCharLeft = 1;
				else if ((b & 0b11110000) == 0b11100000)  varCharLeft = 2;
				else if ((b & 0b11111000) == 0b11110000)  varCharLeft = 3;
				else return false;
			} else {
				if ((b & 0b11000000) != 0b10000000)  return false;
				varCharLeft--;
			}
		}
		return varCharLeft==0;
	}
}

发表于 | 分类于

Given a string s and a string t, check if s is subsequence of t.

You may assume that there is only lower case English letters in both s and t. t is potentially a very long (length ~= 500,000) string, and s is a short string (<=100).

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, “ace” is a subsequence of “abcde” while “aec” is not).

Example 1:
s = “abc”, t = “ahbgdc”

Return true.

Example 2:
s = “axc”, t = “ahbgdc”

Return false.

Follow up:
If there are lots of incoming S, say S1, S2, … , Sk where k >= 1B, and you want to check one by one to see if T has its subsequence. In this scenario, how would you change your code?

解法1： Two pointers O(M + N)

一个指针扫描t，一个指针扫描s。当两个指向的字符相同的时候就把s的指针前进，如果s到了t的末尾，那么就返回true。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public boolean isSubsequence(String s, String t) {
        if (s == null || s.length() == 0) {
            return true;
        }
        if (t == null || t.length() == 0) {
            return false;
        }
        int j = 0;
        for (int i = 0; i < t.length(); i++){
            if (t.charAt(i) == s.charAt(j)) {
                j++;
                if (j == s.length()) {
                    return true;
                }
            }
        }
        return false;
    }
}

Follow up

如果是要不停的处理不同的s的话，一般情况下可以对t进行一些预处理。
首先用O(N)的办法得出每一个字符在t中出现的位置，用一个Map>处理。
然后遍历每一个s中的字符，同时维护一个prev记录上一次在s中match到的位置。
如果一个字符不存在map中，直接返回false
如果一个字符在map中，取得该character在t中的位置的list。
然后可以用一个binarysearch取得最小的比prev大的数字。
如果这个数字不存在，那么就返回false。
如果存在则match这个，同时把prev设为该index的下一个。
复杂度可以降低到O(MlogN)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    public boolean isSubsequence(String s, String t) {
        if ( s == null || s.length() == 0) {
            return true;
        }
        // preprocess, O(N)
        Map<Character, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < t.length(); i++) {
            char ch = t.charAt(i);
            if (!map.containsKey(ch)) {
                map.put(ch, new ArrayList<>());
            }
            map.get(ch).add(i);
        }
        int prev = 0;
        for (char ch : s.toCharArray()) {
            if (!map.containsKey(ch)) {
                return false;
            }
            List<Integer> pos = map.get(ch);
            int index = Collections.binarySearch(pos, prev);
            if (index < 0) index = (-1)*(index + 1);
            if (index == pos.size()) return false;
            prev = pos.get(index) + 1;  // index stores the insertion position, so to get the real position in t you have to get from the list
        }
        return true;
    }
}