前言
算法這個活動很嚴(yán)，每天必須打卡抗悍，而且不限制語言驹饺，群內(nèi)已有PHP、Python缴渊、Java赏壹、Javascript等語言，歡迎大家參加衔沼，并堅持蝌借。能堅持的公眾號回復(fù)算法。本公眾號以JS為主指蚁，解題思路均以js來舉例骨望。
上周回顧：
1、兩個數(shù)組的交集 II
2欣舵、1比特與2比特字符
3擎鸠、二進(jìn)制求和
4、兩數(shù)之和
5缘圈、加一
爬樓梯
假設(shè)你正在爬樓梯劣光。需要 n 階你才能到達(dá)樓頂。
每次你可以爬 1 或 2 個臺階糟把。你有多少種不同的方法可以爬到樓頂呢绢涡？
注意：給定 n 是一個正整數(shù)
- 示例 1：
輸入： 2 輸出： 2 解釋： 有兩種方法可以爬到樓頂。 1. 1 階 + 1 階 2. 2 階 - 示例 2：
輸入： 3 輸出： 3 解釋： 有三種方法可以爬到樓頂 1. 1 階 + 1 階 + 1 階 2. 1 階 + 2 階 3. 2 階 + 1 階
題解：
-
斐波那契數(shù)列公式法
dp[n] = dp[n-1] + dp[n-2]
執(zhí)行用時：64ms遣疯；內(nèi)存消耗：34.2MB雄可；
var climbStairs = function(n) { const dp = []; dp[0] = 1; dp[1] = 1; for(let i = 2; i <= n; i++) { dp[i] = dp[i - 1] + dp[i - 2]; } return dp[n]; }; -
數(shù)學(xué)公式法
image
執(zhí)行用時：72ms；內(nèi)存消耗：33.7MB；var climbStairs = function(n) { const sqrt_5 = Math.sqrt(5); const fib_n = Math.pow((1 + sqrt_5) / 2, n + 1) -Math.pow((1 - sqrt_5) / 2,n + 1); return Math.round(fib_n / sqrt_5); };
只出現(xiàn)一次的數(shù)字
給定一個非空整數(shù)數(shù)組数苫，除了某個元素只出現(xiàn)一次以外聪舒，其余每個元素均出現(xiàn)兩次。找出那個只出現(xiàn)了一次的元素虐急。
說明：
你的算法應(yīng)該具有線性時間復(fù)雜度箱残。你可以不使用額外空間來實現(xiàn)嗎？
- 示例 1:
輸入: [2,2,1] 輸出: 1 - 示例 2:
輸入: [4,1,2,1,2] 輸出: 4
題解
-
對象計數(shù)法
用一個對象來存儲出現(xiàn)的次數(shù)止吁，然后取出次數(shù)為1的值被辑；
執(zhí)行用時：116ms；內(nèi)存消耗：37.5MB敬惦；var singleNumber = function(nums) { let obj={}; let result=null; nums.forEach(item=>{ if(!obj[item]){ obj[item]=1 }else{ obj[item]++ } }) Object.keys(obj).forEach(item=>{ if(obj[item]===1){ result=item-0 } }) return result }; -
有序互斥法
先排序盼理，然后利用相鄰不想等來找出答案；
執(zhí)行用時：156ms俄删；內(nèi)存消耗：36.9MB宏怔；var singleNumber = function(nums) { nums = nums.sort(); for (let i = 0; i < nums.length; i++) { if (nums[i] !== nums[i - 1] && nums[i] !== nums[i + 1]) return nums[i]; } }; -
XOR法（異或法）
第一次看到這種解法，也從側(cè)面體現(xiàn)了對js位運(yùn)算的不熟悉抗蠢，XOR位運(yùn)算举哟，如果你了解它的含義思劳，就不懷疑為什么可以解決此題了迅矛，XOR位運(yùn)算會先轉(zhuǎn)化為二進(jìn)制，如果兩位只有一位為 1 則設(shè)置每位為 1潜叛，最后轉(zhuǎn)化回來秽褒；
執(zhí)行用時：72ms；內(nèi)存消耗：35.8MB威兜；var singleNumber = function(nums) { let gg = function(total,num){ return total ^ num; } return nums.reduce(gg); } -
左右索引法
從左邊檢索和右邊檢索销斟，如果相等，就找到結(jié)果椒舵；
執(zhí)行用時：536ms蚂踊；內(nèi)存消耗：35.2MB；var singleNumber = function(nums) { for (let i = 0; i < nums.length; i++) { if (nums.lastIndexOf(nums[i]) === nums.indexOf(nums[i])) return nums[i]; } } -
循環(huán)減法
從拷貝一個數(shù)組笔宿，定義一個變量犁钟，在循環(huán)中，動態(tài)修改數(shù)組泼橘，如果拷貝數(shù)組中存在當(dāng)前值涝动，就相減，否則相加炬灭；（這是最笨的方法）
執(zhí)行用時：1228ms醋粟；內(nèi)存消耗：37.6MB；var singleNumber = function(nums) { let num=0; let list=[...nums] nums.forEach((item,i)=>{ list.splice(i,1,null); if(list.includes(item)){ num-=item }else{ num+=item } }) return num } -
字符串分割法（正則思想）
將數(shù)組轉(zhuǎn)換成字符串，然后遍歷使用每一項的值去分割字符串米愿，若分割后數(shù)組長度為2則該項只出現(xiàn)一次厦凤。
執(zhí)行用時：9460ms；內(nèi)存消耗：41.9MB吗货；var singleNumber = function(nums) { const numsStr = `/${nums.join('//')}/`; for (let i = 0; i < nums.length; i++) { if (numsStr.split(`/${nums[i]}/`).length === 2) return nums[i]; } }
報數(shù)
報數(shù)序列是一個整數(shù)序列泳唠，按照其中的整數(shù)的順序進(jìn)行報數(shù)，得到下一個數(shù)宙搬。其前五項如下：
1. 1
2. 11
3. 21
4. 1211
5. 111221
1 被讀作 "one 1" ("一個一") , 即 11笨腥。
11 被讀作 "two 1s" ("兩個一"）, 即 21。
21 被讀作 "one 2", "one 1"（"一個二" , "一個一") , 即 1211勇垛。
給定一個正整數(shù)n（1 ≤ n ≤ 30）脖母，輸出報數(shù)序列的第 n 項。
注意：整數(shù)順序?qū)⒈硎緸橐粋€字符串闲孤。
- 示例 1:
輸入: 1 輸出: "1" - 示例 2:
輸入: 4 輸出: "1211"
題解：
-
對象法
用一個對象來存儲報數(shù)字符串谆级，分兩種情況處理，當(dāng)key為1和當(dāng)key>1讼积；當(dāng)key>1的時候肥照，獲取到key-1的字符串，轉(zhuǎn)化為數(shù)組勤众，在利用對象來存儲此數(shù)組中數(shù)字出現(xiàn)的次數(shù)舆绎，但此時會遇到一個問題，像111221這樣前面的1和后面的1不同们颜，所以我們存儲時要區(qū)分開吕朵；這里用num做了區(qū)分，當(dāng)值不相同的時候num再賦值窥突。
ob中存的是每個字符串解讀的對象努溃，比如4的報數(shù)“1211”，5的報數(shù)是解讀1211的字符串阻问，所以ob中存的是
obj的每一個key值就是n梧税，value就是報數(shù)字符串；{ 0:{count:1,value:1}, 1:{count:1,value:2}, 2:{count:2,value:1} }//拼接之后就是111221
執(zhí)行用時：136ms称近；內(nèi)存消耗：36.9MB第队；var countAndSay = function(n) { let obj={} for(let i=1;i<=n;i++){ obj[i]=''; if(i==1){ obj[i]+=1+'' } if(i>1){ let num=null; let ob={}; let list=obj[i-1].split(''); let flag=false; list.forEach((item,index)=>{ if(index==0){ num=0; ob[index]={ value:item, count:1 } } if(index>0){ if(ob[num]&&ob[num].value===item){ ob[num].count&&ob[num].count++ }else{ num=index ob[index]={ value:item, count:1 } } } }) for(let k in ob){ obj[i]+=ob[k].count+''+ob[k].value } } } return obj[n] } -
正則法
先觀察規(guī)律，顯然每一階數(shù)中任意部分的元素一次最多連續(xù)不會超過3次煌茬，所以任一階數(shù)的組成元素最多只有1斥铺、2、3坛善。所以我直接使用正則/(1+)|(2+)|(3+)/g來匹配字符串即可晾蜘。
執(zhí)行用時：80ms邻眷；內(nèi)存消耗：34.8MB；var countAndSay = function(n) { let str = '1'; for (let i = 0; i < n - 1; i++) { str = str.match(/(1+)|(2+)|(3+)/g).reduce( (pre, cur) => pre + cur.length + cur[0], ''); } return str; }; -
遞歸法
先從1到n這個過程中剔交，通過數(shù)組來存儲當(dāng)前結(jié)果肆饶，所以我們的結(jié)構(gòu)可以是這樣fn(index,['...'],n),然后當(dāng)index==n的時候設(shè)立遞歸終止條件；
執(zhí)行用時：124ms岖常；內(nèi)存消耗：35.1MB驯镊；var countAndSay = function(n) { const createStr = function (index, str, n) { //終止條件：查詢到了第n個數(shù)了，立即返回竭鞍，否則index+1 if(index == n) return str.join('') ; index++ let newChar = [] let k = 1//保存該數(shù)存在次數(shù)：當(dāng)查詢到不等的時候板惑，在下方重置k for(let j = 0; j < str.length; j++) { let char = str[j] if(char == str[j+1] && j != str.length - 1) { //不等，且遍歷沒到底偎快，那就繼續(xù)尋找 k++ }else { newChar.push(k) newChar.push(str[j]) k=1 } } return createStr(index, newChar, n) } return createStr(1, ['1'], n) };
最后一個單詞的長度
給定一個僅包含大小寫字母和空格 ' ' 的字符串冯乘，返回其最后一個單詞的長度。
如果不存在最后一個單詞晒夹，請返回 0 裆馒。
說明：一個單詞是指由字母組成，但不包含任何空格的字符串丐怯。
- 示例:
輸入: "Hello World" 輸出: 5
題解：
-
字符串分割法
分割成數(shù)組喷好，然后取最后一個；
執(zhí)行用時：68ms读跷；內(nèi)存消耗：33.7MB梗搅；
當(dāng)然你也可以用正則；var lengthOfLastWord = function(s) { let list=s.trim().split(' ') return list[list.length-1].length }
執(zhí)行用時：76ms舔亭；內(nèi)存消耗：33.5MB些膨；var lengthOfLastWord = function(s) { s = s.replace(/(\s*$)/g, "") let arr = s.split(' ') return arr[arr.length -1].length }
各位相加
給定一個非負(fù)整數(shù) num蟀俊，反復(fù)將各個位上的數(shù)字相加钦铺，直到結(jié)果為一位數(shù)。
- 示例:
輸入: 38 輸出: 2 解釋: 各位相加的過程為：3 + 8 = 11, 1 + 1 = 2肢预。由于 2 是一位數(shù)矛洞，所以返回 2。
題解：
-
遞歸
分割成字符串?dāng)?shù)組烫映，然后遞歸沼本，當(dāng)小于10，返回結(jié)果锭沟，大于等于則遞歸抽兆；
執(zhí)行用時：104ms；內(nèi)存消耗：36MB族淮；ar addDigits = function(num) { let val=0; let getGe=(n)=>{ const list=(n+'').split(''); let res=0; list.forEach(item=>{ res+=item-0 }) if(res>=10){ getGe(res) } if(res<10){ val= res } } getGe(num) return val } -
條件法
有循環(huán)就有條件辫红，看見for就想到while凭涂；
執(zhí)行用時：100ms；內(nèi)存消耗：36.2MB贴妻；var addDigits = function(num) { let Digit=num; while(Digit>=10){ Digit=Digit+''; let list=[...Digit]; Digit=list.reduce((a,b)=>(a-0)+(b-0)) } return Digit } -
模除法
有如下關(guān)系：num = a * 10000 + b * 1000 + c * 100 + d * 10 + e
即：num = (a + b + c + d + e) + (a * 9999 + b * 999 + c * 99 + d * 9)這道題最后的目標(biāo)切油，就是不斷將各位相加，相加到最后名惩，當(dāng)結(jié)果小于10時返回澎胡。因為最后結(jié)果在1-9之間，得到9之后將不會再對各位進(jìn)行相加娩鹉，因此不會出現(xiàn)結(jié)果為0的情況攻谁。因為 (x + y) % z = (x % z + y % z) % z，又因為 x % z % z = x % z弯予，因此結(jié)果為 (num - 1) % 9 + 1巢株，只模除9一次，并將模除后的結(jié)果加一返回熙涤。
北風(fēng)其涼 --OSCHINA但是有1個關(guān)鍵的問題阁苞，如果num是9的倍數(shù)，那么就不適用上述邏輯祠挫。原本我是想得到n被打包成10個1份的份數(shù)+打不進(jìn)10個1份的散落個數(shù)的和那槽。通過與9取模，去獲得那個不能整除的1等舔，作為計算份數(shù)的方式骚灸，但是如果可以被9整除，我就無法得到那個1慌植，也得不到個位上的數(shù)甚牲。
可以這么做的原因：原本可以被完美分成9個為一份的n樣物品，我故意去掉一個蝶柿，那么就又可以回到上述邏輯中去得到我要的n被打包成10個一份的份數(shù)+打不進(jìn)10個一份的散落個數(shù)的和丈钙。而這個減去的1就相當(dāng)于從，在10個1份打包的時候散落的個數(shù)中借走的交汤，本來就不影響原來10個1份打包的份數(shù)雏赦，先拿走再放回來，都只影響散落的個數(shù)芙扎，所以沒有關(guān)系星岗。
liveforexperience --力扣（LeetCode）這是一種數(shù)學(xué)思維，也是算法中常見的思維方式戒洼。
執(zhí)行用時：100ms俏橘；內(nèi)存消耗：35.4MB；var addDigits = function(num) { return (num-1)%9+1 };
第二期結(jié)束圈浇，下期見寥掐。如果有一起學(xué)習(xí)的朋友例获，可以加微信群。
