my729 / algorithm Goto Github PK

View Code? Open in Web Editor NEW

0.0 1.0 0.0 11 KB

收集算法题（主要是常见的前端面试算法），并写出题解和思路，重点在于记录自己思考的过程

algorithm's Introduction

前端算法

收集算法题（主要是常见的前端面试算法），并写出题解和思路，重点在于记录自己思考的过程

所有的算法主要基于JavaScript语言实现

algorithm's People

Contributors

Watchers

algorithm's Issues

题目

数字反转

要求：不能转字符串和数组处理

输出前和输出后都是Number类型

比如12345 反转后为 54321

解析

利用数学的整除和取余

数字对10取余可拿到个位数, 如下：

12345 % 10 === 5

数字对10整除并向下取整，可拿到一个除去个位数的整数，如下：

Math.floor(12345 / 10) === 1234

思路

文字描述有点抽象，我们拿一个数举例，如下：

12345 对10取余拿到 5
5 * 10000
12345 整除 10 拿到 1234
对拿到的1234 重复前三个步骤
最终将结果相加 510000 + 41000 + 3100 + 210 + 1

答案

尾递归的方法

let reverseNum = (num, res = 0) => {
  let intNum = Math.floor(num / 10)
  let len = 0
  while(intNum > 0) {
    len++
    intNum = Math.floor(intNum / 10)
  }
  let result = res + (num % 10) * (10**len)
  res = len > 0 ? reverseNum(Math.floor(num / 10), result) : res + num
  return res
}

reverseNum(1234567) // 调用

非尾递归方法

let reverseNum = (num) => {
  let res = 0
  let intNum = Math.floor(num / 10)
  let len = 0
  while(intNum > 0) {
    len++
    intNum = Math.floor(intNum / 10)
  }
  let result = res + (num % 10) * (10**len)
  res = len > 0 ? reverseNum(Math.floor(num / 10)) + result : res + num
  return res
}

reverseNum(1234567) // 调用

题目

这道题目将考点拆分成4点，要求用递归算法实现，限制15行代码以内，限制时间10分钟

创建一个长度为5的空数组arr
生成一个2 ~ 32之间的随机整数 rand
把随机数rand插入到数组arr内，如果数组arr内已存在与rand相同的数字，则重新生成随机数rand并插入arr内【使用递归实现，不能使用for/while循环】
最终输出一个长度为5，且内容不重复的数组arr

分析

获取min ~ max 范围内的随机数

Math.floor(Math.random() * (max - min + 1) + min)

思路

给定一个变量 i，初始值为 0，用来遍历初始化生成的空数组
当 i 小于数组长度，用 i 一直遍历数组并给arr[i]赋值生成的随机数，直到遍历完数组才返回arr的值
在第二步中，给arr[i]赋值时，如果数组中不存在生成的随机数，则给其赋值，并i++,否则循环调用该函数

答案

let arr = new Array(5)
let printArr = (arr, i = 0) => {
  let rand = Math.floor(Math.random() * 31 + 2)
  if (i < arr.length) {
    if (!arr.includes(rand)) {
      arr[i++] = rand
    }
    printArr(arr, i)
  }
  return arr
}

执行结果：

printArr(arr) // 调用
// 输出，每次执行输出结果都不一样
[27, 10, 26, 16, 2]

题目

统计给定字符串中出现次数最多的字符

要求：输出字符串中出现次数最多的字符和出现的次数

例如：

传入字符串 "aabbbgggg"

输出

{
    str: "g",
    num: 4
}

解析

遍历字符串，利用对象属性的唯一性，将每个字符作为对象的属性
用对象的属性值存储每个字符出现的次数
找出次数最大的字符并输出

答案

let maxStr = (str) => {
  let obj = {}
  for (let i in str) {
    let char = str[i]
    obj[char] = obj.hasOwnProperty(char) ? obj[char] + 1 : 1
  }
  let char = ''
  let num = 0
  for (let key in obj) {
    if (obj[key] > num) {
      char = key
      num = obj[key] 
    }
  }
  return {
    str: char,
    num: num
  }
}

执行结果：

maxStr('aabbbgggg') // 调用

// 输出
{ str: 'g', num: 4 }

题目

利用对象属性名的唯一性对数组去重

解析

遍历数组，将数组的值作为对象的属性名
同时判断对象中是否已经存在该属性，如果不存在，取出这个数存在目标数组
输出目标数组

答案

let uniqueArr = (arr) => {
  let obj = {}
  let newArr = []
  arr.forEach(item => {
    if (!obj.hasOwnProperty(item)) {
      obj[item] = item
      newArr.push(item)
    }
  })
  return newArr
}

执行结果：

let arr = [1, 2, 2, 'a', 'a']
uniqueArr(arr) // 调用

// 输出
[1, 2, "a"]

题目

输出数组中所有两个的数相加等于7的两个数

要求：以数组的形式返回

例如:

给一个数组如下：

let arr = [8, 4, 2, 5, 1, 3, 6, 9]

输出两个数之和为7的两个数：

[[4, 3], [2, 5], [1, 6]]

解析

遍历数组，利用indexOf方法查找，数组中有没有其他数与当前的数相加等7的值

以上面例子为例，要注意的一个点：

要避免重复查找，比如我们遍历到4时，可以找到目标数3，但当我们遍历到3时，应当注意从3往后找目标数，而非从数组的起始位置查找

indexOf 方法有两个参数：

第一个参数要查找的数组
第二个参数规定从数组的哪个位置开始查找【可选，默认从头开始】

答案

let targetArr = (arr, target) => {
    let newArr = []
    arr.forEach((item, index) => {
        let num = target - item
        let i = arr.indexOf(num, index)
        if (i > -1) {
            newArr.push([item, arr[i]])
        }
    })
    return newArr
}

let arr = [8, 4, 2, 5, 1, 3, 6, 9]
targetArr(arr, 7) // 调用

题目

输出前100个质数

注意不是100以内的质数，是前100个质数

解析

质数的概念

质数又称素数。指在一个大于1的自然数中,除了1和此整数自身外,没法被其他自然数整除的数

知道质数的概念后判断一个数是否是质数，可以通过判断这个数除了对1和其本身取余数为0外，不存在其他取余为0的数，那么这个数就是质数，否则就不是

思路

判断一个数是否是质数，可以通过判断这个数除了对1和其本身取余数为0外，不存在其他取余为0的数，那么这个数就是质数，否则就不是
当发现一个质数，添加到数组，进行下一轮的遍历，直到数组长度为100

答案

let primeNum = (len) => {
  let arr = []
  let num = 2
  while(len > 0) {
    let isPrimeNum = true
    for(let i = 2; i < num; i++) {
      if (num % i === 0) {
        isPrimeNum = false
      }
    }
    if (isPrimeNum) {
      arr.push(num)
      len--
    }
    num++
  }
  return arr
}

执行结果：

primeNum(100) // 调用

// 输出
 [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541]

题目

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素

例如，给定数组：

let arr = [1, 2, 3, 4, 4, 3, 2]

输出：

解析

根据给定数组的特性，只有一个数字是唯一的，其他数字都有两个

思路一

indexOf方法

从头遍历数组，返回要找的目标值的下标

lastIndexOf方法

从尾部遍历数组，返回要找的目标值的下标

利用 indexOf 和 lastIndexOf 方法来确定唯一的数，遍历数组，如果一个数重复出现两次，那么 indexOf 和 lastIndexOf返回的下标值不相同，如果相同，说明就是这个唯一的数

思路二

我们知道相同的数字异或运算结果为0
不为0的数字与0异或运算返回这个数字

利用异或运算的特性，可以找出数组的唯一值

答案

寻找下标的方法

let singleNumber = function(nums) {
    return nums.find(item => nums.indexOf(item) === nums.lastIndexOf(item))
}

执行结果：

singleNumber([1, 2, 3, 1, 2]) //调用
// 返回
3

异或运算方法

let singleNumber = function(nums) {
    return nums.reduce((total, num) => {
        return total ^ num
    })
}

执行结果：

singleNumber([1, 2, 3, 3, 4, 1, 2]) //调用
// 返回
4

题目

给定一组非负整数，重新排列它们的顺序使之组成一个最大的整数

例如给定数组：

[3,30,34,5,9]

输出：

"9534330"

注意：输出结果可能非常大，所以你需要返回一个字符串而不是整数

分析

我们首先知道组成这个数的最高位越大，这个数越大

我们先分析一个容易理解的解题思路：

遍历给定的数组，比较两个数的最高位，若最高位不相同，最高位较大的数在前
若最高位相同，则比较第二位数是否相同，若不相同，位数较大的数在前
若后面的位数还是相同，循环上面的步骤，直到找到不相同的位数，比较出两个数的前后顺序

由上面的分析，我们知道，此题的基本**还是比较两个数的先后顺序，它与比较两个数的大小顺序类似，我们可以理解为此题只是排序的规则不同

普通排序，我们只需要比较两个数的大小，而此题需要比较最高位数的大小，
比如 123 大于 4 但4的最高位大于123

基于上面的分析，对于此题我们可以这样比较两个数：
数字 a = 123, 数字 b = 4
将a和b 转字符串（使用 + '' 转字符串）
通过比较 a + b 和 b + a的大小，确定a和b的顺序
即”1234“ < ”4123“ 则 b(4) 在 a(123) 前面

最后注意一个边界：
输入：[0, 0, 0]
输出：”0“

答案

let largestNumber = function(nums) {
    let len = nums.length
    for (let i = 0; i < len; i++) {
        for (let j = 0; j < len; j++) {
            let left = nums[i] + '' + nums[j]
            let right = nums[j] + '' + nums[i]
            if (left > right) {
                let temp = nums[i]
                nums[i] = nums[j]
                nums[j] = temp
            }
        }
    }
    return nums.join('') > 0 ? nums.join('') : "0"
}

执行结果：

largestNumber([3, 30, 34, 5, 9]) // 调用
// 输出
"9534330"

largestNumber([0, 0]) // 调用
// 输出
"0"

题目

统计 1 ~ n 整数中出现 1 的次数

例如：
n为 10，则输出 2
n为11，则输出4
n为100, 则输出21

分析

我们先观察给出n的每个位数出现1的次数, 比如：
n = 100‘
个位数为1的数字：00 '1'， 01 '1'， 02 '1'，03 '1'，04 '1'，05 '1'，06 '1'，07 '1'，08 '1'，09 '1'，共10个
十位数为1的数字：0 '1' 0，0 '1' 1，0 '1' 2，0 '1' 3，0 '1' 4，0 '1' 5，0 '1' 6，0 '1' 7，0 '1' 8，0 '1' 9，共10个
百位数为1的数字：'1' 00，共1个
我们可以看到像11这样的数字，分别在个位数和十位数都被统计了一次，
所以最终，n为100时，出现的1的次数是 10 + 10 + 1 = 21次

通过上面的例子n = 100分析规律：

个位数为1的数，那么只看剩余的位数（百位和十位数）10，可以看出个位数为1的个数是从 00 到 10 - 1（10+ '1' 大于100, 所以是10 -1），共10个
十位数为1的数，那么只看剩余的位数（百位和个位数）10，可以看出十位数为1的个数是从 00 到 10 - 1（1 + '1' + 0 大于100, 所以是10 -1），共10个
百位数为1的数, 那么只看剩余的位数（十位和个位数）00，可以看出十位数为1的个数是只有 00，1个

我们再分析一个n = 111：

个位数为1的数，那么只看剩余的位数（百位和十位数）11，可以看出个位数为1的个数是从 00 到 11，共12个
十位数为1的数，那么只看剩余的位数（百位和个位数）11，可以看出十位数为1的个数是从 00 到 11，共12个
百位数为1数, 那么只看剩余的位数（十位和个位数）11，可以看出十位数为1的个数是 00 到 11，共12个
所以n = 111时，1出现的次数为12 + 12 + 12 = 36

我们再分析一个n = 127：

个位数为1的数，那么只看剩余的位数（百位和十位数）12，可以看出个位数为1的个数是从 00 到 12，共13个
十位数为1的数，那么只看剩余的位数（百位和个位数）17，可以看出十位数为1的个数是从 00 到 19（1 + '1' + 8, 1 + '1' + 9都小于127，所以是19），共20个
百位数为1数, 那么只看剩余的位数（十位和个位数）27，可以看出十位数为1的个数是 00 到 27，共28个
所以n = 127时，1出现的次数为13 + 20 + 28 = 61

判断给定的字符串是否是回文

题目

判断给定的字符串是否是回文

例如：

字符串 "上海自来水来自海上" 是回文
字符串 "abba" 是回文
字符串 "abca" 不是回文

解析

取头部和尾部的字符对比是否相同
取正数第二个和倒数第二个字符对比是否相同
取正数第三个和倒数第三个字符对比是否相同
重复上面的步骤直到取到最中间的数
上面步骤中只要存在一个不相同，那么这个字符串就不是回文

答案

let isBackStr = str => {
  let len = str.length
  let isTargetStr = true
  for(let i = 0; i < len; i++) {
    if(str[i] !== str[len - i - 1]) {
      isTargetStr = false
    }
  }
  return isTargetStr
}

执行结果：

isBackStr('上海自来水来自海上') // 调用
// 输出
true

isBackStr('abba') // 调用
// 输出
true

isBackStr('abca') // 调用
// 输出
false

my729 / algorithm Goto Github PK

algorithm's Introduction

前端算法

目录

algorithm's People

Contributors

Watchers

algorithm's Issues

题目

解析

思路

答案

尾递归的方法

非尾递归方法

题目

分析

获取min ~ max 范围内的随机数

思路

答案

题目

解析

答案

题目

解析

答案

题目

解析

答案

题目

解析

质数的概念

思路

答案

题目

解析

思路一

indexOf方法

lastIndexOf方法

思路二

答案

寻找下标的方法

异或运算方法

题目

分析

答案

题目

分析

题目

解析

答案

Recommend Projects

Recommend Topics

Recommend Org