f**********t
发帖数: 1001 | 1 unsigned MinJump(vector jumps) {
unsigned res = UINT_MAX;
vector minJumps(jumps.size(), UINT_MAX);
if (jumps.empty()) {
return res;
}
minJumps[0] = 0;
for (size_t i = 0; i < jumps.size(); ++i) {
if (jumps[i] == 0 || minJumps[i] >= res) {
continue;
}
if (i + jumps[i] >= jumps.size()) {
res = min(res, minJumps[i] + 1);
continue;
}
for (size_t k = jumps[i]; k != 0; --k) {
minJumps[i + k] = min(minJumps[i + k], minJumps[... 阅读全帖 |
|
f**********t
发帖数: 1001 | 2 unsigned MinJump(vector jumps) {
vector minJumps(jumps.size(), UINT_MAX);
if (jumps.empty()) {
return UINT_MAX;
}
minJumps[0] = 0;
if (jumps[0] >= jumps.size()) {
return 1;
}
for (size_t i = 0; i < jumps.size(); ++i) {
if (jumps[i] == 0) {
continue;
}
for (size_t k = jumps[i]; k != 0; --k) {
minJumps[i + k] = min(minJumps[i + k], minJumps[i] + 1);
if (jumps[i + k] + i + k >= jumps.size()) {
return minJumps[i + k] + 1... 阅读全帖 |
|
e***s
发帖数: 799 | 3 public static int JumpGameII(int[] A)
{
if (A.Length <= 1)
return 0;
int[] MinJumps = new int[A.Length];
MinJumps[0] = 0;
for (int i = 1; i < A.Length; i++)
{
int Min = Int16.MaxValue;
for (int j = 0; j < i; j++)
{
if (MinJumps[j] >= Min)
continue;
if (A[j] >= i - j)
Min = Math.M... 阅读全帖 |
|
e***s
发帖数: 799 | 4 public static int JumpGameII(int[] A)
{
if (A.Length <= 1)
return 0;
int[] MinJumps = new int[A.Length];
MinJumps[0] = 0;
for (int i = 1; i < A.Length; i++)
{
int Min = Int16.MaxValue;
for (int j = 0; j < i; j++)
{
if (MinJumps[j] >= Min)
continue;
if (A[j] >= i - j)
Min = Math.M... 阅读全帖 |
|
f*********m
发帖数: 726 | 5 （1）Jump Game：
Given an array of non-negative integers, you are initially positioned at the
first index of the array.
Each element in the array represents your maximum jump length at that
position.
Determine if you are able to reach the last index.
For example:
A = [2,3,1,1,4], return true.
A = [3,2,1,0,4], return false.
不知道我下面的解法对不对？用了DP，用f存储以前的计算结果。
bool jump(vector& A, int n, vector f){
if (n == 0){
f[0] = true;
return true;
}
if (f[n] != -1)
retur... 阅读全帖 |
|
i***e
发帖数: 452 | 6 上周二去的狗狗家onsite, 今天发信问HR update, HR说还在收集feedback, 说明天可
以给个update. 真心求bless! 希望这次可以成了， 谢谢大家！
----------------------
Update: hr今天打电话说明天hiring committee 出结果！ 还说透露点feedback： ＂
some are good, some are not consistent ", 然后说coding is good！ 看来有一些
不好的feedback 了！ 继续求bless 了！只能看人品爆发了！谢谢
--------------------------------------------------
update2： 写个面经了。。
1） int pow(int n, int m)
2) 写一个类是timer 的东西， 例如给个数值t和函数，等t时间之后call 这个函数。
（然后问有多个这些如果支持多次调用怎么办， 有哪些问题之类的）
3）给一个函数 void f(){.... return;} 然后问在return 语句的时候程序cl... 阅读全帖 |
|
f*********m
发帖数: 726 | 7 从版上大牛的面经中找到的：
---------------
1）原题can Jump, 然后拓展到minJump, 我用dp + greedy从左边做， 写完code,他要
求再说说从右边忘左边如何高。 我说还是dp + greedy（这个估计是他自己背的答案）
，他想了会说， 算了，好像跟你的一样！我也不知道是不是一样就move 到下一道题了。
从右往左好像不好想吧，从左往右跳（最后跳到最右边）和从右往左跳（最后跳到最左
边）不是等假的吧？
-------------
2）一个BST tree， 现在要求在每个node， 添加一个succeesor的指针。 用递归搞定
（这个在他提示下搞出的，code 用递归就几行而已）
考虑inorder 的succeesor。用inorder traverse，大家看对不对？
void inorder(node* n, node*& prev)
{
if (!n)
return;
inorder(n->left, prev);
if (!pre)
pre->succeesor = n;
pre = n;
inord... 阅读全帖 |
|
