l****i
发帖数: 51 | 1 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;
} |
|
i**********e
发帖数: 1145 | 2 我刚在linux上运行了，没有这方面的问题，不过我的程序是C++ 不是Java。
我测试了你的算法，返回结果都算满意，而且运行越多次，返回的结果越接近理想的 p
值。
你的算法不单简洁，而且复杂度是最优的，递归是 average 两次就返回答案。
expected # calls = 1*0.5 + 2*0.5^2 + 3*0.5^3 + ...
= Summation( k * 0.5^k ), k = 1 .. n
= 2 - (n+2)/2^n
When n = infinity,
expected # calls = 2
贴下code方便大家做测试：
#include
#include
#include
#include
using namespace std;
bool rand2() {
return (rand() % 2 == 0);
}
unsigned long long totalCalls = 0;
bool Prob2(double p, bool expected = tru... 阅读全帖 |
|
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
... 阅读全帖 |
|
S******t
发帖数: 151 | 4 我大概写一个吧，没编译，不知道靠谱不
#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
... 阅读全帖 |
|
l*********8
发帖数: 4642 | 5 I modified the program.
Now the major function should be simple enough (although the whole
program is not that short).
class Solution {
public:
bool isMatch(const char *s, const char *p) {
if(!s || !p )
return false;
const char * nextStar = strchr(p, '*');
if ( !nextStar)
return strCmp(s, p);
if (!strCmpN(s, p, nextStar-p) )
return false;
do {
s += nextStar-p;
p = nextStar + 1;
n... 阅读全帖 |
|
s******n
发帖数: 3946 | 6 递归非DP做法
bool isScramble(char* str1, char* str2, int length) {
if (length==1) return *str1 == *str2;
for (int i=1; i
if (isScramble(str1, str2+(length-i), i)
&& isScramble(str1+i, str2, length-i))
return true;
if (isScramble(str1, str2, i)
&& isScramble(str1+i, str2+i, length-i))
return true;
}
return false;
}
递归DP做法
class Solution {
char* str1;
char* str2;
int m;
int m2;
int m3;
int* DP;
#define dp(i,j,k) DP[m2 * (i) + m * (j) + (k) ]
public:
Solution(cha... 阅读全帖 |
|
i**********e
发帖数: 1145 | 7 顶！
这个状态只需用 O(N^3) 的空间来保存就行，复杂度是 O(N^4)。
假设 (i,j) 分别为 s1 和 s2 的开始 index，n 为子串的长度，k 是把字串分成两个
子串的 pivot point (k = 1 ... n-1)：
F(i, j, n) = F(i+n-k, j, k) && F(i, j+k, n-k) ||
F(i, j, n-k) && F(i+n-k, j+n-k, k)
base case 为 F(i, j, 1) == true, iff s1[i] == s2[j]
然后 bottom-up 建立表，从所有 F(i, j, 2) --> F(i, j, len)，len = s1 长度。
那么答案就是 F(0, 0, len).
以下是非递归的 bottom-up DP 代码，空间复杂度 O(N^3)，时间复杂度 O(N^4).
bool isValid(string s1, string s2) {
int len = s1.length();
bool dp[64][64][64] = {f... 阅读全帖 |
|
s***5
发帖数: 2136 | 8 参加下面一个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+... 阅读全帖 |
|
a*******y
发帖数: 1040 | 9 这个不就是hash这个index就行了吗？
bool FindCycle(int a[], int n)
{
std::map indexmap;
map::iterator it;
for (int i = 0; i < n;i++)
{
indexmap[i] = false;
}
indexmap[0] = true;
for (int i = 0; i < n; i++)
{
if( indexmap[a[i]])
return true;
else
indexmap[a[i]] = true;
}
return false;
} |
|
a*******y
发帖数: 1040 | 10 我就在想有没有更好的办法出了用sufix tree
写了个傻的，不过觉得有更好的
bool strMatch(char* str, int start, int length)
{
for (int i = 0; i
{
if (str[start+i] != str[start-length+i])
return false;
}
return true;
}
bool ReturnConsecutiveString(char* str, int n, int& startindex, int&
endindex)
{
int i = 1, j,k;
bool bfail = false;
while (i < n)
{
for (j = 1; (i+j < n) && (i-j-1 >=0);j++)
{
for (k = 0; k<=j;k++)
{
... 阅读全帖 |
|
D**f
发帖数: 439 | 11 看看我的解答吧。他说有什么输入我不能处理，我没看出来，只要输入是有效的digit
和有限范围的count，应该没问题。
class Iterator
{
public:
Iterator(const unordered_map& m);
int next();
bool hasNext();
private:
unordered_map mp;
unordered_map::const_iterator it;
int count;
};
Iterator::Iterator(const unordered_map& m):mp(m),count(0)
{
it=mp.begin();
}
int Iterator::next()
{
if(it->second > count)
{
count++;
return it->first;
}
else
{
++it;... 阅读全帖 |
|
j********x
发帖数: 2330 | 12 写了一个小时，没考虑特别的corner case，O(num of intervals of "except")，用了
上面提到的binary search：
#include
#include
#include
#include
#include
struct compareable_interval {
int start;
int end;
int real_start;
int real_end;
compareable_interval(int lhs, int rhs) : start(lhs), end(rhs), real_
start(lhs), real_end(rhs) {
}
compareable_interval(int l, int r, int rl, int rr) : start(l), end(r),
real_start(rl), real_end(rr) {
}
b... 阅读全帖 |
|
j********x
发帖数: 2330 | 13 写了一个小时，没考虑特别的corner case，O(num of intervals of "except")，用了
上面提到的binary search：
#include
#include
#include
#include
#include
struct compareable_interval {
int start;
int end;
int real_start;
int real_end;
compareable_interval(int lhs, int rhs) : start(lhs), end(rhs), real_
start(lhs), real_end(rhs) {
}
compareable_interval(int l, int r, int rl, int rr) : start(l), end(r),
real_start(rl), real_end(rr) {
}
b... 阅读全帖 |
|
r*****e
发帖数: 146 | 14 How about pre-order visit the tree and keep a record for those already
visited, if current node is in the table, it means it is already visited,
therefore, there is a loop.
here, we can use stl::map to simulate hash table.
//cpp code
bool is_loop(Node* node, map& dict){
if(!node)
return false;
if(dict.find(node) == dict.end()){
dict[node] = false;
bool left = is_loop(node->left, dict);
if(left)
return true;
return is_loop(no... 阅读全帖 |
|
r*****e
发帖数: 146 | 15 How about pre-order visit the tree and keep a record for those already
visited, if current node is in the table, it means it is already visited,
therefore, there is a loop.
here, we can use stl::map to simulate hash table.
//cpp code
bool is_loop(Node* node, map& dict){
if(!node)
return false;
if(dict.find(node) == dict.end()){
dict[node] = false;
bool left = is_loop(node->left, dict);
if(left)
return true;
return is_loop(no... 阅读全帖 |
|
g***j
发帖数: 1275 | 16 哪位大牛帮我看看这个代码，为什么leetcode online judge的small的都过了，large
的就过不了了？
test case 如下，说Time Limit Error, 是不是递归的算法太烂了？ 不至于这个都处
理不了吧？
"
bbbbbabbbbabaababaaaabbababbaaabbabbaaabaaaaababbbababbbbbabbbbababbabaababa
bbbaabababababbbaaababaa",
"
babaaaabbababbbabbbbaabaabbaabbbbaabaaabaababaaaabaaabbaaabaaaabaabaabbbbbbb
bbbbabaaabbababbabbabaab",
"
babbbabbbaaabbababbbbababaabbabaabaaabbbbabbbaaabbbaaaaabbbbaabbaaabababbaaa
aaabababbababaababbababbbababbbbaaaabaabbabbaaaaabbabbaaaabbbaabaaabaababaab
abbaaabbbbb... 阅读全帖 |
|
l***i
发帖数: 1309 | 17 struct Node {
Node *left, *right;
int val;
};
// returns true if subtree at root is BST
// the pair is minval and maxval of this subtree
typedef pair pii;
pair isBST(Node *root)
{
if (root == NULL) return make_pair(true, pii(0,0));
if (root->left == NULL && root->right == NULL)
return make_pair(true, pii(root->val, root->val));
pair p1, p2;
bool b1, b2, ans;
int s1, s2, t1, t2, vmin, vmax;
p1 = isBST(root->left);
p2 = isBST(root->righ... 阅读全帖 |
|
h****n
发帖数: 1093 | 18 和值有关系么，理解错了，以为是所有子树一样的节点，不过道理都一样
代码如下
vector GetAllUnivalNodes(TreeNode * root)
{
vector res;
helper(root, res);
return res;
}
bool helper(TreeNode * root, vector & res)
{
if(root==NULL)
return true;
bool leftRes = helper(root->left, res);
bool rightRes = helper(root->left, res);
if(!leftRes||!rightRes)
return false;
if(root->left&&root->val!=root->left->val)
return false;
if(root->right&&root->val!=r... 阅读全帖 |
|
h****n
发帖数: 1093 | 19 试过了二爷的C++版本，还是超时了，谁贴个能通过OJ大test case的版本
bool isMatch(const char *s, const char *p)
{
int i,j;
int n=0,m=0;
const char* tmp;
tmp = s;
while(*tmp++)n++;
tmp = p;
while(*tmp++)m++;
vector > dp(2,vector(n+1, false));
dp[m%2][n] = true;
for(i=m-1;i>=0;i--)
{
dp[i%2].assign(n+1, false);
dp[i%2][n] = (p[i]=='*'&&dp[(i+1)%2][n]);
for(j=n-1;j>=0;j--)
if(p[i]=='*')
dp[i%2][j] = dp[(i+... 阅读全帖 |
|
w****x
发帖数: 2483 | 20
struct EVENT
{
int nStart;
int nEnd;
bool bFlg;
EVENT(int a, int b) : nStart(a), nEnd(b) { bFlg = false; }
};
struct ENDPOINT
{
int nIndex;
bool bStart;
int nVal;
};
bool lessThan(const ENDPOINT& ed1, const ENDPOINT& ed2)
{
return ed1.nVal < ed2.nVal;
}
void setFlg(EVENT events[], int n)
{
if (events == NULL || n <= 0)
return;
ENDPOINT* ends = new ENDPOINT[n*2];
for (int i = 0; i < n; i++)
{
ends[2*i].bStart = true;
ends[2*... 阅读全帖 |
|
s*****n
发帖数: 994 | 21 用了unordered_map来check第三个数是否存在，如果unordered_map是O（1），那整个
算法复杂度是O（n＊n）啊，为什么过不了large test？
class Solution {
public:
vector > threeSum(vector &num) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
sort(num.begin(),num.end());
unordered_map m;
for (size_t i=0; i
m.insert (make_pair(num[i],true));
}
vector > solution_set;
for (... 阅读全帖 |
|
w****x
发帖数: 2483 | 22
真是..
bool isNull = (bool)*p;
p += sizeof(bool);
String strContent(p);
p += str.length()+1;
这样一个节点就解析出来了 |
|
w****x
发帖数: 2483 | 23
我就想问问那个初始化怎么方便的处理，二爷看看我的code吧
class CIterIter
{
public:
CIterIter(vector>& vecvec) : m_vecvec(vecvec), m_ni(0), m_nj(0),
bInited(false)
{}
bool hasNext()
{
if (!m_vecvec.empty() && !m_vecvec[0].empty())
return true;
int i,j;
return prob(i,j);
}
int getVal() { return m_vecvec[m_ni][m_nj]; }
void next()
{
if (!bInited)
{
bInited = true;
if (!m_vecvec.empty() && !m_vecvec[0].empty())
return;
}
prob(m_ni, m_nj);
}
private:
bool prob(in... 阅读全帖 |
|
c********t
发帖数: 5706 | 24 好像弄明白你的题意了。虽然我不懂c++,不过我觉得你的问题是，findLongestWord_
helper又想split to several words才能true, 又想如果剩一个词也要true
看看改成下面的行不
bool findLongestWord_helper(string &s, map &hm，bool hasSplit)
{
for(int i = 1; i <= s.size(); i++)
{
string sub_f(s, 0, i);
if(hm[sub_f])
{
if(i==s.size() ) return hasSplit;
string sub_b(s, i, s.size()-i);
if(findLongestWord_helper(sub_b, hm, true))
return true;
}
}
return... 阅读全帖 |
|
U***5
发帖数: 2796 | 25 一边看球一边草草写了写，corner case没时间搞了，只写了头2个search的情况：
小于key的最大值 - op_max_less
大于key的最小值 - op_min_great
其他几种情况自己加Functor就是了。感觉myfind return那里比较繁琐，应该有更好办
法整理一下。
写得不好，轻拍。
//Compare.h
enum Op_code
{
op_max_less = 0,
op_min_great
};
class Less
{
public:
Less(int v): val_(v), op_(op_max_less){}
bool operator()(int v1)
{
return v1 < val_;
}
const Op_code op_;
private:
int val_;
};
class Greater
{
public:
Greater(int v): val_(v), op_(op_min_great){}
bool opera... 阅读全帖 |
|
w****x
发帖数: 2483 | 26 做了一个QuadTree
struct PT
{
int x;
int y;
};
struct REC
{
POINT topLft;
POINT bottomRgt;
REC(int a, int b, int c, int d)
{
topLft.x = a;
topLft.y = b;
bottomRgt.x = c;
bottomRgt.y = d;
}
bool inRect(PT pt)
{
return pt.x >= topLft.x && pt.x <= bottomRgt.x
&& pt.y >= topLft.y && pt.y <= bottomRgt.y;
}
bool intersect(REC rect)
{
return min(bottomRgt.x, rect.bottomRgt.x) >= max(topLft.x, rect.
to... 阅读全帖 |
|
p****e
发帖数: 3548 | 27 发个不用'a'-'z'的方法，第一题
class Solution {
public:
bool diff1(string &s1, string &s2)
{
int diff = 0;
//if(s1.size() != s2.size()) return false;
for(int i = 0; i < s1.size(); ++i)
{
if(s1[i] != s2[i])
{
if(diff) return false;
++diff;
}
}
if(diff) return true;
return false;
}
int ladderLength(string start, string end, unordered_set &dict) {
// St... 阅读全帖 |
|
p****e
发帖数: 3548 | 28 发个不用'a'-'z'的方法，第一题
class Solution {
public:
bool diff1(string &s1, string &s2)
{
int diff = 0;
//if(s1.size() != s2.size()) return false;
for(int i = 0; i < s1.size(); ++i)
{
if(s1[i] != s2[i])
{
if(diff) return false;
++diff;
}
}
if(diff) return true;
return false;
}
int ladderLength(string start, string end, unordered_set &dict) {
// St... 阅读全帖 |
|
B********t
发帖数: 147 | 29 第一题写了一个很蠢的，不要笑我。。。。。。测了几个case好像是work的。。。。。
O(n^2)
void DFS(vector &matrix, vector > &visited, int x, int
y, int size)
{
visited[x][y] = true;
matrix[x][y] = '#';
if(y-1 >= 0 && matrix[x][y-1] == 'O' && !visited[x][y-1])
DFS(matrix, visited, x, y-1, size);
if(x+1 < size && matrix[x+1][y] == 'O' && !visited[x+1][y])
DFS(matrix, visited, x+1, y, size);
if(y+1 < size && matrix[x][y+1] == 'O' && !visited[x][y+1])
DFS(matrix, visited, x... 阅读全帖 |
|
B********t
发帖数: 147 | 30 我写了一个，不过第一个判断回文的地方我不知道怎么用dp，还是说没法用？不过不改
变总的时间复杂度
class Solution {
public:
bool isPalindrome(string s)
{
int start = 0, end = s.size() - 1;
while(start < end)
if(s[start++] != s[end--])
return false;
return true;
}
int minCut(string s) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector dp(s.size(), INT_MAX);
vector> isValid(s.size(), vector<... 阅读全帖 |
|
B********t
发帖数: 147 | 31 我写了一个，不过第一个判断回文的地方我不知道怎么用dp，还是说没法用？不过不改
变总的时间复杂度
class Solution {
public:
bool isPalindrome(string s)
{
int start = 0, end = s.size() - 1;
while(start < end)
if(s[start++] != s[end--])
return false;
return true;
}
int minCut(string s) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector dp(s.size(), INT_MAX);
vector> isValid(s.size(), vector<... 阅读全帖 |
|
d**********x
发帖数: 4083 | 32 那题目貌似就没卡复杂度。。。枉我昨天下班后还捏着鼻子写了个treap。。。结果证
明是输出格式错了，只过了两三个case的可以考虑检查一下输出格式
思路大致就是用order statistics tree。每次查询都是O(logn)。手写最大问题在于没
法定制容器的行为。。。
好吧，然后想了一下，如果用两个heap加一个map的话也是可以的，因为只是查询
median，没有要求随机查询kth元素，所以还是写复杂了
附上代码，treap是个随机平衡树，可以拿去用。
#include
#include
#include
#include
using namespace std;
template
class Treap {
public:
class Node {
public:
Node(const T& value)
: value_(value),
left_(NULL),
right_(NULL),... 阅读全帖 |
|
j*****y
发帖数: 1071 | 33 bless
一条龙是什么阿 ? tic tac toe ?
double atof(char *s)
{
int i = 0;
while(s[i] && s[i] == ' ')
{
++i;
}
double num = 0;
bool flag_signal = false;
bool negative = false;
bool flag_dot = false;
vector afterDot;
while(s[i])
{
if(s[i] == '+' || s[i] == '-')
{
if(flag_dot)
{
break;
... 阅读全帖 |
|
n*****g
发帖数: 16 | 34 My version for C#.
static bool IsValidExpression(string expression)
{
Stack stackOperator = new Stack();
Stack stackOperand = new Stack();
int length = expression.Length;
int i;
char opr;
for (i = 0; i < length; ++i)
{
if (expression[i] == '(' || expression[i] == '+' ||
expression[i] == '-' || expression[i] == '*' || expression[i] == '/')
{
... 阅读全帖 |
|
n*****g
发帖数: 16 | 35 My version for C#.
static bool IsValidExpression(string expression)
{
Stack stackOperator = new Stack();
Stack stackOperand = new Stack();
int length = expression.Length;
int i;
char opr;
for (i = 0; i < length; ++i)
{
if (expression[i] == '(' || expression[i] == '+' ||
expression[i] == '-' || expression[i] == '*' || expression[i] == '/')
{
... 阅读全帖 |
|
M**A
发帖数: 78 | 36 最差情况:
假设 adv <=24000, 抽中概率x=1-(1-20/24)(1-65/100)>94%
理想情况:
struct profile {
char* name;
char* employer;
char* nationality;
bool isAdv;
bool approval;
};
bool PermitLottery(profile & applicant) {
if (!strcmp(applicant.nationality,"cn")) return true;
else {
......
}
} |
|
d******k
发帖数: 4295 | 37 写程序不是给自己看的，要考虑以后可能会有无数次修改和其他程序员接手。
举个例子，
某个程序里的flag由A,B,C,D,E,.....H...来决定（可以是变量，表达式或者函数）
所谓的简洁技巧写法(复杂的注释放到最前面)
/*
comments
comments
.....
.....
comments
*/
bool flag = ((A<0) & !B | C) | （(D>E) &
((A==0) &... ) |
((A==1) ...） &
((A==2) ...） &
((A==3) ...） &
(H>0?(F>0):(J<0))
所谓的复杂函数写法（注释在每一行）
bool GetFlag(A,B,C,....H)
{
bool rtn = true;
if (A<0)//comments
{
if (!B)
if (C)
}else//comments
{
switch(A)
case 0: //comments
... 阅读全帖 |
|
r*c
发帖数: 167 | 38 第一题要用binary search？
试写了一下，借用二爷的原代码
#include "stdafx.h" //cause I am using VC++
#include
#include
#include
using namespace std;
class Solution{
public:
Solution(unordered_mapmap){
_map = map;
_size = _map.size();
unordered_map::iterator it = _map.begin();
while(it != _map.end())
_vec.push_back(it++->first);
}
bool Prob() //borrowed from LeetCode
{
return r... 阅读全帖 |
|
s********u
发帖数: 1109 | 39 class Spot{
private:
int length;
int width;
bool state;
int index;
int lvl;
public:
bool isFree();
}
class Vehicle{
private:
int length;
int width;
bool parked;
public:
int getlength();
int getWidth();
int numSpots(Spot* s); //return how many such spots this vehicle
need
void parkVehicle( Spot* s);//park starting from spot S;
void removeVehic... 阅读全帖 |
|
s*******s
发帖数: 1031 | 40 我的代码，用递归做。不一定对 。。
// n1n2n3n4
n1
/
n2
/ \
n3 n4
string getNextTag();
bool isTagStartingNode(string tag);
bool isTagEndNode(string tag);
bool isTagString(string tag)
struct TreeNode {
string value;
TreeNode *left;
TreeNode *right;
TreeNode(string v) : value(v), left(NULL), right(NULL) {}
};
TreeNode *parse(string startTag) {
// no more nodes left
if(str.size() == 0)
retu... 阅读全帖 |
|
D**********d
发帖数: 849 | 41 密码锁问题我要是在 G 家 onsite 前看过你的帖子就好了，
当时就想着找数学规律，没有想过用这种 “brute force”.
以下是我回来后写出的代码:
bool DFS(vector & IsVisited, vector & Result, int CurrNum){
if(Result.size() == 10003) return true;
int pre = (CurrNum % 10000) * 10;
for(int i = 0; i < 9; ++i){
int NextNum = pre + i;
if(IsVisited[NextNum] == true) continue;
Result.push_back('0'+i);
IsVisited[NextNum] = true;
if(DFS(IsVisited,Result,NextNum)) return ... 阅读全帖 |
|
s*******s
发帖数: 1031 | 42 我的C++代码：
class Solution {
public:
bool isMatch(const char *s, const char *p) {
int ptnCnt = 0;
const char *pp = p;
while(pp && (*pp)) {
if(*pp != '*')
++ptnCnt;
++pp;
}
int strCnt = 0;
if(s)
strCnt = strlen(s);
if(strCnt < ptnCnt)
return false;
if(!strCnt)
return !ptnCnt;
if(!ptnCnt)
return strlen(p);
... 阅读全帖 |
|
s*w
发帖数: 729 | 43 要有人觉得有所帮助，给发个包子
【 以下文字转载自 Programming 讨论区 】
发信人: saw (句子熊), 信区: Programming
标 题: Re: 一道count frequency of all words的面试题 (转载)
发信站: BBS 未名空间站 (Mon Sep 23 00:28:12 2013, 美东)
又琢磨了两天，看了不少相关东西，终于搞定了，觉得自己对这个多线程的理解加强了
很多。思考比单纯的看人说原理更刻骨铭心。
这个问题我设计的用一个 producer 多个 consumer 的架构，上个版本的是两头用
condition_variable, 一个通知 producer 有空间了开始干活生产，另一个通知
consumer 有库存了开始消费。参见上篇里面的 wait 和 notify_all,notify_one 语
句。 这个思路对于单 producer 单 consumer 没问题，可是不适用于 多 consumer.
因为所有的 consumer 可能同时睡觉（没空存），同时醒来（有库存）,结果只有一个
能抢占mutex(拿到库存)，... 阅读全帖 |
|
l*****0
发帖数: 13 | 44 class Solution {
public:
bool getSum(vector &ratings, int &sum)
{
bool isReverse = false;
int n = ratings.size();
int* candy = new int[n];
memset(candy, 0, n*sizeof(int));
candy[0] = 1;
for (int i=1; i
{
if (ratings[i] > ratings[i-1])
candy[i] = candy[i-1] + 1;
else if (ratings[i] == ratings[i-1])
candy[i] = candy[i-1];
e... 阅读全帖 |
|
l*****0
发帖数: 13 | 45 class Solution {
public:
bool getSum(vector &ratings, int &sum)
{
bool isReverse = false;
int n = ratings.size();
int* candy = new int[n];
memset(candy, 0, n*sizeof(int));
candy[0] = 1;
for (int i=1; i
{
if (ratings[i] > ratings[i-1])
candy[i] = candy[i-1] + 1;
else if (ratings[i] == ratings[i-1])
candy[i] = candy[i-1];
e... 阅读全帖 |
|
y***n
发帖数: 1594 | 46 LeetCode says that I am failing the test case
Input: {1,2}, 0
Output: true
Expected: false
However, I can pass it with a console assert.
bool getPathSum(TreeNode *root, int pathSum, int sum){
pathSum +=root->val;
if(NULL==root->left && NULL==root->right){//get to the leaf
return pathSum==sum;
}
bool left, right;
if(root->left){
left=getPathSum(root->left, pathSum, sum);
}
if(root->right){
... 阅读全帖 |
|
a******e
发帖数: 710 | 47 题目如下：
Given a 2D array of black and white entries representing a maze with
designated entrance and exit points, find a path from the entrance to the
exit, if one exists.
答案是
class Coordinate {
public:
int x, y;
const bool operator==(const Coordinate &that) const {
return (x == that.x && y == that.y);
}
};
bool is_feasible(const Coordinate &cur, const vector> &maze) {
return cur.x >= 0 && cur.x < maze.size() &&
cur.y >= 0 && cur.y < maze[cur.x].size() &&... 阅读全帖 |
|
T******e
发帖数: 157 | 48 用一个bool数组表示visited or unvisited，从index0开始跳，每次跳都把node标成
visited，并且计数，如果跳回了其它visited的节点，说明是环，记录长度，如果下一
次跳回的visited的节点是自己则说明不存在环，每次重新跳的时候，都遍历bool数组
选择下一个没有visited的节点开始。
因为数字都不同的，所以不会出现多对一的情况。
如果不想用bool数组，可以用把数组中的值改成负值的方法标记，但要注意0的处理。
这样的复杂度估计是O（n^2）求大神更好解法。
刚才想了想其实起点是哪个不重要，每次重新跳的时候可以直接从下一个unvisited节
点开始，如果到头了发现还有没访问的点，就从头开始，这样或许能快些 |
|
T******e
发帖数: 157 | 49 用一个bool数组表示visited or unvisited，从index0开始跳，每次跳都把node标成
visited，并且计数，如果跳回了其它visited的节点，说明是环，记录长度，如果下一
次跳回的visited的节点是自己则说明不存在环，每次重新跳的时候，都遍历bool数组
选择下一个没有visited的节点开始。
因为数字都不同的，所以不会出现多对一的情况。
如果不想用bool数组，可以用把数组中的值改成负值的方法标记，但要注意0的处理。
这样的复杂度估计是O（n^2）求大神更好解法。
刚才想了想其实起点是哪个不重要，每次重新跳的时候可以直接从下一个unvisited节
点开始，如果到头了发现还有没访问的点，就从头开始，这样或许能快些 |
|
f**********t
发帖数: 1001 | 50 // Given an array [a1, a2, ..., an, b1, b2, ..., bn], transform it to [a1,
b1, a2, b2, ..., an, bn].
void EvenShuffle_(string &vi, size_t left, size_t right, bool leftmore) {
size_t len = right - left;
if (len < 2) {
return;
} else if (len == 2) {
if (!leftmore) {
swap(vi[left], vi[left + 1]);
}
return;
}
size_t mid = left + len / 2;
size_t ll = left + len / 4;
bool llmore = true;
bool rlmore = true;
if (len % 4 == 1) {
if (leftmore) {
++mid;
... 阅读全帖 |
|
