Re: [閒聊] 每日LeetCode
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個相異
所以反轉後的字串一定會跟陣列中的每個元素都相異
就是答案
--
Zoosewu
Yoututbe顯示PTT推文
可以在各個網站追實況或Live時使用
預覽圖: https://i.imgur.com/ZhtXdAJ.png
完整介紹: https://github.com/zoosewu/PTTChatOnYoutube/tree/master/homepage
支援的網站: Youtube Twitch Holotools Niji-mado Holodex
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.32.229.33 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1700106677.A.9DB.html
※ 編輯: ZooseWu (114.32.229.33 臺灣), 11/16/2023 11:52:19
推
11/16 11:54,
2年前
, 1F
11/16 11:54, 1F
推
11/16 11:57,
2年前
, 2F
11/16 11:57, 2F
推
11/16 11:59,
2年前
, 3F
11/16 11:59, 3F
→
11/16 12:12,
2年前
, 4F
11/16 12:12, 4F
推
11/16 12:23,
2年前
, 5F
11/16 12:23, 5F
推
11/16 12:57,
2年前
, 6F
11/16 12:57, 6F
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 518 之 719 篇)：