资讯专栏INFORMATION COLUMN

上云采购季！| 2核2G4M爆款云服务器低至59元/年，更有多台、长期优惠，快来选购！

立即前往
首页/文章专栏/TypeScript实现数组相关简单算法

TypeScript实现数组相关简单算法

cloud / 1326人阅读

摘要：本文只是简单理解算法，并不会深入的讨论。大部分来自数组部分。如果数组中每个元素都不相同，则返回。示例输入输出加给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。尽量减少操作次数。

</>复制代码 
  1. 算法（algorithm），在数学（算学）和计算机科学之中，为任何良定义的具体计算步骤的一个序列，常用于计算、数据处理和自动推理。精确而言，算法是一个表示为有限长列表的有效方法。算法应包含清晰定义的指令用于计算函数。                                                - 来自维基百科
写在前面

算法看起来在离我们一般的开发者不是很近，但是实际上又和我们的开发息息相关。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。现在想想大学的时候没有好好的学习算法和数据结构真的是后悔的吐血。本文只是简单理解算法，并不会深入的讨论。毕竟每一个深入讨论都够喝一壶了。只是理解一下算法的思维和实现。 毕竟9月是个跳槽黄金时期，说不定能帮上你得忙呢？

算法在在我看来最直观的作用就在于可以强化我们的编程思维逻辑。让我么养成是用简单的方式去解决问题的思维方式。下面我们一起来入算法的坑。本文中提到的相关的例子，都是相对比较简单的。大部分来自leetcode数组部分。代码都是我自己实现的，并不一定是最优解。欢迎各位大佬在issue中提交更好的实现方式。解析都写到了代码注释中。

为了避免一些不必要的错误，文中的示例使用Typescript编写，JavaScript 部分代码在这儿,本文主要分了两大部分 LeetCode/简单算法

Leetcode部分 1：删除排序数组中的重复项 
</>复制代码 
  1. 给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

示例
给定数组 nums = [1,1,2],
函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。
你不需要考虑数组中超出新长度后面的元素。

</>复制代码 
  1. /**
  2.  * 1 删除排序数组中的重复项
  3.  * 给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。
  4.  * 不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
  5.  * 示例
  6.  * 给定数组 nums = [1,1,2], 
  7.  * 函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。 
  8.  * 你不需要考虑数组中超出新长度后面的元素。
  9.  */
  10. const removeDuplicates =  function(nums: number[]): number {
  11.   let i: number = 0
  12.   for (let j = 0; j < nums.length; j++) {
  13.     if(nums[j] !== nums[i]) {
  14.       i++
  15.       nums[i] = nums[j]
  16.     }
  17.   }
  18.   nums.splice(i+1)
  19.   console.log(nums)
  20.   console.log(nums.length)
  21.   return i + 1
  22. }
  23. /**
  24.  * 解析
  25.  * 方法 双指针法
  26.  * i是慢指针，j是快指针 当我们遇到 nums[j] 
  27. eq nums[i]nums[j]≠nums[i] 时，跳过重复项的运行已经结束，
  28.  * 因此我们必须把它（nums[j]nums[j]）的值复制到 nums[i + 1]nums[i+1]。然后递增 ii，接着我们将再次重复相同的过程，直到 jj 到达数组的末尾为止。
  29.  * 复杂度分析：
  30.  * 时间复杂度： O(n) 假设数组长度是n 那么i和j最多就是遍历n步
  31.  * 空间复杂度： O(1)
  32.  */
  33. removeDuplicates([0,0,1,1,1,2,2,3,3,4])
2：买卖股票的最佳时机 
</>复制代码 
  1. 给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例

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

输出: 7

解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候
卖出, 这笔交易所能获得利润 = 5-1 = 4 。

</>复制代码 
  1. 随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。
</>复制代码 
  1. /**
  2.  * 2：  买卖股票的最佳时机
  3.  * 给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
  4.  * 设计一个算法来计算你所能获取的最大利润。你最多可以完成一次交易
  5.  * 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）
  6.  * 
  7.  * 输入: [7,1,5,3,6,4]
  8.  * 输出: 7
  9.  * 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
  10.  * 随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。
  11.  */
  12.  // 第一种方式
  13. const maxProfit = function (prices: number[]): number {
  14.   if(prices.length < 2) return 0
  15.   // 定义利润
  16.   let count: number = 0
  17.   let PreMin:number =prices[0]
  18.   // 获取最大的单天利润
  19.   for (let i = 0; i < prices.length; i++) {
  20.     count = Math.max(count, prices[i] - PreMin)
  21.     PreMin = Math.min(PreMin, prices[i])
  22.   }
  23.   console.log(count)
  24.   return count
  25. }
  26. /**
  27.  * 解析： 贪心算法
  28.  */
  29. console.log("=================股票最佳购买时机贪心算法===================");
  30. console.log(maxProfit([7,1,5,3,6,4]));
  31. console.log("====================================");
  32. // 第二种方式
  33. const maxProfitMore = function (prices: number[]) :number{
  34.   if(prices.length < 2) return 0
  35.   let ret = 0
  36.   for (let i = 0; i < prices.length; i++) {
  37.     if (prices[i+1] > prices[i]) {
  38.       ret += prices[i+1] - prices[i]
  39.     }
  40.   }
  41.   return ret
  42. }
  43. /**
  44.  * 解析： 非贪心算法 
  45.  * 只要下一天的价钱 大于今天的价钱 那我们就卖出当前天的 最终的结果就是我们的利润总和
  46.  */
  47. console.log("==================股票最佳购买时机非贪心算法==================");
  48. console.log(maxProfitMore([7,1,5,8,3,6,4]))
  49. console.log("=============================================");
3：旋转数组 
</>复制代码 
  1. 给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。

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

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

解释:

向右旋转 1 步: [7,1,2,3,4,5,6]

向右旋转 2 步: [6,7,1,2,3,4,5]

向右旋转 3 步: [5,6,7,1,2,3,4]

要求

要求使用空间复杂度为 O(1) 的原地算法。

</>复制代码 
  1. /**
  2.  * 3： 给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。
  3.  * 要求O(1)的空间复杂度，对原数组进行操作
  4.  */
  5. const rotate = function(nums: number[], k: number) {
  6.   // 循环k,通过k我们可以确定需要移动的次数
  7.   for (let i = 0; i < k; i++) {
  8.     // 先在前面插入我们需要移动的地方
  9.     nums.unshift(nums[nums.length -1 - i])
  10.   }
  11.   // 最后再去处理我们的数组
  12.   nums.splice(nums.length - k, k)
  13. }
  14. rotate([1,2,3,4,5,6,7],3)
4：存在重复 
</>复制代码 
  1. 给定一个整数数组，判断是否存在重复元素。如果任何值在数组中出现至少两次，函数返回 true。如果数组中每个元素都不相同，则返回 false。

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

</>复制代码 
  1. /**
  2.  * 4： 存在重复 
  3.  * 给定一个整数数组，判断是否存在重复元素。
  4.  * 如果任何值在数组中出现至少两次，函数返回 true。如果数组中每个元素都不相同，则返回 false。
  5.  * 
  6.  * 这个一定不是最优解
  7.  */
  8. const containsDuplicate = function (nums: number[]) :boolean{
  9.     // 设置flag
  10.     let judge = false
  11.     // 容错判断
  12.     if (nums.length <= 1) {
  13.       return judge
  14.     }
  15.     // 通过最简单直白的去重的思想去处理
  16.     let current :number[] =[]
  17.     for (let i = 0; i < nums.length; i++) {
  18.       if (current.indexOf(nums[i]) === -1) {
  19.         current.push(nums[i])
  20.       } else {
  21.         return judge = true
  22.       }
  23.     }
  24.     return judge
  25. }
  26. console.log("================是否存在重复算法====================");
  27. console.log(containsDuplicate([3,1]))
  28. console.log("====================================");
  29. // 这个其实是非常常见而且简单得一个算法 但是要考虑到得情况多一点
5：只出现一次的数字 
</>复制代码 
  1. 给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

示例

输入: [2,2,1]

输出: 1

要求
你的算法应该具有线性时间复杂度。 不适用额外的空间来实现

</>复制代码 
  1. /**
  2.  * 5: 只出现一次得数字
  3.  * 给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
  4.  * 你的算法应该具有线性时间复杂度。 不使用额外空间来实现
  5.  */
  6. const singleNumber = function(nums: number[]) :number {
  7.   let index= -1
  8.   // 双层进行比对 目的是当前key和数组中的每一个key进行比较
  9.   nums.forEach((key, j)=> {
  10.     //每次循环小游标
  11.     let count = 0
  12.     for (let k = 0; k < nums.length; k++) {
  13.       if (key === nums[k]) {
  14.         count += 1
  15.       }
  16.       // 循环完找出符合条件的下标
  17.       if (k === nums.length -1 && count === 1) {
  18.         index = j
  19.       }
  20.     }
  21.   })
  22.   return nums[index]
  23. }
  24. console.log("=================查找多带带数算法===================");
  25. console.log(singleNumber([2,2,1,3,3]))
  26. console.log("====================================");
6：两个数组的交集 
</>复制代码 
  1. 给定两个数组，编写一个函数来计算它们的交集。

示例

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

输出: [2,2]

要求

输出结果中每个元素出现的次数，应与元素在两个数组中出现的次数一致。

我们可以不考虑输出结果的顺序。

</>复制代码 
  1. /**
  2.  * 6：求两个数组的交集
  3.  */
  4. const intersect = function (nums1:number[], nums2:number[]) :number[]{
  5.   let arr:number[] = []
  6.   for (let i = 0; i < nums1.length; i++) {
  7.     if (nums2.indexOf(nums1[i]) !== -1 ) {
  8.       nums2.splice(nums2.indexOf(nums1[i]), 1)
  9.       arr.push(nums1[i])
  10.     }
  11.   }
  12.   return arr
  13. }
  14. /**
  15.  * 解析： 在求交集的过程中。主要的思想是关于什么是交集。
  16.  * 两个数组的重合部分理论上来讲就是交集
  17.  * 循环其中一个数组nums1在后在另外一个数组nums2中比对是否出现，如果出现的话就删除nums2中出现过的数组（注意是修改nums2）
  18.  */
  19. intersect([1,2,2,1], [2,2])
7：加1 
</>复制代码 
  1. 给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一.你可以假设除了整数 0 之外，这个整数不会以零开头。

示例

输入: [1,2,3]

输出: [1,2,4]

</>复制代码 
  1. /**
  2.  * 7：加1
  3.  * 给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。
  4.  * 你可以假设除了整数 0 之外，这个整数不会以零开头。
  5.  */
  6. const plusOne =function (nums: number[]) :number[] {
  7.   let j = nums.length - 1
  8.   // js无法正常表示大于16位的整数【非科学计数】
  9.   for (let i = nums.length - 1; i >=0; i--) {
  10.     // 开始逐个进行加法运算
  11.     if(i == j) {
  12.       // 大于10的情况
  13.       if(nums[i] + 1 >= 10){
  14.         nums[i] = nums[i] + 1 -10
  15.         j--
  16.         // 最后一次循环
  17.         if (i === 0) {
  18.           nums.unshift(1)
  19.         }
  20.       } else {
  21.         nums[j] ++
  22.       }
  23.     } else {
  24.       break
  25.     }
  26.   }
  27.   console.log(nums)
  28.   return nums
  29. }
  30. /**
  31.  * 解析： 如果使用太大的数的话转成数字再加1是不行的，我们需要对数组中的的单个数据进行运算，同样的是以辅助游标进行运算
  32.  * 辅助游标j的主要作用是记录需要+1的位置，如果当前的下标不等于j那么就跳出了循环：同时也提高了性能
  33.  */
  34. console.log("================加1算法====================");
  35. 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]))
  36. console.log("====================================");
8：移动零 
</>复制代码 
  1. 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

示例

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

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

要求

必须在原数组上操作，不能拷贝额外的数组。

尽量减少操作次数。

</>复制代码 
  1. /**
  2.  * 8: 移动零
  3.  * 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
  4.  */
  5. const moveZeroes = function(nums: number[]) {
  6.   // 0出现的个数
  7.   let j = 0
  8.   nums.forEach((el: number, index: number, arr: number[]) => {
  9.     if (nums[j] === 0) {
  10.       nums.splice(j, 1)
  11.       nums.push(0)
  12.     } else {
  13.       j++ 
  14.     }
  15.   })
  16.   console.log(nums)
  17. }
  18. /**
  19.  * 解析： 新建一个小游标j 这个是用来标识0出现的地方，每次移动完之后小游标是不变化的，因为原数组已经修改所以要固定一下游标
  20.  * 双游标法在算法真的很实用
  21.  */
  22. console.log("==================移动零算法==================");
  23. moveZeroes([1,2,0,0,0,1])
  24. console.log("====================================");
9：两数之和 
</>复制代码 
  1. 给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。

示例

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

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

所以返回 [0, 1]

</>复制代码 
  1. /**
  2.  * 第一种解法
  3.  * @param nums 
  4.  * @param target 
  5.  */
  6. const twoSumA = function (nums: number[], target: number) :number[] {
  7.   console.log("两数求和第一种解法")
  8.   let arr = [0,0] ,flag = false
  9.   for (let i = 0; i < nums.length; i++) {
  10.     compare(i)
  11.     if (flag) {
  12.       arr = [i, compare(i)]
  13.       break
  14.     }
  15.   }
  16.   /**
  17.    * @param num 
  18.    */
  19.   function compare(index: number) :number {
  20.     for (let j = 0; j < nums.length; j++) {
  21.       if (j!== index && nums[index] + nums[j] === target) {
  22.         flag = true
  23.         return j
  24.       }
  25.     }
  26.   }
  27.   return arr
  28. }
  29. /**
  30.  * 第二种解法
  31.  */
  32. const twoSumB = function (nums: number[], target: number) :number[] {
  33.   let arr = [0,0]
  34.   console.log("两数求和第二种解法")
  35.   for (let i = 0; i < nums.length; i++) {
  36.     for (let j = 0; j < nums.length; j++) {
  37.       if (j!== i && nums[i] + nums[j] === target) {
  38.         return arr = [i,j]
  39.       }
  40.     }
  41.   }
  42.   return arr
  43. }
  44. // 在进行一个数组中两个数得比较中：一定要注意在相加得时候要排除自身去进行相加。
  45. console.log("=================两数之和算法===================");
  46. console.log(twoSumA([3,2,4],6))
  47. console.log(twoSumB([2, 7, 11, 15],9))
  48. console.log("====================================");
10：有效的数独 
</>复制代码 
  1. 判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。

数字 1-9 在每一行只能出现一次。

数字 1-9 在每一列只能出现一次。

数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。

示例

给定

</>复制代码 
  1. [
  2.   ["5","3",".",".","7",".",".",".","."],
  3.   ["6",".",".","1","9","5",".",".","."],
  4.   [".","9","8",".",".",".",".","6","."],
  5.   ["8",".",".",".","6",".",".",".","3"],
  6.   ["4",".",".","8",".","3",".",".","1"],
  7.   ["7",".",".",".","2",".",".",".","6"],
  8.   [".","6",".",".",".",".","2","8","."],
  9.   [".",".",".","4","1","9",".",".","5"],
  10.   [".",".",".",".","8",".",".","7","9"]
  11. ]

输出 js true

说明

一个有效的数独（部分已被填充）不一定是可解的。

只需要根据以上规则，验证已经填入的数字是否有效即可。

给定数独序列只包含数字 1-9 和字符 "." 。

给定数独永远是 9x9 形式的。

</>复制代码 
  1. /**
  2.  * 10：有效得数独
  3.  */
  4. let board = /* [
  5.   ["5","3",".",".","7",".",".",".","."],
  6.   ["6",".",".","1","9","5",".",".","."],
  7.   [".","9","8",".",".",".",".","6","."],
  8.   ["8",".",".",".","6",".",".",".","3"],
  9.   ["4",".",".","8",".","3",".",".","1"],
  10.   ["7",".",".",".","2",".",".",".","6"],
  11.   [".","6",".",".",".",".","2","8","."],
  12.   [".",".",".","4","1","9",".",".","5"],
  13.   [".",".",".",".","8",".",".","7","9"] 
  14. ]*/
  15. [["7",".",".",".","4",".",".",".","."],
  16.  [".",".",".","8","6","5",".",".","."],
  17.  [".","1",".","2",".",".",".",".","."],
  18.  [".",".",".",".",".","9",".",".","."],
  19.  [".",".",".",".","5",".","5",".","."],
  20.  [".",".",".",".",".",".",".",".","."],
  21.  [".",".",".",".",".",".","2",".","."],
  22.  [".",".",".",".",".",".",".",".","."],
  23.  [".",".",".",".",".",".",".",".","."]
  24. ]
  25. const isValidSudoku = function (board: string[][]): boolean {
  26.   let isPass = true
  27.   const sudokuDeep = 9 // 数独深度
  28.   // 判断行和列
  29.   for (let i = 0; i < sudokuDeep; i++) {
  30.     let row:any = {}
  31.     let col:any = {}
  32.     for (let j = 0; j < sudokuDeep; j++) {
  33.       // 判断行
  34.       /**
  35.        * 判断方式
  36.        * 首先判断不为"." => 然后判断是否存在row对象中 
  37.        */
  38.       if (board[i][j] !== ".") {
  39.         if (row[board[i][j]]) {
  40.           console.log(board[i][j])
  41.           return isPass = false
  42.         } else {
  43.           row[board[i][j]] = board[i][j]
  44.         }
  45.       }
  46.       // 判断列
  47.       if (board[j][i] !== ".") {
  48.         if (col[board[j][i]]) {
  49.           console.log(board[j][i]);
  50.           return isPass = false
  51.         } else {
  52.           col[board[j][i]] = board[j][i]
  53.         }
  54.       }
  55.       // 判断九宫格 通过余数的形式判断出来当前所处的9宫格
  56.       // 先计算出位置
  57.       let c = Math.floor(i/3)  // col位置
  58.       let r = Math.floor(j/3) // row 位置
  59.       // 勾勒出九宫格
  60.       for (let m = c*3; m < c*3 + 3; m++) {
  61.         for (let n = r * 3; n < r * 3 + 3; n++) {
  62.           if (m === i && n === j) {
  63.             // m === i && n === j 这时指向同一个位置
  64.             continue
  65.           } else {
  66.             // 最重要的一次求值判断
  67.             if(board[m][n] != "." && board[i][j]!== "." && (board[i][j]) === board[m][n]) {
  68.               return isPass = false
  69.             } 
  70.           }
  71.         }
  72.       }
  73.       
  74.     }
  75.   }
  76.   return isPass
  77. }
  78. console.log("=================有效数独算法结果===================");
  79. console.log(isValidSudoku(board))
  80. console.log("====================================");
11：旋转图像 
</>复制代码 
  1. 给定一个 n × n 的二维矩阵表示一个图像。将图像顺时针旋转 90 度。

示例

给定

</>复制代码 
  1. [
  2.   [1,2,3],
  3.   [4,5,6],
  4.   [7,8,9]
  5. ],

输出

</>复制代码 
  1. [
  2.   [7,4,1],
  3.   [8,5,2],
  4.   [9,6,3]
  5. ]

要求

你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。

</>复制代码 
  1. /**
  2.  * 11： 旋转图像
  3.  **/
  4. const matrix = [
  5.   [1,2,3],
  6.   [4,5,6],
  7.   [7,8,9]
  8. ]
  9. // 
  10. /* const matrix = [
  11.   [ 5, 1, 9,11],
  12.   [ 2, 4, 8,10],
  13.   [13, 3, 6, 7],
  14.   [15,14,12,16]
  15. ] */
  16. const rotateMaps = function (matrix:number[][]) {
  17.   const n = matrix.length
  18.   // 倒叙循环进行90度的反转
  19.   for (let i = n-1; i >= 0; i--) {
  20.     // 新数组补位到原数组中，为了是实现原地的旋转操作，如果不需要
  21.     for (let j = 0; j < n ; j++) {
  22.       // console.log(`当前坐标[${i},${j}]`)
  23.       const current = matrix[i][j]
  24.       matrix[j].push(current)
  25.       // 没完成一组的赋值操作，就删除旋转前数组
  26.       if(j === n - 1) {
  27.         matrix[i].splice(0, n)
  28.       }
  29.     }
  30.   }
  31.   console.log(matrix)
  32.   // return matrix
  33. }
  34. console.log("================旋转图像算法====================");
  35. console.log(rotateMaps(matrix));
  36. console.log("====================================");
其他部分(持续更新...)

这一部分先出demo，后面的代码中的解析注释会慢慢加上

12: 查找父亲节点 
</>复制代码 
  1. fid为0代表一级，fid如果和fid为0的cid相等的话代表二级 以此类推...
</>复制代码 
  1. /**
  2.  * 10：找父亲节点
  3.  * fid为0代表一级，fid如果和fid为0的cid相等的话代表二级 以此类推...
  4.  */
  5. const findArr = [
  6.   {"fid":0,"cid":3,"flag":"最外层3"},
  7.   {"fid":0,"cid":4,"flag":"最外层4"},
  8.   {"fid":4,"cid":5,"flag":"最外层-4"},
  9.   {"fid":5,"cid":6,"flag":"最外层-4-1"},
  10.   {"fid":0,"cid":7,"flag":"最外层7"},
  11.   {"fid":7,"cid":8,"flag":"最外层-7"},
  12.   {"fid":0,"cid":9,"flag":"最外层9"},
  13.   {"fid":9,"cid":10,"flag":"最外层9-1"},
  14.   {"fid":9,"cid":11,"flag":"最外层9-2"},
  15.   {"fid":11,"cid":12,"flag":"最外层9-2-1"}
  16. ]
  17. /**
  18.  * 第一种方法：双递归方式
  19.  * @param arr 
  20.  */
  21. const findfid  = function (arr: any[]): any[] {
  22.   let newArr:any[] = []
  23.   for (let i = 0; i < arr.length; i++) {
  24.     let flagId = arr[i].cid // 取出来一个flag 这个是用于和下一个级别匹配的
  25.     for (let j = 0; j < arr.length; j++) {
  26.       const elJ = arr[j]
  27.       if (elJ.fid === flagId) { // fid 和 上级id 匹配
  28.         (arr[i].children = []).push(elJ)
  29.       }
  30.     }
  31.     // 只存入第一等级
  32.     arr[i].fid === 0 && newArr.push(arr[i])
  33.   }
  34.   return newArr
  35. }
  36. /**
  37.  * 第二种方法： 使用对象存储id 然后和fid进行对比
  38.  * @param arr 
  39.  */
  40. const findfidByObj = function (arr: any[]): any[] {
  41.   let newArr:any[] = []
  42.   let flagObj: any = {}
  43.   arr.forEach(v => {
  44.     flagObj[v.cid] = v
  45.   })
  46.   arr.forEach (item => {
  47.     // 根据当前遍历对象的fid,去map对象中找到对应索引的id
  48.     const top = flagObj[item.fid]
  49.     if (top) {
  50.       // 如果找到索引，那么说明此项不在顶级当中,那么需要把此项添加到，他对应的父级中
  51.       (top.children || (top.children = [])).push(item)
  52.     } else {
  53.       // 如果没有在map中找到对应的索引ID,那么直接把当前的item添加到newData结果集中作为顶级
  54.       newArr.push(item)
  55.     }
  56.   })
  57.   return newArr
  58. }
  59. console.log("====================================");
  60. console.log("找父亲节点方式");
  61. console.log(findfid(findArr))
  62. console.log(findfidByObj(findArr))
  63. console.log("====================================");
13：简单选择排序 
</>复制代码 
  1. 选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法。
</>复制代码 
  1. /**
  2.  * 交换参数
  3.  * @param {*} arr 
  4.  * @param {*} a 
  5.  * @param {*} b 
  6.  */
  7. const swap = function(arr: number[], a:number, b:number) {
  8.   let curr = arr[a]
  9.   arr[a] = arr[b]
  10.   arr[b] = curr
  11. }
  12. /**
  13.  * 
  14.  * @param {选择排序算法} arr 
  15.  */
  16. const sort = function (arr: number[]) {
  17.   console.time()
  18.   for (let i = 0; i < arr.length; i++) {
  19.     //假设遍历的当前第一个是最小的
  20.     let minIndex = i
  21.     //第二次遍历把arr[minIndex]和数组中的其他的值进行遍历
  22.     for (let j = 0; j < arr.length; j++) {
  23.       if(arr[minIndex] > arr[j]){
  24.         minIndex = j
  25.       }
  26.     }
  27.     //外层循环做交换
  28.     swap(arr,minIndex,i)
  29.   }
  30.   console.log(arr)
  31.   console.timeEnd()
  32. }
  33. sort([3,6,28,123,34])
14：简单冒泡排序 
</>复制代码 
  1. 冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法。它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果他们的顺序（如从大到小、首字母从A到Z）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素已经排序完成。
</>复制代码 
  1. /**
  2.  * @param {*冒泡排序算法} arr 
  3.  */
  4. const bubbleSort = function (arr: number[]){
  5.   console.log("冒泡算法开始时间:")
  6.   console.time()
  7.   for (let i = 0; i < arr.length; i++) {
  8.     // 这个循环时获取到之后的项进行比较
  9.     for (let j = i+1; j > 0; j--) {
  10.       // 这个核心就是 如果当前项小于前一项那么当前项向上冒泡
  11.       if(arr[i] < arr[j-1]){
  12.         // 冒泡交换
  13.         swap(arr,j,j-1)
  14.       }
  15.     }
  16.   }
  17.   console.timeEnd()
  18.   console.log(arr)
  19. }
  20. bubbleSort([3,123,6,28,34])
15：简单插入排序 
</>复制代码 
  1. 插入排序是基于比较的排序。所谓的基于比较，就是通过比较数组中的元素，看谁大谁小，根据结果来调整元素的位置。
</>复制代码 
  1. //插入排序算法
  2. /**
  3.  * 
  4.  * @param {插入排序} arr 
  5.  */
  6. const insertSort = function (arr: number[]){
  7.   console.time()
  8.   for (let i = 0; i < arr.length; i++) {
  9.     // 在一次循环的时候首先缓存下来当前的值和上一个index 缓存上一个index用来比较
  10.     let compareIndex = i -1
  11.     let currentValue = arr[i]
  12.     // 在当前位置可以比较并且当前的值小于前一项的值的时候插入缓存的值然后修改index
  13.     while (compareIndex >=0 && arr[compareIndex] > currentValue) {
  14.       arr[compareIndex + 1] = arr[compareIndex]
  15.       compareIndex--
  16.     }
  17.     arr[compareIndex + 1 ] = currentValue
  18.   }
  19.   console.timeEnd()
  20.   console.log(arr)
  21. }
  22. insertSort([3,2,1])
16：简单二分查找算法 
</>复制代码 
  1. 二分查找也称为折半查找。是指在有序的数组里找出指定的值，返回该值在数组中的索引。
</>复制代码 
  1. /**
  2.  * 二分查找算法 
  3.  * 什么叫二分查找？ 二分查找也称为折半查找。是指在有序的数组里找出指定的值，返回该值在数组中的索引。
  4.  * （1）从有序数组的最中间元素开始查找，如果该元素正好是指定查找的值，则查找过程结束。否则进行下一步; 
  5.  * （2）如果指定要查找的元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半区域查找，然后重复第一步的操作; 
  6.  * （3）重复以上过程，直到找到目标元素的索引，查找成功;或者直到子数组为空，查找失败。
  7.  * 注意： 这个先要把数组排序一下 在有序数组中查找
  8.  * 优点是比较次数少，查找速度快，平均性能好；
  9.  * 其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。
  10.  */
  11. /**
  12.  * 非递归实现
  13.  * @param {*} arr 
  14.  * @param {*} target 
  15.  */
  16. function binarySearcNoRecursive(arr: number[], target: number){
  17.   let low: number = 0, high: number = arr.length-1
  18.   while(low <= high) {
  19.     // 首先找到中间位置
  20.     let middle = ((high + low ) / 2)
  21.     if( target === arr[middle]){
  22.       return middle
  23.     } else if (target > arr[middle]){
  24.       low = middle + 1
  25.     } else if ( target < arr[middle] ){
  26.       high = middle -1
  27.     }else { 
  28.       return -1
  29.     }
  30.   }
  31. }
  32. const result = binarySearcNoRecursive( [1,2,3,4,5,6,7,8,9,10,11,23,44,86], 23)
  33. console.log(`二分查找不用循环找到的位置:${result}`)
  34. /**
  35.  * 递归实现 循环调用自身
  36.  * @param {*} arr 
  37.  * @param {*} target 
  38.  */
  39. function binarySearcRecursive(arr: number[], low:number, high: number, target:number){
  40.   if(low > high){
  41.     return -1
  42.   }
  43.   let middle = ((high + low ) / 2)
  44.   if(arr[middle] === target){
  45.     return middle
  46.   } else if(arr[middle] > target){
  47.     high = middle -1
  48.     binarySearcRecursive(arr, low, high, target)
  49.   } else if(arr[middle] < target){
  50.     low = middle + 1
  51.     binarySearcRecursive(arr, low, high, target)
  52.   }
  53. }
  54. const  recursiveRes = binarySearcNoRecursive( [1,2,3,4,5,6,7,8,9,10,11,23,44,86], 3)
  55. console.log(`二分查找不用循环找到的位置:${recursiveRes}`)
总结

算法再编程中占据着相当重要的地位，语言的技术都可以速成。但是算法需要扎实的理论知识作为地基。本文只是根据leetcode中的题目，简单的实现一下。感受一下算法的魅力。学习的话我建议还是系统深入的学。

代码地址

相应的JavaScript示例代码地址

原文地址 如果觉得有用得话给个⭐吧

GPU云服务器 云服务器 自相关算法原理 自相关算法matlab 字符串相关算法 自然语言处理相关算法

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/97667.html

相关文章

  • TypeScript版算法与数据结构-栈

    摘要：时间复杂度是出栈在有之前数组的基础上，出栈也非常简单，实际上的底层操作就是删除数组中的最后一个元素，并返回该元素。出栈也是一个时间复杂度为的操作更多相关数据结构，可以前往我的。 本文的源码在这里，可以参考一下 栈也是一种使用非常广泛的线性数据结构，它具有后进先出last in first out的特点。就像我们平时一本一本的往桌上放书，等到我们又想用书时，我们首先接触到的总是我们最后一...

    JayChen 评论0 收藏0

  • 重读《学习JavaScript数据结构与算法-第三版》-第2章 ECMAScript与TypeScr

    摘要：第二种接口的概念和面向对象编程相关接口视为一份合约，在合约里可以定义这份合约的类或接口的行为接口告诉类，它需要实现一个叫做的方法，并且该方法接收一个参数。 定场诗 八月中秋白露，路上行人凄凉； 小桥流水桂花香，日夜千思万想。 心中不得宁静，清早览罢文章， 十年寒苦在书房，方显才高志广。 前言 洛伊安妮·格罗纳女士所著的《学习JavaScript数据结构与算法》第三版于2019年的5月份...

    TZLLOG 评论0 收藏0

  • 一名【合格】前端工程师的自检清单

    摘要：在他的重学前端课程中提到到现在为止，前端工程师已经成为研发体系中的重要岗位之一。大部分前端工程师的知识，其实都是来自于实践和工作中零散的学习。一基础前端工程师吃饭的家伙，深度广度一样都不能差。 开篇 前端开发是一个非常特殊的行业，它的历史实际上不是很长，但是知识之繁杂，技术迭代速度之快是其他技术所不能比拟的。 winter在他的《重学前端》课程中提到： 到现在为止，前端工程师已经成为研...

    罗志环 评论0 收藏0

  • 一名【合格】前端工程师的自检清单

    摘要：在他的重学前端课程中提到到现在为止，前端工程师已经成为研发体系中的重要岗位之一。大部分前端工程师的知识，其实都是来自于实践和工作中零散的学习。一基础前端工程师吃饭的家伙，深度广度一样都不能差。开篇 前端开发是一个非常特殊的行业，它的历史实际上不是很长，但是知识之繁杂，技术迭代速度之快是其他技术所不能比拟的。 winter在他的《重学前端》课程中提到： 到现在为止，前端工程师已经成为研发体系...

    isaced 评论0 收藏0

  • 使用TypeScript和Canvas编写移动端贪吃蛇大作战游戏

    摘要：基本介绍一款移动端贪吃蛇大作战游戏。主要的游戏逻辑有贪吃蛇移动碰撞检测贪吃蛇碰撞碰撞墙壁和吃食物。贪吃蛇的身体如何跟随头部移动需要分为两种情况，在单位时间内贪吃蛇移动一单位长度和贪吃蛇移动多单位长度。 基本介绍 一款移动端贪吃蛇大作战游戏。(只支持移动端) 这是一个临近 deadline 的课设项目，为了方便地使用TS，我直接使用angular-cli生成了TypeScript的项...

    AlphaWallet 评论0 收藏0

发表评论

登陆后可评论

0条评论

cloud

男|高级讲师
我要私信

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<