算法笔试-常用数据结构
Updated Time
|
2024-12-03 |
Category
|
|
Tags
|
关于语言：一刷用 Golang，二刷用 Rust
题单
枚举右，维护左：对于双变量问题，例如两数之和 \(a_i + a_j = t\)，可以枚举右边的 \(a_j\)，转换成单变量问题，也就是在 \(a_j\) 左边查找是否有 \(a_i = t - a_j\)，可以用哈希表维护。
| 题目 | 来源 | 难度 | 分数 |
|---|---|---|---|
| 1. 两数之和 | 简单 | ||
| 1512. 好数对的数目 | 第 197 场周赛 Q1 | 简单 | 1161 |
| 219. 存在重复元素 II | 简单 | ||
| 121. 买卖股票的最佳时机 | 简单 | ||
| 2815. 数组中的最大数对和 | 第 358 场周赛 Q1 | 简单 | 1295 |
| 2342. 数位和相等数对的最大和 | 第 302 场周赛 Q2 | 中等 | 1309 |
| 1679. K 和数对的最大数目 | 第 218 场周赛 Q2 | 中等 | 1346 |
| 2260. 必须拿起的最小连续卡牌数 | 第 291 场周赛 Q2 | 中等 | 1365 |
题解
1. 两数之和
func twoSum(nums []int, target int) []int {
for r, v := range nums {
for l := 0; l < r; l++ {
if nums[l] + v == target {
return []int{l, r}
}
}
}
return nil
}
1512. 好数对的数目
func numIdenticalPairs(nums []int) (ans int) {
for r, v := range nums {
for l := 0; l < r; l++ {
if nums[l] == v {
ans++
}
}
}
return
}
219. 存在重复元素 II
func containsNearbyDuplicate(nums []int, k int) bool {
vis := make(map[int]int)
for r, v := range nums {
if l, ok := vis[v]; ok && r - l <= k {
return true
}
vis[v] = r
}
return false
}
121. 买卖股票的最佳时机
func maxProfit(prices []int) (ans int) {
mn := math.MaxInt
for _, v := range prices {
ans = max(ans, v - mn)
mn = min(mn, v)
}
return
}
2815. 数组中的最大数对和
func maxSum(nums []int) (ans int) {
vis := make([]int, 10)
ans = -1
for _, v := range nums {
mx := 0
for i := v; i > 0; i /= 10 {
mx = max(mx, i % 10)
}
if a := vis[mx]; a != 0 {
ans = max(ans, a + v)
}
vis[mx] = max(vis[mx], v)
}
return
}
2342. 数位和相等数对的最大和
func maximumSum(nums []int) (ans int) {
m := make(map[int]int)
ans = -1
for _, v := range nums {
sum := 0
for i := v; i > 0; i /= 10 {
sum += i % 10
}
if a, ok := m[sum]; ok {
ans = max(ans, a + v)
}
m[sum] = max(m[sum], v)
}
return
}
1679. K 和数对的最大数目
func maxOperations(nums []int, k int) (ans int) {
cnt := make(map[int]int)
for _, v := range nums {
if cnt[k-v] != 0 {
cnt[k-v]--
ans++
} else {
cnt[v]++
}
}
return
}
2260. 必须拿起的最小连续卡牌数
func minimumCardPickup(cards []int) int {
ans := math.MaxInt
m := make(map[int]int)
for r, v := range cards {
if a, ok := m[v]; ok {
ans = min(ans, r - a + 1)
}
m[v] = r
}
if ans == math.MaxInt {
return -1
}
return ans
}