1比特與2比特字符

有兩種特殊字符泽铛。第一種字符可以用一比特0來(lái)表示尚辑。第二種字符可以用兩比特(10 或 11)來(lái)表示。

現(xiàn)給一個(gè)由若干比特組成的字符串盔腔。問(wèn)最后一個(gè)字符是否必定為一個(gè)一比特字符杠茬。給定的字符串總是由0結(jié)束月褥。

• 示例 1:

  輸入: bits = [1, 0, 0]
  輸出: True
  解釋: 唯一的編碼方式是一個(gè)兩比特字符和一個(gè)一比特字符。所以最后一個(gè)字符是一比特字符瓢喉。
  

• 示例 2:

  輸入: bits = [1, 1, 1, 0]
  輸出: False
  解釋: 唯一的編碼方式是兩比特字符和兩比特字符宁赤。所以最后一個(gè)字符不是一比特字符。
  

題解：

• 正則
  這是我見(jiàn)過(guò)最暴力直接的方式栓票，由群內(nèi)小伙伴提出的解題方式决左。
  執(zhí)行用時(shí)：84ms；內(nèi)存消耗：34.4MB逗载；（我感覺(jué)這個(gè)測(cè)試不準(zhǔn)哆窿，每次提交的用時(shí)和消耗均不同）

   var isOneBitCharacter = function(bits) {
    return /^(10||11||0)*0$/.test(bits.join(""))
   };
  

• 對(duì)象存儲(chǔ)
  通過(guò)對(duì)象的方式；在循環(huán)中判斷厉斟，如果遇到0挚躯、10或者11等情況添加到對(duì)象的屬性上，這種方式可以有效的記錄一共出現(xiàn)1比特和2比特出現(xiàn)的次數(shù)和順序擦秽；最后判斷最后一個(gè)比特是1比特還是2比特码荔。
  執(zhí)行用時(shí)：88ms；內(nèi)存消耗：37.6MB感挥；

  var isOneBitCharacter = function(bits) {
      let obj = {};
      let count = 1;
      bits.forEach((item, i) => {
        if (!obj[count]) obj[count] = [];
        if (obj[count].length >= 2) {count++; obj[count] = []};
        obj[count].push(item)
        if (obj[count][0] == 0 && i!=bits.length-1) count++;
      })
      return obj[count]&&obj[count][0] === 0 ? true : false
  };
    //對(duì)象結(jié)構(gòu)如下
    {
      1:[0],
      2:[1,1],
      3:[1,0],
      ...
    } 
  

• 循環(huán)跳躍法
  循環(huán)缩搅，遇1就++，如果++后跳出循環(huán)触幼，就返回false硼瓣，如果還在循環(huán)內(nèi)，當(dāng)循環(huán)到最后一個(gè)的時(shí)候返回true置谦；
  執(zhí)行用時(shí)：72ms堂鲤；內(nèi)存消耗：34.2MB；

  var isOneBitCharacter = function(bits) {
    let bitsSize = bits.length
    for (let i = 0; i < bitsSize; ++i) {
      if (i == bitsSize - 1) return true
      if (bits[i])++i;
    }
    return false;
  };
  

二進(jìn)制求和

給定兩個(gè)二進(jìn)制字符串媒峡，返回他們的和（用二進(jìn)制表示）瘟栖。
輸入為非空字符串且只包含數(shù)字 1 和 0。

• 示例 1:

  輸入: a = "11", b = "1"
  輸出: "100"
  

• 示例 2:

  輸入: a = "1010", b = "1011"
  輸出: "10101"
  

題析：

面對(duì)這道題谅阿，很多人立馬想到的是2轉(zhuǎn)10半哟，然后轉(zhuǎn)2，但是這會(huì)面臨精度丟失的問(wèn)題签餐，如果解決了精度丟失的問(wèn)題寓涨，那么也不失為一個(gè)好的解題方法。那么就只有一種方法那就是逐位相加法氯檐。

題解：

• 補(bǔ)位法
  字符串轉(zhuǎn)數(shù)組缅茉，然后翻轉(zhuǎn)數(shù)組，取數(shù)組最長(zhǎng)的length循環(huán)男摧，在循環(huán)中數(shù)組短的自動(dòng)補(bǔ)0蔬墩，在循環(huán)中相加，判斷相加為0或1或2的情況耗拓。然后push到新數(shù)組中拇颅，最后翻轉(zhuǎn)，轉(zhuǎn)成字符串乔询。
  執(zhí)行用時(shí)：108ms樟插；內(nèi)存消耗：35.6MB；（最笨的辦法）

  var addBinary = function(a, b) {
    const alist=a.split('').reverse();
    const blist=b.split('').reverse();
    const arr=[];
    const len=alist.length>blist.length?alist.length:blist.length;
    for (let i = 0; i <= len-1; i++) {
        if (alist[i] != 0 && alist[i] != 1) {
          alist[i] = 0
        }
        if (blist[i] != 0 && blist[i] != 1) {
          blist[i] = 0
        }
        alist[i] = alist[i] - 0
        blist[i] = blist[i] - 0
  
        if (alist[i] + blist[i] > 1) {
          if (arr[i] == 0) {
            arr[i] = 1
          } else if (arr[i] == 1) {
            arr[i] = 1
            arr.push(1)
         } else {
            arr[i] = 0
            arr.push(1)
          }
        }
        if (alist[i] + blist[i] == 1) {
          if (arr[i]) {
            arr[i] = 0
            arr.push(1)
          } else {
            arr[i] = 1
          }
        }
        if (alist[i] + blist[i] == 0) {
          if (arr[i]) {
            arr[i] = 1
          } else {
            arr[i] = 0
          }
        }
      }
      return arr.reverse().join('')
  };
  

• 進(jìn)位拼接法
  與補(bǔ)位法類(lèi)似竿刁，區(qū)別就是在進(jìn)行計(jì)算時(shí)直接拼接字符串黄锤，會(huì)得到一個(gè)反向字符，需要最后再進(jìn)行翻轉(zhuǎn)食拜；按照位置給結(jié)果字符賦值鸵熟，最后如果有進(jìn)位，則在前方進(jìn)行字符串拼接添加進(jìn)位负甸。
  執(zhí)行用時(shí)：112ms流强；內(nèi)存消耗：35.9MB；（性能不好）

  var addBinary = function(a, b) {
    let ans = "";
    let ca = 0;
    for(let i = a.length - 1, j = b.length - 1;i >= 0 || j >= 0; i--, j--) {
        let sum = ca;
        sum += i >= 0 ? parseInt(a[i]) : 0;
        sum += j >= 0 ? parseInt(b[j]) : 0;
        ans += sum % 2;
        ca = Math.floor(sum / 2);
    }
    ans += ca == 1 ? ca : "";
    return ans.split('').reverse().join('');
  }
  

兩數(shù)之和

給定一個(gè)整數(shù)數(shù)組 nums和一個(gè)目標(biāo)值 target呻待，請(qǐng)你在該數(shù)組中找出和為目標(biāo)值的那兩個(gè)整數(shù)打月，并返回他們的數(shù)組下標(biāo)。

你可以假設(shè)每種輸入只會(huì)對(duì)應(yīng)一個(gè)答案蚕捉。但是奏篙，你不能重復(fù)利用這個(gè)數(shù)組中同樣的元素。

• 示例:

  給定 nums = [2, 7, 11, 15], target = 9
  因?yàn)閚ums[0] + nums[1] = 2 + 7 = 9
  所以返回 [0, 1]
  

題解：

• 雙循環(huán)法
  兩層循環(huán)迫淹，外層取第一元素秘通，內(nèi)層取相加元素;
  執(zhí)行用時(shí)：164ms；內(nèi)存消耗：34.6MB千绪；

  var twoSum = function(nums, target) {
   for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[i] + nums[j] === target) {
        return [i, j]
       }
     }
   }
  };
  

• 替換法
  復(fù)制原數(shù)組充易，循環(huán)原數(shù)組，防止重復(fù)荸型，通過(guò)splice替換復(fù)制的數(shù)組盹靴，如果復(fù)制數(shù)組中存在相加元素，找到索引瑞妇，即可得到結(jié)果數(shù)組稿静。
  執(zhí)行用時(shí)：304ms；內(nèi)存消耗：36MB辕狰；

  var twoSum = function(nums, target) {
    let list = [...nums];
    let arr = []
    nums.forEach((item, i) => {
      list.splice(i, 1, null)
      const sum = target - item;
      if (list.includes(sum)) {
        arr = [i, list.indexOf(sum)].sort()
      }
    })
    return arr
  }
  

• map
  通過(guò)新的數(shù)據(jù)類(lèi)型Map來(lái)實(shí)現(xiàn)改备；
  執(zhí)行用時(shí)：72ms；內(nèi)存消耗：35.1MB蔓倍；

  var twoSum = function(nums, target) {
    let map = new Map()
    for (let i = 0; i < nums.length; i++) {
       if (map.has(target - nums[i])) {
          return [map.get(target - nums[i]), i]
        }
        map.set(nums[i], i)
     }
  }
  

加一

給定一個(gè)由整數(shù)組成的非空數(shù)組所表示的非負(fù)整數(shù)悬钳，在該數(shù)的基礎(chǔ)上加一盐捷。
最高位數(shù)字存放在數(shù)組的首位， 數(shù)組中每個(gè)元素只存儲(chǔ)一個(gè)數(shù)字默勾。
你可以假設(shè)除了整數(shù) 0 之外碉渡，這個(gè)整數(shù)不會(huì)以零開(kāi)頭。

• 示例 1:

  輸入: [1,2,3]
  輸出: [1,2,4]
  解釋: 輸入數(shù)組表示數(shù)字 123母剥。
  

• 示例 2:

  輸入: [4,3,2,1]
  輸出: [4,3,2,2]
  解釋: 輸入數(shù)組表示數(shù)字 4321滞诺。
  

題解：

• 遞減相加法
  循環(huán)遞減，在循環(huán)中判斷相加是否為10环疼，如果為10习霹，就把當(dāng)前值改為0，下一值加一炫隶；
  執(zhí)行用時(shí)：72ms淋叶；內(nèi)存消耗：33.6MB；（性能不好）

  var plusOne = function(digits) {
    for(let i=digits.length-1;i>=0;i--){
        if(i==digits.length-1){
            digits[i]++
        }
        if(digits[i]==10){
            digits[i]=0
            if(i-1<0){
                digits.unshift(1)
            }else{    
                digits[i-1]++
            }
        }
    }
    return digits
  };
  

• 迭代
  for循環(huán)可以實(shí)現(xiàn)的等限，while也可以實(shí)現(xiàn)搏屑；
  執(zhí)行用時(shí)：72ms代态；內(nèi)存消耗：34.2MB够傍；

  var plusOne = function(digits) {
    const values = digits.reverse();
    let i = 0;
    values[i] += 1;
    while (true) {
      if (values[i] >= 10) {
        values[i] = 0;
        if (values[i + 1] === undefined) {
          values[i + 1] = 1;
          break;
        } else {
          values[i + 1] += 1
        }
        i++
      } else {
        break;
      }
    }
    return values.reverse()
  };
  

第一期結(jié)束男图，下期見(jiàn)。如果有一起學(xué)習(xí)的朋友筹误，可以加微信群桐早。

圖片發(fā)自簡(jiǎn)書(shū)App

鎮(zhèn)樓