Find the Duplicate Number
Given an array
nums containing
n + 1 integers where each integer is between 1 and
n
(inclusive), prove that at least one duplicate number must exist.
Assume that there is only one duplicate number, find the duplicate one.
Note:
- You must not modify the array (assume the array is read only).
- You must use only constant, O(1) extra space.
- Your runtime complexity should be less than
O(n2).
- There is only one duplicate number in the array, but it could be repeated more than once.
-----------------------------------------------------------------------
Sol #1: 因为数字的范围是1 - n, 在范围内取一个值，遍历所给的数组，记下所有比这个值小的个数，进行对比。取值的方法用binary search
O(nlgn)
class Solution {
public:
int findDuplicate(vector<int>& nums) {
int n = nums.size() - 1;
int low = 1, high = n;
while (low < high) {
int mid = (low + high) / 2;
int count = 0;
for (int i = 0; i <= n; i++) {
if (nums[i] <= mid) {
count++;
}
}
if (count > mid) {
high = mid;
}else {
low = mid + 1;
}
if (low == high) return low;
}
}
};
O(n)
ref: http://keithschwarz.com/interesting/code/?dir=find-duplicate
class Solution {
public:
int findDuplicate(vector<int>& nums) {
int n = nums.size();
int slow = n, fast = n;
while (true) {
fast = nums[nums[fast - 1] - 1];
slow = nums[slow - 1];
if (slow == fast) break;
}
slow = n;
while (slow != fast) {
slow = nums[slow - 1];
fast = nums[fast - 1];
}
return slow;
}
};
Word Pattern
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 word in str.
Examples:
- pattern =
"abba", str = "dog cat cat dog" should return true.
- pattern =
"abba", str = "dog cat cat fish" should return false.
- pattern =
"aaaa", str = "dog cat cat dog" should return false.
- pattern =
"abba", str = "dog dog dog dog" should return false.
Notes:
You may assume pattern contains only lowercase letters, and str contains lowercase letters separated by a single space.
--------------------------------------------------
2个hashmap 互相对应
class Solution {
public:
string getWord(string str, int &index) {
string rt = "";
for (; index < str.length(); index++) {
if (isalpha(str[index])) {
rt += str[index];
}else break;
}
index++;
return rt;
}
bool wordPattern(string pattern, string str) {
unordered_map<char,string> pToS;
unordered_map<string,char> sToP;
int index = 0;
for (int i = 0; i < pattern.length(); i++) {
if (index == str.length()) return false;
string word = getWord(str,index);
if (pToS.find(pattern[i]) == pToS.end()) {
pToS[pattern[i]] = word;
}else if (word != pToS[pattern[i]]) return false;
if (sToP.find(word) == sToP.end()) {
sToP[word] = pattern[i];
}else if (sToP[word] != pattern[i]) return false;
}
return index == str.length() + 1;
}
};
Word Pattern II
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:
- 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.
-------------------------------------------------------
back tracking
对一个pattern[i], 试遍每一种可能
class Solution {
public:
bool helper(string pattern, int i, string str, int is, unordered_map<char,string> &ptos, unordered_map<string,char> &stop) {
if (i == pattern.length() && is == str.length()) return true;
if (i == pattern.length() || is == str.length()) return false;
if (ptos.find(pattern[i]) != ptos.end()) {
if (ptos[pattern[i]] == str.substr(is,ptos[pattern[i]].length())) {
return helper(pattern,i + 1, str, is + ptos[pattern[i]].length(),ptos,stop);
}
return false;
}
for (int j = is; j < str.length(); j++) {
string word = str.substr(is,j - is + 1);
if (stop.find(word) != stop.end()) continue;
ptos[pattern[i]] = word;
stop[word] = pattern[i];
if (helper(pattern, i + 1, str, j + 1, ptos,stop)) return true;
ptos.erase(pattern[i]);
stop.erase(word);
}
return false;
}
bool wordPatternMatch(string pattern, string str) {
unordered_map<char,string> ptos;
unordered_map<string,char> stop;
return helper(pattern,0,str,0,ptos,stop);
}
};
Nim Game
You are playing the following Nim Game with your friend: There is a heap
of stones on the table, each time one of you take turns to remove 1 to 3
stones. The one who removes the last stone will be the winner. You will
take the first turn to remove the stones.
Both of you are very clever and have optimal strategies for the game.
Write a function to determine whether you can win the game given the
number of stones in the heap.
For example, if there are 4 stones in the heap, then you will never win
the game: no matter 1, 2, or 3 stones you remove, the last stone will
always be removed by your friend.
Hint:
- If there are 5 stones in the heap, could you figure out a way to remove the stones such that you will always be the winner?
---------------------------------------
可递归，可DP，但是以下为最简
class Solution {
public:
bool canWinNim(int n) {
return n % 4;
}
};
Best Meeting Point
A group of two or more people wants to meet and minimize the total travel distance. You are given a 2D grid of values 0 or 1, where each 1 marks the home of someone in the group. The distance is calculated using
Manhattan Distance, where distance(p1, p2) =
|p2.x - p1.x| + |p2.y - p1.y|.
For example, given three people living at (0,0), (0,4), and (2,2):
1 - 0 - 0 - 0 - 1
| | | | |
0 - 0 - 0 - 0 - 0
| | | | |
0 - 0 - 1 - 0 - 0
The point (0,2) is an ideal meeting point, as the total travel distance of 2+2+2=6 is minimal. So return 6.
Hint:
- Try to solve it in one dimension first. How can this solution apply to the two dimension case?
--------------------------------------------------------------
O(m*n*log(m*n) )
class Solution {
public:
int minTotalDistance(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
vector<int> I,J;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) {
I.push_back(i);
J.push_back(j);
}
}
}
return getDis(I) + getDis(J);
}
int getDis(vector<int> &num) {
int rt = 0, left = 0, right = num.size() - 1;
sort(num.begin(), num.end());
while (left < right) {
rt += num[right] - num[left];
right--;
left++;
}
return rt;
}
};
O(mn)
class Solution {
public:
int minTotalDistance(vector>& grid) {
int m = grid.size(), n = grid[0].size();
vector I,J;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) {
I.push_back(i);
}
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (grid[j][i] == 1) {
J.push_back(i);
}
}
}
return getDis(I) + getDis(J);
}
int getDis(vector &num) {
int rt = 0, left = 0, right = num.size() - 1;
while (left < right) {
rt += num[right] - num[left];
right--;
left++;
}
return rt;
}
};
