LeetCode HOT 100 之总结记录
5. 最长回文串
给你一个字符串 s，找到 s 中最长的回文子串。
使用中心扩散法，使每个字符都充当回文串的中心
此时就需要分情况讨论，中心为1个数还是2个，即回文串为奇数还是偶数；若当前访问字符满足回文串条件（在s中且相同），则继续向外扩散，直到不满足条件
/**
* @param {string} s
* @return {string}
*/
var longestPalindrome = function(s) {
let res=''
for(let i=0;i<s.length;i++){
getString(i,i)
getString(i,i+1)
}
function getString(i,j){
while((i>=0) && (j<s.length) && (s[i]===s[j])){
i--,j++
}
if(j-i-1>res.length){
res=s.slice(i+1,j)
}
}
return res
};17. 电话号码的字母结合
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。 给出数字到字母的映射与电话按键相同，注意 1 不对应任何字母。
可能算是第一次把回溯写出来，其实好像也不难
首先要搞清楚为什么需要回溯？
在这道题里面，如果指定输入数字的长度，其实是可以用循环的，但是并没有，所以你需要自行判断什么时候到达末尾，且在逐步到达末尾的过程中，你需要做一些操作来获得所要求的东西
回溯先是尝试一条路走到黑，然后退回一步，寻找其他出路，再次走到黑，再次回退，直到走遍所有路
回溯函数中需要指定走到的层数以及在这个过程中一直被修改和引用的变量；在回溯函数开头还需要添加判断是否走到尽头的函数：如果是，则做一些操作、返回；如果不是，则继续向下走
如下是这道题的回溯函数：
function recall(floor,str){
if(floor===digits.length){
res.push(str)
return
}
let n=Number(digits[floor])
let t=nums[n-2]
for(let i=0;i<t.length;i++){
str += t[i]
recall(floor+1,str)
str = str.slice(0, str.length - 1)
}
}20. 有效的括号
给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串 s ，判断字符串是否有效。 有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
这道题不难，使用栈的思想就好了，要多考虑特殊情况，比如只有一个字符，或者输入的是”((((“，还需最后判断栈是否为空
/**
* @param {string} s
* @return {boolean}
*/
var isValid = function(s) {
if(s.length===1){
return false
}
let left=['(','[','{']
let right=[')',']','}']
let arr=[]
let i=0
while(i<s.length){
if(left.indexOf(s[i])>=0){
arr.push(s[i])
}else{
let t=arr.pop()
let index1=left.indexOf(t)
let index2=right.indexOf(s[i])
if(index1!==index2){
return false
}
}
i++
}
if(arr.length){
return false
}
return true
};53. 最大子数组和
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组 是数组中的一个连续部分
:star:动态规划
因为我们需要的是最大和的连续子数组，我们无法确定最大的连续子数组会包含哪些数，所以我们需要求出每个数被包含时的最大子数组
又因为无法确定当前查询的数在包含它的最大子数组中的位置，所以我们暂定其为末尾
所以我们目前需要求的就是以每个数为结尾的最大子数组和
那么此时就可以想到动态规划了，大问题可以拆分为小问题求解：以目前的数为结尾的最大子数组和与他前面的数的最大子数组和息息相关，该数的最大子数组和=Math.max(前面的数的最大子数组和+该数，该数)
/**
* @param {number[]} nums
* @return {number}
*/
var maxSubArray = function(nums) {
let pre=0
let res=nums[0]
nums.forEach(item =>{
pre=Math.max(item,item+pre)
res=Math.max(res,pre)
})
return res
};70. 爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
:star:动态规划
/**
* @param {number} n
* @return {number}
*/
var climbStairs = function(n) {
let arr=[]
arr[0]=0
arr[1]=1
arr[2]=2
let i=3
while(i<=n){
arr[i]=arr[i-1]+arr[i-2]
i++
}
return arr[n]
};94. 二叉树的中序遍历
给定一个二叉树的根节点 root ，返回它的 中序 遍历。
多写几遍，要注意代码和思路的整体性
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
var inorderTraversal = function(root) {
if(!root){
return []
}
let res=[]
check(root)
return res
function check(node){
if(node===null){
return
}else{
check(node.left)
res.push(node.val)
check(node.right)
}
}
};101. 对称二叉树
给你一个二叉树的根节点 root ， 检查它是否轴对称。
需要注意的就是特殊情况的判断，如两个node都为空或者有一个node为空一个不为空；仍然需要注意整体性
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {boolean}
*/
var isSymmetric = function(root) {
if(!root.left && !root.right){
return true
}
let res=check(root.left,root.right)
return res
function check(node1,node2){
if(!node1 && !node2){
return true
}if(!node1 || !node2){
return false
}
let l=check(node1.left,node2.right)
let r=check(node1.right,node2.left)
if(node1.val===node2.val && l && r){
return true
}
return false
}
};104. 二叉树的最大深度
给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
如果没有节点，深度为0
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
var maxDepth = function(root) {
var res=0
check(root,0)
function check(node,depth){
if(!node){
res=Math.max(res,depth)
return
}
check(node.left,depth+1)
check(node.right,depth+1)
}
return res
};
136. 只出现一次的数字
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
- 使用两个数组，一个存正数，一个存负数，最后用indexOf查找值为1的
- 使用集合，若集合中有该数就删除，如果没有就添加，最后剩下的就是所要求的
- 计算所有数之和以及出现过的数的2倍和，相减就是所求的数
- 【秒哉】使用异或，相同的数异或是0，数和0异或之后还是该数，该题中只有一个数会出现一次，其余的均出现两次，所以将所有数异或，最后得到的就是所求的
141. 环形链表
给你一个链表的头节点 head ，判断链表中是否有环。如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。如果链表中存在环 ，则返回 true 。 否则，返回 false 。
使用快慢指针，如果快的追上慢的，说明有环；还需要注意特殊情况比如right.next、right.next.next是否为null (下面部分代码省略了树结构)
var hasCycle = function(head) {
if(!head){
return false
}
let left=head,right=head
while(right){
left=left.next
if(!right.next || !right.next.next){
return false
}
right=right.next.next
if(left===right){
return true
}
}
};155. 最小栈
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。 实现 MinStack 类: MinStack() 初始化堆栈对象。 void push(int val) 将元素val推入堆栈。 void pop() 删除堆栈顶部的元素。 int top() 获取堆栈顶部的元素。 int getMin() 获取堆栈中的最小元素。
好几次都做不对的一个点：在初始化函数中，要this.arr=[]，不要var arr=[]
要记住，栈顶是哪里
栈顶不是arr[0]，是arr最末尾
226. 反转二叉树
给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
多琢磨这个思想，递归
var invertTree = function(root) {
if(!root){
return root
}
reverse(root)
return root
function reverse(node){
if(!node){
return node
}
reverse(node.left)
reverse(node.right)
let tem=node.left
node.left=node.right
node.right=tem
}
};更简洁的版本,直接调用该函数本身一直递归：
var invertTree = function(root) {
if(!root){
return root
}
invertTree(root.left)
invertTree(root.right)
let tem=root.left
root.left=root.right
root.right=tem
return root
};234. 回文链表
给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
先存在数组中，然后根据长度是奇数还是偶数来进行不同的操作
var isPalindrome = function(head) {
let arr=[],l,r
while(head){
arr.push(head.val)
head=head.next
}
if(arr.length%2===0){
r=arr.length/2
l=r-1
}else{
let center=parseInt(arr.length/2)
l=center-1,r=center+1
}
while(l>=0 && r<arr.length){
if(arr[l]!==arr[r]){
return false
}
l--,r++
}
return true
};**338. 比特位计数
Brian Kernighan 算法很迷的一点是，下面这两段表示的是一个意思，但是下面那个就会超时超时：
动态规划 最高有效位
var countBits = function(n) {
var arr=new Array(n+1).fill(0)
let high=0
for(let i=1;i<=n;i++){
if((i&(i-1))==0){
high=i
}
arr[i]=arr[i-high]+1
}
return arr
};动态规划 最低有效位
动态规划 最低设置位
总的来说，两个方向：
- 使用x=x&(x-1)，挨个计算每个数，直到x为0
- 动态规划
- bits[i]=bits[i-highbit]+1
- bits[i]=bits[i>>1]+(i&1)
- bits[i]=bits[i&(i-1)]+1
545. 二叉树的直径
给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。
注意读题！可能不穿过根节点。所以要记录l+r的最大值
var diameterOfBinaryTree = function(root) {
var num=0
getLong(root)
function getLong(node){
if(!node){
return -1
}
let l=getLong(node.left)+1
let r=getLong(node.right)+1
num=Math.max(num,l+r)
return Math.max(l,r)
}
return num
};腾讯云开发者
