my729 / algorithm Goto Github PK
View Code? Open in Web Editor NEW收集算法题(主要是常见的前端面试算法),并写出题解和思路,重点在于记录自己思考的过程
收集算法题(主要是常见的前端面试算法),并写出题解和思路,重点在于记录自己思考的过程
数字反转
要求:不能转字符串和数组处理
输出前和输出后都是Number类型
比如12345 反转后为 54321
利用数学的整除和取余
数字对10取余可拿到个位数, 如下:
12345 % 10 === 5
数字对10整除并向下取整,可拿到一个除去个位数的整数, 如下:
Math.floor(12345 / 10) === 1234
文字描述有点抽象,我们拿一个数举例,如下:
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) // 调用
统计 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分析规律:
我们再分析一个n = 111:
我们再分析一个n = 127:
判断给定的字符串是否是回文
例如:
字符串 "上海自来水来自海上" 是回文
字符串 "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
输出数组中所有两个的数相加等于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的数,那么这个数就是质数,否则就不是
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]
输出:
1
根据给定数组的特性,只有一个数字是唯一的,其他数字都有两个
从头遍历数组,返回要找的目标值的下标
从尾部遍历数组,返回要找的目标值的下标
利用 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
这道题目将考点拆分成4点,要求用递归算法实现,限制15行代码以内,限制时间10分钟
Math.floor(Math.random() * (max - min + 1) + min)
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 }
给定一组非负整数,重新排列它们的顺序使之组成一个最大的整数
例如给定数组:
[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"
利用对象属性名的唯一性对数组去重
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"]
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.