TypeScript實現(xiàn)數(shù)組相關(guān)簡單算法

cloud 發(fā)布于2019-08-23 11:55 / 1265人閱讀

摘要：本文只是簡單理解算法，并不會深入的討論。大部分來自數(shù)組部分。如果數(shù)組中每個元素都不相同，則返回。示例輸入輸出加給定一個由整數(shù)組成的非空數(shù)組所表示的非負(fù)整數(shù)，在該數(shù)的基礎(chǔ)上加一。盡量減少操作次數(shù)。

算法（algorithm），在數(shù)學(xué)（算學(xué)）和計算機(jī)科學(xué)之中，為任何良定義的具體計算步驟的一個序列，常用于計算、數(shù)據(jù)處理和自動推理。精確而言，算法是一個表示為有限長列表的有效方法。算法應(yīng)包含清晰定義的指令用于計算函數(shù)。                                                - 來自維基百科

寫在前面

算法看起來在離我們一般的開發(fā)者不是很近，但是實際上又和我們的開發(fā)息息相關(guān)。不同的算法可能用不同的時間、空間或效率來完成同樣的任務(wù)。一個算法的優(yōu)劣可以用空間復(fù)雜度與時間復(fù)雜度來衡量?，F(xiàn)在想想大學(xué)的時候沒有好好的學(xué)習(xí)算法和數(shù)據(jù)結(jié)構(gòu)真的是后悔的吐血。本文只是簡單理解算法，并不會深入的討論。畢竟每一個深入討論都夠喝一壺了。只是理解一下算法的思維和實現(xiàn)。 畢竟9月是個跳槽黃金時期，說不定能幫上你得忙呢？

算法在在我看來最直觀的作用就在于可以強(qiáng)化我們的編程思維邏輯。讓我么養(yǎng)成是用簡單的方式去解決問題的思維方式。下面我們一起來入算法的坑。本文中提到的相關(guān)的例子，都是相對比較簡單的。大部分來自leetcode數(shù)組部分。代碼都是我自己實現(xiàn)的，并不一定是最優(yōu)解。歡迎各位大佬在issue中提交更好的實現(xiàn)方式。解析都寫到了代碼注釋中。

為了避免一些不必要的錯誤，文中的示例使用Typescript編寫，JavaScript 部分代碼在這兒,本文主要分了兩大部分 LeetCode/簡單算法

Leetcode部分 1：刪除排序數(shù)組中的重復(fù)項

給定一個排序數(shù)組，你需要在原地刪除重復(fù)出現(xiàn)的元素，使得每個元素只出現(xiàn)一次，返回移除后數(shù)組的新長度。不要使用額外的數(shù)組空間，你必須在原地修改輸入數(shù)組并在使用 O(1) 額外空間的條件下完成。

示例
給定數(shù)組 nums = [1,1,2],
函數(shù)應(yīng)該返回新的長度 2, 并且原數(shù)組 nums 的前兩個元素被修改為 1, 2。
你不需要考慮數(shù)組中超出新長度后面的元素。

/**
 * 1 刪除排序數(shù)組中的重復(fù)項
 * 給定一個排序數(shù)組，你需要在原地刪除重復(fù)出現(xiàn)的元素，使得每個元素只出現(xiàn)一次，返回移除后數(shù)組的新長度。
 * 不要使用額外的數(shù)組空間，你必須在原地修改輸入數(shù)組并在使用 O(1) 額外空間的條件下完成。
 * 示例
 * 給定數(shù)組 nums = [1,1,2], 
 * 函數(shù)應(yīng)該返回新的長度 2, 并且原數(shù)組 nums 的前兩個元素被修改為 1, 2。 
 * 你不需要考慮數(shù)組中超出新長度后面的元素。
 */
const removeDuplicates =  function(nums: number[]): number {
  let i: number = 0
  for (let j = 0; j < nums.length; j++) {
    if(nums[j] !== nums[i]) {
      i++
      nums[i] = nums[j]
    }
  }
  nums.splice(i+1)
  console.log(nums)
  console.log(nums.length)
  return i + 1
}
/**
 * 解析
 * 方法 雙指針法
 * i是慢指針，j是快指針 當(dāng)我們遇到 nums[j] 
eq nums[i]nums[j]≠nums[i] 時，跳過重復(fù)項的運行已經(jīng)結(jié)束，
 * 因此我們必須把它（nums[j]nums[j]）的值復(fù)制到 nums[i + 1]nums[i+1]。然后遞增 ii，接著我們將再次重復(fù)相同的過程，直到 jj 到達(dá)數(shù)組的末尾為止。
 * 復(fù)雜度分析：
 * 時間復(fù)雜度： O(n) 假設(shè)數(shù)組長度是n 那么i和j最多就是遍歷n步
 * 空間復(fù)雜度： O(1)
 */
removeDuplicates([0,0,1,1,1,2,2,3,3,4])

2：買賣股票的最佳時機(jī)

給定一個數(shù)組，它的第 i 個元素是一支給定股票第 i 天的價格。設(shè)計一個算法來計算你所能獲取的最大利潤。你可以盡可能地完成更多的交易（多次買賣一支股票）。

注意：你不能同時參與多筆交易（你必須在再次購買前出售掉之前的股票）。

示例

輸入: [7,1,5,3,6,4]

輸出: 7

解釋: 在第 2 天（股票價格 = 1）的時候買入，在第 3 天（股票價格 = 5）的時候
賣出, 這筆交易所能獲得利潤 = 5-1 = 4 。

隨后，在第 4 天（股票價格 = 3）的時候買入，在第 5 天（股票價格 = 6）的時候賣出, 這筆交易所能獲得利潤 = 6-3 = 3 。

/**
 * 2：  買賣股票的最佳時機(jī)
 * 給定一個數(shù)組，它的第 i 個元素是一支給定股票第 i 天的價格。
 * 設(shè)計一個算法來計算你所能獲取的最大利潤。你最多可以完成一次交易
 * 注意：你不能同時參與多筆交易（你必須在再次購買前出售掉之前的股票）
 * 
 * 輸入: [7,1,5,3,6,4]
 * 輸出: 7
 * 解釋: 在第 2 天（股票價格 = 1）的時候買入，在第 3 天（股票價格 = 5）的時候賣出, 這筆交易所能獲得利潤 = 5-1 = 4 。
 * 隨后，在第 4 天（股票價格 = 3）的時候買入，在第 5 天（股票價格 = 6）的時候賣出, 這筆交易所能獲得利潤 = 6-3 = 3 。
 */
 // 第一種方式
const maxProfit = function (prices: number[]): number {
  if(prices.length < 2) return 0
  // 定義利潤
  let count: number = 0
  let PreMin:number =prices[0]
  // 獲取最大的單天利潤
  for (let i = 0; i < prices.length; i++) {
    count = Math.max(count, prices[i] - PreMin)
    PreMin = Math.min(PreMin, prices[i])
  }
  console.log(count)
  return count
}
/**
 * 解析： 貪心算法
 */
console.log("=================股票最佳購買時機(jī)貪心算法===================");
console.log(maxProfit([7,1,5,3,6,4]));
console.log("====================================");

// 第二種方式
const maxProfitMore = function (prices: number[]) :number{
  if(prices.length < 2) return 0
  let ret = 0
  for (let i = 0; i < prices.length; i++) {
    if (prices[i+1] > prices[i]) {
      ret += prices[i+1] - prices[i]
    }
  }
  return ret
}
/**
 * 解析： 非貪心算法 
 * 只要下一天的價錢 大于今天的價錢 那我們就賣出當(dāng)前天的 最終的結(jié)果就是我們的利潤總和
 */
console.log("==================股票最佳購買時機(jī)非貪心算法==================");
console.log(maxProfitMore([7,1,5,8,3,6,4]))
console.log("=============================================");

3：旋轉(zhuǎn)數(shù)組

給定一個數(shù)組，將數(shù)組中的元素向右移動 k 個位置，其中 k 是非負(fù)數(shù)。

示例
輸入: [1,2,3,4,5,6,7] 和 k = 3

輸出: [5,6,7,1,2,3,4]

解釋:

向右旋轉(zhuǎn) 1 步: [7,1,2,3,4,5,6]

向右旋轉(zhuǎn) 2 步: [6,7,1,2,3,4,5]

向右旋轉(zhuǎn) 3 步: [5,6,7,1,2,3,4]

要求

要求使用空間復(fù)雜度為 O(1) 的原地算法。

/**
 * 3： 給定一個數(shù)組，將數(shù)組中的元素向右移動 k 個位置，其中 k 是非負(fù)數(shù)。
 * 要求O(1)的空間復(fù)雜度，對原數(shù)組進(jìn)行操作
 */
const rotate = function(nums: number[], k: number) {
  // 循環(huán)k,通過k我們可以確定需要移動的次數(shù)
  for (let i = 0; i < k; i++) {
    // 先在前面插入我們需要移動的地方
    nums.unshift(nums[nums.length -1 - i])
  }
  // 最后再去處理我們的數(shù)組
  nums.splice(nums.length - k, k)
}
rotate([1,2,3,4,5,6,7],3)

4：存在重復(fù)

給定一個整數(shù)數(shù)組，判斷是否存在重復(fù)元素。如果任何值在數(shù)組中出現(xiàn)至少兩次，函數(shù)返回 true。如果數(shù)組中每個元素都不相同，則返回 false。

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

/**
 * 4： 存在重復(fù) 
 * 給定一個整數(shù)數(shù)組，判斷是否存在重復(fù)元素。
 * 如果任何值在數(shù)組中出現(xiàn)至少兩次，函數(shù)返回 true。如果數(shù)組中每個元素都不相同，則返回 false。
 * 
 * 這個一定不是最優(yōu)解
 */
const containsDuplicate = function (nums: number[]) :boolean{
    // 設(shè)置flag
    let judge = false
    // 容錯判斷
    if (nums.length <= 1) {
      return judge
    }
    // 通過最簡單直白的去重的思想去處理
    let current :number[] =[]
    for (let i = 0; i < nums.length; i++) {
      if (current.indexOf(nums[i]) === -1) {
        current.push(nums[i])
      } else {
        return judge = true
      }
    }
    return judge
}
console.log("================是否存在重復(fù)算法====================");
console.log(containsDuplicate([3,1]))
console.log("====================================");
// 這個其實是非常常見而且簡單得一個算法 但是要考慮到得情況多一點

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

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

示例

輸入: [2,2,1]

輸出: 1

要求
你的算法應(yīng)該具有線性時間復(fù)雜度。不適用額外的空間來實現(xiàn)

/**
 * 5: 只出現(xiàn)一次得數(shù)字
 * 給定一個非空整數(shù)數(shù)組，除了某個元素只出現(xiàn)一次以外，其余每個元素均出現(xiàn)兩次。找出那個只出現(xiàn)了一次的元素。
 * 你的算法應(yīng)該具有線性時間復(fù)雜度。 不使用額外空間來實現(xiàn)
 */
const singleNumber = function(nums: number[]) :number {
  let index= -1
  // 雙層進(jìn)行比對 目的是當(dāng)前key和數(shù)組中的每一個key進(jìn)行比較
  nums.forEach((key, j)=> {
    //每次循環(huán)小游標(biāo)
    let count = 0
    for (let k = 0; k < nums.length; k++) {
      if (key === nums[k]) {
        count += 1
      }
      // 循環(huán)完找出符合條件的下標(biāo)
      if (k === nums.length -1 && count === 1) {
        index = j
      }
    }
  })
  return nums[index]
}
console.log("=================查找多帶帶數(shù)算法===================");
console.log(singleNumber([2,2,1,3,3]))
console.log("====================================");

6：兩個數(shù)組的交集

給定兩個數(shù)組，編寫一個函數(shù)來計算它們的交集。

示例

輸入: nums1 = [1,2,2,1], nums2 = [2,2]

輸出: [2,2]

要求

輸出結(jié)果中每個元素出現(xiàn)的次數(shù)，應(yīng)與元素在兩個數(shù)組中出現(xiàn)的次數(shù)一致。

我們可以不考慮輸出結(jié)果的順序。

/**
 * 6：求兩個數(shù)組的交集
 */
const intersect = function (nums1:number[], nums2:number[]) :number[]{
  let arr:number[] = []
  for (let i = 0; i < nums1.length; i++) {
    if (nums2.indexOf(nums1[i]) !== -1 ) {
      nums2.splice(nums2.indexOf(nums1[i]), 1)
      arr.push(nums1[i])
    }
  }
  return arr
}
/**
 * 解析： 在求交集的過程中。主要的思想是關(guān)于什么是交集。
 * 兩個數(shù)組的重合部分理論上來講就是交集
 * 循環(huán)其中一個數(shù)組nums1在后在另外一個數(shù)組nums2中比對是否出現(xiàn)，如果出現(xiàn)的話就刪除nums2中出現(xiàn)過的數(shù)組（注意是修改nums2）
 */
intersect([1,2,2,1], [2,2])

7：加1

給定一個由整數(shù)組成的非空數(shù)組所表示的非負(fù)整數(shù)，在該數(shù)的基礎(chǔ)上加一.你可以假設(shè)除了整數(shù) 0 之外，這個整數(shù)不會以零開頭。

示例

輸入: [1,2,3]

輸出: [1,2,4]

/**
 * 7：加1
 * 給定一個由整數(shù)組成的非空數(shù)組所表示的非負(fù)整數(shù)，在該數(shù)的基礎(chǔ)上加一。
 * 你可以假設(shè)除了整數(shù) 0 之外，這個整數(shù)不會以零開頭。
 */
const plusOne =function (nums: number[]) :number[] {
  let j = nums.length - 1
  // js無法正常表示大于16位的整數(shù)【非科學(xué)計數(shù)】
  for (let i = nums.length - 1; i >=0; i--) {
    // 開始逐個進(jìn)行加法運算
    if(i == j) {
      // 大于10的情況
      if(nums[i] + 1 >= 10){
        nums[i] = nums[i] + 1 -10
        j--
        // 最后一次循環(huán)
        if (i === 0) {
          nums.unshift(1)
        }
      } else {
        nums[j] ++
      }
    } else {
      break
    }
  }
  console.log(nums)
  return nums
}
/**
 * 解析： 如果使用太大的數(shù)的話轉(zhuǎn)成數(shù)字再加1是不行的，我們需要對數(shù)組中的的單個數(shù)據(jù)進(jìn)行運算，同樣的是以輔助游標(biāo)進(jìn)行運算
 * 輔助游標(biāo)j的主要作用是記錄需要+1的位置，如果當(dāng)前的下標(biāo)不等于j那么就跳出了循環(huán)：同時也提高了性能
 */
console.log("================加1算法====================");
console.log(plusOne([8,2,1,,1,2,2,2,3,5,5,5,5,5,2,3,4,2,3,4,5,5,5,5,2,9]))
console.log("====================================");

8：移動零

給定一個數(shù)組 nums，編寫一個函數(shù)將所有 0 移動到數(shù)組的末尾，同時保持非零元素的相對順序。

示例

輸入: [0,1,0,3,12]

輸出: [1,3,12,0,0]

要求

必須在原數(shù)組上操作，不能拷貝額外的數(shù)組。

盡量減少操作次數(shù)。

/**
 * 8: 移動零
 * 給定一個數(shù)組 nums，編寫一個函數(shù)將所有 0 移動到數(shù)組的末尾，同時保持非零元素的相對順序。
 */
const moveZeroes = function(nums: number[]) {
  // 0出現(xiàn)的個數(shù)
  let j = 0
  nums.forEach((el: number, index: number, arr: number[]) => {
    if (nums[j] === 0) {
      nums.splice(j, 1)
      nums.push(0)
    } else {
      j++ 
    }
  })
  console.log(nums)
}
/**
 * 解析： 新建一個小游標(biāo)j 這個是用來標(biāo)識0出現(xiàn)的地方，每次移動完之后小游標(biāo)是不變化的，因為原數(shù)組已經(jīng)修改所以要固定一下游標(biāo)
 * 雙游標(biāo)法在算法真的很實用
 */
console.log("==================移動零算法==================");
moveZeroes([1,2,0,0,0,1])
console.log("====================================");

9：兩數(shù)之和

給定一個整數(shù)數(shù)組和一個目標(biāo)值，找出數(shù)組中和為目標(biāo)值的兩個數(shù)。你可以假設(shè)每個輸入只對應(yīng)一種答案，且同樣的元素不能被重復(fù)利用。

示例

給定 nums = [2, 7, 11, 15], target = 9

因為 nums[0] + nums[1] = 2 + 7 = 9

所以返回 [0, 1]

/**
 * 第一種解法
 * @param nums 
 * @param target 
 */
const twoSumA = function (nums: number[], target: number) :number[] {
  console.log("兩數(shù)求和第一種解法")
  let arr = [0,0] ,flag = false
  for (let i = 0; i < nums.length; i++) {
    compare(i)
    if (flag) {
      arr = [i, compare(i)]
      break
    }
  }
  /**
   * @param num 
   */
  function compare(index: number) :number {
    for (let j = 0; j < nums.length; j++) {
      if (j!== index && nums[index] + nums[j] === target) {
        flag = true
        return j
      }
    }
  }
  return arr
}
/**
 * 第二種解法
 */
const twoSumB = function (nums: number[], target: number) :number[] {
  let arr = [0,0]
  console.log("兩數(shù)求和第二種解法")
  for (let i = 0; i < nums.length; i++) {
    for (let j = 0; j < nums.length; j++) {
      if (j!== i && nums[i] + nums[j] === target) {
        return arr = [i,j]
      }
    }
  }
  return arr
}
// 在進(jìn)行一個數(shù)組中兩個數(shù)得比較中：一定要注意在相加得時候要排除自身去進(jìn)行相加。
console.log("=================兩數(shù)之和算法===================");
console.log(twoSumA([3,2,4],6))
console.log(twoSumB([2, 7, 11, 15],9))
console.log("====================================");

10：有效的數(shù)獨

判斷一個 9x9 的數(shù)獨是否有效。只需要根據(jù)以下規(guī)則，驗證已經(jīng)填入的數(shù)字是否有效即可。

數(shù)字 1-9 在每一行只能出現(xiàn)一次。

數(shù)字 1-9 在每一列只能出現(xiàn)一次。

數(shù)字 1-9 在每一個以粗實線分隔的 3x3 宮內(nèi)只能出現(xiàn)一次。

示例

給定

[
  ["5","3",".",".","7",".",".",".","."],
  ["6",".",".","1","9","5",".",".","."],
  [".","9","8",".",".",".",".","6","."],
  ["8",".",".",".","6",".",".",".","3"],
  ["4",".",".","8",".","3",".",".","1"],
  ["7",".",".",".","2",".",".",".","6"],
  [".","6",".",".",".",".","2","8","."],
  [".",".",".","4","1","9",".",".","5"],
  [".",".",".",".","8",".",".","7","9"]
]

輸出 js true

說明

一個有效的數(shù)獨（部分已被填充）不一定是可解的。

只需要根據(jù)以上規(guī)則，驗證已經(jīng)填入的數(shù)字是否有效即可。

給定數(shù)獨序列只包含數(shù)字 1-9 和字符 "." 。

給定數(shù)獨永遠(yuǎn)是 9x9 形式的。

/**
 * 10：有效得數(shù)獨
 */
let board = /* [
  ["5","3",".",".","7",".",".",".","."],
  ["6",".",".","1","9","5",".",".","."],
  [".","9","8",".",".",".",".","6","."],
  ["8",".",".",".","6",".",".",".","3"],
  ["4",".",".","8",".","3",".",".","1"],
  ["7",".",".",".","2",".",".",".","6"],
  [".","6",".",".",".",".","2","8","."],
  [".",".",".","4","1","9",".",".","5"],
  [".",".",".",".","8",".",".","7","9"] 
]*/
[["7",".",".",".","4",".",".",".","."],
 [".",".",".","8","6","5",".",".","."],
 [".","1",".","2",".",".",".",".","."],
 [".",".",".",".",".","9",".",".","."],
 [".",".",".",".","5",".","5",".","."],
 [".",".",".",".",".",".",".",".","."],
 [".",".",".",".",".",".","2",".","."],
 [".",".",".",".",".",".",".",".","."],
 [".",".",".",".",".",".",".",".","."]
]
const isValidSudoku = function (board: string[][]): boolean {
  let isPass = true
  const sudokuDeep = 9 // 數(shù)獨深度
  // 判斷行和列
  for (let i = 0; i < sudokuDeep; i++) {
    let row:any = {}
    let col:any = {}
    for (let j = 0; j < sudokuDeep; j++) {
      // 判斷行
      /**
       * 判斷方式
       * 首先判斷不為"." => 然后判斷是否存在row對象中 
       */
      if (board[i][j] !== ".") {
        if (row[board[i][j]]) {
          console.log(board[i][j])
          return isPass = false
        } else {
          row[board[i][j]] = board[i][j]
        }
      }
      // 判斷列
      if (board[j][i] !== ".") {
        if (col[board[j][i]]) {
          console.log(board[j][i]);
          return isPass = false
        } else {
          col[board[j][i]] = board[j][i]
        }
      }
      // 判斷九宮格 通過余數(shù)的形式判斷出來當(dāng)前所處的9宮格
      // 先計算出位置
      let c = Math.floor(i/3)  // col位置
      let r = Math.floor(j/3) // row 位置
      // 勾勒出九宮格
      for (let m = c*3; m < c*3 + 3; m++) {
        for (let n = r * 3; n < r * 3 + 3; n++) {
          if (m === i && n === j) {
            // m === i && n === j 這時指向同一個位置
            continue
          } else {
            // 最重要的一次求值判斷
            if(board[m][n] != "." && board[i][j]!== "." && (board[i][j]) === board[m][n]) {
              return isPass = false
            } 
          }
        }
      }
      
    }
  }
  return isPass
}
console.log("=================有效數(shù)獨算法結(jié)果===================");
console.log(isValidSudoku(board))
console.log("====================================");

11：旋轉(zhuǎn)圖像

給定一個 n × n 的二維矩陣表示一個圖像。將圖像順時針旋轉(zhuǎn) 90 度。

示例

給定

[
  [1,2,3],
  [4,5,6],
  [7,8,9]
],

輸出

[
  [7,4,1],
  [8,5,2],
  [9,6,3]
]

要求

你必須在原地旋轉(zhuǎn)圖像，這意味著你需要直接修改輸入的二維矩陣。請不要使用另一個矩陣來旋轉(zhuǎn)圖像。

/**
 * 11： 旋轉(zhuǎn)圖像
 **/
const matrix = [
  [1,2,3],
  [4,5,6],
  [7,8,9]
]
// 
/* const matrix = [
  [ 5, 1, 9,11],
  [ 2, 4, 8,10],
  [13, 3, 6, 7],
  [15,14,12,16]
] */
const rotateMaps = function (matrix:number[][]) {
  const n = matrix.length
  // 倒敘循環(huán)進(jìn)行90度的反轉(zhuǎn)
  for (let i = n-1; i >= 0; i--) {
    // 新數(shù)組補位到原數(shù)組中，為了是實現(xiàn)原地的旋轉(zhuǎn)操作，如果不需要
    for (let j = 0; j < n ; j++) {
      // console.log(`當(dāng)前坐標(biāo)[${i},${j}]`)
      const current = matrix[i][j]
      matrix[j].push(current)
      // 沒完成一組的賦值操作，就刪除旋轉(zhuǎn)前數(shù)組
      if(j === n - 1) {
        matrix[i].splice(0, n)
      }
    }
  }
  console.log(matrix)
  // return matrix
}

console.log("================旋轉(zhuǎn)圖像算法====================");
console.log(rotateMaps(matrix));
console.log("====================================");

其他部分(持續(xù)更新...)

這一部分先出demo，后面的代碼中的解析注釋會慢慢加上

12: 查找父親節(jié)點

fid為0代表一級，fid如果和fid為0的cid相等的話代表二級 以此類推...

/**
 * 10：找父親節(jié)點
 * fid為0代表一級，fid如果和fid為0的cid相等的話代表二級 以此類推...
 */
const findArr = [
  {"fid":0,"cid":3,"flag":"最外層3"},
  {"fid":0,"cid":4,"flag":"最外層4"},
  {"fid":4,"cid":5,"flag":"最外層-4"},
  {"fid":5,"cid":6,"flag":"最外層-4-1"},
  {"fid":0,"cid":7,"flag":"最外層7"},
  {"fid":7,"cid":8,"flag":"最外層-7"},
  {"fid":0,"cid":9,"flag":"最外層9"},
  {"fid":9,"cid":10,"flag":"最外層9-1"},
  {"fid":9,"cid":11,"flag":"最外層9-2"},
  {"fid":11,"cid":12,"flag":"最外層9-2-1"}
]
/**
 * 第一種方法：雙遞歸方式
 * @param arr 
 */
const findfid  = function (arr: any[]): any[] {
  let newArr:any[] = []
  for (let i = 0; i < arr.length; i++) {
    let flagId = arr[i].cid // 取出來一個flag 這個是用于和下一個級別匹配的
    for (let j = 0; j < arr.length; j++) {
      const elJ = arr[j]
      if (elJ.fid === flagId) { // fid 和 上級id 匹配
        (arr[i].children = []).push(elJ)
      }
    }
    // 只存入第一等級
    arr[i].fid === 0 && newArr.push(arr[i])
  }
  return newArr
}
/**
 * 第二種方法： 使用對象存儲id 然后和fid進(jìn)行對比
 * @param arr 
 */
const findfidByObj = function (arr: any[]): any[] {
  let newArr:any[] = []
  let flagObj: any = {}
  arr.forEach(v => {
    flagObj[v.cid] = v
  })
  arr.forEach (item => {
    // 根據(jù)當(dāng)前遍歷對象的fid,去map對象中找到對應(yīng)索引的id
    const top = flagObj[item.fid]
    if (top) {
      // 如果找到索引，那么說明此項不在頂級當(dāng)中,那么需要把此項添加到，他對應(yīng)的父級中
      (top.children || (top.children = [])).push(item)
    } else {
      // 如果沒有在map中找到對應(yīng)的索引ID,那么直接把當(dāng)前的item添加到newData結(jié)果集中作為頂級
      newArr.push(item)
    }
  })
  return newArr
}
console.log("====================================");
console.log("找父親節(jié)點方式");
console.log(findfid(findArr))
console.log(findfidByObj(findArr))
console.log("====================================");

13：簡單選擇排序

選擇排序（Selection sort）是一種簡單直觀的排序算法。它的工作原理是每一次從待排序的數(shù)據(jù)元素中選出最?。ɑ蜃畲螅┑囊粋€元素，存放在序列的起始位置，直到全部待排序的數(shù)據(jù)元素排完。 選擇排序是不穩(wěn)定的排序方法。

/**
 * 交換參數(shù)
 * @param {*} arr 
 * @param {*} a 
 * @param {*} b 
 */
const swap = function(arr: number[], a:number, b:number) {
  let curr = arr[a]
  arr[a] = arr[b]
  arr[b] = curr
}
/**
 * 
 * @param {選擇排序算法} arr 
 */
const sort = function (arr: number[]) {
  console.time()
  for (let i = 0; i < arr.length; i++) {
    //假設(shè)遍歷的當(dāng)前第一個是最小的
    let minIndex = i
    //第二次遍歷把arr[minIndex]和數(shù)組中的其他的值進(jìn)行遍歷
    for (let j = 0; j < arr.length; j++) {
      if(arr[minIndex] > arr[j]){
        minIndex = j
      }
    }
    //外層循環(huán)做交換
    swap(arr,minIndex,i)
  }
  console.log(arr)
  console.timeEnd()
}
sort([3,6,28,123,34])

14：簡單冒泡排序

冒泡排序（Bubble Sort），是一種計算機(jī)科學(xué)領(lǐng)域的較簡單的排序算法。它重復(fù)地走訪過要排序的元素列，依次比較兩個相鄰的元素，如果他們的順序（如從大到小、首字母從A到Z）錯誤就把他們交換過來。走訪元素的工作是重復(fù)地進(jìn)行直到?jīng)]有相鄰元素需要交換，也就是說該元素已經(jīng)排序完成。

/**
 * @param {*冒泡排序算法} arr 
 */
const bubbleSort = function (arr: number[]){
  console.log("冒泡算法開始時間:")
  console.time()
  for (let i = 0; i < arr.length; i++) {
    // 這個循環(huán)時獲取到之后的項進(jìn)行比較
    for (let j = i+1; j > 0; j--) {
      // 這個核心就是 如果當(dāng)前項小于前一項那么當(dāng)前項向上冒泡
      if(arr[i] < arr[j-1]){
        // 冒泡交換
        swap(arr,j,j-1)
      }
    }
  }
  console.timeEnd()
  console.log(arr)
}
bubbleSort([3,123,6,28,34])

15：簡單插入排序

插入排序是基于比較的排序。所謂的基于比較，就是通過比較數(shù)組中的元素，看誰大誰小，根據(jù)結(jié)果來調(diào)整元素的位置。

//插入排序算法
/**
 * 
 * @param {插入排序} arr 
 */
const insertSort = function (arr: number[]){
  console.time()
  for (let i = 0; i < arr.length; i++) {
    // 在一次循環(huán)的時候首先緩存下來當(dāng)前的值和上一個index 緩存上一個index用來比較
    let compareIndex = i -1
    let currentValue = arr[i]
    // 在當(dāng)前位置可以比較并且當(dāng)前的值小于前一項的值的時候插入緩存的值然后修改index
    while (compareIndex >=0 && arr[compareIndex] > currentValue) {
      arr[compareIndex + 1] = arr[compareIndex]
      compareIndex--
    }
    arr[compareIndex + 1 ] = currentValue
  }
  console.timeEnd()
  console.log(arr)
}
insertSort([3,2,1])

16：簡單二分查找算法

二分查找也稱為折半查找。是指在有序的數(shù)組里找出指定的值，返回該值在數(shù)組中的索引。

/**
 * 二分查找算法 
 * 什么叫二分查找？ 二分查找也稱為折半查找。是指在有序的數(shù)組里找出指定的值，返回該值在數(shù)組中的索引。
 * （1）從有序數(shù)組的最中間元素開始查找，如果該元素正好是指定查找的值，則查找過程結(jié)束。否則進(jìn)行下一步; 
 * （2）如果指定要查找的元素大于或者小于中間元素，則在數(shù)組大于或小于中間元素的那一半?yún)^(qū)域查找，然后重復(fù)第一步的操作; 
 * （3）重復(fù)以上過程，直到找到目標(biāo)元素的索引，查找成功;或者直到子數(shù)組為空，查找失敗。
 * 注意： 這個先要把數(shù)組排序一下 在有序數(shù)組中查找
 * 優(yōu)點是比較次數(shù)少，查找速度快，平均性能好；
 * 其缺點是要求待查表為有序表，且插入刪除困難。因此，折半查找方法適用于不經(jīng)常變動而查找頻繁的有序列表。
 */
/**
 * 非遞歸實現(xiàn)
 * @param {*} arr 
 * @param {*} target 
 */
function binarySearcNoRecursive(arr: number[], target: number){
  let low: number = 0, high: number = arr.length-1
  while(low <= high) {
    // 首先找到中間位置
    let middle = ((high + low ) / 2)
    if( target === arr[middle]){
      return middle
    } else if (target > arr[middle]){
      low = middle + 1
    } else if ( target < arr[middle] ){
      high = middle -1
    }else { 
      return -1
    }
  }
}
const result = binarySearcNoRecursive( [1,2,3,4,5,6,7,8,9,10,11,23,44,86], 23)
console.log(`二分查找不用循環(huán)找到的位置:${result}`)
/**
 * 遞歸實現(xiàn) 循環(huán)調(diào)用自身
 * @param {*} arr 
 * @param {*} target 
 */
function binarySearcRecursive(arr: number[], low:number, high: number, target:number){
  if(low > high){
    return -1
  }
  let middle = ((high + low ) / 2)
  if(arr[middle] === target){
    return middle
  } else if(arr[middle] > target){
    high = middle -1
    binarySearcRecursive(arr, low, high, target)
  } else if(arr[middle] < target){
    low = middle + 1
    binarySearcRecursive(arr, low, high, target)
  }
}
const  recursiveRes = binarySearcNoRecursive( [1,2,3,4,5,6,7,8,9,10,11,23,44,86], 3)
console.log(`二分查找不用循環(huán)找到的位置:${recursiveRes}`)

總結(jié)

算法再編程中占據(jù)著相當(dāng)重要的地位，語言的技術(shù)都可以速成。但是算法需要扎實的理論知識作為地基。本文只是根據(jù)leetcode中的題目，簡單的實現(xiàn)一下。感受一下算法的魅力。學(xué)習(xí)的話我建議還是系統(tǒng)深入的學(xué)。

代碼地址

相應(yīng)的JavaScript示例代碼地址

原文地址如果覺得有用得話給個?吧

云服務(wù)器 GPU云服務(wù)器自相關(guān)算法原理自相關(guān)算法matlab 字符串相關(guān)算法自然語言處理相關(guān)算法

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

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

發(fā)表評論

登陸后可評論

0條評論

cloud

男|高級講師

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

TA的文章

#黑五#Database Mart，美國達(dá)拉斯VPS/獨服/GPU服務(wù)器4折優(yōu)惠，月付低至$3.59

閱讀 2879·2021-11-22 11:56
【Python從入門到實戰(zhàn)】一篇文章帶你搞懂Python中的類~

閱讀 3597·2021-11-15 11:39
Python中if判斷語句

閱讀 926·2021-09-24 09:48
VoLLcloud：大促銷-香港vps大帶寬-CMI三網(wǎng)直連-全場7折-月付低至2.8刀-2G冗余-

閱讀 789·2021-08-17 10:14
慶祝新年?畫一顆圣誕樹?還是...

閱讀 1368·2019-08-30 15:55
calc

閱讀 2780·2019-08-30 15:55
【winter重學(xué)前端筆記13】瀏覽器：一個瀏覽器是如何工作的？CSS計算

閱讀 1343·2019-08-30 15:44
margin 實現(xiàn)水平居中，垂直居中原理

閱讀 2813·2019-08-30 10:59

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

資訊專欄INFORMATION COLUMN

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

TypeScript實現(xiàn)數(shù)組相關(guān)簡單算法

相關(guān)文章

TypeScript版算法與數(shù)據(jù)結(jié)構(gòu)-棧

重讀《學(xué)習(xí)JavaScript數(shù)據(jù)結(jié)構(gòu)與算法-第三版》-第2章 ECMAScript與TypeScr

一名【合格】前端工程師的自檢清單

一名【合格】前端工程師的自檢清單

**使用TypeScript和Canvas編寫移動端貪吃蛇大作戰(zhàn)游戲**

發(fā)表評論

0條評論

cloud

男|高級講師

TA的文章

#黑五#Database Mart，美國達(dá)拉斯VPS/獨服/GPU服務(wù)器4折優(yōu)惠，月付低至$3.59

【Python從入門到實戰(zhàn)】一篇文章帶你搞懂Python中的類~

Python中if判斷語句

VoLLcloud：大促銷-香港vps大帶寬-CMI三網(wǎng)直連-全場7折-月付低至2.8刀-2G冗余-

慶祝新年?畫一顆圣誕樹?還是...

calc

【winter重學(xué)前端筆記13】瀏覽器：一個瀏覽器是如何工作的？CSS計算

margin 實現(xiàn)水平居中，垂直居中原理

最新活動

資訊專欄INFORMATION COLUMN

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

TypeScript實現(xiàn)數(shù)組相關(guān)簡單算法

相關(guān)文章

發(fā)表評論

0條評論

男|高級講師

TA的文章

最新活動

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