推 PogChampLUL: 大師 12/08 02:21
→ JIWP: 我只寫出第一題,剩下都比玩才寫的:)_ 12/08 02:22
3375. Minimum Operations to Make Array Values Equal to K
直接硬幹
記錄所有出現過的數字
如果有比k小的數字就回傳-1
不然就去數比k大的數字有幾組
那就是答案
func minOperations(nums []int, k int) int {
rec := [101]int{}
for _, val := range nums {
rec[val]++
}
ans := 0
for i := 0; i < k; i++ {
if rec[i] > 0 {
return -1
}
}
for i := 100; i > k; i-- {
if rec[i] > 0 {
ans++
}
}
return ans
}
3376. Minimum Time to Break Locks I
比賽完後才發現直接暴力法就好
幹你老師
golang code :
var ans int
func findMinimumTime(strength []int, k int) int {
if len(strength) == 1 {
return strength[0]
}
slices.Sort(strength)
ans = 10000000000
x := 1 + k
time := strength[0]
strength = strength[1:]
backtrack(strength, x, k, time)
return ans
}
func backtrack(arr []int, x, k, time int) {
if len(arr) == 0 {
ans = min(ans, time)
}
for key, val := range arr {
tmp := make([]int, len(arr))
copy(tmp, arr)
tmp = append(tmp[:key], tmp[key+1:]...)
backtrack(tmp, x+k, k, time+(val+x-1)/x)
}
}
3377. Digit Operations to Make Two Integers Equal
用graph的觀點去看
每條邊的權重就是下一個可以到達的數字
就變成簡單的最短路徑
golang code :
type minheap [][2]int
func (this minheap) Len() int { return len(this) }
func (this minheap) Swap(i, j int) { this[i], this[j] = this[j], this[i]
}
func (this minheap) Less(i, j int) bool { return this[i][1] < this[j][1] }
func (this *minheap) Push(x interface{}) {
*this = append(*this, x.([2]int))
}
func (this *minheap) Pop() interface{} {
n := len(*this)
res := (*this)[n-1]
*this = (*this)[:n-1]
return res
}
func isPrime(num int) bool {
if num <= 1 {
return false
}
for i := 2; i <= int(math.Sqrt(float64(num))); i++ {
if num%i == 0 {
return false
}
}
return true
}
func minOperations(n int, m int) int {
if isPrime(n){
return -1
}
rec := make(map[int]int)
rec[n] = n
visit := make(map[int]bool)
h := minheap{}
heap.Push(&h, [2]int{n, n})
for {
if h.Len() == 0 {
break
}
next := heap.Pop(&h).([2]int)
if next[0] == m {
return next[1]
}
visit[next[0]] = true
str := strconv.Itoa(next[0])
for i := 0; i < len(str); i++ {
digit := int(str[i] - '0')
if digit < 9 {
digit += 1
nextstr := []byte(str)
nextstr[i] = byte(digit + '0')
nextVal, _ := strconv.Atoi(string(nextstr))
if len(str) == len(strconv.Itoa(nextVal)) && !isPrime(nextVal) && !visit[
nextVal] {
visit[nextVal] = true
heap.Push(&h, [2]int{nextVal, nextVal + next[1]})
}
}
digit = int(str[i] - '0')
if digit > 0 {
digit -= 1
nextstr := []byte(str)
nextstr[i] = byte(digit + '0')
nextVal, _ := strconv.Atoi(string(nextstr))
if len(str) == len(strconv.Itoa(nextVal)) && !isPrime(nextVal) && !visit[
nextVal] {
visit[nextVal] = true
heap.Push(&h, [2]int{nextVal, nextVal + next[1]})
}
}
}
}
return -1
}
3378. Count Connected Components in LCM Graph
我覺得比那2題mid還簡單
就併查表下去就好
然後不要真的去求每組數字LCM，不然會報TEL
直接把每個數字小於threshold的倍數加到並查表就好
func countComponents(nums []int, threshold int) int {
slices.Sort(nums)
rec := make(map[int]int)
n := len(nums)
for _, val := range nums {
rec[val] = val
}
for i := 0; i < n && nums[i] < threshold; i++ {
for j := nums[i]; j <= threshold; j += nums[i] {
if _, ok := rec[j]; !ok {
rec[j] = j
}
parent_i := find(nums[i], rec)
parent_j := find(j, rec)
if parent_i > parent_j {
rec[nums[i]] = parent_j
rec[parent_i] = parent_j
} else {
rec[j] = parent_i
rec[parent_j] = parent_i
}
}
}
for key, val := range rec {
rec[key] = find(val, rec)
}
ans := 0
chk := make(map[int]struct{})
for _, val := range rec {
if _, ok := chk[val]; !ok {
ans++
chk[val] = struct{}{}
}
}
return ans
}
func find(x int, arr map[int]int) int {
if arr[x] == x {
return x
}
arr[x] = find(arr[x], arr)
return arr[x]
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.83.49.67 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1733595546.A.59B.html