一起让华裔陈卓光Denny Chin法官继任最高法院法官！# EB23 - 劳工卡
s*s
1 楼
follow一下我的面经。
http://www.mitbbs.com/article_t/JobHunting/32517841.html
整理了我的几个解答的算法，分享一下。欢迎批评指正。
多谢！
1. 写一个程序，找出 5^1234566789893943的从底位开始的1000位数字。
我用的递归+数组大数乘法。
// Caclulate (m^n)%(10^k). Keep the k integer numbers in an array.
// Note: the integer numbers are in reversed in the array
// Assume: m>0, n>0, k>0
// Need to check validity outside of this function.
// call calculate(5, 1234566789893943, 1000) to get result.
// Time complexity: O((log n) * k * k)
// Space complexity: O((log n) * k)
vector calculate(unsigned long m, unsigned long n, int k) {
if(k == 0) {
return vector(1, 1);
} else if(k % 2) { // odd number
vector tmp(1, m);
vector result1 = calculate(m, n-1, k);
return multiplyArrays(result1, tmp, k);
} else {
vector result1 = calculate(m, n/2, k);
return multiplyArrays(result1, result1, k);
}
}
vector multiplyArrays(const vector &data1, const
vector &data2, int k) {
vector result;
int sz1 = data1.size();
int sz2 = data2.size();
for(int i=0; i
for(int j=0; j
if(i+j+1 > k)
break;
const char value = data1[i] * data2[j];
//if(result.size() < i+j+1) {
while(result.size() < i+j+1) {
result.push_back(0);
}
value += result[i+j] + carry;
carry = value/10;
result[i+j] = value % 10;
}
if(i+sz2<=k && carry) {
while(result.size() < i+sz2) {
result.push_back(0);
}
result[i+sz2-1] += carry;
}
}
return result;
}
2. Given a integer array, test if there is any consequel subarray which sum
of elements is 0.
[7, 1, 1, -2, 3, 4] ==> true [1, 1, -1]
bool validArray(const vector &data) {
unordered_set M;
long long sum = 0;
for(int i=0; i
if(M.find(sum) != M.end())
return true;
M.insert(sum);
}
return false;
}
3. 密码锁问题，实现最短密码问题，版上有讨论。
这个题可以这么描述：
一个数字串有4个数字，每个数字是 0 ~9 这10个数字。
那么一共有0000 ~ 9999 共10,000个串。
要求：找出一个最短的串，包含这10，000个数字串
// Assume memory is not an issue here.
// It is easy to find a memory efficiency way
string calculate() {
// assume all the strings are in an array vector input;
string result;
for(int i=0; i
unordered_set visited;
bool succeed = DFS(visited, input[i], result);
if(succeed)
return result;
}
// Can not generate!
return "";
}
bool DFS(unordered_set &visited, const string &node, string &
result) {
visited.insert(node);
if(visited.size() == 10000)
return true;
string nodeseg = node.substr(1, 3);
for(int i=0; i<10; ++i) {
char ch = '0' + i;
string nextNode = nodeset;
nextNode.push_back(ch);
if(visited.find(nextNode) != visited.end()) {
result.push_back(ch);
bool bSucceed = DFS(visited, nextNode, result);
if(bSucceed)
return true;
result.pop_back();
}
}
visited.erase(node);
return false;
}
http://www.mitbbs.com/article_t/JobHunting/32517841.html
整理了我的几个解答的算法，分享一下。欢迎批评指正。
多谢！
1. 写一个程序，找出 5^1234566789893943的从底位开始的1000位数字。
我用的递归+数组大数乘法。
// Caclulate (m^n)%(10^k). Keep the k integer numbers in an array.
// Note: the integer numbers are in reversed in the array
// Assume: m>0, n>0, k>0
// Need to check validity outside of this function.
// call calculate(5, 1234566789893943, 1000) to get result.
// Time complexity: O((log n) * k * k)
// Space complexity: O((log n) * k)
vector
if(k == 0) {
return vector
} else if(k % 2) { // odd number
vector
vector
return multiplyArrays(result1, tmp, k);
} else {
vector
return multiplyArrays(result1, result1, k);
}
}
vector
vector
vector
int sz1 = data1.size();
int sz2 = data2.size();
for(int i=0; i
for(int j=0; j
if(i+j+1 > k)
break;
const char value = data1[i] * data2[j];
//if(result.size() < i+j+1) {
while(result.size() < i+j+1) {
result.push_back(0);
}
value += result[i+j] + carry;
carry = value/10;
result[i+j] = value % 10;
}
if(i+sz2<=k && carry) {
while(result.size() < i+sz2) {
result.push_back(0);
}
result[i+sz2-1] += carry;
}
}
return result;
}
2. Given a integer array, test if there is any consequel subarray which sum
of elements is 0.
[7, 1, 1, -2, 3, 4] ==> true [1, 1, -1]
bool validArray(const vector
unordered_set
long long sum = 0;
for(int i=0; i
if(M.find(sum) != M.end())
return true;
M.insert(sum);
}
return false;
}
3. 密码锁问题，实现最短密码问题，版上有讨论。
这个题可以这么描述：
一个数字串有4个数字，每个数字是 0 ~9 这10个数字。
那么一共有0000 ~ 9999 共10,000个串。
要求：找出一个最短的串，包含这10，000个数字串
// Assume memory is not an issue here.
// It is easy to find a memory efficiency way
string calculate() {
// assume all the strings are in an array vector
string result;
for(int i=0; i
unordered_set
bool succeed = DFS(visited, input[i], result);
if(succeed)
return result;
}
// Can not generate!
return "";
}
bool DFS(unordered_set
result) {
visited.insert(node);
if(visited.size() == 10000)
return true;
string nodeseg = node.substr(1, 3);
for(int i=0; i<10; ++i) {
char ch = '0' + i;
string nextNode = nodeset;
nextNode.push_back(ch);
if(visited.find(nextNode) != visited.end()) {
result.push_back(ch);
bool bSucceed = DFS(visited, nextNode, result);
if(bSucceed)
return true;
result.pop_back();
}
}
visited.erase(node);
return false;
}
