数据结构与算法

动态规划

最长回文子串

i,j索引间的字符串的判断可以有i+1,j-1之间的字符串是否是回文串得出

我们就可以得出状态转移方程:dp[i][j]=dp[i+1][j-1]

另外只有一位长度的字符串不用判断,(i-1)-(i+1)<1 ==> j-i<3,满足这个条件为回文串

/**
* @param {string} s
* @return {string}
*/
var longestPalindrome = function(s) {
const n=s.length;
const dp = Array.from(s).reduce((acc)=>{
const fillArr = new Array(n);
acc.push(fillArr)
return acc
},[])
let maxLen=1,maxIndex=0;
for(let j=1;j<n;j++){
for(let i=0;i<j;i++){
if(s[i]===s[j]){
if(j-i<3){
dp[i][j]=true;
}else{
dp[i][j]=dp[i+1][j-1];
}
}else{
dp[i][j]=false;
}
if(dp[i][j]&&j-i+1>maxLen){
maxIndex=i;
maxLen=j-i+1;
}
}
}
return s.substring(maxIndex,maxIndex+maxLen)
};

连续子数组的最大和

/**
* @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;
};

最长连续递增序列

/**
* @param {number[]} nums
* @return {number}
*/
var findLengthOfLCIS = function(nums) {
let count=1;
let dp=new Array(nums.length).fill(1);
for(let i=1;i<nums.length;i++){
for(let j=0;j<i;j++){
if(nums[i]>nums[j]){
dp[i]=Math.max(dp[i],dp[j]+1);
if(count<dp[i])count=dp[i];
}
}
}
return count;
};
// 贪心解法
/**
* @param {number[]} nums
* @return {number}
*/
var findLengthOfLCIS = function(nums) {
if(nums.length===0)return 0;
let res=1,count=1;
for(let i=0;i<nums.length-1;i++){
if(nums[i+1]>nums[i]){
count++;
}else{
count=1;
}
if(count>res)res=count;
}
return res;
};

俄罗斯套娃信封问题

/**
* @param {number[][]} envelopes
* @return {number}
*/
var maxEnvelopes = function(envelopes) {
envelopes = envelopes.sort((a,b)=>{
if(a[0]===b[0]){
return a[1]-b[1];
}else{
return a[0]-b[0];
}
})
let count=1;
let dp=new Array(envelopes.length).fill(1);
for(let i=1;i<envelopes.length;i++){
for(let j=0;j<i;j++){
if((envelopes[i][1]>envelopes[j][1])&&(envelopes[i][0]>envelopes[j][0])){
dp[i]=Math.max(dp[i],dp[j]+1);
if(dp[i]>count)count=dp[i];
}
}
}
return count;
};

贪心算法

二分查找

寻找旋转排序数组中的最小值

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;
};

二叉树

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;
};

验证二叉树的前序序列化

模拟前序遍历,用栈存储节点,当两个'#'连着出现时,代表栈尾最后一个非空节点遍历完成

  1. 当前为'#',栈顶也是'#',则出栈两位,出栈过程中如果栈空,直接返回false,并循环判断当前栈顶是不是'#',直到不是后入栈'#'

  2. 最后栈只剩一个元素且为'#'时返回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. 先计算两个不同的数字的异或值

  2. 再计算出这个异或值中某个1位,也就是用来两个数字是不同的位数

  3. 将数组中的值分组异或

/**
* @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]
};

前缀和

区域和检索 - 数组不可变

数组前缀和

/**
* @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)
*/