- 921. Minimum Add to Make Parentheses Valid 使括号有效的最少添加
- 915. Partition Array into Disjoint Intervals 分割数组
- 932. Beautiful Array 漂亮数组
- 940. Distinct Subsequences II 不同的子序列 II
题目地址:https://leetcode.com/problems/product-of-array-except-self/description/
Given an array of n integers where n > 1, nums, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].
Solve it without division and in O(n).
For example, given [1,2,3,4], return [24,12,8,6].
Follow up:
Could you solve it with constant space complexity? (Note: The output array does not count as extra space for the purpose of space complexity analysis.)
当我想了一个用除法做的答案之后就发现题目不允许用除法做233333.
这个题巧妙的地方在于,结果数组不算作空间复杂度里,所以可以用在结果数组中遍历的方式去做。第一次遍历在结果数组里保存每个数字左边的数字乘积,第二个遍历保存的是左边乘积和这个数字右边的乘积的乘积。
所以就得到了出了本身以外的其他元素的乘积。
class Solution(object):
def productExceptSelf(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
answer = []
_len = len(nums)
prod = 1
for i in range(_len):
answer.append(prod)
prod *= nums[i]
prod = 1
for i in range(_len - 1, -1, -1):
answer[i] *= prod
prod *= nums[i]
return answer
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
C++代码如下:
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
const int N = nums.size();
vector<int> res(N, 1);
int prod = 1;
for (int i = 0; i < N; i ++) {
res[i] = prod;
prod *= nums[i];
}
prod = 1;
for (int i = N - 1; i >= 0; i--) {
res[i] *= prod;
prod *= nums[i];
}
return res;
}
};
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
DDKK.COM 弟弟快看-教程,程序员编程资料站,版权归原作者所有
本文经作者:负雪明烛 授权发布,任何组织或个人未经作者授权不得转发
我已经坚持了好几天了……很抱歉遇到这样的问题,但是我只是F#本身的初学者。由于关于类型提供程序的讨论很多,所以我决定建立一个类型提供程序并撰写一篇有关它的论文。当我开始时,我不知道什么是类型提供程序。
我正在开发LAN项目唤醒功能,但是我想控制局域网中计算机是否打开。但是我不想使用ICMP或WMI(我的网络上有DC)。那么,对于此问题,是否还有其他选择,例如“套接字连接”,请检查特定端口是否正在使用
我们有一个旧的VB6应用程序,该应用程序使用Crystal Reports XI生成打印报告。我们已经通过经验发现,如果Crystal Reports打印引擎选择了错误版本的 usp10.dll (W
我正在尝试获取有效的 Android 权限列表。我知道 http://developer.android.com/reference/android/Manifest.permission.html
嗨,我是 nginx 的新手,我试图在我的服务器(运行 Ubuntu 4)上设置它,它已经运行了 apache。 所以在我 apt-get install 它之后,我尝试启动 nginx。然后我收到这
如何在VB 6中检查对象的类型-除了'TypeName'之外,是否还有其他方法,因为无法通过'TypeName'进行检查,我希望使用类似QuichWatch窗口的方法。 最佳答案 对于对象变量,请使用
我的 JSP 应用程序中有一个错误。发布后我的 session 被清除: YAHOO.util.Connect.asyncRequest('POST', Url, callback, post
我是一名优秀的程序员,十分优秀!