jiangjlon

摘要： 一、什么是ES6 ES6（ECMAScript 6），簡(jiǎn)單來(lái)說(shuō)就是JavaScripe的標(biāo)準(zhǔn)。不在贅述ES5和ES6區(qū)別，可以使用Babel將ES6轉(zhuǎn)成ES5，提高可用性。 二、let和const命令 1、let和const命令聲明變量沒(méi)有變量提升，也就是說(shuō)這種代碼是不能正常執(zhí)行的。 <script 閱讀全文

摘要： 并查集是解決兩元素是否屬于同一集合，將一個(gè)集合合并另一集合的數(shù)據(jù)結(jié)構(gòu)。具體來(lái)說(shuō)，我們使用數(shù)字代替集合，比如集合1，集合2.使用數(shù)組f[i]維護(hù)元素i屬于的集合，比如f[2] = 4表示元素2屬于集合4。具體我們有以下實(shí)現(xiàn)功能的代碼 1 初始化表示集合的數(shù)組。 cin>>n>>m; for(int i 閱讀全文

摘要： SPFA算法是在bellman-ford算法基礎(chǔ)上優(yōu)化而來(lái)，所以我們先討論bellman-ford算法 bellman-ford算法的核心是‘松弛’。那么什么是松弛呢？以下圖為例： 假設(shè)數(shù)組d[i]表示源點(diǎn)s到達(dá)結(jié)點(diǎn)i的最短路徑長(zhǎng)度，那么松弛指的就是當(dāng)d[a] + w < d[b]，也就是說(shuō)，這時(shí)候 閱讀全文

摘要： 本文是https://www.acwing.com/problem/content/description/837/的總結(jié)，有興趣可以做做 字典樹的實(shí)現(xiàn)依賴于樹結(jié)構(gòu)，有兩種操作，1是插入字符串，2是查找字符串。使用idx維護(hù)最新的結(jié)點(diǎn)下標(biāo)。如下圖，假設(shè)我們維護(hù)一個(gè) 可以看到，我們維護(hù)了一個(gè)樹形結(jié)構(gòu)儲(chǔ) 閱讀全文

摘要： 首先，本文默認(rèn)讀者基本熟悉Dijkstra基本原理 DIjkstra是單源最短路的一種算法。使用數(shù)組d[i]來(lái)儲(chǔ)存結(jié)點(diǎn)i到源點(diǎn)s的最短路徑長(zhǎng)度，每次更新d[i]數(shù)組后，d[i]中最小的一定是一條最短路徑長(zhǎng)度。也就是說(shuō)每次更新后都能找到一條最短路徑，以下給出證明： 假設(shè)d[]數(shù)組中當(dāng)前最小值對(duì)應(yīng)的結(jié)點(diǎn) 閱讀全文

摘要： 假設(shè)現(xiàn)在有數(shù)組a[n]，和滑動(dòng)的窗口長(zhǎng)度為k <= n，要求長(zhǎng)度為k的滑動(dòng)窗口的最值，一般來(lái)說(shuō)，我們會(huì)遇到以下問(wèn)題： 在窗口向右滑動(dòng)時(shí)，由于不知道將要?jiǎng)h除的元素在窗口中的位置，于是只能暴力遍歷窗口來(lái)刪除舊元素。增加了時(shí)間復(fù)雜度到O(n^2logn) 以下是解決該問(wèn)題的一種方案： 使用一個(gè)額外的優(yōu)先隊(duì) 閱讀全文

摘要： 一，解決問(wèn)題 kmp算法解決的是字符串匹配的問(wèn)題，具體來(lái)說(shuō)假定我們要在主串s[ ] 中匹配模式串p[ ]，找到匹配到的位置loc； 二，具體實(shí)現(xiàn)和演變過(guò)程 最自然的想法是暴力寫法 （BF）枚舉主串字符s[ i ] ,和模式串p[ j ]。一個(gè)一個(gè)匹配，如果匹配失敗，i指針回退回起點(diǎn)，往前進(jìn)一位，再次 閱讀全文