i*********n
发帖数: 58 | 1 int findMin(vector& num) {
int l = 0;
int h = num.size() - 1;
while(l < h && num[l] == num[l + 1]) l ++;
while (l + 1 < h) {
int i = (l + h) / 2;
if (num[l] < num[h])
h = i;
else
if (num[l] < num[i])
l = i;
else
h = i;
while(l < h && num[l] == num[l + 1]) l ++;
}
return std::min(num[l], num[h]);
} |
|
i*********t
发帖数: 23 | 2 public class Solution {
public int findMin(int[] num) {
if(num==null || num.length==0)
return -1;
int beg = 0;
int end = num.length - 1;
while(beg
if(num[beg]
return num[beg];
int mid = beg + (end - beg)/2;
if(num[beg]
beg = mid + 1;
else if(num[beg]>num[mid])
end = mid;
else
beg++;
}
... 阅读全帖 |
|
S********s
发帖数: 29 | 3 A java version:
import java.util.HashSet;
import java.util.Set;
public class DecimalToString {
public static void main(String[] args) {
System.out.println(get_decimal(1, 6));
System.out.println(get_decimal(1, 3));
System.out.println(get_decimal(1, 2));
System.out.println(get_decimal(1, 8));
System.out.println(get_decimal(2, 3));
System.out.println(get_decimal(1, 9));
System.out.println(get_decimal(1, 11));
System.out.println(get... 阅读全帖 |
|
i*****h
发帖数: 1534 | 4 这个比较容易理解。
public boolean search(int[] nums, int target) {
int low=0,high=nums.length-1;
while(low
if(nums[low]==target) return true;
++low;
--high;
}
while(low<=high){
int mid=(low+high)/2;
if(nums[mid]==target) return true;
if((target>nums[mid] && target<=nums[high]) ||
(nums[mid]>nums[high] && (target>nums[mid] ||
target<= nums[hig... 阅读全帖 |
|
L***s
发帖数: 1148 | 5
需求提得有问题，会写程序的人一般不这么问
我猜你可能想要下面的效果，猜得不对你自己酌情修改
In [4]: class Foo (object):
...:
...: def __init__ (self, raw_dict):
...: self.num_to_string_set = {}
...: for tup, string in raw_dict.iteritems():
...: for num in tup:
...: self.num_to_string_set\
...: .setdefault(num,set())\
...: .add(string)
...:
...: def query (self, *nums):
...: assert len(nums) > 0
...: ... 阅读全帖 |
|
f******5
发帖数: 11 | 6 //Algorithm DPKnapsack(w[1..n], v[1..n], W)
// var V[0..n,0..W], P[1..n,1..W]: int
// for j := 0 to W do
// V[0,j] := 0
// for i := 0 to n do
// V[i,0] := 0
// for i := 1 to n do
// for j := 1 to W do
// if w[i] j and v[i] + V[i-1,j-w[i]] > V[i-1,j] then
// V[i,j] := v[i] + V[i-1,j-w[i]]; P[i,j] := j-w[i]
// else
// V[i,j] := V[i-1,j]; P[i,j] := j
// return V[n,W] and the optimal subset by ba... 阅读全帖 |
|
s*****y
发帖数: 897 | 7 写了一个基于tree的，插入的原则是
1.比较最高位的digit，大的插入右边，小于或者等于的插入左边
2.如果最高位相等，比较combine 2个数的结果，哪个大决定插入左边或者右边
所有node都插入到树的最低层。
建完tree后，traverse tree按照right, current left的顺序，测了一下案例，似乎是
对的，
//int A[] = {2, 3, 5, 78 }; //pass
//int A[] = {2, 3, 89, 897 }; //pass
// int A[] = {3,3,43}; //pass
int A[] = {9, 98, 987, 902, 399, 380}; //pass
//int A[] = {900, 9001, 2}; //pass
// int A[] = {2, 3, 89,94, 899 }; //pass
// int A[] = {2, 3, 89, 897 }; //pass
// int A[] = {2, 3, 5... 阅读全帖 |
|
|
|
d*******3
发帖数: 58 | 10 Zhuimeng1314说的对，就是这个意思，这是hash的解法。（3，4），（4，3）不需要都
存，只存一个3就行了
敲了下代码，不知道有木有bug...
vector > twoSum(vector& num,int target)
{
vector >ans;
hash_map num_map;
hash_map pair_map;
typedef pair IntPair;
for(int i=0;i
num_map.insert(IntPair(num[i],1));
for(int i=0;i
{
if(num_map.find(target-num[i])!=num_map.end())//for num[i],exist
target-num[i]
{
int small... 阅读全帖 |
|
i**********e
发帖数: 1145 | 11 没想明白为什么要用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... 阅读全帖 |
|
r********g
发帖数: 1351 | 12 写了个递归的，复杂度。。应该是C(n,k)吧？指数级的？
class Solution {
public:
vector > combinationSum2(vector &num, int target) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
sort(num);
vector > Results;
vector tmpR;
doFind(num, Results, 0, target, tmpR);
return Results;
}
void doFind(vector &num, vector > &Results, int idx,
int target, vector tmpR) {
i... 阅读全帖 |
|
c***e
发帖数: 542 | 13 print in lexi order, here is my code which passed both small and large tests:
class Solution {
public:
vector > permuteUnique(vector &num) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector > allPerm;
sort(num.begin(), num.end());
allPerm.push_back(num);
if(num.size() < 2)
return allPerm;
vector tmp=num;
while(true)
{
... 阅读全帖 |
|
c***e
发帖数: 542 | 14 print in lexi order, here is my code which passed both small and large tests:
class Solution {
public:
vector > permuteUnique(vector &num) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector > allPerm;
sort(num.begin(), num.end());
allPerm.push_back(num);
if(num.size() < 2)
return allPerm;
vector tmp=num;
while(true)
{
... 阅读全帖 |
|
Z***A
发帖数: 33 | 15 写了3sum的solution，但是没通过OJ large judge，Run Status: Time Limit
Exceeded，请分析一下原因。
下面是code：
public ArrayList> threeSum(int[] num) {
// Start typing your Java solution below
// DO NOT write main() function
if (num.length < 3)
return new ArrayList>();
Arrays.sort(num);
ArrayList> res = new ArrayList
>();
for (int i=0; i < num.length; i++)
{
... 阅读全帖 |
|
s*****n
发帖数: 994 | 16 用了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 (... 阅读全帖 |
|
x*****0
发帖数: 452 | 17 遇到一个奇怪的问题。对于同样的数据集，在自己的IDE上测试，没有任何问题，
leetcode的onlinejudge却报错。
例如：
leetcode online judge
input output expected
[0,0] [[0,0,0]] []
[1,2,-2,-1] [[-2,2,0],[-1,1,0]] []
[-1,0,1,2,-1,-4] [[-1,1,0]] [[-1,-1,2],[-1,0,1]]
在自己的IDE上，能够给出expected的答案。
下面是我的代码：
class Solution {
public:
vector > threeSum(vector &num) {
// Start typing your C/C++ solution below
// DO NO... 阅读全帖 |
|
g**4
发帖数: 863 | 18 196ms，C++果然是快啊
class Solution {
public:
vector > fourSum(vector &num, int target) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector > result;
if (num.size() < 4) {
return result;
}
sort(num.begin(),num.end());
for (int j=0;j
int a = num[j];
// 3sum
for (int i=j+1;i
int ... 阅读全帖 |
|
i****y
发帖数: 84 | 19 我写了个循环，请问这个是dp吗？
num[0]=1;
for(int n =0; n
if(num[n]==0)continue;
if(n+1
num[n+1]+=num[n];
if(n+2
num[n+2]+=num[n];
}
return num[num.length-1]; |
|
j********r
发帖数: 25 | 20 参考一下我的做题记录里提取出来的：
class Solution {
public:
vector > permuteUnique(vector &num) {
sort(num.begin(), num.end());
vector > ret;
int n = num.size();
bool *used = new bool[n];
vector index;
memset(used, 0, n*sizeof(bool));
permute(num, used, index, 0, ret);
delete[] used;
return ret;
}
void permute(const vector &num, bool used[], vector& candidate
, int pos, vector阅读全帖 |
|
h**o
发帖数: 548 | 21 我用swap那种解法理解的。去duplicate就加上noswap（）判断。
bool noswap(int level, int i, const vector& num){
for (int j=level;j
if (num[j]==num[i]){
return true;
}
}
return false;
}
void perm_recur(vector &num, int size, int level, vector
> >& results) {
if (level == size) {results.push_back(num); return;}
for (int i = level; i < size; i++){
if (noswap(level, i, num)) continue;
... 阅读全帖 |
|
m**********e
发帖数: 22 | 22 同楼下一大侠的算法。C#写的：
public List GetContainsFive(int num)
{
int m = num;
int i = 0;
while (m > 0)
{
i++;
m = m / 10;
}
string solution = string.Empty;
List result = new List();
GetContainsFiveHelper(num, i, solution, result);
return result;
}
private void GetContainsFiveHelper(int num, int n, string solution,
List resul... 阅读全帖 |
|
m**********e
发帖数: 22 | 23 同楼下一大侠的算法。C#写的：
public List GetContainsFive(int num)
{
int m = num;
int i = 0;
while (m > 0)
{
i++;
m = m / 10;
}
string solution = string.Empty;
List result = new List();
GetContainsFiveHelper(num, i, solution, result);
return result;
}
private void GetContainsFiveHelper(int num, int n, string solution,
List resul... 阅读全帖 |
|
b*******g
发帖数: 57 | 24 来自主题: JobHunting版 - FB 面经 //Find valley(rotation distance) in a rotated array with unique numbers
int findValley(vector num) {
if (num.empty()) return 0;
int lower = 0;
int upper = num.size()-1;
while (lower <= upper) {
if (upper-lower <= 1)
return num[lower] < num[upper] ? lower : upper;
int mid = lower+(upper-lower)/2;
if (num[mid-1] > num[mid] && num[mid] < num[mid+1])
return mid;
if (num[lower] < num[mid])
lower = mid+1;
... 阅读全帖 |
|
D***0
发帖数: 138 | 25 刚刚店面的，一个老印，口音挺重的，说话好像离电话挺远的，接起电话连个自我介绍
都没有，上来就说来给我说说你的简历吧，我说完后他又问我现在的工作主要是干什么
的，解释了3遍这哥们才算明白，难道就这么浪费我宝贵的45分钟？接下来问如何给一
个网站比如尼玛推特设计一个log系统，如果用户打开尼玛推特什么也没有怎么根据你
的log系统查（心中草泥马奔腾啊），说了一堆后，这厮说ok，快到点了，做道题吧，
11
9 12
4 8 6
2 7 3 1
int[] nums = {11, 9, 12, 4, 8, 6, 2, 7, 3, 1}
valid move: 9 - 4 or 8
invalid : 9 - 11 or 12 or 6
all positive numbers
find max sum in any number of possible moves
38 (11 + 12 + 8 + 7)
就是把树装数组里了，他说你可以是认为是完全三角形。好吧，我就开始说我的思路，
刚写
了如何找到左右子的公式，这厮就迫不及待的打断，说你不用解释，快写吧，我操... 阅读全帖 |
|
l*****a
发帖数: 14598 | 26 你们非用for loop把三种情况混在一起，感觉不好。
如下是不是会清晰易懂一点呢
if(num[0]!=start) print(start,num[0]-1);
int cur=0;
while(cur
if(num[cur]!=num[cur+1]-1) print(num[cur]+1,num[cur+1]-1);
cur++;
}
if(num[num.length-1]!=end) print(num[num.length-1]+1,end); |
|
i*********n
发帖数: 58 | 27 int findMaxRecur(vector& num, int begin, int end)
{
if (begin == end)
return num[begin];
if (begin + 1 == end)
return std::max(num[begin], num[end]);
int mid = (begin + end) / 2;
if (num[begin] < num[mid] && num[mid] < num[end]) {
return num[end];
}
else {
return std::max(
findMaxRecur(num, begin, mid),
findMaxRecur(num, mid + 1, end));
}
} |
|
w****a
发帖数: 710 | 28 这题最近出镜率贼高啊。
你这里5/10 返回0.5。有的面经让返回0.5(0)。我贴一个返回0.5(0)的吧。当然没啥区
别，细节改一下而已。
string get_decimal(int num, int den) {
string ret = to_string(num / den);
ret.push_back('.');
num %= den;
map rems;
while(num != 0 && !rems.count(num)) {
rems[num] = (int)ret.size();
num *= 10;
ret.push_back(num / den + '0');
num %= den;
}
if (num != 0) {
ret.insert(ret.begin() + rems[num], '(');
ret += ")";
} else {
ret +=... 阅读全帖 |
|
g**d
发帖数: 383 | 29 PS，你的代码太复杂了，本来是一个正常的问题
public int findMin2(int[] nums) {
int start = 0;
int end = nums.length - 1;
while(start < end - 1) {
if(nums[start] < nums[end]) {
return nums[start];
}
int mid = start + (end - start) / 2;
if(nums[mid] > nums[start]) {
start = mid;
} else if(nums[mid] < nums[start]) {
end = mid;
} else {
start +... 阅读全帖 |
|
k****r
发帖数: 807 | 30 我写了一个，不知道可用不，先用DP找到最长subsequence的长度，complexity is O(
nlongn);
再用recursive找到所有可行解。
public static List> AllLongestIncreasingSubsequence(int[] nums
) {
int[] m = new int[nums.length + 1];
int L = 0;
for (int i = 0; i < nums.length; i++) {
int lo = 1;
int hi = L;
while (lo <= hi) {
int mid = (lo + hi) / 2;
if (nums[m[mid]] < nums[i]) lo = mid + 1;
else hi = mid - 1;
}... 阅读全帖 |
|
a***u
发帖数: 383 | 31 import java.util.*;
public class DesignDataStructure {
Map> map = new HashMap>();
List list = new ArrayList();
public void add(int num){
list.add(num);
int index=list.size()-1;
if(map.containsKey(num)){
map.get(num).add(index);
}else{
Set set =new HashSet();
set.add(index);
map.put(num, set);
}
}
public voi... 阅读全帖 |
|
|
i********s
发帖数: 133 | 33 #include
int main(int argc, char **argv)
{
int num;
std::cout << "enter the size of the square:";
std::cin >> num;
std::cout << std::endl << "size =" << num << std::endl;
int (*array)[num] = new (int[num][num]);
int t = 0;
for(unsigned i=0; i
for(unsigned j=0; j
array[i][j] = ++t;
unsigned leftX = 0;
unsigned leftY = 0;
unsigned rightX = num;
unsigned rightY = num;
while(leftX <= rightX)
{ |
|
m******e
发帖数: 353 | 34 #include
#include
void countOnesAndZeros(int &numZeros, int &numOnes, const std::vector &
sequence) {
numOnes = 0;
numZeros = 0;
for(size_t i = 0; i
sequence[i] == 1 ? ++ numOnes : ++ numZeros;
}
}
int trimLeft(const std::vector &sequence, int start, int numToTrim, int
untilSeenSymbol) {
int trimCnt = 0;
while(start + trimCnt >= 0 && start + trimCnt < (int) sequence.size() &&
numToTrim > 0) {
if(sequenc... 阅读全帖 |
|
i*******n
发帖数: 114 | 35 PayPal的笔试面试，版上一位朋友refer的。
发来5套题，一个小时后做完，发回去。大部分题目都不好做，我把其中的几道发在这
里。
希望后面有牛人帮忙解答。
What is the purpose of this function? (assume int are 32 bits)
int f( int v)
{
int t = 0;
int i;
for (i = 31; i !=0 ; i--) {
t |= v & 1;
t <<= 1;
v >>= 1;
}
t |= v & 1;
return t;
}
----------------------------------------------------
Consider the following function:
int f (int num)
{
int out = 0;
for (; num > 0; num /= 10) {
... 阅读全帖 |
|
t**i
发帖数: 314 | 36 编译过了，运行出错，帮忙看看哪儿出了问题，多谢。
import java.util.*;
public class Solution {
public ArrayList> threeSum(int[] num) {
assert(num.length >= 3);
ArrayList> triplet = new
ArrayList>();
for(int i = 0; i < num.length - 2; i++) {
for(int j = i + 2; j < num.length; j++) {
for(int k = i + 1; k < j; k++) {
if((num[i] + num[j] + num[k]) == 0) {
int[] th... 阅读全帖 |
|
p*****2
发帖数: 21240 | 37 我写了一个练练。
public void nextPermutation(int[] num)
{
int i=num.length-2;
while(i>=0 && num[i]>num[i+1])
i--;
if(i>0)
{
int j=num.length-1;
while(num[j]
j--;
swap(num,i,j);
}
reverse(num,i+1,num.length-1);
} |
|
q***y
发帖数: 236 | 38 不清楚，贴出code大家分析吧。注释部分是后来加的。
unsigned int num_valid_decodings(char const* n_string) {
if (!n_string) return 0;
int n = strlen(n_string);
if (n==1) {
if(n_string[0]=='0') return 0; // not valid
else return 1;
}
vector num(n, 0);
char *p = (char *) n_string;
if (p[0] == '0') return 0; // not valid
else num[0] = 1;
if (p[0]=='1' ) num[1]=2;
else if (p[0]=='2' && p[1]<='6') num[1]=2;
else num[1] = 1;
for (int i=2; i
... 阅读全帖 |
|
q***y
发帖数: 236 | 39 起始条件有点问题，改了一下。
unsigned int num_valid_decodings(char const* n_string) {
if (!n_string) return 0;
int n = strlen(n_string);
if (n==1) {
if(n_string[0]=='0') return 0; // not valid
else return 1;
}
vector num(n, 0);
char *p = (char *) n_string;
if (p[0] == '0') return 0; // not valid
else num[0] = 1;
if (p[1]!='0') num[1]+=num[0];
if (p[0]=='1' || p[0]=='2' && p[1]<='6') num[1]++;
for (int i=2; i
if (p[i]!='0') num[... 阅读全帖 |
|
S*****B
发帖数: 404 | 40 public int check(String s) {
if (s.length() == 0)
return 0;
int n = s.length();
if (n == 1) {
if (s.charAt(0) == '0')
return 0; // not valid
else
return 1;
}
int[] num = new int[n];
if (s.charAt(0) == '0')
return 0; // not valid
else
num[0] = 1;
if (s.charAt(1) != '0')
num[1] += num[0];
if (s.charAt(0) == '1' || (s.charAt(... 阅读全帖 |
|
a******8
发帖数: 90 | 41 我的1和2区别很小啊，测试都过了。我的思路是2无非是有一些重复的，怎么去重复，
先排序，然后我手动run了几个test case,发现在某些情况下，会重复的swap,这样我从
后往前走，一旦遇到相同的数，就可以停止了，否则就是重复，有点排列组合的概念。
请各大牛验证：
比如 yyy9yyy9x 9,比如下个数是9，只需要换下x与9，进下一步，其他之前的不管了
，管了就重复了。
class Solution {
public:
void myPerm(vector &num, vector curv, int curi, vector
int> > &ret)
{
if(curi == num.size())ret.push_back(curv);
else
{
curv.push_back(num[curi]);
myPerm(num,curv,curi+1,ret);
for(int i = curv.size... 阅读全帖 |
|
r*****e
发帖数: 792 | 42 if (num[low]+num[mid]+num[high]==0) {
do {--high;} while (num[high]==num[high+1]);
do {++mid;} while (num[mid]==num[mid-1]);
while (low
}
For low, should use while instead of do while because we don't want to
increment low if unnecessary.
In short, move the indices to positions that result in different num[index]
values. |
|
g***j
发帖数: 1275 | 43 基本思路就是，先把两个的和存起来，并且把相应的index pair存到对应的直的map里
面去。
然后再把所有的两个的和和target的差算出来，去map里面找，因为map里面同样保存了
签名的数字的index，所以，只要后面两个数的最小的index比已有的最大的index大的
时候，就能保证不重复了。
可惜small set 15个总有一个不过，而且，因为显示问题，看不到哪个不过。哪个大侠
帮我看看代码？
class Solution {
public:
vector > fourSum(vector &num, int target) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int n = num.size();
vector > results;
if(n <= 3) return results;
m... 阅读全帖 |
|
|
k****r
发帖数: 807 | 45 楼主大牛拿到G和RF的offer了，能不能上个面经，造福大家啊？
下面是我的code，请指教：
void combinationMultiplyHelper(vector &num, int target, int start,
vector comb, vector> &res) {
if (target == 1) {
res.push_back(comb);
return;
}
for (int i = start; i < num.size(); i++) {
if (target >= num[i] && target % num[i] == 0) {
comb.push_back(num[i]);
combinationMultiplyHelper(num, target/num[i], i, comb, res);
comb.... 阅读全帖 |
|
g*****g
发帖数: 212 | 46 没错，基本上就是暴力组合各种表达式
在表达式最后求值。
void allexpressions(vector &num, vector &exps, vector &
ret, int target)
{
int n =num.size();
for(int i=0; i
{
swap(num, 0,i);
exps.push_back(""+i);
allexpressions(num, 1, n, exps, ret, target);
exps.pop_back();
swap(num, 0,i);
}
}
void caculateExpressions(vector &exps, vector &ret, int
target)
{
}
void allexp... 阅读全帖 |
|
l******6
发帖数: 340 | 47 The first problem , I guess the key is you don't know how many 3 are there
in the array and the interviewer want you traverse the array only once
int ret;
int occur = 0;
for(int i = 0 ; i < input . length ; i++)
{
if(input[i] == 3)
{
occur ++;
if(rand()%occur == 0)
ret = i;
}
}
return ret;
and if it is not known which number occurs most times
int ret = 0;
int maxOccur = 0;
int num;
unordered_map occurMap;
unordered_map randomPickMap;
... 阅读全帖 |
|
R*****i
发帖数: 2126 | 48 CSDN上的编程挑战题。
http://hero.csdn.net/Question/Details?ID=610&ExamID=605
我的算法貌似不对，请问正确算法是神马？
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Numerics;
namespace GridWalk
{
class Program
{
static void Main(string[] args)
{
List nlist = new List();
string line = Console.ReadLine();
while (!string.IsNullOrEmpty(line))
{
nlist.Add(int.Parse(line));
... 阅读全帖 |
|
c**********x
发帖数: 32 | 49 int maxDistance(vector &num){
vector dp(num.size(), 0);
dp[0] = 2*num[0];
for(int i=1; i
dp[i] = dp[i-1]+1+num[i]-num[i-1] > 2*num[i] ?
dp[i-1]+1+num[i]-num[i-1] : 2*num[i];
int maxDistance = dp[0];
for(int i=1; i
maxDistance = dp[i] > maxDistance ? dp[i] : maxDistance;
return maxDistance;
}
这个大概可以吧 |
|
c**********x
发帖数: 32 | 50 int maxDistance(vector &num){
vector dp(num.size(), 0);
dp[0] = 2*num[0];
for(int i=1; i
dp[i] = dp[i-1]+1+num[i]-num[i-1] > 2*num[i] ?
dp[i-1]+1+num[i]-num[i-1] : 2*num[i];
int maxDistance = dp[0];
for(int i=1; i
maxDistance = dp[i] > maxDistance ? dp[i] : maxDistance;
return maxDistance;
}
这个大概可以吧 |
|
