一、腾讯精选练习
按照难度从简单到困难排列
- 删除链表中的节点（237）
var deleteNode = function(node) {
node.val = node.next.val;
node.next = node.next.next;
};
- 二叉树最大深度（104）
var maxDepth = function(root) {
if(root === null) return 0
return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1
};
- Nim游戏(292)
var canWinNim = function(n) {
if(n%4===0) return false
return true
};
- 反转字符串中的单词 III(557)
var reverseWords = function(s) {
return s.split(' ').map(x=>x.split('').reverse().join('')).join(' ')
};
- 反转字符串(344)
var reverseString = function(s) {
let len = s.length
let temp
for(let i=0;i<len/2;i++){
temp = s[len-i-1]
s[len-i-1]=s[i]
s[i]=temp
}
};
- 反转链表(206)
注：用了n的额外空间
其它：1原地修改双指针加临时变量，2递归
// 原地反转
temp = p.next
p.next = pre
pre = p
p = temp
// 递归
HEAD = reverseList(head->next);
head->next->next = head;
head->next = NULL;
return HEAD;
var reverseList = function(head) {
let p = head
let arr = []
if(head === null) return head
while(p !== null){
arr.push(p.val)
p=p.next
}
arr.reverse()
let res = new ListNode(arr[0])
let p2 = res
for(let i=1;i<arr.length;i++){
p2.next = new ListNode(arr[i])
p2 = p2.next
}
p2.next = null
return res
};
- 只出现一次的数字(136)
注：用了异或
var singleNumber = function(nums) {
let res = 0
nums.forEach(x=>{
res = res ^ x
})
return res
};
- 二叉搜索树的最近公共祖先(235)
var lowestCommonAncestor = function(root, p, q) {
if(p===null||q===null||root===null){
return null;
}
if(root.val>=p.val&&root.val<=q.val) return root
if(root.val>p.val&&root.val>q.val) {
return lowestCommonAncestor(root.left,p,q)
}
if(root.val<p.val&&root.val<q.val) {
return lowestCommonAncestor(root.right,p,q)
}
return root
};
- 求众数(169)
var majorityElement = function(nums) {
nums.sort((a,b)=>a-b)
return nums[Math.floor(nums.length/2)]
};
- 合并两个有序链表
注：也可以用递归，剑指offer有
var mergeTwoLists = function(l1, l2) {
if (l1 === null) return l2
if (l2 === null) return l1
l3 = new ListNode(4)
p3 = l3
p1 = l1
p2 = l2
while(p1 !== null && p2 !==null){
if(p1.val <= p2.val){
p3.next = p1
p3 = p3.next
p1 = p1.next
} else {
p3.next = p2
p3 = p3.next
p2 = p2.next
}
}
if(p1 === null) {
p3.next = p2
} else {
p3.next = p1
}
return l3.next
};
- 回文数(9)
var isPalindrome = function(x) {
if(x.toString() === x.toString().split('').reverse().join('')){
return true
}else{
return false
}
};
- 买卖股票的最佳时机 II
var maxProfit = function(prices) {
if(prices.length===0) return 0
let res = 0
let min = prices[0]
for(let i=1;i<prices.length;i++){
if(prices[i]<prices[i-1]){
res = res + prices[i-1]-min
min = prices[i]
}
}
return res + prices[prices.length-1]-min
};
- 买卖股票的最佳时机
var maxProfit = function(prices) {
if(prices.length === 0) return 0
let res = 0
let min = prices[0]
for(let i=1;i<prices.length;i++){
if(prices[i]>min){
res = Math.max(prices[i]-min,res)
} else {
min = prices[i]
}
}
return res
};
- 存在重复元素
var containsDuplicate = function(nums) {
if((new Set(nums)).size === nums.length){
return false
} else {
return true
}
};
- 最小栈
/**
* initialize your data structure here.
*/
var MinStack = function() {
this.data = [];
};
/**
* @param {number} x
* @return {void}
*/
MinStack.prototype.push = function(x) {
this.data.push(x)
};
/**
* @return {void}
*/
MinStack.prototype.pop = function() {
this.data.pop()
};
/**
* @return {number}
*/
MinStack.prototype.top = function() {
return this.data[this.data.length-1]
};
/**
* @return {number}
*/
MinStack.prototype.getMin = function() {
return Math.min(...this.data)
};
/**
* Your MinStack object will be instantiated and called as such:
* var obj = new MinStack()
* obj.push(x)
* obj.pop()
* var param_3 = obj.top()
* var param_4 = obj.getMin()
*/
- 相交链表
注意：AB长度相加消除长度差异
- 相交链表
var getIntersectionNode = function(headA, headB) {
while(headB===null || headA===null) return null
let pA=headA,pB=headB
while(pA !== pB){
if(pA===null){
pA = headB
} else {
pA = pA.next
}
if(pB===null){
pB = headA
} else {
pB = pB.next
}
}
return pB
};
- 最大子序和
注：滑动窗口
- 最大子序和
var maxSubArray = function(nums) {
let res = nums[0]
let sum = 0
for(const num of nums){
if(sum>0){
sum += num
} else {
sum = num
}
res = Math.max(res,sum)
}
return res
};
- 爬楼梯
注：斐波拉契
- 爬楼梯
var climbStairs = function(n) {
if(n===1) return 1
if(n===2) return 2
let num1 = 1;
let num2 = 2;
for(let i=0;i<n-2;i++){
let temp = num2
num2 = num2 + num1
num1 = temp
}
return num2
};
- 2的幂
var isPowerOfTwo = function(n) {
if(+(n.toString(2).split('').reverse().join('')) === 1){return true}
return false
};
- 删除排序数组中的重复项
var removeDuplicates = function(nums) {
let cur = nums[0]
for(let i = 1;i<nums.length;){
if(nums[i] === cur){
nums.splice(i,1)
} else {
cur = nums[i]
i++
}
}
};
- 合并两个有序数组
var merge = function(nums1, m, nums2, n) {
nums1.splice(m,n,...nums2)
nums1.sort((a,b)=>(a-b))
};
- 环形链表
var hasCycle = function(head) {
if(head === null || head.next === null) return false
let slow = head
let fast = head.next
while(slow !== fast){
if(fast === null || fast.next === null) return false
fast = fast.next.next
slow = slow.next
}
return true
};
- 有效括号
注：用栈
- 有效括号
var isValid = function (s) {
const dict = {
'(':')',
'[':']',
'{':'}',
}
let stack = []
for (let i = 0; i < s.length; i++) {
if(s[i]==='('||s[i]==='['||s[i]==='{'){
stack.push(s[i])
} else if(dict[stack[stack.length-1]] === s[i]){
stack.pop()
} else {
return false
}
}
if(stack.length>0) return false
return true
};
- 最长公共前缀
var longestCommonPrefix = function(strs) {
if (strs.length === 0) return ''
let pre = ''
let str = strs[0]
for(let j=0;j<str.length;j++){
let s = str[j]
for(let i=1;i<strs.length;i++){
if(strs[i][j]!==s) {
return pre
}
}
pre = pre+s
}
return pre
};
- 整数反转
var reverse = function(x) {
let num
if(x>0){
num = parseInt((''+x).split('').reverse().join(''))
} else {
num = -((-x).toString().split('').reverse().join(''))
}
if(num>(2**31-1)||num<-(2**31)){
return 0
} else {
return num
}
};
- 螺旋矩阵 II
注意： let arr = new Array(3).fill([]),每行都是引用一个地址
- 螺旋矩阵 II
var generateMatrix = function (n) {
let l = 0, r = n - 1, t = 0, b = n - 1;
let mat = [...Array(n)].map(x=>[])
let num = 1, tar = n * n;
while (num <= tar) {
for (let i = l; i <= r; i++) {
mat[t][i] = num++; // left to right.
}
t++;
for (let i = t; i <= b; i++) {
mat[i][r] = num++; // top to bottom.
}
r--;
for (let i = r; i >= l; i--) {
mat[b][i] = num++; // right to left.
}
b--;
for (let i = b; i >= t; i--) {
mat[i][l] = num++; // bottom to top.
}
l++;
}
return mat;
};
- 子集
var subsets = function(nums) {
if(nums.length===0) return [[]]
let sub = subsets(nums.slice(1))
let res = []
let a = nums[0]
for(let i=0;i<sub.length;i++){
res.push([a,...sub[i]])
}
return [...res,...sub]
};
- 全排列
var permute = function(nums) {
if(nums.length === 1) return [[nums[0]]]
let res = []
let sub = permute(nums.slice(1))
for(let i=0;i<sub.length;i++){
for(let j=0;j<nums.length;j++){
let temp = [...sub[i]]
temp.splice(j,0,nums[0])
res.push(temp)
}
}
console.log(res.length)
return res
};
- 二叉搜索树中第K小的元素
注：中序遍历
- 二叉搜索树中第K小的元素
var kthSmallest = function(root, k) {
if(root === null) return root
var stack = [];
var container = []
var curr = root
while(curr || stack.length){
if(curr !== null){
stack.push(curr)
curr = curr.left
} else {
let node = stack.pop()
container.push(node.val)
if(container.length === k) break;
curr = node.right
}
}
return container.pop()
};
- 格雷编码
注：每次只变一个二进制位，在电路中可以少翻转电路
- 格雷编码
var grayCode = function(n) {
if(n===0) return [0]
if(n===1) return [0,1]
let sub = grayCode(n-1)
return [...sub.map(x=>parseInt(x.toString(2)+'0',2)),...[...sub].reverse().map(x=>parseInt(x.toString(2)+'1',2))]
};
- 除自身以外数组的乘积
注：没有用除法，左边乘积数组和右边乘积数组
- 除自身以外数组的乘积
var productExceptSelf = function(nums) {
let temp = 1
let pre = nums.map(x=>{
temp = temp*x
return temp
})
pre.pop()
pre.unshift(1)
temp = 1
let after = [...nums].reverse().map(x=>{
temp = temp*x
return temp
})
after.pop()
after.unshift(1)
after.reverse()
return pre.map((x,i)=>x*after[i])
};
- 排序链表
var sortList = function(head) {
if(head === null || head.next === null) return head
let p = head
let arr = []
while(p !== null){
arr.push(p.val)
p = p.next
}
arr.sort((a,b)=>a-b)
p = head
arr.forEach(x=>{
p.val = x
p = p.next
})
return head
};
- 数组中第k个最大元素
var findKthLargest = function(nums, k) {
let max = 0
while(k){
k--
max = Math.max(...nums)
let index = nums.indexOf(max)
nums.splice(index,1)
}
return max
};
- 盛最多水的容器
var maxArea = function(height) {
if(height.length===2){
return Math.min(...height)
}
let flag = height.pop()
let len = height.length
let max = 0
for(let i=0;i<height.length;i++){
max = Math.max(max,(len-i)*(Math.min(flag,height[i])))
}
return Math.max(max,maxArea(height))
};
- 二叉树的最近公共祖先
var lowestCommonAncestor = function(root, p, q) {
if (!root || root === p || root === q) {
return root;
}
var left = lowestCommonAncestor(root.left,p,q)
var right = lowestCommonAncestor(root.right,p,q)
if (left && right) {
return root;
}
return left ? left : right;
};
- 不同路径
简单的dp
var uniquePaths = function(m, n) {
if(n===1) return 1
if(m===1) return 1
function factorial(n, total) {
if (n === 1) return total;
return factorial(n - 1, n * total);
}
return factorial(m+n-2,1)/factorial(n-1,1)/factorial(m-1,1)
};
- 环形链表
快慢指针
var detectCycle = function(head) {
var fast = head, slow = head;
while (true) {
if (fast == null || fast.next == null) return null;
fast = fast.next.next;
slow = slow.next;
if (fast == slow) break;
}
fast = head;
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return fast;
};
146.LRU缓存机制
最近最少，用队列，put入队如果满了就出队，get找出原来的数据删除并重新入队
var LRUCache = function(capacity) {
this.cache = new Map()
this.capacity = capacity
};
/**
* @param {number} key
* @return {number}
*/
LRUCache.prototype.get = function(key) {
let cache = this.cache;
if (cache.has(key)) {
let temp = cache.get(key)
cache.delete(key);
cache.set(key, temp);
return temp;
} else {
return -1;
}
};
/**
* @param {number} key
* @param {number} value
* @return {void}
*/
LRUCache.prototype.put = function(key, value) {
let cache = this.cache;
if (cache.has(key)) {
cache.delete(key);
} else if (cache.size >= this.capacity) {
cache.delete(cache.keys().next().value);
}
cache.set(key, value);
};
- 最接近的三数之和
最接近两数之和用双指针，就可以只遍历一遍
两数之和用hash
var threeSumClosest = function(nums, target) {
nums.sort((m,n)=>m-n)
let ans = nums[0]+nums[1]+nums[2]
for(let i=0;i<nums.length;i++){
let start=i+1
let end = nums.length -1
while(start<end){
let sum = nums[i]+nums[start]+nums[end]
if(Math.abs(sum-target)<(Math.abs(ans-target))){
ans = sum
}
if(sum>target){
end--
} else if(sum<target){
start++
} else {
return ans
}
}
}
return ans
};
- 字符串相乘
题意用普通的乘法，大数相乘再大数相加
var multiply = function(num1, num2) {
return ((BigInt(num1)*BigInt(num2))+ "")
};
- 旋转链表
先找到最后的节点，再找旋转点
var rotateRight = function(head, k) {
if(!head || !k) return head
let p = head
let len = 1
while(p.next){
p=p.next
len++
}
p.next = head
let off = len - (k%len)
for(let i=0;i<off;i++){
p=p.next
}
let res = p.next
p.next = null
return res
};
- 螺旋矩阵
注意边界
var spiralOrder = function(matrix) {
let n = matrix.length
if(n===0) return []
let m = matrix[0].length
let l = 0, r = m - 1, t = 0, b = n - 1;
let res = []
let nums = 1, target = n * m;
while (nums<=target) {
for (let i = l; i <= r; i++) {
res.push(matrix[t][i]) // left to right.
nums++
}
if(nums>target) break;
t++;
for (let i = t; i <= b; i++) {
res.push(matrix[i][r]); // top to bottom.
nums++
}
if(nums>target) break;
r--;
for (let i = r; i >= l; i--) {
res.push(matrix[b][i]); // right to left.
nums++
}
if(nums>target) break;
b--;
for (let i = b; i >= t; i--) {
res.push(matrix[i][l]); // bottom to top.
nums++
}
l++;
}
return res;
};
- 两数相加
var addTwoNumbers = function(l1, l2) {
let p1 = l1
let p2 = l2
let res = new ListNode(0)
let p = res
let flag = 0
while(p1!==null||p2!==null){
let x = (p1 !== null)?p1.val:0
let y = (p2 !== null)?p2.val:0
let node = new ListNode(parseInt((x+y+flag)%10))
if(res === null){
p = node
} else {
p.next = node
}
p = p.next
flag = (x+y+flag)>9?1:0
if(p1 !== null) p1 = p1.next
if(p2 !== null) p2 = p2.next
}
if (flag > 0) {
p.next = new ListNode(flag);
}
return res.next
};
- 搜索旋转排序数组
变形的二分
var search = function(nums, target) {
var low = 0;
var high = nums.length - 1;
while (low <= high) {
var mid = Math.floor((low + high) / 2);
if (nums[mid] === target) return mid;
if (nums[low] <= nums[mid]) {
if (nums[low] <= target && nums[mid] > target) {
high = mid - 1;
} else {
low = mid + 1;
}
} else {
if (target <= nums[high] && target > nums[mid]) {
low = mid + 1;
} else {
high = mid - 1;
}
}
}
return -1;
};
- 最长回文子串
两个数之间的空格也可以是回文的中心
var longestPalindrome = function(s) {
let arr = []
for(let i=0;i<s.length;i++){
let temp = s[i]
for(j=1;(i+j<s.length) && ((i-j)>=0);j++){
if(s[i+j]===s[i-j]){
temp=s[i+j]+temp+s[i+j]
} else {
break;
}
}
arr.push(temp)
}
for(let i=1;i<s.length;i++){
let temp = ""
for(j=0;i+j<s.length && (i-j)>=0;j++){
if(s[i+j]===s[i-j-1]){
temp=s[i+j]+temp+s[i+j]
} else {
break;
}
}
arr.push(temp)
}
console.log(arr)
let res = ""
for(let i=0;i<arr.length;i++){
if(arr[i].length>res.length){
res = arr[i]
}
}
return res
};
- 三数之和
也可以用hash
var threeSum = function(nums) {
nums.sort((m,n)=>m-n)
let ans = []
for(let i=0;i<nums.length;i++){
while(i<nums.length&&(nums[i]===nums[i-1])) i++
cur = nums[i]
let start=i+1
let end = nums.length -1
while(start<end){
let sum = nums[i]+nums[start]+nums[end]
if(sum>0){
end--
} else if(sum<0){
start++
} else {
ans.push([nums[i],nums[start],nums[end]])
while((start<end)&&(nums[start]===nums[start+1])) {start++}
while((start<end)&&
(nums[end]===nums[end-1])) {end--}
start++
end--
}
}
}
return ans
};
- 字符串转换整数 (atoi)
var myAtoi = function(str) {
let res = parseInt(str)
if(isNaN(res)) return 0
if(res>2147483647) return 2147483647
if(res<-2147483648) return -2147483648
return parseInt(str)
};
- 合并k个链表
var mergeKLists = function (lists) {
if(lists.length===1) return lists[0]
let result = lists[0]
for(let i=1;i<lists.length;i++){
result = Merge(result,lists[i])
}
return result
function Merge(pHead1, pHead2) {
if (pHead1 === null) return pHead2
if (pHead2 === null) return pHead1
let res = null
if (pHead1.val < pHead2.val) {
res = pHead1
res.next = Merge(pHead1.next, pHead2)
} else {
res = pHead2
res.next = Merge(pHead2.next, pHead1)
}
return res
}
};
- 寻找两个有序数组的中位数
var findMedianSortedArrays = function(nums1, nums2) {
let len = nums1.length+nums2.length
let p1=0, p2=0
let res = []
for(let i=0;i<(len/2+1);i++){
if(nums1[p1]>nums2[p2] || (p1===nums1.length)){
res.push(nums2[p2])
p2++
} else {
res.push(nums1[p1])
p1++
}
}
if(len%2===1) {
return res[res.length-2]
} else {
return (res[res.length-1]+res[res.length-2])/2
}
};
二、剑指offer
- 数组中重复数字
hash,set,indexOf
var findRepeatNumber = function(nums) {
let hash = {}
for(let i=0;i<nums.length;i++){
if(hash[nums[i]] === 1){
return nums[i]
} else {
hash[nums[i]] = 1
}
}
};
- 二维数组中的查找
从左下角或者右上角找
var findNumberIn2DArray = function(matrix, target) {
if(matrix===null||matrix.length===0||matrix[0].length===0){
return false
}
let rows=matrix.length, columns=matrix[0].length
let row = 0, column=columns-1
while(row<rows&&column>=0){
let cur = matrix[row][column]
if(cur===target){
return true
}else if(cur>target){
column--
} else {
row++
}
}
return false
};
- 替换空格
正则
var replaceSpace = function(s) {
return s.replace(/ /g,'%20')
};
- 从尾到头打印链表
本题返回数组，只要遍历一遍即可
var reversePrint = function(head) {
let arr = []
let p = head
while(p !== null){
arr.unshift(p.val)
p=p.next
}
return arr
};
- 重建二叉书
知道中序和前序，前序是根，找出中序被根切分的左右，并算出长度。递归
var buildTree = function(preorder, inorder) {
if(preorder.length === 0 || inorder.length === 0) return null
let root = {
val: preorder[0],
left: null,
right: null
}
let i = inorder.indexOf(preorder[0])
root.left = buildTree(preorder.slice(1,1+i),inorder.slice(0,i))
root.right = buildTree(preorder.slice(1+i),inorder.slice(1+i))
return root
};
- 用两个栈实现队列
var CQueue = function() {
this.inStack = []
this.outStack = []
};
/**
* @param {number} value
* @return {void}
*/
CQueue.prototype.appendTail = function(value) {
this.inStack.push(value)
};
/**
* @return {number}
*/
CQueue.prototype.deleteHead = function() {
const {inStack, outStack} = this
if (outStack.length) {
return outStack.pop();
} else {
while (inStack.length) {
outStack.push(inStack.pop());
}
return outStack.pop() || -1;
}
};
10- I. 斐波那契数列 10- II. 青蛙跳台阶问题
var fib = function(n) {
let arr = [0,1]
for(i=2;i<=n;i++){
arr[i]=arr[i-1]+arr[i-2]
arr[i] %= 1000000007
}
return arr[n]
};
- 旋转数组的最小数字
var minArray = function(numbers) {
let start = 0
let end = numbers.length - 1
while(start<end){
let mid = Math.floor((end+start)/2)
if(numbers[mid]>numbers[end]){
start = mid + 1
} else if(numbers[mid]<numbers[end]) {
end = mid
} else {
end--
}
}
return numbers[start]
};
14- I. 剪绳子
var cuttingRope = function(n) {
if(n === 2) return 1
if(n === 3) return 2
if(n === 4) return 4
let res = 1
while(n>4){
res = res*3
n = n-3
}
return res*n
};
14- II. 剪绳子 II
var cuttingRope = function(n) {
if(n === 2) return 1
if(n === 3) return 2
if(n === 4) return 4
let res = 1
while(n>4){
res = res*3
res %= 1000000007;
n = n-3
}
return (res*n)%1000000007
};
- 二进制中1的个数
var hammingWeight = function(n) {
return n.toString(2).split('').reduce((s,x)=>s+Number(x),0)
};
- 打印从1到最大的n位数
var printNumbers = function(n) {
let str = ''
for(i=0;i<n;i++){
str += 9
}
let num = str - 0
let arr = []
for(i=1;i<=num;i++){
arr.push(i)
}
return arr
};
- 删除链表节点
var deleteNode = function(head, val) {
let pre = new ListNode(-1)
pre.next = head
let p = pre
while(p.next){
if(p.next.val === val){
p.next = p.next.next
break
}
p = p.next
}
return pre.next
};
- 正则表达式匹配
var isMatch = function(s, p) {
return new RegExp("^" + p + "$", "g").test(s);
};
- 调整数组顺序使奇数位于偶数前面
var exchange = function(nums) {
let start = 0
let end = nums.length - 1
while(start<end){
if(nums[start]%2 === 0&&(nums[end]%2 === 1)){
let temp = nums[start]
nums[start] = nums[end]
nums[end] = temp
start++
end--
} else {
if(nums[start]%2 === 1) start++
if(nums[end]%2 === 0) end--
}
}
return nums
};
- 链表中倒数第k个节点
var getKthFromEnd = function(head, k) {
let p = head
for(i=0;i<k;i++){
p = p.next
}
let pre = head
while(p !== null){
pre = pre.next
p = p.next
}
return pre
};
- 反转链表
var reverseList = function(head) {
let cur = null
let pre = head
while (pre !== null) {
let p = pre.next
pre.next = cur
cur = pre
pre = p
}
return cur
};
- 合并两个排序的链表
var mergeTwoLists = function(l1, l2) {
let l = new ListNode(0)
let p = l
while(l1 !== null && l2 !== null) {
if(l1.val<l2.val){
p.next=l1
l1=l1.next
} else {
p.next = l2
l2 = l2.next
}
p = p.next
}
if(l1 === null){
p.next = l2
} else {
p.next = l1
}
return l.next
};
- 二叉树的镜像
var mirrorTree = function(root) {
if(root === null) return root
if(root.left === null && root.right === null) return root
let temp = root.left
root.left = mirrorTree(root.right)
root.right = mirrorTree(temp)
return root
};
- 对称的二叉树
var isSymmetric = function(root) {
if(root === null) return true
function recur(left, right){
if(left === null && right === null) {
return true
} else if(left === null || right === null || left.val!==right.val) {
return false
} else {
return recur(left.left,right.right)&&recur(left.right,right.left)
}
}
return recur(root.left, root.right)
};
- 顺时针打印矩阵
var spiralOrder = function(matrix) {
let n = matrix.length
if(n===0) return []
let m = matrix[0].length
let l = 0, r = m - 1, t = 0, b = n - 1;
let res = []
let nums = 1, target = n * m;
while (nums<=target) {
for (let i = l; i <= r; i++) {
res.push(matrix[t][i]) // left to right.
nums++
}
if(nums>target) break;
t++;
for (let i = t; i <= b; i++) {
res.push(matrix[i][r]); // top to bottom.
nums++
}
if(nums>target) break;
r--;
for (let i = r; i >= l; i--) {
res.push(matrix[b][i]); // right to left.
nums++
}
if(nums>target) break;
b--;
for (let i = b; i >= t; i--) {
res.push(matrix[i][l]); // bottom to top.
nums++
}
l++;
}
return res;
};
- 包含min函数的栈
var MinStack = function() {
this.stack = []
this.minNum = []
};
/**
* @param {number} x
* @return {void}
*/
MinStack.prototype.push = function(x) {
this.stack.push(x)
let len = this.minNum.length
if(len===0) {
this.minNum.push(x)
} else if(this.minNum[len-1]>=x) {
this.minNum.push(x)
}
};
/**
* @return {void}
*/
MinStack.prototype.pop = function() {
let x = this.stack.pop()
let len = this.minNum.length
if(x===this.minNum[len-1]){
this.minNum.pop()
}
};
/**
* @return {number}
*/
MinStack.prototype.top = function() {
let len = this.stack.length
if(len>0){
return this.stack[len-1]
} else return null
};
/**
* @return {number}
*/
MinStack.prototype.min = function() {
let len = this.minNum.length
if(len>0){
return this.minNum[len-1]
} else return null
};
32 - I. 从上到下打印二叉树
var levelOrder = function(root) {
if(root === null) return []
let queue = [root]
let res = []
while(queue.length>0){
let node = queue.shift()
res.push(node.val)
if(node.left !== null) queue.push(node.left)
if(node.right !== null) queue.push(node.right)
}
return res
};
32 - II. 从上到下打印二叉树 II
var levelOrder = function(root) {
if(root === null) return []
let queue = [root]
let res = []
let level = 0
while(queue.length>0){
res[level] = []
let levelNum = queue.length; // 第level层的节点数量
while (levelNum--) {
const front = queue.shift();
res[level].push(front.val);
if (front.left) queue.push(front.left);
if (front.right) queue.push(front.right);
}
level++;
}
return res
};
- 复杂链表的复制
还有点问题，先合并再拆开，链表深克隆，深度优先遍历
var copyRandomList = function(head) {
const map = {};
function recur(node){
if(!node){
return null
}
if(map[node.val]){
return map[node.val]
}
let res = new Node(node.val);
map[node.val] = res;
res.next = recur(node.next);
res.random = recur(node.random)
return res
}
return recur(head)
};
- 数组中出现次数超过一半的数字
var majorityElement = function(nums) {
nums.sort((m,n)=>m-n)
return nums[Math.floor(nums.length/2)]
};
- 最小的k个数
var getLeastNumbers = function(arr, k) {
return arr.sort((m,n)=>m-n).slice(0,k)
};
- 礼物的最大价值
动态规划
var maxValue = function(grid) {
let m = grid[0].length
let n = grid.length
let dp = [[]]
dp[0][0]=grid[0][0]
for(let i=1; i<m;i++){
dp[0][i]=dp[0][i-1]+grid[0][i]
}
for(let i=1; i<n;i++){
dp.push([])
dp[i][0]=dp[i-1][0]+grid[i][0]
}
for(let i=1; i<n;i++){
for(let j=1; j<m;j++){
dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1])+grid[i][j]
}
}
return dp[n-1][m-1]
};
- 最长不含重复字符的子字符串
var lengthOfLongestSubstring = function(s) {
if (s.length === 0) return 0
let obj = {}
let cur = [0]
for (let i = 0; i < s.length; i++) {
if (s[i] in obj) {
cur[i + 1] = Math.min(i - obj[s[i]], cur[i] + 1)
} else {
cur[i + 1] = cur[i] + 1
}
obj[s[i]] = i
}
return Math.max(...cur)
};
- 丑数
var nthUglyNumber = function(n) {
let p2=0,p3=0,p5=0;
let dp = []
dp[0]=1;
for(let i=1;i<n;i++){
dp[i]=Math.min(dp[p2]*2,dp[p3]*3,dp[p5]*5);
if(dp[i]==dp[p2]*2) p2++;
if(dp[i]==dp[p3]*3) p3++;
if(dp[i]==dp[p5]*5) p5++;
}
return dp[n-1];
};
- 第一个只出现一次的字符
var firstUniqChar = function(s) {
let arr = s.split('')
for(let i=0;i<s.length;i++){
if(arr.indexOf(arr[i])===arr.lastIndexOf(arr[i])){
return arr[i]
}
}
return " "
};
- 两个链表的第一个公共节点
var getIntersectionNode = function(headA, headB) {
if(headA === null || headB === null) return null
let node1 = headA
let node2 = headB
let flag = 0
while(node1 !== node2){
if(node1.next === null) {
node1 = headB
flag++
}else{
node1=node1.next
}
if(node2.next === null) {
node2 = headA
} else {
node2=node2.next
}
if(flag>1) return null
}
return node1
};
53 - I. 在排序数组中查找数字 I
var search = function(nums, target) {
let index = nums.indexOf(target)
if(index === -1){
return 0
}
return nums.lastIndexOf(target)+1 - index
};
53 - II. 0～n-1中缺失的数字
var missingNumber = function(nums) {
let low = 0
let high = nums.length - 1
while(low<high){
let mid = Math.floor((low+high)/2)
if(nums[mid] != mid){
high = mid - 1
} else {
low = mid + 1;
}
}
return nums[low] == low ? nums[low]+1 : nums[low]-1;
};
- 二叉搜索树的第k大节点
var kthLargest = function(root, k) {
let res=0
let n=0
dfs(root,k);
return res;
function dfs(root,k){
if(root === null) return
if(root.right) dfs(root.right,k);
n++;
if(n==k) res=root.val;
if(root.left) dfs(root.left,k);
return ;
}
};
55 - I. 二叉树的深度
var maxDepth = function(root) {
if(root === null) return 0
if (root.left === null && root.right === null) {
return 1
}
if (root.left !== null && root.right === null) {
return maxDepth(root.left)+1
}
if (root.left === null && root.right !== null) {
return maxDepth(root.right)+1
}
if (root.left !== null && root.right !== null) {
return Math.max(maxDepth(root.left),maxDepth(root.right))+1
}
};
55 - II. 平衡二叉树
var isBalanced = function(root) {
return recur(root) !== -1
function recur(root){
if (root == null) return 0;
let left = recur(root.left);
if(left == -1) return -1;
let right = recur(root.right);
if(right == -1) return -1;
return Math.abs(left - right) < 2 ? Math.max(left, right) + 1 : -1;
}
};
56 - I. 数组中数字出现的次数
var singleNumbers = function(nums) {
let res = 0
for (let i=0;i<nums.length;i++) {
res ^= nums[i]
}
let flag = res & (-res)
let res1 = 0
let res2 = 0
for (let i=0;i<nums.length;i++) {
if(nums[i]&flag){
res1 ^= nums[i]
} else {
res2 ^= nums[i]
}
}
return [res1,res2]
};
56 - II. 数组中数字出现的次数 II
var singleNumber = function(nums) {
let a=0,b=0;
for (let i=0;i<nums.length;i++) {
b = b ^ nums[i] & ~ a;
a = a ^ nums[i] & ~ b;
}
return b;
};
- 和为s的两个数字
var twoSum = function(nums, target) {
let obj = {}
for(let i=0;i<nums.length;i++){
if(nums[i] in obj){
return [nums[i], obj[nums[i]]]
} else {
obj[target - nums[i]] = nums[i]
}
}
};
面试题57 - II. 和为s的连续正数序列
var findContinuousSequence = function(target) {
let start = 1
let end = 1
let sum = 0
let res = []
while(start<=target/2){
if(sum<target){
sum += end
end++
} else if(sum > target){
sum -=start
start++
} else {
let arr = []
for(let i=start;i<end;i++){
arr.push(i)
}
res.push(arr)
sum -= start
start++
}
}
return res
};
58 - I. 翻转单词顺序
var reverseWords = function(s) {
return s.split(' ').reverse().filter(x=>x!='').join(' ')
};
58 - II. 左旋转字符串
var reverseLeftWords = function(s, n) {
return s.substr(n,s.length) + s.substr(0,n)
};
59 - I. 滑动窗口的最大值
var maxSlidingWindow = function(nums, k) {
if (nums.length === 0) return nums
let arr = []
arr.push(Math.max(...nums.slice(0,k)))
for(i=1;i<nums.length-k+1;i++){
if(nums[i-1]===arr[i-1]){
arr.push(Math.max(...nums.slice(i,k+i)))
} else {
arr.push(Math.max(arr[i-1],nums[i+k-1]))
}
}
return arr
};
- n个骰子的点数
var twoSum = function(n) {
let dp = []
dp[1]=[0,1,1,1,1,1,1]
for (let i = 2; i <= n; i ++) {
for (let j = i; j <= 6*i; j ++) {
for (let cur = 1; cur <= 6; cur ++) {
if (j - cur <= 0) {
break;
}
if(!dp[i]) dp[i] = []
if(!dp[i][j]) dp[i][j] = 0
if(!dp[i-1][j-cur]) dp[i-1][j-cur] = 0
dp[i][j] += dp[i-1][j-cur];
}
}
}
let all = 6**n;
let ret = [];
for (let i = n; i <= 6 * n; i ++) {
ret.push(dp[n][i] / all);
}
return ret;
};
- 扑克牌中的顺子
var isStraight = function(nums) {
nums.sort((m,n)=>m-n)
let res = 0
for(let i=0;i<4;i++){
if(nums[i]===0) {
res++
} else if((nums[i+1]-nums[i])===0) {
return false
} else {
res = res-(nums[i+1]-nums[i])+1
}
}
return res>=0
};
- 股票的最大利润
var maxProfit = function(prices) {
let min = prices[0]
let dp = []
for(let i=1;i<prices.length;i++){
dp[i-1] = prices[i]-min
min = Math.min(min,prices[i])
}
let res = Math.max(...dp)
return res>0?res:0
};
- 求1+2+…+n
var sumNums = function(n) {
n && (n += sumNums(n-1));
return n;
};
- 不用加减乘除做加法
var add = function(a, b) {
if(a == 0) return b;
if(b == 0) return a;
return add(( a ^ b ),((a & b) << 1));
};
- 构建乘积数组
var constructArr = function(a) {
let preArr = []
let afterArr = []
let pre = 1
let after = 1
for(let i=0;i<a.length;i++){
preArr.push(pre)
pre *= a[i]
afterArr.push(after)
after *= a[a.length-i-1]
}
let res = []
for(let i=0;i<a.length;i++){
res.push(preArr[i]*afterArr[a.length-i-1])
}
return res
};
68 - I. 二叉搜索树的最近公共祖先
此题编辑器不可以选js
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
while (root!=null){
if (p.val<root.val && q.val<root.val){
root=root.left;
}else if (p.val>root.val && q.val>root.val){
root=root.right;
}else{
break;
}
}
return root;
}
}
68 - II. 二叉树的最近公共祖先
不可选js
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root==null || root==p || root==q)
return root;
TreeNode leftNode=lowestCommonAncestor(root.left,p,q);
TreeNode rightNode=lowestCommonAncestor(root.right,p,q);
if(leftNode==null)
return rightNode;
if(rightNode==null)
return leftNode;
return root;
}
}
image.png
1、补零
while(bin.length<32){
bin = "0"+bin
}
2、b.length变化了
for(let i=0;i<a.length-b.length;i++){
b='0'+b
}
3、字符串删除一个字符
s=s.replace(char,'')
4、sort()按照字典排序
5、>>>带符号位右移
(-5>>>0)+5
4294967296
2**32
4294967296
6、牛客网的输入输出
反序输出
var line;
while(line = readline()){
print(line.split('').reverse().join(''));
}
