Re: [閒聊] 每日LeetCode

看板Marginalman作者sustainer123 (caster )時間2年前 (2023/11/17 10:34)推噓2(2推 0噓 3→)

留言5則, 3人參與討論串519/719 (看更多)

※ 引述《ZooseWu (動物園公告)》之銘言： : 1980. Find Unique Binary String : 給你一個字串陣列 : 裡面全都是長度為n的二進制數字字串 : 陣列長度也為n : 回傳任何一個不在陣列中出現的二進制數字字串 : Input: nums = ["01","10"] : Output: "11" ("00"也可) : Input: nums = ["00","01"] : Output: "11" ("10"也可) : Input: nums = ["111","011","001"] : Output: "101" ("000", "010", "100", "110"也可) : Intuition: : 把Array改成Set之後找有沒有重複元素 : 沒有就交答案 : TS Code: : function findDifferentBinaryString (nums: string[]): string { : const set = new Set(nums) : for (let i = 0; i < Math.pow(2, nums.length); i++) { : const value = i.toString(2).padStart(nums.length, "0") : if (!set.has(value)) return value : } : } : 本來想說這樣就結束了 : 後來看別人解答之後 : 發現別人用一個超猛的解法：對角論證法 : 對角論證法原本是拿來證明實數沒有上限用的 : 證明方法wiki有寫有興趣的可以自己去找 : 而這個方法剛好也可以拿來解這一題 : 我們把陣列直的排起來 : "111" : "011" : "001" : 然後第n個字串就取第n個字元 : "111" : "011" : "001" : 取出來的字元是"111" : 接下來全部反轉 1變0 0變1 -> "000" : 反轉後的字元"000"有下列特性： : 第一個字元一定跟陣列第一個相異 : 第二個字元一定跟陣列第二個相異 : ... : 第n個字元一定跟陣列第n個相異 : 所以反轉後的字串一定會跟陣列中的每個元素都相異 : 就是答案 Python Code: class Solution: def findDifferentBinaryString(self, nums: List[str]) -> str: l = len(nums) s = set(nums) for i in range(2**l): a = str(bin(i).replace("0b","")).zfill(l) if a not in s: return a 暴力解我的問題是關於動物園提到的對角論證法 wiki第二個前提如下: 我們把區間中所有的數字排成數列（這些數字不需按序排列；事實上，有些可數集，例如有理數也不能按照數字的大小把它們全數排序，但單只是成數列就沒有問題的）。對於那些有兩種小數形式的數字，例如0.499 ... = 0.500 ...，我們選擇前者。為啥後來的x會不在此數列? 假如x不在此數列此數列不就沒有此區間所有數字? 無所有數字則與前提二相違背求數學大師解答 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.119.121.6 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1700188494.A.17E.html

推

wwndbk

11/17 10:37, 2年前 , 1^F

11/17 10:37, 1^F

→

sustainer123

11/17 10:41, 2年前 , 2^F

11/17 10:41, 2^F

→

sustainer123

11/17 10:45, 2年前 , 3^F

11/17 10:45, 3^F