数据结构与算法
动态规划
连续子数组的最大和
/**
* @param {number[]} nums
* @return {number}
*/
var maxSubArray = function(nums) {
let pre=0,max=-Infinity;
nums.forEach(v=>{
pre=Math.max(v+pre,v);
max=Math.max(max,pre);
})
return max;
};贪心算法
二分查找
寻找旋转排序数组中的最小值
function findMin(nums: number[]): number {
let i=0,j=nums.length-1;
let min = Infinity;
while(i<=j){
let mid = Math.floor((j-i)/2)+i;
if(nums[mid]>min){
if(nums[mid]<nums[j]){
j=mid-1;
}else{
i=mid+1;
}
}else{
min=nums[mid];
if(nums[mid]<nums[j]){
j=mid-1;
}else{
i=mid+1;
}
}
}
return min;
}; 搜索旋转排序数组
function search(nums: number[], target: number): number {
let l=0,r=nums.length-1;
let mid;
while(l<=r){
mid=Math.floor((r-l)/2)+l;
const rightIsSort:boolean=nums[mid]<nums[r];
if(nums[mid]===target){
return mid;
}else if(nums[mid]>target){
if(!rightIsSort){
if(nums[r]<target){
r=mid-1;
}else{
l=mid+1;
}
}else{
r=mid-1;
}
}else{
if(rightIsSort){
if(nums[r]<target){
r=mid-1;
}else{
l=mid+1;
}
}else{
l=mid+1;
}
}
}
return -1;
};在 D 天内送达包裹的能力
class Solution {
public:
int shipWithinDays(vector<int>& weights, int D) {
int max=0,sum=0;
for(int val:weights){
if(val>max)max=val;
sum+=val;
}
while(max<sum){
int mid=(sum+max)/2;
int curDay = calDays(weights,mid);
if(curDay>D){
max=mid+1;
}else if(curDay<=D){
sum=mid;
}
}
return max;
}
int calDays(vector<int>& weights,int weight){
int D=0;
int sum=0;
for(int val:weights){
if((sum+val)>weight){
D++;
sum=val;
}else if((sum+val)==weight){
D++;
sum=0;
}else{
sum+=val;
}
}
if(sum!=0)D++;
return D;
}
};二叉树
DFS
BFS
从上到下打印二叉树 III
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number[][]}
*/
var levelOrder = function(root) {
if(!root)return []
const queue=[root]
let direct=false
const ret=[]
while(queue.length){
const tmp=[]
const len=queue.length
for(let i=0;i<len;i++){
const curNode = queue.shift()
tmp.push(curNode.val)
curNode.left&&queue.push(curNode.left)
curNode.right&&queue.push(curNode.right)
}
if(direct){
tmp.reverse()
}
direct=!direct
ret.push(tmp)
}
return ret
};链表
两个链表的第一个公共节点
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} headA
* @param {ListNode} headB
* @return {ListNode}
*/
var getIntersectionNode = function(headA, headB) {
let p1=headA;
let p2=headB;
while(p1!=p2){
p1 = p1?p1.next:headA;
p2 = p2?p2.next:headB;
}
return p1;
};两数相加
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} l1
* @param {ListNode} l2
* @return {ListNode}
*/
var addTwoNumbers = function(l1, l2) {
let ret=[];
let n=0;
while(l1||l2){
let num1=0,num2=0;
if(l1){
num1=l1.val;
l1=l1.next;
}
if(l2){
num2=l2.val;
l2=l2.next;
}
let count=num1+num2+n;
n=count>=10?1:0;
count%=10;
ret.push(count);
}
if(n===1)ret.push(n);
let head = new ListNode();
let node=head;
ret.forEach((value)=>{
node.next = new ListNode(value);
node=node.next;
})
return head.next;
};栈
验证二叉树的前序序列化
模拟前序遍历，用栈存储节点，当两个'#'连着出现时，代表栈尾最后一个非空节点遍历完成
当前为'#'，栈顶也是'#',则出栈两位，出栈过程中如果栈空，直接返回false，并循环判断当前栈顶是不是'#'，直到不是后入栈'#'
最后栈只剩一个元素且为'#'时返回true
/**
* @param {string} preorder
* @return {boolean}
*/
var isValidSerialization = function(preorder) {
const preorderArr = preorder.split(',');
const stack=[preorderArr.shift()];
for(let i=0;i<preorderArr.length;i++){
if(preorderArr[i]==='#'){
while(stack[stack.length-1]==='#'){
stack.pop();
if(!stack.length)return false;
stack.pop();
}
stack.push('#');
}else{
stack.push(preorderArr[i]);
}
}
return stack.length===1&&stack[0]==='#';
}; 逆波兰表达式求值
/**
* @param {string[]} tokens
* @return {number}
*/
var evalRPN = function(tokens) {
const stack=[];
let res=0;
if(tokens.length<2){
return tokens[0]||res
}
for(let i=0;i<tokens.length;i++){
if(!Number.isNaN(Number(tokens[i]))){
stack.push(Number(tokens[i]));
}else{
const numR=stack.pop();
const numL=stack.pop();
if(tokens[i]==='+'){
res=numL+numR;
}else if(tokens[i]==='-'){
res=numL-numR;
}else if(tokens[i]==='*'){
res=numL*numR;
}else{
res=numL/numR;
if(res>0){
res=Math.floor(res)
}else{
res=Math.ceil(res)
}
}
stack.push(res)
}
}
return res;
};每日温度
单调栈
/**
* @param {number[]} T
* @return {number[]}
*/
var dailyTemperatures = function(T) {
const ret=new Array(T.length).fill(0);
const stack=[];
for(let i=0;i<T.length;i++){
const obj={index:i,value:T[i]};
while(stack.length&&T[i]>stack[stack.length-1].value){
const top = stack[stack.length-1];
const {index,value}=top;
ret[index]=i-index;
stack.pop();
}
stack.push(obj);
}
return ret;
};队列
堆
回溯
二叉树中和为某一值的路径
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @param {number} sum
* @return {number[][]}
*/
var pathSum = function (root, sum) {
const res = []
const path = []
function recur(node, tar) {
if (!node) return
tar -= node.val
path.push(node.val)
if (tar === 0 && !node.left && !node.right) {
res.push([...path])
}
recur(node.left, tar)
recur(node.right, tar)
path.pop()
}
recur(root, sum)
return res
}全排列
/**
* @param {number[]} nums
* @return {number[][]}
*/
var permute = function(nums) {
let res=[],track=[];
function backTrack(res,track,nums){
if(track.length===nums.length){
res.push([...track]);
return;
}
for(let i=0;i<nums.length;i++){
if(track.find(v=>v===nums[i])!==undefined){
continue;
}
track.push(nums[i]);
backTrack(res,track,nums);
track.pop();
}
}
backTrack(res,track,nums);
return res;
};位运算
异或
相同的数异或为0
数组中数字出现的次数
先计算两个不同的数字的异或值
再计算出这个异或值中某个1位,也就是用来两个数字是不同的位数
将数组中的值分组异或
/**
* @param {number[]} nums
* @return {number[]}
*/
var singleNumbers = function(nums) {
let n=0;
nums.forEach(num=>{
n^=num;
})
let k=1;
while((k&n)===0){
k<<=1;
}
let a=0,b=0;
nums.forEach(num=>{
if(num&k){
a^=num;
}else{
b^=num;
}
})
return [a,b]
};前缀和
矩形区域不超过 K 的最大数值和
function maxSumSubmatrix(matrix: number[][], k: number): number {
const y=matrix.length,x=matrix[0].length;
const sum=new Array(y+1);
for(let i=0;i<=y;i++)sum[i]=new Array(x+1);
let max=-Infinity;
for(let i=1;i<=x;i++){
for(let j=1;j<=y;j++){
sum[j][i]=matrix[j-1][i-1]+(sum[j][i-1]||0)+(sum[j-1][i]||0)-(sum[j-1][i-1]||0);
}
}
for(let i=1;i<=x;i++){
for(let j=1;j<=y;j++){
for(let p=i;p<=x;p++){
for(let q=j;q<=y;q++){
let cur = sum[q][p]-(sum[q][i-1]||0)-(sum[j-1][p]||0)+(sum[j-1][i-1]||0);
if(cur>max&&cur<=k)max=cur;
}
}
}
}
return max;
};区域和检索 - 数组不可变
数组前缀和
/**
* @param {number[]} nums
*/
var NumArray = function(nums) {
this.cache=[]
nums.reduce((acc,cur,index)=>this.cache[index]=(acc+cur),0)
};
/**
* @param {number} i
* @param {number} j
* @return {number}
*/
NumArray.prototype.sumRange = function(i, j) {
return this.cache[j]-(this.cache[i-1]||0)
};
/**
* Your NumArray object will be instantiated and called as such:
* var obj = new NumArray(nums)
* var param_1 = obj.sumRange(i,j)
*/二维区域和检索 - 矩阵不可变
二维数组前缀和
/**
* @param {number[][]} matrix
*/
var NumMatrix = function(matrix) {
const colLen=matrix.length
if(colLen===0){
this.isEmpty=true
return
}
const rowLen=matrix[0].length
if(rowLen===0){
this.isEmpty=true
return
}
this.rowLen=rowLen
this.colLen=colLen
this.rowCache=new Array(colLen)
this.colCache=new Array(colLen)
for(let i=0;i<colLen;i++){
this.rowCache[i]=new Array(rowLen).fill(0)
}
for(let i=0;i<colLen;i++){
matrix[i].reduce((acc,cur,index)=>this.rowCache[i][index]=(acc+cur),0)
}
};
/**
* @param {number} row1
* @param {number} col1
* @param {number} row2
* @param {number} col2
* @return {number}
*/
NumMatrix.prototype.sumRegion = function(row1, col1, row2, col2) {
if(this.isEmpty)return 0;
if(row1>this.colLen){row1=this.colLen}
if(row2>this.colLen){row2=this.colLen}
if(col1>this.rowLen){col1=this.rowLen}
if(col2>this.rowLen){col2=this.rowLen}
let res=0;
for(;row1<=row2;row1++){
res+=this.rowCache[row1][col2]-(this.rowCache[row1][col1-1]||0)
}
return res;
};
/**
* Your NumMatrix object will be instantiated and called as such:
* var obj = new NumMatrix(matrix)
* var param_1 = obj.sumRegion(row1,col1,row2,col2)
*/Last updated