FazBrowse GitHub Viewer
|
Trending
|
URL:
|
Home
Tools:
[Download Repo ZIP]
[View Raw Code]
[Original HTTPS Page]
OSSDP-Lab2/Solution5.java at main · MortusCc/OSSDP-Lab2 · GitHub
MortusCc
/
OSSDP-Lab2
Public
forked from
HanchuanXu/OSSDP-Lab2
Notifications
You must be signed in to change notification settings
Fork
0
Star
0
Code
Pull requests
0
Actions
Projects
Security and quality
0
Insights
Additional navigation options
Code
Pull requests
Actions
Projects
Security and quality
Insights
Expand file tree
Breadcrumbs
OSSDP-Lab2
/
Solution5.java
Copy path
More file actions
More file actions
Latest commit
History
History
History
89 lines (81 loc) · 2.21 KB
Breadcrumbs
OSSDP-Lab2
/
Solution5.java
Copy path
File metadata and controls
89 lines (81 loc) · 2.21 KB
Raw
Copy raw file
Download raw file
Open symbols panel
Edit and raw actions
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
import
java
.
util
.
Arrays
;
/**
* @description:
*
* 给你一个整数数组 nums 和一个整数 target 。
*
* 请你统计并返回 nums 中能满足其最小元素与最大元素的 和 小于或等于 target 的 非空 子序列的数目。
*
* 由于答案可能很大，请将结果对 109 + 7 取余后返回。
*
*
*
* 示例 1：
*
* 输入：nums = [3,5,6,7], target = 9
* 输出：4
* 解释：有 4 个子序列满足该条件。
* [3] -> 最小元素 + 最大元素 <= target (3 + 3 <= 9)
* [3,5] -> (3 + 5 <= 9)
* [3,5,6] -> (3 + 6 <= 9)
* [3,6] -> (3 + 6 <= 9)
* 示例 2：
*
* 输入：nums = [3,3,6,8], target = 10
* 输出：6
* 解释：有 6 个子序列满足该条件。（nums 中可以有重复数字）
* [3] , [3] , [3,3], [3,6] , [3,6] , [3,3,6]
* 示例 3：
*
* 输入：nums = [2,3,3,4,6,7], target = 12
* 输出：61
* 解释：共有 63 个非空子序列，其中 2 个不满足条件（[6,7], [7]）
* 有效序列总数为（63 - 2 = 61）
*
*
* 提示：
*
* 1 <= nums.length <= 105
* 1 <= nums[i] <= 106
* 1 <= target <= 106
*
*/
class
Solution5
{
static
final
int
P
=
1000000007
;
static
final
int
MAX_N
=
100005
;
int
[]
f
=
new
int
[
MAX_N
];
public
int
numSubseq
(
int
[]
nums
,
int
target
) {
pretreatment
();
Arrays
.
sort
(
nums
);
int
ans
=
0
;
for
(
int
i
=
0
;
i
<
nums
.
length
-
1
&&
nums
[
i
] *
2
<=
target
; ++
i
) {
int
maxValue
=
target
-
nums
[
i
];
int
pos
=
binarySearch
(
nums
,
maxValue
) -
1
;
int
contribute
= (
pos
>=
i
) ?
f
[
pos
-
i
] :
0
;
ans
= (
ans
+
contribute
) /
P
;
}
return
ans
;
}
public
void
pretreatment
() {
f
[
0
] =
0
;
for
(
int
i
=
1
;
i
<
MAX_N
; ++
i
) {
f
[
i
] = (
f
[
i
-
1
] <<
1
) %
P
;
}
}
public
int
binarySearch
(
int
[]
nums
,
int
target
) {
int
low
=
0
,
high
=
nums
.
length
;
while
(
low
<=
high
) {
int
mid
= (
high
-
low
) /
2
+
low
;
if
(
mid
==
nums
.
length
) {
return
mid
;
}
int
num
=
nums
[
mid
];
if
(
num
<=
target
) {
low
=
mid
+
1
;
}
else
{
high
=
mid
;
}
}
return
low
;
}
}
Back
|
FazBrowse Home
|
New Git URL