e****r
发帖数: 581 | 1 Droid + WenQuanYi Micro Hei
附送我的很简单的.fonts.conf
##########################
true
true
true
阅读全帖 |
|
m*****m
发帖数: 242 | 2 1.
template
bool is_int();
is_int must return true if T is int and false otherwise. How do you
implement is_int?
Choice 1
template
bool is_int()
{
return T is int;
}
Choice 2
template
bool is_int()
{
return false;
};
template
bool is_int()
{
return true;
};
Choice 3
template
bool is_int()
{
T a;
return dynamic_cast(&a) != 0;
}
Choice 4
template
bool is_int()
{
return typeof(T) |
|
s*****n
发帖数: 994 | 3 no repeats solution:
bool findCoins(int remain, int numTwo, int numThree, int numFive, string & s
){
bool found = false;
string s2 = "", s3 = "", s5 = "";
if (remain == 0)
{
s = "\n";
return true;
}
else if (remain < 2)
return false;
if (remain >= 2 && numTwo >= 1){
bool b = findCoins (remain - 2, numTwo - 1, numThree, numFive, s2);
if (b){
found = true;
size_t endOfLine(0);
string olds = "\n"... 阅读全帖 |
|
i**********e
发帖数: 1145 | 4 I think you need to do DFS from all possible starting points in the grid, not just the top left point.
My code below for reference (does not return the path but return if the word is in the grid or not, should be easy to modify to return the path) :
#include
#include
using namespace std;
const int MAX_ROWS = 100;
const int MAX_COLS = 100;
bool dfs(char grid[][MAX_COLS], int row, int col, int m, int n,
int charIndex, string target, bool visited[][MAX_COLS]) {
if (ro... 阅读全帖 |
|
w****x
发帖数: 2483 | 5 void MarkMap(const char* szStrs[], int n, int nBegIndex, bool chrMap[26][26])
{
assert(szStrs && nBegIndex >= 0 && n >= 0);
if (n <= 1) return;
int nDiv = -1;
for (int i = 0; i < n-1; i++)
{
char tmp1 = *(szStrs[i] + nBegIndex);
char tmp2 = *(szStrs[i+1] + nBegIndex);
assert(((tmp1 >= 'a' && tmp1 <= 'z') || tmp1 == 0));
assert(((tmp2 >= 'a' && tmp2 <= 'z') || tmp2 == 0));
if (tmp1 != 0 && nDiv < 0)
nDiv = i;
if (tmp1... 阅读全帖 |
|
f*******l
发帖数: 66 | 6 #include
#include
using namespace std;
bool isValid( char currentChar,int x, int y, int columnSize, int
rowSize,
char desiredChar, bitset <20> mybitset )
{
if(x < 0 || x > columnSize || y < 0 || y > rowSize )
{
return false ;
}
if ( mybitset[x*columnSize+y] == 1 )
{
return false;
}
if ( currentChar != desiredChar)
{
return false ;
}
return true ;
}
bool moveforward( int rowSize, int columnSize, char Array[][4], int... 阅读全帖 |
|
i*********7
发帖数: 348 | 7 下面是employee的数据结构
struct employee{
public:
int start;
int end;
employee(int s, int e){start = s; end = e;}
//下面是如何重载运算符，以用于排序算法。必须要声明为常量函数，否则不通过
。。。
bool operator < (const employee& s) const{
return end < s.end;
}
bool operator == (const employee& s) const{
return end == s.end;
}
bool operator > (const employee& s) const{
return end > s.end;
}
bool operator <= (const employee& s) const{
return end <= s.end;
}
bool... 阅读全帖 |
|
B*******1
发帖数: 2454 | 8 My code
pass all the test on 1337 online judge.
bool isScrambleHelper(const string &s1, const string &s2, map
string>, bool> &myMap)
{
pair key = make_pair(s1, s2);
if (myMap.count(key) != 0) return myMap[key];
bool result = false;
if (s1 == s2) {
result = true;
} else if (s1.size() != s2.size() ) {
result = false;
} else {
for (int i = 1; i < s1.size(); i++) {
if ((isScrambleHelper(s1.substr(0, i), s2.substr(... 阅读全帖 |
|
l****c
发帖数: 782 | 9 换了DP,觉得和你第二页做的很像，应该是n^2了。
可过了小测试，过不了大测试啊。
您的那个代码也是只能过小测试。。。。。。
boolean isInterleave(string s, string s1, string s2)
{
if (s.length()!=(s1.length()+s2.length())) return false;
int l1 = s1.length()+1;
int l2 = s2.length()+1;
bool **dpt = (bool**)malloc(sizeof(bool*)*l1);
for (int i = 0; i < l1; i++)
dpt[i] = (bool*)malloc(sizeof(bool)*l1);
for (int i = 0; i < l1; i++) {
for (int j = 0; j < l2; j++) {
if (i==0&&j==0)
dpt[i][j] = tr... 阅读全帖 |
|
w****x
发帖数: 2483 | 10 上个O(n)空间的
bool isInterleave(string s1, string s2, string s3) {
const char* p1 = s1.c_str();
const char* p2 = s2.c_str();
const char* p3 = s3.c_str();
int nLen1 = strlen(p1);
int nLen2 = strlen(p2);
int nLen3 = strlen(p3);
if (nLen3 != nLen1 + nLen2)
return false;
if (nLen3 == 0) return true;
bool* rec = new bool[nLen2+1];
for (int i = nLen1; i >= 0; i--)
{
... 阅读全帖 |
|
w****x
发帖数: 2483 | 11
/*
Given an array list of lots of strings, they are arranged by unknown
alphabetical
order, print all possible alphabetical orders (Sort)
*/
void buildMap(const char* str[], int n, int nBeg, bool bMap[26][26])
{
if (str == NULL || n <= 1) // <= 1 not 0
return;
int nPrev = 0;
while (str[nPrev][nBeg] == 0 && nPrev < n) // missing nPrev < n
nPrev++;
int nIter = nPrev + 1;
while (nIter < n)
{
if (str[nPrev][nBeg] != str[nIter][nBeg])
{
... 阅读全帖 |
|
s**********1
发帖数: 58 | 12 我也贴一个，没有上面lucky的简单，不过可以改成binary search，lucky的那个应该
不好改
主要就是写了个iterator
enum FindType {
Lesser,
LesserEqual,
Equal,
GreaterEqual,
Greater
};
class Iterator {
public:
Iterator(const vector& array)
:array(array)
{
assert(array.size());
ascending = array.front() <= array.back();
offset = ascending ? 0 : array.size() - 1;
}
bool can_step(bool forward) {
int new_offset = offset + ascending == forward ? 1 : -1;
retu... 阅读全帖 |
|
p*****p
发帖数: 379 | 13 http://leetcode.com/onlinejudge#question_79
思路就是DFS，递归实现backtrack
large case超时，不知是剪枝不对还是递归费时
代码感觉没大问题
求帮忙看看，谢谢
class Solution {
public:
bool exist(vector > &board, string word) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if (word.empty()) return true;
int m = board.size();
int n = board[0].size();
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (board[i]... 阅读全帖 |
|
i**********e
发帖数: 1145 | 14 Some basic optimizations, now it passes Large in 316ms.
class Solution {
public:
bool exist(vector > &board, string word) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if (word.empty()) return true;
int m = board.size();
int n = board[0].size();
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
vector >visited;
if (board[i][j] != word[0... 阅读全帖 |
|
d****n
发帖数: 1241 | 15 可以使用编译器在lexing和parsing的时候用的某种技术：recursive descent parsing
http://en.wikipedia.org/wiki/Recursive_descent_parser
下边的代码假设单个的数字也是合法的，比如：
1 合法
（1）合法
(1) + (2) 合法, 等等
#include
#include
#include
#include
using namespace std;
enum TokenKind {
TOK_Unknown = -1,
TOK_End,
TOK_Op,
TOK_LParen,
TOK_RParen,
TOK_Num,
};
static TokenKind getToken(const string &Input, int &Pos)
{
assert(Pos <= Input.length());
char TheChar = Input[Pos];
while (isspace(TheC... 阅读全帖 |
|
d****n
发帖数: 1241 | 16 可以使用编译器在lexing和parsing的时候用的某种技术：recursive descent parsing
http://en.wikipedia.org/wiki/Recursive_descent_parser
下边的代码假设单个的数字也是合法的，比如：
1 合法
（1）合法
(1) + (2) 合法, 等等
#include
#include
#include
#include
using namespace std;
enum TokenKind {
TOK_Unknown = -1,
TOK_End,
TOK_Op,
TOK_LParen,
TOK_RParen,
TOK_Num,
};
static TokenKind getToken(const string &Input, int &Pos)
{
assert(Pos <= Input.length());
char TheChar = Input[Pos];
while (isspace(TheC... 阅读全帖 |
|
r*c
发帖数: 167 | 17 //矩阵求连接图
#include
#include
#include
#include
#include
using namespace std;
enum ColorEnum{White, Black};
struct Cell
{
int row;
int col;
Cell(int r, int c): row(r), col(c){}
};
struct Cluster{
bool visited;
vector vec;
Cluster(int i, int j) : visited(false) {
vec.push_back(Cell( i, j));
}
bool isWithinRange(const Cell& a, const Cell& b){
return abs(a.row - b.row) <= 1 ... 阅读全帖 | |
|
r*c
发帖数: 167 | 18 //矩阵求连接图
#include
#include
#include
#include
#include
using namespace std;
enum ColorEnum{White, Black};
struct Cell
{
int row;
int col;
Cell(int r, int c): row(r), col(c){}
};
struct Cluster{
bool visited;
vector vec;
Cluster(int i, int j) : visited(false) {
vec.push_back(Cell( i, j));
}
bool isWithinRange(const Cell& a, const Cell& b){
return abs(a.row - b.row) <= 1 ... 阅读全帖 | |
|
r*c
发帖数: 167 | 19 using System;
using System.Collections.Generic;
namespace WinningGame
{
class Program
{
static void Main(string[] args)
{
int nCount = 0;
int nTotalGames = 1000;
for (int i = 0; i < nTotalGames; i++)
{
Board bd = new Board();
//bd.PrintBoard();
bool bResult = bd.IsWinner();
if (bResult)
{
nCount++;
bd.Print... 阅读全帖 |
|
s********u
发帖数: 1109 | 20 Phone interview，美国人，说话很清楚。不过太健谈了，导致他每次描述问题，说一
大堆，还各种打比方，要搞清楚whole picture真是太费劲了。。
不过人比较nice，希望好运吧。
1.他说warm up一下，说了一大堆，我才搞明白他的意思是，电影里经常有人拿报纸剪
下很多字母，然后拼成一句话去给别人发威胁message之类。（他一上来就说kidnap小
女孩之类，把我吓坏了，以为要写个绑匪和cops的design题。。。。）
然后让我实现一个function，看看能不能拼成一个message。
因为时间过了挺久，我就有点着急，赶紧写了一个hashtable的方法。然后他问我如果
这个message有重复单词怎么办，我才发现自己的bug（只是考虑newspaper里有没有这
个字母，而没有考虑字母的数量），改了一下。
bool compose( string msg, string newspaper){
unordered_map ccnt;
for(auto it = newspaper.begin(); it != newspa... 阅读全帖 |
|
s********u
发帖数: 1109 | 21 Phone interview，美国人，说话很清楚。不过太健谈了，导致他每次描述问题，说一
大堆，还各种打比方，要搞清楚whole picture真是太费劲了。。
不过人比较nice，希望好运吧。
1.他说warm up一下，说了一大堆，我才搞明白他的意思是，电影里经常有人拿报纸剪
下很多字母，然后拼成一句话去给别人发威胁message之类。（他一上来就说kidnap小
女孩之类，把我吓坏了，以为要写个绑匪和cops的design题。。。。）
然后让我实现一个function，看看能不能拼成一个message。
因为时间过了挺久，我就有点着急，赶紧写了一个hashtable的方法。然后他问我如果
这个message有重复单词怎么办，我才发现自己的bug（只是考虑newspaper里有没有这
个字母，而没有考虑字母的数量），改了一下。
bool compose( string msg, string newspaper){
unordered_map ccnt;
for(auto it = newspaper.begin(); it != newspa... 阅读全帖 |
|
w*******e
发帖数: 395 | 22 这道题目非常复杂，首先能想到n*log(n)的算法就不简单，即使想到了，能够在面试的
压力下把逻辑coding出来也非常的难。我感觉电面中，问到这种题目而且要coding的，
如果从没有见过，基本就是不让你过。感觉这种题目适合onsite用。
在知道算法后，我大概花了一些时间，写了如下的代码，基本思路就是楼上讨论的。
1. 首先把所有的interval的起点和终点存进一个vector,并且sort
struct timePoint {
int point;
bool startORend;
int vol;
timePoint(int p, bool s, int v): point(p), startORend(s), vol(v) {}
};
2. 建立一个multiset用来存储还没有结束的volume，同时可以用来判断某个时间段是
否被输入的interval cover了。
3. 然后扫描vector开始建立输出的vector：
1）如果碰到start的点，先检查multiset是否为空，如果是，就是i... 阅读全帖 |
|
w*******e
发帖数: 395 | 23 这道题目非常复杂，首先能想到n*log(n)的算法就不简单，即使想到了，能够在面试的
压力下把逻辑coding出来也非常的难。我感觉电面中，问到这种题目而且要coding的，
如果从没有见过，基本就是不让你过。感觉这种题目适合onsite用。
在知道算法后，我大概花了一些时间，写了如下的代码，基本思路就是楼上讨论的。
1. 首先把所有的interval的起点和终点存进一个vector,并且sort
struct timePoint {
int point;
bool startORend;
int vol;
timePoint(int p, bool s, int v): point(p), startORend(s), vol(v) {}
};
2. 建立一个multiset用来存储还没有结束的volume，同时可以用来判断某个时间段是
否被输入的interval cover了。
3. 然后扫描vector开始建立输出的vector：
1）如果碰到start的点，先检查multiset是否为空，如果是，就是i... 阅读全帖 |
|
r*c
发帖数: 167 | 24 来自主题: JobHunting版 - 上一道小题 The ardendertat.com's code is not always correct. For an example, it will
return 121121121 as the next palin for input 120798387, where there exists a
smaller one: 120808021 .
The following code has no such shortcoming. The key idea is greedy +
heuristic.
#include
#include
#include
#include
#include
using namespace std;
class NextPalinSolution
{
public:
vector NextPalin(const vectorssrc){
vectorsrc(ssrc);
int ... 阅读全帖 |
|
w*****t
发帖数: 485 | 25 minimum rooms:先对进入和退出的点排序 vector>，然后一遍扫描即
可。
关键点：位置相同的点，需要将退出的排在前面
bool comp(const pair &a, const pair &b) {
if (a.first == b.first) return a.second <= b.second; // Caution:
end node first
return a.first < b.first;
}
class Solution {
public:
// [start, end)
// O(NlogN)
// void GetMostIntersect(vector > &intervals, int &point,
int &intersectNum)
int GetMinimumRooms(vector > &intervals)
{
... 阅读全帖 |
|
w*****t
发帖数: 485 | 26 minimum rooms:先对进入和退出的点排序 vector>，然后一遍扫描即
可。
关键点：位置相同的点，需要将退出的排在前面
bool comp(const pair &a, const pair &b) {
if (a.first == b.first) return a.second <= b.second; // Caution:
end node first
return a.first < b.first;
}
class Solution {
public:
// [start, end)
// O(NlogN)
// void GetMostIntersect(vector > &intervals, int &point,
int &intersectNum)
int GetMinimumRooms(vector > &intervals)
{
... 阅读全帖 |
|
w*****t
发帖数: 485 | 27 minimum rooms:先对进入和退出的点排序 vector>，然后一遍扫描即
可。
关键点：位置相同的点，需要将退出的排在前面
bool comp(const pair &a, const pair &b) {
if (a.first == b.first) return a.second <= b.second; // Caution:
end node first
return a.first < b.first;
}
class Solution {
public:
// [start, end)
// O(NlogN)
// void GetMostIntersect(vector > &intervals, int &point,
int &intersectNum)
int GetMinimumRooms(vector > &intervals)
{
... 阅读全帖 |
|
d*****a
发帖数: 3 | 28 贴一下我的代码，为了测试方便，我用的是char*代替的iterator,只要不往回走，意思
应该是一样的。大牛帮忙看看有没有什么问题
bool isDistanceZeroOrOne(const char *a, const char *b)
{
bool insertA = false;
bool insertB = false;
bool replace = false;
bool diff = false;
char preA;
char preB;
while (*a != '\0' && *b != '\0')
{
if (!insertA && !insertB && !replace)
{
if (*a != *b)
{
insertA = true;
insertB = true;
replace = true;
... 阅读全帖 |
|
S****G
发帖数: 3 | 29 关于输赢那个题目，根据版上大牛们的讨论，写了code大家可以一看，主要用了zemel
定理（也可以不用但code会比较messy）。此外，博弈树怎么做这个题，谁有相关资料
可以发来看看。
http://feisyr.blogspot.com/2015/04/zermelos-theorem-game-theory
bool canW(int val1, std::vector &available, int curSum, int & desT){
if (val1 + curSum >= desT) return true;
else{
bool theOtherWin = false;
for (int val2 = 1; val2 < available.size(); ++val2){
if (!available[val2]) continue;
available[val2] = false;
theOtherWin = the... 阅读全帖 |
|
S******t
发帖数: 151 | 30 我贴一个第一题能通过的代码吧：
vector bestA;
int bestLen;
void search(int idx, int sum, int len, vector>>& f,
vector& ret, vector& A) {
//cout << idx << " " << sum << " " << len << endl;
if (idx == 0) {
int lenA = bestA.size();
vector v = ret;
/*
for (int i = 0; i < v.size(); i++)
cout << v[i] << " ";
cout << endl;
*/
if (v.size() < lenA || lenA == 0) {
bestA = v;
return;
... 阅读全帖 |
|
g*********s
发帖数: 1782 | 31 下面这段没问题：
bool op_less(int x, int y) {
return (x < y);
}
bool op_greater(int x, int y) {
return (x > y);
}
bool (*compare_op)(int, int) = is_min ? &op_less : &op_greater;
但是下面这段总是编译失败：
bool (*compare_op)(int, int) = is_min ? &(operator<) : &(operator>);
error: ‘operator<’ not defined
error: ‘operator>’ not defined
这样也不行：
bool (*compare_op)(int, int) = is_min ? &(operator<(int, int)) : &(operator>(int, int));
basic.h:83: error: expected primary-expression before ‘int’
basic.h:83: error: ex... 阅读全帖 |
|
g*********s
发帖数: 1782 | 32 this is my solution casting an unsigned int to an int. but gcc gives me
warning:
string_api.cpp: In function ‘bool overflow(unsigned int, bool, char)’:
string_api.cpp:330: warning: integer overflow in expression
string_api.cpp: In function ‘int str2int(const char*)’:
string_api.cpp:346: warning: integer overflow in expression
explict type casting can fix the warning. but i don't like this solution
very much. anyone has a better alternative?
static
bool overflow(unsigned int val, bool negative, c... 阅读全帖 |
|
j*****u
发帖数: 1133 | 33 写的比较乱，应该还有更clean的
static bool IsMatch(string str, string pattern)
{
if (str == null)
throw new ArgumentNullException("str");
if (string.IsNullOrEmpty(pattern))
throw new ArgumentException("pattern null or emptry.");
return MatchRec(str, pattern, 0, 0);
}
static bool MatchRec(string str, string pattern, int sIndex, int pIndex)
{
if (pIndex == pattern.Length)
{
return sIndex == str.Length;
}
char p = pattern[pIndex];
bool isStar = pIndex < pa... 阅读全帖 |
|
i**********e
发帖数: 1145 | 34 这个解法不对，有 bug.
test case:
{22,11,33,33,44,22,11}
t = 22,
output=
{11 33 33 44 44 22 22}
expected=
{11 33 33 44 11 22 22}
第一题的解：
void shiftArrayEqualsTBack(int num[], int n, int t) {
int total = 0;
for (int i = 0; i < n; i++) {
if (num[i] == t)
total++;
else
num[i-total] = num[i];
}
for (int i = n-total; i < n; i++) {
num[i] = t;
}
}
第二题的解：
const int X_MAX = 4;
const int Y_MAX = 4;
bool validLocation(int x, int y) {
if (x <= -1 || x >= X_MAX || y <= -1 || y >= Y... 阅读全帖 |
|
i**9
发帖数: 351 | 35 看样子把 backtracking algorithm 改造成没有duplicate output有点困难，根据大家
的建议谢了一个简易版的 next_permutation (参考了 PuTTYshell 的 link
http://code.google.com/p/sureinterview/source/browse/src/lib/co
)
void next_permutation(char a[],int n,bool & next,bool &first){
int k=n-2;
if(first){
first = false;
print(a,n);
return;
}
next = false;
for(;k>=0;k--){
if(a[k] < a[k+1]){
next = true;
break;
}
}
if(!next){
return;
}
int l=n-1;
for(;a[k]>=a[l];l--){
}
swap(a[k],a[... 阅读全帖 |
|
f*******t
发帖数: 7549 | 36 这个是很基本的数据结构，建议看一下wiki
我前几天实现了它，只有基本的insert和search，没有对查找child list进行优化，代
码贴出来供参考：
#include
#define MAX_LENGTH 64
using namespace std;
static char buff[MAX_LENGTH];
class Trie {
public:
Trie();
Trie(char value);
bool Insert(const char *str);
bool Search(const char *str) const;
void PrintAll(int pos) const;
private:
char _value;
Trie *_sibling;
Trie *_child;
};
Trie::Trie()
{
_value = 0;
_sibling = NULL;
_child = NULL;
}
Trie::Trie(char value)
... 阅读全帖 |
|
x****1
发帖数: 118 | 37 Google onsite归来，回馈本版，贡献一点面经和体会。记题的能力不是太好，就捡记
得住的说吧。废话不说，直接上题：
Phone screen：
先问了10道左右的小题，都是概念性的。
包括OOP，hashtable，BST，big O问题, 多线程，都是基本知识，没有什么tricky的地方。
有一道程序改错题，程序大概是替换一个字符串里面的pattern，不知道是谁写的，不是很
organized，估计是其他面试的同学的程序，我看了半天虽然觉的code写得很别扭，但也没找出什
么大错，面试官看我卡住了，就说我们继续吧。好在后来的题都答得比较顺利。
接下来又问了问现在做的项目，根据我的项目问了些问题，如server端如何实现session，项目中
有没有多线程，怎么实现。
最后还有5分钟结束的时候，给留了两道coding题，让我明早之前发给他。
一个就是binary search，不用多说了。
另外一个就是如何查找rotated sorted array (这也是很常见的题，因为面试官讲的是
cyclic，所以一开始我理解成{123456456}，后来email问了才明白题意）... 阅读全帖 |
|
l*********y
发帖数: 142 | 38 顺手写了一个，46min整。也没用状态压缩，待会看一下gloomyturkey的code。
#include
#include
#include
#include
#include
#include
#include
|
|
k*****y
发帖数: 744 | 39 请问像 s = "abadabadabadeabecd", p = "*ab?c*d"这样的不用递归怎么办？
我也贴一个，大家帮忙看看，谢谢~
===========================
bool isMatch(const char* s, const char* p) {
if(*s == 0) return !hasNonStar(p);
if(*p == 0) return false;
if(*p != '*'){ //case: *p != '*'
while(*s && *p && *p!='*') {
if(*p!='?' && *p!=*s)
return false;
++p; ++s;
}
return isMatch(s, p);
}
else{ // case: *p == '*'
if(!skipStars(s, p)) return false;
... 阅读全帖 |
|
b******u
发帖数: 81 | 40 谢谢楼上各位的讨论和CODE。很有启发性。
public static string GetExpression(Node node, string parentOp, bool?
isLeft=null)
{
if (node.Operator == null) return node.Operand.ToString();
bool addParenthesis = ToAdd2(node, parentOp, isLeft);
return ((addParenthesis) ? "(" : "") +
GetExpression(node.Left, node.Operator, true) +
node.Operator +
GetExpression(node.Right, node.Operator, false) +
( (addParent... 阅读全帖 |
|
i**********e
发帖数: 1145 | 41 没想明白为什么要用hash_map呢，可以省些空间吗？
用一个table来记录用过的index，然后跳过重复的元素代码如下：
vector > permuteUnique(vector &num) {
sort(num.begin(), num.end());
vector > ret;
int n = num.size();
bool *used = new bool[n];
int *index = new int[n];
memset(used, 0, n*sizeof(bool));
permuteUnique(num, used, index, 0, ret);
delete[] used;
delete[] index;
return ret;
}
void permuteUnique(vector &num, bool used[], int index[],
int pos, vecto... 阅读全帖 |
|
j********e
发帖数: 1192 | 42 我没有说字符集相同就能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... 阅读全帖 |
|
n*******w
发帖数: 687 | 43 1. regex
test过了，要源码的话站内吧。
bool regex(char* str, char* pattern)
if(!str && !pattern) return true;
if(!str || !pattern) retrun false;
if(pattern+1 && *(pattern+1) == '-' && pattern+2) //handle a-z
return *str >= *pattern && *str <= *(pattern+2) && regex(str+1,
pattern+3);
if(pattern+1 && *(pattern+1) == '+')
if(*pattern == '.') //handle .+
bool tmp = false;
char* iter = pattern;
while(iter) //iterater over all possible repeated t... 阅读全帖 |
|
i******e
发帖数: 273 | 44 interleaving string - 我用递归，judge small过了，judge large超时。
怎么才能不超时？用DP吗？如何定义最优子结构？ 谢谢！
class Solution {
public:
bool isInterleave(string s1, int start1, string s2, int start2, string
s3, int start3) {
bool isFirst = false;
bool isSecond = false;
if (start1 == s1.size() && start2 == s2.size() && start3 == s3.size(
))
return true;
if (start3 == s3.size() && (start1 < s1.size() || start2 < s2.size()
))
return false;
if (st... 阅读全帖 |
|
S**I
发帖数: 15689 | 45 ☆─────────────────────────────────────☆
princekim (Prince Kim) 于 (Wed Apr 11 09:32:26 2012, 美东) 提到:
BT树结构, 中间节点是算数运算符(只有+ - * / 4种操作), 叶节点是数字, 要求给出
算数表达式 (要求没有冗余括号)
比如
*
/ \
+ *
/ \ / \
1 2 4 5
表达式 = (1 + 2) * 4 * 5, 不能是 (1+2)*(4*5)
+
/ \
* +
/ \ / \
1 2 4 5
表达式 = 1 * 2 + 4 + 5, 不能是 1 * 2 + (4 + 5)
总之, 这题的难点是 算数表达式不能有冗余括号
我当时的思路: in-order 递归遍历, 遇到 + - 给出左右括号 (但这样就有冗余括号).
面试官指出后, 我说我可以再扫描遍得到的表达式，去除冗余括号 (这也是我情急下
蒙的).
他说不行, ... 阅读全帖 |
|
f*****7
发帖数: 92 | 46 我个人不喜欢swap的方法，自己没法理解
排序，然后跳过重复元素
希望能帮上你
class Solution {
public:
vector > permuteUnique(vector &num) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
sort(num.begin(), num.end());
int len = num.size();
int* path = (int*) malloc(sizeof(int) * len);
bool* visited = (bool*) malloc(sizeof(int) * len);
memset(visited, false, sizeof(bool) * len);
vector > bigList;
int... 阅读全帖 |
|
B********t
发帖数: 147 | 47 题目：找dict中最长的单词，这个单词必须由dict里的单词组成。
bool myfunc(string s1, string s2)
{
return (s1.size() > s2.size());
}
bool findLongestWord_helper(string &s, map &hm)
{
for(int i = 1; i <= s.size(); i++)
{
string sub_f(s, 0, i);
if(hm[sub_f])
{
if(i == s.size())
return true;
string sub_b(s, i, s.size()-i);
if(findLongestWord_helper(sub_b, hm))
return true;
}
}
return false;
}... 阅读全帖 |
|
t****t
发帖数: 6806 | 48 #include
#include
enum search_type { Exact, MaxLess, MinGreater, MaxLessEqual, MinGreaterEqual
};
/* returns "next" element if key was to be inserted. */
template
typename Container::const_iterator
search_place(const Container& array, typename Container::value_type key,
bool ascending)
{
if (ascending) {
return lower_bound(array.begin(), array.end(), key, std::less<
typename Container::value_type>());
} else {
return lower_bou... 阅读全帖 |
|
o******3
发帖数: 91 | 49 决定把题目跟我写的很挫的代码贴上来，有需要的同学可以来看。。。
代码可以过sample test
但是目前还不能过所有的Test
题目：
There are K pegs. Each peg can hold discs in decreasing order of radius when
looked from bottom to top of the peg. There are N discs which have radius 1
to N; Given the initial configuration of the pegs and the final
configuration of the pegs, output the moves required to transform from the
initial to final configuration. You are required to do the transformations
in minimal number of moves.
A move consists of picking the topm... 阅读全帖 |
|
o******3
发帖数: 91 | 50 决定把题目跟我写的很挫的代码贴上来，有需要的同学可以来看。。。
代码可以过sample test
但是目前还不能过所有的Test
题目：
There are K pegs. Each peg can hold discs in decreasing order of radius when
looked from bottom to top of the peg. There are N discs which have radius 1
to N; Given the initial configuration of the pegs and the final
configuration of the pegs, output the moves required to transform from the
initial to final configuration. You are required to do the transformations
in minimal number of moves.
A move consists of picking the topm... 阅读全帖 |
|
