f*****e
发帖数: 2992 | 1 先扫一遍，确定范围。然后分配一个这个范围大小的数组A。
每个数组元素，结构为：
{bool, Node *} bool记载这个点occupied or not。
然后创建一个Node链表B，每个Node存放起点和终点。
struct Node {
int start;
int end;
Node* next;
}
A的每一个occupied的元素指向B的一个元素。
当插入v到A的时候，如果A[v]已经occupied了就什么事也不做，如果A[v]没有occupied
并且A[v-1]或A[v+1]有一个已经occupied，就并入那个occupied的interval:A[v]=A[v-
1]或A[v]=A[v+1], 并且更新相应的B的start & end信息。如果A[v-1]和A[v+1]两个都
occupied，就合并两个B interval。如果两边都没有occupied，就加入一个新元素到B
。好想见到过或做过。 |
|
B********t
发帖数: 147 | 2 小冷骑士 多谢建议 我也刚学c++不久
c++里有set和map set是avl树实现的 map是红黑树实现的 为什么这里要用set而不
是map呢？
如果用set就是这样
bool myfunc(string s1, string s2)
{
return (s1.size() > s2.size());
}
bool findLongestWord_helper(string &s, set &hs)
{
for(int i = 1; i <= s.size(); i++)
{
string sub_f(s, 0, i);
if(hs.find(sub_f) != hs.end())
{
if(i == s.size())
return true;
string sub_b(s, i, s.size()-i);
if(findLongestWord_helper(sub_b, hs))
return true;
}
}
return false;
}
string findLongestWord(vector &vs)
{
string ... 阅读全帖 |
|
s*****n
发帖数: 994 | 3 多谢各位，刚才把regular expression match理解为wildcard matching了，
那就顺便把wildcard matching的code给贴上来吧
class Solution {
public:
bool isMatch(const char *s, const char *p) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int m=strlen(s);
int n=strlen(p);
bool dp[1000][1000] = {false};//dp[i][j] means last i chars in s
matches last j chars in p
dp[0][0] = true;
for (int i=1; i<=n; ++i){
dp[0][i] = dp[0][i-1]... 阅读全帖 |
|
f*******4
发帖数: 64 | 4 第3题二爷的代码可以过大数据吗？
我的做法貌似和二爷的一样，但是跑不完大数据，贴出来大家给瞧瞧怎么优化
typedef std::tr1::unordered_map hash_t;
bool isBad(const hash_t & bad, int W, int w, int h) {
hash_t::const_iterator it = bad.find(W*h+w);
if (it == bad.end())
return false;
else return true;
}
int solve(int W,int H,int P,int Q,int N,int X,int Y,int a,int b,int c,int d)
{
hash_t bad;
for (int i=0,x=X,y=Y,t; i
bad[x+y*W] = true;
t = x;
x = (x*a+y*b+1)%W;
y = (t*c+y*... 阅读全帖 |
|
B********t
发帖数: 147 | 5 贴一个, 如果递归不算extra space....
class Solution {
public:
void recoverTree(TreeNode *root, TreeNode *&pre, TreeNode *&big,
TreeNode *&small, bool &first)
{
if(root)
{
recoverTree(root->left, pre, big, small, first);
if(first && root->val < pre->val)
{
big = pre;
first = false;
}
if(root->val < pre->val)
small = root;
pre = root;
recoverTree(root->r... 阅读全帖 |
|
w****x
发帖数: 2483 | 6 class Solution {
public:
int ladderLength(string start, string end, unordered_set &dict) {
unordered_set visited;
visited.insert(start);
queue que;
que.push(start);
int nCurLev = 1;
int nCurNum = 1;
int nNextNum = 0;
while (!que.empty())
{
string strCur = que.front();
que.pop();
nCurNum--;
for (unordered_set::itera... 阅读全帖 |
|
w****x
发帖数: 2483 | 7 class Solution {
public:
int ladderLength(string start, string end, unordered_set &dict) {
unordered_set visited;
visited.insert(start);
queue que;
que.push(start);
int nCurLev = 1;
int nCurNum = 1;
int nNextNum = 0;
while (!que.empty())
{
string strCur = que.front();
que.pop();
nCurNum--;
for (unordered_set::itera... 阅读全帖 |
|
f*******t
发帖数: 7549 | 8 找出了一年多前写的逆波兰处理算数表达式的代码，强烈建议有兴趣的自己实现一下：
#include
#include
#include
#include
#define BUFFSIZE 1024
using namespace std;
struct Token {
bool isNum;
int num;
char op;
Token();
Token(const Token& t);
};
Token::Token()
{
isNum = false;
num = 0;
op = 0;
}
Token::Token(const Token& t)
{
isNum = t.isNum;
num = t.num;
op = t.op;
}
Token *getToken(const char expr[], int& idx)
{
Token *res = NULL;
while(expr[idx] == ' ')
... 阅读全帖
|
|
x******a
发帖数: 6336 | 9 ／／main（）
#include
#include
#include "linkedlist.h"
int main()
{
LinkedList myList(5, "luke");
Iterator myIterator=myList.begin();
myList.insert(myIterator, "leia");
myIterator.forward();
myList.erase(myIterator);
myList.insert(myIterator, "chewbca"); 《＝＝＝＝＝＝出问题。
myList[2]="han";
for (int i=0; i
std::cout<
}
myList.insert(myIterator, "chewbca"); 《＝＝＝＝＝＝出问题。
这一句运行起来ta... 阅读全帖 |
|
r*****e
发帖数: 146 | 10 agree,if the people in the past thousand of years are too many, we can
simplify it by recording the visited ancestor.
// for the root id, dict[root_id] == "#";
// dict is something like map
bool share_ancestor(map dict, string c1, string c2){
set found;
while(true){
if(check(c1,dict, found))
return true;
if(check(c2,dict, found))
return true;
if(c1 == "#" && c2 == "#")
return false;
... 阅读全帖 |
|
p*****p
发帖数: 379 | 11 随便写了下，可能有bug
1.
bool checkDup(int *a, int n) {
unordered_set set;
for (int i = 0; i < n; ++i) {
if (set.find(a[i]) == set.end()) {
set.insert(a[i]);
}
else {
return true;
}
}
return false;
}
2.
bool checkDup(int *a, int n, int k) {
list kCont;
unordered_set set;
for (int i = 0; i < n; ++i) {
if (set.find(a[i]) == set.end()) {
if (kCont.size() == k) {
set.erase(kC... 阅读全帖 |
|
p****e
发帖数: 3548 | 12 修改下BFS也可以，要记下路径就行
用'a'-'z'方法再写了一个
大数据: 750ms
class Solution {
public:
void getrows(vector, unordered_map::
iterator> > &path,
int col, vector &row, vector > &
ret){
row.push_back(path[col].second->first);
vector & cp = path[col].first;
for(int i=0; i
if(cp[i] < 0){
reverse(row.begin(), row.end());
ret.push_back(row);
... 阅读全帖 |
|
p****e
发帖数: 3548 | 13 修改下BFS也可以，要记下路径就行
用'a'-'z'方法再写了一个
大数据: 750ms
class Solution {
public:
void getrows(vector, unordered_map::
iterator> > &path,
int col, vector &row, vector > &
ret){
row.push_back(path[col].second->first);
vector & cp = path[col].first;
for(int i=0; i
if(cp[i] < 0){
reverse(row.begin(), row.end());
ret.push_back(row);
... 阅读全帖 |
|
h***i
发帖数: 1970 | 14 贴个旁门左道。 88 milli secs过large test.
typedef struct FU {
int parent;
bool fill;
int rank;
FU(int v, bool f)
: parent(v),
fill(f),
rank(0) {
}
} FU;
int find(int i, vector &v) {
if (v[i].parent == i) return i;
v[i].parent = find(v[i].parent, v);
return v[i].parent;
}
void union_by_rank(int i, int j, vector &v) {
int k = find(i, v);
int ... 阅读全帖 |
|
K********y
发帖数: 47 | 15 （原贴见http://www.mitbbs.com/article/JobHunting/32331973_3.html）
3: 实现两个函数: H() and O(), 这两个函数会被多线程调用。当一个线程调用H或O时
，如果当前已经有至少两个线程call H和一个线程call O。那么让两个call H和一个
call O的线程返回（产生一个水分子），其他的都block。
多线程我不熟，pthread里没有现成的semaphore，所以习惯用condition variable。闭
门造车写了下面这样一个解法，显然不如版上各位给的代码简洁。但是这里有个bug我
想不明白，请教一下各位：
我的基本想法是，如果三个原子里最后一个就位的是H，则signal O，O再signal另一个
H；如果最后一个是O，则signal一个H，这个H再signal另一个H。为了区分H函数的两种
情况，我起初用了个bool signalNextH，但是会出现死锁。改成int来计数就过了（下
面的代码）。从这个症状来看，似乎是有两个O原子同时发出了signal，所以
signalNextH要用counter... 阅读全帖 |
|
K********y
发帖数: 47 | 16 （原贴见http://www.mitbbs.com/article/JobHunting/32331973_3.html）
3: 实现两个函数: H() and O(), 这两个函数会被多线程调用。当一个线程调用H或O时
，如果当前已经有至少两个线程call H和一个线程call O。那么让两个call H和一个
call O的线程返回（产生一个水分子），其他的都block。
多线程我不熟，pthread里没有现成的semaphore，所以习惯用condition variable。闭
门造车写了下面这样一个解法，显然不如版上各位给的代码简洁。但是这里有个bug我
想不明白，请教一下各位：
我的基本想法是，如果三个原子里最后一个就位的是H，则signal O，O再signal另一个
H；如果最后一个是O，则signal一个H，这个H再signal另一个H。为了区分H函数的两种
情况，我起初用了个bool signalNextH，但是会出现死锁。改成int来计数就过了（下
面的代码）。从这个症状来看，似乎是有两个O原子同时发出了signal，所以
signalNextH要用counter... 阅读全帖 |
|
o******3
发帖数: 91 | 17 我今天又写了一下
现在这个可以过所有数据集合了
方法还是BFS
区别的 这次我没有模拟stack
直接在Array上操作 这样程序更简单 写的可以快一点
#include
#include
#include
#include
#include |
|
j********r
发帖数: 25 | 18 参考了大牛们的， 写了一个自认为还算简洁的：
int minCut(string s) {
int m = s.length();
vector> palindromes(m, vector(m, false));
vector cuts(m,m);
cuts[0] = 0;
for(int i = 1; i < m; i++) {
for(int j = i; j >= 0; j--) {
if (s[i] == s[j] && (i-j <2 || palindromes[i-1][j+1])){
palindromes[i][j] = true;
if (j==0)
cuts[i] = 0;
else
... 阅读全帖 |
|
T*******e
发帖数: 4928 | 19 similar, C++ DP version.
int minCut(string s) {
int sSize=s.size();
if(sSize<2) return 0;
vector minCuts(sSize+1,0);
for(int i=0; i<=sSize; ++i) minCuts[i]=sSize-1-i;
vector > isPalindrome(sSize, vector(sSize, false));
for(int i=sSize-2; i>=0; --i) {
for(int j=i; j
if(s[i]==s[j] && (j-i<=2 ||isPalindrome[i+1][j-1])) {
isPalindrome[i][j]=true;
minCuts[i]=min(minCuts[i],minCuts[j+1]+... 阅读全帖 |
|
j*****y
发帖数: 1071 | 20 写了一个，欢迎测试
#include
#include
#include
#include
#include
using namespace std;
bool isNumber(string s)
{
if(s[0] == '+' || s[0] == '-' || s[0] == '(' || s[0] == ')')
{
return false;
}
return true;
}
int helper(int a, int b, char c)
{
if(c == '+')
{
return a + b;
}
else
{
return a - b;
}
}
bool valid(vector &s)
{
stack v;
stack c;
for(int i = 0; i < s.size(); ++i)
... 阅读全帖 |
|
j*****y
发帖数: 1071 | 21 写了一个，欢迎测试
#include
#include
#include
#include
#include
using namespace std;
bool isNumber(string s)
{
if(s[0] == '+' || s[0] == '-' || s[0] == '(' || s[0] == ')')
{
return false;
}
return true;
}
int helper(int a, int b, char c)
{
if(c == '+')
{
return a + b;
}
else
{
return a - b;
}
}
bool valid(vector &s)
{
stack v;
stack c;
for(int i = 0; i < s.size(); ++i)
... 阅读全帖 |
|
d****n
发帖数: 233 | 22 bool isDigit(const string &expr, int pos)
{
return expr[pos] >='0' && expr[pos] <= '9';
}
void parseNum(const string &expr, int &pos)
{
if (expr[pos] == '0') {
pos++;
// if the first char is '0', it is a number
// following digits should be treated as separate number.
return;
}
while(isDigit(expr, pos))
pos++;
return;
}
bool validate(const string& expr) {
stack st;
int i = 0;
while(i < expr.length()) ... 阅读全帖 |
|
J**9
发帖数: 835 | 23 来自主题: JobHunting版 - G家电面题 This is another question that seems easy but hard to code precisely.
Here's my version in C:
///1) Convert the string into all lower cases either in place or into
another buffer;
///2) First pass to check which ones are vowels;
///3) Second pass to sum up the products.
///4) Space O(n); Time O(n)
/** convert a string to lowercase in place */
char* hkStringTolower(char *str)
{
if(!str) return NULL;
char *s=str;
while(*s)
{
*s = tolower(*s);
s++;
}
return st... 阅读全帖 |
|
r***e
发帖数: 29 | 24 最后个人标准答案
#ifndef _ROMON_HEADER_
#define _ROMON_HEADER_
#define _DEBUG_
#include
#include
//ROMON digits
const std::string ROMON_DIGITS[] = {"I","IV","V","IX", "X","XL","L","XC","C"
,"CD","D","CM","M" };
//ROMON scale
const int ROMON_SCALE[] = {1, 4, 5, 9, 10, 40, 50, 90, 100, 400, 500, 900,
1000};
const int ROMON_MAX = 3999;
const int ROMON_MIN = 1;
class RomanNumeralGenerator
{
public:
virtual std::string generator(int num) = 0;
};
class CRoman : public RomanNumeralGene... 阅读全帖 |
|
s*********e
发帖数: 197 | 25 为了积攒人品RP，为了H1B顺利，为了有更好的工作，为了有一个更好的将来，开始追
leetcode，并写下自己的做题感受和大家分享，更是作为自己的督促。做题目的原则如
下：
1) Optimized Algorithms to pass the "large" test.
2) Proper abstraction
3) Write the code whose correctness is *easy* to reason about.
4) Favor readability over efficiency without compromising item 1).
5) Rearrangement and tweaking
我试图对自己进行训练的目标就是写完代码，能够确认自己写对了。目前为止，我有一
些小小的心得，会贯穿在下面和以后的文章中。第一，循环不变式；第二，优化控制流
；第三，适度抽象，语义精确的子函数。
抛砖引玉，献上第一弹：Text Justification. 为了更好的可读性，想用一种类C的伪
代码并尽量省略一些类型声明。很多叙述可能比较罗嗦，见谅。
首先要考虑的... 阅读全帖 |
|
r*****e
发帖数: 792 | 26 insert() 返回的是pair, second就是这个bool值啊。
这个和hash table强和弱没关系啊，呵呵。最好的办法就是读一下hash_set
的description，这些基础的东西其实也得会啊:-)
.. |
|
r*********n
发帖数: 4553 | 27 传说中的pruning? 在recursion的时候设置一个全局flag，如果达到条件，就直接返回
比如在binary tree里面寻找一个key，
class BT{
bool found;
void contain(Node* nd, int key){
if(found) return;
if(nd == nullptr) return;
if(nd->val == key){
found = true;
return;
}
contain(nd->left, key);
contain(nd->right, key);
}
public:
BT():found(false){}
bool contain(Node* root, int key){
contain(root, key);
return found;
}
};
如果没有found，那么每个node都要check一遍。如果key刚好在最左下角的node里面，
那么上面这个方法只需要check那个node的height那么多... 阅读全帖 |
|
p*****3
发帖数: 488 | 28 //DP矩阵中如果遇到.*或.+, 那么DP[i][j] == DP[i][j+1] = true/false
const int M = 100;
bool isMatchDP(const char* str, const char* pattern)
{
if (NULL == str || NULL == pattern)
return false;
int len1 = strlen(str);
int len2 = strlen(pattern);
bool DP[M][M] = { false }; //DP[len1+1][len2+1]
DP[0][0] = true;
for (int i = 1; i <= len2; )
{
if (pattern[i] == '*')
{
DP[0][i] = DP[0][i-1];
DP[0][i+1] = DP[0][i];
i += 2;
... 阅读全帖 |
|
b******g
发帖数: 1721 | 29 You are given a game board that contains a four by four (4x4) array of
pieces. The pieces can be one of six shapes and can be one of six colors
If the board contains 4 pieces of the same shape and same color, the board
contains a winning pattern.
public enum Color
{
Red,
Blue,
Green,
Yellow,
Black,
Purple
}
public enum Shape
{
Square,
Triangle,
Circle,
Star,
Pentagon,
Octagon
}... 阅读全帖 |
|
r*********n
发帖数: 4553 | 30 要写一个真正的C++ iterator不容易，对于bst，bidirectional iterator应该就够了。
//T is the type of tree node value
template class BSTIterator: public std::iterator
iterator_tag, T> {
//....
public:
//...
BSTIterator& operator++();
BSTIterator opterator++(int);
BSTIterator& operator--();
BSTIterator operator--(int);
T& operator*();
bool operator==(const BSTIterator&);
bool operator!=(const BSTIterator&);
};
至少把上面几个关键的operator overload之后才差不多吧。 |
|
d***n
发帖数: 832 | 31 来自主题: JobHunting版 - 一个小题目 给一个function bool flip()
返回 True or False 的概率是 50/50
要写一个bool flipbiased(int n)
要求返回True的概率是1/n
False自然就是(n-1)/n |
|
d******e
发帖数: 164 | 32 抛个砖：
bool isNumber(const char *s) {
while (isspace(*s)) s++;
if (*s == '+' || *s == '-') s++;
bool num = false;
while (isdigit(*s)) s++, num = true;
if (*s == '.') {
s++;
while (isdigit(*s)) s++, num = true;
}
if (*s == 'e' && num) {
s++, num = false;
if (*s == '+' || *s == '-') s++;
while (isdigit(*s)) s++, num = true;
}
while (isspace(*s)) s++;
return ... 阅读全帖 |
|
r*c
发帖数: 167 | 33 RK肯定好写些，尽管它比KMP要慢不少。
前些天看到一个帖子，把RK的实现搞得特麻烦。下面贴个改进的，其中hash function
可替换，只要把各个char的信息都用到就好了。
class RobinKarpSolution
{
public:
char *strStr(char *haystack, char *needle) {
int nHSLen = strlen(haystack), nNDLen = strlen(needle);
if(nNDLen > nHSLen) return NULL;
int h_hash, n_hash = hashAString(needle, nNDLen, 0);
for(int i = 0; i <= nHSLen-nNDLen; ++i){
h_hash = hashAString(haystack, nNDLen, i);
if(n_hash == h_hash) {
if(!C... 阅读全帖 |
|
s***5
发帖数: 2136 | 34 O(n) space, O(n) time.
bool equal_bits(bool input[], int n, int& sta, int& end) {
// check if all elements are all 1's or all 0's
int sum = 0;
for(int i = 0; i < n; i++)
sum += input[i];
if(sum == 0 || sum == n) return false;
unordered_map freq;
int counter = 0, maxL = 0;
freq[counter] = -1;
for(int i = 0; i < n; i++) {
if(input[i])
counter++;
else
counter--;
if(freq.count(... 阅读全帖 |
|
a********m
发帖数: 15480 | 35 dp
hashmap, int> mem;
int CalcMax(Node *node, bool flag) {
if (!node) return 0;
if (!mem.exist(node, flag)) {
if (flag) {
mem[node, flag] = CalcMax(node->left, false) + CalcMax(node->left,
false);
} else {
mem[node, flag] = max(CalcMax(node->left, false) + CalcMax(node->left,
false),
CalcMax(node->left, true) + CalcMax(node->left, true) +
node->value);
}
}
return mem[node, flag];
} |
|
d****n
发帖数: 397 | 36 这个算法行不行，基本上和上面的同学说的差不多。
第一步，把身高数组和b数组，一起按身高数组排序。
第二步，从最小的element开始，reconstruct 新的数组。
第一步是O(nlgn).第二步，最坏是O(n^2)。（当b全为0）时。
以下是程序。
#include
#include
#include
using namespace std;
struct mypair {
int a;
int b;
mypair(int c,int d) {a=c;b=d;}
friend bool operator<(const mypair&,const mypair&);
};
bool operator<(const mypair &p1,const mypair &p2) {
return (p1.a
}
vector heightcomp(vector& a,vector& b) {
int i,k,j,n,m;
n=a.size();
vector阅读全帖 |
|
k*******2
发帖数: 84 | 37 II是含duplicate的。下面这个解法过OJ没问题，但是我不是很理解它是怎么处理{1, 1
}这种情况的。
if (used[i] || (i != 0 && num[i] == num[i - 1] && used[i - 1])) continue;
我怎么觉得它会返回空{}。
估计是哪里想错了，求指教。多谢！
class Solution {
public:
vector > permuteUnique(vector &num) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector used(num.size(), false);
vector path;
vector > ret;
sort(num.begin(), num.end());
sub(num, ... 阅读全帖 |
|
s*******y
发帖数: 12 | 38 改一下: 原因是因为leetcode每次只生一个Solution的一个instance，所以注意
int last_val = INT_MIN;每次调用isValidBST_inner之前要自己重新初始化。
class Solution {
public:
int last_val = INT_MIN;
bool isValidBST(TreeNode *root) {
last_val = INT_MIN;
return isValidBST_inner(root);
}
bool isValidBST_inner(TreeNode *root) {
if (root == NULL) {
return true;
}
if (!isValidBST(root->left)) {
return false;
}
if (root->val <= last_val) {
... 阅读全帖 |
|
x******e
发帖数: 18 | 39 多谢大牛，如果last_val初始化放在class内，在本机上会报错但是在leetcode上没事
？上一个AC的：
int last_val = INT_MIN;
class Solution {
public:
bool isValidBST(TreeNode *root) {
last_val = INT_MIN;
return isValidBST_inner(root);
}
bool isValidBST_inner(TreeNode *root) {
if (root == NULL) {
return true;
}
if (!isValidBST_inner(root->left)) {
return false;
}
if (root->val <= last_val) {
return false;
}
last_va... 阅读全帖 |
|
s***e
发帖数: 403 | 40 没有什么太大的难度啊
设置两个变量，back_left, back_right，然后先向左移动。在向parent移动的时候识
别是从左边子树移动来的还是从右边子树移动来的。如果是从右边子树移动来的说明所
有右边子树已经访问过，所以就向上移动，否则访问右边子树。最后从右边移动到root
的时候表明访问完毕。需要考察的也就是根节点的右子树是否访问完全。
下面是代码，可能有bug，不过思路大致如此。
struct TreeNode
{
TreeNode* parent;
TreeNode* left;
TreeNode* right;
int value;
explicit TreeNode(int val, TreeNode* p=nullptr) :
parent(p), left(nullptr), right(nullptr), value(val)
{}
};
void traverse(TreeNode* node)
{
TreeNode* iter=node;
bool backleft=false... 阅读全帖 |
|
m**********e
发帖数: 22 | 41 今天重做leetcode：String Reorder Distance Apart。发现1337c0d3r给出的答案（http://discuss.leetcode.com/questions/31/string-reorder-distance-apart）有较大改进的地方："used" array and the while loop inside the for loop are not needed. I wrote one with C#:
// String Reorder Distance Apart
public string ReorderDistanceApart(string str, int distance)
{
int[] freq = new int[256];
int[] used = new int[256];
bool[] except = new bool[256];
int n = str.Length... 阅读全帖 |
|
y***n
发帖数: 1594 | 42 Is this a DP problem, I tried a recursive solution which exceeds time limit
bool wordBreak(string s, unordered_set &dict) {
if(s.length()==0) return true;
bool foundBreak=false;
for(const string& current: dict){
if(s.compare(0, current.size(),current)==0){//find current
foundBreak= wordBreak(s.substr(current.size()), dict);
if(foundBreak)
break;
}
}
return foundBreak;
... 阅读全帖 |
|
T*******e
发帖数: 4928 | 43 哈，咱们思路差不多。
bool wordBreak(string s, unordered_set &dict) { //Time: O(n^2)
int sSize=s.size();
if(sSize<=0||dict.empty()) return false;
vector isWord(sSize+1, false);
isWord[0]=true;
for(int i=1; i<=sSize; ++i) {
for(int j=i-1; j>=0; --j) {
if(dict.find(s.substr(j, i-j))!=dict.end() &&isWord[j]) {
isWord[i]=true;
break;
}
}
}
return isWord[sSize];
}
reused |
|
s********u
发帖数: 1109 | 44 做了一下7.6，就是找经过点最多的直线。
答案给的比较复杂，是用一个 >的hashmap，在斜率匹配的情况
下，再去vector找匹配的line，而且感觉有bug，在匹配斜率的时候没有考虑斜率无穷
大的情况。
我想了一下C++的做法，比较直观的做法是建立 的hashtable,然后重载一下
预算符，当斜率差和截距差都小于eps = 0.0001的时候视作两条线是同一条线。
但是因为重载这一块不太熟，不知道写的对不对，请大牛们指点一下：
//Given a two-dimensional graph with points on it,find a line which passes
the most number of points.
class Line{
private:
double slope;
double intercept;
bool infinity_slope;
static double eps;
public:
... 阅读全帖 |
|
m**********g
发帖数: 153 | 45 先dp, 然后dfs, 用dp信息剪枝.
class Solution {
void getSentence(string &s, int start, string sentence, vector &
output, unordered_set &dict, bool *breakable)
{
if(start == s.size()) {
sentence.erase(sentence.end() -1);
output.push_back(sentence);
return;
}
for(int i=start; i
if(breakable[i+1] == false) //prune here
continue;
string tmp=s.substr(start, i-start+1);
... 阅读全帖 |
|
s********u
发帖数: 1109 | 46 写了一下，觉得难点主要在回溯写这个path，如果维护不好，很容易出bug。
52ms通过。
class Solution {
public:
void backtracking( int end,const vector >&prev,const string
&s, vector &paths, string &path ){
if(end == -1){
paths.push_back(path);
return;
}
int prev_end;
string word;
const string local = path;
for(int i = 0; i < prev[end].size(); i++){
prev_end = prev[end][i];
... 阅读全帖 |
|
r*******n
发帖数: 3020 | 47 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();
}
//DP
for(int i=0; i
for(int j=i;j阅读全帖 |
|
p****o
发帖数: 46 | 48 why not bool array? because the size is unknown?
c++ solution:
#include
#include
using namespace std;
int findCycle(int idx[], int size){
deque visited(size, false);
int max = 1;
for (int i = 0; i < size; ++i) {
if (!visited[i]) {
visited[i] = true;
int cnt = 1;
for (int j = idx[i]; j!=i; j = idx[j]) {
visited[j] = true;
cnt++;
}
if (cnt > max) max = cnt;
}
}
return max;
}
int main(){
int idx [] = {3, 2, 1, 4, 0};
cout << findCycle (idx, 5) << endl;
} |
|
p****o
发帖数: 46 | 49 why not bool array? because the size is unknown?
c++ solution:
#include
#include
using namespace std;
int findCycle(int idx[], int size){
deque visited(size, false);
int max = 1;
for (int i = 0; i < size; ++i) {
if (!visited[i]) {
visited[i] = true;
int cnt = 1;
for (int j = idx[i]; j!=i; j = idx[j]) {
visited[j] = true;
cnt++;
}
if (cnt > max) max = cnt;
}
}
return max;
}
int main(){
int idx [] = {3, 2, 1, 4, 0};
cout << findCycle (idx, 5) << endl;
} |
|
s********u
发帖数: 1109 | 50 今天bbs有问题，刚刚写了一堆没有了，先贴代码：
void remove(char *str){
int left = 0, right = 0;
bool unique = true;
while(str[right]!= '\0'){
//你也可以用一个 bool unique(char *str,int right)函数来判断，不用这个
unique变量
unique = true;
for(int i = 0; i < right; i++){
if( str[i] == str[right] ){
duplicate = false;
break;
}
}
if(unique){
str[left++] = str[right++];
}else{
right++;
}
}
str[left] = '\0';
}
int main(){
char str[9] = "abcabxyx";
remove(str);
cout<
} |
|
