webvueblog / bytedance-campus-59-leetcode Goto Github PK

View Code? Open in Web Editor NEW

5.0 5.0 0.0 6 KB

力扣 (LeetCode) 🐿️ 字节校园 59

Home Page: https://webvueblog.github.io/Bytedance-campus-59-Leetcode/

bytedance leetcode leetcode-javascript leetcode-solutions

bytedance-campus-59-leetcode's Introduction

感谢关注 Thanks for your attention ༼ つ ◕_◕ ༽つ

后端技术栈

前端技术栈

DevOps

运维技术栈

测试技术栈

开发工具

其他

☀️ 个人优势

开发经验：丰富的多端 0-1 前后端项目开发经验，独立开发经验3年，大型前后端开发重构经验，有 4-5 前端团队搭建敏捷项目管理，团队多人协同开发能力，可独立全栈开发。
熟练前端架构：qiankun微前端架构系统、vue3、taro、react、express/node、vite3、TypeScript/4、Ant�Design-Vue/3.2、element-plus/2.2、vue-i18n/9、mitt/3、axios、pinia/2、vue-router/4、tailwindcss/3、VueRequest、VueUse等主流技术开发，跨平台uniapp、flutter框架，移动端H5网页、PC、微信/支付宝小程序、安卓/IOS App等。
熟练后端架构：Spring Cloud微服务、Maven 多模块管理、Java8、Spring、Spring Boot2、SpringMVC、Docker、kafka、（netty-mqtt,tcp,udp,sip,coap）、Cassandra、Elasticsearch、Nacos（Nacos Config）服务注册中与配置中心、Ribbon负载均衡、OpenFeign服务调用、sentinel服务熔断、SpringCloud Gateway服务网关、SpringCloud Alibaba、MyBatis、Mybatis-Plus、log4j、Nginx（负载均衡）、SpringSecurity、Redis、MySql、MongoDB、Zookeeper、Seata分布式事务、Skywalking链路追踪，XXL-Job等。
熟练运维方面：熟悉Linux操作系统及常用命令，了解Docker，k8s等，Linux日常服务器操作管理。
管理层经验4+年：负责团队技术选型、技术攻坚及管理工作（项目计划表，每周会议，绩效考核），管理项目全生命周期，制定项目计划，监控项目进程，对项目的质量，成本，风险，进度等进行管理和控制；对公司领导汇报项目进度，编写项目相关文档；协调其他安排的工作，注重标准化，模块化，工程化，在部门内部标准落地，已落地电商、新能源、物联网、有声小说行业业务能力。
微服务平台稳定生产了三年+，mysql主从模式，使用Netty、mqtt采集设备信息，k8s + jenkins的部署架构，采用Spring Boot 2.7 、Spring Cloud 2021 ，集成Minio分布式对象存储、Skywalking追踪监控、Sentinel从流量控制、熔断降级、系统负载等多个维度保护服务的稳定性，注册中心、配置中心选型Nacos，使用Traefik进行反向代理，借鉴OAuth2，实现了多终端认证系统，可控制子系统的token权限互相隔离，借鉴Security，封装了Secure模块，采用JWT做Token认证，可拓展集成Redis等细颗粒度控制方案，完全遵循阿里巴巴编码规范，实现SaaS多租户微服务平台。
深入理解 Vue，并研究过其内部实现，并输出 JS LeetCode 算法解决方案（小册），刷题近500道题。
喜欢分享，推动团队内部技术分享与复盘总结，工作认真负责，注重代码质量，工作效率，工作内容输出。

🍰 我的B站账号：https://space.bilibili.com/144761334
🌈 掘金技术平台：掘金我是哪吒
🌸 我的leetcode册子： nice-js-leetcode ，leetcode-javascript
🏡 个人博客网站：🌱 1024bat.cn 🌱 1024bibi.com 🌱 达达前端 🌱 github

汇总

netty4.x案例。（ https://github.com/webVueBlog/springboot-netty ）
Netty 4 的粘包和拆包解决办法，心跳测试，http服务的实现，client重连机制，TCP滑动窗口、protobuf协议传输等相关技术。（ https://github.com/webVueBlog/Netty-study ）
Redisson实现分布式锁（ https://github.com/webVueBlog/spring-boot-distributed-redisson ）
基于 VitePress 的个人后端架构系统日志（ https://github.com/webVueBlog/vitepress-java ）
unida-最好的uni跨平台开发脚手架（小程序，h5，App）( https://github.com/webVueBlog/unida )
低代码数字化大屏-基于 React 技术栈实现（ https://github.com/webVueBlog/low-code-digital-big-screen ）
charging-station-large-screen 新能源充电桩数据可视化平台，采用Vue3、Echarts技术栈（https://github.com/webVueBlog/charging-station-large-screen ）
gd-ui-comonents 前端 UI 组件库（https://github.com/webVueBlog/gd-ui-comonents ）
Springboot-IOT-Platform 物联网平台，智能家居、智慧办公、智慧社区、农业监测、水利监测、工业控制等。(https://github.com/webVueBlog/Springboot-IOT-Platform)
Springboot-IOT-Gateway 基于netty的UDP物联网网关程序，设备报文可转发至KAFKA或MQTT broker(https://github.com/webVueBlog/Springboot-IOT-Gateway)
Visual-Screen-Vue3 vue3、vite、Echart 框架的大数据可视化大屏展示(https://github.com/webVueBlog/Visual-Screen-Vue3)
Springboot-WeChat-Login SpringBoot 实现微信扫码登录(https://github.com/webVueBlog/Springboot-WeChat-Login)
Springboot-WeChat-Pay SpringBoot 实现微信扫码支付功能(https://github.com/webVueBlog/Springboot-WeChat-Pay)
Springboot-Redis-IpLimiter Springboot + Redis 组件，实现一个分布式接口IP访问限流功能(https://github.com/webVueBlog/Springboot-Redis-IpLimiter)
spring-boot-sharding-sphere 实现分库分表 + 读写分离功能(https://github.com/webVueBlog/spring-boot-sharding-sphere)
kafka-send-message Kafka简单案例(https://github.com/webVueBlog/kafka-send-message)
express-mysql-back 基于express后端框架，使用mysql数据库(https://github.com/webVueBlog/express-mysql-back)
spring-boot-mongodb-crud Spring Boot MongoDB CRUD（创建、读取、更新、删除）示例使用 MongoTemplate 和 MongoRepository(https://github.com/webVueBlog/spring-boot-mongodb-crud)
spring-boot-cassandra-crud Spring boot CRUD（创建、读取、更新、删除）演示应用程序，带有使用 Swaager 和 OpenAPI UI 的 cassandra DB 和 API 文档(https://github.com/webVueBlog/spring-boot-cassandra-crud)
webVueBlog-netty-kafka Http (Netty) producer for Apache Kafka(https://github.com/webVueBlog/webVueBlog-netty-kafka)
dadawebsocket 基于Netty和Kafka集群的websocket消息推送服务器(https://github.com/webVueBlog/dadawebsocket)
netty-kafka 使用netty发送、接收tcp和udp数据，多线程处理接收的数据。 kafka批处理(https://github.com/webVueBlog/netty-kafka)
mqtt-client-java Java MQTT 客户端使用示例(https://github.com/webVueBlog/netty-kafka)
awesome-stars-webVueBlog 🤩 我的star列表，每天凌晨自动更新(https://github.com/webVueBlog/awesome-stars-webVueBlog)
springboot-vxapp 基于Spring Boot的微服务框架-整合微信小程序登录(https://github.com/webVueBlog/springboot-vxapp)
JavaGuideInterview 「JavaGuideInterview学习」每日 3+1，以面试题来驱动学习，提倡每日学习与思考，每天进步一点！每天早上纯手工发布（死磕自己，愉悦大家）准备 Java 面试，首选 JavaGuideInterview！面试题大收集，面试集锦 ❤ 💝 💘(https://github.com/webVueBlog/JavaGuideInterview)
WebGuideInterview 「WebGuideInterview学习」每日 3+1，以面试题来驱动学习，提倡每日学习与思考，每天进步一点！每天早上纯手工发布（死磕自己，愉悦大家）准备前端面试，首选 WebGuideInterview！面试题大收集，面试集锦 ❤ 💝 💘(https://github.com/webVueBlog/WebGuideInterview)
nice-my-friend 😳轻松查看和过滤所有关注和关注。通过 GitHub Action 自动更新。(https://github.com/webVueBlog/nice-my-friend)
socket_im_flutter 聊天工具flutter(https://github.com/webVueBlog/socket_im_flutter)
tomato_clock 开发番茄钟计时器(https://github.com/webVueBlog/tomato_clock)
tailwindcss-chinese 🤖 国内tailwindcss平台从业者交流，Github Actions自动化部署(https://github.com/webVueBlog/tailwindcss-chinese)
sms 发送短信验证码-腾讯云(https://github.com/webVueBlog/sms)
flutter_login_ui 登录UI(https://github.com/webVueBlog/flutter_login_ui)
write-vue-js 手写vue.js - Vue.js v2.5.16(https://github.com/webVueBlog/write-vue-js)
springboot-bookadmin SpringBoot2.X整合MyBatis-Plus实现图书管理系统的增删改查(https://github.com/webVueBlog/springboot-bookadmin)
JavaScript-standard-library 前端进阶必看的JavaScript 标准库 JavaScript-standard-library(https://github.com/webVueBlog/JavaScript-standard-library)
vue3-vite-pinia-template 企业级前端开发与构建框架 Vite + Vue3 + TypeScript + Vue-Router4 + Pinia + Tailwind CSS + ant-design-vueTemplate.(https://github.com/webVueBlog/vue3-vite-pinia-template)
koa2-login-registration koa2-login-registration Koa2实现基本的登录注册(https://github.com/webVueBlog/koa2-login-registration)
electron-vue electron-vue 实战(https://github.com/webVueBlog/electron-vue)
webpack-studying webpack - 为前端圈提供一点贡献(https://github.com/webVueBlog/webpack-studying)
Quick-Hand-Algorithm 快手-算法(https://github.com/webVueBlog/Quick-Hand-Algorithm)
nice-js-leetcode 好青年 | leetcode 今日事今日毕（✅GitHub Actions集成LeetCode每日一题至issues）(https://github.com/webVueBlog/nice-js-leetcode)
Bytedance-campus-59-Leetcode 力扣 (LeetCode) 🐿️ 字节校园 59(https://github.com/webVueBlog/Bytedance-campus-59-Leetcode)
LeetCode-HOT-100 力扣 (LeetCode) 🔥LeetCode HOT 100(https://github.com/webVueBlog/LeetCode-HOT-100)
Tencent-50-Leetcode 力扣 (LeetCode) 🐧 腾讯精选练习 50 题(https://github.com/webVueBlog/Tencent-50-Leetcode)
mini-vue vue超详细逐行解析版源码，手写，算法，javascript等(https://github.com/webVueBlog/mini-vue)
file-breakpoint-continue 🐬 实现大文件📄上传，断点续传等💎(https://github.com/webVueBlog/file-breakpoint-continue)
uui 🖖 【uui组件库】A vue-cli 3.0 + vue + typeScript + babel + eslint + unit-mocha + scss + chai + karma。(https://github.com/webVueBlog/uui)
umi-poster 海报，封面生成器(https://github.com/webVueBlog/umi-poster)
web-audio-video 📺 研究方向音视频相关领域(https://github.com/webVueBlog/web-audio-video)
leetcode-javascript Collection of LeetCode questions to ace the coding interview!(https://github.com/webVueBlog/leetcode-javascript)
Leetcode 🎲【每日更新 question & answers】一个 ☝️ 正经的前端学习，每天进步一点点！手写源码，api，算法；包含JavaScript / Vue / React / TypeScript /HTML / CSS / Nodejs / Leetcode……Suggest 👍(https://github.com/webVueBlog/Leetcode)
express-node ⚡ express-node-mysql-react全家桶(https://github.com/webVueBlog/express-node)
promise ♥ Bare bones Promises/A+ implementation 简单的 Promises/A+ 实现(https://github.com/webVueBlog/promise)
vue-ts-webpack-system vue2+typescript4+webpack5+element-ui项目系统解决方案(Node数据支撑)(https://github.com/webVueBlog/vue-ts-webpack-system)
static-html 主要研究日常开发中一些功能点的实现，旨在帮大家捋顺前端底层知识(https://github.com/webVueBlog/static-html)
awesome-collection 【建议👍】【个人收藏】Personal collection(https://github.com/webVueBlog/awesome-collection)
Vite-Vue3-TypeScript 🎲一套规范的 Vite + Vue3 + TypeScript 前端工程化项目环境(https://github.com/webVueBlog/Vite-Vue3-TypeScript)
vue-ts-netease-cloud-music 网易云音乐客户端播放器（PC） Online Music Player(https://github.com/webVueBlog/vue-ts-netease-cloud-music)
ueditor_vue_doc ueditor_vue_doc文档(https://github.com/webVueBlog/ueditor_vue_doc)
vue3-vite2-ts4 🎲一套规范的vue3+vite2+ts4前端工程化项目环境(https://github.com/webVueBlog/vue3-vite2-ts4)
learn-web 🚴一份 🚀 涵盖大部分程序员所需要掌握的知识 🚄。(https://github.com/webVueBlog/learn-web)
todolist-vue 用 Todoist 组织一切，管理工作和生活的To Do List，使用 Vite、Vue 和 Vuex 构建的 TodoMVC(https://github.com/webVueBlog/todolist-vue)
todolist-react TypeScript版本-使用 React 和 Redux 构建的 TodoMVC (props&Event&Context&Mobx&Redux)(https://github.com/webVueBlog/todolist-react)

我喜欢交朋友。所以如果你想打个招呼，我会很高兴见到你更多！ 😊

💬 我的微信号: xiaoda0423⚡ 👉 如果你有问题提出： click
🤔 坚持的趣事: 终身学习 common Snippets 坚持运动，阅读
JavaGuideInterview学习每日 3+1，以面试题来驱动学习，提倡每日学习与思考，每天进步一点！每天早上纯手工发布（死磕自己，愉悦大家）准备 Java 面试，首选 JavaGuideInterview！面试题大收集，面试集锦 ❤ 💝 💘
WebGuideInterview学习每日 3+1，以面试题来驱动学习，提倡每日学习与思考，每天进步一点！每天早上纯手工发布（死磕自己，愉悦大家）准备前端面试，首选 WebGuideInterview！面试题大收集，面试集锦 ❤ 💝 💘

开源

腾讯位置服务开发应用(https://ext.dcloud.net.cn/plugin?id=3746)
JesksonUI-UniApp(https://ext.dcloud.net.cn/plugin?id=3837)

📚 小书

封面	书名	简述	成就
	《Webpack学习笔记》	Webpack学习笔记
	《前端进阶JavaScript》	前端进阶 JavaScript 标准库
	《腾讯精选练习 50 题》	力扣 (LeetCode) 🐧 腾讯精选练习 50 题
	《字节校园 59》	力扣 (LeetCode) 🐿️ 字节校园算法与数据结构
	《LeetCode HOT 100》	力扣 (LeetCode) 🔥LeetCode HOT 100
	《数据结构与算法》	哪吒的数据结构与算法
	《手写代码》	✨✨✨ 集锦前端JavaScript 手写题，编程题，Not just for interviews

项目	Github	简述
【uui】	Github	🖖 uui组件库
【file-breakpoint-continue】	Github	🐬 实现大文件上传，断点续传等
【express-node】	Github	🌙 express-node-mysql-react
【awesome-css】	Github	🍉 国内css平台从业者交流
【nice-my-friend】	Github	♻️ 关注人数列表数据
【awesome-stars-webVueBlog】	Github	🤩 我的star列表
【promise】	Github	🐧 Promises/A+ 实现
【mini-vue】	Github	🖖 mini-vue

bytedance-campus-59-leetcode's People

Contributors

Stargazers

Watchers

bytedance-campus-59-leetcode's Issues

53. 最大子数组和

Description

Difficulty: 中等

Related Topics: 数组, 分治, 动态规划

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组 是数组中的一个连续部分。

示例 1：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

示例 2：

输入：nums = [1]
输出：1

示例 3：

输入：nums = [5,4,-1,7,8]
输出：23

提示：

1 <= nums.length <= 10⁵
-10⁴ <= nums[i] <= 10⁴

**进阶：**如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。

Solution

Language: JavaScript

/**
 * @param {number[]} nums
 * @return {number}
 */
// 动态规划
var maxSubArray = function(nums) {
    let pre = 0
    let maxAns = nums[0]
    nums.forEach((x) => {
        pre = Math.max(pre + x, x)
        maxAns = Math.max(maxAns, pre)
    })
    return maxAns
}

198. 打家劫舍

Description

Difficulty: 中等

Solution

Language: JavaScript

/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function(nums) {
    const len = nums.length
    if (len === 0) return 0
    const dp = new Array(len + 1)
    dp[0] = 0
    dp[1] = nums[0]
    for (let i = 2; i <= len; i++) {
        dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i - 1])
    }
    return dp[len]
}

105. 从前序与中序遍历序列构造二叉树

Description

Difficulty: 中等

Related Topics: 树, 数组, 哈希表, 分治, 二叉树

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

示例 1:

输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]

示例 2:

输入: preorder = [-1], inorder = [-1]
输出: [-1]

提示:

1 <= preorder.length <= 3000
inorder.length == preorder.length
-3000 <= preorder[i], inorder[i] <= 3000
preorder 和 inorder 均 无重复 元素
inorder 均出现在 preorder
preorder 保证为二叉树的前序遍历序列
inorder 保证为二叉树的中序遍历序列

Solution

Language: JavaScript

/**
 * 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 {number[]} preorder
 * @param {number[]} inorder
 * @return {TreeNode}
 */
// 前序遍历: 根-左-右
// 中序遍历：左-根-右
// 先用前序遍历找根节点，在用根节点去中序遍历确定左右子树
var buildTree = function(preorder, inorder) {
    // 当preorder和inorder均为空的时候说明已经到了空节点
    if (!preorder.length || !inorder.length) return null

    // 创建根节点 -> preorder[0]
    let node = new TreeNode(preorder[0])

    // 找到perorder[0]对应inorder中的位置
    let index = inorder.indexOf(preorder.shift())

    // 左右子树递归
    node.left = buildTree(preorder, inorder.slice(0, index))
    node.right = buildTree(preorder, inorder.slice(index + 1))

    // 返回根节点
    return node
}

103. 二叉树的锯齿形层序遍历

Description

Difficulty: 中等

Related Topics: 树, 广度优先搜索, 二叉树

给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历 。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[20,9],[15,7]]

示例 2：

输入：root = [1]
输出：[[1]]

示例 3：

输入：root = []
输出：[]

提示：

树中节点数目在范围 [0, 2000] 内
-100 <= Node.val <= 100

Solution

Language: JavaScript

/**
 * 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 zigzagLevelOrder = function(root) {
    if (!root) return []
    const ans = []
    const nodeQueue = [root]

    let isOrderLeft = true

    while (nodeQueue.length) {
        let levelList = []
        const size = nodeQueue.length
        for (let i = 1; i <= size; i++) {
            const node = nodeQueue.shift()
            if (isOrderLeft) {
                levelList.push(node.val)
            } else {
                levelList.unshift(node.val)
            }
            if (node.left) nodeQueue.push(node.left)
            if (node.right) nodeQueue.push(node.right)
        }
        ans.push(levelList)
        isOrderLeft = !isOrderLeft
    }

    return ans
};

199. 二叉树的右视图

Description

Difficulty: 中等

Related Topics: 树, 深度优先搜索, 广度优先搜索, 二叉树

给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

示例 1:

输入: [1,2,3,null,5,null,4]
输出: [1,3,4]

示例 2:

输入: [1,null,3]
输出: [1,3]

示例 3:

输入: []
输出: []

提示:

二叉树的节点个数的范围是 [0,100]
-100 <= Node.val <= 100

Solution

Language: JavaScript

/**
 * 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 rightSideView = function(root) {
//     const res = []
//     const dfs = (root, depth) => {
//         if (!root) return null
//         if (depth === res.length) {
//             res.push(root.val)
//         }
//         depth++
//         dfs(root.right, depth)
//         dfs(root.left, depth)
//     }
//     dfs(root, 0)
//     return res
// };

var rightSideView = function(root) {
    if (!root) return []
    const q = [root]
    const res = []
    while (q.length) {
        let len = q.length
        while(len--) {
            const n = q.shift()
            if (!len) res.push(n.val)
            n.left && q.push(n.left)
            n.right && q.push(n.right)
        }
    }
    return res
}

88. 合并两个有序数组

Description

Difficulty: 简单

Related Topics: 数组, 双指针, 排序

给你两个按 非递减顺序 排列的整数数组 nums1和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你合并 nums2到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

**注意：**最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

示例 1：

输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]
解释：需要合并 [1,2,3] 和 [2,5,6] 。
合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。

示例 2：

输入：nums1 = [1], m = 1, nums2 = [], n = 0
输出：[1]
解释：需要合并 [1] 和 [] 。
合并结果是 [1] 。

示例 3：

输入：nums1 = [0], m = 0, nums2 = [1], n = 1
输出：[1]
解释：需要合并的数组是 [] 和 [1] 。
合并结果是 [1] 。
注意，因为 m = 0 ，所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。

提示：

nums1.length == m + n
nums2.length == n
0 <= m, n <= 200
1 <= m + n <= 200
-10⁹ <= nums1[i], nums2[j] <= 10⁹

**进阶：**你可以设计实现一个时间复杂度为 O(m + n) 的算法解决此问题吗？

Solution

Language: JavaScript

/**
 * @param {number[]} nums1
 * @param {number} m
 * @param {number[]} nums2
 * @param {number} n
 * @return {void} Do not return anything, modify nums1 in-place instead.
 */

// var merge = function(nums1, m, nums2, n) {
//     for (let i = 0, len = nums1.length; i < len; i++) {
//         if (m === 0) {
//             nums1[len-1-i] = nums2[--n];
//         } else if (n === 0) {
//             break
//         } else {
//             nums1[len-1-i] = nums1[m-1] > nums2[n-1] ? nums1[--m] : nums2[--n]
//         }
//     }
// };

// 直接合并后排序
var merge = function(nums1, m, nums2, n) {
    nums1.splice(m, nums1.length - m, ...nums2)
    nums1.sort((a, b) => a - b)
}

69. x 的平方根

Description

Difficulty: 简单

Solution

Language: JavaScript

/**
 * @param {number} x
 * @return {number}
 */
// 「x的平方根」 二分
var mySqrt = function(x) {
    let left = 0
    let right = x
    while (left <= right) {
        let mid = left + ((right - left) >>> 1)

        if (mid * mid < x) {
            left = mid + 1
        } else if (mid * mid > x) {
            right = mid - 1
        } else {
            return mid
        }
    }
    return right
};

152. 乘积最大子数组

Description

Difficulty: 中等

Solution

Language: JavaScript

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxProduct = function (nums) {
    let min = 1, max = 1, res = -Infinity
    for (let num of nums) {
        if (num < 0) [min, max] = [max, min]
        max = Math.max(num * max, num)
        min = Math.min(num * min, num)
        res = Math.max(res, max)
    }
    return res
}

72. 编辑距离

Description

Difficulty: 困难

Solution

Language: JavaScript

/**
 * @param {string} word1
 * @param {string} word2
 * @return {number}
 */
// dp[i][j]是word1,word2的最小编辑距离
var minDistance = function(word1, word2) {
    let m = word1.length
    let n = word2.length
    const dp = new Array(m+1).fill(0).map(() => new Array(n+1).fill(0))
    // 初始化
    for (let i = 1; i <= m; i++) {
        dp[i][0] = i
    }
    for (let j = 1; j <= n; j++) {
        dp[0][j] = j
    }
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (word1[i-1] === word2[j-1]) {
                dp[i][j] = dp[i-1][j-1]
            } else {
                dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
            }
        }
    }
    return dp[m][n]
}

135. 分发糖果

Description

Difficulty: 困难

Solution

Language: JavaScript

/**
 * @param {number[]} ratings
 * @return {number}
 */
// 两次遍历
// 从左向右遍历，保证右边大于左边
// 从右向左遍历，保证左边大于右边
var candy = function(ratings) {
    const len = ratings.length
    const candies = new Array(len).fill(1)

    for (let i = 1; i < len; i++) {
        if (ratings[i-1] < ratings[i]) {
            candies[i] = candies[i-1] + 1
        }
    }

    for (let i = len - 2; i >= 0; i--) {
        if (ratings[i] > ratings[i+1]) {
            candies[i] = Math.max(candies[i], candies[i+1] + 1)
        }
    }

    return candies.reduce((a, b) => a + b)
};

4. 寻找两个正序数组的中位数

Description

Difficulty: 困难

Related Topics: 数组, 二分查找, 分治

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

算法的时间复杂度应该为 O(log (m+n)) 。

示例 1：

输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2

示例 2：

输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5

提示：

nums1.length == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
-10⁶ <= nums1[i], nums2[i] <= 10⁶

Solution

Language: JavaScript

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var findMedianSortedArrays = function(nums1, nums2) {
    const newNums = nums1.concat(nums2).sort((a, b) => a - b)
    const len = newNums.length
    if (len % 2 === 0) {
        return (newNums[len/2 - 1] + newNums[len/2]) / 2
    } else {
        return newNums[Math.floor(len/2)]
    }
}

129. 求根节点到叶节点数字之和

Description

Difficulty: 中等

Related Topics: 树, 深度优先搜索, 二叉树

给你一个二叉树的根节点 root ，树中每个节点都存放有一个 0 到 9 之间的数字。

每条从根节点到叶节点的路径都代表一个数字：

例如，从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123 。

计算从根节点到叶节点生成的 所有数字之和 。

叶节点 是指没有子节点的节点。

示例 1：

输入：root = [1,2,3]
输出：25
解释：
从根到叶子节点路径 1->2 代表数字 12
从根到叶子节点路径 1->3 代表数字 13
因此，数字总和 = 12 + 13 = 25

示例 2：

输入：root = [4,9,0,5,1]
输出：1026
解释：
从根到叶子节点路径 4->9->5 代表数字 495
从根到叶子节点路径 4->9->1 代表数字 491
从根到叶子节点路径 4->0 代表数字 40
因此，数字总和 = 495 + 491 + 40 = 1026

提示：

树中节点的数目在范围 [1, 1000] 内
0 <= Node.val <= 9
树的深度不超过 10

Solution

Language: JavaScript

/**
 * 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 sumNumbers = function(root) {
    const dfs = (root, prevSum) => {
        if (!root) return 0
        const sum = prevSum * 10 + root.val
        if (root.left === null && root.right === null) {
            return sum
        } else {
            return dfs(root.left, sum) + dfs(root.right, sum)
        }
    }
    return dfs(root, 0)
};

2. 两数相加

Description

Difficulty: 中等

Solution

Language: JavaScript

/**
 * 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 dummy = new ListNode()
    let curr = dummy
    let carry = 0

    while(l1 || l2) {
        const x = l1 ? l1.val : 0
        const y = l2 ? l2.val : 0

        const total = x + y + carry
        curr.next = new ListNode(total % 10)
        curr = curr.next
        carry = Math.floor(total / 10)

        if (l1) l1 = l1.next
        if (l2) l2 = l2.next
    }
    if (carry) curr.next = new ListNode(carry)

    return dummy.next
}

146. LRU 缓存

Description

Difficulty: 中等

Related Topics: 设计, 哈希表, 链表, 双向链表

请你设计并实现一个满足 LRU (最近最少使用) 缓存约束的数据结构。

实现 LRUCache 类：

LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该逐出最久未使用的关键字。

函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

示例：

输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]

解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1);    // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2);    // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1);    // 返回 -1 (未找到)
lRUCache.get(3);    // 返回 3
lRUCache.get(4);    // 返回 4

提示：

1 <= capacity <= 3000
0 <= key <= 10000
0 <= value <= 10⁵
最多调用 2 * 10⁵ 次 get 和 put

Solution

Language: JavaScript

/**
 * @param {number} capacity
 */
var LRUCache = function(capacity) {
 this.map = new Map()
 this.capacity = capacity
};

/** 
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function(key) {
 if (this.map.has(key)) {
  let value = this.map.get(key)
  // 重新set，相当于更新到 map 最后
  this.map.delete(key)
  this.map.set(key, value)
  return value
 }
 return -1
};

/** 
 * @param {number} key 
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.put = function(key, value) {
 if (this.map.has(key)) {
  this.map.delete(key)
 }

 this.map.set(key, value)

 if (this.map.size > this.capacity) {
  this.map.delete(this.map.keys().next().value)
 }
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * var obj = new LRUCache(capacity)
 * var param_1 = obj.get(key)
 * obj.put(key,value)
 */

21. 合并两个有序链表

Description

Difficulty: 简单

Solution

Language: JavaScript

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} list1
 * @param {ListNode} list2
 * @return {ListNode}
 */
// 递归
// var mergeTwoLists = function(list1, list2) {
//     if (!list1) {
//         return list2
//     } else if (!list2) {
//         return list1
//     } else if (list1.val < list2.val) {
//         list1.next = mergeTwoLists(list1.next, list2)
//         return list1
//     } else {
//         list2.next = mergeTwoLists(list1, list2.next)
//         return list2
//     }
// }

// 迭代
var mergeTwoLists = function(list1, list2) {
    const dummy = new ListNode()
    let curr = dummy
    while (list1 && list2) {
        list1.val < list2.val
            ? [curr.next, list1] = [list1, list1.next]
            : [curr.next, list2] = [list2, list2.next]
        curr = curr.next
    }
    curr.next = list1 ?? list2
    return dummy.next
}

42. 接雨水

Description

Difficulty: 困难

Related Topics: 栈, 数组, 双指针, 动态规划, 单调栈

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例 1：

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

示例 2：

输入：height = [4,2,0,3,2,5]
输出：9

提示：

n == height.length
1 <= n <= 2 * 10⁴
0 <= height[i] <= 10⁵

Solution

Language: JavaScript

/**
 * @param {number[]} height
 * @return {number}
 */
// 动态规划
var trap = function(height) {
    const n = height.length
    const left = new Array(n).fill(0)
    const right = new Array(n).fill(0)
    let ans = 0
    for (let i = 1; i < n; i++) {
        left[i] = Math.max(left[i-1], height[i-1])
    }
    for (let i = n - 2; i >= 0; i--) {
        right[i] = Math.max(right[i+1], height[i+1])

        let short = Math.min(left[i], right[i])
        if (short > height[i]) {
            ans += short - height[i]
        }
    }
    return ans
}

14. 最长公共前缀

Description

Difficulty: 简单

Solution

Language: JavaScript

/**
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function(strs) {
    let re = strs[0] || ''
    if (strs.length === 1) return strs[0]

    for (let i = 1; i < strs.length; i++) {
        while (strs[i].slice(0, re.length) !== re) {
            re = re.slice(0, re.length - 1)
        }
    }

    return re
};

142. 环形链表 II

Description

Difficulty: 中等

Related Topics: 哈希表, 链表, 双指针

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表。

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。

提示：

链表中节点的数目范围在范围 [0, 10⁴] 内
-10⁵ <= Node.val <= 10⁵
pos 的值为 -1 或者链表中的一个有效索引

**进阶：**你是否可以使用 O(1) 空间解决此题？

Solution

Language: JavaScript

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
// 快慢指针
// 快慢指针初始化指向 head
// 快指针走到末尾时停止
// 慢指针走一步，快指针走两步
// 快慢指针相遇，说明含有环
// 任一一节点指向头节点
// 同步向前进
// 返回入口节点
var detectCycle = function(head) {
    let slow = head
    let fast = head
    while (fast && fast.next) {
        slow = slow.next
        fast = fast.next.next
        if (slow === fast) {
            fast = head
            while (fast !== slow) {
                fast = fast.next
                slow = slow.next
            }
            return fast
        }
    }
    return null
}

// 哈希表
// var detectCycle = function(head) {
//     const map = new Map()
//     let p = head
//     while (p) {
//         if (map.get(p)) return p
//         else {
//             map.set(p, p.val)
//             p = p.next
//         }
//     }
//     return null
// }

// var detectCycle = function(head) {
//     const set = new Set()
//     while (head) {
//         if (set.has(head)) return head
//         else {
//             set.add(head)
//             head = head.next
//         }
//     }
//     return null
// }

43. 字符串相乘

Description

Difficulty: 中等

Related Topics: 数学, 字符串, 模拟

给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。

**注意：**不能使用任何内置的 BigInteger 库或直接将输入转换为整数。

示例 1:

输入: num1 = "2", num2 = "3"
输出: "6"

示例 2:

输入: num1 = "123", num2 = "456"
输出: "56088"

提示：

1 <= num1.length, num2.length <= 200
num1 和 num2 只能由数字组成。
num1 和 num2 都不包含任何前导零，除了数字0本身。

Solution

Language: JavaScript

/**
 * @param {string} num1
 * @param {string} num2
 * @return {string}
 */
var multiply = function(num1, num2) {
 if (num1 === '0' || num2 === '0') return '0'
 let len1 = num1.length, len2 = num2.length, res = new Array(len1 + len2).fill(0)
 for (let i = len1 - 1; i >= 0; i--) {
  for (let j = len2 - 1; j >= 0; j--) {
   const mul = num1[i] * num2[j]
   const p1 = i + j, p2 = i + j + 1
   const sum = mul + res[p2]
   res[p1] += Math.floor(sum / 10)
   res[p2] = sum % 10
  }
 }
 if (res[0] === 0) res.shift()
 return res.join('')
};

31. 下一个排列

Description

Difficulty: 中等

Solution

Language: JavaScript

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
// a[i-1] a[j]
var nextPermutation = function(nums) {
    const len = nums.length
    let i = len - 2
    // 找到第一个当前项比后一项小的位置
    while (i >= 0 && nums[i] >= nums[i+1]) i--
    // i>=0，说明此时不是最大的排序
    if (i >= 0) {
        let j = len - 1
        // 找到最小的比nums[i]大的数对应的j
        while (j > i && nums[i] >= nums[j]) j--
        // 交换位置
        [nums[i], nums[j]] = [nums[j], nums[i]]
    }
    // i后面的数升序排序
    let [left, right] = [i + 1, len - 1]
    while (left < right) {
        [nums[left], nums[right]] = [nums[right], nums[left]]
        left++
        right--
    }
}

128. 最长连续序列

Description

Difficulty: 中等

Related Topics: 并查集, 数组, 哈希表

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为 O(n)的算法解决此问题。

示例 1：

输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

示例 2：

输入：nums = [0,3,7,2,5,8,4,6,0,1]
输出：9

提示：

0 <= nums.length <= 10⁵
-10⁹ <= nums[i] <= 10⁹

Solution

Language: JavaScript

/**
 * @param {number[]} nums
 * @return {number}
 */
// 1.将数组元素存入set中
// 2.遍历nums，如果当前项-1存在于set，说明当前项不是连续序列的起点，忽略，继续遍历
// 3.如果当前项没有“左邻居”，它就是连续序列的起点，循环查看当前项连续的右邻居有多少个
// 4.返回最长的连续次数
var longestConsecutive = function (nums) {
    // 把数组的数字全部放入set中，一来去重，二来方便快速查找
    const set = new Set(nums)
    let max = 0
    for (let val of nums) {
        // 没有左邻居，是序列的起点，才开始数数
        if (!set.has(val - 1)) {
            let count = 1
            let now = val
            // 有右邻居，看连续的右邻居右多少个
            while (set.has(now + 1)) {
                now++
                count++
            }
            // 存放最大的连续邻居的值
            max = Math.max(max, count)
        }
    }
    return max
}

160. 相交链表

Description

Difficulty: 简单

Related Topics: 哈希表, 链表, 双指针

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

图示两个链表在节点 c1 开始相交**：**

题目数据保证整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

自定义评测：

评测系统 的输入如下（你设计的程序 不适用 此输入）：

intersectVal - 相交的起始节点的值。如果不存在相交节点，这一值为 0
listA - 第一个链表
listB - 第二个链表
skipA - 在 listA 中（从头节点开始）跳到交叉节点的节点数
skipB - 在 listB 中（从头节点开始）跳到交叉节点的节点数

评测系统将根据这些输入创建链式数据结构，并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点，那么你的解决方案将被 视作正确答案 。

示例 1：

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
— 请注意相交节点的值不为 1，因为在链表 A 和链表 B 之中值为 1 的节点 (A 中第二个节点和 B 中第三个节点) 是不同的节点。换句话说，它们在内存中指向两个不同的位置，而链表 A 和链表 B 中值为 8 的节点 (A 中第三个节点，B 中第四个节点) 在内存中指向相同的位置。

示例 2：

输入：intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Intersected at '2'
解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [1,9,1,2,4]，链表 B 为 [3,2,4]。
在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。

示例 3：

输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。
由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
这两个链表不相交，因此返回 null 。

提示：

listA 中节点数目为 m
listB 中节点数目为 n
1 <= m, n <= 3 * 10⁴
1 <= Node.val <= 10⁵
0 <= skipA <= m
0 <= skipB <= n
如果 listA 和 listB 没有交点，intersectVal 为 0
如果 listA 和 listB 有交点，intersectVal == listA[skipA] == listB[skipB]

**进阶：**你能否设计一个时间复杂度 O(m + n) 、仅用 O(1) 内存的解决方案？

Solution

Language: JavaScript

/**
 * 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) {
//     const set = new Set()
//     let temp = headA
//     while (temp) {
//         set.add(temp)
//         temp = temp.next
//     }
//     temp = headB
//     while (temp) {
//         if (set.has(temp)) return temp
//         temp = temp.next
//     }
//     return null
// }

// 哈希集合
// var getIntersectionNode = function(headA, headB) {
//     const map = new Map()
//     let temp = headA
//     while (temp) {
//         map.set(temp)
//         temp = temp.next
//     }
//     temp = headB
//     while (temp) {
//         if (map.has(temp)) return temp
//         temp = temp.next
//     }
//     return null
// }

// 双指针
var getIntersectionNode = function(headA, headB) {
    if (headA === null || headB === null) return null
    let pA = headA, pB = headB
    while (pA !== pB) {
        pA = pA === null ? headB : pA.next
        pB = pB === null ? headA : pB.next
    }
    return pA
}

22. 括号生成

Description

Difficulty: 中等

Related Topics: 字符串, 动态规划, 回溯

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例 1：

输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]

示例 2：

输入：n = 1
输出：["()"]

提示：

1 <= n <= 8

Solution

Language: JavaScript

/**
 * @param {number} n
 * @return {string[]}
 */
// 回溯法(DFS)
var generateParenthesis = function(n) {
    const res = []
    const backtrack = (left, right, str) => {
        if (left === n && right === n) return res.push(str)
        if (left < n) backtrack(left + 1,  right, str + '(')
        if (right < left) backtrack(left, right + 1, str + ')')
    }
    backtrack(0, 0, '')
    return res
}

5. 最长回文子串

Description

Difficulty: 中等

Solution

Language: JavaScript

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
    let max = ''
    
    for (let i = 0; i < s.length; i++) {
        helper(i, i)
        helper(i, i+1)
    }

    function helper(l, r) {
        while(l >= 0 && r < s.length && s[l] === s[r]) {
            l--
            r++
        }
        const maxStr = s.slice(l + 1, r - 1 + 1)
        if (maxStr.length > max.length) max = maxStr
    }

    return max
}

15. 三数之和

Description

Difficulty: 中等

Related Topics: 数组, 双指针, 排序

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

**注意：**答案中不可以包含重复的三元组。

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。

示例 2：

输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。

示例 3：

输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。

提示：

3 <= nums.length <= 3000
-10⁵ <= nums[i] <= 10⁵

Solution

Language: JavaScript

/**
 * @param {number[]} nums
 * @return {number[][]}
 */

var threeSum = function(nums) {
    let ans = []
    const len = nums.length
    if (nums === null || len < 3) return ans
    nums.sort((a, b) => a - b)

    for (let i = 0; i < nums.length; i++) {
        if (nums[0] > 0) break
        if (i > 0 && nums[i] === nums[i - 1]) continue
        let l = i + 1
        let r = len - 1
        while (l < r) {
            const sum = nums[i] + nums[l] + nums[r]
            if (sum === 0) {
                ans.push([nums[i], nums[l], nums[r]])
                while(l < r && nums[l] === nums[l+1]) l++
                while(l < r && nums[r] === nums[r-1]) r--
                l++
                r--
            }
            else if (sum < 0) l++
            else if (sum > 0) r--
        }
    }

    return ans
}

25. K 个一组翻转链表

Description

Difficulty: 困难

Solution

Language: JavaScript

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
const myReverse = (head, tail) => {
    let prev = tail.next;
    let p = head;
    while (prev !== tail) {
        const nex = p.next;
        p.next = prev;
        prev = p;
        p = nex;
    }
    return [tail, head];
}

var reverseKGroup = function(head, k) {
    const hair = new ListNode(0)
    hair.next = head
    let pre = hair

    while (head) {
        let tail = pre
        // 查看剩余部分长度是否大于等于k
        for (let i = 0; i < k; ++i) {
            tail = tail.next
            if (!tail) {
                return hair.next
            }
        }
        const nex = tail.next;
        [head, tail] = myReverse(head, tail)
        // 把子链表重新接回原链表
        pre.next = head
        tail.next = nex
        pre = tail
        head = tail.next
    }
    return hair.next
};

3. 无重复字符的最长子串

Description

Difficulty: 中等

Related Topics: 哈希表, 字符串, 滑动窗口

给定一个字符串 s ，请你找出其中不含有重复字符的 **最长子串 **的长度。

示例 1:

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

提示：

0 <= s.length <= 5 * 10⁴
s 由英文字母、数字、符号和空格组成

Solution

Language: JavaScript

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    const set = new Set()
    let [l, r, maxLen] = [0, 0, 0]
    while(r < s.length) {
        set.has(s[r]) ? set.delete(s[l++]) : set.add(s[r++])
        maxLen = Math.max(maxLen, set.size)
    }
    return maxLen
}

23. 合并K个升序链表

Description

Difficulty: 困难

Related Topics: 链表, 分治, 堆（优先队列）, 归并排序

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例 1：

输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
  1->4->5,
  1->3->4,
  2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

示例 2：

输入：lists = []
输出：[]

示例 3：

输入：lists = [[]]
输出：[]

提示：

k == lists.length
0 <= k <= 10^4
0 <= lists[i].length <= 500
-10^4 <= lists[i][j] <= 10^4
lists[i] 按升序排列
lists[i].length 的总和不超过 10^4

Solution

Language: JavaScript

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode[]} lists
 * @return {ListNode}
 * 递归合并链表+两两合并
 */
var mergeKLists = function(lists) {
    if (!lists.length) return null
    function merge(l1, l2) {
        if (!l1) return l2
        if (!l2) return l1
        if (l1.val < l2.val) {
            l1.next = merge(l1.next, l2)
            return l1
        } else {
            l2.next = merge(l1, l2.next)
            return l2
        }
    }
    return lists.reduce((pre, cur) => merge(pre, cur))
}

124. 二叉树中的最大路径和

Description

Difficulty: 困难

Related Topics: 树, 深度优先搜索, 动态规划, 二叉树

路径被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。

路径和 是路径中各节点值的总和。

给你一个二叉树的根节点 root ，返回其 最大路径和 。

示例 1：

输入：root = [1,2,3]
输出：6
解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6

示例 2：

输入：root = [-10,9,20,null,null,15,7]
输出：42
解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42

提示：

树中节点数目范围是 [1, 3 * 10⁴]
-1000 <= Node.val <= 1000

Solution

Language: JavaScript

/**
 * 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}
 */
// 最大路径和为根节点+左子树+右子树的深度最大值
// 当前节点往下走的最大值分三种情况：
// 1. 往左走：当前节点+L(左子树的最大深度)
// 2. 往右走：当前节点+R(右子树的最大深度)
// 3. 不走：当前节点如果为负值，直接舍弃返回0
var maxPathSum = function(root) {
    let ans = -Infinity
    dfs(root)
    return ans

    // 从当前节点往下走
    function dfs(root) {
        // 根节点为空直接返回0
        if (!root) return 0
        // 遍历左子树的深度
        let left = dfs(root.left)
        // 遍历右子树的深度
        let right = dfs(root.right)
        // 更新路径的最大值
        ans = Math.max(ans, root.val + left + right)
        // 返回从当前节点往下走的最大值
        return Math.max(0, Math.max(left, right) + root.val)
    }
}

92. 反转链表 II

Description

Difficulty: 中等

Solution

Language: JavaScript

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} left
 * @param {number} right
 * @return {ListNode}
 */
var reverseBetween = function(head, left, right) {
    const dummyNode = new ListNode(-1)
    dummyNode.next = head // 虚拟节点
    let pre = dummyNode
    for (let i = 0; i < left - 1; i++) {
        // pre 遍历到left前一个节点
        pre = pre.next
    }

    let rightNode = pre
    for (let i = 0; i < right - left + 1; i++) {
        // rightNode 遍历到right的位置
        rightNode = rightNode.next
    }

    let leftNode = pre.next // 保存leftNode
    let curr = rightNode.next // 保存rightNode.next

    // 切断left到right的子链
    pre.next = null
    rightNode.next = null

    // 反转left到right的子链
    reverseLinkedList(leftNode)

    // 反转 连接
    pre.next = rightNode
    leftNode.next = curr
    return dummyNode.next
};

const reverseLinkedList = (head) => {
    let pre = null
    let cur = head

    while (cur) {
        const next = cur.next
        cur.next = pre
        pre = cur
        cur = next
    }
}

143. 重排链表

Description

Difficulty: 中等

Related Topics: 栈, 递归, 链表, 双指针

给定一个单链表 L的头节点 head ，单链表 L 表示为：

L0 → L1 → … → Ln - 1 → Ln

请将其重新排列后变为：

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …

不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例 1：

输入：head = [1,2,3,4]
输出：[1,4,2,3]

示例 2：

输入：head = [1,2,3,4,5]
输出：[1,5,2,4,3]

提示：

链表的长度范围为 [1, 5 * 10⁴]
1 <= node.val <= 1000

Solution

Language: JavaScript

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {void} Do not return anything, modify head in-place instead.
 */
// 利用双向队列依次弹出前后对应的节点并进行插入操作
// 首先遍历将链表每一项放入队列
// 每次弹出队列头和队列尾的节点并改变指向
// 将尾节点（队列中的最后一个元素）的next赋值为null
var reorderList = function(head) {
    if (head === null) return head
    let queue = []
    let p = head
    while (p) {
        queue.push(p)
        p = p.next
    }
    while (queue.length > 2) {
        let h = queue.shift()
        let t = queue.pop()
        t.next = h.next
        h.next = t
    }
    queue[queue.length-1].next = null
    return head
};

206. 反转链表

Description

Difficulty: 简单

Solution

Language: JavaScript

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
// 假设链表为 1→2→3→∅，我们想要把它改成 ∅←1←2←3。
// 迭代
var reverseList = function(head) {
    let prev = null
    let curr = head
    while (curr) {
        [curr.next, prev, curr] = [prev, curr, curr.next]
    }
    return prev
};

// 递归
// var reverseList = function(head) {
//     if (head === null || head.next === null) {
//         return head
//     }

//     const nextHead = reverseList(head.next)
//     head.next.next = head
//     head.next = null
//     return nextHead
// }

20. 有效的括号

Description

Difficulty: 简单

Solution

Language: JavaScript

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
    if (s.length % 2 !== 0) return false
    const map = {
        '(' : ')',
        '{' : '}',
        '[' : ']',
    }
    let stack = []
    for (let char of s) {
        if (map[char]) {
            stack.push(map[char])
        } else {
            let ret = stack.pop()
            if (ret !== char) {
                return false   
            }
        }
    }
    return stack.length === 0
}

56. 合并区间

Description

Difficulty: 中等

Solution

Language: JavaScript

/**
 * @param {number[][]} intervals
 * @return {number[][]}
 */

var merge = function (intervals) {
    let res = []
    intervals.sort((a, b) => a[0] - b[0])

    let prev = intervals[0]

    for (let i = 1; i < intervals.length; i++) {
        let cur = intervals[i]
        if (prev[1] >= cur[0]) {
            prev[1] = Math.max(prev[1], cur[1])
        } else {
            res.push(prev)
            prev = cur
        }
    }

    res.push(prev)
    return res
}

200. 岛屿数量

Description

Difficulty: 中等

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

示例 1：

输入：grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
输出：1

示例 2：

输入：grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
输出：3

提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 300
grid[i][j] 的值为 '0' 或 '1'

Solution

Language: JavaScript

/**
 * @param {character[][]} grid
 * @return {number}
 */
var numIslands = function(grid) {
    let count = 0
    for (let i = 0; i < grid.length; i++) {
        for (let j = 0; j < grid[0].length; j++) {
            if (grid[i][j] == 1) {
                dfs(i, j)
                count++
            }
        }
    }

    function dfs(x, y) {
        grid[x][y] = 0
        if (grid[x-1] && grid[x-1][y] == 1) dfs(x-1, y)
        if (grid[x+1] && grid[x+1][y] == 1) dfs(x+1, y)
        if (grid[x][y-1] == 1) dfs(x, y-1)
        if (grid[x][y+1] == 1) dfs(x, y+1)
    }
    return count
}

1. 两数之和

Description

Difficulty: 简单

Solution

Language: JavaScript

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    let map = new Map()
    for (let i = 0; i < nums.length; i++) {
        if (map.has(target - nums[i])) {
            return [map.get(target-nums[i]), i]
        }
        map.set(nums[i], i)
    }
    return [-1, -1]
}

215. 数组中的第K个最大元素

Description

Difficulty: 中等

Related Topics: 数组, 分治, 快速选择, 排序, 堆（优先队列）

给定整数数组 nums 和整数 k，请返回数组中第 **k** 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1:

输入: [3,2,1,5,6,4], k = 2
输出: 5

示例 2:

输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4

提示：

1 <= k <= nums.length <= 10⁵
-10⁴ <= nums[i] <= 10⁴

Solution

Language: JavaScript

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
// 数组排序，取第 k 个数
// var findKthLargest = function (nums, k) {
//     nums.sort((a, b) => b - a).slice(0, k)
//     return nums[k - 1]
// };

// 构造前 k 个最大元素小顶堆，取堆顶
// 从数组中取出 k 个元素构造一个小顶堆，然后将其余元素与小顶堆对比，如果大于堆顶则替换堆顶，然后堆化，所有元素遍历完成后，堆中的堆顶即为第 k 个最大值
var findKthLargest = function (nums, k) {
    let heap = [,], i = 0
    while (i < k) {
        heap.push(nums[i++])
    }
    buildHeap(heap, k)

    for (let i = k; i < nums.length; i++) {
        if (heap[1] < nums[i]) {
            heap[1] = nums[i]
            heapify(heap, k, 1)
        }
    }
    return heap[1]
};

let buildHeap = (arr, k) => {
    if (k === 1) return
    for (let i = Math.floor(k/2); i>=1; i--) {
        heapify(arr, k, i)
    }
}

let heapify = (arr, k, i) => {
    while(true) {
        let minIndex = i
        if (2*i <= k && arr[2*i] < arr[i]) {
            minIndex = 2*i
        }
        if (2*i+1 <= k && arr[2*i+1] <arr[minIndex]) {
            minIndex = 2*i + 1
        }
        if (minIndex !== i) {
            swap(arr, i, minIndex)
            i = minIndex
        } else {
            break
        }
    }
}

let swap = (arr, i, j) => {
    let temp = arr[i]
    arr[i] = arr[j]
    arr[j] = temp
}

102. 二叉树的层序遍历

Description

Difficulty: 中等

Related Topics: 树, 广度优先搜索, 二叉树

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。（即逐层地，从左到右访问所有节点）。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]

示例 2：

输入：root = [1]
输出：[[1]]

示例 3：

输入：root = []
输出：[]

提示：

树中节点数目在范围 [0, 2000] 内
-1000 <= Node.val <= 1000

Solution

Language: JavaScript

/**
 * 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 levelOrder = function(root) {
    const ans = []
    if (!root) return ans
    const q = []
    q.push(root) // 初始化队列
    while (q.length) {
        const len = q.length // 当前层节点的数量
        ans.push([]) // 新的层推入数组
        for (let i = 1; i <= len; i++) {
            const node = q.shift()
            // 推入当前层的数组
            ans[ans.length - 1].push(node.val)
            // 检查左节点，存在左节点就继续加入队列
            if (node.left) q.push(node.left)
            if (node.right) q.push(node.right)
        }
    }
    return ans
}

33. 搜索旋转排序数组

Description

Difficulty: 中等

Solution

Language: JavaScript

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 * 二分搜索
 * 关键字：排序，搜索
 * [4,5,6,7,8,9,0,1,2,3]
 */
var search = function(nums, target) {
    let [left, right] = [0, nums.length - 1]
    while (left <= right) {
        const mid = (left + right) >>> 1
        if (nums[mid] === target) return mid

        if (nums[mid] > nums[right]) {
            if (nums[left] <= target && target < nums[mid]) right = mid - 1
            else left = mid + 1 // nums[mid] < target
        } else {
            if (nums[right] >= target && target > nums[mid]) left = mid + 1
            else right = mid - 1
        }
    }
    return -1
}

64. 最小路径和

Description

Difficulty: 中等

Related Topics: 数组, 动态规划, 矩阵

给定一个包含非负整数的 _m_ x _n_ 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

**说明：**每次只能向下或者向右移动一步。

示例 1：

输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。

示例 2：

输入：grid = [[1,2,3],[4,5,6]]
输出：12

提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 200
0 <= grid[i][j] <= 100

Solution

Language: JavaScript

/**
 * @param {number[][]} grid
 * @return {number}
 */
var minPathSum = function(grid) {
    if (grid === null || grid.length === 0 || grid[0].length === 0) {
        return 0
    }

    let row = grid.length, col = grid[0].length

    const dp = new Array(row).fill(0).map(() => new Array(col).fill(0))
    dp[0][0] = grid[0][0]

    for (let i = 1; i < row; i++) {
        dp[i][0] = dp[i-1][0] + grid[i][0]
    }

    for (let j = 1; j < col; j++) {
        dp[0][j] = dp[0][j-1] + grid[0][j]
    }

    for (let i = 1; i < row; i++) {
        for (let j = 1; j < col; j++) {
            dp[i][j] = Math.min(dp[i][j-1], dp[i-1][j]) + grid[i][j]
        }
    }

    return dp[row-1][col-1]
}

141. 环形链表

Description

Difficulty: 简单

Related Topics: 哈希表, 链表, 双指针

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。**注意：pos 不作为参数进行传递 **。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。否则，返回 false 。

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

输入：head = [1], pos = -1
输出：false
解释：链表中没有环。

提示：

链表中节点的数目范围是 [0, 10⁴]
-10⁵ <= Node.val <= 10⁵
pos 为 -1 或者链表中的一个 有效索引 。

**进阶：**你能用 O(1)（即，常量）内存解决此问题吗？

Solution

Language: JavaScript

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {boolean}
 */
// 快慢指针
// 快慢指针初始化指向 head
// 快指针走到末尾时停止
// 慢指针走一步，快指针走两步
// 快慢指针相遇，说明含有环，否则不含有环
var hasCycle = function(head) {
    let slow = head
    let fast = head
    while (fast && fast.next) {
        slow = slow.next
        fast = fast.next.next
        if (slow === fast) {
            return true
        }
    }
    return false
}

// 哈希表
// var hasCycle = function(head) {
//     const map = new Map()
//     let p = head
//     while (p) {
//         if (map.get(p)) return true
//         else {
//             map.set(p, p.val)
//             p = p.next
//         }
//     }
//     return false

94. 二叉树的中序遍历

Description

Difficulty: 简单

Related Topics: 栈, 树, 深度优先搜索, 二叉树

给定一个二叉树的根节点 root ，返回 它的中序遍历 。

示例 1：

输入：root = [1,null,2,3]
输出：[1,3,2]

示例 2：

输入：root = []
输出：[]

示例 3：

输入：root = [1]
输出：[1]

提示：

树中节点数目在范围 [0, 100] 内
-100 <= Node.val <= 100

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

Solution

Language: JavaScript

/**
 * 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) {
    const res = []
    let stack = []
    while (root || stack.length) {
        while (root) {
            stack.push(root)
            root = root.left
        }
        root = stack.pop()
        res.push(root.val)
        root = root.right
    }
    return res
}

232. 用栈实现队列

Description

Difficulty: 简单

Solution

Language: JavaScript

// 双栈
// 将一个栈当作输入栈，用于压入 push 传入的数据；另一个栈当作输出栈，用于pop和peek操作
// 每次pop或peek时，若输出栈为空则将输入栈的全部数据依次弹出并压入输出栈，这样输出栈从栈顶往栈底的顺序就是队列从队首往队尾的顺序
var MyQueue = function() {
    // 用来入栈
    this.stack1 = []
    // 用来出栈
    this.stack2 = []
};

/** 
 * @param {number} x
 * @return {void}
 */
MyQueue.prototype.push = function(x) {
    this.stack1.push(x)
};

/**
 * @return {number}
 */
MyQueue.prototype.pop = function() {
    // 只要 stack2 有值，就直接return
    if (this.stack2.length > 0) {
        return this.stack2.pop()
    }

    // 当 stack2 为空的时候，将 stack1 的值放到 stack2 中
    while (this.stack1.length > 0) {
        this.stack2.push(this.stack1.pop())
    }

    return this.stack2.pop()
};

/**
 * @return {number}
 */
MyQueue.prototype.peek = function() {
    let tmp = this.pop()
    this.stack2.push(tmp)
    return tmp
};

/**
 * @return {boolean}
 */
MyQueue.prototype.empty = function() {
    return this.stack1.length === 0 && this.stack2.length === 0
};

/**
 * Your MyQueue object will be instantiated and called as such:
 * var obj = new MyQueue()
 * obj.push(x)
 * var param_2 = obj.pop()
 * var param_3 = obj.peek()
 * var param_4 = obj.empty()
 */

41. 缺失的第一个正数

Description

Difficulty: 困难

Solution

Language: JavaScript

/**
 * @param {number[]} nums
 * @return {number}
 */
var firstMissingPositive = function(nums) {
    for (let i = 0; i < nums.length; i++) {
        // 循环nums，当前元素在(0, nums.length)之间，并且nums[nums[i]-1] !== nums[i], 则交换位置
        while (nums[i] > 0 && nums[i] <= nums.length && nums[nums[i] - 1] !== nums[i]) {
            const temp = nums[nums[i] - 1]
            nums[nums[i] - 1] = nums[i]
            nums[i] = temp
        }
    }
    for (let i = 0; i < nums.length; i++) {
        // 循环交换位置之后的数组，判断第一个缺失的正数
        if (nums[i] !== i+1) {
            return i+1
        }
    }
    return nums.length + 1
};

76. 最小覆盖子串

Description

Difficulty: 困难

Related Topics: 哈希表, 字符串, 滑动窗口

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

注意：

对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
如果 s 中存在这样的子串，我们保证它是唯一的答案。

示例 1：

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"

示例 2：

输入：s = "a", t = "a"
输出："a"

示例 3:

输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。

提示：

1 <= s.length, t.length <= 10⁵
s 和 t 由英文字母组成

**进阶：**你能设计一个在 o(n) 时间内解决此问题的算法吗？

Solution

Language: JavaScript

/**
 * @param {string} s
 * @param {string} t
 * @return {string}
 */
// 将需要匹配的字符放入字典表，存储结构为需要匹配的字符，以及字符出现的次数：[字符，次数]
// 利用双指针维护一个滑动窗口，不断移动右指针
// 判断右指针的字符是否与字典表中的匹配
// 是：将字典表中的次数-1，直到为0 （创建一个needType）记录需要匹配的字符数量，初始长度为Map的size，当对应的字符次数为0时，就减1
// 否：继续移动右指针
// 当needType的值为0时，就证明在当前窗口所有字符都匹配成功了
// 1.移动左指针，缩小滑动窗口的大小
// 2.移动过程中判断左指针指向的值是否为字典中值，如果是就证明匹配的值少了一个，这个需要更新Map中的次数，以及needType的数量
// 3.记录每次窗口中的字符，找到最小的返回
var minWindow = function(s, t) {
    // 创建左指针
    let l = 0
    // 创建右指针
    let r = 0
    // 最后需要返回的最小长度子串
    let res = ''
    // 创建字典表
    const m = new Map()
    // 遍历需要匹配的字符
    for (let i = 0; i < t.length; i++) {
        const c = t[i]
        // 放入字典表
        m.set(c, m.has(c) ? m.get(c) + 1 : 1)
    }
    // 创建记录需要匹配的字符种类
    let needType = m.size
    // 遍历字符串
    while (r < s.length) {
        // 获取当前字符
        const c = s[r]
        // 如果是需要匹配的字符
        if (m.has(c)) {
            // 更新字典表中的次数-1
            m.set(c, m.get(c) - 1)
            // 如果次数为0，证明这个字符种类在当前窗口已经集齐了，needType-1
            if (m.get(c) === 0) needType -= 1
        }
        // 当needType为0，证明所有需要匹配的字符串都已经在当前滑动窗口中
        while (needType === 0) {
            const c2 = s[l]
            // 记录当前滑动窗口的字符
            let newRes = s.slice(l, r + 1)
            // 当新的窗口中字符长度小于上次的字符长度时，更新结果
            // !res 是在结构值为空的时候需要更新一下第一次匹配的值
            if (!res || newRes.length < res.length) res = newRes
            // 如果左指针移动过程中出现，字典中的值证明需要匹配的字符已经脱离了当前窗口
            if (m.has(c2)) {
                // 更新表中需要出现的次数
                m.set(c2, m.get(c2) + 1)
                // 更新needType
                if (m.get(c2) === 1) needType += 1
            }
            // 移动左指针
            l++
        }
        // 移动右指针
        r++
    }
    // 返回结果值
    return res
}

7. 整数反转

Description

Difficulty: 中等

Solution

Language: JavaScript

/**
 * @param {number} x
 * @return {number}
 */
var reverse = function(x) {
    let result = 0

    while(x) {
        result = result * 10 + x % 10
        x = x / 10 | 0
    }

    return (result | 0) === result ? result : 0
};

121. 买卖股票的最佳时机

Description

Difficulty: 简单

Solution

Language: JavaScript

/**
 * @param {number[]} prices
 * @return {number}
 */
// 买入卖出各一次
//  贪心
// var maxProfit = function(prices) {
//     if (prices.length === 0) return 0

//     let min = prices[0]
//     let max = 0

//     for (let p of prices) {
//         min = Math.min(min, p)
//         max = Math.max(max, p - min)
//     }

//     return max
// }

// 动态规划 时间复杂度O(n) 空间复杂度O(n)，dp数组第二维是常数
var maxProfit = function(prices) {
    let n = prices.length
    let dp = new Array(n).fill(0).map(() => new Array(2));

    dp[0][0] = 0
    dp[0][1] = -prices[0]

    for (let i = 1; i < n; i++) {
        dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i])
        dp[i][1] = Math.max(dp[i-1][1], - prices[i])
    }

    return dp[n-1][0]
}

// 压缩空间
// var maxProfit = function(prices) {
//     let n = prices.length
//     let dp = Array.from(new Array(n), () => new Array(2))

//     dp[0] = 0
//     dp[1] = -prices[0]

//     for (let i = 1; i < n; i++) {
//         dp[0] = Math.max(dp[0], dp[1] + prices[i])
//         dp[1] = Math.max(dp[1], -prices[i])
//     }
//     return dp[0]
// }

151. 反转字符串中的单词

Description

Difficulty: 中等

Solution

Language: JavaScript

/**
 * @param {string} s
 * @return {string}
 */
// 使用语言特性
// split(拆分),reverse(翻转),join(连接)
var reverseWords = function(s) {
    return s.trim().split(/\s+/).reverse().join(' ')
};

54. 螺旋矩阵

Description

Difficulty: 中等

Solution

Language: JavaScript

/**
 * @param {number[][]} matrix
 * @return {number[]}
 */
var spiralOrder = function(matrix) {
    let n = []
    while (matrix.length) {
        n = _.concat(n, matrix.shift())
        matrix = _.reverse(_.zip(...matrix))
    }
    return n
};

46. 全排列

Description

Difficulty: 中等

Solution

Language: JavaScript

/**
 * @param {number[]} nums
 * @return {number[][]}
 * 广度优先遍历
 * 深度优先遍历
 */
var permute = function(nums) {
    const ans = []
    const dfs = (item = []) => {
        if (item.length === nums.length) return ans.push([...item])

        nums.forEach(num => {
            if (!item.includes(num)) {
                dfs([...item, num])
            }
        })
    }
    dfs()
    return ans
}