g*****5
发帖数: 87 | 1 刚面完
题目不难，不过是烙印，拿不定
1. Given an integer array, place all the zeros to the end.
{4, 0, 5, 0, 8} => { 4, 5, 8, 0, 0}
follow up：不care顺数的话尽量少用write，swap就行
2.The number of valid combinations of a strings for given input array a[],
where a=>1, z => 26, and 0 <= a[i] <= 9
{1,1,1} => { aaa, ak, ka} => 3
{1,1,0} => {aj} => 1
follow up: O(1) memory
20分钟2题就写完了，非要我做了一堆test
他说马上就提交feedback，求bless | r*******e
发帖数: 971 | 2 new grad 么？
【在 g*****5 的大作中提到】
: 刚面完
: 题目不难，不过是烙印，拿不定
: 1. Given an integer array, place all the zeros to the end.
: {4, 0, 5, 0, 8} => { 4, 5, 8, 0, 0}
: follow up：不care顺数的话尽量少用write，swap就行
: 2.The number of valid combinations of a strings for given input array a[],
: where a=>1, z => 26, and 0 <= a[i] <= 9
: {1,1,1} => { aaa, ak, ka} => 3
: {1,1,0} => {aj} => 1
: follow up: O(1) memory
| g*****5
发帖数: 87 | 3
intern
【在 r*******e 的大作中提到】
: new grad 么？
| d*******5
发帖数: 22 | 4 啥叫 “不care顺数的话尽量少用write”？ | r*******e
发帖数: 971 | 5 不需要维持原来顺序，则可以直接交换0 与最后一个非0的数。
【在 d*******5 的大作中提到】
: 啥叫 “不care顺数的话尽量少用write”？
| r****7
发帖数: 2282 | 6 follow up是说你先不是swap，不是O(1) memory么？
【在 g*****5 的大作中提到】
: 刚面完
: 题目不难，不过是烙印，拿不定
: 1. Given an integer array, place all the zeros to the end.
: {4, 0, 5, 0, 8} => { 4, 5, 8, 0, 0}
: follow up：不care顺数的话尽量少用write，swap就行
: 2.The number of valid combinations of a strings for given input array a[],
: where a=>1, z => 26, and 0 <= a[i] <= 9
: {1,1,1} => { aaa, ak, ka} => 3
: {1,1,0} => {aj} => 1
: follow up: O(1) memory
| g*****5
发帖数: 87 | 7
没懂你说什么，follow up的解法是swap
之前我做的时候是把所有非0数往左移动，按顺序的
【在 r****7 的大作中提到】
: follow up是说你先不是swap，不是O(1) memory么？
| k****r
发帖数: 807 | | s*i
发帖数: 5025 | 9 The first one?
void placeZerosToEnd (int[] A)
{
if (A == null)
{
return;
}
int endPos = A.length - 1;
for (int i = 0; i < endPos; i++)
{
if (A[i] == 0)
{
A[i] = A[endPos];
A[endPos] = 0;
endPos --;
i--; //need to test this newly swapped element
}
}
}
【在 g*****5 的大作中提到】
: 刚面完
: 题目不难，不过是烙印，拿不定
: 1. Given an integer array, place all the zeros to the end.
: {4, 0, 5, 0, 8} => { 4, 5, 8, 0, 0}
: follow up：不care顺数的话尽量少用write，swap就行
: 2.The number of valid combinations of a strings for given input array a[],
: where a=>1, z => 26, and 0 <= a[i] <= 9
: {1,1,1} => { aaa, ak, ka} => 3
: {1,1,0} => {aj} => 1
: follow up: O(1) memory
| n*****r
发帖数: 106 | 10 谢谢楼主分享经验
【在 g*****5 的大作中提到】
: 刚面完
: 题目不难，不过是烙印，拿不定
: 1. Given an integer array, place all the zeros to the end.
: {4, 0, 5, 0, 8} => { 4, 5, 8, 0, 0}
: follow up：不care顺数的话尽量少用write，swap就行
: 2.The number of valid combinations of a strings for given input array a[],
: where a=>1, z => 26, and 0 <= a[i] <= 9
: {1,1,1} => { aaa, ak, ka} => 3
: {1,1,0} => {aj} => 1
: follow up: O(1) memory
| | | h*********o
发帖数: 230 | 11 双指针可以了吧。
第二题 你给的DP 解法？
O（1）是指递归吗？多谢
【在 g*****5 的大作中提到】
:
: 没懂你说什么，follow up的解法是swap
: 之前我做的时候是把所有非0数往左移动，按顺序的
| y*****i
发帖数: 141 | | v****a
发帖数: 236 | 13 Leetcode Decode Ways
【在 y*****i 的大作中提到】
: 谁给解释一下第二题的题意？
| l*********8
发帖数: 4642 | 14 {1,1,1} 有三种可能：
[1, 1, 1] 对应 aaa
[1, 11] 对应 ak
[11, 1] 对应 ka
【在 y*****i 的大作中提到】
: 谁给解释一下第二题的题意？
| y*****i
发帖数: 141 | 15 谢谢！
【在 l*********8 的大作中提到】
: {1,1,1} 有三种可能：
: [1, 1, 1] 对应 aaa
: [1, 11] 对应 ak
: [11, 1] 对应 ka
| x*********a
发帖数: 36 | | g********r
发帖数: 89 | 17 array的swap怎么做的？不用write吗？
【在 g*****5 的大作中提到】
: 刚面完
: 题目不难，不过是烙印，拿不定
: 1. Given an integer array, place all the zeros to the end.
: {4, 0, 5, 0, 8} => { 4, 5, 8, 0, 0}
: follow up：不care顺数的话尽量少用write，swap就行
: 2.The number of valid combinations of a strings for given input array a[],
: where a=>1, z => 26, and 0 <= a[i] <= 9
: {1,1,1} => { aaa, ak, ka} => 3
: {1,1,0} => {aj} => 1
: follow up: O(1) memory
| p*********j
发帖数: 47 | 18 public static void placeZerosToEnd(int[] A) {
if (A == null || A.length == 0) {
return;
}
int start = 0;
int end = A.length - 1;
while (start < end) {
if (A[start] == 0) {
while (A[end] == 0) {
end--;
}
if (end <= start) {
break;
}
A[start] = A[end];
A[end] = 0;
end--;
}
start++;
}
for (int i = 0; i < A.length; i++) {
System.out.print(A[i] + ",");
}
System.out.println("--------------");
} | l*****a
发帖数: 14598 | 19 这样写是不是更好呢
while(start
if(A[start]!=0) {
start++;
} else if(A[end]==0) {
end--;
} else {
swap();
start++;
end--;
}
}
【在 p*********j 的大作中提到】
: public static void placeZerosToEnd(int[] A) {
: if (A == null || A.length == 0) {
: return;
: }
: int start = 0;
: int end = A.length - 1;
: while (start < end) {
: if (A[start] == 0) {
: while (A[end] == 0) {
: end--;
| p*********j
发帖数: 47 | 20 public static int validCombinations_O1(int[] A) {
if (A == null || A.length == 0) {
return 0;
}
int prepre = 1;
int pre = (A[0] == 0) ? 0 : 1;
int current = pre;
for (int i = 2; i <= A.length; i++) {
current = 0;
if (A[i - 1] != 0) {
current = pre;
}
int num = A[i - 2] * 10 + A[i - 1];
if (num <= 26 && num >= 10) {
current += prepre;
}
prepre = pre;
pre = current;
}
return current;
} | | | p*********j
发帖数: 47 | 21 学习了，赞成！
【在 l*****a 的大作中提到】
: 这样写是不是更好呢
: while(start: if(A[start]!=0) {
: start++;
: } else if(A[end]==0) {
: end--;
: } else {
: swap();
: start++;
: end--;
| g*****5
发帖数: 87 | 22
递归明显不是O(1)啊
DP优化一下就可以O(1)了
因为DP其实只是用到数组的最后3个数，把这三个数记下来就行了，每次update
【在 h*********o 的大作中提到】
: 双指针可以了吧。
: 第二题 你给的DP 解法？
: O（1）是指递归吗？多谢
| g*****5
发帖数: 87 | 23
这已经是第二轮电面了
【在 k****r 的大作中提到】
: intern只一轮电面吗？谢谢
| a*****a
发帖数: 46 | 24 第一题，直接一直把不是0的往前移动，然后最后再把空余的位置赋值为0.这样也可以
保持顺序。
#include
#include
using namespace std;
void place_zeros(vector & v) {
int L = 0;
while(v[L] != 0) L++;
int R = L+1;
while(R
if (v[R] == 0) {
R++;
continue;
}
v[L] = v[R];
L++; R++;
}
while(L
v[L] = 0;
L++;
}
}
int main(int argc, const char *argv[])
{
vector v = {0, 1, 2, 3};
place_zeros(v);
for(auto i: v) cout << i << endl;
return 0;
} | g*****5
发帖数: 87 | 25 刚面完
题目不难，不过是烙印，拿不定
1. Given an integer array, place all the zeros to the end.
{4, 0, 5, 0, 8} => { 4, 5, 8, 0, 0}
follow up：不care顺数的话尽量少用write，swap就行
2.The number of valid combinations of a strings for given input array a[],
where a=>1, z => 26, and 0 <= a[i] <= 9
{1,1,1} => { aaa, ak, ka} => 3
{1,1,0} => {aj} => 1
follow up: O(1) memory
20分钟2题就写完了，非要我做了一堆test
他说马上就提交feedback，求bless
__________________________________
I got the offer, thx everyone | r*******e
发帖数: 971 | 26 new grad 么？
【在 g*****5 的大作中提到】
: 刚面完
: 题目不难，不过是烙印，拿不定
: 1. Given an integer array, place all the zeros to the end.
: {4, 0, 5, 0, 8} => { 4, 5, 8, 0, 0}
: follow up：不care顺数的话尽量少用write，swap就行
: 2.The number of valid combinations of a strings for given input array a[],
: where a=>1, z => 26, and 0 <= a[i] <= 9
: {1,1,1} => { aaa, ak, ka} => 3
: {1,1,0} => {aj} => 1
: follow up: O(1) memory
| g*****5
发帖数: 87 | 27
intern
【在 r*******e 的大作中提到】
: new grad 么？
| d*******5
发帖数: 22 | 28 啥叫 “不care顺数的话尽量少用write”？ | r*******e
发帖数: 971 | 29 不需要维持原来顺序，则可以直接交换0 与最后一个非0的数。
【在 d*******5 的大作中提到】
: 啥叫 “不care顺数的话尽量少用write”？
| r****7
发帖数: 2282 | 30 follow up是说你先不是swap，不是O(1) memory么？
【在 g*****5 的大作中提到】
: 刚面完
: 题目不难，不过是烙印，拿不定
: 1. Given an integer array, place all the zeros to the end.
: {4, 0, 5, 0, 8} => { 4, 5, 8, 0, 0}
: follow up：不care顺数的话尽量少用write，swap就行
: 2.The number of valid combinations of a strings for given input array a[],
: where a=>1, z => 26, and 0 <= a[i] <= 9
: {1,1,1} => { aaa, ak, ka} => 3
: {1,1,0} => {aj} => 1
: follow up: O(1) memory
| | | g*****5
发帖数: 87 | 31
没懂你说什么，follow up的解法是swap
之前我做的时候是把所有非0数往左移动，按顺序的
【在 r****7 的大作中提到】
: follow up是说你先不是swap，不是O(1) memory么？
| k****r
发帖数: 807 | | s*i
发帖数: 5025 | 33 The first one?
void placeZerosToEnd (int[] A)
{
if (A == null)
{
return;
}
int endPos = A.length - 1;
for (int i = 0; i < endPos; i++)
{
if (A[i] == 0)
{
A[i] = A[endPos];
A[endPos] = 0;
endPos --;
i--; //need to test this newly swapped element
}
}
}
【在 g*****5 的大作中提到】
: 刚面完
: 题目不难，不过是烙印，拿不定
: 1. Given an integer array, place all the zeros to the end.
: {4, 0, 5, 0, 8} => { 4, 5, 8, 0, 0}
: follow up：不care顺数的话尽量少用write，swap就行
: 2.The number of valid combinations of a strings for given input array a[],
: where a=>1, z => 26, and 0 <= a[i] <= 9
: {1,1,1} => { aaa, ak, ka} => 3
: {1,1,0} => {aj} => 1
: follow up: O(1) memory
| h*********o
发帖数: 230 | 34 双指针可以了吧。
第二题 你给的DP 解法？
O（1）是指递归吗？多谢
【在 g*****5 的大作中提到】
:
: 没懂你说什么，follow up的解法是swap
: 之前我做的时候是把所有非0数往左移动，按顺序的
| y*****i
发帖数: 141 | | v****a
发帖数: 236 | 36 Leetcode Decode Ways
【在 y*****i 的大作中提到】
: 谁给解释一下第二题的题意？
| l*********8
发帖数: 4642 | 37 {1,1,1} 有三种可能：
[1, 1, 1] 对应 aaa
[1, 11] 对应 ak
[11, 1] 对应 ka
【在 y*****i 的大作中提到】
: 谁给解释一下第二题的题意？
| y*****i
发帖数: 141 | 38 谢谢！
【在 l*********8 的大作中提到】
: {1,1,1} 有三种可能：
: [1, 1, 1] 对应 aaa
: [1, 11] 对应 ak
: [11, 1] 对应 ka
| x*********a
发帖数: 36 | | g********r
发帖数: 89 | 40 array的swap怎么做的？不用write吗？
【在 g*****5 的大作中提到】
: 刚面完
: 题目不难，不过是烙印，拿不定
: 1. Given an integer array, place all the zeros to the end.
: {4, 0, 5, 0, 8} => { 4, 5, 8, 0, 0}
: follow up：不care顺数的话尽量少用write，swap就行
: 2.The number of valid combinations of a strings for given input array a[],
: where a=>1, z => 26, and 0 <= a[i] <= 9
: {1,1,1} => { aaa, ak, ka} => 3
: {1,1,0} => {aj} => 1
: follow up: O(1) memory
| | | p*********j
发帖数: 47 | 41 public static void placeZerosToEnd(int[] A) {
if (A == null || A.length == 0) {
return;
}
int start = 0;
int end = A.length - 1;
while (start < end) {
if (A[start] == 0) {
while (A[end] == 0) {
end--;
}
if (end <= start) {
break;
}
A[start] = A[end];
A[end] = 0;
end--;
}
start++;
}
for (int i = 0; i < A.length; i++) {
System.out.print(A[i] + ",");
}
System.out.println("--------------");
} | l*****a
发帖数: 14598 | 42 这样写是不是更好呢
while(start
if(A[start]!=0) {
start++;
} else if(A[end]==0) {
end--;
} else {
swap();
start++;
end--;
}
}
【在 p*********j 的大作中提到】
: public static void placeZerosToEnd(int[] A) {
: if (A == null || A.length == 0) {
: return;
: }
: int start = 0;
: int end = A.length - 1;
: while (start < end) {
: if (A[start] == 0) {
: while (A[end] == 0) {
: end--;
| p*********j
发帖数: 47 | 43 public static int validCombinations_O1(int[] A) {
if (A == null || A.length == 0) {
return 0;
}
int prepre = 1;
int pre = (A[0] == 0) ? 0 : 1;
int current = pre;
for (int i = 2; i <= A.length; i++) {
current = 0;
if (A[i - 1] != 0) {
current = pre;
}
int num = A[i - 2] * 10 + A[i - 1];
if (num <= 26 && num >= 10) {
current += prepre;
}
prepre = pre;
pre = current;
}
return current;
} | p*********j
发帖数: 47 | 44 学习了，赞成！
【在 l*****a 的大作中提到】
: 这样写是不是更好呢
: while(start: if(A[start]!=0) {
: start++;
: } else if(A[end]==0) {
: end--;
: } else {
: swap();
: start++;
: end--;
| g*****5
发帖数: 87 | 45
递归明显不是O(1)啊
DP优化一下就可以O(1)了
因为DP其实只是用到数组的最后3个数，把这三个数记下来就行了，每次update
【在 h*********o 的大作中提到】
: 双指针可以了吧。
: 第二题 你给的DP 解法？
: O（1）是指递归吗？多谢
| g*****5
发帖数: 87 | 46
这已经是第二轮电面了
【在 k****r 的大作中提到】
: intern只一轮电面吗？谢谢
| a*****a
发帖数: 46 | 47 第一题，直接一直把不是0的往前移动，然后最后再把空余的位置赋值为0.这样也可以
保持顺序。
#include
#include
using namespace std;
void place_zeros(vector & v) {
int L = 0;
while(v[L] != 0) L++;
int R = L+1;
while(R
if (v[R] == 0) {
R++;
continue;
}
v[L] = v[R];
L++; R++;
}
while(L
v[L] = 0;
L++;
}
}
int main(int argc, const char *argv[])
{
vector v = {0, 1, 2, 3};
place_zeros(v);
for(auto i: v) cout << i << endl;
return 0;
} | p*****9
发帖数: 273 | | p*****9
发帖数: 273 | |
|
