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;};
从上到下打印二叉树 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=falseconst ret=[]while(queue.length){const tmp=[]const len=queue.lengthfor(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=!directret.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) returntar -= node.valpath.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]};
数组前缀和
/*** @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.lengthif(colLen===0){this.isEmpty=truereturn}const rowLen=matrix[0].lengthif(rowLen===0){this.isEmpty=truereturn}this.rowLen=rowLenthis.colLen=colLenthis.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)*/