JavaScript數(shù)據(jù)結(jié)構(gòu)與算法-Array-(leetcode原題)

joy968 發(fā)布于2019-08-26 13:51 / 1934人閱讀

摘要：的最大公約數(shù)是，記為，，。示例輸入輸出示例輸入輸出注意數(shù)組內(nèi)已種好的花不會違反種植規(guī)則。輸入的數(shù)組長度范圍為。是非負(fù)整數(shù)，且不會超過輸入數(shù)組的大小。

博客原文地址： https://finget.github.io/2019...

只出現(xiàn)一次的數(shù)字i

給定一個(gè)非空整數(shù)數(shù)組，除了某個(gè)元素只出現(xiàn)一次以外，其余每個(gè)元素均出現(xiàn)兩次。找出那個(gè)只出現(xiàn)了一次的元素。

說明：

你的算法應(yīng)該具有線性時(shí)間復(fù)雜度。 你可以不使用額外空間來實(shí)現(xiàn)嗎？

示例 1:

輸入: [2,2,1]
輸出: 1
示例 2:

輸入: [4,1,2,1,2]
輸出: 4

主要運(yùn)用的就是異或運(yùn)算和交換定律。

例如：1 ^ 1 = 0 、 2 ^ 2 = 0、 0 ^ 1 = 1 、1 ^ 1 ^ 2 ^ 3 ^ 2 ^ 4 ^ 3 = 4

/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function(nums) {
    // 這個(gè)方法可以找出存在奇數(shù)次的數(shù)字，不一定只有一次
    for(let i = 1;i
只出現(xiàn)一次的數(shù)字ii
給定一個(gè)非空整數(shù)數(shù)組，除了某個(gè)元素只出現(xiàn)一次以外，其余每個(gè)元素均出現(xiàn)了三次。找出那個(gè)只出現(xiàn)了一次的元素。

說明：

你的算法應(yīng)該具有線性時(shí)間復(fù)雜度。 你可以不使用額外空間來實(shí)現(xiàn)嗎？

示例 1:

輸入: [2,2,3,2]
輸出: 3
示例 2:

輸入: [0,1,0,1,0,1,99]
輸出: 99
/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function(nums) {
    // 這個(gè)方法也可以做上面的題，i+=2，可以以此類推下去
    nums.sort();
    for (let i = 0; i < nums.length; i+=3) {
        if (nums[i] !== nums[i + 1]) {
          return nums[i];
          break;
        }
    }
};
兩個(gè)數(shù)組的交集i
給定兩個(gè)數(shù)組，編寫一個(gè)函數(shù)來計(jì)算它們的交集。

示例 1:

輸入: nums1 = [1,2,2,1], nums2 = [2,2]
輸出: [2]
示例 2:

輸入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
輸出: [9,4]
說明:

輸出結(jié)果中的每個(gè)元素一定是唯一的。 *
我們可以不考慮輸出結(jié)果的順序。
思路：這個(gè)題比較簡單，用filter遍歷，用indexOf判斷nums1中的數(shù)字是否存在于nums2中，這可能會有重復(fù)出現(xiàn)的情況，再用Set 去重就行了。
/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var intersection = function(nums1, nums2) {
    return Array.from(new Set(nums1.filter(item => nums2.indexOf(item)>-1)))
};
兩個(gè)數(shù)組的交集ii
給定兩個(gè)數(shù)組，編寫一個(gè)函數(shù)來計(jì)算它們的交集。

示例 1:

輸入: nums1 = [1,2,2,1], nums2 = [2,2]
輸出: [2,2]
示例 2:

輸入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
輸出: [4,9]
說明：

輸出結(jié)果中每個(gè)元素出現(xiàn)的次數(shù)，應(yīng)與元素在兩個(gè)數(shù)組中出現(xiàn)的次數(shù)一致。
我們可以不考慮輸出結(jié)果的順序。
進(jìn)階:

如果給定的數(shù)組已經(jīng)排好序呢？你將如何優(yōu)化你的算法？
如果 nums1 的大小比 nums2 小很多，哪種方法更優(yōu)？
如果 nums2 的元素存儲在磁盤上，磁盤內(nèi)存是有限的，并且你不能一次加載所有的元素到內(nèi)存中，你該怎么辦？
思路：這個(gè)題和上面那個(gè)題，最大的區(qū)別是，數(shù)組中有重復(fù)的數(shù)字，也得返回，。而且還的考慮一下，數(shù)組的長度對遍歷的優(yōu)化。我的解法是判斷數(shù)組的長度，遍歷長度短的數(shù)組，因?yàn)閮蓚€(gè)數(shù)組的交集不可能超出最短的數(shù)組，然后用indexOf判斷是否是交集，再刪除長數(shù)組中重復(fù)的這一項(xiàng)，進(jìn)行下一次循環(huán)，因?yàn)?b>indexOf只能找出第一個(gè)出現(xiàn)的位置，會出錯。例如：[2,2]和[1,2,1],如果不刪，返回結(jié)果是[2,2]，正確結(jié)果是[2]。
/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var intersect = function(nums1, nums2) {
    let res = []
    function fnc(min, max) {
        let index = -1
        for (let i = 0; i < min.length; i++) {
            if (max.indexOf(min[i]) > -1) {
                res.push(min[i])
                max.splice(max.indexOf(min[i]),1)
            }
        }
    }
    if (nums1.length > nums2.length) {
        fnc(nums2, nums1)
    } else {
        fnc(nums1, nums2)
    }
    return res
};
加一
給定一個(gè)由整數(shù)組成的非空數(shù)組所表示的非負(fù)整數(shù)，在該數(shù)的基礎(chǔ)上加一。

最高位數(shù)字存放在數(shù)組的首位， 數(shù)組中每個(gè)元素只存儲一個(gè)數(shù)字。

你可以假設(shè)除了整數(shù) 0 之外，這個(gè)整數(shù)不會以零開頭。

示例 1:

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

輸入: [4,3,2,1]
輸出: [4,3,2,2]
解釋: 輸入數(shù)組表示數(shù)字 4321。
思路： 我一開始想的是，轉(zhuǎn)成數(shù)字直接+1，結(jié)果發(fā)現(xiàn)如果數(shù)字超出最大數(shù)字就會出錯。那就只能從數(shù)組最后一位開始加了，遇到9就得向前進(jìn)一位加一。這里用的是遞歸，用了一個(gè)res臨時(shí)變量來存0，然后將原數(shù)組最后一位刪了。如果數(shù)組長度為1，要么=10 => return [1,0,...res]，要么<10 => [...arr,...res]。
/**
 * @param {number[]} digits
 * @return {number[]}
 */
var plusOne = function(digits) {
    let res = []
    function fnc (arr) {
        let len = arr.length - 1
        if (arr[len] + 1 == 10) {
            if (len==0) {
                return [1,0,...res]
            }
            res.unshift(0)
            arr.pop()
            // 這里需要return 遞歸調(diào)用，不然會得到undefined
            return fnc(arr)
        } else {
            digits[len]+=1
            return [...arr,...res]
        }
    }
    return fnc(digits)
};
電話號碼
給定一個(gè)僅包含數(shù)字 2-9 的字符串，返回所有它能表示的字母組合。
給出數(shù)字到字母的映射如下（與電話按鍵相同）。注意 1 不對應(yīng)任何字母。

示例:
輸入："23"
輸出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
說明:
盡管上面的答案是按字典序排列的，但是你可以任意選擇答案輸出的順序。

這道題的思路就是遞歸，因?yàn)檩斎氲淖址L度不確定，所以就兩個(gè)兩個(gè)的組合，比如輸入234,他們對應(yīng)的字符串映射成["abc","def","ghi"],就先組合 abc和 def => [["ad","ae","af","bd","be","bf","cd","ce","cf"],"ghi"] 再遞歸。
export default (str) => {
  // 建立電話號碼鍵盤映射
  let map = ["", 1, "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]
  // 字符串轉(zhuǎn)成數(shù)組
  let num = str.split("")
  let code = []
  // code 是存儲 str 對應(yīng)的 映射 字符串的數(shù)組
  num.forEach(item => {
    if (map[item]) {
      code.push(map[item])
    }
  })
  // 遞歸函數(shù)
  let fnc = arr => {
    let tmp = []
    for (let i = 0; i < arr[0].length; i++) {
      for (let j = 0; j < arr[1].length; j++) {
        tmp.push(`${arr[0][i]}${arr[1][j]}`)
      }
    }
    // 替換數(shù)組前兩項(xiàng)，至關(guān)重要
    arr.splice(0, 2, tmp)
    if (arr.length > 1) {
      fnc(arr)
    } else {
      return tmp
    }
    // 最后會返回一個(gè)二維數(shù)組，而我們需要的就是第一個(gè)
    return arr[0]
  }
  return fnc(code)
}
卡牌分組
給定一副牌，每張牌上都寫著一個(gè)整數(shù)。

此時(shí)，你需要選定一個(gè)數(shù)字 X，使我們可以將整副牌按下述規(guī)則分成 1 組或更多組：

每組都有 X 張牌。
組內(nèi)所有的牌上都寫著相同的整數(shù)。
僅當(dāng)你可選的 X >= 2 時(shí)返回 true。

示例 1：

輸入：[1,2,3,4,4,3,2,1]
輸出：true
解釋：可行的分組是 [1,1]，[2,2]，[3,3]，[4,4]
示例 2：

輸入：[1,1,1,2,2,2,3,3]
輸出：false
解釋：沒有滿足要求的分組。
示例 3：

輸入：[1]
輸出：false
解釋：沒有滿足要求的分組。
示例 4：

輸入：[1,1]
輸出：true
解釋：可行的分組是 [1,1]
示例 5：

輸入：[1,1,2,2,2,2]
輸出：true
解釋：可行的分組是 [1,1]，[2,2]，[2,2]

提示：

1 <= deck.length <= 10000
0 <= deck[i] < 10000
思路：這個(gè)題比較難，主要是最大公約數(shù)。
最大公約數(shù)：幾個(gè)整數(shù)中公有的約數(shù)，叫做這幾個(gè)數(shù)的公約數(shù)；其中最大的一個(gè)，叫做這幾個(gè)數(shù)的最大公約數(shù)。例如：12、16的公約數(shù)有1、2、4，其中最大的一個(gè)是4，4是12與16的最大公約數(shù)，一般記為（12，16）=4。12、15、18的最大公約數(shù)是3，記為（12，15，18）=3。
// 此方法主要用到這樣一個(gè)定理：a和b的公約數(shù)==b和a%b的公約數(shù)==a%b和b%(a%b)的公約數(shù)…………； 另外要知道.a和0的公約數(shù)==a;

function Mgn(num1,num2){  
    return num2!=0 ? Mgn(num2,num1%num2):num1; 
}  
按位非運(yùn)算符“~”
先看看w3c的定義：

位運(yùn)算 NOT 由否定號（~）表示，它是 ECMAScript 中為數(shù)不多的與二進(jìn)制算術(shù)有關(guān)的運(yùn)算符之一。

位運(yùn)算 NOT 是三步的處理過程：

把運(yùn)算數(shù)轉(zhuǎn)換成 32 位數(shù)字

把二進(jìn)制數(shù)轉(zhuǎn)換成它的二進(jìn)制反碼（0->1, 1->0）

把二進(jìn)制數(shù)轉(zhuǎn)換成浮點(diǎn)數(shù)

簡單的理解，對任一數(shù)值 x 進(jìn)行按位非操作的結(jié)果為 -(x + 1)

console.log("~null: ", ~null);       // => -1
console.log("~undefined: ", ~undefined);  // => -1
console.log("~0: ", ~0);          // => -1
console.log("~{}: ", ~{});         // => -1
console.log("~[]: ", ~[]);         // => -1
console.log("~(1/0): ", ~(1/0));      // => -1
console.log("~false: ", ~false);      // => -1
console.log("~true: ", ~true);       // => -2
console.log("~1.2543: ", ~1.2543);     // => -2
console.log("~4.9: ", ~4.9);       // => -5
console.log("~(-2.999): ", ~(-2.999));   // => 1

那么, ~~x就為 -(-(x+1) + 1)

console.log("~~null: ", ~~null);       // => 0
console.log("~~undefined: ", ~~undefined);  // => 0
console.log("~~0: ", ~~0);          // => 0
console.log("~~{}: ", ~~{});         // => 0
console.log("~~[]: ", ~~[]);         // => 0
console.log("~~(1/0): ", ~~(1/0));      // => 0
console.log("~~false: ", ~~false);      // => 0
console.log("~~true: ", ~~true);       // => 1
console.log("~~1.2543: ", ~~1.2543);     // => 1
console.log("~~4.9: ", ~~4.9);       // => 4
console.log("~~(-2.999): ", ~~(-2.999));   // => -2

/**
 * @param {number[]} deck
 * @return {boolean}
 */
var hasGroupsSizeX = function(deck) {
    
    let map = {}
    for(let item of deck) {
        map[item] = ~~map[item] + 1
    }
    // map = {0:2,1:2,3:4} 這就是各個(gè)數(shù)出現(xiàn)的次數(shù)，然后去它們的最大公約數(shù)
    const min = Math.min(...Object.values(map))

    if(min < 2) return false
  
    for (let index of Array(min).fill().keys()) {
        if(index === 0) continue
        // 取最大公約數(shù)
        if(Object.values(map).every(item => item % (index + 1) === 0)) {
            return true
        }
    }
  
    return false
};
// 這是leetcode的最優(yōu)解法
/**
 * @param {number[]} deck
 * @return {boolean}
 */

const gcd = (...arr) => {
  // 取最大公約數(shù)
  let _gcd = (x, y) => (!y ? x : gcd(y, x % y))
  return [...arr].reduce((a, b) => _gcd(a, b))
}
var hasGroupsSizeX = function (deck) {
  
  let obj = {}
  deck.forEach(v => { obj[v] ? obj[v]++ : obj[v] = 1 })
  let arr = Object.values(obj)
  return gcd(...arr) !== 1
};
找出字符串中出現(xiàn)次數(shù)最多的字符
根據(jù)上面的題得出了這個(gè)解法
function maxStr(str) {
  let map = {}
  for(let v of str) {
    map[v] = ~~map[v] + 1
  }
  // 將object的value 變成一個(gè)數(shù)組
  let max = Math.max(...Object.values(map))
  for (let key in map) {
    if (map[key] == max){
      return key
    }
  }
}
種花問題
假設(shè)你有一個(gè)很長的花壇，一部分地塊種植了花，另一部分卻沒有?？墒?，花卉不能種植在相鄰的地塊上，它們會爭奪水源，兩者都會死去。

給定一個(gè)花壇（表示為一個(gè)數(shù)組包含0和1，其中0表示沒種植花，1表示種植了花），和一個(gè)數(shù) n 。能否在不打破種植規(guī)則的情況下種入 n 朵花？能則返回True，不能則返回False。

示例 1:

輸入: flowerbed = [1,0,0,0,1], n = 1
輸出: True
示例 2:

輸入: flowerbed = [1,0,0,0,1], n = 2
輸出: False
注意:

數(shù)組內(nèi)已種好的花不會違反種植規(guī)則。
輸入的數(shù)組長度范圍為 [1, 20000]。
n 是非負(fù)整數(shù)，且不會超過輸入數(shù)組的大小。
思路：[0,0,0] 前后都是0，就可以插入一個(gè)，然后數(shù)組下標(biāo)加2，再判斷。
暴力求解
/**
 * @param {number[]} flowerbed
 * @param {number} n
 * @return {boolean}
 */
var canPlaceFlowers = function(flowerbed, n) {
    let blank = 0
    if (flowerbed.length == 1&&flowerbed[0]==0) {
        return 1 >= n
    }
    for(let i = 0;i= n) {
              break;
            }
        }
    }
    return blank >= n
};
最后
創(chuàng)建了一個(gè)前端學(xué)習(xí)交流群，感興趣的朋友，一起來嗨呀！

GPU云服務(wù)器云服務(wù)器算法與數(shù)據(jù)結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法教程數(shù)據(jù)結(jié)構(gòu)與算法答案

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

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

發(fā)表評論

登陸后可評論

0條評論

joy968

男|高級講師

我要關(guān)注我要私信

TA的文章

初學(xué)C語言《掃雷》

閱讀 3067·2021-11-16 11:45
基于MDK創(chuàng)建STM32匯編語言工程——上機(jī)實(shí)驗(yàn)一（9527）

閱讀 3598·2021-09-29 09:34
Hostmem：$11.99/年KVM-512MB/10GB/500GB/洛杉磯機(jī)房

閱讀 713·2021-08-16 10:50
多余文字省略解決方案

閱讀 1581·2019-08-30 15:52
推薦一款強(qiáng)大的輕量級模塊化WEB前端快速開發(fā)框架--UIkit

閱讀 1972·2019-08-30 15:45
前端每日實(shí)戰(zhàn)：21# 視頻演示如何用純 CSS 創(chuàng)作文本滑動特效的 UI 界面

閱讀 868·2019-08-29 15:23
JavaScript數(shù)據(jù)結(jié)構(gòu)與算法-Array-(leetcode原題)

閱讀 1935·2019-08-26 13:51
前端抽象世界之DOM與Virtual DOM

閱讀 3308·2019-08-26 12:23

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

資訊專欄INFORMATION COLUMN

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺、長期優(yōu)惠，快來選購！

JavaScript數(shù)據(jù)結(jié)構(gòu)與算法-Array-(leetcode原題)

相關(guān)文章

*JavaScript**數(shù)據(jù)結(jié)構(gòu)與算法-Sort-(leetcode*原題)

*JavaScript**數(shù)據(jù)結(jié)構(gòu)與算法-String-(leetcode*原題)

**[Leetcode] Maximum Subarray 子序列最大和**

LeetCode——Longest Palindromic Substring

【算法】劍指 Offer II 110. 所有路徑｜797. 所有可能的路徑（多語言實(shí)現(xiàn)）

發(fā)表評論

0條評論

joy968

男|高級講師

TA的文章

初學(xué)C語言《掃雷》

基于MDK創(chuàng)建STM32匯編語言工程——上機(jī)實(shí)驗(yàn)一（9527）

Hostmem：$11.99/年KVM-512MB/10GB/500GB/洛杉磯機(jī)房

多余文字省略解決方案

推薦一款強(qiáng)大的輕量級模塊化WEB前端快速開發(fā)框架--UIkit

前端每日實(shí)戰(zhàn)：21# 視頻演示如何用純 CSS 創(chuàng)作文本滑動特效的 UI 界面