剑指offer胡解(一)

u=2466331554,2187977111&fm=26&gp=0

建完博客发现一时没啥写的,转载灌水也不合适,想起来在牛客网看到的《剑指offer66题》基本都是 c 跟 Java,写一份 JS 的好了。作为一个小白没啥性能追求,能写出来就行。todo是参看题解获得的思路,日后自己写一下。

也不知道啥时候能写完,66题就拆6篇写。

1.二维数组中的查找

题目描述

在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。

遍历每个一维数组,一维数组内用二分查找

todo

从左下 / 右上找:左下为该列最大该行最小

二维折半查找:二维数组分为上下左右四个边界 top, bottom, left, right, 对 top 折半,将二维数组位于终止点E右边的矩形Rr排除,终止点E小于其右边相邻的元素E+1,E+1是右边矩形Rr的最小元素(左上元素),上下左右依次

function Find(target, array) {
	// write code here
	function FindInline(array) {
		if (array[0] == target) {
			x = 0
			return true
		}
		if (array[w - 1] == target) {
			x = w
			return true
		}
		while (x != rx) {
			switch (true) {
				case array[x - 1] > target:
					rx = x
					x = Math.ceil((lx + rx) / 2)
					break
				case array[x - 1] < target:
					lx = x
					x = Math.ceil((lx + rx) / 2)
					break
				default:
					return true
			}
		}
		lx = 1
		rx = w
		x = Math.ceil((lx + rx) / 2)
		return false
	}
	let w = array[0].length
	let lx = 1
	let rx = w
	let x = Math.ceil((lx + rx) / 2)
	if (!array.length || !w) return false
	for (let i = 0; i < array.length; i++) {
		if (FindInline(array[i])) return true
  }
	return false
}

</>

2.替换空格

题目描述

请实现一个函数,将一个字符串中的每个空格替换成“%20”。例如,当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

差点就想用 .replace ,不行啊大兄弟,要自己实现一个

function replaceSpace(str) {
	// write code here
	let arr = str.split('')
	let k
	for (k in arr) {
		arr[k] == ' ' ? (arr[k] = '%20') : 0
	}
	return arr.join('')
}

3.翻转单词顺序列

题目描述

牛客最近来了一个新员工Fish,每天早晨总是会拿着一本英文杂志,写些句子在本子上。同事Cat对Fish写的内容颇感兴趣,有一天他向Fish借来翻看,但却读不懂它的意思。例如,“student. a am I”。后来才意识到,这家伙原来把句子单词的顺序翻转了,正确的句子应该是“I am a student.”。Cat对一一的翻转这些单词顺序可不在行,你能帮助他么?

JS 一句话解决(这样是拿不到 offer 的 = =,下次再改吧)

function ReverseSentence(str)
{
    // write code here
    return str
	.split(" ")
	.reverse()
	.join(" ")
}

4.左旋转字符串

题目描述

汇编语言中有一种移位指令叫做循环左移(ROL),现在有个简单的任务,就是用字符串模拟这个指令的运算结果。对于一个给定的字符序列S,请你把其循环左移K位后的序列输出。例如,字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果,即“XYZdefabc”。是不是很简单?OK,搞定它!

拆成数组 .shift.push 模拟即可

function LeftRotateString(str, n)
{
    // write code here
    if(!str) return ''
    let strA = str.split('')
	for (let i = 0; i < n; i++) {
		strA.push(strA.shift())
	}
	return strA.join('')
}

5.扑克牌顺子

题目描述

LL今天心情特别好,因为他去买了一副扑克牌,发现里面居然有2个大王,2个小王(一副牌原本是54张^_^)…他随机从中抽出了5张牌,想测测自己的手气,看看能不能抽到顺子,如果抽到的话,他决定去买体育彩票,嘿嘿!!“红心A,黑桃3,小王,大王,方片5”,“Oh My God!”不是顺子…..LL不高兴了,他想了想,决定大\小 王可以看成任何数字,并且A看作1,J为11,Q为12,K为13。上面的5张牌就可以变成“1,2,3,4,5”(大小王分别看作2和4),“So Lucky!”。LL决定去买体育彩票啦。 现在,要求你使用这幅牌模拟上面的过程,然后告诉我们LL的运气如何, 如果牌能组成顺子就输出true,否则就输出false。为了方便起见,你可以认为大小王是0。

排序后统计 Joker (0) 的个数并从数组剔除
依次确认差是否为1
不为1则使用 Joker 填补,差增加1,剩余 Joker 个数减1
但凡不满足条件则 flag = false

function IsContinuous(numbers) {
	// write code here
	if (!numbers.length) return false
	let flag = true
	let joker = 0
	let [...num] = numbers.sort()
	numbers.reduce(function(pv, cv) {
		if (cv == 0) {
			num.shift()
			joker++
		}
		return cv
	}, 0)
	num.reduce(function(pv, cv) {
		if (pv + 1 == cv) return cv
		let i = 1
		while (joker > 0) {
			joker--
			i++
			if (pv + i == cv) return cv
		}
		flag = false
		return cv
	})
	return flag
}

6.孩子们的游戏(圆圈中最后剩下的数)

题目描述

每年六一儿童节,牛客都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此。HF作为牛客的资深元老,自然也准备了一些小游戏。其中,有个游戏是这样的:首先,让小朋友们围成一个大圈。然后,他随机指定一个数m,让编号为0的小朋友开始报数。每次喊到m-1的那个小朋友要出列唱首歌,然后可以在礼品箱中任意的挑选礼物,并且不再回到圈中,从他的下一个小朋友开始,继续0…m-1报数….这样下去….直到剩下最后一个小朋友,可以不用表演,并且拿到牛客名贵的“名侦探柯南”典藏版(名额有限哦!!^_^)。请你试着想下,哪个小朋友会得到这份礼品呢?(注:小朋友的编号是从0到n-1)

如果没有小朋友,请返回-1

产生包含小朋友序号的数组
.splice 模拟出圈
使用 % 解决 m > n 的情况

function LastRemaining_Solution(n, m) {
	// write code here
	if (n == 0) return -1
	let arr = Array.from({ length: n }, (v, i) => i)
	let ctr = m - 1
	while (arr.length > 1) {
		ctr = ctr % arr.length
		arr.splice(ctr, 1)
		ctr += m - 1
	}
	return arr[0]
}

7.求1+2+3+…+n

题目描述

求1+2+3+…+n,要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句(A?B:C)。

实际 .reduce 也是用循环了,算投机吧

todo

看了下题解有用位运算符实现乘法的,实在是力所不能及

或者使用递归实现循环,用 && 短路或者 try{}catch{} 实现循环终止

function Sum_Solution(n) {
	// write code here
	let arr = Array.from({ length: n }, (v, i) => i + 1)
	return arr.reduce((pv, cv) => {
		return pv + cv
	})
}

8.不用加减乘除做加法

题目描述

写一个函数,求两个整数之和,要求在函数体内不得使用+、-、*、/四则运算符号。

使用数组长度记录数字绝对值,通过 .concat .splice 完成加减

++ -- 情况下相加即可,+— 需判断绝对值大小

PS: 0分做法,大数计算直接崩。

function Add(num1, num2) {
	// write code here
	num1 > num2 ? 0 : ([num1, num2] = [num2, num1])
	let flag1 = num1 >= 0
	let flag2 = num2 >= 0
	num1 = Math.abs(num1)
	num2 = Math.abs(num2)
	let l1 = new Array(num1).concat(new Array(num2)).length
	if (flag2) return l1
	if (flag1) {
		if (num1 > num2) return new Array(num1).splice(num2).length
		return -new Array(num2).splice(num1).length
	}
	return -l1
}

9.把字符串转换成整数

题目描述

将一个字符串转换成一个整数,要求不能使用字符串转换整数的库函数。 数值为0或者字符串不是一个合法的数值则返回0

拿不到 offer 做法+1,日后再改吧
n < -2147483648||n>2147483647 这个条件是 int 类型取值范围,出题人估计只考虑了强类型语言。
JS 没有这个限制

正经做应该 .split('') 拆分以后,每位乘10。

PS:看题解也是一大片的 int(s) 一步到位。。。

function StrToInt(str)
{
    // write code here
    if (!/^[+-]?\d+$/.test(str)) return 0
    let n = parseInt(str,10)
    if (n < -2147483648||n>2147483647) return 0
    return n
}

10.数组中重复的数字

题目描述

在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的,但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如,如果输入长度为7的数组{2,3,1,0,2,5,3},那么对应的输出是第一个重复的数字2。

用一个对象记录出现过的数字,或者用原数组记录

PS: 强行用了一下 in,直接 if(count[numbers[i]]) 就行(这个运算符存在感好低呀)

function duplicate(numbers, duplication) {
	// write code here
	//这里要特别注意~找到任意重复的一个值并赋值到duplication[0]
	//函数返回True/False
	let count = {}
	let n = numbers.length
	let index = 0
	for (i = 0; i < n; i++) {
		index = numbers[i]
		index > n ? (index -= n) : 0
		if (numbers[index] > n) {
			duplication[0] = index
			return true
		}
		numbers[index] += n
		// if (count[numbers[i]]) {
		// 	duplication[0] = numbers[i]
		// 	return true
		// }
		// count[numbers[i]] = 1
	}
	return false
}

11.构建乘积数组

题目描述

给定一个数组A[0,1,…,n-1],请构建一个数组B[0,1,…,n-1],其中B中的元素B[i]=A[0]A[1]…*A[i-1]A[i+1]…*A[n-1]。不能使用除法。

考虑到 i-1 不能小于0,题目应意为 B_i=\frac{\prod_{0}^{N-1}A_n}{A_i}

B_i=C_i\cdot{D_i}A_i 为界拆分为两个积

C_0=1 C_1=C_0\cdot{A_0}

D_{n-1}=1 D_{n-2}=D_{n-1}\cdot{A_{n-1}}

function multiply(array) {
	// write code here
	let al = array.length
	let arrB = []
	let arrC = [1]
	let arrD = []
	arrD[al - 1] = 1
	for (let i = 1; i < al; i++) {
		arrC[i] = arrC[i - 1] * array[i - 1]
		arrD[al - i - 1] = arrD[al - i] * array[al - i]
	}
	for (let i = 0; i < al; i++) {
		arrB[i] = arrC[i] * arrD[i]
	}
	return arrB
}

https://juejin.im/post/5e37e70df265da3dee22030a

「点点赞赏,手留余香」

    还没有人赞赏,快来当第一个赞赏的人吧!
0 条回复 A 作者 M 管理员
    所有的伟大,都源于一个勇敢的开始!
欢迎您,新朋友,感谢参与互动!欢迎您 {{author}},您在本站有{{commentsCount}}条评论