由买买提看人间百态

topics

全部话题 - 话题: num
首页 上页 1 2 3 4 5 6 7 8 9 10 下页 末页 (共10页)
w****a
发帖数: 710
1
来自主题: JobHunting版 - 被鄙视了, c++基础知识
template
struct Num
{
enum { Result = Num::Result + 1 };
static void print(){
printf("%d ",Result);
Num::print();
};
};
template <>
struct Num<1>
{
enum { Result = 1 };
static void print(){
printf("%d ",Result);
Num<2>::print();
};
};
template <>
struct Num<10>
{
enum { Result = 10 };
static void print(){
printf("%d ",Result);
};
};
////////////
Num<1> x;
x.print();
w****a
发帖数: 710
2
来自主题: JobHunting版 - 被鄙视了, c++基础知识
template
struct Num
{
enum { Result = Num::Result + 1 };
static void print(){
printf("%d ",Result);
Num::print();
};
};
template <>
struct Num<1>
{
enum { Result = 1 };
static void print(){
printf("%d ",Result);
Num<2>::print();
};
};
template <>
struct Num<10>
{
enum { Result = 10 };
static void print(){
printf("%d ",Result);
};
};
////////////
Num<1> x;
x.print();
j*****y
发帖数: 1071
3
来自主题: JobHunting版 - 新鲜SDET M onsite 面经 [update offer]
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;
... 阅读全帖
g***j
发帖数: 1275
4
来自主题: JobHunting版 - Longest Consecutive Sequence 问题释疑
Given an unsorted array of integers, find the length of the longest
consecutive elements sequence.
For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length
Your algorithm should run in O(n) complexity.
我在网上看到了几段code,用到了set或者map,每次要在set或者map里面找到,然后删
掉,我想问,这样的code时间是n么?find in a set难道不是logn么?当然也有用到
map的,我觉得找元素都是logn啊,那么最终的时间就是nlogn啊,比如如下code
class Solution {
public:
int longestConsecutive(vector &num) {
// Start typing... 阅读全帖
r**h
发帖数: 1288
5
不需要ls这么复杂啊,1D的经典多重背包问题
a = [1, 3, 5, 7, 9]
num = [9999 for i in range(30)]
num[0] = 0
for coin in a:
i = coin
while i<30:
if num[i-coin]+1 < num[i]:
num[i] = num[i-coin]+1
i = i+1
print(num)
a*****a
发帖数: 46
6
来自主题: JobHunting版 - leetcode上最搞笑的是这题
Code readability也很重要。
很多细节也会影响程序的效率。比如s.substring(2)每次都会生成一个新的string,无
形中就增加了时间和空间复杂度,recursion也会增加时间和空间复杂度。这都是可以
优化的地方。
1: public String intToRoman(int num) {
2: int[] nums = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
3: String[] symbols = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "
IX", "V", "IV", "I"};
4: StringBuilder res = new StringBuilder();
5: int i=0;
6: while (num>0) {
7: int times = num / nums[i];
8: num -= nums[i]*times;
9: ... 阅读全帖
d******e
发帖数: 164
7
来自主题: JobHunting版 - 我觉得valid number其实并不难
抛个砖:
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 ... 阅读全帖
s***5
发帖数: 2136
8
来自主题: JobHunting版 - 请教一道题
在input integer加个1,再把26进制得到的div和module,都减掉1,搞定。
string int2str(int num) {
if(num < 0) return "";
string str;
char c;
while(num >= 26) {
int rem = (num+1) % 26;
if(rem == 0)
str = 'Z' + str;
else {
c = rem-1+'A';
str = c + str;
}
num = (num+1)/26-1;
}
c = num + 'A';
return c+str;
}
p****o
发帖数: 46
9
oj 在{0, 1}测试的结果是{{1}, {0,1}, {1,0}}
但我自己运行打印出来是{{0,1}, {1,0}}
请大伙帮忙看看。
代码如下
#include "stdio.h"
#include
using namespace std;
class Solution {
public:
vector > permute(vector &num) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector v(0);
doPermute(v, num);
return vv;
}

void doPermute(vector &v, vector &num) {
if(num.empty()) {
vv.push_back(v); ... 阅读全帖
J**9
发帖数: 835
10
check whether it can be equal 1/2 + 1/4 + 1/8 + ...
see /// below
/**
* Given a real number between 0 and 1 (e.g., 0.72) that is passed in as a
double, print
* the binary representation. If the number c*annot be represented
accurately in binary
* with at most 32 characters, print "ERROR."
* hkBitsDoubleBits(): 0.720000 = 0.101110000101000111101011100001
* hkBitsDoubleBits(): 0.687500 = 0.1011
* hkBitsDoubleBits(): 0.500000 = 0.1
*/
char *hkBitsDoubleBits(double num, char *str, int maxSize)
{
... 阅读全帖
l*********8
发帖数: 4642
11
来自主题: JobHunting版 - 上一道小题
他的程序是有问题,改了改:
def nextPalindrome(num):
oddDigits = (len(str(num)) %2 != 0)
leftHalf = getLeftHalf(num)
newNum = getPalin(leftHalf, oddDigits)
if newNum > num:
return newNum
nextLeftHalf = str(int(leftHalf) + 1)
if len(nextLeftHalf) == len(leftHalf):
return getPalin(nextLeftHalf, oddDigits)
if oddDigits:
return getPalin(nextLeftHalf[:-1], 0)
else:
return getPalin(nextLeftHalf, 1)
def getLeftHalf(num):
return str(num)[:(len(str(nu... 阅读全帖
c****u
发帖数: 59
12
来自主题: JobHunting版 - G家onsite一题
int MaxSumCircularSubArray(vector &num) {
int sum;
int max_v, max_c;
int min_v, min_c;
if (num.size() < 1) return 0;
max_c = min_c = max_v = min_v = sum = num[0];
for (int i = 1;i < num.size();++i) {
sum += num[i];
if (max_c <= 0) max_c = 0;
if (min_c >= 0) min_c = 0;
max_c += num[i];
min_c += num[i];
max_v = std::max(max_v, max_c);
min_v = std::min(min_v, min_c);
}
return std::max(max_v, sum - min_v);
}
f******s
发帖数: 659
13
//use recursion
boolean isPalindrome(int num){
if(num<0) return false;
if(num<10) return true;

int length = (int) Math.log10(num) +1; //how many digits?

//compare the 1st and last digit
if (num/((int) Math.pow(10, length-1))!=num%10)
return false;

//chop off the 1st and last digit
return isPalindrome (((int)(num%(Math.pow(10, length-1))))/10);
}
S********0
发帖数: 5749
14
也贴个自己的code, 跟前面一个童鞋说的类似,碰见扩号或者等号就递归,这样子也
很容易扩展到乘号或者除号.
double solve(string str, double x) {
int x_coeff, y_coeff, con;
int size = str.size();
x_coeff = y_coeff = con = 0;

getCoeff(str, 0, x_coeff, y_coeff, con);
if (y_coeff != 0) {
double y = -(con + x_coeff*x) / y_coeff;
return y;
}
else return DBL_MAX;
}
int getCoeff(string &str, int start, int &x_coeff, int &y_coeff, int &con) {
int end;
int num;
int digit_flag = 0;
int sign ... 阅读全帖
a***e
发帖数: 413
15
来自主题: JobHunting版 - 有人同看First Missing Positive 吗?
Given an unsorted integer array, find the first missing positive integer.
For example,
Given [1,2,0] return 3,
and [3,4,-1,1] return 2.
Your algorithm should run in O(n) time and uses constant space.
我自己想的答案通过了OJ,但用的那个vector p(max+1,0);是不是会被说不是
constant space?其实我第一个想法就是最多是一个 INT_MAX大小的数组,不也是
constant space么?
class Solution {
public:
int firstMissingPositive(int A[], int n) {
int min = INT_MAX, max = INT_MIN;

for (int i=0; i {
if (A[i]<... 阅读全帖
s***c
发帖数: 639
16
得把bucket变大,这下可以过了
class Solution {
public:
int maximumGap(vector &num) {
unordered_set hh;
int res(0);
int vmax(-1), vmin(INT_MAX);
for(int i=0; i hh.insert(num[i]);
vmax=std::max(vmax, num[i]);
vmin=std::min(vmin, num[i]);
}
int hsz=hh.size();
if(hsz<=1) return res;
double dbin = double(vmax-vmin)/(hsz-1);

vector minvec(hsz, INT_MAX), maxvec(hs... 阅读全帖
d****n
发帖数: 397
17
来自主题: JobHunting版 - 请教一道题 median ii
用两个heap.一个max heap,一个min heap, maxheap size = min heap size 或者
maxheap size = minheapsize + 1.
java implementation
public class Solution {
/**
* @param nums: A list of integers.
* @return: the median of numbers
*/
public int[] medianII(int[] nums) {
// write your code here
PriorityQueue pmin = new PriorityQueue ();
PriorityQueue pmax = new PriorityQueue (10, new
MaxComparator());
int i, l = nums.l... 阅读全帖
C****t
发帖数: 53
18
来自主题: JobHunting版 - 一道老题
Q1.
def swap(nums):
n = len(nums)
for i in range(n):
tmp = origIdx(i, n//2)
while tmp < i: tmp = origIdx(tmp, n//2)
nums[i], nums[tmp] = nums[tmp], nums[i]
print(nums)
def origIdx(cur, n):
return (cur%2)*n + cur//2
t****o
发帖数: 94
19
这个呢?随便写的,没test过。
bool CanAlwaysWin(vector& num, vector& used, int target)
{
if (target <= 0) return false;
for (int i = 0; i < num.size(); i++)
{
if (used[i]) continue;
if (num[i] >= target) return true;
used[i] = true;
bool win_anyway = true;
for (int j = 0; j < num.size(); j++)
{
if (used[j]) continue;
used[j] = true;
if (!CanAlwaysWin(num, used, target - num[i] - num[j]))
... 阅读全帖
l******s
发帖数: 3045
20
来自主题: JobHunting版 - 贡献一道面试题
private IList singles(int[] nums){
ISet result = new HashSet();
ISet multi = new HashSet();
for(int i = 0; i < nums.Length; i++)
if(result.Contains(nums[i])){
result.Remove(nums[i]);
multi.Add(nums[i]);
}
else if (!multi.Contains(nums[i]))
result.Add(nums[i]);
return result.ToList();
}
S*******C
发帖数: 822
21
来自主题: JobHunting版 - 问一个多次遇到的面试题
//return the closet number
public double closestNumber(double[] nums, double target) {
if (nums == null || nums.length == 0) {
return -1;
}
int low = 0, high = nums.length - 1;
while (low < high) {
int mid = low + (high - low) / 2;
double diff1 = Math.abs(nums[mid] - target);
double diff2 = Math.abs(nums[mid + 1] - target);
if (diff1 >= diff2) {
low = mid + 1;
} else {
... 阅读全帖
n*****x
发帖数: 686
22
来自主题: JobHunting版 - 贡献一个最近电面题目
维护一个stack,里面存index。还要记录当前见过的最大值。开始扫数组
比当前最大大就push,比top指的数字小就pop,不然就continue。扫一边数组。
然后开始pop stack,index间隔不是1的就是你要找到的,最后一个元素和-1比。top需
要是n-1。应该算On
vector solve(vector& nums){
vector res(2,-1);
int n = nums.size();
if (n==0) return res;
stack stk;
stk.push(-1);
int max_sofar = nums[0];
for (int i=0; i while (stk.size()!=1 && nums[stk.top()]>nums[i]) stk.pop();
if (nums[i]>=max_sofar){
max_sofar = nums[i];
... 阅读全帖
d***a
发帖数: 316
23
没找到 Python 版,只能在这里问问了,谢谢。
问题:Find the sum of all the primes below two million.
我的方法,一个for loop,从 1 到 2M,依次判断是否prime,是则累加。
(当然,请教更好的算法,谢谢。)
同样的想法,分别用 Python 和 Java 实现,但结果差了 1。
Python给出 142913828923, 而Java是142913828922
提交后看答案是 Java 对。
以下 Python code
# Find the sum of all the primes below two million.
import math
def IsPrime(num):
if (num == 2 or num == 3 or num == 5 or num == 7):
return True
elif (num%2 == 0 or num%3 == 0):
return False
else:
for i in range(5, m
l********a
发帖数: 1154
j*****g
发帖数: 16
25
来自主题: Programming版 - vector的析构问题
摸黑写了一下,可是编译(g++ A.cpp)出错, 就是this->children->parent
A.cpp:20: error: base operand of ‘->’ has non-pointer type ‘std::vector *, std::allocator >’
A.cpp
//******************************
1 #include
2 class A
3 {
4 public:
5 int num;
6 A *parent;
7 std::vector children;
8 public:
9 A(){
10 this->num=3;
11 this->parent=0;
12 for (int i=0;inum;++i)
13 {
14 this->children.push_back(new A(this,this->num));
15 }
16 }
17 A(A *...
阅读全帖
l********a
发帖数: 1154
26
来自主题: Programming版 - vector的析构问题
不好意思,原class是个非常大的类,为了说问题简单,
我手打的时候,把带参数的构造函数那句写错了,应该是
this->parent = a;
不是this->children->parent = a;
下面的测试用例复制可以编译运行的
#include
#include
using namespace std;
#include
class A
{
public:
int num;
A *parent;
vector children;
// 无参数调用
A(void)
{
this->num = 3;
this->parent = 0;
for (int i=0;inum;++i)
this->children.push_back(new A(this,this->num-1));
}
// 子构造函数,被上面的无参函数调用
A(A *a,int n)
...
阅读全帖
l******s
发帖数: 3045
27
来自主题: Programming版 - 强迫症爱好者进来做题了
再强迫
public maxAny(params int[] nums){
for(int i = 0; i < nums.Length; i++)
nums[0] = nusm[i] > nums[0] : nums[i] ? nums[0];
return nums[0];
}
a****n
发帖数: 1887
28
来自主题: JobHunting版 - 聊聊黑名单吧
假设数组为int sum[N], 需要分为M段
int foo()
{
int maxv = accumulate(&num[0],&num[N],0);
int minv = *max_element(&num[0],&num[N]);
int midv;
while(minv < maxv)
{
midv = (minv + maxv)>>1;
int k = 0;
int sum = 0;
for (int i = 0; i < N; ++i)
{
sum += num[i];
if (sum > midv)
{
sum = num[i];
++k;
}
}
if (k < M) maxv = midv;
else minv = midv + 1;
s*******e
发帖数: 93
29
来自主题: JobHunting版 - 问一个关于merge sort的小细节
所以你说的sentinel的意思是左右两个array中一个array走到尽头之后,append一个很大的数在最尾端
确保之后都从另外一个array取数?
这样看的话,sentinel好像不是必须的啊
这一段代码:
for (int i=0; i if (left[pl] else num[i] = right[pr++];
是否可以改成
for (int i=0; i {
if (pl>=nl) num[i]=right[pr++];
else if (pr>=nr) num[i]=left[pl++];
else if (left[pl] else num[i] = right[pr++];
}

do
P********l
发帖数: 452
30
来自主题: JobHunting版 - Facebook Hacker Cup
public void test() {
int num = 2147483646;
// num = 100;
num = 2147395601;
Set hs = new HashSet((int) (Math.sqrt(num)) + 100);
for (int i = 0; i < Math.sqrt(num); i++) {
hs.add(i * i);
}
for (Integer i : hs) {
int j = num - i;
if (j < i)
continue;
if (hs.contains(j)) {
System.out.println(i + ", " + j);
}
}
}
21473956... 阅读全帖
w*******s
发帖数: 96
31
check num = 00100100(binary) in your case:
you will only get y = 001001.
It looks ugly, but should work.
bool judge(int num){
if (num < 0) return false;
int i, x, y;
int bitsize = sizeof(num)*8;
for (i = 0, x = num, y = 0; i< bitsize ; x >>= 1,i++)
y = (y << 1) | (x & 1);
return (y == num);
}
l*****a
发帖数: 14598
32
来自主题: JobHunting版 - G四次电面面经
bool IsPalindrome(int i) {
if(i < 0)
return false;
int num = i;
int reversed = 0;
while(num) {
reversed *= 10;
reversed += num % 10;
if (num==reversed) return true;
num /= 10;
if (num==reversed) return true;
}
return false;
}
f*******t
发帖数: 7549
33
来自主题: JobHunting版 - find k missing numbers in range [0, N].
#include
#include
bool isSet(char *bitarray, int num)
{
int index = num / 8;
int offset = num % 8;
return bitarray[index] & (char)(1 << offset);
}
void set(char *bitarray, int num)
{
int index = num / 8;
int offset = num % 8;
bitarray[index] |= (char)(1 << offset);
}
void printMissingNum(int *array, int arraysize, int N)
{
int bitarraysize = (N + 7) / 8;
char *bitarray = (char*)calloc(bitarraysize, 1);
for(int i = 0; i < arraysize; ++i) {
... 阅读全帖
S****h
发帖数: 115
34
最近做题做的有点晕的感觉... 这题我想的对么?
method1:
public boolean isPower2(int num){
if(num <= 0)
return false;
int mask = 1;
for(int i = 0; i <31; i++){
mask = mask << 1;
if(mask == num)
return true;
else if(mask > num)
return false;
}
return false;
}
method2:
public boolean isPower2(int num){
//skip
switch(num){
case 1:
... 阅读全帖
k*****y
发帖数: 744
35
来自主题: JobHunting版 - 罗马数字转换成十进制
string intToRoman(int num) {
char Roman[] = {'I', //1
'V', //5
'X', //10
'L', //50
'C', //100
'D', //500
'M'}; //1000
string ans;
if(num >= 4000 || num <= 0) return ans;
stack digits;
while(num){
digits.push(num%10);
num/=10;
}
int offset=digits.size()*2-2;
while(digits.size()){
int lastDigit = dig... 阅读全帖
p*****2
发帖数: 21240
36
来自主题: JobHunting版 - 面经from M and A
我没有加一,写了一个,对不对呀。感觉这东西没写过,面试的时候很难写对呀。
String intToStr(int num)
{
if (num == 0)
return "A";
StringBuffer sb = new StringBuffer();
while (num > 0)
{
int a = num % 26;
if (sb.length() == 0)
sb.append((char) ('A' + a));
else
{
if (a == 0)
{
sb.append('Z');
num -= 26;
}
else
... 阅读全帖
Q*******e
发帖数: 939
37
来自主题: JobHunting版 - Amazon电面两题
def prime_factor(num):
factor = 2
st = "%d 's factor:" % num
while factor <= num:
if num % factor == 0 :
st = st + ' ' + str(factor)
num = num / factor
else:
factor = factor + 1
print st
prime_factor(17)
prime_factor(20)
prime_factor(200)
prime_factor(217)
~
E*******0
发帖数: 465
38
来自主题: JobHunting版 - 实现next_permutation
我说下我的算法,大家帮忙看看有没有问题。
#include
class Solution {
public:
void nextPermutation(vector &num) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if (1==num.size())
return;
vector::reverse_iterator rit;
vector::reverse_iterator it1,it2;
for ( rit=num.rbegin() ; rit < num.rend(); ++rit )
{
rit++;
it1=rit;
rit--;
it2=rit;
... 阅读全帖
d****o
发帖数: 2
39
来自主题: JobHunting版 - 面试F家让先做programming puzzle
抛砖引玉
#include
#include
#include
const int kMaxK = 5;
const int kMaxN = 8;
const int kMaxS = 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5;
#define DEBUG(v) std::cerr << #v << " = " << (v) << "\n"
int N, K, max_state;
short top[kMaxS][kMaxK];
int G[kMaxS][kMaxK * (kMaxK - 1) + 1];
int src = 0, dst = 0;
int f[kMaxS];
int pow(int base, int power) {
int r = 1;
for (int i = 0; i < power; r *= base, ++i);
return r;
}
int get(int num, int d) {
for (int i = 0; i < d; num /= K, ++i)... 阅读全帖
d****o
发帖数: 2
40
来自主题: JobHunting版 - 面试F家让先做programming puzzle
抛砖引玉
#include
#include
#include
const int kMaxK = 5;
const int kMaxN = 8;
const int kMaxS = 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5;
#define DEBUG(v) std::cerr << #v << " = " << (v) << "\n"
int N, K, max_state;
short top[kMaxS][kMaxK];
int G[kMaxS][kMaxK * (kMaxK - 1) + 1];
int src = 0, dst = 0;
int f[kMaxS];
int pow(int base, int power) {
int r = 1;
for (int i = 0; i < power; r *= base, ++i);
return r;
}
int get(int num, int d) {
for (int i = 0; i < d; num /= K, ++i)... 阅读全帖
s********u
发帖数: 1109
41
来自主题: JobHunting版 - ebay skype interview面经(4轮)
我自己写的:
list findNthPrime( int N ){
int prime = 2;
int num = 3;

list primes;
primes.push_back(2);

while( primes.size() < N){


for( listiterator:: it = primes.begin(); it != primes.end() &&
*it <= (int) sqrt( num ); it++ ){

if( num%(*it) == 0 ){
num += 2;
it = primes.begin();
}
}

primes.push_back(num);

num += 2;
}

return p... 阅读全帖
r***e
发帖数: 29
42
来自主题: JobHunting版 - BBC 编程风格面试题,求指教
最后个人标准答案
#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... 阅读全帖
b****g
发帖数: 192
43
来自主题: JobHunting版 - leetcode上的4Sum一问
为了防止4元组重复,我没用set或者map保存整数对而是在每个for循环之后立即判断,
如果num[i] == num[i-1],那么就重复了,于是就不执行底下的操作,直接++i了。这
样就不用uniqueset,比较省空间。看下面的注释

~~这里判断如果num[i] == num[i-1],那么就重复了,于是continue;
~~这里判断如果num[j] == num[j],就continue;
k*******t
发帖数: 144
44
class Solution {
public:
int longestConsecutive(vector &num) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
unordered_map mapping;
for(int i = 0; i < num.size(); ++i)
{
mapping[num[i]] = true;
}

int longest = 0;
for(int i = 0; i < num.size(); ++i)
{
int len = 0;
int cur = num[i];
while(mapping.find(cur) != mapping.end... 阅读全帖
p*i
发帖数: 411
45
来自主题: JobHunting版 - 问一道题
bottom-up
vector> num; // assume this is the input
const int n = num.size();
if (n == 0) return 0;
for (int i = n-2; i >= 0 --i) {
for (int j = 0; j <= i; ++j) {
num[i][j] += max(num[i+1][j], num[i+1][j+1]);
}
}
return num[0][0];

the
triangle
r*********n
发帖数: 4553
46
来自主题: 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... 阅读全帖
s********u
发帖数: 1109
47
来自主题: JobHunting版 - 这段LIS为啥崩溃?
if(nums[i]>nums[j] && sizes[i] < sizes[j]+1)
{
sizes[i] = sizes[j]+1;
paths[i] = paths[j] + nums[i] + " ";
if(maxLength < sizes[i])
maxLength = sizes[i];
}
中间这一段写的不太好,尤其是paths[i]的处理,应该用一个变量比如local_prev来记
录j的值,等j全部遍历完了,这时候再处理paths。包括maxlength也是。
应该是
for( int j = 0; j < i; j++){
if(nums[i]>nums[j] && sizes[i] < sizes[j]+1)
{
sizes[i] = sizes[j]+1;
local_prev = j;
}
}
paths[i] = path[j] + num[i] + " ";
if(ma... 阅读全帖
s********u
发帖数: 1109
48
来自主题: JobHunting版 - 经典题:找前N个质数
发现careercup上面面经的解答真是不忍直视,挺明了的思路经常有人写一长串代码,
乍看容易把人吓到。
我的思路是建立一个list存质数,然后对每个奇数检验(遍历一遍这个质数list),直
到这个list的size到N。
因为是经典题,所以想问问是否这个就是最优解法了。
list findNthPrime( int N ){
int prime = 2;
int num = 3;

list primes;
primes.push_back(2);

while( primes.size() < n){

for( list::iterator it = primes.begin(); it != primes.end() &&
*it <= (int) sqrt( num ); it++ ){

if( num%(*it) == 0 ){
num += 2;
it = prime... 阅读全帖
B******l
发帖数: 262
49
来自主题: JobHunting版 - Google phone interview 金天
从左到右走一遍生成array L,L[i]=num[0]*num[1]*...*num[i]
从右到左走一遍生成array R,R[i]=num[i]*num[i+1]*...*num[n-1]
output[i]=L[i-1]*R[i+1]

where
b*****a
发帖数: 1
50
来自主题: JobHunting版 - f家店面题
好像是 Jump Game II 稍加改动, 楼主的case可以过
int jump(int* nums, int numsSize)
{
if (!nums || !numsSize) return -1;
else
{
int last = 0;
int cur = 0;
int jumps = 0;
int speed = 1;
int i;

for (i = 0; i < numsSize; i++)
{
if (i > last)
{
last = cur;
jumps++;
speed++;
}

if (nums[i] && (nums[i + speed] || (i + speed > numsSize - 1)... 阅读全帖
首页 上页 1 2 3 4 5 6 7 8 9 10 下页 末页 (共10页)