發表於   |   分類於   |   0 comments

Given a set of words (without duplicates), find all word squares you can build from them.

A sequence of words forms a valid word square if the kth row and column read the exact same string, where 0 ≤ k < max(numRows, numColumns).

For example, the word sequence [“ball”,”area”,”lead”,”lady”] forms a word square because each word reads the same both horizontally and vertically.

1
2
3
4
b a l l
a r e a
l e a d
l a d y

Note:
There are at least 1 and at most 1000 words.
All words will have the exact same length.
Word length is at least 1 and at most 5.
Each word contains only lowercase English alphabet a-z.

Example 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Input:
["area","lead","wall","lady","ball"]
Output:
[
  [ "wall",
    "area",
    "lead",
    "lady"
  ],
  [ "ball",
    "area",
    "lead",
    "lady"
  ]
]
Explanation:
The output consists of two word squares. The order of output does not matter (just the order of words in each word square matters).

Example 2:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Input:
["abat","baba","atan","atal"]
Output:
[
  [ "baba",
    "abat",
    "baba",
    "atan"
  ],
  [ "baba",
    "abat",
    "baba",
    "atal"
  ]
]
Explanation:
The output consists of two word squares. The order of output does not matter (just the order of words in each word square matters).

先构建一个字典树再用回溯法搜索。Trie我之前还没有写过，只知道概念，其结构是有一个26个nullptr的children指针的vector，有子树时那条边的字母对应的children元素从nullptr改为子树地址。另外还有index数组保存该节点子树中所有字符串在原words中对应的index。

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
class TrieNode {
public:
    vector<int> index;
    vector<TrieNode*> children;
public:
    TrieNode():children(26, nullptr) { }
};
class Solution {
public:
    vector<vector<string>> res;
    TrieNode* buildTrie(vector<string>& words) {
        TrieNode* root = new TrieNode();
        TrieNode* node;
        for (int j = 0; j < words.size(); j++) {
            node = root;
            string word = words[j];
            for (int i = 0; i < word.length(); i++) {
                if (!node -> children[word[i]-'a']) {
                    TrieNode* new_node = new TrieNode();
                    node -> children[word[i]-'a'] = new_node;
                }
                node = node -> children[word[i]-'a'];
                node -> index.push_back(j);
            }
        }
        return root;
    }
    
    void backtracking(TrieNode* r, int level, vector<string> &square, vector<string> &words) {
        if (level >= words[0].length()) {
            res.push_back(square);
            return;
        }
        TrieNode* t = r;
        for (int i = 0; i < level; i++) {
            if (!t->children[square[i][level]-'a'])  return;
            t = t->children[square[i][level]-'a'];
        }
        for (auto in:t->index) {
            square[level] = words[in];
            backtracking(r, level+1, square, words);
            square[level] = "";
        }
        return;
    }
    vector<vector<string>> wordSquares(vector<string>& words) {
        vector<string> square{words.size(), ""};
        TrieNode* root = buildTrie(words);
        for (auto word: words) {
            square[0] = word;
            backtracking(root, 1, square, words);
        }
        return res;
    }
};

發表於   |   分類於   |   0 comments

A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down).

Find all strobogrammatic numbers that are of length = n.

For example,
Given n = 2, return [“11”,”69”,”88”,”96”].

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
class Solution {
    vector<vector<string>> res;
public:
    vector<string> findStrobogrammatic(int n) {
        res.push_back({""});
        res.push_back({"0", "1", "8"});
        for (int i = 2; i <= n; i++) {
            res.push_back({});
        }
        recursion(n, true);
        return res[n];
    }
    vector<string> recursion(int n, bool outer) {
        if (res[n].size())    return res[n];
        string s = "";
        vector<pair<string, string>> p = {make_pair("0", "0"), make_pair("1","1"), make_pair("6", "9"), make_pair("8", "8"), make_pair("9", "6")};
        for (int i = outer; i < 5; i++) {
            for (auto j:recursion(n-2, false)) {
                s = p[i].first + j + p[i].second;
                res[n].push_back(s);
            }
        }
        return res[n];
    }
};

發表於   |   分類於   |   0 comments

There is a fence with n posts, each post can be painted with one of the k colors.

You have to paint all the posts such that no more than two adjacent fence posts have the same color.

Return the total number of ways you can paint the fence.

Note:
n and k are non-negative integers.

一开始理解错“no more than two adjacent fence posts”了，以为是说总共最多只能有两个相邻的，题意应该是相邻的情况里只能是两个相邻，但是XXOO这种是允许的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    
public:
    int numWays(int n, int k) {
        if (!n || !k) return 0;
        vector<int> same(n, 0);
        vector<int> dif(n, 0);
        same[0] = 0;
        dif[0] = k;
        for (int i = 1; i < n; i++) {
            same[i] = dif[i-1];
            dif[i] = (same[i-1]+dif[i-1])*(k-1);
        }
        return same[n-1]+dif[n-1];
    }
};

發表於   |   分類於   |   0 comments

Given a stream of integers and a window size, calculate the moving average of all integers in the sliding window.

For example,
MovingAverage m = new MovingAverage(3);
m.next(1) = 1
m.next(10) = (1 + 10) / 2
m.next(3) = (1 + 10 + 3) / 3
m.next(5) = (10 + 3 + 5) / 3

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
class MovingAverage {
    int win_size;
    deque<int> q;
    double sum = 0;
public:
    /** Initialize your data structure here. */
    MovingAverage(int size) {
        win_size = size;
    }
    
    double next(int val) {
        if (q.size() >= win_size) {
            sum -= q.front();
            q.pop_front();
        }
        q.push_back(val);
        sum += val;
        return sum/double(q.size());
    }
};
/**
 * Your MovingAverage object will be instantiated and called as such:
 * MovingAverage obj = new MovingAverage(size);
 * double param_1 = obj.next(val);
 */

發表於   |   分類於   |   0 comments

Given two 1d vectors, implement an iterator to return their elements alternately.

For example, given two 1d vectors:

1
2
v1 = [1, 2]
v2 = [3, 4, 5, 6]

By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1, 3, 2, 4, 5, 6].

Follow up: What if you are given k 1d vectors? How well can your code be extended to such cases?

Clarification for the follow up question - Update (2015-09-18):
The “Zigzag” order is not clearly defined and is ambiguous for k > 2 cases. If “Zigzag” does not look right to you, replace “Zigzag” with “Cyclic”. For example, given the following input:

1
2
3
[1,2,3]
[4,5,6,7]
[8,9]

It should return [1,4,8,2,5,9,3,6,7].

用cur代表当前位置，cur % k代表要读哪个vector，cur/k是那个vector要读取的index。

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
class ZigzagIterator {
    int m, n;
    int cur = -1;
    vector<int> v1, v2;
public:
    ZigzagIterator(vector<int>& v1, vector<int>& v2) {
        m = v1.size();
        n = v2.size();
        this -> v1 = v1;
        this -> v2 = v2;
    }
    int next() {
        cur++;
        if (cur / 2 < min(m, n)) {
            if (cur % 2) return v2[cur/2];
            else return v1[cur/2];
        }
        else if (m < n) {
            return v2[cur-m];
        }
        else return v1[cur-n];
    }
    bool hasNext() {
        return cur+1 < m+n;
    }
};
/**
 * Your ZigzagIterator object will be instantiated and called as such:
 * ZigzagIterator i(v1, v2);
 * while (i.hasNext()) cout << i.next();
 */

發表於   |   分類於   |   0 comments

Given a 2D grid, each cell is either a wall ‘W’, an enemy ‘E’ or empty ‘0’ (the number zero), return the maximum enemies you can kill using one bomb.
The bomb kills all the enemies in the same row and column from the planted point until it hits the wall since the wall is too strong to be destroyed.
Note that you can only put the bomb at an empty cell.

Example:

1
2
3
4
5
6
7
For the given grid
0 E 0 0
E 0 W E
0 E 0 0
return 3. (Placing a bomb at (1,1) kills 3 enemies)

这道题是……泡泡堂？

可能是受grid illumination的影响，最开始的想法是，遍历一遍保存下来每行每列的enemy count，碰到墙就把这个vector切割（pushback新元素0）；在每个0的位置放炸弹的效果就是把对应的行/列enemy count数加起来就好。但因为要找到被墙分割以后在count数组中的位置，时间复杂度较高。

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
class Solution {
    vector<vector<int>> row_walls, col_walls;
    vector<vector<int>> row_cnt, col_cnt;
    int m, n;
public:
    int maxKilledEnemies(vector<vector<char>>& grid) {
        m = grid.size();
        if (!m) return 0;
        n = grid[0].size();
        vector<vector<int>> cnt(m, vector<int>(n,0));
        for (int i = 0; i < m; i++) {
            row_cnt.push_back(vector<int>{0});
            row_walls.push_back(vector<int>{});
        }
        for (int j = 0; j < n; j++) {
            col_cnt.push_back(vector<int>{0});
            col_walls.push_back(vector<int>{});
        }
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 'E') {
                    row_cnt[i][row_cnt[i].size()-1]++;
                    col_cnt[j][col_cnt[j].size()-1]++;
                }
                if (grid[i][j] == 'W') {
                    row_cnt[i].push_back(0);
                    row_walls[i].push_back(j);
                    col_cnt[j].push_back(0);
                    col_walls[j].push_back(i);
                }
            }
        }
        int max = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] != '0') continue;
                int w = 0;
                while (w < row_walls[i].size() && row_walls[i][w] < j) {
                    w++;
                }
                cnt[i][j] += row_cnt[i][w];
                
                w = 0;
                while (w < col_walls[j].size() && col_walls[j][w] < i) {
                    w++;
                }
                cnt[i][j] += col_cnt[j][w];
                // cout << i << " " << j << " " << cnt[i][j] << endl;
                if (cnt[i][j] > max) max = cnt[i][j];
            }
        }
        return max;
        
    }
};

用DP来做的话，从前往后遍历一遍，从后往前遍历一遍，分别用之前算的结果算当前的值，时间复杂度O(mn)。

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
class Solution {
public:
    int maxKilledEnemies(vector<vector<char>>& grid) {
        int m = grid.size();
        if (!m) return 0;
        int n = grid[0].size();
        vector<vector<int>> rcnt1(m, vector<int>(n,0)), rcnt2(m, vector<int>(n,0));
        vector<vector<int>> ccnt1(m, vector<int>(n,0)), ccnt2(m, vector<int>(n,0));
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 'W')  {rcnt1[i][j] = 0; ccnt1[i][j] = 0;}
                else {
                    rcnt1[i][j] += (grid[i][j]=='E');
                    ccnt1[i][j] += (grid[i][j]=='E');
                    if (i > 0) rcnt1[i][j] += rcnt1[i-1][j];
                    if (j > 0) ccnt1[i][j] += ccnt1[i][j-1];
                }
            }
        }
        
        for (int i = m-1; i >= 0; i--) {
            for (int j = n-1; j >= 0; j--) {
                if (grid[i][j] == 'W')  {rcnt2[i][j] = 0; ccnt2[i][j] = 0;}
                else {
                    rcnt2[i][j] += (grid[i][j]=='E');
                    ccnt2[i][j] += (grid[i][j]=='E');
                    if (i < m-1) rcnt2[i][j] += rcnt2[i+1][j];
                    if (j < n-1) ccnt2[i][j] += ccnt2[i][j+1];
                }
            }
        }
        
        int max = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] != '0') continue;
                int cnt = rcnt1[i][j] + rcnt2[i][j] + ccnt1[i][j] + ccnt2[i][j];
                if (cnt > max) max = cnt;
            }
        }
        return max;
        
    }
};

减少空间的常数项，可以只用一个cnt矩阵，前后的enemy信息用常数表示。

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:
    int maxKilledEnemies(vector<vector<char>>& grid) {
        int m = grid.size();
        if (!m) return 0;
        int n = grid[0].size();
        vector<vector<int>> cnt1(m, vector<int>(n,0));
        for (int i = 0; i < m; i++) {
            int f = 0, b = 0;
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 'W')  f = 0; 
                if (grid[i][n-j-1] == 'W') b = 0;
                f += grid[i][j]=='E';
                b += grid[i][n-j-1]=='E';
                if (grid[i][j] == '0') cnt1[i][j] += f;
                if (grid[i][n-j-1] == '0') cnt1[i][n-j-1] += b;
            }
        }
        
        for (int j = 0; j < n; j++) {
            int f = 0, b = 0;
            for (int i = 0; i < m; i++) {
                if (grid[i][j] == 'W')  f = 0; 
                if (grid[m-i-1][j] == 'W') b = 0;
                f += grid[i][j]=='E';
                b += grid[m-i-1][j]=='E';
                if (grid[i][j] == '0') cnt1[i][j] += f;
                if (grid[m-i-1][j] == '0') cnt1[m-i-1][j] += b;
            }
        }
        
        int max = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] != '0') continue;
                if (cnt1[i][j] > max) max = cnt1[i][j];
            }
        }
        return max;
        
    }
};

發表於   |   分類於   |   0 comments

Given a pattern and a string str, find if str follows the same pattern.

Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty substring in str.

Examples:

1
2
3
pattern = "abab", str = "redblueredblue" should return true.
pattern = "aaaa", str = "asdasdasdasd" should return true.
pattern = "aabb", str = "xyzabcxzyabc" should return false.

Notes:
You may assume both pattern and str contains only lowercase letters.

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 {
    unordered_map<char, string> mp;
    set<string> visited;
public:
    bool wordPatternMatch(string pattern, string str) {
        if (!pattern.length() && !str.length()) return true;
        if (!pattern.length() || !str.length()) return false;
        char p = pattern[0];
        if (mp.find(p) != mp.end()) {
            if (str.substr(0, mp[p].length()) != mp[p]) return false;
            return wordPatternMatch(pattern.substr(1), 
            	str.substr(mp[p].length()));
        }
        else {
            for (int i = 1; i <= str.length(); i++) {
                string s = str.substr(0, i);
                // cout << s;
                if (visited.find(s)!=visited.end()) continue;
                visited.insert(s);
                mp[p] = s;
                if (wordPatternMatch(pattern.substr(1), 
                	str.substr(mp[p].length())))  
                		return true;
                visited.erase(s);
                mp.erase(p);
            }
            return false;
        }
    }
};

發表於   |   分類於   |   0 comments

Design a hit counter which counts the number of hits received in the past 5 minutes.

Each function accepts a timestamp parameter (in seconds granularity) and you may assume that calls are being made to the system in chronological order (ie, the timestamp is monotonically increasing). You may assume that the earliest timestamp starts at 1.

It is possible that several hits arrive roughly at the same time.

Example:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
HitCounter counter = new HitCounter();
// hit at timestamp 1.
counter.hit(1);
// hit at timestamp 2.
counter.hit(2);
// hit at timestamp 3.
counter.hit(3);
// get hits at timestamp 4, should return 3.
counter.getHits(4);
// hit at timestamp 300.
counter.hit(300);
// get hits at timestamp 300, should return 4.
counter.getHits(300);
// get hits at timestamp 301, should return 3.
counter.getHits(301);

code:

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 HitCounter {
    queue<int> q;
public:
    /** Initialize your data structure here. */
    HitCounter() {
        
    }
    
    /** Record a hit.
        @param timestamp - The current timestamp (in seconds granularity). */
    void hit(int timestamp) {
        q.push(timestamp);
    }
    
    /** Return the number of hits in the past 5 minutes.
        @param timestamp - The current timestamp (in seconds granularity). */
    int getHits(int timestamp) {
        while (!q.empty() && timestamp - q.front() >= 300) q.pop();
        return q.size();
    }
};
/**
 * Your HitCounter object will be instantiated and called as such:
 * HitCounter obj = new HitCounter();
 * obj.hit(timestamp);
 * int param_2 = obj.getHits(timestamp);
 */
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 HitCounter {
    queue<int> q;
public:
    /** Initialize your data structure here. */
    HitCounter() {
        
    }
    
    /** Record a hit.
        @param timestamp - The current timestamp (in seconds granularity). */
    void hit(int timestamp) {
        q.push(timestamp);
    }
    
    /** Return the number of hits in the past 5 minutes.
        @param timestamp - The current timestamp (in seconds granularity). */
    int getHits(int timestamp) {
        while (!q.empty() && timestamp - q.front() >= 300) q.pop();
        return q.size();
    }
};
/**
 * Your HitCounter object will be instantiated and called as such:
 * HitCounter obj = new HitCounter();
 * obj.hit(timestamp);
 * int param_2 = obj.getHits(timestamp);
 */
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 HitCounter {
    deque<int> q;
    unordered_map<int,int> qm;
    int count;
public:
    /** Initialize your data structure here. */
    HitCounter() {
        this->count = 0; 
    }
    
    /** Record a hit.
        @param timestamp - The current timestamp (in seconds granularity). */
    void hit(int timestamp) {
        count++;
        if(qm.find(timestamp) == qm.end())
            q.push_back(timestamp);
        qm[timestamp]++;
    }
    
    /** Return the number of hits in the past 5 minutes.
        @param timestamp - The current timestamp (in seconds granularity). */
    int getHits(int timestamp) {
        while(!q.empty() && timestamp-q.front()>=300){
            this->count -= qm[q.front()];
            qm.erase(qm.find(q.front()));
            q.pop_front();
        } 
        return this->count;
    }
};

發表於   |   分類於   |   0 comments

Given a rows x cols screen and a sentence represented by a list of words, find how many times the given sentence can be fitted on the screen.

Note:

A word cannot be split into two lines.
The order of words in the sentence must remain unchanged.
Two consecutive words in a line must be separated by a single space.
Total words in the sentence won’t exceed 100.
Length of each word won’t exceed 10.
1 ≤ rows, cols ≤ 20,000.

Example 1:

Input:
rows = 2, cols = 8, sentence = [“hello”, “world”]

Output:
1

Explanation:
hello—
world—

The character ‘-‘ signifies an empty space on the screen.
Example 2:

Input:
rows = 3, cols = 6, sentence = [“a”, “bcd”, “e”]

Output:
2

Explanation:
a-bcd-
e-a—
bcd-e-

The character ‘-‘ signifies an empty space on the screen.
Example 3:

Input:
rows = 4, cols = 5, sentence = [“I”, “had”, “apple”, “pie”]

Output:
1

Explanation:
I-had
apple
pie-I
had–

The character ‘-‘ signifies an empty space on the screen.

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:
    int wordsTyping(vector<string>& sentence, int rows, int cols) {
        int cur_len = 0;
        int num_words = sentence.size();
        for (auto s: sentence) {
            if (s.length() > cols)
                return 0;
        }
        vector<int> vv(num_words, 0);
        for (int j = 0; j < num_words; j++) {
            cur_len = 0;
            for (int i = j; sentence[i].length()+cur_len<=cols; i=(i+1)%num_words) {
                cur_len+=sentence[i].length()+1;
                vv[j]++;
            }
        }
        int k = 0;
        int m = 0;
        for (int j = 0; j < rows; j++) {
            m += vv[k];
            k = (k+vv[k]) % num_words;
        }
        int res = m/num_words;
        return res;
    }
};
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:
    int wordsTyping(vector<string>& sentence, int rows, int cols) {
        int num_words = sentence.size();
        for (auto s: sentence) {
            if (s.length() > cols)
                return 0;
        }
        vector<int> vv(num_words, -1);
        
        int k = 0;
        int m = 0;
        for (int j = 0; j < rows; j++) {
            if (vv[k] == -1) {
                int cur_len = 0;
                vv[k]++;
                for (int i = k; sentence[i].length()+cur_len<=cols; i=(i+1)%num_words) {
                    cur_len+=sentence[i].length()+1;
                    vv[k]++;
                }
            }
            m += vv[k];
            k = (k+vv[k]) % num_words;
        }
        int res = m/num_words;
        return res;
    }
};

Dec 8 update:

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:
    int wordsTyping(vector<string>& sentence, int rows, int cols) {
        int len = sentence.size();
        if (!len) return 0;
        vector<int> mp(len, 0);
        int cur = 0;
        int total = 0;
        for (int row = 0; row < rows; row++) {
            int cur_len = 0;
            int slen;
            if (!mp[cur]) {
                for (int j = cur; cur_len + (slen=sentence[j].length()) <= cols; j=j+1-((j+1)>=len?len:0)) {
                    cur_len += slen+1;
                    mp[cur]++;
                }
            }
            total += mp[cur];
            cur = (mp[cur]+cur)%len;
            // cout << cur << " " << mp[cur] << " " <<total<< endl;
        }
        return total/len;
    }
};

發表於   |   分類於   |   0 comments

Given a string, find the length of the longest substring T that contains at most 2 distinct characters.

For example, Given s = “eceba”,

T is “ece” which its length is 3.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int lengthOfLongestSubstringTwoDistinct(string s) {
        int hash[128] = {0};
        int l = s.length();
        int max_len=0, cur_nchar=0;
        for (int i=0, j=0; i<l; i++) {
            if (!hash[s[i]-'A']++) cur_nchar++;
            if (cur_nchar <= 2) max_len = max(max_len, i-j+1);
            while (cur_nchar > 2) {
                if(!--hash[s[j++]-'A']) cur_nchar--;
            }
        }
        return max_len;
    }
};