1.矩形重叠
/**
* @param {number[]} rec1
* @param {number[]} rec2
* @return {boolean}
*/
var isRectangleOverlap = function(rec1, rec2) {
return (Math.min(rec1[2], rec2[2]) > Math.max(rec1[0], rec2[0]) &&Math.min(rec1[3], rec2[3]) > Math.max(rec1[1], rec2[1]))
};
2.二进制间距
/**
* @param {number} n
* @return {number}
*/
var binaryGap = function(n) {
let str = n.toString(2)
let L=0,R=L+1;
let res=[0];
while(R<str.length){
if(str[L]!=1){
L++;
R++;
}else{
if(str[L]==str[R]){
res.push(R-L)
L = R;
R = L+1;
}else{
R++;
}
}
}
return Math.max(...res)
};
3. 最小差值 I
/**
* @param {number[]} A
* @param {number} K
* @return {number}
*/
var smallestRangeI = function(A, K) {
let len = A.length
if(len==1) return 0
let sum=0;
for(let i=0;i<A.length;i++){
sum+=A[i]
}
let middle = Math.round(sum/len)
A.sort((a,b)=>a-b)
if(A[len-1]-middle>=K){
A[len-1]-=K
}else{
A[len-1]-=(A[len-1]-A[0])
}
if(A[len-1]-A[0]>K){
A[0]=(A[0]+K)
}else{
A[0]=A[len-1]
}
return A[len-1]-A[0]
};
4. 卡牌分组
var hasGroupsSizeX = function(deck) {
let map = new Map()
for(let n of deck){
map.set(n,map.has(n)?map.get(n)+1:1)
}
let arr = [...map.values()]
let res = arr[0]
return arr.every(i => (res = gcd(res, i)) > 1)
};
let gcd = (a, b) => (b === 0 ? a : gcd(b, a % b))
5.增减字符串匹配
/**
* @param {string} S
* @return {number[]}
*/
var diStringMatch = function(S) {
let nums=[],res=[];
for(let i=0;i<=S.length;i++){
nums.push(i);
}
for(let i=0;i<S.length;i++){
if(S[i]=='D'){
res.push(Math.max(...nums));
nums.pop();
}else{
res.push(Math.min(...nums));
nums.shift()
}
}
res.push(nums[0])
return res
};
6.强整数
/**
* @param {number} x
* @param {number} y
* @param {number} bound
* @return {number[]}
*/
var powerfulIntegers = function(x, y, bound) {
let set = new Set()
function getRes(numx,numy){
let num = numx+numy
if(num>bound) return;
set.add(num)
if(x!==1) getRes(numx*x,numy)
if(y!==1) getRes(numx,numy*y)
}
getRes(1,1)
return Array.from(set.values())
};
7.三角形的最大周长
/**
* @param {number[]} A
* @return {number}
*/
var largestPerimeter = function(A) {
A.sort((a,b)=>b-a)
for(let i=0;i<A.length-2;i++){
if((A[i+2]+A[i+1]>A[i])&&(A[i]-A[i+1]<A[i+2])){
return A[i]+A[i+1]+A[i+2]
}
}
return 0
};
8.玩筹码
/**
* @param {number[]} position
* @return {number}
*/
var minCostToMoveChips = function(position) {
let o=0,j=0;
for(let i=0;i<position.length;i++){
if(position[i]%2==0){
o++
}else{
j++
}
}
return Math.min(o,j)
};
9.整数的各位积和之差
/**
* @param {number} n
* @return {number}
*/
var subtractProductAndSum = function(n) {
let h=0,j=1;
while(n>0){
h+=n%10
j*=n%10
n = Math.floor(n/10)
}
return j-h
};
10.打印从1到最大的n位数
/**
* @param {number} n
* @return {number[]}
*/
var printNumbers = function(n) {
let res=[]
let len=0
for(let i=0;i<n;i++){
len+=Math.pow(10,i)*9
}
for(let i=1;i<=len;i++){
res.push(i)
}
return res
};
实际上，本题的主要难点是大数越界情况下的打印。应该使用全排列方法
11.第 N 个泰波那契数
/**
* @param {number} n
* @return {number}
*/
var tribonacci = function(n) {
if(n==0) return 0
if(n==1) return 1
if(n==2) return 1
const fun = (x1,x2,x3,num)=>{
let sum=x1+x2+x3
if(num==n){
return sum
}
num++
return fun(x2,x3,sum,num)
}
return fun(0,1,1,3)
};
12.斐波那契数列
由于测试数据会溢出 js 中的整数范围，所以请使用大数（bigint）类型
/**
* @param {number} n
* @return {number}
*/
var fib = function(n) {
if(n==0) return 0
if(n==1) return 1
const fun = (x1,x2,num)=>{
let sum=x1+x2
if(num==n){
return sum % 1000000007n
}
num++
return fun(x2,sum,num)
}
return fun(0n,1n,2)
};
12.青蛙跳台阶问题
/**
* @param {number} n
* @return {number}
*/
var numWays = function(n) {
const fn = (num=2,num1=1n,num2=1n)=>{
if(n<2){
return 1
}
if(n==num){
return (num1+num2)%1000000007n
}
num++
return fn(num,num2,(num1+num2)%1000000007n)
}
return fn()
};
13.跳水板
var divingBoard = function(shorter, longer, k) {
if(k==0) return []
if(shorter===longer){
return [shorter*k]
}
let res = []
for(let i=0;i<=k;i++){
res[i] = shorter*(k-i)+longer*i
}
return res
};
14.汉诺塔问题
/**
* @param {number[]} A
* @param {number[]} B
* @param {number[]} C
* @return {void} Do not return anything, modify C in-place instead.
*/
var hanota = function(A, B, C) {
let len = A.length
const move = (n,A,B,C)=>{
if(n===1){
C.push(A.pop())
return
}
move(n-1,A,C,B)
C.push(A.pop())
move(n-1,B,A,C)
}
move(len,A,B,C);
};
