1.环形链表
var detectCycle = function(head) {
let map = new Map()
while(head){
if(map.get(head)) return head
map.set(head,1)
head = head.next
}
return null
};
2.链表相交
var getIntersectionNode = function(headA, headB) {
let map = new Map()
let curA=headA,curB=headB
while(curA){
map.set(curA,1)
curA=curA.next
}
while(curB){ //curB是否在map中
if(map.get(curB)){
return curB
}
curB=curB.next
}
return null
};
3.判断两个map是否相等
//判断mas和mat是否相等
if (mas.size !== mat.size) {
return false;
}
for (var [key, val] of mas) {
testVal = mat.get(key);
//值不相等或不存在这个值
if (testVal !== val || (testVal === undefined && !mat.has(key))) {
return false;
}
}
return true;
}
同类题
判断一个map是否在另一个map内,383赎金信
/map1是否在map2内
if(map1.size>map2.size){
return false
}
//1.map1在map2内但很大
//2.map1不在map2内
for(var [key,val] of map1){
map2val=map2.get(key)
if((map2val<val&&map2.has(key))||((map2.get(key)===undefined)&&!map2.has(key))){
return false
}
}
return true
标准答案是用数组，先放一个数，再减掉比较
var canConstruct = function(ransomNote, magazine) {
const arr = new Array(26).fill(0);
const base = 'a'.charCodeAt();
if(ransomNote.length>magazine.length) return false;
for(const i of magazine){
arr[i.charCodeAt()-base]++;
}
for(const i of ransomNote){
arr[i.charCodeAt()-base]--;
if(arr[i.charCodeAt()-base]<0) return false;
}
return true;
};
4.计算map:如果比较多，封装
第一种方法
function countmap(nums1){
let map=new Map()
for(let s of nums1){
let count=map.has(s)?map.get(s):0
map.set(s,count+1)
}
return map
}
第二种方法
for(let s1 of nums1){
// if(map1.get(s1)){
// map1.set(s1,map1.get(s1)+1)
// }
// else{
// map1.set(s1,1)
// }
// }
5.将map的[key,val]设置为[num,index]
for(let i=0;i<nums.length;i++){
map.set(nums[i],i)
}
var hashMap = new Map();
nums.forEach(function(item,index){
hashMap.set(item,index);
})
let set =new Set(num1) //去重
set.add(i)//加入set中
Array.from（set)//转成数组
转换成tostring，然后放到数组里
function qushu(n){
let str=n.toString()
let sum=0
for(let i of str){
sum+=i*i
}
return sum
// console.log(sum)
}
递归思路：先找到最后一个，再往前操作
function ReverseList(pHead)
{
// write code here
//1.迭代
/*if(!pHead||!pHead.next) return pHead
let cur = pHead,pre=null,temp=null
while(cur){
temp=cur.next
cur.next = pre
pre = cur
cur=temp
}
return pre*/
//2.递归
if(!pHead||!pHead.next) return pHead
let result=ReverseList(pHead.next)//找到最后一个
pHead.next.next=pHead//反转
pHead.next=null//注意要置空
return result
}
1.和为S的连续正序列
function getsum(num1,num2){//计算总和的
return (num2+num1)*(num2-num1+1)/2
}
function getpath(start,end){//路径
let res=[]
for(let i=start;i<=end;i++){
res.push(i)
}
return res
}
function FindContinuousSequence(sum)
{
// write code here
//双指针，滑动窗口
if(!sum) return []
let left=1,right=1
let result=[]//存放结果
let end=Math.ceil(sum/2)
while(right<=end){
let n=getsum(left,right)
if(sum===n){
let m=getpath(left,right)
if(m.length==1) return []
result.push(getpath(left,right))
left++
right++
}
else if(sum<n){
left++
}
else{
right++
}
}
return result
}
2.和为S的两个数字（也可以用map解决）
function FindNumbersWithSum(array, sum)
{
// write code here
// const map=new Map()
// for(let num of array){
// if(map.get(sum-num)) return [num,sum-num]
// else map.set(num,true)
// }
// return []
//滑动窗口
let res=[]
let left=0;
let right=array.length-1;
while(left<right){//终止条件
if(array[left]+array[right]==sum){
res.push(array[left])
res.push(array[right])
break
}
else if(array[left]+array[right]>sum){ //缩小右边
right--
}
else{//扩大左边
left++
}
}
return res
}
while j < len(nums):
判断[i, j]是否满足条件
while 满足条件：
不断更新结果(注意在while内更新！)
i += 1 （最大程度的压缩i，使得滑窗尽可能的小）
j += 1
最大滑窗模板：给定数组 nums，定义滑窗的左右边界 i, j，求满足某个条件的滑窗的最大长度。
while j < len(nums):
判断[i, j]是否满足条件
while 不满足条件：
i += 1 （最保守的压缩i，一旦满足条件了就退出压缩i的过程，使得滑窗尽可能的大）
不断更新结果（注意在while外更新！）
j += 1
1.找规律递归
function LastRemaining_Solution(n, m)
{
// 约瑟夫问题的递推公式 f(n,m) = ( f(n-1,m) +m)%n )
/*假设f(n)表示0~n-1共n个数字中最后剩下的数字，去掉的数字为(m-1)%n，而下一次报数是从 m%n个数字开始(即出局的下一个为止)，因此
f(n-1) 和 f(n)之前的关系如下：
f(n-1) f(n)
0 m%n
1 (m+1)%n
... ...
n-2 (m-2)%n*/
if(n==0)
return -1;
if(n==1)
return 0;
else
return (LastRemaining_Solution(n-1,m)+m)%n;//
}
//层序遍历
function Print(pRoot)
{
// write code here
let res=[]//存放最后结果
let queue=[]//队列暂存每一层，便于下一层遍历
queue.push(pRoot)
if(pRoot===null) return res
while(queue.length!==0){
let length=queue.length
let curlevel=[]//存每一层的
for(let i=0;i<length;i++){//注意length这里是定量
let node=queue.shift()//当前node输出!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
curlevel.push(node.val)//记录node的值
node.left&&queue.push(node.left)
node.right&&queue.push(node.right)
}
res.push(curlevel)
}
return res
1.螺旋矩阵，输入n
let matrix=new Array(n).fill(0).map(()=>new Array(n).fill(0)); //注意生成二维数组的方法
//let matrix = new Array(n).fill(new Array(n).fill(0))有问题，修改的时候会改掉同列
let left=0,right=n-1,top=0,bottom=n-1
// let result=[]//保存result
//和牛客网上的题不同的是一个是打印数组一个是打印n
let num=1
while(num<=n*n){
//left to right
for(let i = left; i <= right; i++) matrix[top][i]=num++;
top++;
//top tp bottom
for(let i = top; i <= bottom; i++) matrix[i][right]=num++;
right--;
//right to left
for(let i = right; i >= left ; i--) matrix[bottom][i]=num++;
bottom--;
//bottom to top
for(let i = bottom; i >= top; i--) matrix[i][left]=num++;
left++;
}
return matrix
2.顺时针打印矩阵
function printMatrix(matrix)
{
// write code here
let row = matrix.length;
let col= matrix[0].length;
let result=[]
// 输入的二维数组非法，返回空的数组
if (row == 0 || col == 0) return result;
let top = 0, left = 0, right = col-1, bottom = row-1;
//为什么没有区别，单句是没有区别的，只有在字句里才有区别
while(top <= bottom && left<= right){
//left to right
for(let i = left; i <= right; i++) result.push(matrix[top][i]);
top++;
//top tp bottom
for(let i = top; i <= bottom; i++) result.push(matrix[i][right]);
right--;
//right to left
for(let i = right; i >= left&&top<=bottom; i--) result.push(matrix[bottom][i]);
bottom--;
//bottom to top
for(let i = bottom; i >=top &&left<=right ; i--) result.push(matrix[i][left]);
left++;
}
return result;
}
var removeNthFromEnd = function(head, n) {
//利用双指针的快慢指针，找到第n个
//slow就是要删除节点的前一个
const pre=new ListNode(0,head)//头结点，这个为什么会这么重要（可以把他们统一起来）
let slow=pre,fast=pre
while(n-->=0){
fast=fast.next
}
while(fast){
fast=fast.next
slow=slow.next
}
slow.next=slow.next.next
return pre.next
};
设置头结点，不设置头结点的话过不去，因为fast没有next
1.三数之和
var threeSum = function(nums) {
//用一维记录，二维写，记录-a-b是否在内
nums.sort((a,b)=>a-b) //排序
let hashmap=new Map()
nums.forEach(function(value,index){
hashmap.set(value,index)
})
let res=[]
let set = new Set()
for(let i=0;i<nums.length - 2;i++){
for(let j=i+1;j<nums.length - 1;j++){
if(hashmap.has(-nums[i]-nums[j])&&hashmap.get(-nums[i]-nums[j])>j){//避免内部重复
let cur = [nums[i],nums[j],-nums[i]-nums[j]]//避免外部重复
let s = cur.toString();//去重妙啊
if (set.has(s)) continue
res.push(cur)
set.add(s)
}
}
}
return res
2.四数之和
var fourSum = function(nums, target) {
//a+b=-c-d
//abmap，是否在cdmap
//双指针的变种，固定两个，放两个移动
nums.sort((a,b)=>a-b)
let len=nums.length
let res=[]
for(let i=0;i<len-3;i++){
if(nums[i]==nums[i-1]) continue
for(let j=i+1;j<len-2;j++){
if(j>i+1&&nums[j]==nums[j-1]) continue //这一步很重要,确保j从第二个数开始比j>i+1
// console.log(j)
let left=j+1,right=len-1
while(left<right){
if(nums[i]+nums[j]+nums[left]+nums[right]===target){
res.push([nums[i],nums[j],nums[left],nums[right]])
console.log(i,j,left,right)
while(left<right&&nums[left]==nums[left+1]){
left++
}
while(left<right&&nums[right]==nums[right-1]){
right--
}
left++
right--
}
else if(nums[i]+nums[j]+nums[left]+nums[right]>target){
right--
}
else{
left++
}
}
}
}
return res
操作的时候要记得把字符串转成数组
var replaceSpace = function(s) {
//1.计算空格个数
//2.总长度计算
//3.从后往前覆盖
//注意，需要把字符串切成数组
s=s.split('')
console.log(s)
let bcount=0
let slen=s.length
for(let str of s){
if(str==' '){
bcount++
}
}
let len=slen+2*bcount
for(let i=slen-1,j=len-1;i>=0,j>=0;i--){//对s从后往前遍历
if(s[i]!==' '){
s[j--]=s[i]
// console.log(j,s[i])
}
else{
s[j--]='0'
s[j--]='2'
s[j--]='%'
console.log(j,s[j])
}
}
return s.join('')
};
这里要注意s=s.split(’ ‘)和s=s.split(’ ‘)一个是分离单词一个是分离字符
s=s.join(’ ‘)连接会加上空格，因此就直接把所有空格去掉然后再用s=s.join(’ ')加上单词会出现的字符
var reverseWords = function(s) {
//1.去掉空格
//2.翻转字符串
function removeblank(s){//输入数组，输出数组
let slow=0,fast=0
console.log(s,s.length)
while(fast<s.length){
if(s[fast]===''){//去掉所有空格
//如果去掉前面和重复的需要if(s[fast]===''&&(fast===0||s[fast-1]=='')
fast++
console.log(fast)
}
else{
s[slow++]=s[fast++]//记录的为没有空格的
// console.log(slow)
}
}
//slow存的是没有空格的单词，因此把前slow输出
return s.slice(0,slow)
//去掉最后的空格
// console.log(s)
// let slen=s[slow-1]===''?slow-1:slow
// console.log(s.slice(0,slen))
// return s.slice(0,slen)
//
}
function resver(s){//输入数组，输出字符串
let slen=s.length
let l=0,r=slen-1
while(l<r){
[s[l],s[r]]=[s[r],s[l]]
l++
r--
}
console.log(s)
return s.join(' ')//会加上空格
}
s=s.split(' ')
console.log(s)
return resver(removeblank(s))
};
可以用map来解决
key:value
//递归
// if(root==null) return true
// return judge(root.left,root.right)
// function judge(left,right){
// if(!left&&!right) return true
// if(!left||!right) return false
// if(left.val!=right.val) return false
// if(left.val==right.val) return judge(left.left,right.right)&&judge(left.right,right.left) //内侧和外侧
// }
//迭代
if(root==null) return true
let queue=[root.left,root.right]
while(queue.length!=0){
let len=queue.length
for(let i=0;i<len;i++){
let left=queue.shift()
let right=queue.shift()
if(!left&&!right) continue
if((!left||!right)||left.val!=right.val) return false
queue.push(left.right,right.left)
queue.push(left.left,right.right)
}
}
return true
};
1.先转成数组，递归中序遍历
2.map求众数
//求map众数
let max=-Infinity
let result=[]
for(let [key,val] of map){
if(max<val){
max=val
result=[]//把前面清空，只记录最大的
result.push(key)
}
else if(max==val){//如果众数相等
result.push(key)
}
}
这道题有点难,竹子哥的思路很清晰
if(!root) return null
if(root.val>key) root.left=deleteNode(root.left,key)
else if(root.val<key) root.right=deleteNode(root.right,key)
else{//刚好等于这个值
if(!root.right){//没有右节点
return root.left
}
else{
root.val=postnode(root)
root.right=deleteNode(root.right,root.val)
}
}
return root;
function postnode(node){
node=node.right
while(node.left){
node=node.left
}
return node.val
}
组合问题模板
1.写back(n,k,startindex)
path.push()
path.pop()
function back(n,k,a){
if(path.length==k){
// console.log(path)
res.push(path.join(''))
return
}
for(const v of map[n[a]]){ //digits第a个数,0,1
path.push(v)
back(n,k,a+1)
path.pop()
}
}
2.分割回文串
let path=[],res=[]
function ishuiwen(s,start,end){
let len=s.length
for(let i=start,j=end;i<j;i++,j--){
if(s[i]!=s[j]){
return false
}
}
return true
}
// console.log(ishuiwen(s,0,1))
function back(s,startindex){//startindex切割线
if(startindex>=s.length){//到了最右边终止
res.push([...path])
// console.log(res)
return
}
for (let i = startindex; i < s.length; i++) {//横向
if(ishuiwen(s,startindex,i)){//是回文串
let str=s.substr(startindex,i-startindex+1)//截取
path.push(str)
// console.log(path,startindex)
}
else{
continue;
}
back(s,i+1)//深度
path.pop()
}
}
back(s,0)
return res
1.contiue的条件不同，他不能排顺序
let path=[],res=[]
function back(nums,used){
if(path.length==nums.length){
res.push([...path])
return
}
for(let i=0;i<nums.length;i++){
//每个数用一次且每层用一次
if(used[i]==true||(i>0&&nums[i]==nums[i-1]&&used[i-1]==false)){
continue
}
used[i]=true
path.push([nums[i]])
back(nums,used)
used[i]=false
path.pop()
}
}
nums.sort((a,b)=>a-b)
let used=new Array(nums.length).fill(false)
back(nums,used)
return res
1.终止条件 path.length==nums.length
back(nums,target,sum,startindex)
横向：i=startindex，i++
纵向：back(nums,target,sum,i+1)
1.终止条件 startindex==nums.length 到达最右边
back(nums,startindex)
横向：i=startindex，i++
纵向：back(nums,i+1)
1.终止条件 startindex==nums.length 到达最右边
back(nums,startindex)
res.push([…path]) 放在最前面不然会漏掉本身
横向：i=startindex，i++
纵向：back(nums,i+1)
1.终止条件 path.length==nums.length
back(nums,used) //每个数只能用一次，用used标记
横向：i=0，i++
纵向：back(nums,used)
树枝去重条件
i>startindex&&num[i]==num[i-1]&&used[i-1]==fasle continue
数组排序：去重的时候
1.跳跃游戏
有两步比较关键：i<=cover，把零的排除掉和 cover=Math.max(cover,i+nums[i])
var canJump = function(nums) {
if(nums.length==1){
return true
}
let cover=0//能走的范围
//怎么把零排除掉，因为是从第一步开始走
for(let i=0;i<=cover;i++){//小于cover
cover=Math.max(cover,i+nums[i])//这一步很重要
if(cover>=nums.length-1){
console.log(cover)
return true
}
}
return false
2.跳跃游戏(进阶)
var jump = function(nums) {
let curIndex=0
let nextIndex=0
let steps=0
for(let i=0;i<nums.length-1;i++){
nextIndex=Math.max(nextIndex,nums[i]+i)
if(i==curIndex){
curIndex=nextIndex
steps++
}
}
return steps
};
3.数组和
1）nums.reduce((a,b)=>{
return a+b;
2）直接数组相加
4.绝对值从小到大排序
nums.sort((a,b)=>{
return Math.abs(b)-Math.abs(a)
})
5.最大子数组和
如果为负数重新开始
// result=-Infinity
// sum=0
// for(let i=0;i<nums.length;i++){
// sum+=nums[i]
// if(result<sum){
// result=sum
// }
// if(sum<0){
// sum=0
// }
// }
// return result
6.加油站问题
局部最优
let cursum=0,totalsum=0,start=0
for(let i=0;i<gas.length;i++){
cursum+=gas[i]-cost[i] //当前的值
totalsum+=gas[i]-cost[i]
if(cursum<0){//如果小于零，不可能能开出去，从下一个找
cursum=0
start=i+1
}
}
if(totalsum<0) return -1
return start
7.Math.pow
8.candys.reduce((a, b) => {
return a + b
})
9.splice(index,howmany,index1)
把index1插入index前面(index,0，index1)
10.二维数组排序
people.sort((a, b ) => {
if(b[0] !== a[0]) {
return b[0] - a[0]
} else {
return a[1] - b[1]
}
})
var findMinArrowShots = function(points) {
//计算有交叉的数量
let count=1
//排下序吧
points.sort((a,b)=>{
return a[0]-b[0]
}
)
//遍历,start<end说明无交叉，+1，就
let m=points.length
// let n=points[0].length 2
console.log(points)
for(let i=1;i<m;i++){
//二维数组怎么比较？i+1会越界
if(points[i-1][1]<points[i][0]){
count++
}
else{
points[i][1]=Math.min(points[i-1][1],points[i][1])//
console.log(points[i-1][1],points[i][1])
}
}
return count
};
合并二叉树
注意第一个数怎么表达感觉二维数组最好从i=1遍历，然后就不会越界
let left=intervals[0][0]
let right=intervals[0][1]
for(let i=1;i<intervals.length;i++){
if(intervals[i][0]>right){//无重叠
console.log(left,right)//这样就把第一个数输入
res.push([left,right])
left=intervals[i][0]
right=intervals[i][1]
}
else{//重叠
right=Math.max(intervals[i][1],right)
// console.log(right)
}
// console.log(left,right)
}
// console.log(left,right)
//输入最后一个
res.push([left,right])
return res
监控二叉树
后序遍历+状态判断
贪心问题：局部-》全局
区间问题先排序，然后注意二维数组的使用，一维points，二维points[i]
输入输出
因篇幅问题不能全部显示，请点此查看更多更全内容