發表於   |   分類於

Maximum Product of Word Lengths

Given a string array words, find the maximum value of length(word[i]) * length(word[j]) where the two words do not share common letters. You may assume that each word will contain only lower case letters. If no such two words exist, return 0.

Example 1:

1
2
Given ["abcw", "baz", "foo", "bar", "xtfn", "abcdef"]
Return 16

The two words can be “abcw”, “xtfn”.

Example 2:

1
2
Given ["a", "ab", "abc", "d", "cd", "bcd", "abcd"]
Return 4

The two words can be “ab”, “cd”.

Example 3:

1
2
Given ["a", "aa", "aaa", "aaaa"]
Return 0

No such pair of words.

使用一个int值来表示字符串中字符的出项情况。

注意使用 与操作（|=） 来生成int值。

当两个int值的 和操作（&）结果不为 0 时，说明它们的二进制表示至少有一个相同的位为 1 。这也就代表着对应的字符串中有相同的字符。

想了半天没有好方法，结果还是暴力求解最大值……

AC代码：

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
class Solution {
public:

    int ToInt(string& s)
    {
        int ans = 0;
        for (int i = 0; i < s.length(); ++i)
        {
            int n = s[i] - 'a';
            int k = 1 << n;
            ans |= k;
        }
        return ans;
    }

    int maxProduct(vector<string>& words) {

        vector<int> bitMap(words.size(),0);

        // build bitmap
        for (int i = 0; i < words.size(); ++i)
        {
            bitMap[i] = ToInt(words[i]);
        }

        int R = 0;

        for (int i = 0; i < words.size(); ++i)
        {

            for (int j = i; j < words.size(); ++j)
            {
                if (bitMap[i] & bitMap[j]) continue;
                int r = words[j].length() * words[i].length();
                if (r > R) R = r;
            }
        }

        return R;
    }
};

發表於   |   分類於

Gray Code

The gray code is a binary numeral system where two successive values differ in only one bit.

Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.

For example, given n = 2, return [0,1,3,2]. Its gray code sequence is:

1
2
3
4
00 - 0
01 - 1
11 - 3
10 - 2

Note:

For a given n, a gray code sequence is not uniquely defined.

For example, [0,2,3,1] is also a valid gray code sequence according to the above definition.

For now, the judge is able to judge based on one instance of gray code sequence. Sorry about that.

DFS。

注意对数组遍历的时候应该逆序。

AC代码：

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:

	void solve(int n, vector<int>& r)
	{
		if (0 == n)
		{
			r.push_back(0);
			return;
		}
		else if (1 == n)
		{
			r.push_back(0);
			r.push_back(1);
			return;
		}
		solve(n - 1, r);
		int lv = 1 << (n - 1);
		int size = r.size();
		for (int i = size - 1; i >= 0; --i)
		{
			r.push_back(r[i] + lv);
		}
	}

	vector<int> grayCode(int n) {
		vector<int> result;
		if (n < 0) return result;
		solve(n, result);
		return result;
	}
};

發表於   |   分類於

Courses Schedule

There are a total of n courses you have to take, labeled from 0 to n - 1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses.

There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.

For example:

1
2, [[1,0]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1]

1
4, [[1,0],[2,0],[3,1],[3,2]]

There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. So one correct course order is [0,1,2,3]. Another correct ordering is[0,2,1,3].

拓扑排序。流程和 Courses Schedule一样。但有两个需要注意的地方：

  • pair是边，如果没有边的话，那么所有的节点都是单独的，因此应当按照编号输出所有节点；
  • 如果没有可行的选课方案，那么最后的最后的选课的队列长度一定不等于课程数目，从而能可以判定无解，清空选课队列并输出。
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
class Solution {
public:
	vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
		vector<int> order;
		if (numCourses == 0) return order;
		int reqs = prerequisites.size();
		if (reqs == 0)
		{
		    for (int i = 0; i < numCourses; ++i)
		    {
		        order.push_back(i);
		    }
		    return order;
		}
		vector<int> inDegrees(numCourses, 0);
		vector<vector<int>> graphic(numCourses, vector<int>());
		for (auto p : prerequisites)
		{
			graphic[p.second].push_back(p.first);
			inDegrees[p.first]++;
		}
		queue<int> q;
		for (int i = 0; i < numCourses; ++i)
		{
			if (inDegrees[i] == 0)
			{
				q.push(i);
				order.push_back(i);
			}
		}

		while (!q.empty())
		{
			int f = q.front();
			q.pop();
			for (auto i = 0; i < graphic[f].size(); ++i)
			{
				inDegrees[graphic[f][i]]--;
				if (inDegrees[graphic[f][i]] == 0)
				{
					q.push(graphic[f][i]);
					order.push_back(graphic[f][i]);
				}
			}
		}
		if (order.size() != numCourses) order.clear();
		return order;
	}
};

發表於   |   分類於

Number od Island

Given a 2d grid map of ‘1’s (land) and ‘0’s (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:

1
2
3
4
11110
11010
11000
00000

Answer: 1

Example 2:

1
2
3
4
11000
11000
00100
00011

Answer: 3

DFS。

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
class Solution {
public:

    vector<vector<int>> vis;
    int rows;
    int cols;
    int result;
    int* rdir;
    int* cdir;
    void DFS(vector<vector<char>>& grid, int r, int c)
    {
        if (vis[r][c]) return;
        if (grid[r][c] == '1')
        {
            vis[r][c] = true;
            for(int k = 0; k < 4; ++k)
            {
                int i = r + rdir[k];
                int j = c + cdir[k];
                if(i >=0 && i < rows && j >= 0 && j < cols && vis[i][j] == 0)
                    DFS(grid,i,j);
            }
        }
    }

    int numIslands(vector<vector<char>>& grid) {
        result = 0;
        rows = grid.size();
        if (rows == 0) return 0;
        cols = grid[0].size();
        if (cols == 0) return 0;
        vis = vector<vector<int>>(rows,vector<int>(cols,0));
        int rdirs[] = {0,0,1,-1};
        int cdirs[] = {1,-1,0,0};
        rdir = rdirs;
        cdir = cdirs;

        for (int i = 0; i < rows; ++i)
        {
            for (int j = 0; j < cols; ++j)
            {
                if (vis[i][j] == 0 && grid[i][j] == '1')
                {
                    ++result;
                    DFS(grid,i,j);
                }
            }
        }
        return result;
    }
};

發表於   |   分類於

Path Sum II

Given a binary tree and a sum, find all root-to-leaf paths where each path’s sum equals the given sum.

For example:

Given the below binary tree and sum = 22,

1
2
3
4
5
6
7
      5
     / \
    4   8
   /   / \
  11  13  4
 /  \    / \
7    2  5   1

return

1
2
3
4
[
   [5,4,11,2],
   [5,8,4,5]
]

DFS+回溯。

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:

    vector<int> vi;
    vector<vector<int>> vvi;

    void DFS(TreeNode* root, int sum)
    {
        if (root == NULL) return;
        if (root->left == NULL && root->right == NULL)
        {
            if (sum == root->val)
            {
                vi.push_back(root->val);
                vvi.push_back(vi);
                vi.pop_back();
            }
            return;
        }
        vi.push_back(root->val);
        sum -= root->val;
        DFS(root->left,sum);
        DFS(root->right,sum);
        vi.pop_back();
    }

    vector<vector<int>> pathSum(TreeNode* root, int sum) {
        DFS(root,sum);
        return vvi;
    }
};

發表於   |   分類於

Word Search

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

For example,

Given board =

1
2
3
4
5
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

word = “ABCCED”, -> returns true,

word = “SEE”, -> returns true,

word = “ABCB”, -> returns false.

回溯。

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
58
59
class Solution {
public:

	typedef vector<int> vi;
	typedef vector<vi> vvi;

	vvi vis;
	int index;
	int* rdir;
	int* cdir;
	int rows;
	int cols;
	bool result;

	void solve(vector<vector<char>>& board, int r, int c, string& word)
	{
		vis[r][c] = true;
		if (word[index] == board[r][c])
		{
			if (result) return;
			if (index == word.length() - 1) result = true;
			for (int k = 0; k < 4; ++k)
			{
				int i = r - rdir[k];
				int j = c - cdir[k];
				if (i >= 0 && i < rows && j >= 0 && j < cols && vis[i][j] == 0)
				{
					++index;
					solve(board, i, j, word);
					--index;
				}
			}
		}
		vis[r][c] = false;
	}

	bool exist(vector<vector<char>>& board, string word) {
		rows = board.size();
		if (rows == 0) return false;
		cols = board[0].size();
		if (cols == 0) return false;
		vis = vvi(rows, vi(cols, 0));
		index = 0;
		result = false;
		int rdirs[] = { 0,0,1,-1 };
		int cdirs[] = { 1,-1,0,0 };
		rdir = rdirs;
		cdir = cdirs;
		for (int i = 0; i < rows; ++i)
		{
			for (int j = 0; j < cols; ++j)
			{
				solve(board, i, j, word);
				if (result) return true;
			}
		}
		return false;
	}
};

發表於   |   分類於

Add and Search Word - Data structure design

Design a data structure that supports the following two operations:

1
2
void addWord(word)
bool search(word)

search(word) can search a literal word or a regular expression string containing only letters a-z or .. A . means it can represent any one letter.

For example:

1
2
3
4
5
6
7
addWord("bad")
addWord("dad")
addWord("mad")
search("pad") -> false
search("bad") -> true
search(".ad") -> true
search("b..") -> 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
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
58
59
60
61
62
class WordDictionary {
public:

	map<string, int> datas;
	// Adds a word into the data structure.
	void addWord(string word) {
		auto it = datas.find(word);
		if (it == datas.end())
		{
			pair<string, int> p(word, 1);
			datas.insert(p);
		}
		else
		{
			it->second += 1;
		}
	}

	// Returns if the word is in the data structure. A word could
	// contain the dot character '.' to represent any one letter.
	bool search(string word) {
		bool r = false;
		string st;
		solve(r, st, word, 0);
		return r;
	}

	void solve(bool& r, string& st, string& word, int index)
	{
		int pos = index;
		for (; pos < word.length(); ++pos)
		{
			if (word[pos] == '.')
			{
				break;
			}
			st.push_back(word[pos]);
		}

		if (st.length() == word.length())
		{
			if (r == false)
			{
				r = (datas.find(st) != datas.end());
			}
			return;
		}

		for (int i = 'a'; i <= 'z'; ++i)
		{
			st.push_back((char)i);
			solve(r, st, word, pos + 1);
			if (r) return;
			int l = st.length() - pos;
			while (l > 0)
			{
				st.pop_back();
				--l;
			}
		}
	}
};

然后是AC了的剪枝版本。剪枝过程使用了字典树，然后就是Check函数的三种返回值需要注意；字典树节点中的BOOL成员表明该字符是否属于一个字符串的终结字符。

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
class WordDictionary {
public:

	struct Node
	{
		char c;
		bool bstr;
		Node* children[26];
		Node()
		{
			for (int i = 0; i < 26; ++i)
				children[i] = NULL;
			bstr = false;
		}
		Node(char ch):c(ch)
		{
			for (int i = 0; i < 26; ++i)
				children[i] = NULL;
			bstr = false;
		}
	}root;
	// Adds a word into the data structure.
	void addWord(string word) {
		Node* pRoot = &root;
		for (int i = 0; i < word.length(); ++i)
		{
			if (pRoot->children[word[i] - 'a'] == NULL)
			{
				pRoot->children[word[i] - 'a'] = new Node(word[i]);
			}
			pRoot = pRoot->children[word[i] - 'a'];
			if (i + 1 == word.length())
				pRoot->bstr = true;
		}
	}

	int check(string& s)
	{
		Node* pRoot = &root;
		Node* eNode = NULL;
		for (int i = 0; i < s.length(); ++i)
		{
			pRoot = pRoot->children[s[i] - 'a'];
			if (pRoot == NULL)
				return 0;
			if (i + 1 == s.length())
				eNode = pRoot;
		}
		if (eNode->bstr) return 1;
		return -1;
	}

	// Returns if the word is in the data structure. A word could
	// contain the dot character '.' to represent any one letter.
	bool search(string word) {
		bool r = false;
		string st;
		solve(r, st, word, 0);
		return r;
	}

	void solve(bool& r, string& st, string& word, int index)
	{
		int pos = index;
		for (; pos < word.length(); ++pos)
		{
			if (word[pos] == '.')
			{
				break;
			}
			st.push_back(word[pos]);
		}

		if (st.length() == word.length())
		{
			if (r == false)
			{
				r =  (1 == check(st));
			}
			return;
		}

		for (int i = 'a'; i <= 'z'; ++i)
		{
			st.push_back((char)i);
			if (0 == check(st))
			{
				st.pop_back();
				continue;
			}
			solve(r, st, word, pos + 1);
			if (r) return;
			int l = st.length() - pos;
			while (l > 0)
			{
				st.pop_back();
				--l;
			}
		}
	}
};

發表於   |   分類於

Unique Binary Search Trees

Given n, how many structurally unique BST’s (binary search trees) that store values 1…n?

For example,

Given n = 3, there are a total of 5 unique BST’s.

1
2
3
4
5
1         3     3      2      1
 \       /     /      / \      \
  3     2     1      1   3      2
 /     /       \                 \
2     1         2                 3

比较像矩阵链乘：取不同的分界点作为根，求两边的子树数量的乘积。

递归形式的AC代码，对迭代递推还是不够熟练：

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:

    vector<vector<int>> DP;

    int solve(int begin, int end)
    {
        if (begin >= end) return 1;
        if (DP[begin][end]) return DP[begin][end];
        int f = 0;
        for (int i = begin; i <= end; ++i)
        {
            int r = solve(begin,i-1);
            int l = solve(i+1,end);
            f += r * l;
        }
        DP[begin][end] = f;
        return f;
    }

    int numTrees(int n) {
        if (1 >= n) return 1;
        DP = vector<vector<int>>(n+1,vector<int>(n+1,0));
        solve(1,n);
        int result = 0;
        return DP[1][n];
    }
};

發表於   |   分類於

Counting Bits

Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1’s in their binary representation and return them as an array.

Example:

For num = 5 you should return [0,1,1,2,1,2].

关键点在于找出数字二进制之间的关系：15 = 8 + 7，20 = 16 + 4这样

AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<int> countBits(int num) {
        vector<int> DP(num+1,0);
        DP[1] = 1;
        DP[2] = 1;
        for (int i = 3; i <= num; ++i)
        {
            int k = 1;
            while(k <= i)
            {
                k *= 2;
            }
            k /= 2;
            int l = i - k;
            if (l == 0) DP[i] = 1;
            else DP[i] = DP[k] + DP[l];
        }
        return DP;
    }
};

發表於   |   分類於

Coin Change

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount.

If that amount of money cannot be made up by any combination of the coins, return -1.

Example 1:

coins = [1, 2, 5], amount = 11
return 3 (11 = 5 + 5 + 1)

Example 2:

coins = [2], amount = 3
return -1.

Note:
You may assume that you have an infinite number of each kind of coin.

有向无环图上的最短路问题：给定一个出发点，求它到所有叶子节点的路径中最短的那条路径的长度。

AC代码：

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:

	int solve(int rest,vector<int>& coins, int amount, vector<int>& DP)
	{
		if (rest == 0) return 0;
		if (rest < 0) return amount+1;

		if (DP[rest] >= 0) return DP[rest];

		int r = amount + 1;

		for (int i = 0; i < coins.size(); ++i)
		{
			int s = solve(rest - coins[i], coins, amount, DP) + 1;
			if (s < r) r = s;
		}

		DP[rest] = r;

		return r;
	}

	int coinChange(vector<int>& coins, int amount) {

		if (0 == amount) return 0;
		if (0 == coins.size()) return -1;

		vector<int> DP(amount+1,-1);

		int r = solve(amount,coins,amount,DP);

		if (r > amount) return -1;

		return r;
	}
};

非递归形式：

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 coinChange(vector<int>& coins, int amount) {
		if (0 == amount) return 0;
		if (0 == coins.size()) return -1;

		vector<int> DP(amount + 1, INT_MAX);
		DP[0] = 0;

		for (int i = 0; i < coins.size(); ++i)
		{
			for (int j = 1; j <= amount ; ++j)
			{
				if (j >= coins[i] && DP[j - coins[i]] != INT_MAX)
				{
					DP[j] = min(DP[j], DP[j-coins[i]]+1);
				}
			}
		}

		if (DP[amount] > amount) return -1;
		return DP[amount];
	}
};