c*******4
发帖数: 51 | 1 No offer。发面经供大家参考，5轮
1：（1）：写一个bool Palindrome(string s)，就是测s是否是Palindrome。
（2）：已知bool Palindrome(string s)方程，写一个 int howmanyPalindrome
(string s), 输入s，返回s中包含多少个Palindrome的单词。 例如abbbac返回10，有a
,b,b,b,a,c,bb, bbb, bb, abbba.
2: 给一个树root的pointer，树包含多个分支，树结构要自己创造。求一条最长路径。
例如（括号对应上面node）
树： 2
| | | |
5 7 3 6
（| | ）（ | ） （|） （| |）
6 3 2 4 5 8
|
3
返回3因为 （2-3-4） 这条线。优化要求时间O(n)
3.时间区间合并问题，leetcode上有相似题，关键词interval
4.(1)一个sorted array，如果其中有一个数重复超过array里面总数的1/4 return
true。就是说{2，2，3，4} return true
{1，1，2，3，4，5，6，7} return false。
（2）优化第一部分用O（log2(N)) 时间复杂度
(3)完全平方解集，做一个：int minsol（int i）。
比如1=1^2 所以minsol(1)返回1,
2=1^2+1^2 返回2,
4=2^2或者4个1^2,1比4小， 返回1，
12=2^2+2^2+2^2或者3^2+3个1^2返回3.
5.有一个游戏，他说是fishing game，给一个数组vector Basket, 比如里面元素
是{2，3，5，1，3，4，7}
有A，B 2个player，规定只能从Basket2端选数字，意思就是A开始的话一开始A只能选2
或者7，然后B选，同样只能2端选。所以比如一开始A选了7，B只能从2和4中选。问给定
数组A能取的最大值。B的策略已知，是greedy，就是总会取最大的那个数。
写一个 int maxA（vector& Basket）；
加油！希望多少能给你们复习带来一点动力！ |
T*****n
发帖数: 82 | |
z****0
发帖数: 4413 | 3 好人 比不发面筋的索男强多了
howmanyPalindrome
有a
【在 c*******4 的大作中提到】
: No offer。发面经供大家参考，5轮
: 1：（1）：写一个bool Palindrome(string s)，就是测s是否是Palindrome。
: （2）：已知bool Palindrome(string s)方程，写一个 int howmanyPalindrome
: (string s), 输入s，返回s中包含多少个Palindrome的单词。 例如abbbac返回10，有a
: ,b,b,b,a,c,bb, bbb, bb, abbba.
: 2: 给一个树root的pointer，树包含多个分支，树结构要自己创造。求一条最长路径。
: 例如（括号对应上面node）
: 树： 2
: | | | |
: 5 7 3 6
|
l****c
发帖数: 782 | 4 感谢楼主分享。
howmanyPalindrome这道题用recursive暴力解，面试官满意吗？还是必须要用Manacher
’s 算法？ |
J*******o
发帖数: 741 | |
e****o
发帖数: 176 | |
b**********5
发帖数: 7881 | 7 傻逼， 你读过你签的NDA么？？！！！ 你不想报面经， 别他妈的用傻逼NDA做借口！
自己他妈的先去读读NDA再说！
【在 e****o 的大作中提到】
: 你这签了NDA了吗?
|
A*******e
发帖数: 2419 | 8 谢谢分享。第二题的答案为何是3？显然有更长的路径啊。
howmanyPalindrome
有a
【在 c*******4 的大作中提到】
: No offer。发面经供大家参考，5轮
: 1：（1）：写一个bool Palindrome(string s)，就是测s是否是Palindrome。
: （2）：已知bool Palindrome(string s)方程，写一个 int howmanyPalindrome
: (string s), 输入s，返回s中包含多少个Palindrome的单词。 例如abbbac返回10，有a
: ,b,b,b,a,c,bb, bbb, bb, abbba.
: 2: 给一个树root的pointer，树包含多个分支，树结构要自己创造。求一条最长路径。
: 例如（括号对应上面node）
: 树： 2
: | | | |
: 5 7 3 6
|
c*******4
发帖数: 51 | 9 我不懂manacher算法，刚查了一下，这算法主要是用来找string中最长palindromic
substring的么？我不太懂你想如何应用到这题上，咱可以讨论讨论，因为我这题当时
没做完，也想知道下正确思路。我当时想了自己的算法，一位一位移过去，以移到的那
位置开始recursive找+1，然后-1，有点bfs的意思，并判断是否是palindromic，后来
发现如果遇到有重复的单词处理起来很麻烦，最后暴力解了，还没解完。
Manacher
【在 l****c 的大作中提到】
: 感谢楼主分享。
: howmanyPalindrome这道题用recursive暴力解，面试官满意吗？还是必须要用Manacher
: ’s 算法？
|
c*******4
发帖数: 51 | 10 我工作快2年了，在MD这儿，女友在马大毕业了找到Sunnyvale CA的工作所以最近才急
急忙忙想找工作转到硅谷湾区那块。这是software engineer的面试，最后一轮是
search组的人面的题
【在 J*******o 的大作中提到】
: lz是new grad吧
|
|
|
c*******4
发帖数: 51 | 11 什么是NDA？我可能签了，我不太懂，我看大家都把面经放上来交流所以我也放了，是
不能放么。。。
【在 e****o 的大作中提到】
: 你这签了NDA了吗?
|
c*******4
发帖数: 51 | 12 很感谢，我第二题漏了条件，路径要连续的，所以那一条2，3，4最长，所以返回3.
我把条件加上了
【在 A*******e 的大作中提到】
: 谢谢分享。第二题的答案为何是3？显然有更长的路径啊。
:
: howmanyPalindrome
: 有a
|
l****c
发帖数: 782 | 13 感谢楼主分享！
看下面链接里有两种解法：
一种recursive 暴力解，另一种利用Manacher解。暴力解不难，但是不知道面试官是不
是期待O（n） 的Manacher解法。
http://stackoverflow.com/questions/19801081/find-all-substrings
【在 c*******4 的大作中提到】
: 我不懂manacher算法，刚查了一下，这算法主要是用来找string中最长palindromic
: substring的么？我不太懂你想如何应用到这题上，咱可以讨论讨论，因为我这题当时
: 没做完，也想知道下正确思路。我当时想了自己的算法，一位一位移过去，以移到的那
: 位置开始recursive找+1，然后-1，有点bfs的意思，并判断是否是palindromic，后来
: 发现如果遇到有重复的单词处理起来很麻烦，最后暴力解了，还没解完。
:
: Manacher
|
l****c
发帖数: 782 | 14 楼主，第二题最长路径是任意两个node之间路径，还是从root到某个节点，还是从上面
某个node到下面某个node？ |
y**i
发帖数: 1112 | 15 第一题如果不是非要用你之前写好的那个函数判断，可以用DP，Leetcode上有类似的
，用一个二维DP数组，所有行列相等的埴都是True，然后只计算上半部分，从下往上，
利用已经计算过的结果，最后O（n2）
【在 c*******4 的大作中提到】
: 我不懂manacher算法，刚查了一下，这算法主要是用来找string中最长palindromic
: substring的么？我不太懂你想如何应用到这题上，咱可以讨论讨论，因为我这题当时
: 没做完，也想知道下正确思路。我当时想了自己的算法，一位一位移过去，以移到的那
: 位置开始recursive找+1，然后-1，有点bfs的意思，并判断是否是palindromic，后来
: 发现如果遇到有重复的单词处理起来很麻烦，最后暴力解了，还没解完。
:
: Manacher
|
y**i
发帖数: 1112 | 16 4（3）是个数学定理吧，记得好像所有数都可以分解成不超过4个平方和，然后计算1个
的情况，不行就2个，3个。。。 |
c*******4
发帖数: 51 | 17 是从node算，比如root为5的： 5-2-3-4-7 这种情况返回3，因为2-3-4这条路径
【在 l****c 的大作中提到】
: 楼主，第二题最长路径是任意两个node之间路径，还是从root到某个节点，还是从上面
: 某个node到下面某个node？
|
c*******4
发帖数: 51 | 18 我自己研究下再跟你交流~很感谢信息
【在 l****c 的大作中提到】
: 感谢楼主分享！
: 看下面链接里有两种解法：
: 一种recursive 暴力解，另一种利用Manacher解。暴力解不难，但是不知道面试官是不
: 是期待O（n） 的Manacher解法。
: http://stackoverflow.com/questions/19801081/find-all-substrings
|
c*******4
发帖数: 51 | 19 问过出题人了，第一题第二部分不必须用那个函数。我去leetcode上看看, 感谢解法信息
【在 y**i 的大作中提到】
: 4（3）是个数学定理吧，记得好像所有数都可以分解成不超过4个平方和，然后计算1个
: 的情况，不行就2个，3个。。。
|
c*******4
发帖数: 51 | 20 这题我是硬解的找一个vector存下所有从1到n的可能类似vector sol={1,3,2,1..
.}，然后有点类似找n sum那种根据1到n-1的情况推1到n的。我觉得应该有好的算法吧
，我当时没时间了他让我暴力从n-1数组中一个个凑。
【在 y**i 的大作中提到】
: 4（3）是个数学定理吧，记得好像所有数都可以分解成不超过4个平方和，然后计算1个
: 的情况，不行就2个，3个。。。
|
|
|
l****c
发帖数: 782 | 21 这个用DP解。
..
【在 c*******4 的大作中提到】
: 这题我是硬解的找一个vector存下所有从1到n的可能类似vector sol={1,3,2,1..
: .}，然后有点类似找n sum那种根据1到n-1的情况推1到n的。我觉得应该有好的算法吧
: ，我当时没时间了他让我暴力从n-1数组中一个个凑。
|
z***b
发帖数: 127 | 22 楼主能把你树的那个题当时写的代码贴出来看看嘛？谢谢！
howmanyPalindrome
有a
【在 c*******4 的大作中提到】
: No offer。发面经供大家参考，5轮
: 1：（1）：写一个bool Palindrome(string s)，就是测s是否是Palindrome。
: （2）：已知bool Palindrome(string s)方程，写一个 int howmanyPalindrome
: (string s), 输入s，返回s中包含多少个Palindrome的单词。 例如abbbac返回10，有a
: ,b,b,b,a,c,bb, bbb, bb, abbba.
: 2: 给一个树root的pointer，树包含多个分支，树结构要自己创造。求一条最长路径。
: 例如（括号对应上面node）
: 树： 2
: | | | |
: 5 7 3 6
|
z***b
发帖数: 127 | 23 用DP咋做？
【在 l****c 的大作中提到】
: 这个用DP解。
:
: ..
|
y**i
发帖数: 1112 | 24 这个递归就可解吧，bottom－up，求所有子树的最长路径，用一个全局变量或者类变量
什么的记录最长路径长度。如果有子树根节点和当前节点值差1，就返回子树最长路径
加1（有多个就返回最长那个，如果连续递增和连续递减都要考虑，还要返回递增属性
），否则返回1。递归返回前更新全局变量，取更大的长度。
【在 c*******4 的大作中提到】
: 是从node算，比如root为5的： 5-2-3-4-7 这种情况返回3，因为2-3-4这条路径
|
n******n
发帖数: 12088 | 25 什么叫有重复单词？你给的答案也有重复啊。
就是以每个字母和间隙向两边扩展到最大为止。长度为k，则有(k+1)/2个。
【在 c*******4 的大作中提到】
: 我不懂manacher算法，刚查了一下，这算法主要是用来找string中最长palindromic
: substring的么？我不太懂你想如何应用到这题上，咱可以讨论讨论，因为我这题当时
: 没做完，也想知道下正确思路。我当时想了自己的算法，一位一位移过去，以移到的那
: 位置开始recursive找+1，然后-1，有点bfs的意思，并判断是否是palindromic，后来
: 发现如果遇到有重复的单词处理起来很麻烦，最后暴力解了，还没解完。
:
: Manacher
|
n******n
发帖数: 12088 | 26 典型DP
【在 c*******4 的大作中提到】
: 这题我是硬解的找一个vector存下所有从1到n的可能类似vector sol={1,3,2,1..
: .}，然后有点类似找n sum那种根据1到n-1的情况推1到n的。我觉得应该有好的算法吧
: ，我当时没时间了他让我暴力从n-1数组中一个个凑。
|
n******n
发帖数: 12088 | 27 没问题。那个人是挖坑的。
【在 c*******4 的大作中提到】
: 什么是NDA？我可能签了，我不太懂，我看大家都把面经放上来交流所以我也放了，是
: 不能放么。。。
|
c******n
发帖数: 4965 | 28 recursive:
minsol(n)= math.min( minsol(k))+1. for all. k
and I is a square number
dp just mechanically transforms the above recuraion to a 1 dimensional array
(how many args there are to the recursive function, how many dimensions
there will be)
【在 z***b 的大作中提到】
: 用DP咋做？
|
f********e
发帖数: 100 | 29 RE:
4.(1)一个sorted array，如果其中有一个数重复超过array里面总数的1/4 return
true。就是说{2，2，3，4} return true
{1，1，2，3，4，5，6，7} return false。
（2）优化第一部分用O（log2(N)) 时间复杂度
{1，1，2，3，4，5，6，7} 该return true? |
g*****c
发帖数: 106 | 30 是要超过n/4。这个是等于n/4。
求问这题该怎么做？
【在 f********e 的大作中提到】
: RE:
: 4.(1)一个sorted array，如果其中有一个数重复超过array里面总数的1/4 return
: true。就是说{2，2，3，4} return true
: {1，1，2，3，4，5，6，7} return false。
: （2）优化第一部分用O（log2(N)) 时间复杂度
: {1，1，2，3，4，5，6，7} 该return true?
|
|
|
l**o
发帖数: 356 | |
s******x
发帖数: 417 | 32 （2）优化第一部分用O（log2(N)) 时间复杂度
这个怎么优化？
第一部分我是用map来记数，所以一定是O（n)复杂度。 |
c*******4
发帖数: 51 | 33 重复意思是abbbbac里面的bbbb如果用我前面那个方法移动一位左右bfs这样扫，同样的
会重复扫到的意思。
【在 n******n 的大作中提到】
: 什么叫有重复单词？你给的答案也有重复啊。
: 就是以每个字母和间隙向两边扩展到最大为止。长度为k，则有(k+1)/2个。
|
c*******4
发帖数: 51 | 34 等我有空了写
【在 z***b 的大作中提到】
: 楼主能把你树的那个题当时写的代码贴出来看看嘛？谢谢！
:
: howmanyPalindrome
: 有a
|
c*******4
发帖数: 51 | 35 超过1/4,1出现2次，是正好1/4，所以false
【在 f********e 的大作中提到】
: RE:
: 4.(1)一个sorted array，如果其中有一个数重复超过array里面总数的1/4 return
: true。就是说{2，2，3，4} return true
: {1，1，2，3，4，5，6，7} return false。
: （2）优化第一部分用O（log2(N)) 时间复杂度
: {1，1，2，3，4，5，6，7} 该return true?
|
c*******4
发帖数: 51 | 36 可能我没写清除或者你想复杂了，
直接从一开始扫，因为array sort过了，所以只要后面=前面的就开始记录就好了，
array长度你能知道，用vector是.size(),array的话 sizeof(A)/sizeof(A[0])然后比
较重复和N/4
【在 g*****c 的大作中提到】
: 是要超过n/4。这个是等于n/4。
: 求问这题该怎么做？
|
c*******4
发帖数: 51 | 37 binary search的方法
【在 s******x 的大作中提到】
: （2）优化第一部分用O（log2(N)) 时间复杂度
: 这个怎么优化？
: 第一部分我是用map来记数，所以一定是O（n)复杂度。
|
b********a
发帖数: 70 | |
S*****e
发帖数: 6676 | 39
你是上次威胁要撤人offer的狗狗索男么？
【在 e****o 的大作中提到】
: 你这签了NDA了吗?
|
z********o
发帖数: 83 | 40 第二题确实是3，从2->7->2->3的最长路径为max depth，包含3个edges
【在 A*******e 的大作中提到】
: 谢谢分享。第二题的答案为何是3？显然有更长的路径啊。
:
: howmanyPalindrome
: 有a
|
|
|
c*******4
发帖数: 51 | 41 忘了是怎么样的了，这个是重新写的，想法大概是这样，没检查过，可能有问题，再交
流吧
struct Node{
int val;
vector next;
};
int r(Node * root, int counter)
{
if(root->next.size()==0) return counter;
int maxi=counter;
for(int i=0; inext.size(); i++)
{
if(root->next[i]->val==root->val+1)
maxi=max(maxi, r(root->next[i], counter++));
else
maxi=max(maxi, r(root->next[i], 1));
}
return maxi;
}
int result(Node * root)
{
if(!root) return 0;
return r(root, 1);
}
【在 z***b 的大作中提到】
: 楼主能把你树的那个题当时写的代码贴出来看看嘛？谢谢！
:
: howmanyPalindrome
: 有a
|
c*******4
发帖数: 51 | 42 不好意思，是我题目没说清楚，还要连续，所以是2-3-4这条返回的3
【在 z********o 的大作中提到】
: 第二题确实是3，从2->7->2->3的最长路径为max depth，包含3个edges
|
g*****c
发帖数: 106 | 43 怎么binary search做？求问～
【在 c*******4 的大作中提到】
: binary search的方法
|
b********a
发帖数: 70 | 44 第五题怎么做？
dp复杂度是2的n次幂。。。。 |
z********o
发帖数: 83 | 45 tree这道题目的path，是可以绕过root的吗
howmanyPalindrome
有a
续]
【在 c*******4 的大作中提到】
: No offer。发面经供大家参考，5轮
: 1：（1）：写一个bool Palindrome(string s)，就是测s是否是Palindrome。
: （2）：已知bool Palindrome(string s)方程，写一个 int howmanyPalindrome
: (string s), 输入s，返回s中包含多少个Palindrome的单词。 例如abbbac返回10，有a
: ,b,b,b,a,c,bb, bbb, bb, abbba.
: 2: 给一个树root的pointer，树包含多个分支，树结构要自己创造。求一条最长路径。
: 例如（括号对应上面node）
: 树： 2
: | | | |
: 5 7 3 6
|
c*********i
发帖数: 46 | |
s******x
发帖数: 417 | 47 看lintcode的coin in a line
还是问binary search怎么做？谢谢！
【在 b********a 的大作中提到】
: 第五题怎么做？
: dp复杂度是2的n次幂。。。。
|
s******x
发帖数: 417 | 48 先建立一个tree，然后后面做search，是吧。
所以寻找是logN，但是前面会先建立tree，那就懂了。谢谢！
【在 s******x 的大作中提到】
: 看lintcode的coin in a line
: 还是问binary search怎么做？谢谢！
|
s********l
发帖数: 998 | 49 第二题怎么用dp?
【在 c*********i 的大作中提到】
: 1,2,4,5 都可以dp搞定
|
s********l
发帖数: 998 | 50 那道题要先建个tree啊？
【在 s******x 的大作中提到】
: 先建立一个tree，然后后面做search，是吧。
: 所以寻找是logN，但是前面会先建立tree，那就懂了。谢谢！
|
|
|
c*********i
发帖数: 46 | |
c*********i
发帖数: 46 | |
k****i
发帖数: 128 | 53 第二题，如果我理解题意是对的话
int longestPath(TreeNode* root)
{
int max=0;
TreeNode* maxRoot, curRoot;
dfs(root, NULL, curRoot, 0, max, maxRoot);
return max;
}
void dfs(TreeNode* root, TreeNode* parent, TreeNode*& curRoot, int height,
int& max, TreeNode*& maxRoot)
{
if(!root) return;
if(parent && root->val=parent->val+1) {
height++;
} else {
height=1;
curRoot=root;
}
if(height>max){
max=height;
maxRoot=curRoot;
}
for(auto c : root->children){
dfs(c, root, curRoot, height, max, maxRoot);
}
} |
c*******4
发帖数: 51 | 54 是的
【在 z********o 的大作中提到】
: tree这道题目的path，是可以绕过root的吗
:
: howmanyPalindrome
: 有a
: 续]
|
c*******4
发帖数: 51 | 55 回复 guokecc (guokecc) ，smartfox (smartfox)
咱可以再讨论
我也不知道我思路对不对，当时优化要求O(log2N)而且题目有sorted array，而且时间
不够了只能想到这个，现在也想不到其他的，欢迎来讨论
我试着把数组一半一半切，因为要求大于N/4， 如果true存在，那么切3刀分成4份必有
2刀左右有出现同样数字是中大于N/4那个数的，然后再排除N/4的情况，如果没有
return false。
【在 g*****c 的大作中提到】
: 怎么binary search做？求问～
|
c*******4
发帖数: 51 | 56 你说的对，我当时写完greedy后发现不对就用dp这样做的
【在 b********a 的大作中提到】
: 第五题怎么做？
: dp复杂度是2的n次幂。。。。
|
c*******4
发帖数: 51 | 57 讨论讨论，当时给的方程是这种形式 bool existN(vector& array)，这样是否需
要先把数组存到树里？这样存需要N吧。
【在 s******x 的大作中提到】
: 先建立一个tree，然后后面做search，是吧。
: 所以寻找是logN，但是前面会先建立tree，那就懂了。谢谢！
|
f********i
发帖数: 546 | 58 请问你们这个都是什么level的面试啊？ 是master刚毕业的面试题吗？ 还是有几年工
作经验的？ 我怎么连题目都看不懂？ |
P**********0
发帖数: 412 | |
c*******4
发帖数: 51 | 60 我本科，工作2年，general SWE的面试，可能我有些题目没说清楚
【在 f********i 的大作中提到】
: 请问你们这个都是什么level的面试啊？ 是master刚毕业的面试题吗？ 还是有几年工
: 作经验的？ 我怎么连题目都看不懂？
|
|
|
h**p
发帖数: 211 | 61 LZ能解释下4（3）吗？不是很明白，要求返回的是什么值？
谢谢
howmanyPalindrome
有a
续]
【在 c*******4 的大作中提到】
: No offer。发面经供大家参考，5轮
: 1：（1）：写一个bool Palindrome(string s)，就是测s是否是Palindrome。
: （2）：已知bool Palindrome(string s)方程，写一个 int howmanyPalindrome
: (string s), 输入s，返回s中包含多少个Palindrome的单词。 例如abbbac返回10，有a
: ,b,b,b,a,c,bb, bbb, bb, abbba.
: 2: 给一个树root的pointer，树包含多个分支，树结构要自己创造。求一条最长路径。
: 例如（括号对应上面node）
: 树： 2
: | | | |
: 5 7 3 6
|
S**********5
发帖数: 896 | |
h*******0
发帖数: 270 | |
s********g
发帖数: 1 | |
c*******4
发帖数: 51 | 65 完全平方解集，做一个：int minsol（int i），
返回的数为最少构成i的平方合的个数，
举例子就是如果输入数为
1，i=1, 输出为1， 因为最小1个数的平方数就能构成i，返回1。 1^2=1;
3, i=3, 最小3个数的平方数能构成i，所以返回3. 1^2+1^2+1^2=3;
5, i=5, 当然可以5个1的平方，但可以2^2+1^2=5, 这样构成的数为2 为最少的，所以
返回2；
9，返回1，因为3^2
12. 可以3^2+1^2+1^2+1^2(4个数)或者 2^2+2^2+2^2(3个数)或者还有1啥的等等，最后
3个数最少，所以返回3
……
可能还是没说清楚，如果还不懂在问哈
【在 h**p 的大作中提到】
: LZ能解释下4（3）吗？不是很明白，要求返回的是什么值？
: 谢谢
:
: howmanyPalindrome
: 有a
: 续]
|
c*******4
发帖数: 51 | 66 因该是最后一题吧，当时先写了贪心算法，最后发现如果像4，10，2，3这种，A先选，
贪心算法就有问题，然后暴力解了，时间到了写完，没来及带值检验，感觉他还有后续
问题没问
【在 h*******0 的大作中提到】
: 楼主你哪道题没答好？ 怎么没有offer？
|
h**p
发帖数: 211 | 67 明白了，多谢LZ解释
【在 c*******4 的大作中提到】
: 完全平方解集，做一个：int minsol（int i），
: 返回的数为最少构成i的平方合的个数，
: 举例子就是如果输入数为
: 1，i=1, 输出为1， 因为最小1个数的平方数就能构成i，返回1。 1^2=1;
:
: 3, i=3, 最小3个数的平方数能构成i，所以返回3. 1^2+1^2+1^2=3;
:
: 5, i=5, 当然可以5个1的平方，但可以2^2+1^2=5, 这样构成的数为2 为最少的，所以
: 返回2；
:
|
j**********0
发帖数: 20 | 68 一个sorted array，如果其中有一个数重复超过array里面总数的1/4 return
true。就是说{2，2，3，4} return true
{1，1，2，3，4，5，6，7} return false。
How can this be O(logN)?
I am thinking check position 1/4, 2/4, 3/4, 4/4 for continuity.
But the worst case could be O(N). For example, we could spend 1/4* at first
position, second, and third position and find the element in last position.
The total time is 3/4*N-3=O(N) |
w********5
发帖数: 81 | 69 谢谢面经。最后一个题我有详细解法，整理一下发出来。 |
h******e
发帖数: 52 | 70 4 和 5大家有解吗？
..
【在 c*******4 的大作中提到】
: 这题我是硬解的找一个vector存下所有从1到n的可能类似vector sol={1,3,2,1..
: .}，然后有点类似找n sum那种根据1到n-1的情况推1到n的。我觉得应该有好的算法吧
: ，我当时没时间了他让我暴力从n-1数组中一个个凑。
|
|
|
l******s
发帖数: 3045 | 71 5 seems easier.
Below is Divide and Conquer for 4.(2)
private bool quarterPart(int[] nums)
{
for (int counter = 0, left = 0; counter < 8; counter++)
{
int i = left, j = left + (nums.Length >> 2);
if (j >= nums.Length) return false;
if (nums[i] == nums[j]) return true;
for (int mid = (i + j) >> 1; i < j; left = i, mid = (i + j) >> 1)
if (nums[i] == nums[mid] || nums[i] != nums[mid] && nums[mid] != nums[
j])
i = mid + 1;
else if (nums[mid] == nums[j])
{
//Get left of index which is equal to nums[j]
int subLeft = i, subRight = mid;
while (subLeft < subRight)
{
int subMid = (subLeft + subRight) >> 1;
if (nums[subMid] == nums[j]) subRight = subMid;
else subLeft = subMid + 1;
}
left = subLeft;
break;
}
}
return false;
}
【在 h******e 的大作中提到】
: 4 和 5大家有解吗？
:
: ..
|
c***u
发帖数: 4107 | 72 请问, 第五题, fish game, 规定了谁先取吗? A或者B, 还是随便谁先取都可以, 或者
谁先取也是一个参数 |
