17 - 打印从1到最大的n位数
要求：比如打印三位数，就从1打印到999。以此类推。
题解：数据范围很小不怕越界，暴力从(1)打到(10^n-1)即可。
/**
* @param {number} n
* @return {number[]}
*/
// 10^n - 1
var printNumbers = function(n) {
let r = []
for (let i = 1; i < Math.pow(10, n); i++) {
r.push(i)
}
return r
};
22 - 链表中倒数第k个节点
要求：输出该链表中倒数第k个节点。（最后一个节点称为倒数第1个）
题解：很容易想到快慢指针。快指针先走k步，然后快慢指针一起走。快指针到尾部时，慢指针即指向结果。
/**
* @param {ListNode} head
* @param {number} k
* @return {ListNode}
*/
var getKthFromEnd = function(head, k) {
let fast = head, slow = head
for (let i = 0; i < k - 1; i++) {
fast = fast.next
}
while (fast.next) {
fast = fast.next
slow = slow.next
}
return slow
};
27 - 二叉树的镜像
要求：输入二叉树，输出它的镜像（每个结点左右子树互换）。
题解：对每个结点都交换左右子树，不难想到递归处理（自下而上）。
/**
* @param {TreeNode} root
* @return {TreeNode}
*/
var mirrorTree = function(root) {
if (root == null) { return null }
let backup = root.left
root.left = root.right
root.right = backup
mirrorTree(root.left)
mirrorTree(root.right)
return root
};
55-I - 二叉树的深度
要求：输入二叉树，输出深度。
题解：递归向深处探索。递归函数附加一个参数记录当前深度。
/**
* @param {TreeNode} root
* @return {number}
*/
var maxDepth = function(root) {
if (root == null) { return 0 }
let res = 0
let deepWalk = function(root, depth) {
if (root.left) { deepWalk(root.left, depth + 1) }
if (root.right) { deepWalk(root.right, depth + 1) }
res = depth > res ? depth : res
}
deepWalk(root, 1)
return res
};
58-II - 左旋转字符串
要求：左旋转指将字符串头k个字符顺序移动到末尾。
题解：字符串切片后拼接、字符串翻倍后截取都可以完成。这里用数学规律“假装”字符串翻倍处理之。
不妨举例，可清楚发现规律：
下标： 01 23456 7 k=2
字符串：abcde len=5
结果： ab|cdeab|cde
分析： 5->0 6->1 ---> mod 5
/**
* @param {string} s
* @param {number} n
* @return {string}
*/
var reverseLeftWords = function(s, n) {
let len = s.length, res = ''
for (let i = n; i < len + n; i++) {
res += s.charAt(i % len)
}
return res
};
05 - 替换空格
要求：把字符串里的空格全部换成%20
题解：循环一遍即可
举一反三：多个连续空格只视为一个如何处理？①找到一个空格后向后找删除所有连续空格；②正则替换
/**
* @param {string} s
* @return {string}
*/
var replaceSpace = function(s) {
let res = ''
for (let i = 0; i < s.length; i++){
res += (s.charAt(i)==' ' ? '%20' : s.charAt(i))
}
return res
};
06 - 从尾到头打印链表
要求：反着打印链表
题解：入栈，然后出栈即可
/**
* @param {ListNode} head
* @return {number[]}
*/
var reversePrint = function(head) {
if (head == null) {return []}
let stack = []
while (head) {
stack.push(head.val)
head = head.next
}
let res = []
while (stack.length != 0) { res.push(stack.pop()) }
return res
};
10-I - 斐波那契数列
要求：输出Fib数列第n项模1e9+7
题解：设定迭代基础f(0)、f(1)，迭代之
/**
* @param {number} n
* @return {number}
*/
var fib = function(n) {
if (n == 0) return 0
if (n == 1) return 1
let a = 0, b = 1, c
for (let i = 2; i <= n;i++) {
c = a
a = b
b = (c + b) % (1e9+7)
}
return b
};
24 - 反转链表
要求：输入链表的头节点，反转链表，输出反转后的头节点
题解：一画图就明白。主要是用r暂存原先的next以便继续操作
/**
* @param {ListNode} head
* @return {ListNode}
*/
var reverseList = function(head) {
if (head == null) { return null }
let p, q, r
p = null, q = head
while (q) {
r = q.next
q.next = p
p = q
q = r
}
return p
};
25 - 合并两个排序的链表
要求：输入两个递增的链表，合并这两个链表为一个递增链表
题解：两个指针一起走，哪个小就接哪个进去。注意①伪头结点的使用；②一个走到尾后另一个直接接后面，不用继续遍历
/**
* @param {ListNode} l1
* @param {ListNode} l2
* @return {ListNode}
*/
var mergeTwoLists = function(l1, l2) {
if (!l1 || !l2) { return l1 ? l1 : l2 }
let res = new ListNode(-1), head = res
while (l1 && l2) {
if (l1.val < l2.val) {
res.next = new ListNode(l1.val)
res = res.next
l1 = l1.next
} else {
res.next = new ListNode(l2.val)
res = res.next
l2 = l2.next
}
}
res.next = (l1 ? l1 : l2)
return head.next
};
04 - 二维数组中的查找
要求：二维数组中，每一行从左到右递增，每一列从上到下递增。找是否存在一个数。
题解：从右上角开始找，要变小就往左，要变大就往下。越界了就是找不到。
/**
* @param {number[][]} matrix
* @param {number} target
* @return {boolean}
*/
var findNumberIn2DArray = function(matrix, target) {
if (!matrix || matrix.length==0){return false}
let row = 0, col = matrix[0].length - 1
while(true){
if (matrix[row][col]==target) {return true}
if (matrix[row][col]>target) {col-=1} else {row+=1}
if (row>=matrix.length || col <0) {return false}
}
};
10-II - 青蛙跳台阶问题
要求：一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个n级的台阶总共有多少种跳法。
题解：斐波那契数列递推之。n步的跳法等于n-1步的跳法加上n-2步的跳法。注意数据中res[0]=1，不必纠结意义。
/**
* @param {number} n
* @return {number}
*/
var numWays = function(n) {
let res = []
res[0] = 1; res[1] = 1; res[2] = 2;
for (let i = 3; i <= n; i++) {
res[i] = (res[i - 1] + res[i - 2]) % (1e9+7)
}
return res[n]
};
58-I - 翻转单词顺序
要求：例如输入: "the sky is blue"；输出: "blue is sky the"。
题解：用空格split，入栈弹出即可。
/**
* @param {string} s
* @return {string}
*/
var reverseWords = function(s) {
s = s.trim()
let stack = s.split(' '), res = '', x
while (stack.length != 0) {
x = stack.pop()
if (x != '' && x != ' ') {
res += x
res += ' '
}
}
return res.substring(0, res.length - 1) // 去除最后一个多余空格
};
40 - 最小的k个数
要求：输入整数数组arr，找出其中最小的k个数。
题解：“正统”做法是优先队列（构造小顶堆，取k个）。C++中自带pq，但JS中不带。手写堆难度超纲，故用此处仅用sort解法，参考价值不大。
注意Array.sort时最好覆写一下cmp函数，避免发生按字典序排序的悲剧。(a,b)=>a-b即为顺序排序。
/**
* @param {number[]} arr
* @param {number} k
* @return {number[]}
*/
var getLeastNumbers = function(arr, k) {
return arr.sort((a, b) => a - b).slice(0, k)
};
50 - 第一个只出现一次的字符
要求：在字符串s中找出第一个只出现一次的字符。
题解：map<char, bool>记录之。注意没必要统计出现次数，避免越界等错误。
/**
* @param {string} s
* @return {character}
*/
var firstUniqChar = function(s) {
let map = {}
for (let i = 0 ; i < s.length; i ++){
if (map[s[i]]){map[s[i]]=-1}else{map[s[i]]=1}
}
for (let i = 0 ; i < s.length; i ++){
if (map[s[i]]==1) return s[i]
}
return ' '
};