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)
ve... 阅读全帖
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)
ve... 阅读全帖
DP:
public bool WordBreak(string str, Dictionary dict)
{
// f[i] is true when str[0,...,i] is word break;
// f[i] = true when f[k]==true and str[k+1,...,i] is a word
// or str[0,...,i] is a word
int n = str.Length;
bool[] allWords = new bool[n];
int i, j;
for (i = 0; i < n; ++i)
{
if (!allWords[i] && dict.ContainsKey(str.Substring(0, i + 1)
)... 阅读全帖
多谢，改了后过了OJ。
如你所说，我加了1-D bool table来记录有没有解
后面DFS根据这个如果没有解就停止递归搜索
把整个code贴下面
vector wordBreak(string s, unordered_set &dict) {
// Note: The Solution object is instantiated only once and is reused
by each test case.
vector result;
int n = s.size();
vector> table(n, vector(n,false));
int max_len=0;
for(auto& word:dict){
if(max_len
max_len=word.size();
}
... 阅读全帖
challenge me
bool isRepeat(string s) {
bool ret = false;
int sz = s.size();
vector pi(sz, 0);
int k = 0;
for (int i = 1; i < sz; i ++) {
while (k != 0 && s[i] != s[k]) {
k = pi[k - 1];
}
if (s[i] == s[k]) {
k ++;
}
pi[i] = k;
}
int d = sz - pi[sz - 1];
int idx = d - 1;
int expectedRes = 0;
bool rFlag = false;
if (d < 2) {
ret = false;
goto e;
}
while (t... 阅读全帖
challenge me
bool isRepeat(string s) {
bool ret = false;
int sz = s.size();
vector pi(sz, 0);
int k = 0;
for (int i = 1; i < sz; i ++) {
while (k != 0 && s[i] != s[k]) {
k = pi[k - 1];
}
if (s[i] == s[k]) {
k ++;
}
pi[i] = k;
}
int d = sz - pi[sz - 1];
int idx = d - 1;
int expectedRes = 0;
bool rFlag = false;
if (d < 2) {
ret = false;
goto e;
}
while (t... 阅读全帖
Following is a recursive function. Use ids of p and q to identify the p and
q node. It is not very elegant to me. Any suggestions to improve it.
Thanks
void countPQ(TreeNode *root, int idP, bool &startP, int& counterP, int idQ,
bool &startQ, int &counterQ)
{
if(root==NULL)
{
return;
}
countPQ(root->left, idP, startP, counterP, idQ, startQ, counterQ);
if( root->val==idP ) startP=false;
if(startP) counterP++;
if( root->val==idQ ) startQ=false;
if(startQ) counterQ... 阅读全帖
走迷宫的 时间复杂度是多少？谢谢 如这个解法
#include
// Maze size
#define N 4
bool solveMazeUtil(int maze[N][N], int x, int y, int sol[N][N]);
/* A utility function to print solution matrix sol[N][N] */
void printSolution(int sol[N][N])
{
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
printf(" %d ", sol[i][j]);
printf("n");
}
}
/* A utility function to check if x,y is valid index for N*N maze */
bool isSafe(int maze[N][N], int x, int y)
{
// if (x,y out... 阅读全帖
完整代码：
/**
* 一个Cube有6个面，每一个面有一个color，这6个面的color是可以
* 任意的，而且可以重复。输入一系列的cube，判断这些cube能否组成一个四面都是
同样
* 颜色的tower(这些cube一个接一个竖着摞，没有并排的cube)。
*/
#include
using namespace std;
// Cube class. Color of cube is given in constructor.
class cube {
public:
int sides[6]; // {top, side1, side2, side3, side4, bottom}
int colors[6];
int config;
cube() {}
void init(int color[6]) {
for (int i = 0; i < 6; ++ i) colors[i] = color[i];
config = 0;
}
// given a cube ... 阅读全帖
各位都是大牛，我只有写代码的份。
根据mitkook2的算法，采用DP，复杂度O(NK) time, O(N) space
bool solve1(int n, const vector & seq)
{
if (n < 1 || (n < 2 && !seq.empty()))
return true;
vector dp(n, true);
for (int s : seq) {
assert(0 <= s && s < n);
bool survive = false, prev = false;
for (int i = 0; i < n; ++i) {
const bool c = (s != i
&& ((i && prev)
|| (i + 1 < n && dp[i + 1])));
if (c)
survive... 阅读全帖
Here is some code from the book. You can decide if you want to
read it ... I would spend my time on STL and Boost, at least
they are shown to be WORKING.
class SparseMultiGRAPH
{ int Vcnt, Ecnt; bool digraph;
struct node
{ int v; node* next;
node(int x, node* t) { v = x; next = t; }
};
typedef node* link;
vector adj;
public:
SparseMultiGRAPH(int V, bool digraph = false) :
adj(V), Vcnt(V), Ecnt(0), digraph(digraph)
{ adj.assign(V, 0); }
int V() const { retur... 阅读全帖
bool FindThreeNum1(int in[], int len, int sum, int out[]){
if (!in || len < 3 || !out)
return false;
std::sort(in, in + len);
int prej = 1;
int prek = len - 1;
for (int i = 0; i < prek - 2; ++i){
bool nobig = true;
bool nosmall = true;
int j = prej;
int k = prek;
int two_sum = sum - in[i];
while(j < k){
if (in[j] + in[k] == two_sum){
out[0] = in[i];
out[1] = in[j];
... 阅读全帖
bool findSolution (int coefficient[], int size, int rightside){//coefficient
[i] for Xi.
if (size<1) return false;
int reviewed = new int[size];
int lreviewed = 0;
return findPartialSolution (reviewed,lreviewed, coefficient, size,
rightside);
}
bool findPartialSolution (int reviewed[], int lreviewed, int coefficient [],
int size, int rightside){
if (lreviewed==size){
for (int i=0;i
return;
}
bool found=false;
for (int i=0; i阅读全帖
How about this one?
class Interval {
public:
Interval(int start_, int end_): start(start_),end(end_){}
int start;
int end;
};
bool comp(Interval &rhs, Interval &lhs)
{
return (rhs.start == lhs.start ? rhs.end < lhs.end : rhs.start < lhs.start);
}
bool check(vector &input)
{
int left = input[0].start;
int right = input[0].end;
for (int i = 1; i < input.size(); i++) {
if (right < input[i].start) {
return false;
} else {
right = max(input[i].end, right);
}
}
return true;
}
int main()
... 阅读全帖
bool Rand2(){ return true or false equally.};
// p is between 0 and 1
// return false for probability of p
bool PCal(double p)
{
p *= 2;
bool b = Rand2();
while(p != 0 && p! = 1)
{
b = Rand2();
if (!b && p > 1)
return false;
else (b && p < 1)
return true;
else
p = p *2;
}
return b;
}
bool Rand2(){ return true or false equally.};
// p is between 0 and 1
// return false for probability of p
bool PCal(double p)
{
p *= 2;
bool b = Rand2();
while(p != 0 && p! = 1)
{
b = Rand2();
if (!b && p > 1)
return false;
else (b && p < 1)
return true;
else if ( p > 1)
p = (p-1) *2;
else
p * =2;
}
return b;
}
bool Rand2(){ return true or false equally.};
// p is between 0 and 1
// return false for probability of p
bool PCal(double p)
{
p *= 2;
bool b = Rand2();
while(p != 0 && p! = 1)
{
b = Rand2();
if (!b && p > 1)
return false;
else (b && p < 1)
return true;
else
p = p *2;
}
return b;
}
