web大前端复习——js常见算法题2

Q19 回文解码

现在有一个字符串，你要对这个字符串进行 n 次操作，每次操作给出两个数字：(p, l) 表示当前字符串中从下标为 p 的字符开始的长度为 l 的一个子串。你要将这个子串左右翻转后插在这个子串原来位置的正后方，求最后得到的字符串是什么。字符串的下标是从 0 开始的，你可以从样例中得到更多信息。输入描述:

每组测试用例仅包含一组数据，每组数据第一行为原字符串，长度不超过 10 ，仅包含大小写字符与数字。接下来会有一个数字 n 表示有 n 个操作，再接下来有 n 行，每行两个整数，表示每次操作的(p , l)。保证输入的操作一定合法，最后得到的字符串长度不超过 1000。

输出描述:

输出一个字符串代表最后得到的字符串。

输入例子:

0 2

1 3

输出例子:

abbaabb

function reversecion(input){

var arr = input.split('\n')

var str=arr[0],

num=arr[1]

for(var i=0;i<num;i++){

var arrtemp = arr[i+2]

var start=arrtemp.split(' ')

var startnum = + start[0]

var endnum = + start[1]

var temp=str.substr(startnum,endnum)

str=str.substr(0,startnum+endnum)+temp.split("").reverse().join("") +str.substr(startnum+endnum)

}

return str;

}

var input = "ab\n2\n0 2\n1 3"

console.log(reversecion(input)) //abbaabb

var input1= "abc\n2\n0 2\n1 2"

console.log(reversecion(input1)) //abbbbac

substring()

substr()

slice()

第一个参数代表开始位置,第二个参数代表结束位置的下一个位置,截取出来的字符串的长度为第二个参数与第一个参数之间的差;若参数值为负数,则将该值加上字符串长度后转为正值;若第一个参数等于大于第二个参数,则返回空字符串.

substring()

第一个参数代表开始位置,第二个参数代表结束位置的下一个位置;若参数值为负数,则将该值转为0;两个参数中,取较小值作为开始位置,截取出来的字符串的长度为较大值与较小值之间的差.

substr()

第一个参数代表开始位置,第二个参数代表截取的长度

Q20 你作为一名出道的歌手终于要出自己的第一份专辑了，你计划收录 n 首歌而且每首歌的长度都是 s 秒，每首歌必须完整地收录于一张 CD 当中。每张 CD 的容量长度都是 L 秒，而且你至少得保证同一张 CD 内相邻两首歌中间至少要隔 1 秒。为了辟邪，你决定任意一张 CD 内的歌数不能被 13 这个数字整除，那么请问你出这张专辑至少需要多少张 CD ?

输入描述:

每组测试用例仅包含一组数据，每组数据第一行为三个正整数 n, s, L。保证 n ≤ 100 , s ≤ L ≤ 10000

输出描述:

输出一个整数代表你至少需要的 CD 数量。

输入例子:

7 2 6

输出例子:

function getNum(n,s,l){

var maxPerCD = parseInt((l+1) / (s+1));

var num= 0;

if(maxPerCD>n){

if(n%13==0){

return 2

}else{

return 1

}

if(maxPerCD%13==0){

maxPerCD--;

}

if(n%maxPerCD==0){

return n/maxPerCD

}else{

if(n%maxPerCD%13==0&&(n%maxPerCD==maxPerCD-1)){ //如果余数可被13整除，并且余数等于每张CD最多歌数-1，

// 这时候余数不能单独一张CD，也不能再从其他CD挪一张，只能再加一张CD

return parseInt(n/maxPerCD)+2

}else{

return parseInt(n/maxPerCD)+1

}

console.log(getNum(7,2,6)) //4

console.log(getNum(28,30,400)) //3

Q21 从一个数组中找出与给定数字最接近的元素。例如，数组[1,23,24,14,31,45,11,18,54,47,75,99,65]，给定值70，输出75.

var arr = [1,23,24,14,31,45,11,18,54,47,75,99,65];

var n = 70;

function findNear(arr,n){

var returnNum,cha,temp;

for(var i=0;i<arr.length;i++){

temp = Math.abs(arr[i]-n)

if(!cha||cha>temp){

cha = temp

returnNum = arr[i]

}

return returnNum

}

console.log(findNear(arr,n))

Q22 倒序打印链表的值，列如

node = {

val:1,

next:{

val:2,

next:{

val:3,

next:{

val:4

}

输出 4 3 2 1

并且不能用web存储，比如不能使用临时变量 var temp = XXX

面试今日头条被问到了这个问题，当时没想上来。

var node = {

val:1,

next:{

val:2,

next:{

val:3,

next:{

val:4

}

function reverseFun(node){

if(!node){

return

}else{

reverseFun(node.next)

console.log(node.val)

}

reverseFun(node);

Q23 从一个有序数组中找出两个元素之和等于给定值得元素角标的集合，只能使用单次遍历，例如，从数组 [1,2,5,7,9,12,15,18]中找出两个和为19的元素的集合，输出[0,7] [3,5]。

var arr = [1,2,5,7,9,12,15,18]

var s= 19

function fun(arr,s){

var len = arr.length

var i=0,j=len-1

while(i<j){

if((arr[i]+arr[j])<s){

i++

}else if((arr[i]+arr[j])>s){

j--

}else{

var res = [i,j]

console.log(res)

i++

j--

}

fun(arr,s)

//[0, 7] [3, 5]

Q24 求二叉树中和值为n的路径

题目描述:

输入一颗二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。

思路

前序遍历二叉树，每次更新当前路径的和curtSum；

判断当前结点是否是叶子结点，以及curtSum是否等于expectNumber。如果是，把当前路径保存在res结果中；

若不符合条件，则弹出此结点。

实现代码

var tree = {

"val": 0,

"left": {

"val": 1,

"left": {

"val": 3,

"left": {

"val": 7,

"left": {

"val": 11,

}

"right": {

"val": 8,

"left": {

"val": 12,

}

"right": {

"val": 4,

"left": {

"val": 9,

}

"right": {

"val": 2,

"left": {

"val": 5,

"right": {

"val": 6,

"right": {

"val": 10,

}

function FindPath(root, expectNumber) {

var result = [];

if (root === null) {

return result;

}

dfsFind(root, expectNumber, [], 0, result);

return result;

}

function dfsFind(root, expectNumber, path, currentSum, result) {

currentSum += root.val;

path.push(root.val);

if (currentSum == expectNumber && root.left == null && root.right == null) {

result.push(path.slice(0));

}

if (root.left != null) {

dfsFind(root.left, expectNumber, path, currentSum, result);

}

if (root.right != null) {

dfsFind(root.right, expectNumber, path, currentSum, result);

}

path.pop();

}

console.log(FindPath(tree,18)) // [0, 2, 6, 10]

Q25 有一个数组和一个给定的值，从数组中选择任意数，可以重复选择，使其和为给定的值，求所需数最少的一组数。例如：数组[2,3,6,7] 常数7，[2,2,3] [7]两种组合的和值为7，所以需要数最少的组合是[7]。

var res = []

function combinationSum(candidates,target){

helper(candidates,target,[],0)

var minNum = res[0].length,temp=0

for(var i=1;i<res.length;i++){

if(res[i].length<minNum){

minNum= res[i].length

temp = i

}

console.log('所有符合条件的组合为：',res)

console.log('最小个数为：', minNum)

console.log('最小个数的组合为：', res[temp])

}

function helper(candidates,target,list,index){

if(target == 0){

res.push(list.slice())

}

for(var i=index;i<candidates.length;i++){

if(candidates[i] <= target){

list.push(candidates[i])

helper(candidates,target-candidates[i], list, i)

list.pop()

}

combinationSum([1,3,4],6)

Q26 合并两个降序排列的数组，使合并之后数组仍然降序排列，要求时间复杂度低。例如：[100,97,92,89,80,76] [96,93,88,72,71,66,55] 合并后为[100,97,96,93,92,89,88,80,76,72,71,66,55]

var arr1 = [100,97,94,88,84,80,79,77,73,68,65,62,57,55,52,49,46,44]

var arr2 = [96,93,90,89,85,78,74,69,63,59,57,56,52,48,46,33]

function mergeFun(arr1,arr2){

var i=0,j=0;

var res = []

while(i<arr1.length && j<arr2.length){

if(arr1[i] > arr2[j]){

res.push(arr1[i++])

}else if(arr1[i] == arr2[j]){

res.push(arr1[i++])

j++;

}else{

res.push(arr2[j++])

}

while(i<arr1.length){

res.push(arr1[i++])

}

while (j< arr2.length){

res.push(arr2[j++])

}

return res

}

console.log(mergeFun(arr1,arr2))

Q27 输出杨辉三角第m行n列的值，m、n从0开始。

我们很容易想到用递归的方法实现，如下：

function triangle1(m,n){

if(n==0||m==n){

return 1

}

return (triangle1(m-1,n)||0) + (triangle1(m-1,n-1)||0)

}

console.log(triangle1(6,3))

递归的方法在计算较小的数时没问题，但是计算较大的数时就容易超时。

下面用数组的方法实现一下：

function triangle(m,n){

var arr = [[1]]

for(var i=1;i<m;i++){

arr[i] = []

for(var j=0;j<=i;j++){

arr[i][j]= (arr[i-1][j-1] || 0) + (arr[i-1][j] || 0)

}

return arr

}

console.log(triangle(64,30))

Q28 给定一个整数数组 arr ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

例如，输入: [-2,1,-3,4,-1,2,1,-5,4],

输出: 6

解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

动态规划法——O(N)

设sum[i]为以第i个元素结尾且和最大的连续子数组。假设对于元素i，所有以它前面的元素结尾的子数组的长度都已经求得，那么以第i个元素结尾且和最大的连续子数组实际上，要么是以第i-1个元素结尾且和最大的连续子数组加上这个元素，要么是只包含第i个元素，即sum[i]

= max(sum[i-1] + a[i], a[i])。可以通过判断sum[i-1] + a[i]是否大于a[i]来做选择，而这实际上等价于判断sum[i-1]是否大于0。由于每次运算只需要前一次的结果，因此并不需要像普通的动态规划那样保留之前所有的计算结果，只需要保留上一次的即可，因此算法的时间和空间复杂度都很小

var arr = [2,4,-3,5,-1,3,-2,-6,-5,6]

function maxSubArray(arr){

var sum = arr[0],

n = arr[0]; //当前循环最大和值

for(var i=1;i<arr.length;i++){

if(n>0){

n += arr[i]

}else{

n = arr[i]

}

if(n>sum){

sum = n

}

return sum

}

console.log(maxSubArray(arr))

Q29 无重复字符的最长子串的长度

无重复字符的最长子串

给定一个字符串，找出不含有重复字符的最长子串的长度。

示例：

给定 "abcabcbbefdxvbnmkjtgfsd" ，没有重复字符的最长子串是"fdxvbnmkjtg"，那么长度就是12。

给定 "bbbbb" ，最长的子串就是 "b"，长度是1。

给定 "pwwkew"，最长子串是"wke"，长度是3。请注意答案必须是一个子串，"pwke"是子序列而不是子串。

思路分析：

对字符串进行遍历，使用String.prototype.indexOf()实时获取遍历过程中的无重复子串并存放于str，并保存当前状态最长无重复子串的长度为res，当遍历结束时，res的值即为无重复字符的最长子串的长度。

function longSubString(str){

var res =0,

currentStr = '',

len = str.length

for(var i=0;i<len;i++){

var char = str.charAt(i);

var index = currentStr.indexOf(char)

if(index==-1){

currentStr += char

res = res< currentStr.length? currentStr.length: res

}else{

currentStr = currentStr.substring(index+1) + char

}

return res

}

console.log(longSubString('abcabcbbefdxvbnmkjtgfsd'))

Q30 删除链表的倒数第N个节点

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。

示例：

给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后，链表变为 1->2->3->5.

说明：

给定的 n 保证是有效的。

进阶：

你能尝试使用一趟扫描实现吗？

思路:

这道题要用双指针来实现。先用first指针前进n，然后让second从head开始和first一起前进，直到first到了末尾，此时second的下一个节点就是要删除的节点。（另外，若first一开始前进n就已经不在链表中了，说明要删除的节点正是head节点，那么直接返回head的下一个节点接口。）

/**

* Definition for singly-linked list.

* function ListNode(val) {

* this.val = val;

* this.next = null;

* }

/**

* @param {ListNode} head

* @param {number} n

* @return {ListNode}

var removeNthFromEnd = function(head, n) {

let first = head, second = head;

while (n > 0) {

first = first.next

n--

}

if (!first) return head.next; // 删除的是头节点

while (first.next) {

first = first.next;

second = second.next;

}

second.next = second.next.next;

return head

}

Q31 写一个函数获取两个日期之间所有日期，放在对象里。

例如：getAllDate('2018/09/10','2019/03/04')

输出：

{

2018:{

9:[12,13,14,...30],

10:[...],

11:[...],

12:[...]

2019:{

1:[...],

2:[...],

3:[1,2,3]

}

function getAllDate(startDate,endDate){

let startTime = new Date(startDate),

endTime = new Date(endDate)

let arr = []

let dateObj = {}

while(startTime<endTime){

let year = startTime.getFullYear()

let month = startTime.getMonth()

let day = startTime.getDate()

arr.push(year +'/'+month +'/'+day)

startTime.setDate(startTime.getDate() +1)

}

for(let i=0;i<arr.length;i++){

let temp = arr[i].split('/')

let year = parseInt(temp[0]),

month = parseInt(temp[1]) +1,

day = parseInt(temp[2])

if(!dateObj[year]){

dateObj[year] = {}

}

if(!dateObj[year][month]){

dateObj[year][month] = []

}

dateObj[year][month].push(day)

}

return dateObj

}

console.log(getAllDate('2018/09/10','2019/03/04'))

Q32 给定一个字符串，形如：'a=12,b=23,c=k1,d=2s,k=$'，请写一个find方法，给定左侧值，找到右侧值，例如：find('a')，打印：‘12’。

var str = 'a=12,b=23,c=k1,d=2s,k=$'

function find(param){

var arr= str.split(',')

var obj={}

for(var i=0;i<arr.length;i++){

obj[arr[i].split('=')[0]] = arr[i].split('=')[1]

}

console.log(obj[param])

}

find('k')

Q33 给定一个字符串，找出无重复字母的最长子串。

这个题和29题类似

function func(str){

var subStr = ''

var arr = []

var maxLen = 0

var maxIndex=0

var subMaxStr = ''

for(var i=0;i<str.length;i++){

if(subStr.indexOf(str.charAt(i))===-1){

subStr+=str.charAt(i)

}else{

arr.push(subStr)

subStr = subStr.split(str.charAt(i))[1]+str.charAt(i)

}

maxLen = arr[0].length

subMaxStr = arr[0]

for(var j=1;j<arr.length;j++){

if(arr[j].length>maxLen){

maxLen = arr[j].length

maxIndex = j

subMaxStr = arr[j]

}

console.log(subMaxStr)

}

func('zxcvbngfdvfeeewdfrgthfqwertyuiokjhofd')

func('zxcvbngfeefd')

方法二

function getSubString(str){

let longSub = '',len=str.length,currentStr='',max=0

for(let i=0;i<len;i++){

let char = str.charAt(i)

if(currentStr.indexOf(char)==-1){

currentStr+=char

if(max<currentStr.length){

max = currentStr.length

longSub = currentStr

}

}else{

currentStr = currentStr.substring(currentStr.indexOf(char)+1)+char

}

return longSub

}

console.log(getSubString('zxcvbngfdvfeeewdfrgthfqwertyuiokjhofd'))

console.log(getSubString('zxcvbngfeefd'))

Q34 给一个obj，要求实现一个console.tree(obj)，在控制台以缩进的形式打印这个值的树状结构（不要打印原型链中的方法名称），例如：

var obj = {'x':1,'y':{'z':2,'b':4,'c':{'d':5}},'a':3}

打印：

console.__proto__.tree = function(json){

var i=0

var str = ''

var fun= function(json){

for(var key in json){

if(json.hasOwnProperty(key)){

if(typeof json[key] ==='object'){

str+='\t'.repeat(i)+ '|---'+key+'\n'

i++

fun(json[key])

i--

}else{

str+= '\t'.repeat(i)+ '|---'+key+':'+json[key] +'\n'

}

fun(json)

console.log(str)

}

var json = {'x':1,'y':{'z':2,'b':4,'c':{'d':5}},'a':3}

console.tree(json)

Q35 有一组不同高度的台阶，有一个整数数组表示，数组中每个数是台阶的高度，当开始下雨了（雨水足够多）台阶之间的水坑会积水多少呢？如下图，可以表示为数组[0,1,0,2,1,0,1,3,2,1,2,1]，返回积水量6。

方法一

先在这个数组中找到最大值，然后从左右两边遍历。以左边为例，只要当前的数字比下一个数字大，那么这个数字的右边就可以存水，按照这个思路去分析就可以了，右边的也是一样的道理。

代码如下：

let maxIndex=0,max = arr[0]

for(let i=1;i<arr.length;i++){

if(arr[i]>max){

max=arr[i]

maxIndex = i

}

let sum = 0,leftMax=arr[0],rightMax=arr[arr.length-1]

for(let i=1;i<maxIndex;i++){

if(arr[i]<leftMax){

sum += (leftMax-arr[i])

}else{

leftMax = arr[i]

}

for(let j = arr.length-1;j>maxIndex;j--){

if(arr[j]<rightMax){

sum += (rightMax - arr[j])

}else{

rightMax = arr[j]

}

console.log(sum)

方法二

这个原理和方法一一样，只需一次遍历，相对方法一略微难理解。

let leftM = arr[0],rightM = arr[arr.length-1],leftIndex = 0,rightIndex = arr.length-1,volumn=0

while (leftIndex < rightIndex) {

if(leftM < rightM){

leftIndex++

if(arr[leftIndex]>leftM){

leftM = arr[leftIndex]

}else{

volumn += (leftM-arr[leftIndex])

}

}else{

rightIndex--

if(arr[rightIndex]>rightM){

rightM = arr[rightIndex]

}else{

volumn += (rightM - arr[rightIndex])

}

console.log(volumn)

Q36 替换字符串中所有指定的子字符串。

例如：替换‘asssdfgghhjsssertyu’中‘sss’

方法一：

str.replace(/需要替换的字符串/g，"新字符串")

'asssdfgghhjsssertyu'.replace(/sss/g,'123')

这种形式要替换的字符串没法用参数，可以用

var str = 'asssdfgghhjsssertyu'

function replacer(str,str1,str2){

return str.replace(new RegExp(str1,'g'),str2)

}

console.log(replacer(str,'sss',12))

方法二

var str = 'asssdfgghhjsssertyu'

function replacer(str,str1,str2){

var arg = str.split(str1)

return arg.join(str2)

}

console.log(replacer(str,'sss',12))

Q 37 给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。

案例:

s = "leetcode"

返回 0.

s = "loveleetcode",

返回 2.

解法一：有点暴力，主要思路为抛出本身后，利用indexOf查询查找是否存在重复值，不存在则直接返回当前索引

/**

* @param {string} s

* @return {number}

var firstUniqChar = function(s) {

var len = s.length;

for(var i=0;i<len;i++){

var str = s,

test = str.split('');

test.splice(i,1);

var sub = test.indexOf(s[i]);

if(sub === -1) return i;

}

return -1;

};

方法二

　　方法一用到了indexOf ,所以时间复杂度也达到了O（n^2）,

　　则想到了利用哈希来存储重复的次数，在循环字符串查找哈希中值为1的这个字符，第一次遇到则返回，这样循环次数相对减少时间复杂度也降到了O（n）

/**

* @param {string} s

* @return {number}

var firstUniqChar = function(s) {

var len = s.length,

haxi = {};

for(var i=0;i<len;i++){

var sub = haxi[s[i]];

if(sub){

haxi[s[i]] = ++sub;

}else{

haxi[s[i]] = 1;

}

for(var i=0;i<len;i++){

if(haxi[s[i]] === 1) {

return i

}

return -1;

};

Q 38 实现一个函数 find(obj, str)，满足:

如

var obj = {a:{b:{c:1}}};

var obj2 = {d:{e:{f:2}}}

find(obj, 'a.b.c') //返回1

find(obj, 'a.d.c') //返回undefined

find(obj2, 'd') //返回{e:{f:2}}

find(obj2, 'd.e.f') //返回2

function find(obj,str){

var arrStr = str.split('.')

var newObj = obj

for(var i=0;i<arrStr.length;i++){

var temp = newObj[arrStr[i]]

if(temp){

newObj = temp

}else{

return undefined

}

return newObj

}

var obj = {a:{b:{c:1}}};

var obj2 = {d:{e:{f:2}}}

console.log(find(obj, 'a.b.c')) //返回1

console.log(find(obj, 'a.d.c')) //返回undefined

console.log(find(obj2, 'd')) //返回{e:{f:2}}

console.log(find(obj2, 'd.e.f')) //返回2

Q39 把数值转化为货币形式，并保留两位小数。

例如：输入1234567.891，输出1,234,567.89

function int2str (num){

let newNum = num.toFixed(2)

let arr = newNum.toString().split('.')

let strLeft = arr[0],strRight = arr[1]

let str = strLeft.split('').reverse()

for(let i=0;i<str.length;i++){

if((i+1)%4 === 0){

str.splice(i,0,',')

}

str.reverse()

let reg = str.join('') + '.' + strRight

return reg

}

console.log(int2str(1234567.891))

Q40 JS写一个方法，传入一个数组，返回该数组的层深(维度)

如：var arr = [1,[2,3,[4,[5,6,7]],11],[8]]

function fo(arr,len){

var flag = false

var arr1= []

for(var i=0;i<arr.length;i++){

if(!!arr[i].length){

for(var j=0;j<arr[i].length;j++){

arr1.push(arr[i][j])

}

flag = true

}

if(flag){

len++

return fo(arr1,len)

}else{

return len

}

var arr = [1,[2,3,[4,[5,6,7]],11],[8]]

console.log(fo(arr,1))

作者：指尖跳动

链接：https://www.jianshu.com/p/2f38ac50c63a

来源：简书

著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。