亲宝软件园·资讯

展开

【剑指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 }; ```

加载全部内容

相关教程
猜你喜欢
用户评论