LeetCode 213. House Robber II

Jan 19, 2017

题目描述：

Note: This is an extension of House Robber.

After robbing those houses on that street, the thief has found himself a new place for his thievery so that he will not get too much attention. This time, all houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, the security system for these houses remain the same as for those in the previous street.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

在House Robber的简单DP基础上考虑首尾也是相邻的。我把第一个house是否rob分开来进行了两次DP，然后根据最后一个house有没有被抢来从中选择正确的结果。

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
class Solution {
public:
	int rob(vector<int>& nums) {
		if (nums.empty()) return 0;
		else if (nums.size() == 1) return nums[0];
		else if (nums.size() == 2) {
			return max(nums[0], nums[1]);
		}
		vector<int> v(nums.size(), 0);
		vector<bool> robbed(nums.size(), false);
		v[0] = nums[0];
		robbed[0] = true;
		v[1] = v[0];
		for (int i = 2; i < nums.size(); i++) {
			if (nums[i] + v[i - 2] > v[i - 1]) {
				v[i] = nums[i] + v[i - 2];
				robbed[i] = true;
				robbed[i - 1] = false;
				robbed[i - 2] = true;
			}
			else {
				v[i] = v[i - 1];
				robbed[i - 1] = true;
				robbed[i - 2] = false;
			}
		}
		bool lastRobbed = robbed.back();
		int firstRobbedMax = v.back(), firstRobbedLastNotMax3 = v[v.size() - 3], firstRobbedLastNotMax2 = v[v.size() - 2];
		v[0] = 0;
		robbed[0] = false;
		v[1] = nums[1];
		robbed[1] = true;
		for (int i = 2; i < nums.size(); i++) {
			if (nums[i] + v[i - 2] > v[i - 1]) {
				v[i] = nums[i] + v[i - 2];
				robbed[i] = true;
			}
			else {
				v[i] = v[i - 1];
			}
		}
		int firstNotRobbedMax = v.back();
		if (firstRobbedMax > firstNotRobbedMax && !lastRobbed) return firstRobbedMax;
		else return max(firstNotRobbedMax, max(firstRobbedLastNotMax3, firstRobbedLastNotMax2));
	}
};

LeetCode 212. Word Search II

Jan 19, 2017

题目描述：

Given a 2D board and a list of words from the dictionary, find all words in the board.

Each word must 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 in a word.

For example, Given words = ["oath","pea","eat","rain"] and board =

1
2
3
4
5
6
7
[
  ['o','a','a','n'],
  ['e','t','a','e'],
  ['i','h','k','r'],
  ['i','f','l','v']
]

Return

1
["eat","oath"]

.

Note: You may assume that all inputs are consist of lowercase letters a-z.

用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
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
class TrieNode {
public:
    bool isEnd;
    char val;
    vector<TrieNode*> children;
    TrieNode(char _v): isEnd(false), val(_v) {
        children = vector<TrieNode*>(26, nullptr);
    }
};

class Solution {
    TrieNode* root = new TrieNode(0);
    vector<vector<int>> visited;
    vector<string> ans;
    vector<vector<int>> steps = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    int row, col;
public:
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        for(auto word : words) {
            insertToTrie(word);
        }
        row = board.size();
        if(row == 0) return ans;
        col = board[0].size();
        if(col == 0) return ans;
        visited = vector<vector<int>>(row, vector<int>(col, 0));
        
        string path;
        for(int i = 0; i < row; i++){
            for(int j = 0; j < col; j++){
                DFS(board, path, i, j, root->children[board[i][j] - 'a']);
            }
        }
        return ans;
    }
    
    void DFS(vector<vector<char>>& board, string &boardPath, int r, int c, TrieNode *node) {
        if (node == nullptr) return;
        visited[r][c] = 1;
        char val = board[r][c];
        boardPath.push_back(val);
        
        if (node->isEnd) {
            ans.push_back(boardPath); 
            node->isEnd = false;
        }
        
        for (int i = 0; i < 4; i++) {
            int tr = r + steps[i][0], tc = c + steps[i][1];
            if (isValidPoint(board, tr, tc)) {
                TrieNode *next = node->children[board[tr][tc] - 'a'];
                DFS(board, boardPath, tr, tc, next);
            }
        }
        boardPath.pop_back();
        visited[r][c] = 0;
    }
    
    bool isValidPoint(vector<vector<char>>& board, int r, int c) {
        if(r < 0 || r >= row || c < 0 || c >= col || visited[r][c]) return false;
        else return true;
    }
    
    void insertToTrie(string s) {
        TrieNode *p = root, *prev;
        int i = 0;
        do {
            int next = s[i++] - 'a';
            prev = p;
            p = p->children[next];
        } while (p && i < s.length());
        if (i < s.length() || p == nullptr) {
            p = prev;
            for(i--; i < s.length(); i++){
                int next = s[i] - 'a';
                p->children[next] = new TrieNode(s[i]);
                p = p->children[next];
            }
        }
        p->isEnd = true;
    }
};

LeetCode 211. Add and Search Word - Data structure design

Jan 17, 2017

题目描述：

Design a data structure that supports the following two operations:

1
2
3
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
8
addWord("bad")
addWord("dad")
addWord("mad")
search("pad") -> false
search("bad") -> true
search(".ad") -> true
search("b..") -> true

Note: You may assume that all words are consist of lowercase letters a-z.

直接用前缀树来实现。

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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
class TrieNode {
public:
	char val;
	vector<TrieNode*> children;
	TrieNode* parent;
	bool wordEnd = false;
	TrieNode(char v = 0, TrieNode *p = nullptr) : val(v), parent(p) {}
};

class Trie {
public:
	TrieNode* root;
	Trie() {
		root = new TrieNode();
	}

	// Inserts a word into the trie.
	void insert(string word) {
		insertToNode(word, root);
	}

	void insertToNode(string word, TrieNode* node) {
		if (word.empty()) {
			node->wordEnd = true;
			return;
		}
		for (int i = 0; i < node->children.size(); i++) {
			if (word[0] == node->children[i]->val) {
				return insertToNode(word.substr(1), node->children[i]);
			}
		}
		TrieNode *p = new TrieNode(word[0], node);
		node->children.push_back(p);
		for (int i = 1; i < word.size(); i++) {
			TrieNode *tmp = new TrieNode(word[i], p);
			p->children.push_back(tmp);
			p = tmp;
		}
		p->wordEnd = true;
	}

	// Returns if the word is in the trie.
	bool search(string word, TrieNode *node = nullptr) {
		int pos = 0;
		TrieNode *p = (node ? node : root);
		if (word.empty()) {
			if (p->wordEnd)
				return true;
			else
				return false;
		}
		for (; pos < word.size(); pos++) {
			if (word[pos] == '.') {
				if (p->children.empty() && word.size() > 1)
					return false;
				for (int i = 0; i < p->children.size(); i++) {
					if (search(word.substr(pos + 1), p->children[i]))
						return true;
				}
				return false;
			}
			else {
				bool flag = false;
				for (int i = 0; i < p->children.size(); i++) {
					if (word[pos] == p->children[i]->val) {
						p = p->children[i];
						flag = true;
						break;
					}
				}
				if (flag == false) {
					return false;
				}
			}
		}
		if (pos == word.size() && p->wordEnd) return true;
		else return false;
	}

	// Returns if there is any word in the trie
	// that starts with the given prefix.
	bool startsWith(string prefix) {
		int pos = 0;
		TrieNode *p = root;
		for (; pos < prefix.size(); pos++) {
			bool flag = false;
			for (int i = 0; i < p->children.size(); i++) {
				if (prefix[pos] == p->children[i]->val) {
					p = p->children[i];
					flag = true;
					break;
				}
			}
			if (flag == false) {
				return false;
			}
		}
		return true;
	}

};

class WordDictionary {
public:
	Trie trie;

	// Adds a word into the data structure.
	void addWord(string word) {
		trie.insert(word);
	}

	// 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) {
		return trie.search(word);
	}
};

LeetCode 210. Course Schedule II

Jan 17, 2017

题目描述：

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].

Note: The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.

要求返回一个图的拓扑排序结果，在有向图存在环路的时候返回空集。拓扑排序可以用点度和队列结合的办法，也可以用DFS的办法。因为输入数据是邻接表，对边的处理比较慢，所以我用DFS来实现拓扑排序，同时判断是否有环存在。

这个题有个条件就是节点编号是在0-n-1之间的，所以记录一个节点的状态可以用数组，没有查询的开销。

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 {
    vector<int> visited;
    vector<int> inPath;
public:
    vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
        vector<vector<int>> nextCourses(numCourses), preReq(numCourses);
        for(auto i : prerequisites){
            preReq[i.first].push_back(i.second);
            nextCourses[i.second].push_back(i.first);
        }
        visited = vector<int>(numCourses, 0);
        inPath = vector<int>(numCourses, 0);
        vector<int> ans;
        for(int i = 0; i < numCourses; i++){
            if(!visited[i] && preReq[i].empty()){
                // Begin node
                vector<int> t, path;
                if(DFS(nextCourses, preReq, i, path, t))
                    ans.insert(ans.end(), t.begin(), t.end());
                else
                    return vector<int>();
            }
        }
        if(ans.size() != numCourses)
            return vector<int>();
        else
            return ans;
    }
    
    bool DFS(vector<vector<int>> &nextCourses, vector<vector<int>> &preReq, int node, vector<int> &path, vector<int> &ans){
        if(inPath[node]) {
            ans.clear();
            return false;
        }
        if(visited[node]) return true;
        for(auto i : preReq[node]){
            if(!visited[i])
                return true;
        }
        
        path.push_back(node);
        ans.push_back(node);
        inPath[node] = visited[node] = 1;
        
        for(auto i : nextCourses[node]){
            if(!DFS(nextCourses, preReq, i, path, ans)) 
                return false;
        }
        path.pop_back();
        inPath[node] = 0;
        return true;
    }
};

LeetCode 488. Zuma Game

Jan 15, 2017

题目描述：

Think about Zuma Game. You have a row of balls on the table, colored red®, yellow(Y), blue(B), green(G), and white(W). You also have several balls in your hand.

Each time, you may choose a ball in your hand, and insert it into the row (including the leftmost place and rightmost place). Then, if there is a group of 3 or more balls in the same color touching, remove these balls. Keep doing this until no more balls can be removed.

Find the minimal balls you have to insert to remove all the balls on the table. If you cannot remove all the balls, output -1.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Examples:

Input: "WRRBBW", "RB"
Output: -1
Explanation: WRRBBW -> WRR[R]BBW -> WBBW -> WBB[B]W -> WW

Input: "WWRRBBWW", "WRBRW"
Output: 2
Explanation: WWRRBBWW -> WWRR[R]BBWW -> WWBBWW -> WWBB[B]WW -> WWWW -> empty

Input:"G", "GGGGG"
Output: 2
Explanation: G -> G[G] -> GG[G] -> empty 

Input: "RBYYBBRRB", "YRBGB"
Output: 3
Explanation: RBYYBBRRB -> RBYY[Y]BBRRB -> RBBBRRB -> RRRB -> B -> B[B] -> BB[B] -> empty

Note:

  1. You may assume that the initial row of balls on the table won’t have any 3 or more consecutive balls with the same color.
  2. The number of balls on the table won’t exceed 20, and the string represents these balls is called “board” in the input.
  3. The number of balls in your hand won’t exceed 5, and the string represents these balls is called “hand” in the input.
  4. Both input strings will be non-empty and only contain characters ‘R’,‘Y’,‘B’,‘G’,‘W’.

这次Contest中最难的题。Zuma游戏的规则，从hand中抽取ball插入到board中，有大于等于三个相同颜色的ball连着就可以消去，问最少几步可以消去，或者无法消去。

初看这道题我以为是图的连通性和最短路径问题（其实也差不多），然后发现构建图的过程中就已经完成了遍历可以得到结果了。使用回溯法，时间上可能效率不高，但好在方法比较容易想到。

对输入的board尝试消去每一个可能的位置，然后对每一个得到的结果递归地进行处理（DFS）。因为board长度不超过20，所以不会因为解空间太大而超时。

代码是Contest的时候写的，可能比较乱……

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
class Solution {
public:
    int findMinStep(string board, string hand){
        return findMinStepImpl(board, hand);
    }
    
    int findMinStepImpl(string board, string hand) {
        if(board.empty()) return 0;
        int minStep = INT_MAX;
        for(int i = 0; i < board.size() - 1; i++){
            if(board[i] == board[i + 1]){
                if(findBall(board[i], hand) != -1){
                    string tb = board, th = hand;
                    char ball = board[i];
                    removeBall(ball, th);
                    tb.insert(tb.begin() + i, ball);
                    removeThree(tb);
                    int ans = findMinStepImpl(tb, th);
                    if(ans != -1) minStep = min(minStep, ans + 1);
                }
            }
        }
        
        if(minStep != INT_MAX)
            return minStep;
        
        for(int i = 0; i < board.size(); i++){
            if(findBall(board[i], hand) != -1){
                string tb = board, th = hand;
                char ball = board[i];
                removeBall(ball, th);
                tb.insert(tb.begin() + i, ball);
                int ans = findMinStepImpl(tb, th);
                if(ans != -1) minStep = min(minStep, ans + 1);
            }
        }
        if(minStep != INT_MAX)
            return minStep;
        else
            return -1;
    }
    
    int findBall(char ball, string &hand){
        auto iter = find(hand.begin(), hand.end(), ball);
        if(iter == hand.end()) return -1;
        else return iter - hand.begin();
    }
    
    void removeBall(char ball, string &hand){
        auto iter = find(hand.begin(), hand.end(), ball);
        if(iter != hand.end()){
            hand.erase(iter);
        }
    }
    
    void removeThree(string &b){
        if(b.size() < 3) return ;
        for(int i = 1; i < b.size(); i++){
            if(b[i] == b[i - 1]){
                int j;
                for(j = i; j < b.size() && b[j] == b[i]; j++);
                if(j - i + 1 >= 3) {
                    b.erase(i - 1, j - i + 1);
                    return removeThree(b);
                }
            }
        }
    }
};

LeetCode 487. Max Consecutive Ones II

Jan 15, 2017

题目描述：

Given a binary array, find the maximum number of consecutive 1s in this array if you can flip at most one 0.

Example 1:

1
2
3
4
5
Input: [1,0,1,1,0]
Output: 4
Explanation: Flip the first zero will get the the maximum number of consecutive 1s.
    After flipping, the maximum number of consecutive 1s is 4.

Note:

  • The input array will only contain 0 and 1.
  • The length of input array is a positive integer and will not exceed 10,000

Follow up: What if the input numbers come in one by one as an infinite stream? In other words, you can’t store all numbers coming from the stream as it’s too large to hold in memory. Could you solve it efficiently?

这道题是上一题的升级版。区别在于可以把最多一个0视为1，再求最长的连续1的个数。

我的解法也延续上一题的思路使用双指针，不过这次增加一个变量来记录跳过了多少个0。需要注意的是...100这种情况，左指针（指向子串开头的位置）不能只简单地跳过所有1之后再加1，而应该继续跳过连续的0，这可能导致左指针超过右指针，所以这时要更新右指针。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int findMaxConsecutiveOnes(vector<int>& nums) {
       int maxNum = 0;
       int p1 = 0, p2 = 0, zero = 1;
       for(; p2 < nums.size(); p2++){
           if(nums[p2] == 0) zero--;
           if(zero < 0){
               maxNum = max(maxNum, p2 - p1);
               while(p1 < nums.size() && nums[p1] != 0) p1++;
               while(p1 < nums.size() && nums[p1] != 1) {
                   p1++;
                   if(zero < 1) zero++;
               }
               if(p2 < p1) p2 = p1;
           }
       }
       maxNum = max(maxNum, (int)nums.size() - p1);
       return maxNum;
    }
};

LeetCode 485. Max Consecutive Ones

Jan 15, 2017

题目描述：

Given a binary array, find the maximum number of consecutive 1s in this array.

Example 1:

1
2
3
4
5
Input: [1,1,0,1,1,1]
Output: 3
Explanation: The first two digits or the last three digits are consecutive 1s.
    The maximum number of consecutive 1s is 3.

Note:

  • The input array will only contain 0 and 1.
  • The length of input array is a positive integer and will not exceed 10,000

最长的连续1的个数。很简单，方法也很多。一开始在最后加一个0是为了方便结尾的处理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int findMaxConsecutiveOnes(vector<int>& nums) {
        nums.push_back(0);
        int maxNum = 0;
        int beginIndex = -1;
        for (int i = 0; i < nums.size(); i++) {
            if(nums[i] == 1 && beginIndex == -1){
                beginIndex = i;
            }
            else if(nums[i] == 0){
                if(beginIndex != -1){
                    maxNum = max(maxNum, i - beginIndex);
                }
                beginIndex = -1;
            }
        }
        return maxNum;
    }
};

LeetCode 390. Elimination Game

Jan 13, 2017

题目描述：

There is a list of sorted integers from 1 to n. Starting from left to right, remove the first number and every other number afterward until you reach the end of the list.

Repeat the previous step again, but this time from right to left, remove the right most number and every other number from the remaining numbers.

We keep repeating the steps again, alternating left to right and right to left, until a single number remains.

Find the last number that remains starting with a list of length n.

Example:

1
2
3
4
5
6
7
8
9
Input:
n = 9,
1 2 3 4 5 6 7 8 9
2 4 6 8
2 6
6

Output:
6

这道题我一开始认为会有一个公式来直接计算出最后一个剩下的数是多少，然后又尝试DP从n-1推出n，都没想出来，最后采用的是递归的方法。对于n来说，当n为偶数时，经过一次处理后剩下n/2个数；当为n奇数时，经过一次处理后剩下(n-1)/2个数，把剩下的数的个数作为下一次处理的输入（假设我们的每次处理返回的是数的下标而不是数的具体值），得到的结果为m，那么我们只要把下标m恢复为本次处理的下标即可。

那么如何回复呢？同样分奇偶进行分类，当n为奇数时，举个例子：

1
2
3
4
Index: 0 1 2 3 4
Value: 1 2 3 4 5
Index: _ 0 _ 1 _
Value: _ 2 _ 4 _

无论处理方向正反得到的结果是一样的。可以看出这么一个映射：

1
2
3
4
5
m
0 => 1
1 => 3
2 => 5
...

所以m * 2 + 1就是本次处理的结果中下标为m的数在本次处理之前的下标。

当m为奇数时有类似的规律，只不过要分处理正（从头到尾）反（从尾到头）方向来讨论。对于正向来说，仍然是m * 2 + 1，对于反向来说则是m * 2。

递归终止条件显然为n==1时返回0。每次递归时要对处理方向取反。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    const int L2R = 1, R2L = -1;
    
public:
    int lastRemaining(int n) {
        return lastRemainingImpl(n, L2R) + 1;
    }
    
    int lastRemainingImpl(int n, int direction){
        if(n == 1){
            return 0;
        }
        
        int t = lastRemainingImpl(n % 2 ? (n - 1) / 2 : n / 2, -direction);
        if(n % 2 || direction == L2R){
            return t * 2 + 1;
        }
        else{
            return t * 2;
        }
    }
};

LeetCode 482. License Key Formatting

Jan 13, 2017

题目描述：

Now you are given a string S, which represents a software license key which we would like to format. The string S is composed of alphanumerical characters and dashes. The dashes split the alphanumerical characters within the string into groups. (i.e. if there are M dashes, the string is split into M+1 groups). The dashes in the given string are possibly misplaced.

We want each group of characters to be of length K (except for possibly the first group, which could be shorter, but still must contain at least one character). To satisfy this requirement, we will reinsert dashes. Additionally, all the lower case letters in the string must be converted to upper case.

So, you are given a non-empty string S, representing a license key to format, and an integer K. And you need to return the license key formatted according to the description above.

Example 1:

1
2
3
4
5
6
Input: S = "2-4A0r7-4k", K = 4

Output: "24A0-R74K"

Explanation: The string S has been split into two parts, each part has 4 characters.

Example 2:

1
2
3
4
5
6
Input: S = "2-4A0r7-4k", K = 3

Output: "24-A0R-74K"

Explanation: The string S has been split into three parts, each part has 3 characters except the first part as it could be shorter as said above.

Note:

  1. The length of string S will not exceed 12,000, and K is a positive integer.
  2. String S consists only of alphanumerical characters (a-z and/or A-Z and/or 0-9) and dashes(-).
  3. String S is non-empty.

题目说了很长，但是意思却很简单。就是把一个输入的字符串从后往前分割为K个一组，第一组可以不足K个。然后用“-”把它们连接起来。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    string licenseKeyFormatting(string S, int K) {
        string str;
        for(auto c : S){
            if(c == '-') continue;
            str.push_back(toupper(c));
        }
        string ans, tmp;
        int i;
        for(i = str.length(); i >= K; i -= K){
            ans = str.substr(i - K, K) + "-" + ans;
        }
        if(i > 0){
            ans = str.substr(0, i) + "-" + ans;
        }
        ans.pop_back(); // Delete "-" in the end of ans.
        return ans;
    }
};

LeetCode 476. Number Complement

Jan 13, 2017

题目描述：

Given a positive integer, output its complement number. The complement strategy is to flip the bits of its binary representation.

Note:

  1. The given integer is guaranteed to fit within the range of a 32-bit signed integer.
  2. You could assume no leading zero bit in the integer’s binary representation.

Example 1:

1
2
3
4
Input: 5
Output: 2
Explanation: The binary representation of 5 is 101 (no leading zero bits), and its complement is 010. So you need to output 2.

Example 2:

1
2
3
Input: 1
Output: 0
Explanation: The binary representation of 1 is 1 (no leading zero bits), and its complement is 0. So you need to output 0.

就是简单的按位取反，不过不能把前导零给取反了，所以要先确定最高位所在的位置，取反后将更高位置零。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int findComplement(int num) {
        unsigned int unum = num;
        int sigbit = 0;
        while(unum){
            unum >>= 1;
            sigbit++;
        }
        unum = ~num;
        unum = unum << (32 - sigbit) >> (32 - sigbit);
        return (int)unum;
    }
};