Swordoffer

题目 在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。 详解 排序：将输入数组排序，再判断相邻位置是否存在相同数字，如果存在，对 duplication 赋值返回，否则继续比较 JS实现 function duplicate(numbers, duplication) { // write code here if (numbers.length <= 0) { …

题目 求1+2+3+…+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。 详解 短路原理 JS实现 function Sum_Solution(n) { // write code here let result = n; result && (result += Sum_Solution(n - 1)); return result; }

题目 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 …

题目 给你一根长度为n的绳子，请把绳子剪成整数长的m段（m、n都是整数，n>1并且m>1），每段绳子的长度记为k[0],k[1],…,k[m]。 请问k[0] x k[1] x … x k[m]可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。 输入描述: 输入一个数n，意义见题面。（2 <= n <= 60） 输出描述: 输出答案。 示例1 输入 8 输出 18 详解 动态规划（自底向上） 使用动态规划，从已知值 F(2) 逐步迭代到目标值 F(n)，它是一种自底向上的方法。 …

题目 把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组 {3,4,5,1,2} 为 {1,2,3,4,5} 的一个旋转，该数组的最小值为1。 原来的：{1,2,3,4,5} 旋转后：{3,4,5,1,2} NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。 详解 旋转之后的数组实际上可以划分成两个有序的子数组：前面子数组的值 都大于 后面子数组中的元素。 注意到实际上最小的元素就是两个子数组的分界线。本题目给出的数组一定程度上是排序的，因此我们试着用二分查找法寻找这个最小的元素。 思路： 我们用 …

题目 请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy。则经过替换之后的字符串为We%20Are%20Happy。 JS实现 //实现1：调用自带函数 function replaceSpace(str) { // write code here return str.replace(/\s{1}/g, "%20"); } //实现2：用新的变量存，当遇到 " "，就追加 "%20"，否则遇到什么追加什么 function replaceSpace(str) { // write code …

题目 输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。 例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。 详解 前序：根->左->右 {1,2,4,7,3,5,6,8} 中序：左->根->右 {4,7,2,1,5,3,8,6} 根据中序遍历和前序遍历可以确定二叉树，具体过程为： 根据前序序列第一个结点确定根结点； 根据根结点在中序序列中的位置分割出左右两个子序列； 对左子树和右子树分别递归使用同样的方法继续分解； 例如： 前序序 …

题目 在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。 [ [1, 2, 3], [4, 5, 6], [7, 8, 9] ] 详解 暴力法 挨个遍历数组，如果找到就返回 true 时间复杂度：O(n^2) 空间复杂度：O(1) 从左下找 利用该二维数组的性质： 每一行都按照从左到右递增的顺序排序， 每一列都按照从上到下递增的顺序排序 换个说法，即对于左下角的值 m，m 是该行最小的数，是该列最大的数 每次将 m 和目标值 target 比较： 当 m …

题目 输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构） JS实现 /* function TreeNode(x) { this.val = x; this.left = null; this.right = null; } */ function HasSubtree(root1, root2) { // write code here if (root1 === null || root2 === null) { return false; } let result = false; if (root1.val === root2.val) { …

题目 输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字， 例如， 如果输入如下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. 详解 简单来说，就是不断地收缩矩阵的边界。 定义四个变量代表范围，up、down、left、right 向右走存入整行的值，当存入后，该行再也不会被遍历，代表上边界的 up 加一，同时判断是否和代表下边界的 down 交错 向下走存入整列的值，当存入后，该列再也不会被遍历， …