社区微信群开通啦,扫一扫抢先加入社区官方微信群
社区微信群
剑指offer(点击此处)的题目在牛客网上可以看
题目描述:
在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
// 方式一(暴力循环):
// 解题思路:使用双重循环,外层表示当前第几行的数组,内层表示对每行的一维数组的遍历,直到找到需要查找的那个整数
function Find(target, array)
{
// write code here
var arrLen = array.length
var arrChildLen = array[0].length
for (let i = 0; i < arrLen; i++) {
for (let j = 0; j < arrChildLen; j++) {
if (array[i][j] === target) {
return true
}
}
}
return false
}
// 方式二:
// 解题思路:以二维数组的左下角这个值开始和需要查找的整数比较,比整数大则行下标减一,比整数小则列下标加一,直至找到退出
function Find(target, array)
{
// write code here
var arrLen = array.length
var arrChildLen = array[0].length
var rowIndex = arrLen - 1
var colIndex = 0
while (rowIndex >= 0 && colIndex <= arrChildLen - 1) {
if (array[rowIndex][colIndex] === target) {
return true
} else if (array[rowIndex][colIndex] > target) {
rowIndex -= 1
} else {
colIndex += 1
}
}
return false
}
题目描述:
请实现一个函数,将一个字符串中的每个空格替换成“%20”。例如,当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
方法一(正则):
function replaceSpace(str)
{
// write code here
var r = /s/g
// 或 var r = new RegExp('\s','g')
var newStr = str.replace(r, '%20')
return newStr
}
// 方法二: 数组和字符串转换
function replaceSpace(str)
{
// write code here
var arr = str.split(' ')
var newStr = arr.join('%20')
return newStr
}
题目描述:
输入一个链表,按链表从尾到头的顺序返回一个ArrayList。
/*function ListNode(x){
this.val = x;
this.next = null;
}*/
// 将链表的值从头到尾依次压入从前面压入数组
function printListFromTailToHead(head)
{
// write code here
var node = head
var arrList = []
while (node != null) {
arrList.unshift(node.val)
node = node.next
}
return arrList
}
题目描述:
输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回。
/* function TreeNode(x) {
this.val = x;
this.left = null;
this.right = null;
} */
// 递归方法实现
function reConstructBinaryTree(pre, vin)
{
// write code here
if (pre.length === 0 || vin.length === 0) {
return null
}
const index = vin.indexOf(pre[0])
const left = vin.slice(0, index)
const right = vin.slice(index + 1)
return {
val: pre[0],
left: reConstructBinaryTree(pre.slice(1, index + 1), left),
right: reConstructBinaryTree(pre.slice(index + 1), right)
}
}
题目描述:
用两个栈来实现一个队列,完成队列的Push和Pop操作。 队列中的元素为int类型。
// 第一个数组做入栈,第二个数组做出栈(第一个数组中的元素pop出的是最后入栈的,第二个数组在压入第一个pop出的,最后再pop的时候就是最开始压入第一个数组的元素)这样即实现了先入先出
function push(node)
{
// write code here
inStack.push(node)
}
function pop()
{
// write code here
if (outStack.length === 0) {
while (inStack.length) {
outStack.push(inStack.pop())
}
}
return outStack.pop()
}
var inStack = []
var outStack = []
题目描述:
把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。
输入一个非递减排序的数组的一个旋转,输出旋转数组的最小元素。
例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。
NOTE:给出的所有元素都大于0,若数组大小为0,请返回0。
// 方法一:
// 二分查找的思想找到最大和最小分界的地方
function minNumberInRotateArray(rotateArray)
{
// write code here
var left = 0
var right = rotateArray.length - 1
while (right - left > 1) {
var mid = Math.floor((left + right) / 2)
if (rotateArray[mid] > rotateArray[right]) {
left = mid
} else {
right = mid
}
}
return Math.min(rotateArray[left],rotateArray[right])
}
// 方法二:
// 不用算法思想,直接将数组排序,取出最小的数
function minNumberInRotateArray(rotateArray)
{
// write code here
return rotateArray.sort((a, b) => a - b)[0]
}
题目描述:
大家都知道斐波那契数列,现在要求输入一个整数n,请你输出斐波那契数列的第n项(从0开始,第0项为0)。
n<=39
// 使用动态规划的算法思想
function Fibonacci(n)
{
// write code here
let a = 0
let b = 1
while (n > 0) {
b += a
a = b - a
n--
}
return a
}
题目描述:
一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法(先后次序不同算不同的结果)。
// 斐波那契数列的变形
function jumpFloor(number)
{
// write code here
let a = 1
let b = 2
while (--number) {
b = a + b
a = b - a
}
return a
}
题目描述:
一只青蛙一次可以跳上1级台阶,也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
// 青蛙跳的变形
// 其中n级台阶为 a[n] = a[n-1] + a[n-2] + ... + a[1]
// a[n-1] = a[n-2] + ... + a[1]
// 则两式相减 a[n] = 2*a[n-1] 从而得知上n级台阶是n-1级跳法的2倍
function jumpFloorII(number)
{
// write code here
let i = 1
while (--number) {
i *= 2
}
return i
}
题目描述:
我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2*n的大矩形,总共有多少种方法?
// 斐波那契的变形
function rectCover(number)
{
// write code here
if (number === 0 ) return 0
let x = 1
let y = 2
while (--number) {
y += x
x = y - x
}
return x
}
题目描述:
输入一个整数,输出该数二进制表示中1的个数。其中负数用补码表示。
// 法一
// 二进制的数当自己与自己-1 相与,则会将最右边的1变为0,直到循环至最左边的1
function NumberOf1(n)
{
// write code here
let count = 0
while (n) {
n = n & n - 1
count++
}
return count
}
// 法二
// 使用32位二进制表示的1111 1111 1111 1111左移位并依次与传入的二进制数相与,直到相与之后为0,则表示1的个数
function NumberOf1(n)
{
// write code here
let count = 0
let flag = 1
while (flag) {
if (flag & n) count++
flag = flag << 1
}
return count
}
题目描述:
给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。
保证base和exponent不同时为0
// 法一:(估计面试的时候这样写就没了!)
function Power(base, exponent)
{
// write code here
return Math.pow(base, exponent)
}
// 法二:(快速幂求解)
function Power(base, exponent)
{
// write code here
let res = 1
let n
if (exponent > 0) {
n = exponent
} else if (exponent < 0) {
if (base === 0) return -1
n = -exponent
} else {
return 1
}
while (n) {
if (n & 1) {
res *= base
}
base *= base
n >>= 1
}
return exponent > 0 ? res : 1 / res
}
题目描述:
输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有的奇数位于数组的前半部分,所有的偶数位于数组的后半部分,并保证奇数和奇数,偶数和偶数之间的相对位置不变。
// 方法一:
// 定义奇偶两个数组以此判断并存入相应数组,最后将两个数组连接起来
function reOrderArray(array)
{
// write code here
var jiArr = []
var ouArr = []
for (let i = 0; i < array.length; i++) {
if (array[i] & 1) {
jiArr.push(array[i])
} else {
ouArr.push(array[i])
}
}
return jiArr.concat(ouArr)
}
// 方法二:
// 使用filter过滤
function reOrderArray(array)
{
// write code here
var jiArr = array.filter(x => x & 1)
var ouArr = array.filter(x => !(x & 1))
return jiArr.concat(ouArr)
}
题目描述:
输入一个链表,输出该链表中倒数第k个结点。
// 方法一:
// 将链表元素用unshift()存入数组,使后面的链表元素存在数组前面
/*function ListNode(x){
this.val = x;
this.next = null;
}*/
function FindKthToTail(head, k)
{
// write code here
var arr = []
var node = head
while (node) {
arr.unshift(node)
node = node.next
}
return arr[k-1]
}
// 方法二:
// 用两个指针来跑,两个指针中间相距k-1个节点,第一个指针先跑,跑到了第k个节点时,第二个指针则是第一个节点。这时候两个一起跑。当第一个跑到了最后一个节点时,这时候第二个指针则是倒数第k个节点。
/*function ListNode(x){
this.val = x;
this.next = null;
}*/
function FindKthToTail(head, k)
{
// write code here
let node1 = head,
node2 = head
while (k--) {
if (node1) {
node1 = node1.next
} else {
return null
}
}
while (node1) {
node1 = node1.next
node2 = node2.next
}
return node2
}
题目描述:
输入一个链表,反转链表后,输出新链表的表头。
// 方法一:
// unshift存入数组并改变链表指针反向,输出第一个值
/*function ListNode(x){
this.val = x;
this.next = null;
}*/
function ReverseList(pHead)
{
// write code here
var node = pHead,
arr = []
while (node) {
arr.unshift(node)
node = node.next
}
arr.forEach((el, index) => {
if (index !== arr.length - 1) {
el.next = arr[index + 1]
} else {
el.next = null
}
})
return arr[0]
}
// 方法二:
// 用三个指针pPre(指向前一个结点)、pCurrent(指向当前的结点,在代码中就是pHead)、pPnext(指向后一个结点)。将当前节点pHead的next指向前一个节点pPre,前一个节点pPre等于当前节点pHead,当前节点pHead等于下一个节点pNext(相当于将前后指针互换)
/*function ListNode(x){
this.val = x;
this.next = null;
}*/
function ReverseList(pHead)
{
// write code here
let pPre = null,
pNext = null
while (pHead) {
pNext = pHead.next
pHead.next = pPre
pPre = pHead
pHead = pNext
}
return pPre
}
题目描述:
输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则。
// 方法一:
// 还是使用数组的方法排序并连接链表指针
/*function ListNode(x){
this.val = x;
this.next = null;
}*/
function Merge(pHead1, pHead2)
{
// write code here
var arr = []
while (pHead1) {
arr.push(pHead1)
pHead1 = pHead1.next
}
while (pHead2) {
arr.push(pHead2)
pHead2 = pHead2.next
}
arr.sort((x, y) => x.val - y.val)
arr.forEach((node,index) => {
if (index !== arr.length - 1) {
node.next = arr[index + 1]
} else {
node.next = null
}
})
return arr[0]
}
// 方法二:
// 不断地比较他们的头结点,谁大将谁取出到新链表表头(也有两种:递归和非递归)
// 递归
/*function ListNode(x){
this.val = x;
this.next = null;
}*/
function Merge(pHead1, pHead2)
{
// write code here
let newHead = null
if (pHead1 === null) return pHead2
if (pHead2 === null) return pHead1
if (pHead1.val < pHead2.val) {
newHead = pHead1
newHead.next = Merge(pHead1.next, pHead2)
} else {
newHead = pHead2
newHead.next = Merge(pHead1, pHead2.next)
}
return newHead
}
// 非递归
/*function ListNode(x){
this.val = x;
this.next = null;
}*/
function Merge(pHead1, pHead2)
{
// write code here
let newHead = null
let newNode = null
if (pHead1 === null) return pHead2
if (pHead2 === null) return pHead1
while (pHead1 && pHead2) {
if (pHead1.val < pHead2.val) {
if (newNode) {
newHead.next = pHead1
newHead = newHead.next
} else {
newNode = newHead = pHead1
}
pHead1 = pHead1.next
} else {
if (newNode) {
newHead.next = pHead2
newHead = newHead.next
} else {
newNode = newHead = pHead2
}
pHead2 = pHead2.next
}
}
while (pHead1 !== null) {
newHead.next = pHead1
newHead = newHead.next
pHead1 = pHead1.next
}
while (pHead2 !== null) {
newHead.next = pHead2
newHead = newHead.next
pHead2 = pHead2.next
}
return newNode
}
题目描述:
输入两棵二叉树A,B,判断B是不是A的子结构。(ps:我们约定空树不是任意一个树的子结构)
/* function TreeNode(x) {
this.val = x;
this.left = null;
this.right = null;
} */
function HasSubtree(pRoot1, pRoot2)
{
// write code here
let result = false
if (!pRoot1 || !pRoot2) return false
if (pRoot1.val === pRoot2.val) result = tree1HasTree2(pRoot1, pRoot2)
if (!result) result = HasSubtree(pRoot1.left, pRoot2)
if (!result) result = HasSubtree(pRoot1.right, pRoot2)
return result
}
function tree1HasTree2(pRoot1, pRoot2) {
if (!pRoot2) return true
if (!pRoot1) return false
if (pRoot1.val === pRoot2.val) {
return tree1HasTree2(pRoot1.left, pRoot2.left) && tree1HasTree2(pRoot1.right, pRoot2.right)
}
return false
}
题目描述:
操作给定的二叉树,将其变换为源二叉树的镜像。
// 递归到叶子节点后逐层交换节点的值
/* function TreeNode(x) {
this.val = x;
this.left = null;
this.right = null;
} */
function Mirror(root)
{
// write code here
if (root !== null) {
Mirror(root.left)
Mirror(root.right)
} else {
return
}
[root.left, root.right] = [root.right, root.left]
return root
}
题目描述:
输入一个矩阵,按照从外向里以顺时针的顺序依次打印出每一个数字,例如,如果输入如下4 X 4矩阵: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.
// 模拟魔方逆时针解法。
// 例如
// 1 2 3
// 4 5 6
// 7 8 9
// 输出并删除第一行后,再进行一次逆时针旋转,就变成:
// 6 9
// 5 8
// 4 7
// 继续重复上述操作即可
(即定义一个翻转矩阵的函数再重复去掉第一行)
function printMatrix(matrix)
{
// write code here
var list = [...matrix.shift()]
while (matrix.length) {
matrix = rotateMatrix(matrix)
list = list.concat(matrix.shift())
}
return list
}
function rotateMatrix (matrix) {
if (!matrix[0]) {
return matrix
}
rowLen = matrix[0].length
colLen = matrix.length
let newMatrix = []
for (let i = rowLen - 1; i >= 0 ; i--) {
let newArr = []
for (let j = 0; j < colLen; j++) {
newArr.push(matrix[j][i])
}
newMatrix.push(newArr)
}
return newMatrix
}
// 方法二:
// 分解一下步骤是从左到右,从上到下,从右到左,从下到上。不过要注意下边界条件,也就是最后一圈构成不了一个完整的圈的一些条件。
// 需要思考从第一圈到第二圈的条件是什么或者说他们有什么共同的特征。我们注意4X4的矩阵,只有两圈,到从第一圈到第二圈,起点从(0,0)变为了(1,1),我们发现4>1*2,类似的对于一个5X5的矩阵而言,最后一圈只有一个数字,起点坐标为(2,2),满足5>2*2,同理对于6X6的矩阵也是类似。故可以得出循环的条件就是columns>startX*2并且rows>startY*2
function printMatrix(matrix) {
if (matrix === null) return null;
const rows = matrix.length,
cols = matrix[0].length;
let start = 0,
res = [];
while (rows > start * 2 && cols > start * 2) {
res = res.concat(printMatrixInCircle(matrix, rows, cols, start));
start++;
}
return res;
}
function printMatrixInCircle(matrix, rows, cols, start) {
const endX = cols - 1 - start,
endY = rows - 1 - start,
res = [];
for (let i = start; i <= endX; i++) {
res.push(matrix[start][i]);
}
for (let i = start + 1; i <= endY; i++) {
res.push(matrix[i][endX]);
}
for (let i = endX - 1; i >= start && endY > start; i--) {
res.push(matrix[endY][i]);
}
for (let i = endY - 1; i >= start + 1 && endX > start; i--) {
res.push(matrix[i][start]);
}
return res;
}
题目描述:
定义栈的数据结构,请在该类型中实现一个能够得到栈中所含最小元素的min函数(时间复杂度应为O(1))。
// 增加一个辅助栈,每次压入栈时,和辅助栈栈顶值比较,小则压入辅助栈当中,大则再次压入辅助栈栈顶的值。这样辅助栈的栈顶数据一直是数据栈中最小的值。
var stack = []
var minstack = []
function push(node)
{
// write code here
stack.unshift(node)
if (minstack.length === 0) {
minstack.unshift(node)
} else {
if (minstack[0] > stack[0]) {
minstack.unshift(node)
} else {
minstack.unshift(minstack[0])
}
}
}
function pop()
{
// write code here
stack.shift()
minstack.shift()
}
function top()
{
// write code here
return stack[0]
}
function min()
{
// write code here
return minstack[0]
}
题目描述:
输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序,序列4,5,3,2,1是该压栈序列对应的一个弹出序列,但4,3,5,1,2就不可能是该压栈序列的弹出序列。(注意:这两个序列的长度是相等的)
// 使用一个辅助栈,先将pushV中的值依次压入辅助栈,在压入后将压入的值比对popV中的值,若有则弹出此时压入的值,并继续比较popV中的下一个值在辅助栈中是否还有,有则继续弹出辅助栈,直到比对到最后,若辅助栈为空,则是该压栈序列的弹出序列,反之亦然
function IsPopOrder(pushV, popV)
{
// write code here
let stack = []
if (pushV.length === 0) return false
for (let i = 0, j = 0; i < pushV.length; i++) {
stack.push(pushV[i])
while (j < popV.length && stack[stack.length - 1] === popV[j]) {
stack.pop()
j++
}
}
if (stack.length === 0) {
return true
} else {
return false
}
}
题目描述:
从上往下打印出二叉树的每个节点,同层节点从左至右打印。
// 二叉树的层序遍历,使用队列来帮助实现
/* function TreeNode(x) {
this.val = x;
this.left = null;
this.right = null;
} */
function PrintFromTopToBottom(root)
{
// write code here
var queue = []
var result = []
if (root === null) {
return result
}
queue.unshift(root)
while (queue.length) {
const pRoot = queue.pop()
if (pRoot.left !== null) {
queue.unshift(pRoot.left)
}
if (pRoot.right !== null) {
queue.unshift(pRoot.right)
}
result.push(pRoot.val)
}
return result
}
题目描述:
输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
// 二叉搜索树:左子节点小于父节点,右子节点大于父节点
// 方法一:递归实现,判断数组最右边的值(即父节点)是否大于左子树,小于又子树
function VerifySquenceOfBST(sequence)
{
// write code here
if (sequence.length === 0) return false
return judgeBitTree(sequence, 0, sequence.length - 1)
}
function judgeBitTree (arr, left, right) {
if (left > right) return true
let i = right
while (arr[i - 1] > arr[right] && i > left) {
i--
}
for (let j = i - 1; j >= left; j--) {
if (arr[j] > arr[right]) {
return false
}
}
return judgeBitTree(arr, left + 1, right) && judgeBitTree(arr, left, right - 1)
}
// 方法二: 非递归实现,思路和递归差不多,定义了i从头开始和最后一个值比较,如果中间的值不对,则i最终比maxIndex小。
function VerifySquenceOfBST(sequence)
{
// write code here
let maxIndex = sequence.length
if (maxIndex === 0) return false
while (maxIndex--) {
let i = 0
while (sequence[i] < sequence[maxIndex]) i++
while (sequence[i] > sequence[maxIndex]) i++
if (i < maxIndex) return false
}
return true
}
题目描述:
输入一颗二叉树的根节点和一个整数,打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中,数组长度大的数组靠前)
// 深度优先遍历思想,将沿途的值相加若等于传入的整数,则此条路通,放入listAll
/* function TreeNode(x) {
this.val = x;
this.left = null;
this.right = null;
} */
function FindPath(root, expectNumber)
{
// write code here
let list = []
let listAll = []
return dfs(root, expectNumber, list, listAll)
}
function dfs (root, expectNumber, list, listAll) {
if (root === null) return listAll
list.push(root.val)
expectNumber -= root.val
if (expectNumber === 0 && root.left === null && root.right === null) {
listAll.push(Array.of(...list))
}
dfs(root.left, expectNumber, list ,listAll)
dfs(root.right, expectNumber, list ,listAll)
list.pop()
return listAll
}
题目描述:
输入一个复杂链表(每个节点中有节点值,以及两个指针,一个指向下一个节点,另一个特殊指针指向任意一个节点),返回结果为复制后复杂链表的head。(注意,输出结果中请不要返回参数中的节点引用,否则判题程序会直接返回空)
// 用map来保存<N,N`>,这样就很容易设置p.random了,比如我们在节点S处和节点S`处,我们通过S可以得到N,那么<N,N`>对应,就可以就可以使得S`的next指向N`了。这是通过空间换时间
function RandomListNode(x){
this.label = x;
this.next = null;
this.random = null;
}
function Clone(pHead)
{
// write code here
if (pHead === null) return null
const map = new Map()
var p1 = pHead
var p2 = new RandomListNode(pHead.label)
var pHead2 = p2
while (p1) {
if (p1.next) p2.next = new RandomListNode(p1.next.label)
else p2.next = null
if (p1.random) p2.random = new RandomListNode(p1.random.label)
else p2.random = null
p1 = p1.next
p2 = p2.next
}
return pHead2
}
题目描述:
输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向。
// 方法一:(非递归)
// 核心是中序遍历的非递归算法。
// 修改当前遍历节点与前一遍历节点的指针指向。
/* function TreeNode(x) {
this.val = x;
this.left = null;
this.right = null;
} */
function Convert(pRootOfTree)
{
// write code here
if (!pRootOfTree) return null
let stack = [],
p = pRootOfTree,
pre = null,
isFirst = true
while (p || stack.length) {
while (p) {
stack.push(p)
p = p.left
}
p = stack.pop()
if (isFirst) {
pRootOfTree = p
pre = pRootOfTree
isFirst = false
} else {
pre.right = p
p.left = pre
pre = p
}
p = p.right
}
return pRootOfTree
}
// 方法二:(递归)
// 先对左子数调整为双向链表,并用变量pLast指向最后一个节点
// 再将中间节点和pLast连起来
// 再去调整右子树
/* function TreeNode(x) {
this.val = x;
this.left = null;
this.right = null;
} */
function Convert(pRootOfTree)
{
// write code here
if (!pRootOfTree) return null
let pLast = null
pLast = convertNode(pRootOfTree, pLast)
let pHead = pLast
while (pHead && pHead.left) {
pHead = pHead.left
}
return pHead
}
function convertNode (pNode, pLast) {
if (!pNode) return
if (pNode.left) {
pLast = convertNode(pNode.left, pLast)
}
pNode.left = pLast
if (pLast) {
pLast.right = pNode
}
pLast = pNode
if (pNode.right) {
pLast = convertNode(pNode.right, pLast)
}
return pLast
}
题目描述:
输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
输入描述:
输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。
// 方法一:(递归)
// 把字符串分为两部分:第一部分为第一个字符,第二部分为第一个字符以后的字符串。
// 然后接下来求后面那部分的全排列。
// 再将第一个字符与后面的那部分字符逐个交换
function Permutation(str) {
let res = [];
if (str.length <= 0) return res;
arr = str.split(''); // 将字符串转化为字符数组
res = permutate(arr, 0, res);
res = [...new Set(res)]; // 去重
res.sort(); // 排序
return res;
}
function permutate(arr, index, res) {
if (arr.length === index) {
let s = '';
for (let i = 0; i < arr.length; i++) {
s += arr[i];
}
return res.push(s);
}
for (let i = index; i < arr.length; i++) {
[arr[index], arr[i]] = [arr[i], arr[index]]; // 交换
permutate(arr, index + 1, res);
[arr[index], arr[i]] = [arr[i], arr[index]]; // 交换
}
return res;
}
// 方法二:回溯法
//利用树去尝试不同的可能性,不断地去字符串数组里面拿一个字符出来拼接字符串,当字符串数组被拿空时,就把结果添加进结果数组里,然后回溯上一层。(通过往数组加回去字符以及拼接的字符串减少一个来回溯。)
function Permutation(str) {
let res = [];
const pStr = '';
if (str.length <= 0) return res;
arr = str.split(''); // 将字符串转化为字符数组
res = permutate(arr, pStr, res);
return res;
}
function permutate(arr, pStr, res) {
if (arr.length === 0) {
return res.push(pStr);
}
const isRepeated = new Set();
for (let i = 0; i < arr.length; i++) {
if (!isRepeated.has(arr[i])) {
// 避免相同的字符交换
const char = arr.splice(i, 1)[0];
pStr += char;
permutate(arr, pStr, res);
arr.splice(i, 0, char); // 恢复字符串,回溯
pStr = pStr.slice(0, pStr.length - 1); // 回溯
isRepeated.add(char);
}
}
return res;
}
// 方法3:用字符串的每个字符插入字符串的前中后里
function Permutation(str) {
if (str.length === 0) return []
var arr = [str[0]]
for (let j = 1; j < str.length; j++) {
arr = fp(arr, str[j])
}
return [...new Set(arr)].sort()
}
function fp (arr, ch) {
var tmp = []
for (let i = 0; i <= arr[0].length; i++) {
tmp = tmp.concat(arr.map(x => x.slice(0, i) + ch + x.slice(i)))
}
return [...new Set(tmp)]
}
题目描述:
数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次,超过数组长度的一半,因此输出2。如果不存在则输出0。
// 准备一个辅助数组等于传入的数组,将传入数组的每个值在辅助数组中查找,查找到则次数+1,直到其出现的次数大于数组的一半时,则返回此值
function MoreThanHalfNum_Solution(numbers)
{
// write code here
let arr = [...numbers]
for (let i = 0; i < numbers.length; i++) {
let count = 0
for (let j = 0; j < arr.length; j++) {
if (arr.indexOf(numbers[i]) !== -1) {
arr.splice(arr.indexOf(numbers[i]), 1)
count++
}
}
arr = [...numbers]
if (count > Math.floor(numbers.length / 2)) {
return numbers[i]
}
}
return 0
}
题目描述:
输入n个整数,找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字,则最小的4个数字是1,2,3,4,。
// 方法一:
// 非算法题思想--!
function GetLeastNumbers_Solution(input, k)
{
// write code here
if (k > input.length) return []
return input.sort((a, b) => a - b).splice(0, k)
}
// 方法二:
// 基于partition快排的思想来查找第k大的数
function GetLeastNumbers_Solution(input, k) {
if (input.length === 0 || k > input.length || k < 1) return [];
const left = 0,
right = input.length - 1;
let key = partition(input, left, right);
while (key !== k - 1) {
if (key > k - 1) {
key = partition(input, left, key - 1);
} else {
key = partition(input, key + 1, right);
}
}
const res = input.slice(0, key + 1);
res.sort((a, b) => a - b);
return res;
}
function partition(a, left, right) {
const key = a[left]; // 一开始让key为第一个数
while (left < right) {
// 扫描一遍
while (key <= a[right] && left < right) {
// 如果key小于a[right],则right递减,继续比较
right--;
}
[a[left], a[right]] = [a[right], a[left]]; // 交换
while (key >= a[left] && left < right) {
// 如果key大于a[left],则left递增,继续比较
left++;
}
[a[left], a[right]] = [a[right], a[left]]; // 交换
}
return left; // 把key现在所在的下标返回
}
题目描述:
HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢?例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。给一个数组,返回它的最大连续子序列的和,你会不会被他忽悠住?(子向量的长度至少是1)
动态规划思路
F(i):以array[i]为末尾元素的子数组的和的最大值,子数组的元素的相对位置不变
F(i)=max(F(i-1)+array[i] , array[i])
res:所有子数组的和的最大值
res=max(res,F(i))
如数组[6, -3, -2, 7, -15, 1, 2, 2]
初始状态:
F(0)=6
res=6
i=1:
F(1)=max(F(0)-3,-3)=max(6-3,3)=3
res=max(F(1),res)=max(3,6)=6
i=2:
F(2)=max(F(1)-2,-2)=max(3-2,-2)=1
res=max(F(2),res)=max(1,6)=6
i=3:
F(3)=max(F(2)+7,7)=max(1+7,7)=8
res=max(F(2),res)=max(8,6)=8
i=4:
F(4)=max(F(3)-15,-15)=max(8-15,-15)=-7
res=max(F(4),res)=max(-7,8)=8
以此类推
最终res的值为8
// (动态规划解法)
// 解析如上(两种写法)
// 写法1
function FindGreatestSumOfSubArray(array)
{
// write code here
let res = array[0],
max = array[0]
for (let i = 1; i < array.length; i++) {
max = Math.max(max + array[i], array[i])
res = Math.max(max, res)
}
return res
}
// 写法2
function FindGreatestSumOfSubArray(array)
{
// write code here
if (array.length === 0) return 0
else {
let res = array[0],
max = array[0]
for (let i = 1; i < array.length; i++) {
if (max <= 0) {
max = array[i]
} else {
max += array[i]
}
if (res < max) {
res = max
}
}
return res
}
}
题目描述:
求出113的整数中1出现的次数,并算出1001300的整数中1出现的次数?为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数(从1 到 n 中1出现的次数)。
// 方法一: (正则匹配)
function NumberOf1Between1AndN_Solution(n)
{
// write code here
if (n < 1) return 0
let str = ''
for (let i = 1; i <= n; i++) {
str += String(i)
}
let arrNum = str.match(/(1)/g)
return arrNum.length
}
// 方法二:
// 暴力解法,也就是逐个判断
function NumberOf1Between1AndN_Solution(n){
let ones = 0
for (let i = 0;i <= n; i++) {
let num = i
while (num) {
if (num %10 === 1) {
ones++
}
num = ~~(num / 10)
}
}
return ones
}
// 方法三主要思路:设定整数点(如1、10、100等等)作为位置点i(对应n的各位、十位、百位等等),分别对每个数位上有多少包含1的点进行分析
// 根据设定的整数位置,对n进行分割,分为两部分,高位n/i,低位n%i
// 当i表示百位,且百位对应的数>=2,如n=31456,i=100,则a=314,b=56,此时百位为1的次数有a/10+1=32(最高两位0~31),每一次都包含100个连续的点,即共有(a%10+1)100个点的百位为1
// 当i表示百位,且百位对应的数为1,如n=31156,i=100,则a=311,b=56,此时百位对应的就是1,则共有a%10(最高两位0-30)次是包含100个连续点,当最高两位为31(即a=311),本次只对应局部点00~56,共b+1次,所有点加起来共有(a%10100)+(b+1),这些点百位对应为1
// 当i表示百位,且百位对应的数为0,如n=31056,i=100,则a=310,b=56,此时百位为1的次数有a/10=31(最高两位0~30)
// 综合以上三种情况,当百位对应0或>=2时,有(a+8)/10次包含所有100个点,还有当百位为1(a%101),需要增加局部点b+1
// 之所以补8,是因为当百位为0,则a/10(a+8)/10,当百位>=2,补8会产生进位位,效果等同于(a/10+1)
// 方法三:
// 运用了根据位数来做,逐位求解,并且对于特殊情况做下判断。
// 主要注意下每位0,1,>2三种情况。并且通过+8处理可以很好地把>2情况归在一起。
function NumberOf1Between1AndN_Solution(n){
if(n <=0 ) return 0
let count = 0
for (let i = 1; i <= n; i *= 10) {
let a = ~~(n / i),b = n % i
count = count + ~~((a + 8) / 10) * i + (a % 10 === 1) * (b + 1)
}
return count
}
题目描述:
输入一个正整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。例如输入数组{3,32,321},则打印出这三个数字能排成的最小数字为321323。
// 比较数组每个元素的字典序
function PrintMinNumber(numbers)
{
// write code here
if (numbers.length === 0) return ''
numbers.sort((a, b) => {
let s1 = String(a) + String(b)
let s2 = String(b) + String(a)
return s1 - s2
})
return numbers.join('')
}
题目描述:
把只包含质因子2、3和5的数称作丑数(Ugly Number)。例如6、8都是丑数,但14不是,因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
// 动态规划思想
function GetUglyNumber_Solution(index)
{
// write code here
if (index < 7) return index
let t1 = 0,
t2 = 0,
t3 = 0
let res = []
res[0] = 1
for (let i = 1; i < index; i++) {
res[i] = Math.min(res[t1] * 2, Math.min(res[t2] * 3, res[t3] * 5))
if (res[i] === res[t1] * 2) t1++
if (res[i] === res[t2] * 3) t2++
if (res[i] === res[t3] * 5) t3++
}
return res[index - 1]
}
// 牛客网运行超时(暴力循环)
function GetUglyNumber_Solution(index) {
if (index <= 1) return 0;
let count = 0;
let num = 0;
while (count < index) {
num++;
if (isUgly(num)) {
count++;
}
}
return num;
}
function isUgly(num) {
while (num % 2 === 0) num /= 2;
while (num % 3 === 0) num /= 3;
while (num % 5 === 0) num /= 5;
return num === 1;
}
题目描述:
在一个字符串(0<=字符串长度<=10000,全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1(需要区分大小写).
// 方法一:
// 正则匹配比较个数
function FirstNotRepeatingChar(str)
{
// write code here
for (let i = 0; i < str.length; i++) {
let r = `/${str[i]}/g`
let arr = str.match(eval(r))
if (arr.length === 1) {
return i
}
}
return -1
}
// 方法二:
// 用Map()的结构来实现每个字符串对应的个数(用对象也可以)
function FirstNotRepeatingChar(str)
{
// write code here
let map = new Map()
for (let i = 0; i < str.length; i++) {
if (map.get(str[i]) === undefined) {
map.set(str[i], 1)
} else {
let count = map.get(str[i])
map.set(str[i], ++count)
}
}
for (let i = 0; i < str.length; i++) {
if (map.get(str[i]) === 1) {
return i
}
}
return -1
}
题目描述:
在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007
输入描述: 题目保证输入的数组中没有的相同的数字
数据范围:
对于%50的数据,size<=10^4
对于%75的数据,size<=10^5
对于%100的数据,size<=2*10^5
示例1
输入1,2,3,4,5,6,7,0
输出7
// 第一反应是没思路,然后想到采用暴力解法,不过肯定会超时,所以我们需要用时间复杂度更低的解法.
// 说实话这道题有点难,我也是参考別人的。那么难点在哪呢?
// 难点一:要想到基于归并排序去解决。
// 难点二:参数的问题,这里很巧妙地用了一个copy数组作为data参数。
// 难点三:合并时,count如何计数。
// 不过只要注意这些小细节,多花点时间想明白还是能做出来的.
function InversePairs(data) {
if (!data || data.length < 2) return 0;
const copy = data.slice();
let count = 0;
count = mergeCount(data, copy, 0, data.length - 1);
return count % 1000000007;
}
function mergeCount(data, copy, start, end) {
if (start === end) return 0;
const mid = end - start >> 1,
left = mergeCount(copy, data, start, start + mid), // 注意参数,copy作为data传入
right = mergeCount(copy, data, start + mid + 1, end); // 注意参数,copy作为data传入
let [p, q, count, copyIndex] = [start + mid, end, 0, end];
while (p >= start && q >= start + mid + 1) {
if (data[p] > data[q]) {
copy[copyIndex--] = data[p--];
count = count + q - start - mid;
} else {
copy[copyIndex--] = data[q--];
}
}
while (p >= start) {
copy[copyIndex--] = data[p--];
}
while (q >= start + mid + 1) {
copy[copyIndex--] = data[q--];
}
return count + left + right;
}
题目描述:
输入两个链表,找出它们的第一个公共结点。
// 用两个指针扫描”两个链表“,最终两个指针到达 null 或者到达公共结点。
/*function ListNode(x){
this.val = x;
this.next = null;
}*/
function FindFirstCommonNode(pHead1, pHead2)
{
// write code here
let p1 = pHead1
let p2 = pHead2
while (p1 !== p2) {
p1 = (p1 === null ? pHead2 : p1.next)
p2 = (p2 === null ? pHead1 : p2.next)
}
return p1
}
题目描述:
统计一个数字在排序数组中出现的次数。
// 方法一:(循环依次判断个数)
function GetNumberOfK(data, k)
{
// write code here
let count = 0
for (let i = 0; i < data.length; i++) {
if (data[i] === k) {
count++
}
if (data[i] > k) break
}
return count
}
// 方法二:(二分查找法)
function GetNumberOfK(data, k) {
if (getEnd(data, k) === -1 && getBegin(data, k) === -1) return 0;
return getEnd(data, k) - getBegin(data, k) + 1;
}
function getBegin(data, k) {
let [left, right] = [0, data.length - 1];
let mid = left + right >> 1;
while (left <= right) {
if (data[mid] > k) {
right = mid - 1;
} else if (data[mid] < k) {
left = mid + 1;
} else if (mid - 1 >= 0 && data[mid - 1] === k) {
right = mid - 1;
} else return mid;
mid = left + right >> 1;
}
return -1;
}
function getEnd(data, k) {
let [left, right] = [0, data.length - 1];
let mid = left + right >> 1;
while (left <= right) {
if (data[mid] > k) {
right = mid - 1;
} else if (data[mid] < k) {
left = mid + 1;
} else if (mid + 1 < data.length && data[mid + 1] === k) {
left = mid + 1;
} else return mid;
mid = left + right >> 1;
}
return -1;
}
题目描述:
输入一棵二叉树,求该树的深度。从根结点到叶结点依次经过的结点(含根、叶结点)形成树的一条路径,最长路径的长度为树的深度。
// 方法一:
// 递归实现(层序遍历)
/* function TreeNode(x) {
this.val = x;
this.left = null;
this.right = null;
} */
function TreeDepth(pRoot)
{
// write code here
if (pRoot === null) return 0
let leftDeep = TreeDepth(pRoot.left) + 1
let rightDeep = TreeDepth(pRoot.right) + 1
return Math.max(leftDeep, rightDeep)
}
// 方法二:
// 队列实现
/* function TreeNode(x) {
this.val = x;
this.left = null;
this.right = null;
} */
function TreeDepth(pRoot)
{
// write code here
if (pRoot === null) return 0
let deep = 0,
queue = []
queue.unshift(pRoot)
let count = 0,
nextCount = 1
while(queue.length) {
let top = queue.pop()
count++
if (top.left) {
queue.unshift(top.left)
}
if (top.right) {
queue.unshift(top.right)
}
if (count === nextCount) {
nextCount = queue.length
count = 0
deep++
}
}
return deep
}
题目描述:
输入一棵二叉树,判断该二叉树是否是平衡二叉树。
// 结合二叉树深度的递归来判断是否为平衡二叉树
// 平衡二叉树:是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树
/* function TreeNode(x) {
this.val = x;
this.left = null;
this.right = null;
} */
function IsBalanced_Solution(pRoot)
{
// write code here
if (!pRoot) return true
let leftDeep = treeDeep(pRoot.left)
let rightDeep = treeDeep(pRoot.right)
return Math.abs(leftDeep - rightDeep) <= 1 && IsBalanced_Solution(pRoot.left) && IsBalanced_Solution(pRoot.right)
}
function treeDeep (pRoot) {
if (!pRoot) return 0
let leftTree = treeDeep(pRoot.left)
let rightTree = treeDeep(pRoot.right)
return Math.max(leftTree, rightTree) + 1
}
// 但是这种做法有很明显的问题,在判断上层结点的时候,会多次重复遍历下层结点,增加了不必要的开销。如果改为从下往上遍历,如果子树是平衡二叉树,则返回子树的高度;如果发现子树不是平衡二叉树,则直接停止遍历,这样至多只对每个结点访问一次。
function IsBalanced_Solution(pRoot) {
return treeDeep(pRoot) !== -1;
}
function treeDeep(pRoot) {
if (pRoot === null) return 0;
const leftLen = treeDeep(pRoot.left);
if (leftLen === -1) return -1;
const rightLen = treeDeep(pRoot.right);
if (rightLen === -1) return -1;
return Math.abs(leftLen - rightLen) > 1 ? -1 : Math.max(leftLen, rightLen) + 1;
}
题目描述:
一个整型数组里除了两个数字之外,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
// 方法一:(暴力循环)
// 循环将需要查找的数字从原数组中删除,然后在查找是否含有相同值,没有则只有一次
function FindNumsAppearOnce(array)
{
// write code here
if (!array.length) return null
let arr = []
for (let i = 0; i < array.length; i++) {
let newA = [...array]
newA.splice(i,1)
if (newA.indexOf(array[i]) === -1) {
arr.push(array[i])
}
}
return arr
// return list, 比如[a,b],其中ab是出现一次的两个数字
}
// 更简洁的写法 (用indexOf和lastIndexOf判断是否相等得到)
function FindNumsAppearOnce(array)
{
// write code here
if (!array.length) return null
let arr = []
for (let i = 0; i < array.length; i++) {
if (array.indexOf(array[i]) === array.lastIndexOf(array[i])) {
arr.push(array[i])
}
}
return arr
// return list, 比如[a,b],其中ab是出现一次的两个数字
}
// 方法二:
// 思路和第34题方法二相同,这次我使用对象来实现数组中每个值对应的个数
function FindNumsAppearOnce(array)
{
// write code here
if (!array.length) return null
let arrObj = {}
let list = []
let len = array.length
for (let i = 0; i < len; i++) {
if (!arrObj[array[i]]) {
arrObj[array[i]] = 1
} else {
arrObj[array[i]]++
}
}
for (let i = 0; i < len; i++) {
if (arrObj[array[i]] === 1) {
list.push(array[i])
}
}
return list
// return list, 比如[a,b],其中ab是出现一次的两个数字
}
第三种方法,根据异或结果中1所在的二进制位数,把数组中数分成两种不同类别,分别异或得出结果。
位运算中异或的性质:两个相同数字异或=0,一个数和0异或还是它本身。
–
当只有一个数出现一次时,我们把数组中所有的数,依次异或运算,最后剩下的就是落单的数,因为成对儿出现的都抵消了。
依照这个思路,我们来看两个数(我们假设是AB)出现一次的数组。我们首先还是先异或,剩下的数字肯定是A、B异或的结果,
这个结果的二进制中的1,表现的是A和B的不同的位。
我们就取异或的结果中第一个1所在的位数,假设是第3位,接着把原数组分成两组,通过比较第3位是否为1来分成两组。
如此,相同的数肯定在一个组,因为相同数字所有位都相同,而不同的数,肯定不在一组。
然后把这两个组按照最开始的思路,依次异或,剩余的两个结果就是这两个只出现一次的数字。
// 方法三:
function FindNumsAppearOnce3(array) {
let tmp = array[0];
for (let i = 1; i < array.length; i++) {
tmp = tmp ^ array[i];
}
if (tmp === 0) return;
let index = 0; // 记录第几位是1
while ((tmp & 1) === 0) {
tmp = tmp >> 1;
index++;
}
let num1 = 0,
num2 = 0;
for (let i = 0; i < array.length; i++) {
if (isOneAtIndex(array[i], index)) num1 = num1 ^ array[i];
else num2 = num2 ^ array[i];
}
return [num1, num2];
}
function isOneAtIndex(num, index) {
num = num >> index;
return num & 1;
}
题目描述:
小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck!
输出描述:
输出所有和为S的连续正数序列。序列内按照从小至大的顺序,序列间按照开始数字从小到大的顺序
// 方法一:
// 双指针技术,就是相当于有一个窗口,窗口的左右两边就是两个指针,我们根据窗口内值之和来确定窗口的位置和宽度
function FindContinuousSequence(sum)
{
// write code here
// 两个起点,相当于动态窗口的两边,根据其窗口内的值的和来确定窗口的位置和大小
let plow = 1,
phigh = 2,
// 存放结果
result = []
while(plow < phigh) {
// 由于是连续的,差为1的一个序列,那么求和公式是(a0+an)*n/2
let curSum = (plow + phigh) * (phigh - plow + 1) / 2
// 相等,那么就将窗口范围的所有数添加进结果集
if (curSum === sum) {
let list = []
for (let i = plow; i <= phigh; i++) {
list.push(i)
}
result.pu
如果觉得我的文章对您有用,请随意打赏。你的支持将鼓励我继续创作!