z*****e
发帖数: 231 | 1 贴一个O（n）的，
#include
using namespace std;
int trap(int A[], int n) {
int max=A[0];
int int_max=0;
int area=A[0];
if(n<3) return 0;
for(int i=1;i
{
area+=A[i];
if(A[i]>max)
{
max=A[i];
int_max=i;
}
}
int i=0;
int current=A[i];
int total=current;
i++;
while(i<=int_max)
... 阅读全帖 |
|
S******t
发帖数: 151 | 2 我大概写一个吧，没编译，不知道靠谱不
#include
#include
#include
using namespace std;
string dict[MAXNUM];
vector graph[MAXNUM];
bool visited[MAXNUM];
bool diff_one(string a,string b) {
int len_a = (int)a.size();
int len_b = (int)b.size();
if (len_a != len_b) return false;
int cnt = 0;
for(int i=0;i
if(a[i]!=b[i]) cnt++;
return cnt == 1;
}
void preprocess() {
int dict_sz = (int)dict.size();
for(int i=0;i
for(int j=i+1;j
... 阅读全帖 |
|
S******t
发帖数: 151 | 3 我大概写一个吧，没编译，不知道靠谱不
#include
#include
#include
using namespace std;
string dict[MAXNUM];
vector graph[MAXNUM];
bool visited[MAXNUM];
bool diff_one(string a,string b) {
int len_a = (int)a.size();
int len_b = (int)b.size();
if (len_a != len_b) return false;
int cnt = 0;
for(int i=0;i
if(a[i]!=b[i]) cnt++;
return cnt == 1;
}
void preprocess() {
int dict_sz = (int)dict.size();
for(int i=0;i
for(int j=i+1;j
... 阅读全帖 |
|
x*******5
发帖数: 152 | 4 这个是我的题库，还有一些题没有coding，比如back of envelop计算，idea思考，等等
Column 4-5 Pearl (namespace Pearl)
64. Implement bitsort (Bitsort)
65 Find the k unique random integers from the range of [0,n-1] (STL, knuth,
swap, floyd) (generate_int_floyd; generate_int_swap; generate_int_knuth)
66. If memory is limited, using k-pass bitsort to sort integers (bitsort_
kpass)
67. Rotation of array (reverse, gcd, blockswap) (rotate; rotate2; rotate3)
68. Permutation of a string (without/with duplicates chars) (String::string_... 阅读全帖 |
|
a**U
发帖数: 115 | 5 来源于面试题目，下面的code可以编译运行成功。关键是我觉得不应该编译运行成功，
请看下面我的comments。请高手指点。
#include
using namespace std;
class A
{
public:
virtual void test(){ cout <<"test A"<
};
class B : public A
{
public:
virtual void test(){ cout <<"test B"<
};
class C : public A
{
int value;
public:
C(){value = 1; }
virtual void test(){ cout <<"test C"<
void accessValue() { cout << "value=" << value << endl; }
void setValue(int value){ this->value... 阅读全帖 |
|
s*******f
发帖数: 1114 | 6 //码遍本版
//need more boundary check and a wrapper function for interview.
namespace maze{
struct Info{
int idx;
};
int di[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
bool InRange(int row, int col, int xx, int yy){
return 0 <= xx && xx < row && 0 <= yy && yy < col;
}
template
void MazeRoute(int m[][col], int row, int x0, int y0, int x1, int y1){
//static Info *info = new Info[row * col];
static vector > path;
... 阅读全帖 |
|
e***n
发帖数: 42 | 7 第一遍扫描array用hashmap存array[i]，
第二遍扫描找出hashmap（target - array[i]）
但是如果遇到重复多次的数（如下例程 x=5）且x+x=target=10， C++ 的hashtable （
map) 就只存第一次出现的x 请问有什么办法解决？
#include |
|
e***n
发帖数: 42 | 8 搞定.用了multimap 和两个iterator.
#include |
|
k***g
发帖数: 166 | 9 弱人路过，用的是楼上说的两个指针往中间走的办法
#include
using namespace std;
void find2sum(int a[], int size, int target)
{
if (size<2)
return;
for (int i=0, j=size-1; i
int sum = a[i]+a[j];
if (sum == target) {
cout<
i++; j--;
} else if (sum > target) {
j--;
} else if (sum < target) {
i++;
}
}
}
int main(int argc, char* argv[])
{
//int a[] = {1, 4, 5, 5, 5, 5, 6, 7, 8... 阅读全帖 |
|
l*********8
发帖数: 4642 | 10 我用c++写了如下代码：
#include
using namespace std;
....
if (i
throw out_of_range;
}
我的程序在Visual c++ 2008 express edition编译是通过的，但在leetcode上面编译
错误。 错误信息是： “ 'out_of_range' was not declared in this scope”
这是怎么回事？ |
|
z**********8
发帖数: 229 | 11 来自主题: JobHunting版 - 汉若塔问题 #include
using namespace std;
#include
#include
class Tower{
private:
int index;//indicate the number of tower
stack one_tower;
public:
Tower(int i=0):index(i){}//constructor
int getindex();
void add(int d);
void moveTopTo(Tower t);
void print();
void moveDisks(int n,Tower Destination,Tower buffer);
};
int Tower::getindex()
{
return index;
}
void Tower::add(int d)
{
if((!one_tower.empty())&&(d>one_tower.top()))
cout<<"... 阅读全帖 |
|
l*****a
发帖数: 14598 | 12 my backup.
#include
using namespace std;
vector find_lis(vector &a)
{
vector b, p(a.size());
int u, v;
if (a.size() < 1) return b;
b.push_back(0);
for (size_t i = 1; i < a.size(); i++) {
if (a[b.back()] < a[i])
{
p[i] = b.back();
b.push_back(i);
continue;
}
for (u = 0, v = b.size()-1; u < v;) {
int c = (u + v) / 2;
... 阅读全帖 |
|
j********e
发帖数: 1192 | 13 我没有说字符集相同就能scramble，字符集相同是必要条件，而不充分。
我的做法是，先找到一个位置i在s1,j在s2使得分割后的4个字符串两两
有相同的字符集（i=j 或者i=N-j)。然后接着对这2对字符串继续做同样
的事情连寻找分割位置。这样递归下去，如果有某对字符串无法找到分割
位置，则表示失败。否则，最后分隔最小的字符串只有一个字符。就可以
判断scramble成功。
问题是，如果有多个分割位置，是否任选一个都可以？如果必须测试每个可能的分割位置，那复杂度就不好说了。
下面是我的简单实现代码，通过了leetcode的online judge (包括judge large)。这段代码中会处理所有可能的分割位置。如果只选第一个可能的分割位置，有一个测试失败了。
#include
#include
#include
#include
using namespace std;
#define BITMAP_LEN 256
bool compare_char_set(const char *s1, con... 阅读全帖 |
|
j********e
发帖数: 1192 | 14 写了个使用O(1)memory, O(logN * logN) (N是tree的size)的程序。
类似于binary search的算法，测试代码也在下面，应该没有大bug。
先获得树的高度h，然后比较h和root->right子树的高度+1,如果相同，
说明树最后一个节点在root->right，否则最后一个节点在root->left的子树。
#include
#include
#include
#include
using namespace std;
class Node {
private:
Node *left;
Node *right;
int value;
public:
Node() {
left = right = NULL;
value = 0;
}
Node(int v) {
left = right = NULL;
value = v;
}
int Height(Node *node) {
int h... 阅读全帖
|
|
s****e
发帖数: 638 | 15 下面这个是O(n) 不知道这样做行不行。
#include
#include
#include
using namespace std;
void shuffle(char* A)
{
int size = strlen(A);
int i=1;
while(i
if (A[i] & 0x80) {
i++;
continue;
}
int j=i;
int j2;
while(true){
if ( j < size/2 ) j2 = j*2;
else j2 = 2*(j-size/2)+1;
if (j2<=i) break;
swap(A[i], A[j2]);
A[j2] |= 0x80;
j=j2;
}
i++;
}
for (int i=0; i
}
int ... 阅读全帖 |
|
b********7
发帖数: 717 | 16 亚马逊人力资源和我联系让我电面
本着考验自己行业水准和玩玩看的心态，接受电面网络开发要求， 要去是不现实的，
地点在西雅图，不可能。
面试是网络开发主要是前台html, css, javascript，电话打来，打开白板开始做题。
亚马逊不象其他公司会问你的经历和爱好,介绍自己啥的，接通后直接技术问题没有一
分钟的缓冲。html问题有啥是doctype, 啥是namespace,啥是form control, 老印口音
重，听不清楚多次要求type. 然后写一段css,提出要求让你修改，然后一系列css问题
。 然后是让你裸写javascript, 给你一个integer array,让你写个类似的，虽然很简
单，大妈我被唬住了有点找不着北，马马虎虎乱写了几行，人家就说算了。
整个过程你基本没时间google作弊， 让你写代码你只能一个一个打出来，不肯能找
code来copy and paste.
见识了非常挑剔，非常不人性的面试。老印威武啊！ |
|
E*******0
发帖数: 465 | 17 // NextPermutation.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include
#include
using namespace std;
#include
bool myfunction (int i,int j) { return (i>j); }
bool nextPermutation(vector &num) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
//If vector size is 1, permutation is its self.
if (1==num.size())
return true;
// rit is the iterator indicates current ite... 阅读全帖 |
|
z**********6
发帖数: 68 | 18 第一题
#include "iostream"
using namespace std;
#define N 10
int num[N] = {1, 2, 3, 9, 8, 9, 9, 9, 9, 9};
void plus_one(int* num, int end_position) {
if (num[end_position] == 9) {
plus_one(num, end_position-1);
cout<<"0";
} else {
num[end_position]++;
for(int i = 0; i <= end_position; ++i)
cout<
}
}
int main() {
plus_one(num,N-1);
}
第二题纯排列组合
C(m-1,m+n-2) |
|
s***5
发帖数: 2136 | 19 参加下面一个challenge，就是给定一系列电话号码，把每个号码对应的所有单词都按
字母顺序打印出来，并用,分隔。具体在这：
http://www.codeeval.com/open_challenges/59/
我下面的code提交就说不能通过所有的test cases，或者有warnings。谁大牛指出问题
所在！包子谢。
#include
#include
#include
#include
using namespace std;
void printWord(vector, string, string, bool&);
int main(int argc, char* argv[])
{
string pad1[10] = {"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs",
"tuv", "wxyz"};
vector pad;
for(int i = 0; i < 10; i+... 阅读全帖 |
|
d****n
发帖数: 1637 | 20 /*
trick is to sort 'num' first
Run Status: Accepted!
Program Runtime: 156 milli secs
Progress: 30/30 test cases passed.
*/
#include
#include
using namespace std ;
class Solution {
public:
int int_cmp(int i, int j){ return (i
vector > permuteUnique(vector &num) {
sort(num.begin(), num.end() ) ;
vector > ret;
do{
ret.push_back( num );
}while(next_permutation(num.begin(), num.end())!=f... 阅读全帖 |
|
d****n
发帖数: 1637 | 21 /*
trick is to sort 'num' first
Run Status: Accepted!
Program Runtime: 156 milli secs
Progress: 30/30 test cases passed.
*/
#include
#include
using namespace std ;
class Solution {
public:
int int_cmp(int i, int j){ return (i
vector > permuteUnique(vector &num) {
sort(num.begin(), num.end() ) ;
vector > ret;
do{
ret.push_back( num );
}while(next_permutation(num.begin(), num.end())!=f... 阅读全帖 |
|
g**********t
发帖数: 475 | 22 Isn't it very slow to swap one array k times? Remember that k could be very
large! I attached my code using a different idea.Its complexity is O(n^2).
#include
#include
#include
#include
using namespace std;
int permutation(int n){
int p = 1;
for(int i = 1; i <= n; i ++){
p *= i;
}
return p;
}
string perSeq(int n, int k){
string output;
bool flag[10];
fill_n(flag, 10, false);
--k;
for (int i = 1; ... 阅读全帖 |
|
t*****h
发帖数: 137 | 23 #include
#include
#include
using namespace std;
bool find_begin_word(string &sentence, vector &dict, vector &
space_pos, int pos)
{
int new_pos = 0;
bool found = false;
for ( int i = 0; i < dict.size() && !found; ++i )
{
int w_len = dict[i].length();
if ( pos + w_len <= sentence.length() && sentence.substr(pos, w_len) ==
dict[i] )
{
new_pos = pos + w_len;
if ( new_pos == sentence.length() )
{
space_pos.push_... 阅读全帖 |
|
t*****h
发帖数: 137 | 24 #include
#include
#include
using namespace std;
bool find_begin_word(string &sentence, vector &dict, vector &
space_pos, int pos)
{
int new_pos = 0;
bool found = false;
for ( int i = 0; i < dict.size() && !found; ++i )
{
int w_len = dict[i].length();
if ( pos + w_len <= sentence.length() && sentence.substr(pos, w_len) ==
dict[i] )
{
new_pos = pos + w_len;
if ( new_pos == sentence.length() )
{
space_pos.push_... 阅读全帖 |
|
b*********n
发帖数: 1258 | 25 #include
#include
using namespace std;
void getQuery(int number, int length)
{
int original_len = length;
while(number)
{
int mod = number%10;
if( mod != 0 ) {
int base = number - number%10;
for (int i=0; i
cout<< "A";
for (int j=0; j0?(int)log10((
float)base):0; ++j) {
... 阅读全帖 |
|
r**u
发帖数: 1567 | 26 我最近被问到的:
1. throw exception from constructor/destructor
2. What is the advantage of using exception over returning an error?
3. Why assignment operator returns a reference to the class?
4. const function
5. singleton, details, which should be private? How to initialize the
instance? How to make it thread-safe?
6. type cast, dynamic_cast, what happens when the base class is/is-not
polymorphism?
7. Derived class want to use base class interface but hides them from
outside (private inheritance?)
8.... 阅读全帖 |
|
n*****g
发帖数: 178 | 27 本帖内容来自于：
发信人: segin (segin), 信区: JobHunting
标 题: 明天ONSITE攒人品,发面试知识点总结!!
发信站: BBS 未名空间站 (Thu Feb 4 13:40:29 2010, 美东)
http://www.mitbbs.com/bbsann2/life.faq/JobHunting/17/D128425435
非常好的总结啊！！！！攒人品再转发一次。
C: pointer, call by value/pointer, return the pointer of a local variable,
string manipulations, source code of some important C string subroutines
(strcpy, strtok, etc), itoa, atoi, static variable and fuction, name
mangling,
memory allocation
http://www.eskimo.com/~scs/C-faq/faq.html
C++: name... 阅读全帖 |
|
y********a
发帖数: 18 | 28 #include
#include
#include
#include
using namespace std;
template
void printvec( vector vec ) {
cout << "begin--------------------" << endl;
for ( vector::const_iterator it = vec.begin(); it != vec.end();
it++ ) {
cout << setw(10) << *it << endl;
}
cout << "----------------------end" << endl;
}
int main() {
vector vec1;
for ( int ii = 0; ii < 10; ii++ ) {
vec1.push_back( ii );
... 阅读全帖 |
|
i***h
发帖数: 12655 | 29 用C++ STL, 还好了
下面的代码少了最后一步, 也没有sanity check
但也不难
当然效率不是最好的
#include
#include
#include
#include
using namespace std;
bool
compstr(char* a, char* b)
{
return strcmp(a,b)<0;
}
void
suffixArray(char *a, char *b)
{
char *m = (a>b)? a-1 : b-1;
char* suffix[strlen(a)+strlen(b)];
for(int i = 0; i
suffix[i] = a+i;
}
for(int i=0; i
suffix[strlen(a)+i] = b+i;
}
sort(suffix, suffix+strlen(a)+strlen(b), comp... 阅读全帖 |
|
g**u
发帖数: 504 | 30 看我的这个行不行？
#include
#include
using namespace std;
int maxShiftedSortArray(vector& array){
int n=array.size();
if(n==1)
return array[0];
int l=0;
int r=n-1;
int m;
while(l
m=(r+l)/2;
if(array[m]>=array[l]){
l=m;
}else{
r=m-1;
}
}
return max(array[l],array[r]);
} |
|
a******a
发帖数: 2646 | 31 来自主题: JobHunting版 - G电面一题 请指教。我的解答
#include "stdafx.h"
#include
using namespace std;
void transform(char* ,char* ,int ,int,int );
int _tmain(int argc, _TCHAR* argv[])
{
char b[100];
char a[100];
cin.getline(a,100);
int length;
for( length=0;length<100;length++)
if(a[length]=='\0')
break;
transform( a, b, length,0,0);
return 0;
}
void transform(char* a,char* b,int length,int loca,int locb)
{
char x,y[2];
x=*(a+loca);
*(b+locb)=static_cast(atoi(&x)+97... 阅读全帖 |
|
d****n
发帖数: 1637 | 32 //in windows
#include
#include
using namespace std;
class A{
public :
int a;
int b;
};
int main()
{
cout<<&main<
int before=4;
cout<<"STACK &before="<<&before<
A objA;
void *p=malloc(1000);
cout<<"HEAP *p="<
cout<<"&objA.a"<<&(objA.a)<
cout<<"&objA.b"<<&(objA.b)<
cout<<"objA="<<&objA<
int after=4;
cout<<"STACK &after="<<&after<
return 0;
}
//output from windows wi... 阅读全帖 |
|
s***0
发帖数: 117 | 33 #include
#include
#include
#include
#include
using namespace std;
class ProcessParen
{
public:
ProcessParen(){};
void processString(string& inString)
{
stack charStack;
for (int i = 0; i< inString.length(); ++i)
{
if(inString[i] == '{')
{
mResult += "{";
charStack.push('{');
}
if(inString[i] == '}')
{
... 阅读全帖 |
|
y****e
发帖数: 20 | 34 unordered_map does not keep the original order.
Try this code on your machine and see the output.
#include
#include
using namespace std;
int main() {
unordered_map um;
for (int i = 100; i >= 0; i--) {
um.insert(make_pair(i, i));
}
for (unordered_map::iterator it = um.begin(); it != um.end(); it
++)
cout << it->first << " ";
cout << endl;
}
comparison |
|
l********t
发帖数: 878 | 35 Judge small 全对
Judge large, 一共92个test case,有90个是对滴，
其中一个错误的是这个test case
{9,6,-3,#,#,-6,2,#,#,2,#,-6,-6,-6}
还有一个太长，不写了。
我自己编译运行结果是16，也是正确答案。上OJ非说我的结果是15...
leetcode，或者哪位大牛给看看？谢谢啊！
/**
* Definition for binary tree */
#include
#include
#include
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
int maxValue;
int maxPathSum(TreeNode... 阅读全帖 |
|
d******i
发帖数: 76 | 36 谢谢@wwwyhx大牛贡献的题。看了帖子里面的回复后，有了些思路，虽然对于牛人们，
这道题很简单，对于还是菜鸟的我还是很难的，发个帖子，供大家讨论，希望最
终得出正确的答案吧。
“我面的时候有一简单题一定要O(n), 找树的unival个数(就是这个节点开始所有子树都
一样的节点数) ”
题的意思是，找到这样的子树，满足子树中所有节点的值相等。计算满足此条件的子树
中节点的总个数。（希望没有理解错。）
例子1：
1
结果为 1
例子2：
1
1 1
结果为 3
例子3：
1
2 3
结果为2（2, 3）
例子4：
1
2 3
2
结果为：3 ({2,2}, {3})
例子 5：
1
2 3
2
4
结果为： 2 （4，3）；
下面是C++代码，大家指正
---------------更新：不需要看我写的了，直接看楼下的解法吧，哈哈。-----------
----
#include
#include
using namespace std;
struct TreeN... 阅读全帖 |
|
l*******b
发帖数: 2586 | 37 测了下，貌似没问题呀，感觉和merge interval哪个题一样
#include
#include
#include
using namespace std;
struct Interval {
int a;
int b;
bool cf;
Interval() : a(0), b(0), cf(false) {}
Interval(int start, int end) : a(start), b(end), cf(false) {}
};
bool compare(const Interval &s, const Interval &t) {
return s.a < t.a;
}
class Play {
public:
void setflag(vector &list) {
/* same idea as merge intervals, when intervals merge, they conflict
*/
... 阅读全帖 |
|
r**d
发帖数: 90 | 38 来自主题: JobHunting版 - 贡献一道题 using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;
namespace ConsoleApplication1
{
class Program
{
static private bool isWord(string s)
{
switch (s)
{
case "this":
case "is":
case "a":
case "all":
case "some":
case "allsome":
return true;
}
return fal... 阅读全帖 |
|
T******7
发帖数: 1419 | 39 //==========================================================================
==
// Binary Tree Maximum Path Sum
// Given a binary tree, find the maximum path sum.
//
// The path may start and end at any node in the tree.
//
// For example:
// Given the below binary tree,
//
// " 1 "
// " / \ "
// " 2 3 "
//
// Return 6.
//
//==========================================================================
==
#include
using namespace std;
/**
* Definition for binary t... 阅读全帖 |
|
l*******b
发帖数: 2586 | 40 #include
using namespace std;
struct IntNode {
int a;
int b;
IntNode *next;
IntNode(int low, int high) : a(low), b(high), next(NULL) {}
};
struct HeadsNode {
IntNode *list;
HeadsNode *next;
HeadsNode() : next(NULL) {}
};
class MergeInt {
public:
void merger(HeadsNode *h, HeadsNode *t) {
if(h == t) return;
HeadsNode *mid = middle(h,t);
merger(h, mid);
merger(mid->next, t);
h->list = mergeTwoList(h->list, (mid->next... 阅读全帖 |
|
l*******b
发帖数: 2586 | 41 C++写了个。。。大伙看吧，这里用的ruby的语法挺好懂呀
#include
#include
#include |
|
l*******b
发帖数: 2586 | 42 经过很久挣扎终于调成功了。。。test case好诡异
#include
using namespace std;
class Play {
public:
bool isNumber(const char *s) {
int mat[11][7] = {0 ,0 ,0 ,0 ,0 ,0 ,0, // false
0 ,2 ,3 ,0 ,1 ,4 ,0, // 1
0 ,2 ,5 ,6 ,9 ,0 ,10,// 2
0 ,5 ,0 ,0 ,0 ,0 ,0, // 3
0 ,2 ,3 ,0 ,0 ,0 ,0, // 4
0 ,5 ,0 ,6 ,9 ,0 ,10,// 5
0 ,7 ,0 ,0 ,0 ,8 ,0, // 6
... 阅读全帖 |
|
l*******b
发帖数: 2586 | 43 经过很久挣扎终于调成功了。。。test case好诡异
#include
using namespace std;
class Play {
public:
bool isNumber(const char *s) {
int mat[11][7] = {0 ,0 ,0 ,0 ,0 ,0 ,0, // false
0 ,2 ,3 ,0 ,1 ,4 ,0, // 1
0 ,2 ,5 ,6 ,9 ,0 ,10,// 2
0 ,5 ,0 ,0 ,0 ,0 ,0, // 3
0 ,2 ,3 ,0 ,0 ,0 ,0, // 4
0 ,5 ,0 ,6 ,9 ,0 ,10,// 5
0 ,7 ,0 ,0 ,0 ,8 ,0, // 6
... 阅读全帖 |
|
a*********8
发帖数: 17 | 44 #include
using namespace std;
class Solution {
public:
bool isSymmetric(TreeNode *root) {
if(NULL == root) return true;
queue q;
q.push(root->left);
q.push(root->right);
while(!q.empty()) {
TreeNode *left = q.front();
q.pop();
TreeNode *right = q.front();
q.pop();
if(NULL == left && NULL == right)
continue;
if(left && right) {
if(l... 阅读全帖 |
|
r*c
发帖数: 167 | 45 二爷，坑爹算法来也。用状态机搞砸一切面面！哈哈
#include
#include
#include
using namespace std;
class Numericality;
void TestNumericality();
void TestNumericalityHelper(const string& str, const bool expected,
Numericality& nc);
class Numericality
{
public:
struct State
{
const string _str;
int _index;
State() {}
State(string s, int i) : _str(s), _index(i){}
virtual State* MoveNext(){
if(_str.empty() || _index < 0 || _index >= _str... 阅读全帖 |
|
d**********x
发帖数: 4083 | 46 实际上是O(logn)的空间，但是既然长度为2^32的数列可以借助一个int来作为辅助空间
，这点overhead基本可以忽略不计了。欢迎找bug：
#include
#include
#include
using namespace std;
#include
static int get_index(int i) {
if (i == 0) {
return 1;
}
return (1 << i) + 1;
}
void rearrange(vector& vec) {
int bitmap = 0; //"O(1)" space for length < (1 << 32)
int k = vec.size() / 2;
int n = vec.size();
for (int i = 0; get_index(i) < k; ++i) {
int cur = get_index(i);
... 阅读全帖 |
|
p****e
发帖数: 3548 | 47 试了一下，合格不
// Type your C++ code and click the "Run Code" button!
// Your code output will be shown on the left.
// Click on the "Show input" button to enter input data to be read (from
stdin).
#include
using namespace std;
char getnonduplicate(string s)
{
int size = s.size();
if(size == 0) return '\0';
vector cc;
int lastnonduplicate = 0;
for(int i = 0; i < size; i++)
{
bool duplicate = false;
for(int j=0; j < cc.size(); j++)
{
... 阅读全帖 |
|
h********g
发帖数: 496 | 48 如下。本来想算算尾递归和递归的性能区别。结果发现iterative的算法都不行。
每步的结果都%777，就是为了防止结果溢出。
#include
using namespace std;
int factor(int n){
if(n==0) return 1;
int acc=1;
for(int i=n; i>0; i--)
acc=acc*i%777;
return acc;
}
int factor_recursive(int n){
if(n==1 || n==0) return 1;
return factor_recursive(n-1)*n%777;
}
//g++ doesn't optimize for tail-recursion. The following function stops at
Factor(37).
int factor_tailrecursive(int n, int acc){
if(n==1 || n==0) return acc;
re... 阅读全帖 |
|
d**********x
发帖数: 4083 | 49 应该没问题，和coldknight的程序在2-10000之内做了对比，结果完全一致。他的
nMaxStep我设置为了2 * target，不知道会不会引起问题。
在纸面上也做了不太严格的证明。。这样复杂度就是O(logn)。
对比程序：（前半部分还是coldknight的）
#include
#include
#include
using namespace std;
vector getJumpSteps(int nCur, int nMaxStep)
{
vector vec;
if (nCur <= 0 || nMaxStep < nCur)
return vec;
int flg = 1;
while (nCur + flg <= nMaxStep)
{
vec.push_back(nCur + flg);
flg = (flg << 1);
}
flg = 1;
while (nCur - ... 阅读全帖 |
|
d**********x
发帖数: 4083 | 50 这个优化之后用的时间大概是顶楼解法的一半(leetcode, 1020ms vs 530ms)
为了清晰起见我就没用bitarray，这个解法的额外空间还是比较多。。
#include
#include
using namespace std;
class Solution {
public:
int totalNQueens(int n) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
n_ = n;
principal_diagonal_.resize(2 * n - 1);
principal_diagonal_.assign(2 * n - 1, 0);
minor_diagonal_.resize(2 * n - 1);
minor_diagonal_.assign(2 * n - 1, 0);
... 阅读全帖 |
|
