【剑指Offer】简单部分每日五题 - Day 1
z0gSh1u 人气:0
今天开始更新leetcode上《剑指Offer》的题解，先从简单难度开始。预计按下列顺序更新：
- 简单难度：每日5题
- 中等难度：每日3题
- 困难难度：每日1题
## 17 - 打印从1到最大的n位数 **要求：**比如打印三位数，就从1打印到999。以此类推。 **题解：**数据范围很小不怕越界，暴力从$1$打到$10^n-1$即可。 ```js /** * @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步，然后快慢指针一起走。快指针到尾部时，慢指针即指向结果。 ```js /** * @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 - 二叉树的镜像 **要求：**输入二叉树，输出它的镜像（每个结点左右子树互换）。 **题解：**对每个结点都交换左右子树，不难想到递归处理（自下而上）。 ```js /** * @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 - 二叉树的深度 **要求：**输入二叉树，输出深度。 **题解：**递归向深处探索。递归函数附加一个参数记录当前深度。 ```js /** * @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 ``` ```js /** * @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 }; ```
## 17 - 打印从1到最大的n位数 **要求：**比如打印三位数，就从1打印到999。以此类推。 **题解：**数据范围很小不怕越界，暴力从$1$打到$10^n-1$即可。 ```js /** * @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步，然后快慢指针一起走。快指针到尾部时，慢指针即指向结果。 ```js /** * @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 - 二叉树的镜像 **要求：**输入二叉树，输出它的镜像（每个结点左右子树互换）。 **题解：**对每个结点都交换左右子树，不难想到递归处理（自下而上）。 ```js /** * @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 - 二叉树的深度 **要求：**输入二叉树，输出深度。 **题解：**递归向深处探索。递归函数附加一个参数记录当前深度。 ```js /** * @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 ``` ```js /** * @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 }; ```
加载全部内容