Skip to content

Commit 82b544c

Browse files
halfrosthalfrost
committed
Add solution 1818
1 parent 443b7ce commit 82b544c

File tree

6 files changed

+322
-2
lines changed

6 files changed

+322
-2
lines changed

‎leetcode/1818.Minimum-Absolute-Sum-Difference/1818. Minimum Absolute Sum Difference.go

Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,38 @@
1+
package leetcode
2+
3+
func minAbsoluteSumDiff(nums1 []int, nums2 []int) int {
4+
diff := 0
5+
maxDiff := 0
6+
for i, n2 := range nums2 {
7+
d := abs(nums1[i] - n2)
8+
diff += d
9+
if maxDiff < d {
10+
t := 100001
11+
for _, n1 := range nums1 {
12+
maxDiff = max(maxDiff, d-min(t, abs(n1-n2)))
13+
}
14+
}
15+
}
16+
return (diff - maxDiff) % (1e9 + 7)
17+
}
18+
19+
func max(a, b int) int {
20+
if a > b {
21+
return a
22+
}
23+
return b
24+
}
25+
26+
func abs(a int) int {
27+
if a > 0 {
28+
return a
29+
}
30+
return -a
31+
}
32+
33+
func min(a, b int) int {
34+
if a > b {
35+
return b
36+
}
37+
return a
38+
}

‎leetcode/1818.Minimum-Absolute-Sum-Difference/1818. Minimum Absolute Sum Difference_test.go

Lines changed: 53 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,53 @@
1+
package leetcode
2+
3+
import (
4+
"fmt"
5+
"testing"
6+
)
7+
8+
type question1818 struct {
9+
para1818
10+
ans1818
11+
}
12+
13+
// para 是参数
14+
// one 代表第一个参数
15+
type para1818 struct {
16+
nums1 []int
17+
nums2 []int
18+
}
19+
20+
// ans 是答案
21+
// one 代表第一个答案
22+
type ans1818 struct {
23+
one int
24+
}
25+
26+
func Test_Problem1818(t *testing.T) {
27+
28+
qs := []question1818{
29+
30+
{
31+
para1818{[]int{1, 7, 5}, []int{2, 3, 5}},
32+
ans1818{3},
33+
},
34+
35+
{
36+
para1818{[]int{2, 4, 6, 8, 10}, []int{2, 4, 6, 8, 10}},
37+
ans1818{0},
38+
},
39+
40+
{
41+
para1818{[]int{1, 10, 4, 4, 2, 7}, []int{9, 3, 5, 1, 7, 4}},
42+
ans1818{20},
43+
},
44+
}
45+
46+
fmt.Printf("------------------------Leetcode Problem 1818------------------------\n")
47+
48+
for _, q := range qs {
49+
_, p := q.ans1818, q.para1818
50+
fmt.Printf("【input】:%v 【output】:%v\n", p, minAbsoluteSumDiff(p.nums1, p.nums2))
51+
}
52+
fmt.Printf("\n\n\n")
53+
}

‎leetcode/1818.Minimum-Absolute-Sum-Difference/README.md

Lines changed: 117 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,117 @@
1+
# [1818. Minimum Absolute Sum Difference](https://leetcode.com/problems/minimum-absolute-sum-difference/)
2+
3+
## 题目
4+
5+
You are given two positive integer arrays `nums1` and `nums2`, both of length `n`.
6+
7+
The **absolute sum difference** of arrays `nums1` and `nums2` is defined as the **sum** of `|nums1[i] - nums2[i]|` for each `0 <= i < n` (**0-indexed**).
8+
9+
You can replace **at most one** element of `nums1` with **any** other element in `nums1` to **minimize** the absolute sum difference.
10+
11+
Return the *minimum absolute sum difference **after** replacing at most one ****element in the array `nums1`.* Since the answer may be large, return it **modulo** `109 + 7`.
12+
13+
`|x|` is defined as:
14+
15+
- `x` if `x >= 0`, or
16+
- `x` if `x < 0`.
17+
18+
**Example 1:**
19+
20+
```
21+
Input: nums1 = [1,7,5], nums2 = [2,3,5]
22+
Output: 3
23+
Explanation:There are two possible optimal solutions:
24+
- Replace the second element with the first: [1,7,5] => [1,1,5], or
25+
- Replace the second element with the third: [1,7,5] => [1,5,5].
26+
Both will yield an absolute sum difference of|1-2| + (|1-3| or |5-3|) + |5-5| =3.
27+
28+
```
29+
30+
**Example 2:**
31+
32+
```
33+
Input: nums1 = [2,4,6,8,10], nums2 = [2,4,6,8,10]
34+
Output: 0
35+
Explanation:nums1 is equal to nums2 so no replacement is needed. This will result in an
36+
absolute sum difference of 0.
37+
38+
```
39+
40+
**Example 3:**
41+
42+
```
43+
Input: nums1 = [1,10,4,4,2,7], nums2 = [9,3,5,1,7,4]
44+
Output: 20
45+
Explanation:Replace the first element with the second: [1,10,4,4,2,7] => [10,10,4,4,2,7].
46+
This yields an absolute sum difference of|10-9| + |10-3| + |4-5| + |4-1| + |2-7| + |7-4| = 20
47+
```
48+
49+
**Constraints:**
50+
51+
- `n == nums1.length`
52+
- `n == nums2.length`
53+
- `1 <= n <= 10^5`
54+
- `1 <= nums1[i], nums2[i] <= 10^5`
55+
56+
## 题目大意
57+
58+
给你两个正整数数组 nums1 和 nums2 ，数组的长度都是 n 。数组 nums1 和 nums2 的 绝对差值和 定义为所有 |nums1[i] - nums2[i]|（0 <= i < n）的 总和（下标从 0 开始）。你可以选用 nums1 中的 任意一个 元素来替换 nums1 中的 至多 一个元素，以 最小化 绝对差值和。在替换数组 nums1 中最多一个元素 之后 ，返回最小绝对差值和。因为答案可能很大，所以需要对 10^9 + 7 取余 后返回。
59+
60+
## 解题思路
61+
62+
- 如果不改变任何元素，绝对差值和为
63+
64+
$$\sum \left | nums1[i] - nums2[i] \right |$$
65+
66+
- 如果改变一个元素后，那么绝对差值和为
67+
68+
$$\begin{aligned}&\sum \left | nums1[i] - nums2[i] \right | - \left ( \left | nums1[i] - nums2[i] \right | - \left | nums1[j] - nums2[i] \right |\right )\\= &\sum \left | nums1[i] - nums2[i] \right | - \Delta \end{aligned}$$
69+
70+
题目要求返回最小绝对差值和，即求
71+
72+
$$\Delta $$
73+
74+
的最大值。暴力枚举 nums1 和 nums2 中两两差值，找到 maxdiff。
75+
76+
## 代码
77+
78+
```go
79+
package leetcode
80+
81+
func minAbsoluteSumDiff(nums1 []int, nums2 []int) int {
82+
diff := 0
83+
maxDiff := 0
84+
for i, n2 := range nums2 {
85+
d := abs(nums1[i] - n2)
86+
diff += d
87+
if maxDiff < d {
88+
t := 100001
89+
for _, n1 := range nums1 {
90+
maxDiff = max(maxDiff, d-min(t, abs(n1-n2)))
91+
}
92+
}
93+
}
94+
return (diff - maxDiff) % (1e9 + 7)
95+
}
96+
97+
func max(a, b int) int {
98+
if a > b {
99+
return a
100+
}
101+
return b
102+
}
103+
104+
func abs(a int) int {
105+
if a > 0 {
106+
return a
107+
}
108+
return -a
109+
}
110+
111+
func min(a, b int) int {
112+
if a > b {
113+
return b
114+
}
115+
return a
116+
}
117+
```

‎website/content/ChapterFour/1700~1799/1758.Minimum-Changes-To-Make-Alternating-Binary-String.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -73,5 +73,5 @@ func min(a, b int) int {
7373
----------------------------------------------
7474
<div style="display: flex;justify-content: space-between;align-items: center;">
7575
<p><a href="https://books.halfrost.com/leetcode/ChapterFour/1700~1799/1752.Check-if-Array-Is-Sorted-and-Rotated/">⬅️上一页</a></p>
76-
<p><a href="https://books.halfrost.com/leetcode/ChapterFour/1800~1899/1846.Maximum-Element-After-Decreasing-and-Rearranging/">下一页➡️</a></p>
76+
<p><a href="https://books.halfrost.com/leetcode/ChapterFour/1800~1899/1818.Minimum-Absolute-Sum-Difference/">下一页➡️</a></p>
7777
</div>

‎website/content/ChapterFour/1800~1899/1818.Minimum-Absolute-Sum-Difference.md

Lines changed: 112 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,112 @@
1+
# [1818. Minimum Absolute Sum Difference](https://leetcode.com/problems/minimum-absolute-sum-difference/)
2+
3+
## 题目
4+
5+
You are given two positive integer arrays `nums1` and `nums2`, both of length `n`.
6+
7+
The **absolute sum difference** of arrays `nums1` and `nums2` is defined as the **sum** of `|nums1[i] - nums2[i]|` for each `0 <= i < n` (**0-indexed**).
8+
9+
You can replace **at most one** element of `nums1` with **any** other element in `nums1` to **minimize** the absolute sum difference.
10+
11+
Return the *minimum absolute sum difference **after** replacing at most one ****element in the array `nums1`.* Since the answer may be large, return it **modulo** `109 + 7`.
12+
13+
`|x|` is defined as:
14+
15+
- `x` if `x >= 0`, or
16+
- `x` if `x < 0`.
17+
18+
**Example 1:**
19+
20+
```
21+
Input: nums1 = [1,7,5], nums2 = [2,3,5]
22+
Output: 3
23+
Explanation:There are two possible optimal solutions:
24+
- Replace the second element with the first: [1,7,5] => [1,1,5], or
25+
- Replace the second element with the third: [1,7,5] => [1,5,5].
26+
Both will yield an absolute sum difference of|1-2| + (|1-3| or |5-3|) + |5-5| =3.
27+
28+
```
29+
30+
**Example 2:**
31+
32+
```
33+
Input: nums1 = [2,4,6,8,10], nums2 = [2,4,6,8,10]
34+
Output: 0
35+
Explanation:nums1 is equal to nums2 so no replacement is needed. This will result in an
36+
absolute sum difference of 0.
37+
38+
```
39+
40+
**Example 3:**
41+
42+
```
43+
Input: nums1 = [1,10,4,4,2,7], nums2 = [9,3,5,1,7,4]
44+
Output: 20
45+
Explanation:Replace the first element with the second: [1,10,4,4,2,7] => [10,10,4,4,2,7].
46+
This yields an absolute sum difference of|10-9| + |10-3| + |4-5| + |4-1| + |2-7| + |7-4| = 20
47+
```
48+
49+
**Constraints:**
50+
51+
- `n == nums1.length`
52+
- `n == nums2.length`
53+
- `1 <= n <= 10^5`
54+
- `1 <= nums1[i], nums2[i] <= 10^5`
55+
56+
## 题目大意
57+
58+
给你两个正整数数组 nums1 和 nums2 ，数组的长度都是 n 。数组 nums1 和 nums2 的 绝对差值和 定义为所有 |nums1[i] - nums2[i]|（0 <= i < n）的 总和（下标从 0 开始）。你可以选用 nums1 中的 任意一个 元素来替换 nums1 中的 至多 一个元素，以 最小化 绝对差值和。在替换数组 nums1 中最多一个元素 之后 ，返回最小绝对差值和。因为答案可能很大，所以需要对 10^9 + 7 取余 后返回。
59+
60+
## 解题思路
61+
62+
- 如果不改变任何元素，绝对差值和为 {{< katex >}} \sum \left | nums1[i] - nums2[i] \right | {{< /katex >}}。如果改变一个元素后，那么绝对差值和为 {{< katex >}} \begin{aligned}&\sum \left | nums1[i] - nums2[i] \right | - \left ( \left | nums1[i] - nums2[i] \right | - \left | nums1[j] - nums2[i] \right |\right )\\= &\sum \left | nums1[i] - nums2[i] \right | - \Delta \end{aligned} {{< /katex >}}。题目要求返回最小绝对差值和，即求 {{< katex >}}\Delta {{< /katex >}} 的最大值。暴力枚举 nums1 和 nums2 中两两差值，找到 maxdiff，即 {{< katex >}}\Delta {{< /katex >}} 的最大值，此题得到解。
63+
64+
## 代码
65+
66+
```go
67+
package leetcode
68+
69+
func minAbsoluteSumDiff(nums1 []int, nums2 []int) int {
70+
diff := 0
71+
maxDiff := 0
72+
for i, n2 := range nums2 {
73+
d := abs(nums1[i] - n2)
74+
diff += d
75+
if maxDiff < d {
76+
t := 100001
77+
for _, n1 := range nums1 {
78+
maxDiff = max(maxDiff, d-min(t, abs(n1-n2)))
79+
}
80+
}
81+
}
82+
return (diff - maxDiff) % (1e9 + 7)
83+
}
84+
85+
func max(a, b int) int {
86+
if a > b {
87+
return a
88+
}
89+
return b
90+
}
91+
92+
func abs(a int) int {
93+
if a > 0 {
94+
return a
95+
}
96+
return -a
97+
}
98+
99+
func min(a, b int) int {
100+
if a > b {
101+
return b
102+
}
103+
return a
104+
}
105+
```
106+
107+
108+
----------------------------------------------
109+
<div style="display: flex;justify-content: space-between;align-items: center;">
110+
<p><a href="https://books.halfrost.com/leetcode/ChapterFour/1700~1799/1758.Minimum-Changes-To-Make-Alternating-Binary-String/">⬅️上一页</a></p>
111+
<p><a href="https://books.halfrost.com/leetcode/ChapterFour/1800~1899/1846.Maximum-Element-After-Decreasing-and-Rearranging/">下一页➡️</a></p>
112+
</div>

‎website/content/ChapterFour/1800~1899/1846.Maximum-Element-After-Decreasing-and-Rearranging.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -104,5 +104,5 @@ func min(a, b int) int {
104104

105105

106106
----------------------------------------------
107-
<p><a href="https://books.halfrost.com/leetcode/ChapterFour/1700~1799/1758.Minimum-Changes-To-Make-Alternating-Binary-String/">⬅️上一页</a></p>
107+
<p><a href="https://books.halfrost.com/leetcode/ChapterFour/1800~1899/1818.Minimum-Absolute-Sum-Difference/">⬅️上一页</a></p>
108108

0 commit comments

Comments
 (0)