小锵的博客

题目信息 题目：剑指 Offer 42. 连续子数组的最大和 时间： 2020-08-30 题目链接：Leetcode tag： 动态规划 难易程度：简单 题目描述： 输入一个整型数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。 要求时间复杂度为O(n)。 示例: 123输入: nums = [-2,1,-3,4,-1,2,1,-5,4]输出: 6解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。 提示 121. 1 <= arr.length <= 10^52. -100 <= arr[i] <= 100 解题思路 本题难点 常见解法 时间复杂度 空间复杂度 暴力搜索 O(N^2) O(1) 分治思想 O(NlogN) O(logN) 动态规划 O(N) O(1) 具体思路 动态规划 状态定义：设动态规划列表 dp ，dp[i]]代表以元素 nums[i] 为结尾的连续子数组最大和。 转移方程： 若 dp[i−1]≤0 ，说明 ...

题目信息 题目：剑指 Offer 43. 1～n整数中1出现的次数 时间： 2020-08-29 题目链接：Leetcode tag： 整除 取余 规律 递归 难易程度：中等 题目描述： 输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数。 例如，输入12，1～12这些整数中包含1 的数字有1、10、11和12，1一共出现了5次。 示例1: 12输入：n = 12输出：5 示例2: 12输入：n = 13输出：6 提示 11. 1 <= n < 2^31 解题思路 本题难点 数字 n 是个 x 位数，记 n 的第 i 位为 n i ，则可将 n 写为 nx nx−1⋯n2 n1，n的位数都可能为1。 具体思路 将 1 ~ n 的个位、十位、百位、…的 1 出现次数相加，即为 1 出现的总次数。 某位中 11出现次数的计算方法： 根据当前位 cur 值的不同，分为以下三种情况： cur=0：此位 1的出现次数只由高位 high决定，high×digit cur=1： 此位 1的出现次数只由高位 high和地位low决 ...

题目信息 题目：剑指 Offer 44. 数字序列中某一位的数字 时间： 2020-08-28 题目链接：Leetcode tag： 规律 难易程度：中等 题目描述： 数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中，第5位（从下标0开始计数）是5，第13位是1，第19位是4，等等。 请写一个函数，求任意第n位对应的数字。 示例1: 12输入：n = 3输出：3 示例2: 12输入：n = 11输出：0 提示 11. 0 <= n < 2^31 解题思路 本题难点 0<n<9时，第n位对应的数字为n。n>9时，需要确定n对应的数字的位数，再确定n对应的数字，最后确定n对应数字的哪一位上。 具体思路 将 101112⋯ 中的每一位称为 数位 ，记为 n； 将 10,11,12,⋯ 称为 数字 ，记为 num ； 数字 10是一个两位数，称此数字的 位数 为 2 ，记为 digit； 每 digit 位数的起始数字（即：1,10,100,⋯），记为 sta ...

题目信息 题目：剑指 Offer 45. 把数组排成最小的数 时间： 2020-08-27 题目链接：Leetcode tag： 快速排序 难易程度：中等 题目描述： 输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。 示例1: 12输入: [10,2]输出: "102" 示例2: 12输入: [3,30,34,5,9]输出: "3033459" 提示 11. 0 < nums.length <= 100 解题思路 本题难点 此题求拼接起来的 “最小数字” ，本质上是一个排序问题。 具体思路 字符串 xy < yx , yz < zy ，需证明 xz < zx 一定成立。 代码 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849class Solution { public String minNumber(int[] nu ...

题目信息 题目：剑指 Offer 46. 把数字翻译成字符串 时间： 2020-08-26 题目链接：Leetcode tag： 动态规划 难易程度：中等 题目描述： 给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。 示例: 123输入: 12258输出: 5解释: 12258有5种不同的翻译，分别是"bccfi", "bwfi", "bczi", "mcfi"和"mzi" 提示 11. 0 <= num < 2^31 解题思路 本题难点 当数字中包含两位数时，存在两种不同的组合情况。 具体思路 动态规划：  num =x1x2…xi−2xi−1xi…xn−1xn (例如 :12258=x1x2x3x4x5)[ 设 x1x2…xi−2 的翻译方案数量为 f(i−2) 设 x1x2…xi−2xi−1 的翻译方案数量为 f(i−1)\begin{arra ...

题目信息 题目：剑指 Offer 47. 礼物的最大价值 时间： 2020-08-25 题目链接：Leetcode tag：动态规划 难易程度：中等 题目描述： 在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？ 示例: 12345678输入: [ [1,3,1], [1,5,1], [4,2,1]]输出: 12解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物 注意 121. 0 < grid.length <= 2002. 0 < grid[0].length <= 200 解题思路 本题难点 根据题目说明，某单元格可能从上边单元格或左边单元格到达。 具体思路 动态规划解决此问题，转移方程f(i,j)=max[f(i,j−1),f(i−1,j)]+grid(i,j) 设动态规划矩阵 dp(i,j) 代表从棋盘的左 ...

题目信息 题目：剑指 Offer 48. 最长不含重复字符的子字符串 时间： 2020-08-24 题目链接：Leetcode tag： 动态规划 哈希表 难易程度：中等 题目描述： 请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。 示例1: 123输入: "abcabcbb"输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。 示例2: 123输入: "bbbbb"输出: 1解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。 示例3: 1234输入: "pwwkew"输出: 3解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。  请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。 注意 11. s.length <= 40000 解题思路 本题难点 长度为 N 的字符串共有 (1+N)N/2 个子字符串（复杂度为 O(N^2 ) ），判断长度为 N 的字符串是否有重复字符的复杂度为 O(N) ，使用暴力法解决的复杂度为 O ...

题目信息 题目：剑指 Offer 49. 丑数 时间： 2020-08-23 题目链接：Leetcode tag：动态规划 小根堆 难易程度：中等 题目描述： 我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。 示例: 123输入: n = 10输出: 12解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。 注意 121. 1是丑数2. n < 1690 解题思路 本题难点 丑数的定义以及查找的方式 具体思路 丑数只包含因子 2,3,5 ，因此有 “丑数 = 某较小丑数 × 某因子” （例如：10=5×2） 设已知长度为 n 的丑数序列 x1,x2,⋯,xn ，求第 n+1 个丑数 xn+1 。根根据递推性质，丑数 x n+1 只可能是以下三种情况其中之一（索引 a,b,c 为未知数）： xn+1={xa×2,a∈[1,n]xb×3,b∈[1,n]xc×5,c∈[1,n]x_{n+1}=\left\{\begin{array}{ll} ...

题目信息 题目：剑指 Offer 50. 第一个只出现一次的字符 时间： 2020-08-22 题目链接：Leetcode tag：哈希表 难易程度：简单 题目描述： 在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。 示例: 12345s = "abaccdeff"返回 "b"s = "" 返回 " " 注意 11. 0 <= s 的长度 <= 50000 解题思路 本题难点 字符串查找第一个只出现一次的字符，性能最优。 具体思路 哈希表 遍历字符串 s：使用哈希表统计 “各字符数量是否 >1 ”。 再遍历字符串 s ：在哈希表中找到首个 “数量为 1的字符”，并返回。 注意 代码 1234567891011class Solution { public char firstUniqChar(String s) { HashMap<Character, Boolean> dic = new HashMap<> ...

题目信息 题目；剑指 Offer 52. 两个链表的第一个公共节点 时间： 2020-08-21 题目链接：Leetcode tag： 单链表 难易程度：简单 题目描述： 输入两个链表，找出它们的第一个公共节点。 示例: 12345A： a1 -> a2 \ -> c1 -> c2 -> c3 /B：b1 -> b2 -> b3 注意 12341. 如果两个链表没有交点，返回 null.2. 在返回结果后，两个链表仍须保持原有的结构。3. 可假定整个链表结构中没有循环。4. 程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。 解题思路 本题难点 两条链表不一样长，其到达交点的路程不一样。时间复杂度有要求。 具体思路 使用两个指针 node1，node2 分别指向两个链表 headA，headB 的头结点，然后同时分别逐结点遍历。 当 node1 到达链表 headA 的末尾时，重新定位到链表 head ...