|
|---|
|
|
|
|
|
|
x********o
发帖数: 519 | 1 [Coding Q1]: Given an array A, output another array B such that B[k]=product
of all elements in A but A[k]. You are not allowed to use division. | i**********e
发帖数: 1145 | 2 这题这里有解答，你可以看看：
http://www.ihas1337code.com/2010/04/multiplication-of-numbers.h
给你另一题的变种：
Equilibrium index of an array is an index such that the sum of elements at
lower indexes is equal to the sum of elements at higher indexes. For example
, in an array A:
A[0] = -7, A[1] = 1, A[2] = 5, A[3] = 2, A[4] = -4, A[5] = 3, A[6]=0
3 is an equilibrium index, because:
A[0] + A[1] + A[2] = A[4] + A[5] + A[6]
6 is also an equilibrium index, because sum of zero elements is zero, i.e.,
A[0] + A[1] + A[2] + A[3] + A[4] + A[5]=0
7 is not an equilibrium index, because it is not a valid index of array A.
Write a function int equilibrium(int[] arr, int n); that given a sequence
arr[] of size n, returns an equilibrium index (if any) or -1 if no
equilibrium indexes exist.
一些常见面试题的答案与总结 -
http://www.ihas1337code.com | s**x
发帖数: 7506 | 3 你的网站还不错， 怎么起了这么个怪怪的名字？
example
,
【在 i**********e 的大作中提到】
: 这题这里有解答，你可以看看：
: http://www.ihas1337code.com/2010/04/multiplication-of-numbers.h
: 给你另一题的变种：
: Equilibrium index of an array is an index such that the sum of elements at
: lower indexes is equal to the sum of elements at higher indexes. For example
: , in an array A:
: A[0] = -7, A[1] = 1, A[2] = 5, A[3] = 2, A[4] = -4, A[5] = 3, A[6]=0
: 3 is an equilibrium index, because:
: A[0] + A[1] + A[2] = A[4] + A[5] + A[6]
: 6 is also an equilibrium index, because sum of zero elements is zero, i.e.,
| O******n
发帖数: 1505 | 4 size = 10
a = []
for i in range(size):
a.append(i+1)
print a
t1 = [0]*size
t2 = [0]*size
result = 1
for i in range(size):
result = result * a[i]
t[i] = result
result = 1
for i in range(size-1, -1, -1):
result = result * a[i]
t2[i] = result
output = [0]*size
for i in range(1, size-1):
output[i] = t1[i-1]*t2[i+1]
output[0] = t2[1]
output[size-1] = t1[size-2]
print output
product
【在 x********o 的大作中提到】
: [Coding Q1]: Given an array A, output another array B such that B[k]=product
: of all elements in A but A[k]. You are not allowed to use division.
| y****n
发帖数: 579 | 5 变题有类似不能用减法的要求吗？
at
example
i.e.,
【在 i**********e 的大作中提到】
: 这题这里有解答，你可以看看：
: http://www.ihas1337code.com/2010/04/multiplication-of-numbers.h
: 给你另一题的变种：
: Equilibrium index of an array is an index such that the sum of elements at
: lower indexes is equal to the sum of elements at higher indexes. For example
: , in an array A:
: A[0] = -7, A[1] = 1, A[2] = 5, A[3] = 2, A[4] = -4, A[5] = 3, A[6]=0
: 3 is an equilibrium index, because:
: A[0] + A[1] + A[2] = A[4] + A[5] + A[6]
: 6 is also an equilibrium index, because sum of zero elements is zero, i.e.,
| W**********r
发帖数: 8927 | | i**********e
发帖数: 1145 | 7 sdlx:
我也觉得怪怪，似乎不是很多人懂 1337 的意思。你有想到其他的名字吗？
Oceanian:
你这个可以，但是用了 2*n 的空间。
yulian:
可以减。只要不用额外空间就行，O(n) run time。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com | z****d
发帖数: 89 | 8 看了下ihas1337code上的解法，
思路类似，觉得对equilibram的话改下就好
for (int i = 0; i < n; i++) {
OUTPUT[i] += left;
OUTPUT[n - 1 - i] -= right;
left += A[i];
right -= A[n - 1 - i];
}
然后看output里值为0的就是要找的index
可能会找到不止一个
这样算不算用额外空间。。 | r*******y
发帖数: 1081 | 9 good idea, but last line should be right+= A[n - 1 - i];
【在 z****d 的大作中提到】
: 看了下ihas1337code上的解法，
: 思路类似，觉得对equilibram的话改下就好
: for (int i = 0; i < n; i++) {
: OUTPUT[i] += left;
: OUTPUT[n - 1 - i] -= right;
: left += A[i];
: right -= A[n - 1 - i];
: }
: 然后看output里值为0的就是要找的index
: 可能会找到不止一个
| N******r
发帖数: 26 | 10 能不能这样考虑呢：先获取所有元素的乘积，然后除以当前的元素就可以得到product
of all elements but A[k].
int product = 1;
for(int i = 0; i < A.length; i++)
{
product *= A[i];
}
for(int j = 0; j < A.length; j++)
{
B[j] = product/a[j];
}
不知道可不可行，请指教。。 | | | m****t
发帖数: 555 | 11
product
题目已经说了不能用除法。
【在 N******r 的大作中提到】
: 能不能这样考虑呢：先获取所有元素的乘积，然后除以当前的元素就可以得到product
: of all elements but A[k].
: int product = 1;
: for(int i = 0; i < A.length; i++)
: {
: product *= A[i];
: }
: for(int j = 0; j < A.length; j++)
: {
: B[j] = product/a[j];
| N******r
发帖数: 26 | | m****t
发帖数: 555 | 13
You are not allowed to use division.
【在 N******r 的大作中提到】
: 没看到不许用除法 ：）
| N******r
发帖数: 26 | 14 谢谢提醒。我的意思是做题之前没留意到不许用除法
【在 m****t 的大作中提到】
:
: You are not allowed to use division.
| f****4
发帖数: 1359 | 15 你要是把网站改成中文的那就更好，特别是题目和讨论
别让老印啥的看了和我们竞争
【在 i**********e 的大作中提到】
: sdlx:
: 我也觉得怪怪，似乎不是很多人懂 1337 的意思。你有想到其他的名字吗？
: Oceanian:
: 你这个可以，但是用了 2*n 的空间。
: yulian:
: 可以减。只要不用额外空间就行，O(n) run time。
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com
| z****d
发帖数: 89 | 16
哦，对的，疏忽下打错了。。
谢谢指出～～
【在 r*******y 的大作中提到】
: good idea, but last line should be right+= A[n - 1 - i];
| i**********e
发帖数: 1145 | 17 这样算额外空间，因为你需要另一个数组。
这题不用想太复杂，数组遍历两次就行，不需要额外空间。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
【在 z****d 的大作中提到】
: 看了下ihas1337code上的解法，
: 思路类似，觉得对equilibram的话改下就好
: for (int i = 0; i < n; i++) {
: OUTPUT[i] += left;
: OUTPUT[n - 1 - i] -= right;
: left += A[i];
: right -= A[n - 1 - i];
: }
: 然后看output里值为0的就是要找的index
: 可能会找到不止一个
| g*****k
发帖数: 623 | 18 C[i]=A[0]*A[1]*...*A[i]
D[j]=A[j]*A[j+1]*...A[N]
B[k]=C[k-1]*D[k+1]
product
【在 x********o 的大作中提到】
: [Coding Q1]: Given an array A, output another array B such that B[k]=product
: of all elements in A but A[k]. You are not allowed to use division.
| g*****k
发帖数: 623 | 19 如果可以用减法,那么就是先求总和sum, let left = 0, right = sum
然后从头遍历, 对于index 0, left = 0, right = right - A[0]
对于index i,
left += A[i-1]
right -= A[i]
如果left == right 则返回。
example
,
【在 i**********e 的大作中提到】
: 这题这里有解答，你可以看看：
: http://www.ihas1337code.com/2010/04/multiplication-of-numbers.h
: 给你另一题的变种：
: Equilibrium index of an array is an index such that the sum of elements at
: lower indexes is equal to the sum of elements at higher indexes. For example
: , in an array A:
: A[0] = -7, A[1] = 1, A[2] = 5, A[3] = 2, A[4] = -4, A[5] = 3, A[6]=0
: 3 is an equilibrium index, because:
: A[0] + A[1] + A[2] = A[4] + A[5] + A[6]
: 6 is also an equilibrium index, because sum of zero elements is zero, i.e.,
| g*****k
发帖数: 623 | 20 I checked your solution. Brilliant!!!
巧妙
example
,
【在 i**********e 的大作中提到】
: 这题这里有解答，你可以看看：
: http://www.ihas1337code.com/2010/04/multiplication-of-numbers.h
: 给你另一题的变种：
: Equilibrium index of an array is an index such that the sum of elements at
: lower indexes is equal to the sum of elements at higher indexes. For example
: , in an array A:
: A[0] = -7, A[1] = 1, A[2] = 5, A[3] = 2, A[4] = -4, A[5] = 3, A[6]=0
: 3 is an equilibrium index, because:
: A[0] + A[1] + A[2] = A[4] + A[5] + A[6]
: 6 is also an equilibrium index, because sum of zero elements is zero, i.e.,
| | | g*****i
发帖数: 2162 | 21 先遍历一遍求总的sum
然后用一个变量存储0到i-1的sum,看看是不是等于(sum-a[i])/2.0.
example
,
【在 i**********e 的大作中提到】
: 这题这里有解答，你可以看看：
: http://www.ihas1337code.com/2010/04/multiplication-of-numbers.h
: 给你另一题的变种：
: Equilibrium index of an array is an index such that the sum of elements at
: lower indexes is equal to the sum of elements at higher indexes. For example
: , in an array A:
: A[0] = -7, A[1] = 1, A[2] = 5, A[3] = 2, A[4] = -4, A[5] = 3, A[6]=0
: 3 is an equilibrium index, because:
: A[0] + A[1] + A[2] = A[4] + A[5] + A[6]
: 6 is also an equilibrium index, because sum of zero elements is zero, i.e.,
| c*********t
发帖数: 2921 | 22 怎么数组遍历两次解决equilibrium index的问题？in O(n).
谢谢！
【在 i**********e 的大作中提到】
: 这样算额外空间，因为你需要另一个数组。
: 这题不用想太复杂，数组遍历两次就行，不需要额外空间。
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com
| i**********e
发帖数: 1145 | 23 请参考 #19 的答案。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
【在 c*********t 的大作中提到】
: 怎么数组遍历两次解决equilibrium index的问题？in O(n).
: 谢谢！
| s****g
发帖数: 1795 | 24 不懂它为啥不叫做i have 1337而用has
【在 i**********e 的大作中提到】
: sdlx:
: 我也觉得怪怪，似乎不是很多人懂 1337 的意思。你有想到其他的名字吗？
: Oceanian:
: 你这个可以，但是用了 2*n 的空间。
: yulian:
: 可以减。只要不用额外空间就行，O(n) run time。
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com
| b********r
发帖数: 620 | 25 what if sum overflow?
【在 i**********e 的大作中提到】
: 请参考 #19 的答案。
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com
| c******a
发帖数: 789 | 26 1337=leet=elite...
it's a leet language guys... |
|
|
|
|
|
|
|
