Re: [閒聊] 每日leetcode

[JIWP (神楽めあ的錢包)]

2501. Longest Square Streak in an Array

給一個nums，nums的subsequence稱為square streak如果滿足以下條件

(1)長度大於2

(2)在排序後，每個元素都是前一個元素的平方

請回傳最長的square streak長度

思路:

兩個想法

(1)

用一個hash map紀錄nums所有元素

接著去看每個元素nums[i]的平方是否存在

存在就繼續找nums[i]^4是否存在，依此類推

最後找出最大的長度

(2)

這個太笨了

就不講

golang code :

func longestSquareStreak(nums []int) int {
        hash_table := make(map[int]struct{})
        for _, val := range nums {
                hash_table[val] = struct{}{}
        }
        ans := 0
        for _, val := range nums {
                tmp := 1
                for {
                        if _, ok := hash_table[val*val]; ok {
                                tmp++
                                val *= val
                        } else {
                                break
                        }
                }
                ans = max(tmp, ans)
        }
    if ans == 1{
        return -1
    }
        return ans
}

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.71.213.218 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1730118253.A.033.html
推 Furina: 大師
推 RinNoKareshi: 大師
推 dont: 大師
推 DJYOMIYAHINA: 大師
推 Phoenix9: 大師