l********t
发帖数: 878 | 1 /*accepted*/
bool equalVector(vector v1, vector v2){
for(int ii = 0; ii < v1.size(); ++ii){
if (v1[ii] != v2[ii]) return false;
}
return true;
}
bool compareVector(vector v1, vector v2){
for(int ii = 0; ii < v1.size(); ++ii){
if (v1[ii] < v2[ii]) return true;
else if (v1[ii] > v2[ii]) return false;
}
return false;
}
class Solution {
public:
vector > fourSum(vect... 阅读全帖 |
|
g***j
发帖数: 1275 | 2 来自主题: JobHunting版 - 问几道题目 1 给任意一个double，如何构建一个hash function to get a key?
2 给一个N，几个质数，打印这些质数的倍数，我给了给所有的N构建flag的solution，
然后他说如果range很大呢，比如1b？ space是一个问题。
3 实现vector的resize问题，请问这个问题的trick是什么？
4 prefix tree, what if the words are very long, total number of words are
small, and the characters are more than 26. How to optimize? |
|
z****o
发帖数: 78 | 3 来自主题: JobHunting版 - 问几道题目
什么时候resize，怎么做均摊分析。
不分叉就不断层；每个节点子树个数动态。 |
|
|
H****s
发帖数: 247 | 5 vector 内存是连续的，不过问题是每次size超过2^n都要resize到2^(n+1), 也就是要
重新分配内存然后copy原来的数据到新分配的内存区域，然后释放老的内存区域。
linked list 最笨，不过没有重新分配内存的问题。
buffer |
|
l****c
发帖数: 782 | 6 我能想到的inplace可能就是用vector， 存在前面，然后resize了
不知道满足2爷的面试要求不 |
|
l*********8
发帖数: 4642 | 7 void convertToMostBeautiful(string & s)
{
unordered_map count;
unordered_map chosen;
for (int i=0; i
count[s[i]]++;
chosen[s[i]] = false;
}
int tail = -1;
for (int i=0; i < s.size(); i++) {
if (chosen[s[i]]) {
count[s[i]]--;
} else {
while (tail >=0 && s[tail] <= s[i] && count[s[tail]] > 1) {
chosen[s[tail]] = false;
count[s[tail--]]--;
}
s[++tail] = s[i];
chosen[s[i]] =... 阅读全帖 |
|
l*********8
发帖数: 4642 | 8 void convertToMostBeautiful(string & s)
{
unordered_map count;
unordered_map chosen;
for (int i=0; i
count[s[i]]++;
chosen[s[i]] = false;
}
int tail = -1;
for (int i=0; i < s.size(); i++) {
if (chosen[s[i]]) {
count[s[i]]--;
} else {
while (tail >=0 && s[tail] <= s[i] && count[s[tail]] > 1) {
chosen[s[tail]] = false;
count[s[tail--]]--;
}
s[++tail] = s[i];
chosen[s[i]] =... 阅读全帖 |
|
c**s
发帖数: 159 | 9 int maximalRectangle(vector > &matrix) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int m = matrix.size();
if (m == 0) {
return 0;
}
int n = matrix[0].size();
vector height;
height.resize(n,0);
stack > st;
int i, j ,answer = 0;
for (i = 0; i < m; ++i) {
for (j = 0; j < n; ++j) {
if (matrix[i][j] == '1') {
++height[j];
... 阅读全帖 |
|
d*s
发帖数: 699 | 10 I think it is yes and no. Yes because indeed the collision can be solved
with hashtable + bst. No because if the collision is so severe that a bst is
needed, probably redesigning the hashfunction or resize the table or using
bst directly is a much better solution. |
|
B********t
发帖数: 147 | 11 找大于target的最小数，写了一个。大家看看有问题没
void findMinOfLarger_Helper(string &s, int target, int *min, string &number)
{
if(atoi(number.c_str()) <= target)
for(int i = 0; i < s.size(); i++)
{
number.push_back(s[i]);
findMinOfLarger_Helper(s, target, min, number);
number.resize(number.size() - 1);
// 我想用pop_back(), 但是好像c++11才支持，可以通过编译选项解决吗
，还是说得用updated的g++
}
else
if(atoi(number.c_str()) < *min)
*min = atoi(numb... 阅读全帖 |
|
j*****y
发帖数: 1071 | 12 void sumOfNodes(TreeNode * root, vector &A, int &sum)
{
if(root->child.size() == 0)
{
int sub_sum = 0;
for(int i = 0; i < A.size() ; ++i)
{
sub_sum += 10 * sub_sum + A[i];
}
sub_sum += 10 * sub_sum + root->val;
sum += sub_sum;
return;
}
for(int i = 0; i < root->child.size(); ++i)
... 阅读全帖 |
|
s******c
发帖数: 99 | 13 问题在于recursive call的时候，你每次都重新生成left_path和right_path，然后拷
贝整个path到里面，这样就会慢，不需要这两个额外的arraylist,就用path一个就可，
backtrack就是你走完left child和 right child 之后都回到parent就可，其实就是把
path最后一个element去掉就行。
public class Solution {
public ArrayList> pathSum(TreeNode root, int sum) {
// Start typing your Java solution below
// DO NOT write main() function
ArrayList> results=new ArrayList
Integer>>();
ArrayList path=new ArrayList<... 阅读全帖 |
|
A***o
发帖数: 358 | 14 Like this?
sort U = {n_0 .... n_99}, n_i\in {1 , 2, 3,..., 200}, and n_i =\= n_j, if i=
\=j
vector S;
S.resize(200,-1);
for i = 0...99
S[ U[i] ] = U[i]
linear scan S, generate the sorted array |
|
o******3
发帖数: 91 | 15 决定把题目跟我写的很挫的代码贴上来，有需要的同学可以来看。。。
代码可以过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 | 16 决定把题目跟我写的很挫的代码贴上来，有需要的同学可以来看。。。
代码可以过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... 阅读全帖 |
|
j*****y
发帖数: 1071 | 17 bless
第一题
string itos(int n)
{
string s;
s.append(1, '0' + n % 10);
n = n / 10;
while(n > 0)
{
s.insert(0, 1, '0' + n % 10);
n = n / 10;
}
return s;
}
void change(string &s)
{
int i = 0;
int index = 0;
while(i < s.length())
{
int j = i;
while(j < s.length() - 1 && s[j] == s[j + 1])
{
++j;
}... 阅读全帖 |
|
s**x
发帖数: 405 | 18 难看是难看了点，但是避免字符串复制
如果不传引用就可以直接传 sample+"(" |
|
|
s********u
发帖数: 1109 | 20 挖个坟，这个readline的题目，搜了一下，好像应该是这个意思吧：
用一个buffer来存字符流，如果中间有换行，那么将这一行返回成一个字符串输出，但
是这个buffer里面的东西继续保留，下次readline（）再输出；
如果一行非常长，那么可能需要用到几次read（），来拼出这个完整的line。
/*Implement a function char* readLine(); which returns single lines from a
buffer.
To read the buffer, you can makes use of a function int read(char* buf, int
len) which fills buf with upto len chars and returns the actual number of
chars filled in. Function readLine can be called as many times as desired.
If there is no valid data or newline ter... 阅读全帖 |
|
d**********x
发帖数: 4083 | 21 如果你不是一次删完的话，但是要从尾部删，直接resize即可，循环和function call
都是有cost的，而且写着也麻烦不是
其实clear和直接析构的差别在于vector本身是否需要析构，大头在哪边要看你的元素
有没有析构的cost
overhead? |
|
d**********x
发帖数: 4083 | 22 恩，destruct的时候有两部分cost
1是vector本身的内存
2是各个元素的destruct
如果元素都是int啊char之类的，那大头基本在vector那边，用resize好了 |
|
g********E
发帖数: 178 | 23 1，第一层循环的时候跳过重复的；
2，第二层循环从两头跳过循环的；
vector< vector > threeSum(vector &num){
int n = num.size();
vector< vector > res;
vector cur;
sort(num.begin(), num.end());
for(int i = 0; i < n-2; i++){
if(i > 0 && num[i] == num[i-1]) continue;
cur.push_back(num[i]);
int start = i + 1, end = n - 1;
while(start < end){
if(start > i+1 && num[start] == num[start-1]) {
start++; continue;
... 阅读全帖 |
|
t****e
发帖数: 279 | 24 What is iterator invalidation?
Answer:
Insertion
Sequence containers
vector: all iterators and references before the point of insertion are
unaffected, unless the new container size is greater than the previous
capacity (in which case all iterators and references are invalidated) [23.2.
4.3/1]
deque: all iterators and references are invalidated, unless the inserted
member is at an end (front or back) of the deque (in which case all
iterators are invalidated, but references to elements are unaffe... 阅读全帖 |
|
d**********x
发帖数: 4083 | 25 我想了一会儿其他可能性，比如说什么异或，rotation之类的
感觉确实是没有多余的空间可以存东西。
所以要么是
1.字符的范围有限制，所以我们可以取一个bit，或者更少的空间做标记什么的
2.考虑到这是个c++函数，可以用很tricky的手段，即先设定字符串的capacity=str1.
length+str2.length，然后resize到str1.length，再把str1和str2的内容填进去。如
果有人想说G不会出这种恶心题目，请参考我的签名档…… |
|
C****y
发帖数: 581 | 26 我查了这个Amortized Time worst case可以是o(n)， 如果要resize arraylist
的话 |
|
r*********n
发帖数: 4553 | 27 来自主题: JobHunting版 - 问一道题~ 贴一个代码。这个复杂度是O（N^2），原因是set::iterator是bidirectional，
所以下面这一行是linear time：
auto it = advance(num.begin(), A[i])
如果要得到O(NlogN)，需要set提供 iterator select(int rank) 这个API，
auto it = num.select(A[i])
其实BST稍微改一下就可以实现select（可惜STL set没这个method），复杂度是O(logN
)。
vector original_arr(const vector& A){
vector ret;
if( A.empty() ) return ret;
ret.resize(A.size());
set num;
for(int i = 1; i <= A.size(); i++){
num.insert(i);
}
for(int i = 0; i < A.size(); i... 阅读全帖 |
|
h****y
发帖数: 137 | 28 double find_kth_largest_unknown_length(istringstream &sin, int k)
{
vector vec;
double x;
while (sin >> x)
{
vec.emplace_back(x);
if (vec.size() == (k << 1) - 1)
{
nth_element(vec.begin(), vec.begin() + k - 1, vec.end(), greater
());
vec.resize(k);
}
}
nth_element(vec.begin(), vec.begin()+k-1, vec.end(), greater());
return vec[k-1];
} |
|
h****y
发帖数: 137 | 29 double find_kth_largest_unknown_length(istringstream &sin, int k)
{
vector vec;
double x;
while (sin >> x)
{
vec.emplace_back(x);
if (vec.size() == (k << 1) - 1)
{
nth_element(vec.begin(), vec.begin() + k - 1, vec.end(), greater
());
vec.resize(k);
}
}
nth_element(vec.begin(), vec.begin()+k-1, vec.end(), greater());
return vec[k-1];
} |
|
s*w
发帖数: 729 | 30 改 string 的话，貌似应该 str.resize(i); |
|
s********u
发帖数: 1109 | 31 首先lz你用的应该是老版本的书，新版都没这道题。
我看到题目之后的思路是，先sort，然后是用两个index或者两个指针，一个i匀速往后
遍历，另一个j匀速运动且碰到重复就往后跳。
str[i++] = str[j++];最后根据i的位置resize string。
应该没有o(n)的做法吧，除非用bitset。
每次碰到重复都删除的话，哪怕是用hash table存，看起来是一次遍历O(n)，但挪动起
来相当于是O（n^2)了。所以一定用覆盖来做这个事情，最后一起把尾巴去掉就行。 |
|
s********u
发帖数: 1109 | 32 用数组也可以啊，只是稍微麻烦点，要考虑resize的问题。 |
|
s********u
发帖数: 1109 | 33 这是readline那个题我参照网上的代码写的。比这个要复杂一些，因为一个line的字符
是不确定的。
#define MAX_LEN 4096
int read(char* buf, int len);
char *readLine(){
static bool EOF = false;
char *str = NULL;
int i, size = 0;
static int currentPos = MAX_LEN;
static char* buffer = new char[MAX_LEN];
while(!EOF || currentPos != MAX_LEN ){
// buffer is not empty, handle buffer first
if(currentPos != MAX_LEN){
for(i = currentPos; i < MAX_LEN; i++)
... 阅读全帖 |
|
s********u
发帖数: 1109 | 34 老题了吧，不过老要写错，尤其是那个read4写read的更恶心。
#define MAX_LEN 4096
int read(char* buf, int len);
char *readLine(){
static bool EOF = false;
char *str = NULL;
int i, size = 0;
static int currentPos = MAX_LEN;
static char* buffer = new char[MAX_LEN];
while(!EOF || currentPos != MAX_LEN ){
// buffer is not empty, handle buffer first
if(currentPos != MAX_LEN){
for(i = currentPos; i < MAX_LEN; i++)
if( buffer[i] ==... 阅读全帖 |
|
y****k
发帖数: 71 | 35 【 以下文字转载自 Programming 讨论区 】
发信人: ystdpk (ystdpk), 信区: Programming
标 题: c++ thread 求助
发信站: BBS 未名空间站 (Fri Jan 31 21:12:20 2014, 美东)
有一个50 million 行的文本。每行四列数字。
要求每行求一个特殊函数的值，把此值输出为第五列。次函数的求值所花的时间可能很
快，如果四个数比较小， 也可能要花到10几到100倍的时间如果数比较大。
想用36个boost thread。
有没有人能提供一个boost thread 的代码。谢谢了。
我写了一个下面的，但是cpu浪费比较严重，有的thread 结束早，有的结束慢。而且不
知道2000行一个thread是不是好的选择。
int batchSize = 2000;
int num_of_lines = 50100100;
bool end_of_file = false;
int pstart = 0;
boost::thread_group io;
while( ! end_of_file )
{
b... 阅读全帖 |
|
|
|
q********c
发帖数: 1774 | 38 来自主题: JobHunting版 - 一道面试题 直接用数组：
class Solution {
public:
vector plusOne(vector &digits) {
int len = digits.size();
int i = len-1;
int sum;
do {
sum = digits[i] + 1;
digits[i] = sum==10?0:sum;
i--;
}while(i>=0 && sum==10);
if(sum==10) {
digits.resize(len+1);
for(int k = len-1; k >=0; k--)
digits[k+1] = digits[k];
digits[0] = 1;
}
return digits;
}
}; |
|
l*********8
发帖数: 4642 | 39 void removeDup(string & str) {
int tail = -1;
for (int i = 0; i < str.size(); ) {
if (tail < 0 || str[i] != str[tail]) {
str[++tail] = str[i++];
} else {
--tail;
while(str[i] == str[tail + 1])
++i;
}
}
str.resize(tail+1);
} |
|
a*****y
发帖数: 22 | 40 看了大家的回复，得到启发，思路如下：
遍历两遍：第一遍确定如下情况：
1， 新区间可以被原有的某个区间包含，直接返回
2， 新区间与原有的区间都不相交，push_back，返回
3， 相交，又分为两种情况：（1）新区间完全覆盖原有某区间，将改区间置为无效（
opening > close） （2）部分相交：更新新区间的头或尾，将原有的那个区间置为无效
第二遍遍历，删掉标记为无效的区间
总时间复杂度为O（n）
struct Interval {
int opening;
int close;
};
void MergeInterval(std::vector& org, Interval new_interval) {
int n = org.size();
if (n == 0) {
return;
}
bool is_intersected = false;
for (int i = 0; i < n; ++i) {
if (org[i].opening <= new_interval.opening) {
... 阅读全帖 |
|
t**r
发帖数: 3428 | 41 class Solution {
public:
vector > fourSum(vector &num, int target) {
int n = num.size();
vector > ret;
sort(num.begin(), num.end());
for (int i = 0; i < n; ++i) {
if (i != 0 && num[i] == num[i - 1]) continue;
for (int j = n - 1; j > i; --j) {
if (j != n - 1 && num[j] == num[j + 1]) continue;
int L = i + 1, R = j - 1;
while (L < R) {
int sum ... 阅读全帖 |
|
a********r
发帖数: 217 | 42 在leetcode上总是TLE, 基本想法是：建一个二维表（vector>）vvi记录
所有palindrome的位置，如果s[i]是一个palindrome的开头，则vvi[i]的vector记录所
有的下一个palindrome的开始位置。Vector dp记录最小分割数，dp[i]是sub
string s[i...n-]的最小分割数。从右到左扫描vvi,就可以建立dp[].最后输出dp[0].
这个方法应该是O(n^2) time 和 O(n^2) space.
int minCut(string s) {
int n=s.size();
if(s.size()==1) return 0;
if(setTable(s)) return 0;
vector dp(n);// dp[i] store the minCut for s[i...n-1]
dp[n-1]=0;
for(int i=n-2; i>=0;i--){
dp[i]=n-i-1;
for(auto... 阅读全帖 |
|
g********t
发帖数: 212 | 43 额 那道题目的话，完整是给你int read_buffer(char*buffer, int len)，返回值是-1
或者填好的buffer的大小。如果不是-1需要可能再次调用，再取下一段。
我讨论了这些内容:
1. read_line()的返回值怎么传: 在read_line()里面分配好，还是api调用者分配好把
大小传进来? 如果用c++既有的string类，跨函数体的时候复制是怎么做的，内部内存
表示是怎样的？这些实现在这个scenario里面会有哪些缺陷？在这个scenario里会产生
内存fragmentation吗？有没有办法用一个自己管理的内存池减少fragmentation？当然
，难的设计只是提一下，也没有时间写出来。
2. 然后我用了一个read_line()自己的可以复用的固定大小buffer，一个指针指到上次
自己的内部buffer用了多少了，再遇到read_line就找下一个'n',如果用完了就把
buffer刷新。还有一些边界判定，比如上次取下来的buffer没有取满之类的。
3. 最后简化解是，最后写代码就用了unique_ptr, 里面... 阅读全帖 |
|
g********t
发帖数: 212 | 44 额 那道题目的话，完整是给你int read_buffer(char*buffer, int len)，返回值是-1
或者填好的buffer的大小。如果不是-1需要可能再次调用，再取下一段。
我讨论了这些内容:
1. read_line()的返回值怎么传: 在read_line()里面分配好，还是api调用者分配好把
大小传进来? 如果用c++既有的string类，跨函数体的时候复制是怎么做的，内部内存
表示是怎样的？这些实现在这个scenario里面会有哪些缺陷？在这个scenario里会产生
内存fragmentation吗？有没有办法用一个自己管理的内存池减少fragmentation？当然
，难的设计只是提一下，也没有时间写出来。
2. 然后我用了一个read_line()自己的可以复用的固定大小buffer，一个指针指到上次
自己的内部buffer用了多少了，再遇到read_line就找下一个'n',如果用完了就把
buffer刷新。还有一些边界判定，比如上次取下来的buffer没有取满之类的。
3. 最后简化解是，最后写代码就用了unique_ptr, 里面... 阅读全帖 |
|
c****a
发帖数: 50 | 45 请教大牛，被问到这个问题怎么回答
一般情况是O(1), resize的时候是O(n) ? |
|
a***e
发帖数: 413 | 46 为什么要j>=prevSize？总是不理解这一点，多谢！
if (i==0||S[i]!=S[i-1]||j>=prevSize)
https://oj.leetcode.com/problems/subsets-ii/
Given a collection of integers that might contain duplicates, S, return all
possible subsets.
Note:
vector > subsetsWithDup(vector &S) {
vector> ret;
int n = S.size();
if (n==0) return ret;
sort(S.begin(),S.end());
ret.resize(1);
int prevSize = 0;
for (int i=0; i
{
... 阅读全帖 |
|
A*****e
发帖数: 26 | 47 two c++ positions
1. interviewer: one Korean guy
C++ basics: public, private, struct, etc. 秒掉
C++ : the member functions of map,list, vector, how to resize vector, how
to delete the middle element in a given list, time complexity。 Nothing
difficult for me. list in stl is actually doubly linked list, so remove one
member would take O(1) time, but the reviewer seemed to disagree. Ask is
there a size member available for list in STL. A: i think so. I: er..ok (
seems he did not know that)
Programm... 阅读全帖 |
|
g*****g
发帖数: 34805 | 48 #3, hashtable + array, swap the last element with the deleted one to make
removal O(1). addition is O(1) if the initial size is big enough and you don
't need resize, as is the case with hashtable. |
|
B********4
发帖数: 7156 | 49 能否展开说说hashtable + array怎么存放数据的？怎么决定（k,v)的？
为啥3个方法都是O(1)？
先谢谢了
removal O(1). addition is O(1) if the initial size is big enough and you don
't need resize, as is the case with hashtable. |
|
g*****g
发帖数: 34805 | 50 You have a hashtable with keys as your server id and values for the
positions in the array. You just keep
the size of the array and every time you delete something, you swap the last
element in the array with the deleted one and reduced the size by 1, you
don't actually need to resize the array physically.
With a continuous array, obviously random access stays at O(1).
don |
|
