中文亚洲精品无码_熟女乱子伦免费_人人超碰人人爱国产_亚洲熟妇女综合网

當(dāng)前位置: 首頁 > news >正文

鄭州制作各種證件聯(lián)系方式淘寶怎樣優(yōu)化關(guān)鍵詞

鄭州制作各種證件聯(lián)系方式,淘寶怎樣優(yōu)化關(guān)鍵詞,30張女性人像攝影作品欣賞,做詳情頁比較好的網(wǎng)站本文屬于「征服LeetCode」系列文章之一,這一系列正式開始于2021/08/12。由于LeetCode上部分題目有鎖,本系列將至少持續(xù)到刷完所有無鎖題之日為止;由于LeetCode還在不斷地創(chuàng)建新題,本系列的終止日期可能是永遠(yuǎn)。在這一系列刷題文章…

本文屬于「征服LeetCode」系列文章之一,這一系列正式開始于2021/08/12。由于LeetCode上部分題目有鎖,本系列將至少持續(xù)到刷完所有無鎖題之日為止;由于LeetCode還在不斷地創(chuàng)建新題,本系列的終止日期可能是永遠(yuǎn)。在這一系列刷題文章中,我不僅會(huì)講解多種解題思路及其優(yōu)化,還會(huì)用多種編程語言實(shí)現(xiàn)題解,涉及到通用解法時(shí)更將歸納總結(jié)出相應(yīng)的算法模板。

為了方便在PC上運(yùn)行調(diào)試、分享代碼文件,我還建立了相關(guān)的倉庫。在這一倉庫中,你不僅可以看到LeetCode原題鏈接、題解代碼、題解文章鏈接、同類題目歸納、通用解法總結(jié)等,還可以看到原題出現(xiàn)頻率和相關(guān)企業(yè)等重要信息。如果有其他優(yōu)選題解,還可以一同分享給他人。

由于本系列文章的內(nèi)容隨時(shí)可能發(fā)生更新變動(dòng),歡迎關(guān)注和收藏征服LeetCode系列文章目錄一文以作備忘。

有一個(gè)需要密碼才能打開的保險(xiǎn)箱。密碼是?n?位數(shù), 密碼的每一位都是范圍?[0, k - 1]?中的一個(gè)數(shù)字。

保險(xiǎn)箱有一種特殊的密碼校驗(yàn)方法,你可以隨意輸入密碼序列,保險(xiǎn)箱會(huì)自動(dòng)記住?最后?n?位輸入?,如果匹配,則能夠打開保險(xiǎn)箱。

  • 例如,正確的密碼是?"345"?,并且你輸入的是?"012345"?:
    • 輸入?0?之后,最后?3?位輸入是?"0"?,不正確。
    • 輸入?1?之后,最后?3?位輸入是?"01"?,不正確。
    • 輸入?2?之后,最后?3?位輸入是?"012"?,不正確。
    • 輸入?3?之后,最后?3?位輸入是?"123"?,不正確。
    • 輸入?4?之后,最后?3?位輸入是?"234"?,不正確。
    • 輸入?5?之后,最后?3?位輸入是?"345"?,正確,打開保險(xiǎn)箱。

在只知道密碼位數(shù)?n?和范圍邊界?k?的前提下,請你找出并返回確保在輸入的?某個(gè)時(shí)刻?能夠打開保險(xiǎn)箱的任一?最短?密碼序列 。

示例 1:

輸入:n = 1, k = 2
輸出:"10"
解釋:密碼只有 1 位,所以輸入每一位就可以。"01" 也能夠確保打開保險(xiǎn)箱。

示例 2:

輸入:n = 2, k = 2
輸出:"01100"
解釋:對于每種可能的密碼:
- "00" 從第 4 位開始輸入。
- "01" 從第 1 位開始輸入。
- "10" 從第 3 位開始輸入。
- "11" 從第 2 位開始輸入。
因此 "01100" 可以確保打開保險(xiǎn)箱。"01100"、"10011""11001" 也可以確保打開保險(xiǎn)箱。

提示:

  • 1 <= n <= 4
  • 1 <= k <= 10
  • 1 <= k^n <= 4096

保險(xiǎn)箱的密碼是一個(gè)長度為? n n n?的數(shù)字字符串,密碼中每位數(shù)字的取值范圍是從? 0 0 0?到? k ? 1 k-1 k?1 。現(xiàn)在這? n n n?位密碼未知,題目要求我們生成一個(gè)可以暴力破解這? n n n?位密碼的字符串序列? s e q seq seq ,要想用? s e q seq seq?破解密碼,那么? s e q seq seq?中必須包含? n n n?位密碼的所有組合,最簡單的是將? n n n 位密碼的? k n k^n kn?個(gè)組合拼在一起構(gòu)成? s e q seq seq ,但這樣的? s e q seq seq?太長了,題目要我們生成一個(gè)包含? n n n?位密碼所有組合情況的一個(gè)最短序列。

舉個(gè)例子, n = 2 , k = 2 n = 2, k = 2 n=2,k=2 ,密碼長度為? 2 2 2 ,每位數(shù)字由 0 0 0?和? 1 1 1?組成,那么長度為? 2 2 2?的密碼就有? k n = 2 2 = 4 k^n = 2^2 = 4 kn=22=4?種組合,即? 00 , 01 , 10 , 11 00, 01, 10, 11 00,01,10,11 ,要想破解密碼,最簡做法是,將這四種密碼組合拼在一起組成破解序列? s e q = 00011011 seq = 00011011 seq=00011011 ,這樣得到的序列長度為? 8 8 8 ,但它不是包含所有密碼組合的最短序列。也就是說這種簡單拼接在一起的方法,得到的破解序列是冗余的,會(huì)增加破解時(shí)間。

而密碼破解的方法其實(shí)就是樸素的字符串匹配,比如上面的? s e q = 00011011 seq = 00011011 seq=00011011 ,依次匹配的子串是? 00 , 00 , 01 , 11 , 10 , 01 , 11 00, 00, 01, 11, 10, 01, 11 00,00,01,11,10,01,11 ,一共做了? 7 7 7?次密碼匹配,其中? 00 , 01 , 11 00, 01, 11 00,01,11?分別匹配了兩次,也就是說多做了? 3 3 3?次冗余的密碼匹配。題目要求的?最短破解序列 就是不會(huì)產(chǎn)生冗余密碼匹配的序列,長度正好是? k n + ( n ? 1 ) k^n + (n - 1) kn+(n?1) ,最多只需要匹配? k n k^n kn?次 s e q = 00110 seq = 00110 seq=00110?是上面的其中一個(gè)破解序列,長度為? 5 5 5 ,依次匹配的子串分別是? 00 , 01 , 11 , 10 00, 01, 11, 10 00,01,11,10 ,匹配的正好是所有四種密碼組合。

一種建模方式是:對于所有? m = k n m = k^n m=kn?個(gè)密碼組合,我們把每個(gè)? n n n 位可能的密碼看成是圖中的一個(gè)頂點(diǎn),對于這? m m m?個(gè)頂點(diǎn)構(gòu)成的 完全圖?中,讓我們找到這樣一個(gè)回路? v 1 → v 2 → v 3 → . . . → v m → v 1 v_1 \to v_2\to v_3\to ... \to v_m \to v_1 v1?v2?v3?...vm?v1?除起始頂點(diǎn)外每個(gè)頂點(diǎn)訪問且僅訪問一次,其中? < u , v > <u, v> <u,v>?表示回路中一條由頂點(diǎn) u u u?指向? v v v,且頂點(diǎn)? u u u?長為? n ? 1 n-1 n?1?的后綴恰好是頂點(diǎn)? v v v?的前綴。最終我們要的 最短破解序列 ,一種頂點(diǎn)序列是? v 1 , v 2 , v 3 , . . . , v m v_1, v_2, v_3, ..., v_m v1?,v2?,v3?,...,vm? ,長度為? k n + ( n ? 1 ) k^n + (n - 1) kn+(n?1) ,這個(gè)?最短破解序列 不止一個(gè),因?yàn)?回路?中的任意一個(gè)頂點(diǎn)都可以做?起始頂點(diǎn)。這就是?哈密頓回路問題 。

不過查看Wiki,發(fā)現(xiàn)本題求的答案有專門的術(shù)語 De Bruijn sequence B ( k , n ) B(k,n) B(k,n) k k k 進(jìn)制元素構(gòu)成的循環(huán)序列,所有長度為 n n n k k k 進(jìn)制元素序列都是 B ( k , n ) B(k, n) B(k,n) 的子數(shù)組(以環(huán)狀形式),在 B ( k , n ) B(k,n) B(k,n) 中出現(xiàn)且僅出現(xiàn)一次。

描述該循環(huán)序列的圖是 De Bruijn 圖(一張歐拉圖)。使用( n ? 1 = 4 ? 1 = 3 n - 1 = 4 - 1=3 n?1=4?1=33-D De Bruijn 圖可以循環(huán)構(gòu)造長度為 2 4 = 16 2^4 = 16 24=16B(2,4) De Bruijn 序列。如下的3維 De Bruijn 圖中的每條邊對應(yīng)于一個(gè)四位數(shù)字的序列:三個(gè)數(shù)字分別標(biāo)記該邊要離開的頂點(diǎn),其后是一個(gè)數(shù)字標(biāo)記該邊。如果一個(gè)人從 000 000 000 穿過標(biāo)記為 1 1 1 的邊,則一個(gè)人到達(dá) 001 001 001 ,從而表明 De Bruijn 序列中存在子序列 0001 0001 0001 。精確遍歷每條邊一次,就是使用 16 16 16 個(gè)四位數(shù)序列中的每一個(gè)恰好一次。下圖,在 B(2,3) 中每個(gè)頂點(diǎn)被訪問一次,而在 B(2,4) 中每條邊(包括自環(huán))都被遍歷一次。


解法 Hierholzer \text{Hierholzer} Hierholzer 算法

Hierholzer \text{Hierholzer} Hierholzer 算法可以在一個(gè)歐拉圖中找出歐拉回路。具體地,我們將所有的 n ? 1 n-1 n?1 位數(shù)作為節(jié)點(diǎn),共有 k n ? 1 k^{n-1} kn?1 個(gè)節(jié)點(diǎn),每個(gè)節(jié)點(diǎn)有 k k k 條入邊和出邊。如果當(dāng)前節(jié)點(diǎn)對應(yīng)的數(shù)為 a 1 a 2 ? a n ? 1 a_1 a_2 \cdots a_{n-1} a1?a2??an?1? ,那么它的第 x x x 條出邊就連向數(shù) a 2 ? a n ? 1 x a_2 \cdots a_{n-1} x a2??an?1?x 對應(yīng)的節(jié)點(diǎn)。這樣從一個(gè)節(jié)點(diǎn)順著第 x x x 條邊走到另一個(gè)節(jié)點(diǎn),就相當(dāng)于輸入了數(shù)字 x x x 。

在某個(gè)節(jié)點(diǎn)對應(yīng)的數(shù)的末尾放上它某條出邊的編號,就形成了一個(gè) n n n 位數(shù),并且每個(gè)節(jié)點(diǎn)都能用這樣的方式形成 k k k 個(gè) n n n 位數(shù)

例如 k = 4 , n = 3 k=4,n=3 k=4,n=3 時(shí),節(jié)點(diǎn)分別為 00 , 01 , 02 , ? , 32 , 33 00,01,02,??,32,33 00,01,02,??,32,33 ,每個(gè)節(jié)點(diǎn)的出邊的編號分別為 0 , 1 , 2 , 3 0,1,2,3 0,1,2,3 ,那么 00 00 00 和它的出邊形成了 000 , 001 , 002 , 003 000,001,002,003 000,001,002,003 4 4 4 個(gè) 3 3 3 位數(shù), 32 32 32 和它的出邊形成了 320 , 321 , 322 , 323 320,321,322,323 320,321,322,323 4 4 4 個(gè) 3 3 3 位數(shù)。這樣共計(jì)有 k n ? 1 × k = k n k^{n-1} \times k = k^n kn?1×k=kn 個(gè) n n n 位數(shù),恰好就是所有可能的密碼

由于這個(gè)圖的每個(gè)節(jié)點(diǎn)都有 k k k 條入邊和出邊(有向連通圖節(jié)點(diǎn)度數(shù)都為 0 0 0 ),因此它一定存在一個(gè)歐拉回路,即可以從任意一個(gè)節(jié)點(diǎn)開始,一次性不重復(fù)地走完所有的邊且回到該節(jié)點(diǎn)。因此,我們可以用 Hierholzer \text{Hierholzer} Hierholzer 算法找出這條歐拉回路:

  • 設(shè)起始節(jié)點(diǎn)對應(yīng)的數(shù)為 u u u ,歐拉回路中每條邊的編號為 x 1 , x 2 , x 3 , ? x_1, x_2, x_3, \cdots x1?,x2?,x3?,? ,那么最終的字符串即為 u x 1 x 2 x 3 ? u u~ x_1 ~ x_2 ~ x_3 \cdots\ u u?x1??x2??x3???u

H i e r h o l z e r Hierholzer Hierholzer 算法如下:

  1. 我們從節(jié)點(diǎn) u u u 開始,任意地經(jīng)過還未經(jīng)過的邊,直到我們「無路可走」。此時(shí)我們一定回到了節(jié)點(diǎn) u u u ,這是因?yàn)樗泄?jié)點(diǎn)的入度和出度都相等。
  2. 回到節(jié)點(diǎn) u u u 之后,我們得到了一條從 u u u 開始到 u u u 結(jié)束的回路,這條回路上仍然有些節(jié)點(diǎn)有未經(jīng)過的出邊。從某個(gè)這樣的節(jié)點(diǎn) v v v 開始,繼續(xù)得到一條從 v v v 開始到 v v v 結(jié)束的回路,再嵌入之前的回路中,即 u → ? → v → ? → u u \to \cdots \to v \to \cdots \to u u?v?u
    變?yōu)? u → ? → v → ? → v → ? → u u\to \cdots \to v \to \cdots \to v \to \cdots \to u u?v?v?u
  3. 以此類推,直到?jīng)]有節(jié)點(diǎn)有未經(jīng)過的出邊,此時(shí)我們就找到了一條歐拉回路。

實(shí)際的代碼編寫具有一定的技巧性。

class Solution {
private:int highest, k;string ans;unordered_set<int> rec;void dfs(int node) {for (int x = 0; x < k; ++x) {int nei = node * 10 + x;if (!rec.count(nei)) { // 改為插入邊rec.insert(nei);dfs(nei % highest);ans += (x + '0');}}}
public:string crackSafe(int n, int k) {this->highest = pow(10, n - 1);this->k = k;dfs(0); // 從n-1個(gè)0出發(fā)ans += string(n - 1, '0'); // 返回的路徑順序應(yīng)該是n-1個(gè)0+翻轉(zhuǎn)的ans// 由于是歐拉回路,所以不用翻轉(zhuǎn),即可直接返回return ans;}
};

但上述寫法比較抽象。我們可以這么寫:從一個(gè) n ? 1 n-1 n?1 長度的全 0 0 0 串出發(fā)枚舉 k k k 條邊,每經(jīng)過一條邊就將其加入到哈希表中,防止重復(fù)經(jīng)過同一條邊。

class Solution {
private:string ans;unordered_set<string> edges;void dfs(string &cur, int k) {for (int i = 0; i < k; ++i) {string edge = cur + to_string(i);if (!edges.count(edge)) {edges.insert(edge);string next = edge.substr(1);dfs(next, k);ans += to_string(i);}}}
public:string crackSafe(int n, int k) {string start = string(n - 1, '0');dfs(start, k);ans += start;return ans;}
};

復(fù)雜度分析:

  • 時(shí)間復(fù)雜度: O ( n × k n ) O(n \times k^n) O(n×kn) 。
  • 空間復(fù)雜度: O ( n × k n ) O(n \times k^n) O(n×kn) 。
http://www.risenshineclean.com/news/22374.html

相關(guān)文章:

  • 去國外怎么導(dǎo)航地圖搜索引擎關(guān)鍵詞怎么優(yōu)化
  • 網(wǎng)站建設(shè) 無錫登錄注冊入口
  • 網(wǎng)站專題頁ps教程關(guān)鍵詞點(diǎn)擊排名系統(tǒng)
  • wordpress 注冊 插件信息流優(yōu)化師是干什么的
  • flash做的網(wǎng)站優(yōu)化網(wǎng)站推廣
  • 網(wǎng)站ftp用戶名和密碼做推廣哪個(gè)平臺(tái)好
  • 廣州建筑股份有限公司官網(wǎng)seo課程培訓(xùn)學(xué)校
  • 湛江有沒有做網(wǎng)站的關(guān)鍵詞seo培訓(xùn)
  • 純css網(wǎng)站騰訊體育nba
  • 電子商務(wù)網(wǎng)站建設(shè)招標(biāo)書網(wǎng)絡(luò)營銷常見的工具
  • 學(xué)做網(wǎng)站初入門教程太原seo代理商
  • 中交路橋建設(shè)網(wǎng)站百度seo工作室
  • 裝飾畫嘉興seo外包公司費(fèi)用
  • 吉林網(wǎng)站備案英文seo實(shí)戰(zhàn)派
  • 修改網(wǎng)站圖標(biāo)seo有名氣的優(yōu)化公司
  • 河南省建設(shè)教育協(xié)會(huì)網(wǎng)站口碑營銷的方法
  • 長安網(wǎng)站建設(shè)費(fèi)用查詢網(wǎng)站流量
  • 重慶梁平網(wǎng)站建設(shè)哪家便宜優(yōu)化網(wǎng)站標(biāo)題是什么意思
  • 做qq游戲的視頻秀網(wǎng)站楓樹seo
  • 網(wǎng)站登錄注冊頁面模板下載百度搜索引擎收錄
  • 小型網(wǎng)站開發(fā)用什么語言營銷案例網(wǎng)站
  • 企業(yè)門戶網(wǎng)站建設(shè)渠道服裝市場調(diào)研報(bào)告范文
  • 鄭州網(wǎng)站建設(shè)公司價(jià)格經(jīng)濟(jì)新聞最新消息財(cái)經(jīng)
  • 邢臺(tái)做網(wǎng)站口碑好怎么弄推廣廣告
  • 百度收錄網(wǎng)站要多網(wǎng)站策劃書模板
  • 東莞企業(yè)黃頁百度關(guān)鍵詞優(yōu)化送網(wǎng)站
  • 編程線下培訓(xùn)機(jī)構(gòu)廣安seo外包
  • 泗洪網(wǎng)站建設(shè)蘭蔻搜索引擎營銷案例
  • 做網(wǎng)站要做哪些站長工具高清無嗎
  • 網(wǎng)站優(yōu)化標(biāo)題怎么做自媒體平臺(tái)注冊入口官網(wǎng)