Skip to content

Commit 5be8de3

Browse files
yanglbmeyanglbme
committed
feat: add solutions to lcof problem: No.66
1 parent 0ddc119 commit 5be8de3

File tree

12 files changed

+110
-34
lines changed

12 files changed

+110
-34
lines changed

‎lcof/面试题38. 字符串的排列/Solution.py

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -15,4 +15,4 @@ def dfs(i):
1515
ans = []
1616
cs = list(s)
1717
dfs(0)
18-
return ans
18+
return ans

‎lcof/面试题57. 和为s的两个数字/Solution.js

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -16,4 +16,4 @@ var twoSum = function (nums, target) {
1616
++l;
1717
}
1818
}
19-
};
19+
};

‎lcof/面试题66. 构建乘积数组/README.md

Lines changed: 63 additions & 14 deletions
Original file line numberDiff line numberDiff line change
@@ -27,7 +27,17 @@
2727

2828
<!-- 这里可写通用的实现逻辑 -->
2929

30-
`B[i] = (A[0] * A[1] * ... * A[i-1]) * (A[i+1] * ... * A[n-1])`
30+
**方法一：两次遍历**
31+
32+
我们先创建一个长度为 $n$ 的答案数组 $ans$。
33+
34+
接下来，我们从左到右遍历数组 $a$，过程中维护一个变量 $left$，表示当前元素左边所有元素的乘积，初始时 $left=1$。当遍历到 $a[i]$ 时，我们将 $left$ 赋值给 $ans[i]$，然后 $left$ 乘以 $a[i]$，即 $left \leftarrow left \times a[i]$。
35+
36+
然后，我们从右到左遍历数组 $a$，过程中维护一个变量 $right$，表示当前元素右边所有元素的乘积，初始时 $right=1$。当遍历到 $a[i]$ 时，我们将 $ans[i]$ 乘上 $right$，然后 $right$ 乘以 $a[i]$，即 $right \leftarrow right \times a[i]$。
37+
38+
最终，数组 $ans$ 即为所求的答案。
39+
40+
时间复杂度 $O(n)$，其中 $n$ 为数组 $a$ 的长度。忽略答案数组的空间消耗，空间复杂度 $O(1)$。
3141

3242
<!-- tabs:start -->
3343

@@ -39,15 +49,15 @@
3949
class Solution:
4050
def constructArr(self, a: List[int]) -> List[int]:
4151
n = len(a)
42-
output = [1] * n
52+
ans = [0] * n
4353
left = right = 1
4454
for i in range(n):
45-
output[i] = left
55+
ans[i] = left
4656
left *= a[i]
4757
for i in range(n - 1, -1, -1):
48-
output[i] *= right
58+
ans[i] *= right
4959
right *= a[i]
50-
return output
60+
return ans
5161
```
5262

5363
### **Java**
@@ -58,17 +68,56 @@ class Solution:
5868
class Solution {
5969
public int[] constructArr(int[] a) {
6070
int n = a.length;
61-
int[] output = new int[n];
71+
int[] ans = new int[n];
6272
for (int i = 0, left = 1; i < n; ++i) {
63-
output[i] = left;
73+
ans[i] = left;
6474
left *= a[i];
6575
}
6676
for (int i = n - 1, right = 1; i >= 0; --i) {
67-
output[i] *= right;
77+
ans[i] *= right;
78+
right *= a[i];
79+
}
80+
return ans;
81+
}
82+
}
83+
```
84+
85+
### **C++**
86+
87+
```cpp
88+
class Solution {
89+
public:
90+
vector<int> constructArr(vector<int>& a) {
91+
int n = a.size();
92+
vector<int> ans(n);
93+
for (int i = 0, left = 1; i < n; ++i) {
94+
ans[i] = left;
95+
left *= a[i];
96+
}
97+
for (int i = n - 1, right = 1; ~i; --i) {
98+
ans[i] *= right;
6899
right *= a[i];
69100
}
70-
return output;
101+
return ans;
71102
}
103+
};
104+
```
105+
106+
### **Go**
107+
108+
```go
109+
func constructArr(a []int) []int {
110+
n := len(a)
111+
ans := make([]int, n)
112+
for i, left := 0, 1; i < n; i++ {
113+
ans[i] = left
114+
left *= a[i]
115+
}
116+
for i, right := n-1, 1; i >= 0; i-- {
117+
ans[i] *= right
118+
right *= a[i]
119+
}
120+
return ans
72121
}
73122
```
74123

@@ -81,16 +130,16 @@ class Solution {
81130
*/
82131
var constructArr = function (a) {
83132
const n = a.length;
84-
let output = new Array(n);
133+
const ans = new Array(n);
85134
for (let i = 0, left = 1; i < n; ++i) {
86-
output[i] = left;
135+
ans[i] = left;
87136
left *= a[i];
88137
}
89-
for (let i = n - 1, right = 1; i >= 0; --i) {
90-
output[i] *= right;
138+
for (let i = n - 1, right = 1; ~i; --i) {
139+
ans[i] *= right;
91140
right *= a[i];
92141
}
93-
return output;
142+
return ans;
94143
};
95144
```
96145

‎lcof/面试题66. 构建乘积数组/Solution.cpp

Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,16 @@
1+
class Solution {
2+
public:
3+
vector<int> constructArr(vector<int>& a) {
4+
int n = a.size();
5+
vector<int> ans(n);
6+
for (int i = 0, left = 1; i < n; ++i) {
7+
ans[i] = left;
8+
left *= a[i];
9+
}
10+
for (int i = n - 1, right = 1; ~i; --i) {
11+
ans[i] *= right;
12+
right *= a[i];
13+
}
14+
return ans;
15+
}
16+
};

‎lcof/面试题66. 构建乘积数组/Solution.go

Lines changed: 13 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,13 @@
1+
func constructArr(a []int) []int {
2+
n := len(a)
3+
ans := make([]int, n)
4+
for i, left := 0, 1; i < n; i++ {
5+
ans[i] = left
6+
left *= a[i]
7+
}
8+
for i, right := n-1, 1; i >= 0; i-- {
9+
ans[i] *= right
10+
right *= a[i]
11+
}
12+
return ans
13+
}

‎lcof/面试题66. 构建乘积数组/Solution.java

Lines changed: 4 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -1,15 +1,15 @@
11
class Solution {
22
public int[] constructArr(int[] a) {
33
int n = a.length;
4-
int[] output = new int[n];
4+
int[] ans = new int[n];
55
for (int i = 0, left = 1; i < n; ++i) {
6-
output[i] = left;
6+
ans[i] = left;
77
left *= a[i];
88
}
99
for (int i = n - 1, right = 1; i >= 0; --i) {
10-
output[i] *= right;
10+
ans[i] *= right;
1111
right *= a[i];
1212
}
13-
return output;
13+
return ans;
1414
}
1515
}

‎lcof/面试题66. 构建乘积数组/Solution.js

Lines changed: 5 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -4,14 +4,14 @@
44
*/
55
var constructArr = function (a) {
66
const n = a.length;
7-
let output = new Array(n);
7+
const ans = new Array(n);
88
for (let i = 0, left = 1; i < n; ++i) {
9-
output[i] = left;
9+
ans[i] = left;
1010
left *= a[i];
1111
}
12-
for (let i = n - 1, right = 1; i >= 0; --i) {
13-
output[i] *= right;
12+
for (let i = n - 1, right = 1; ~i; --i) {
13+
ans[i] *= right;
1414
right *= a[i];
1515
}
16-
return output;
16+
return ans;
1717
};

‎lcof/面试题66. 构建乘积数组/Solution.py

Lines changed: 4 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -1,12 +1,12 @@
11
class Solution:
22
def constructArr(self, a: List[int]) -> List[int]:
33
n = len(a)
4-
output = [1] * n
4+
ans = [0] * n
55
left = right = 1
66
for i in range(n):
7-
output[i] = left
7+
ans[i] = left
88
left *= a[i]
99
for i in range(n - 1, -1, -1):
10-
output[i] *= right
10+
ans[i] *= right
1111
right *= a[i]
12-
return output
12+
return ans

‎solution/2500-2599/2557.Maximum Number of Integers to Choose From a Range II/README.md

Lines changed: 0 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -61,7 +61,6 @@
6161

6262
相似题目：[2557. 从一个范围内选择最多整数 II](/solution/2500-2599/2557.Maximum%20Number%20of%20Integers%20to%20Choose%20From%20a%20Range%20II/README.md)
6363

64-
6564
相似题目：[2556. 从一个范围内选择最多整数 I](/solution/2500-2599/2554.Maximum%20Number%20of%20Integers%20to%20Choose%20From%20a%20Range%20I/README.md)
6665

6766
<!-- tabs:start -->

‎solution/2500-2599/2557.Maximum Number of Integers to Choose From a Range II/README_EN.md

Lines changed: 0 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -43,7 +43,6 @@ All these integers are in the range [1, 7], all do not appear in banned, and the
4343
<li><code>1 &lt;= maxSum &lt;= 10<sup>15</sup></code></li>
4444
</ul>
4545

46-
4746
## Solutions
4847

4948
<!-- tabs:start -->

0 commit comments

Comments
 (0)