<h2 style="text-align:start;" size="0" _root="undefined" __ownerid="undefined" __hash="undefined" __altered="false">二叉树的前序遍历</h2>给定一个二叉树，返回它的 前序 遍历。示例: <pre data-lang="javascript" class="lang-javascript"><code>输入: [1,null,2,3] 1 \ 2 / 3 输出: [1,2,3]</code></pre><h3>思路</h3>前序遍历：跟 -&gt; 左 -&gt; 右。<h4>递归：</h4><pre data-lang="javascript" class="lang-javascript"><code>/** * @param {TreeNode} root * @return {number[]} */ var preorderTraversal = function (root) { let ret = []; let node = root; function traverse(node, ret) { if (!node) { return; } ret.push(node.val); if (node.left) { traverse(node.left, ret); } if (node.right) { traverse(node.right, ret); } } traverse(node, ret); return ret; };</code></pre><pre data-lang="javascript" class="lang-javascript"><code>Accepted 68/68 cases passed (68 ms) Your runtime beats 48.83 % of javascript submissions Your memory usage beats 72.22 % of javascript submissions (33.7 MB)</code></pre><h4>循环：</h4><pre><code>/** * @param {TreeNode} root * @return {number[]} */ var preorderTraversal = function (root) { if (!root) { return []; } let ret = []; let stack = []; stack.push(root); while (stack.length) { let node = stack.pop(); ret.push(node.val); if (node.right) { stack.push(node.right); } if (node.left) { stack.push(node.left); } } return ret; };</code></pre><pre><code>Accepted 68/68 cases passed (64 ms) Your runtime beats 69.91 % of javascript submissions Your memory usage beats 72.22 % of javascript submissions (33.8 MB)</code></pre>

LeetCode：二叉树的前序遍历

<h2 style="text-align:start;" size="0" _root="undefined" __ownerid="undefined" __hash="undefined" __altered="false">斐波那契数</h2>斐波那契数，通常用 <code>F(n)</code> 表示，形成的序列称为斐波那契数列。该数列由 <code>0</code> 和 <code>1</code> 开始，后面的每一项数字都是前面两项数字的和。也就是：<pre><code>F(0) = 0,   F(1) = 1 F(N) = F(N - 1) + F(N - 2), 其中 N &gt; 1.</code></pre>给定 <code>N</code>，计算 <code>F(N)</code>。示例: <pre data-lang="javascript" class="lang-javascript"><code>输入：2 输出：1 解释：F(2) = F(1) + F(0) = 1 + 0 = 1. 输入：3 输出：2 解释：F(3) = F(2) + F(1) = 1 + 1 = 2.</code></pre><h3>思路</h3><h4>普通递归</h4><pre><code>/** * @param {number} n * @return {number} */ var fib = function (n) { if (n &lt; 2) return n; return fib(n) + fib(n - 1); };</code></pre><pre><code>Accepted 31/31 cases passed (100 ms) Your runtime beats 10.54 % of javascript submissions Your memory usage beats 60 % of javascript submissions (34.2 MB)</code></pre><h4>循环实现</h4>f(2) = f(1) + f(0) =&gt; f(3) = f(2) + f(1)，所以可以直接从 0 和 1 循环到 n 即可。<pre><code>/** * @param {number} n * @return {number} */ var fib = function (n) { let a = 0; let b = 1; let t = 0; while (n-- &gt; 0) { t = a; a = b; b += t; } return a; };</code></pre><pre><code>Accepted 31/31 cases passed (64 ms) Your runtime beats 67.36 % of javascript submissions Your memory usage beats 84 % of javascript submissions (33.7 MB)</code></pre><h4>尾递归</h4>与循环实现思路一致，改造成尾递归减少调用栈。<pre><code>/** * @param {number} n * @return {number} */ var fib = function (n) { function f(a, b, n) { if (n &lt; 1) return a; return f(b, a + b, n - 1); } return f(0, 1, n); };</code></pre><pre><code>Accepted 31/31 cases passed (56 ms) Your runtime beats 93.71 % of javascript submissions Your memory usage beats 84 % of javascript submissions (33.7 MB)</code></pre>

LeetCode：斐波那契数

<h2 style="text-align:start;" size="0" _root="undefined" __ownerid="undefined" __hash="undefined" __altered="false">存在重复元素</h2>给定一个整数数组，判断是否存在重复元素。 如果任意一值在数组中出现至少两次，函数返回 <code>true</code> 。如果数组中每个元素都不相同，则返回 <code>false</code>。示例: <pre data-lang="javascript" class="lang-javascript"><code>输入: [1,2,3,1] 输出: true 输入: [1,2,3,4] 输出: false 输入: [1,1,1,3,3,4,3,2,4,2] 输出: true</code></pre><h3>思路</h3>利用对象对数字计数<pre data-lang="javascript" class="lang-javascript"><code>/** * @param {number[]} nums * @return {boolean} */ var containsDuplicate = function (nums) { if (!nums || nums.length === 0 || nums.length == 1) return false; if (nums.length === 2) return nums[0] === nums[1]; let map = {}; for (let num of nums) { if (map[num]) { return true; } else { map[num] = !map[num] ? 1 : map[num] + 1; } } return false; };</code></pre>运行结果：<pre data-lang="javascript" class="lang-javascript"><code>Accepted 18/18 cases passed (88 ms) Your runtime beats 54.62 % of javascript submissions Your memory usage beats 41.31 % of javascript submissions (42.6 MB)</code></pre>

给定一个整数数组，判断是否存在重复元素。如果任意一值在数组中出现至少两次，函数返回 true 。如果数组中每个元素都不相同，则返回 false。

LeetCode：存在重复元素

# Leetcode

✅ Solutions to LeetCode by JavaScript.

## 简单

- [两数之和](https://github.com/fantasticit/LeetCode/tree/master/Easy/0001.两数之和.js)
- [整数反转](https://github.com/fantasticit/LeetCode/tree/master/Easy/0007.整数反转.js)
- [回文数](https://github.com/fantasticit/LeetCode/tree/master/Easy/0009.回文数.js)
- [有效的括号](https://github.com/fantasticit/LeetCode/tree/master/Easy/0020.有效的括号.js)
- [合并两个有序链表](https://github.com/fantasticit/LeetCode/tree/master/Easy/0021.合并两个有序链表.js)
- [删除排序数组中的重复项](https://github.com/fantasticit/LeetCode/tree/master/Easy/0026.删除排序数组中的重复项.js)
- [移除元素](https://github.com/fantasticit/LeetCode/tree/master/Easy/0027.移除元素.js)
- [实现-str-str](https://github.com/fantasticit/LeetCode/tree/master/Easy/0028.实现-str-str.js)
- [搜索插入位置](https://github.com/fantasticit/LeetCode/tree/master/Easy/0035.搜索插入位置.js)
- [最大子序和](https://github.com/fantasticit/LeetCode/tree/master/Easy/0053.最大子序和.js)
- [最后一个单词的长度](https://github.com/fantasticit/LeetCode/tree/master/Easy/0058.最后一个单词的长度.js)
- [加一](https://github.com/fantasticit/LeetCode/tree/master/Easy/0066.加一.js)
- [二进制求和](https://github.com/fantasticit/LeetCode/tree/master/Easy/0067.二进制求和.js)
- [爬楼梯](https://github.com/fantasticit/LeetCode/tree/master/Easy/0070.爬楼梯.js)
- [删除排序链表中的重复元素](https://github.com/fantasticit/LeetCode/tree/master/Easy/0083.删除排序链表中的重复元素.js)
- [合并两个有序数组](https://github.com/fantasticit/LeetCode/tree/master/Easy/0088.合并两个有序数组.js)
- [相同的树](https://github.com/fantasticit/LeetCode/tree/master/Easy/0100.相同的树.js)
- [对称二叉树](https://github.com/fantasticit/LeetCode/tree/master/Easy/0101.对称二叉树.js)
- [二叉树的最大深度](https://github.com/fantasticit/LeetCode/tree/master/Easy/0104.二叉树的最大深度.js)
- [二叉树的层次遍历-ii](https://github.com/fantasticit/LeetCode/tree/master/Easy/0107.二叉树的层次遍历-ii.js)
- [平衡二叉树](https://github.com/fantasticit/LeetCode/tree/master/Easy/0110.平衡二叉树.js)
- [二叉树的最小深度](https://github.com/fantasticit/LeetCode/tree/master/Easy/0111.二叉树的最小深度.js)
- [只出现一次的数字](https://github.com/fantasticit/LeetCode/tree/master/Easy/0136.只出现一次的数字.js)
- [环形链表](https://github.com/fantasticit/LeetCode/tree/master/Easy/0141.环形链表.js)
- [反转链表](https://github.com/fantasticit/LeetCode/tree/master/Easy/0206.反转链表.js)
- [最小栈](https://github.com/fantasticit/LeetCode/tree/master/Easy/0155.最小栈.js)
- [移除链表元素](https://github.com/fantasticit/LeetCode/tree/master/Easy/0203.移除链表元素.js)
- [存在重复元素](https://github.com/fantasticit/LeetCode/tree/master/Easy/0217.存在重复元素.js)
- [回文链表](https://github.com/fantasticit/LeetCode/tree/master/Easy/0234.回文链表.js)
- [各位相加](https://github.com/fantasticit/LeetCode/tree/master/Easy/0258.各位相加.js)
- [反转字符串](https://github.com/fantasticit/LeetCode/tree/master/Easy/0344.反转字符串.js)
- [找不同](https://github.com/fantasticit/LeetCode/tree/master/Easy/0389.找不同.js)
- [用队列实现栈](https://github.com/fantasticit/LeetCode/tree/master/Easy/0225.用队列实现栈.js)
- [斐波那契数](https://github.com/fantasticit/LeetCode/tree/master/Easy/0509.斐波那契数.js)
- [二分查找](https://github.com/fantasticit/LeetCode/tree/master/Easy/0704.二分查找)
- [反转字符串-ii](https://github.com/fantasticit/LeetCode/tree/master/Easy/0541.反转字符串-ii.js)

## 中等

- [两数相加](https://github.com/fantasticit/LeetCode/tree/master/Medium/0002.两数相加.js)
- [字符串转换整数-atoi](https://github.com/fantasticit/LeetCode/tree/master/Medium/0008.字符串转换整数-atoi.js)
- [盛最多水的容器](https://github.com/fantasticit/LeetCode/tree/master/Medium/0011.盛最多水的容器.js)
- [三数之和](https://github.com/fantasticit/LeetCode/tree/master/Medium/0015.三数之和.js)
- [最接近的三数之和](https://github.com/fantasticit/LeetCode/tree/master/Medium/0016.最接近的三数之和.js)
- [四数之和](https://github.com/fantasticit/LeetCode/tree/master/Medium/0018.四数之和.js)
- [删除链表的倒数第 n 个节点](https://github.com/fantasticit/LeetCode/tree/master/Medium/0019.删除链表的倒数第n个节点.js)
- [括号生成](https://github.com/fantasticit/LeetCode/tree/master/Medium/0022.括号生成.js)
- [两两交换链表中的节点](https://github.com/fantasticit/LeetCode/tree/master/Medium/0024.两两交换链表中的节点.js)
- [两数相除](https://github.com/fantasticit/LeetCode/tree/master/Medium/0029.两数相除.js)
- [在排序数组中查找元素的第一个和最后一个位置](https://github.com/fantasticit/LeetCode/tree/master/Medium/0034.在排序数组中查找元素的第一个和最后一个位置.js)
- [有效的数独](https://github.com/fantasticit/LeetCode/tree/master/Medium/0036.有效的数独.js)
- [字符串相乘](https://github.com/fantasticit/LeetCode/tree/master/Medium/0043.字符串相乘.js)
- [字母异位词分组](https://github.com/fantasticit/LeetCode/tree/master/Medium/0049.字母异位词分组.js)
- [pow-x-n](https://github.com/fantasticit/LeetCode/tree/master/Medium/0050.pow-x-n.js)
- [二叉树的前序遍历](https://github.com/fantasticit/LeetCode/tree/master/Medium/0144.二叉树的前序遍历.js)
- [lru 缓存机制](https://github.com/fantasticit/LeetCode/tree/master/Medium/0146.lru缓存机制.js)
- [最长上升子序列](https://github.com/fantasticit/LeetCode/tree/master/Medium/0300.最长上升子序列)
- [二叉树的中序遍历](https://github.com/fantasticit/LeetCode/tree/master/Medium/0094.二叉树的中序遍历)

## 困难

- [缺失的第一个正数](https://github.com/fantasticit/LeetCode/tree/master/Hard/0041.缺失的第一个正数.js)
- [最小覆盖子串](https://github.com/fantasticit/LeetCode/tree/master/Hard/0076.最小覆盖子串)
- [二叉树的后序遍历](https://github.com/fantasticit/LeetCode/tree/master/Hard/0145.二叉树的后序遍历)

## LICENSE

MIT


LeetCode 刷题

<h2 style="text-align:start;" size="0" _root="undefined" __ownerid="undefined" __hash="undefined" __altered="false">反转字符串</h2>编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。 不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。 你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。示例: <pre data-lang="javascript" class="lang-javascript"><code>输入：[&quot;h&quot;,&quot;e&quot;,&quot;l&quot;,&quot;l&quot;,&quot;o&quot;] 输出：[&quot;o&quot;,&quot;l&quot;,&quot;l&quot;,&quot;e&quot;,&quot;h&quot;] 输入：[&quot;H&quot;,&quot;a&quot;,&quot;n&quot;,&quot;n&quot;,&quot;a&quot;,&quot;h&quot;] 输出：[&quot;h&quot;,&quot;a&quot;,&quot;n&quot;,&quot;n&quot;,&quot;a&quot;,&quot;H&quot;]</code></pre><h3>思路</h3>前半部分和后半部分两两交换即可。<pre data-lang="javascript" class="lang-javascript"><code>/** * @param {character[]} s * @return {void} Do not return anything, modify s in-place instead. */ var reverseString = function (s) { let len = s.length; let mid = ~~(len / 2); for (let i = 0; i &lt; mid; i++) { let tmp = s[i]; s[i] = s[len - 1 - i]; s[len - 1 - i] = tmp; } };</code></pre>运行结果：<pre data-lang="javascript" class="lang-javascript"><code>Accepted 478/478 cases passed (200 ms) Your runtime beats 11.27 % of javascript submissions Your memory usage beats 95.29 % of javascript submissions (46.7 MB)</code></pre>

LeetCode：反转字符串

<h2 style="text-align:start;" size="0" _root="undefined" __ownerid="undefined" __hash="undefined" __altered="false">找不同</h2>给定两个字符串 s 和 t，它们只包含小写字母。 字符串 t 由字符串 s 随机重排，然后在随机位置添加一个字母。 请找出在 t 中被添加的字母。示例: <pre data-lang="javascript" class="lang-javascript"><code>输入： s = &quot;abcd&quot; t = &quot;abcde&quot; 输出： e 解释： &#x27;e&#x27; 是那个被添加的字母。</code></pre><h3>思路</h3>首先，遍历字符串 <code>s</code> 将出现的各个字符存进对象 <code>m</code> 并进行计数；然后，遍历字符串 <code>t</code> ，同时构建 <code>t</code> 的字符对象 <code>n</code> 。如果字符在 <code>m</code> 中不存在，直接返回字符，若都存在，遍历 <code>n</code> ，比较字符在 <code>m</code> 和 <code>n</code> 中的计数是否相等。<pre data-lang="javascript" class="lang-javascript"><code>/** * @param {string} s * @param {string} t * @return {character} */ var findTheDifference = function (s, t) { let m = {}; let n = {}; for (let i = 0; i &lt; s.length; i++) { m[s[i]] = m[s[i]] ? m[s[i]] + 1 : 1; } for (let j = 0; j &lt; t.length; j++) { if (!m[t[j]]) { return t[j]; } n[t[j]] = n[t[j]] ? n[t[j]] + 1 : 1; } for (let char in n) { if (n[char] !== m[char]) { return char; } } return; };</code></pre>运行结果：<pre data-lang="javascript" class="lang-javascript"><code>Accepted 54/54 cases passed (88 ms) Your runtime beats 22.41 % of javascript submissions Your memory usage beats 53.85 % of javascript submissions (35.9 MB)</code></pre>

给定两个字符串 s 和 t，它们只包含小写字母。字符串 t 由字符串 s 随机重排，然后在随机位置添加一个字母。请找出在 t 中被添加的字母。

LeetCode：找不同

<h2 id="lru">LRU缓存机制</h2>
运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。 
获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。 
写入数据 put(key, value) - 如果密钥已经存在，则变更其数据值；如果密钥不存在，则插入该组「密钥/数据值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。
示例:
<pre><code>LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // 返回 1
cache.put(3, 3); // 该操作会使得密钥 2 作废
cache.get(2); // 返回 -1 (未找到)
cache.put(4, 4); // 该操作会使得密钥 1 作废
cache.get(1); // 返回 -1 (未找到)
cache.get(3); // 返回 3
cache.get(4); // 返回 4
</code></pre>
<h3 id="">思路</h3>
维护待删除 key 值的队列，根据使用情况对 key 值进行位置调整。
<pre><code>/**
 * @param {number} capacity
 */
var LRUCache = function (capacity) {
 this.capacity = capacity;
 this.usedCapacity = 0;
 this.store = Object.create(null);
 this.toDeleteKeys = [];
};

/**
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function (key) {
 if (this.store[key]) {
 this.moveKeyToEnd(key);
 }

 return this.store[key] || -1;
};

LRUCache.prototype.moveKeyToEnd = function (key) {
 let arr = this.toDeleteKeys;
 let idx = this.toDeleteKeys.indexOf(key);

 if (idx &lt; 0) {
 return;
 }

 if (idx === arr.length - 1) {
 return;
 }

 arr.splice(idx, 1);
 arr.push(key);
};

/**
 * @param {number} key
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.put = function (key, value) {
 if (this.store[key]) {
 this.moveKeyToEnd(key);
 this.store[key] = value;
 return;
 }

 this.toDeleteKeys.push(key);

 if (this.usedCapacity &lt; this.capacity) {
 this.store[key] = value;
 this.usedCapacity += 1;
 } else {
 let deleteKey = this.toDeleteKeys.shift();
 delete this.store[deleteKey];
 this.store[key] = value;
 }
};
</code></pre>
运行结果：
<pre><code>Accepted
18/18 cases passed (256 ms)
Your runtime beats 38.35 % of javascript submissions
Your memory usage beats 100 % of javascript submissions (58.9 MB)
</code></pre>

## 双向链表实现

最近最少使用，淘汰最进最久未使用的数据。

### 思路


使用哈希表和双向链表维护所有键值对。


- get：key 不存在，返回 -1；key 存在，通过哈希表定位到节点，移动到链表头部，返回节点值
- put：key 不存在，使用 key/value 构建节点，将节点添加到哈希表并添加到链表头部，然后判断是否超出数量，如果超出，删除链表尾部节点，删除对应哈希；key 存在，通过哈希表获取到节点，更新值，移动节点到链表头部

### 实现


```js
class LinkNode {
 constructor (key, value) {
 this.key = key;
 this.value = value;
 this.prev = null;
 this.next = null;
 }
}

class LRUCache {
 constructor(capacity) {
 this.capacity = capacity; // 容量
 this.size = 0; // 当前数据量
 this.cache = {}; // 哈希表
 this.head = new LinkNode(); // 伪头部节点（不设值）
 this.tail = new LinkNode(); // 伪尾部节点（不设值）
 this.head.next = this.tail;
 this.tail.prev = this.head;
 }

 /**
 * 添加到节点到头部（即伪头部的next）
 * @param {*} node
 */
 addToHead(node) {
 node.prev = this.head;
 node.next = this.head.next;
 this.head.next.prev = node;
 this.head.next = node;
 }

 /**
 * 移除节点（连接其prev和next，实现移除）
 * @param {*} node
 */
 removeNode(node) {
 node.prev.next = node.next;
 node.next.prev = node.prev;
 }

 /**
 * 移动节点到头部（删除后添加到头部）
 */
 moveToHead(node) {
 this.removeNode(node);
 this.addToHead(node);
 }

 /**
 * 移除尾节点（伪尾部节点的 prev，即最近最久未使用）
 */
 removeTail() {
 const node = this.tail.prev;
 this.removeNode(node);
 return node;
 }

 /**
 * 查询
 * @param {*} key
 * @returns
 */
 get(key) {
 if (key in this.cache) {
 const node = this.cache[key];
 this.moveToHead(node); // 移动到头部
 return node.value;
 }
 else {
 return -1;
 }
 }

 /**
 * 存值
 * @param {*} key
 * @param {*} value
 */
 put(key, value) {
 if (key in this.cache) {
 const node = this.cache[key];
 node.value = value;
 this.moveToHead(node)
 }
 else {
 const node = new LinkNode(key, value);
 this.cache[key] = node;
 this.size += 1;
 this.addToHead(node); // 添加到头部

 if (this.size > this.capacity) { // 超出容量，删除数据
 const removedNode = this.removeTail();
 delete this.cache[removedNode.key];
 this.size -= 1;
 }
 }
 }
}

```

LeetCode：LRU缓存机制

<h2 style="text-align:start;" size="0" _root="undefined" __ownerid="undefined" __hash="undefined" __altered="false">用队列实现栈</h2>使用队列实现栈的下列操作：<ul><li>push(x) -- 元素 x 入栈</li><li>pop() -- 移除栈顶元素</li><li>top() -- 获取栈顶元素</li><li>empty() -- 返回栈是否为空</li></ul>注意:<ul><li>你只能使用队列的基本操作-- 也就是 <code>push to back</code>, <code>peek/pop from front</code>, <code>size</code>, 和 <code>is empty</code> 这些操作是合法的。</li><li>你所使用的语言也许不支持队列。 你可以使用 list 或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。</li><li>你可以假设所有操作都是有效的（例如, 对一个空的栈不会调用 pop 或者 top 操作）。</li></ul><h3>思路</h3>队列：先进先出；栈：后进先出。<pre data-lang="javascript" class="lang-javascript"><code>/** * Initialize your data structure here. */ var MyStack = function () { this.elements = []; this.length = 0; }; /** * Push element x onto stack. * @param {number} x * @return {void} */ MyStack.prototype.push = function (x) { this.elements.push(x); this.length += 1; }; /** * Removes the element on top of the stack and returns that element. * @return {number} */ MyStack.prototype.pop = function () { let element = this.elements.pop(); this.length -= 1; return element; }; /** * Get the top element. * @return {number} */ MyStack.prototype.top = function () { return this.elements[this.length - 1]; }; /** * Returns whether the stack is empty. * @return {boolean} */ MyStack.prototype.empty = function () { return this.length === 0; }; /** * Your MyStack object will be instantiated and called as such: * var obj = new MyStack() * obj.push(x) * var param_2 = obj.pop() * var param_3 = obj.top() * var param_4 = obj.empty() */</code></pre>运行结果：<pre data-lang="javascript" class="lang-javascript"><code>Accepted 16/16 cases passed (68 ms) Your runtime beats 38.28 % of javascript submissions Your memory usage beats 100 % of javascript submissions (33.6 MB)</code></pre>