题目：
在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
思路：
/**
* @param {number[]} nums
* @return {number}
*/
var findRepeatNumber = function(nums) {
if(nums.length==0) return false;
//1.循环比较(耗时) （1420 ms / 43.1 MB）
for(let i=0;i<nums.length;i++){
for(let j=i+1;j<nums.length;j++){
if(nums[i]==nums[j]){
return nums[i];
}
}
}
//2.排序后比较(优) (104 ms / 44.2 MB)
nums.sort();
for(let i=0;i<nums.length;i++){
if(nums[i]==nums[i+1]){
return nums[i];
}
}
//3.set 判断 size (100 ms / 45.9 MB)
let s=new Set();
let len=0;
for(let i=0;i<nums.length;i++){
s.add(nums[i]);
if(len==s.size){
return nums[i];
}else{
len=s.size;
}
}
//4. set判断 has (88 ms / 45.6 MB)
let s=new Set();
for(let i=0;i<nums.length;i++){
if(s.has(nums[i])){
return nums[i];
}else{
s.add(nums[i]);
}
}
return false;
};
题目：
在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
示例：
现有矩阵 matrix 如下：
[
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]
给定 target = 5，返回 true。给定 target = 20，返回 false。
思路：
/**
* @param {number[][]} matrix
* @param {number} target
* @return {boolean}
*/
var findNumberIn2DArray = function(matrix, target) {
//1. 矩阵遍历 (88 ms / 40.6 MB)
for(let i=0;i<matrix.length;i++){
for(let j=0;j<matrix[0].length;j++){
if(target==matrix[i][j]){
return true;
}
}
}
//2. （因为已经是顺序）线性查找 (104 ms / 40.7 MB )
for(let i=0;i<matrix.length;i++){
if(target<matrix[i][0]){
return false;
}
for(let j=0;j<matrix[0].length;j++){
if(target==matrix[i][j]){
return true;
}else if(target<matrix[i][j]){
continue;
}
}
}
//3. 二叉搜索树(优) (76 ms / 40.9 MB)
for(let i=0;i<matrix.length;i++){
for(let j=matrix[0].length;j>=0;j--){
if(target==matrix[i][j]){
return true;
}else if(target>matrix[i][j]){
continue;
}
}
}
return false;
};
题目：
请实现一个函数，把字符串 s 中的每个空格替换成"%20"。
思路：
/**
* @param {string} s
* @return {string}
*/
var replaceSpace = function(s) {
//1. 转换数组 (84 ms / 37.6 MB )
let arr=Array.from(s);
for(let i=0;i<arr.length;i++){
if(arr[i]==' '){
arr[i]="%20";
}
}
return arr.join('');
//2. 库函数 (92 ms / 37.5 MB )
return s.replaceAll(" ","%20");
};
题目：
输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。
思路：
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {number[]}
*/
var reversePrint = function(head) {
let arr=new Array();
let cur=head;
while(cur){ //结点为null时无法取值，所以判断当前节点是否存在
arr.unshift(cur.val);
cur=cur.next;
}
return arr;
};
题目：
输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。
假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
思路：
划分左右子树，分别获取其前序遍历和中序遍历，然后递归生成树
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {number[]} preorder
* @param {number[]} inorder
* @return {TreeNode}
*/
var buildTree = function(preorder, inorder) {
if(preorder.length==0) return null;
if(preorder.length==1) return new TreeNode(preorder[0]);
root=preorder[0];
//根据根节点，获取左右树的中序遍历
rootIndex=inorder.indexOf(root);
var leftIn=inorder.slice(0,rootIndex);
var rightIn=inorder.slice(rootIndex+1)
// console.log(leftIn,rightIn)
//根据中序遍历，判断左右树分离点，获取左右树的前序遍历
for(let i=1;i<=preorder.length;i++){
if(!leftIn.includes(preorder[i])){
var leftPre=preorder.slice(1,i);
var rightPre=preorder.slice(i);
break;
}
}
// console.log(leftPre,rightPre)
//根据子前序遍历和子中序遍历（递归参数），递归产生树
var node=new TreeNode(root);
node.left=buildTree(leftPre,leftIn);
node.right=buildTree(rightPre,rightIn);
return node;
};
题目：
用两个栈实现一个队列。
队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。
(若队列中没有元素，deleteHead 操作返回 -1 )
思路：
var CQueue = function() {
this.stack1=[];
this.stack2=[];
};
/**
* @param {number} value
* @return {void}
*/
CQueue.prototype.appendTail = function(value) {
this.stack1.push(value);
};
/**
* @return {number}
*/
CQueue.prototype.deleteHead = function() {
if(this.stack1.length==0){
return -1;
}else{
return this.stack1.shift();
}
};
/**
* Your CQueue object will be instantiated and called as such:
* var obj = new CQueue()
* obj.appendTail(value)
* var param_2 = obj.deleteHead()
*/
题目：
写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：
F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
思路：
/**
* @param {number} n
* @return {number}
*/
var fib = function(n) {
let mod=1e9+7;
//1. 循环计算 (88 ms/38.4 MB)
if(n==0) return 0;
if(n==1) return 1;
let temp,temp1=0,temp2=1;
for(let i=1;i<n;i++){
temp=(temp1+temp2)%mod;
temp1=temp2;
temp2=temp;
}
return temp;
//2. 存入数组 (80 ms/37.8 MB)
let arr=[0,1];
for(let i=2;i<=n;i++){
let temp=(arr[i-1]+arr[i-2])%mod;
arr.push(temp);
}
return arr[n];
};
背景：
一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
思路：
/**
* @param {number} n
* @return {number}
*/
//斐波那契数列(72 ms/37.7 MB)
var numWays = function(n) {
let mod=1e9+7;
let arr=[1,1];
for(let i=2;i<=n;i++){
arr.push((arr[i-1]+arr[i-2])%mod);
}
return arr[n]
};
注：
此类求多少种可能性的题目一般都有递推性质 ，即 f(n)和f(n−1)…f(1) 之间是有联系的。
题目：
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1。
思路：
/**
* @param {number[]} numbers
* @return {number}
*/
var minArray = function(numbers) {
//按序查找（80 ms/38.9 MB）
if(numbers.length==0) return false;
for(let i=0;i<numbers.length;i++){
if(numbers[i]>numbers[i+1]){
return numbers[i+1]
}
}
return numbers[0];
};
题目：
给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
例如，在下面的 3×4 的矩阵中包含单词 “ABCCED”（单词中的字母已标出）。
思路：
【遍历矩阵，比较四个相邻元素，判断过的做标记，本轮中止时还原。】
/**
* @param {character[][]} board
* @param {string} word
* @return {boolean}
*/
//(108 ms/41 MB)
var exist = function(board, word) {
let wordArr=word.split("");
for(let i=0;i<board.length;i++){
for(j=0;j<board[0].length;j++){
if(dfs(board,wordArr,i,j,0)) return true;
}
}
return false;
};
function dfs(board,wordArr,i,j,cur){
if(i >= board.length || i < 0 || j >= board[0].length || j < 0 || board[i][j] != wordArr[cur]){
return false
}else{
board[i][j]=""; //标记当前轮次中的单元格
}
//遍历到最后一个字母，即存在
if(cur==wordArr.length-1){
return true;
}
//递归判断
var res=dfs(board,wordArr,i+1,j,cur+1)||dfs(board,wordArr,i,j+1,cur+1)||dfs(board,wordArr,i-1,j,cur+1)||dfs(board,wordArr,i,j-1,cur+1);
//递归结束，还原标记，开始下一轮
board[i][j]=wordArr[cur];
return res;
}
题目：
地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。
一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。
例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。
请问该机器人能够到达多少个格子？
思路：
/**
* @param {number} m
* @param {number} n
* @param {number} k
* @return {number}
*/
//大于10时，计算数位之和
function add(num){
let s=parseInt(num/10);
let g=num%10;
return s+g;
}
var movingCount = function(m, n, k) {
let count=0;
let arr=new Array();
for(let i=0;i<m;i++){
arr[i]=new Array();//创建二维数组 存储状态
for(let j=0;j<n;j++){
arr[i][j]=false; //初始化数组
if(dfs(i,j,k,arr)){ //遍历标记
arr[i][j]=true;
count++;
}else{
continue;
}
}
}
return count;
};
//遍历并判断
function dfs(i,j,k,arr){
// 单独判断0的情况
if(i==0&&j==0){return true;}
if(i==0){
if(arr[0][j-1]){
if(j>=10) {j=add(j);}
return k>=i+j;
}else{
return false;
}
}else if(j==0){
if(arr[i-1][0]){
if(i>=10) {i=add(i);}
return k>=i+j;
}else{
return false;
}
//条件：上或者左 有路径
}else if(arr[i-1][j]||arr[i][j-1]){
if(i>=10) i=add(i);
if(j>=10) j=add(j);
return k>=i+j;
}
return false;
}
【深度里的递归遍历，利用的系统栈：一个方向遍历到底，不满足条件时回头】
/**
* @param {number} m
* @param {number} n
* @param {number} k
* @return {number}
*/
//计算数位之和
function add(i,j){
if(i>=10){i=parseInt(i/10)+i%10}
if(j>=10){j=parseInt(j/10)+j%10}
return i+j;
}
var movingCount = function(m, n, k) {
let count=0;
let arr=new Array();
for(let i=0;i<m;i++){
arr[i]=new Array();//创建二维数组 存储状态
for(let j=0;j<n;j++){
arr[i][j]=false;//初始化数组
}
}
return dfs(m,n,k,arr,0,0);
};
function dfs(m,n,k,arr,i,j){
//设置边界条件 1.范围内 2.未查询过 3.条件：k>=i+j
if(i<0||i>=m||j<0||j>=n||arr[i][j]||k<add(i,j)){
return false;
}
//符合条件时更改状态
arr[i][j]=true;
//递归遍历 符合时增加
return 1+dfs(m,n,k,arr,i,j+1)+dfs(m,n,k,arr,i+1,j);
}
题目：
给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]…k[m-1] 。
请问 k[0]k[1]…*k[m-1] 可能的最大乘积是多少？
例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。
注：2 <= n <= 58
思路：
我们想要求长度为n的绳子剪掉后的最大乘积，可以从前面比n小的绳子转移而来
1️⃣用一个dp数组记录从0到n长度的绳子剪掉后的最大乘积，也就是 dp[ i] 表示长度为i的绳子剪成m段后的最大乘积
2️⃣先剪第一段（长度为 j ），如果只剪掉长度为1，对最后的乘积无任何增益，所以从长度为2开始剪。剪了第一段后，剩下(i - j)长度可以剪也可以不剪。如果不剪的话长度乘积即为 j * (i - j)；如果剪的话长度乘积即为 j * dp[i - j]。取两者最大值max(j * (i - j), j * dp[i - j])
3️⃣第一段长度 j 可以取的区间为[2,i)，对所有j不同的情况取最大值，因此最终dp[i]的转移方程为 dp[i] = max(dp[i], max(j * (i - j), j * dp[i - j]))
4️⃣最后返回dp[n]即可
1.dp[n] 记录最大值（数组需初始化）：长度为i的绳子最大乘积为dp[i]
2.（以小见大） 剪一段 j 【因为1无意义，所以从2开始剪（2<=j<i）】 剩下的则为（i-j）
3.两种选择：剪或者不继续剪=》Math.max( j*(i-j)，j*dp[i-j] )
4. 最终比较得出状态转移方程：dp[i] = max(dp[i], max(j * (i - j), j * dp[i - j]))
优化： 剪第一段长度时，因为剪完绳长i 的前半段，后半段也相应相同，所以只要遍历一半
/**
* @param {number} n
* @return {number}
*/
//(80 ms/39.2 MB)
var cuttingRope = function(n) {
let dp=new Array(n+1).fill(1);
dp[1]=dp[2]=1;
dp[3]=2;
for(let i=3;i<=n+1;i++){//绳子长度 初始化后从3开始
for(let j=2;j<i/2+1;j++){ //剪的第一段长度
dp[i]=Math.max(dp[i],Math.max(j*(i-j),j*dp[i-j]));
}
}
return dp[n];
};
/**
* @param {number} n
* @return {number}
*/
var cuttingRope = function(n) {
if(n==1||n==2) return 1;
if(n==3) return 2;
if(n==4) return 4;
let res=1;
while(n>4){
res*=3;
n-=3;
}
res*=n; // 剩余的段（1/2/3）相乘
return res;
};
题目：
同上，区别：2 <= n <= 1000
思路：
不同在于本题涉及 “大数越界情况下的求余问题”
循环求余：
/**
* @param {number} n
* @return {number}
*/
var cuttingRope = function(n) {
if(n==1||n==2) return 1;
if(n==3) return 2;
if(n==4) return 4;
let res=1;
while(n>4){
res=(res*3)%1000000007;
n-=3;
}
return (res*n)%1000000007;
};
题目：
请实现一个函数，输入一个整数（以二进制串形式），输出该数二进制表示中 1 的个数。例如，把 9 表示成二进制是 1001，有 2 位是 1。因此，如果输入 9，则该函数输出 2。
思路：
/**
* @param {number} n - a positive integer
* @return {number}
*/
var hammingWeight = function(n) {
let count=0;
while(n>0){
count+=n&1; //最后一位为1时，n&1为1
n=n>>>1; //无符号右移 >>> , 有符号右移 >>
}
return count;
};
/**
* @param {number} n - a positive integer
* @return {number}
*/
var hammingWeight = function(n) {
let num=0;
n=n.toString(2).split(""); //用二进制转换
for(let i of n){
if(i==1) num++;
}
return num;
};
题目：
实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xn）。不得使用库函数，同时不需要考虑大数问题。
思路：
根据二分推导，可通过循环 x =x2 操作，每次把幂从 n降至 n/2 ，直至将幂降为 0；
设 res=1 ，则初始状态 xn=xn * res 。在循环二分时，每当 n为奇数，将多出的一项 x乘入res ，则最终可化至 xn=x0*res ，返回 res 即可。
位运算：
向下整除 n/2 等价于 右移一位 n>>1 ；
取余数 n%2 等价于 判断二进制最右一位值 n&1 ；
/**
* @param {number} x
* @param {number} n
* @return {number}
*/
var myPow = function(x, n) {
if(n<0){
n=-n;
x= 1/x;
}
let res=1;
while(n>0){
if(n&1){ res=res*x;} //取余，n为奇数
x=x*x;
n=n>>>1; //n/2
}
return res;
};
题目：
输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数 999。
思路：
字符串组出最大数字，转换成数字，循环打印
/**
* @param {number} n
* @return {number[]}
*/
var printNumbers = function(n) {
let maxStr='';
while(n>=1){
maxStr+="9";
n--;
}
let maxNum=Number(maxStr);
let arr=[];
for(let i=1;i<=maxNum;i++)
arr.push(i);
return arr;
};
题目：
给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。返回删除后的链表的头节点
思路：
1.遍历链表
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @param {number} val
* @return {ListNode}
*/
//1.遍历(next)
var deleteNode = function(head, val) {
let node=head;
if(node.val==val){return node.next;}
while(node.next!=null){
if(node.next.val==val){
node.next=node.next.next;
}else{
node=node.next;
}
}
return head;
};
//2.遍历（pre,next）
var deleteNode = function(head, val) {
if(head.val==val) return head.next;
let cNode=head.next;
let pre=head;
while(cNode!=null && cNode.val!=val){
pre=cNode;
cNode=cNode.next;
}
pre.next=cNode.next;
return head;
};
题目：
定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。
思路：
1.使用数组（stack）存储结点
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var reverseList = function(head) {
if(head==null){return null}
let stack=[];
let node=head;
while(node!=null){
stack.push(node.val);
node=node.next;
}
let nHead=new ListNode();
nHead.val=stack.pop();
let thead=nHead;
while(stack.length>0){
let nNode=insertNode(stack.pop(),thead);
thead=nNode;
}
return nHead;
};
var insertNode=function(val,head){
let nNode=new ListNode();
nNode.val=val;
head.next=nNode;
return nNode;
}
2.原地改变链表结点指向
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var reverseList = function(head) {
if(head==null) return null;
else if(head.next==null) return head;
else{
let cur=head.next;
let pre=head;
while(cur.next){
let temp=cur.next;
cur.next=pre;
pre=cur;
cur=temp;
}
cur.next=pre;
head.next=null;
return cur;
}
};
题目：
输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。
思路：
定义一个虚拟头结点，两个链表比较后链入，最后剩余的直接加入链尾。
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} l1
* @param {ListNode} l2
* @return {ListNode}
*/
var mergeTwoLists = function(l1, l2) {
let nl=new ListNode(0);
let node=nl;
while(l1&&l2){
if(l1.val<=l2.val){
node.next=l1;
l1=l1.next;
}else{
node.next=l2;
l2=l2.next;
}
node=node.next;
}
if(l1){node.next=l1}
if(l2){node.next=l2}
return nl.next;
};
题目：
给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。
输入: 12258
输出: 5
解释: 12258有5种不同的翻译，分别是"bccfi", “bwfi”, “bczi”, “mcfi"和"mzi”
思路：
/**
* @param {number} num
* @return {number}
*/
var translateNum = function(num) {
let arr=num.toString().split("");
let dp=[1,1];
for(let i=1;i<arr.length;i++){
if(Number(arr[i-1]+arr[i])<26 && Number(arr[i-1]+arr[i])>=10){
dp.push(dp[i]+dp[i-1]);
}else{
dp.push(dp[i]);
}
}
return dp[dp.length-1]
};
题目：
输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。
思路：
因为递增排序，使用头尾双指针，碰撞时结束循环。
过小：小指针增大
过大：大指针减小
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function(nums, target) {
let a=0;
let b=nums.length-1;
while(a<b){
if(nums[a]+nums[b]==target){
return [nums[a],nums[b]]
}
else if(nums[a]+nums[b]>target){
b--;
}else if(nums[a]+nums[b]<target){
a++
}
}
return false;
};
1. for循环
i是变量，不能直接和数字运算
//true
for(let i in nums){
if(nums[i]==nums[++i]){
return nums[i]
}
}
//false
for(let i in nums){
if(nums[i]==nums[i+1]){
return nums[i]
}
}
2. slice & splice
arr.slice(begin,end)：
array.splice( start, deleteCount, item1, item2, …)