成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

數(shù)據(jù)結(jié)構(gòu)與算法-LeetCode 格雷編碼(No.89)

Youngs / 3593人閱讀

摘要：例如，也是一個(gè)有效的格雷編碼序列。示例輸入輸出解釋我們定義格雷編碼序列必須以開(kāi)頭。給定編碼總位數(shù)為的格雷編碼序列，其長(zhǎng)度為。因此，當(dāng)時(shí)，其格雷編碼序列為。

LeetCode 89. 格雷編碼

格雷編碼是一個(gè)二進(jìn)制數(shù)字系統(tǒng)，在該系統(tǒng)中，兩個(gè)連續(xù)的數(shù)值僅有一個(gè)位數(shù)的差異。
給定一個(gè)代表編碼總位數(shù)的非負(fù)整數(shù) n，打印其格雷編碼序列。格雷編碼序列必須以 0 開(kāi)頭。第一個(gè)數(shù)與最后一位數(shù) 也只差以為一位數(shù) ‘首尾相連’ 所以又稱為循環(huán)碼或反射碼

示例 1:

輸入: 2
輸出: [0,1,3,2]
解釋:
00 - 0
01 - 1
11 - 3
10 - 2

對(duì)于給定的 n，其格雷編碼序列并不唯一。
例如，[0,2,3,1] 也是一個(gè)有效的格雷編碼序列。

00 - 0
10 - 2
11 - 3
01 - 1

示例 2:

輸入: 0
輸出: [0]
解釋: 我們定義格雷編碼序列必須以 0 開(kāi)頭。
     給定編碼總位數(shù)為 n 的格雷編碼序列，其長(zhǎng)度為 2n。當(dāng) n = 0 時(shí)，長(zhǎng)度為 20 = 1。
     因此，當(dāng) n = 0 時(shí)，其格雷編碼序列為 [0]。

這題的難度主要是將給定的n轉(zhuǎn)化為格雷編碼

第一步  將n轉(zhuǎn)變?yōu)楦窭拙幋a1=>["0","1"]

n = 1
0
1

n = 2
00
01
--
11
10

n = 3
000
001
011
010
---
110
111
101
100

分析上面的數(shù)字排列 我們可以注意到3點(diǎn)

以--為間隔上面的編碼與下面的編碼是軸對(duì)稱的（除了第一位以外）

后一個(gè)格雷編碼 是以上一個(gè)為基礎(chǔ) 做軸對(duì)稱生成，并且前一半編碼每項(xiàng)"0"+"xxx",后一半編碼每項(xiàng)"1"+"xxx",

每組的編碼的長(zhǎng)度為2^n

先實(shí)現(xiàn)這部分邏輯

let make = (n) => {
 if (n === 1) {
   return ["0", "1"]
 } else {
   let pre = make(n - 1)//獲取上次的格雷編碼
   let result = [] //存放結(jié)果
   let max = Math.pow(2, n) - 1//當(dāng)前n個(gè)最后一位的索引
   for (let i = 0, len = pre.length; i < len; i++) {
     result[i] = `0${pre[i]}`
     result[max - i] = `1${pre[i]}`
   }
   return result
 }
}

完整解題

let make = (n) => {
 if (n === 1) {
   return ["0", "1"]
 } else {
   let pre = make(n - 1)//獲取上次的格雷編碼
   let result = [] //存放結(jié)果
   let max = Math.pow(2, n) - 1//當(dāng)前n個(gè)最后一位的索引
   for (let i = 0, len = pre.length; i < len; i++) {
     result[i] = `0${pre[i]}`
     result[max - i] = `1${pre[i]}`
   }
   return result
 }
}
let grayCode = (n) => {
 if (n === 0) return [0]

 let arr = make(n)
 return arr.map(item => {
   return parseInt(item, 2)  //parseInt(item,10)默認(rèn)以十進(jìn)制來(lái)?yè)Q算
 })

};

將二進(jìn)制轉(zhuǎn)十進(jìn)制 parseInt

parseInt(string, radix)  String -> Number
console.log(parseInt("11", 2));//返回一個(gè)數(shù)字 radix默認(rèn)10 按照十進(jìn)制解析 如果字符串的第一個(gè)字符不能轉(zhuǎn)為數(shù)字 將返回NaN

提到這個(gè)parseInt 就要提 toString

let num = 100;
NumberObject.toString(radix); Number -> String
console.log(num.toString(2));//返回一個(gè)字符串 radix默認(rèn)10 按照十進(jìn)制解析
"1100100"
最快的范例

他的思路其實(shí)也差不多 只是不采用遞歸的形式 比較直接 以1=>["0", "1"] 為基礎(chǔ) 生成目標(biāo)格雷編碼

var grayCode = function (n) {//n=2
  if (n === 0) return [0]

  const nums = ["0", "1"]
  const arr_splice = Array.prototype.splice
  for (let t = 2; t <= n; t++) {
    let args = nums.slice().reverse()//["1","0"]
    args.forEach((s, i) => args[i] = "1" + s)//["11","10"]
    args.unshift(0)//["0",11","10"]
    args.unshift(nums.length)//["2","0",11","10"]
    console.log(args)
    nums.forEach((s, i) => nums[i] = "0" + s)// ["00", "01"]
    arr_splice.apply(nums, args)// nums=> [ "00", "01", "11", "10" ]
  }
  return nums.map(binary => parseInt(binary, 2))
};

上面最關(guān)鍵步驟

const arr_splice = Array.prototype.splice
...
args.unshift(0)//["0",11","10"]
args.unshift(nums.length)//["2","0",11","10"]
...
arr_splice.apply(nums, args)// nums=> [ "00", "01", "11", "10" ]


["00", "01"]+["11","10"] => [ "00", "01", "11", "10" ]
由于splice接受的是參數(shù)列表 arr.splice(2,0,"00","01") 不接受數(shù)組
所以巧妙的采用apply ，因?yàn)閍pply自身就是可以將集合的形式轉(zhuǎn)變?yōu)閰?shù)列表的形式
這也是call 與apply的區(qū)別之一

如果喜歡LeetCode或者更多數(shù)據(jù)結(jié)構(gòu)的內(nèi)容，可以戳這里,歡迎star

掃一掃

往期文章

數(shù)據(jù)結(jié)構(gòu)與算法-LeetCode 格雷編碼(No.89)

數(shù)據(jù)結(jié)構(gòu)與算法-LeetCode 種花問(wèn)題(No.605)

LeetCode-電話號(hào)碼的字母組合(No.17) 遞歸+hash

JavaScript 數(shù)據(jù)結(jié)構(gòu)與算法 這題你會(huì)嗎？

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/109513.html

相關(guān)文章

  • LeetCode-電話號(hào)碼的字母組合(No.17) 遞歸+hash

    摘要：電話號(hào)碼的字母組合給定一個(gè)僅包含數(shù)字的字符串，返回所有它能表示的字母組合。給出數(shù)字到字母的映射如下與電話按鍵相同。注意不對(duì)應(yīng)任何字母。 LeetCode 17. 電話號(hào)碼的字母組合 給定一個(gè)僅包含數(shù)字 2-9 的字符串，返回所有它能表示的字母組合。給出數(shù)字到字母的映射如下（與電話按鍵相同）。 注意 1 不對(duì)應(yīng)任何字母。 showImg(https://user-gold-cdn.xit...

    周國(guó)輝 評(píng)論0 收藏0

  • 數(shù)據(jù)結(jié)構(gòu)與算法-LeetCode 種花問(wèn)題(No.605)

    摘要：能否在不打破種植規(guī)則的情況下種入朵花能則返回，不能則返回。示例輸入輸出示例輸入輸出注意數(shù)組內(nèi)已種好的花不會(huì)違反種植規(guī)則。輸入的數(shù)組長(zhǎng)度范圍為。是非負(fù)整數(shù)，且不會(huì)超過(guò)輸入數(shù)組的大小。 LeetCode 605. 種花問(wèn)題 假設(shè)你有一個(gè)很長(zhǎng)的花壇，一部分地塊種植了花，另一部分卻沒(méi)有?？墒?，花卉不能種植在相鄰的地塊上，它們會(huì)爭(zhēng)奪水源，兩者都會(huì)死去。 給定一個(gè)花壇（表示為一個(gè)數(shù)組包含0和1，...

    xuexiangjys 評(píng)論0 收藏0

  • h5 vue引入微信sdk 實(shí)現(xiàn)分享朋友圈，分享給朋友，獲取地理位置

    最近入職的公司主要做微信端的h5，所以在所難免要引用sdk。雖然官方文檔寫(xiě)的還算清楚，但是還是有坑。 1.在index.html中 引入微信sdk 2.在assets/js 下新建文件 wx.js export default { wxShowMenu: function (that,sign=) { let url = window.location.href.split(#)[...

    tomorrowwu 評(píng)論0 收藏0

  • 微信小程序中圖片上傳阿里云Oss

    摘要：微信小程序圖片上傳阿里云服務(wù)器也折騰了蠻久才解決的，所以特意去記錄一下。上傳失敗第四步源碼在這里如果覺(jué)得這面文章對(duì)你有幫助的話，可給我點(diǎn)個(gè)這里，謝謝最后，希望這篇文章對(duì)你有所幫助，真真確確是可以在微信小程序中上傳圖片到阿里云的。 本人今年6月份畢業(yè)，最近剛在上海一家小公司實(shí)習(xí)，做微信小程序開(kāi)發(fā)。最近工作遇到一個(gè)小問(wèn)題。 微信小程序圖片上傳阿里云服務(wù)器Oss也折騰了蠻久才解決的，所以特意...

    Yang_River 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

Youngs

男|高級(jí)講師

TA的文章

閱讀更多
最新活動(dòng)
閱讀需要支付1元查看
<