- 博客(242)
- 收藏
- 关注
RSS订阅原创 [LeetCode]（面试题38）字符串的排列
题目输入一个字符串，打印出该字符串中字符的所有排列。你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。示例:输入：s = "abc"输出：["abc","acb","bac","bca","cab","cba"]限制：1 <= s 的长度 <= 8解题思路求字符串的排列，可以看成两步，第一步求所有可能出现在第一个位置的字符，即把第一个字符与后面所有的字符交换。第二部固定第一个字符，求后面所有字符的排列，也是分成两部分来解。具体思路：先固定第 1 位字符、再固定第
2020-07-25 02:02:25
294
原创 [LeetCode]1025. 除数博弈
题目爱丽丝和鲍勃一起玩游戏，他们轮流行动。爱丽丝先手开局。最初，黑板上有一个数字 N 。在每个玩家的回合，玩家需要执行以下操作：选出任一 x，满足 0 < x < N 且 N % x == 0 。用 N - x 替换黑板上的数字 N 。如果玩家无法执行这些操作，就会输掉游戏。只有在爱丽丝在游戏中取得胜利时才返回 True，否则返回 false。假设两个玩家都以最佳状态参与游戏。示例 1：输入：2输出：true解释：爱丽丝选择 1，鲍勃无法进行操作。示例 2：输入：3输
2020-07-25 01:59:35
231
原创 [LeetCode]95. 不同的二叉搜索树 II
题目给定一个整数 n，生成所有由 1 … n 为节点所组成的 二叉搜索树 。示例：输入：3输出：[ [1,null,3,2], [3,2,null,1], [3,1,null,null,2], [2,1,3], [1,null,2,null,3]]解释：以上的输出对应以下 5 种不同结构的二叉搜索树： 1 3 3 2 1 \ / / / \ \ 3 2
2020-07-25 01:56:53
226
原创 [LeetCode]（面试题17）打印从1到最大的n位数
题目输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数 999。示例 1:输入: n = 1输出: [1,2,3,4,5,6,7,8,9]说明：用返回一个整数列表来代替打印n 为正整数解题思路注：此题与原书有出入代码class Solution { public int[] printNumbers(int n) { int size = (int)Math.pow(10, n)-1;
2020-07-25 01:54:54
169
原创 [LeetCode]（面试题67）把字符串转换成整数
题目写一个函数 StrToInt，实现把字符串转换成整数这个功能。不能使用 atoi 或者其他类似的库函数。首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。当我们寻找到的第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字组合起来，作为该整数的正负号；假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成整数。该字符串除了有效的整数部分之后也可能会存在多余的字符，这些字符可以被忽略，它们对于函数不应该造成影响。注意：假如该字符串中的第一
2020-07-25 01:52:36
153
原创 [LeetCode]（面试题66）构建乘积数组
题目给定一个数组 A[0,1,…,n-1]，请构建一个数组 B[0,1,…,n-1]，其中 B 中的元素 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法。示例:输入: [1,2,3,4,5]输出: [120,60,40,30,24]提示：所有元素乘积之和不会溢出 32 位整数a.length <= 100000解题思路构建两个dp数组，记为left，right，分别维护 i 左侧、右侧元素的连乘积。1）计算每个元素左边所有元素的
2020-07-25 01:49:37
118
原创 [LeetCode]312. 戳气球
题目有 n 个气球，编号为0 到 n-1，每个气球上都标有一个数字，这些数字存在数组 nums 中。现在要求你戳破所有的气球。如果你戳破气球 i ，就可以获得 nums[left] * nums[i] * nums[right] 个硬币。 这里的 left 和 right 代表和 i 相邻的两个气球的序号。注意当你戳破了气球 i 后，气球 left 和气球 right 就变成了相邻的气球。求所能获得硬币的最大数量。说明:你可以假设 nums[-1] = nums[n] = 1，但注意它们不是真实
2020-07-25 01:47:17
83
原创 [LeetCode]97. 交错字符串
题目给定三个字符串 s1, s2, s3, 验证 s3 是否是由 s1 和 s2 交错组成的。示例 1：输入：s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"输出：true示例 2：输入：s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"输出：false解题思路记 |s1| = m，|s2| = n，|s3| = t。1）如果 m+n!=t，显然 s3 必不可能由 s1和 s2 交错组成。2）在 m
2020-07-23 01:48:45
95
原创 [LeetCode]785. 判断二分图
题目给定一个无向图graph，当这个图为二分图时返回true。如果我们能将一个图的节点集合分割成两个独立的子集A和B，并使图中的每一条边的两个节点一个来自A集合，一个来自B集合，我们就将这个图称为二分图。graph将会以邻接表方式给出，graph[i]表示图中与节点i相连的所有节点。每个节点都是一个在0到graph.length-1之间的整数。这图中没有自环和平行边： graph[i] 中不存在i，并且graph[i]中没有重复的值。示例 1:输入: [[1,3], [0,2], [1,3], [
2020-07-23 01:46:33
83
原创 [LeetCode]（面试题65）不用加减乘除做加法
题目写一个函数，求两个整数之和，要求在函数体内不得使用 “+”、“-”、“*”、“/” 四则运算符号。示例:输入: a = 1, b = 1输出: 2提示：a, b 均可能是负数或 0结果不会溢出 32 位整数解题思路无进位和与‘异或运算’规律相同，进位与‘与运算’规律相同（并需左移一位）。因此，无进位和 n 与进位 c 的计算公式如下：非进位和（异或运算）：n = a⊕b 进位（与运算 + 左移一位）：c = a&b<<1 那么 s=a+b ⇒ s
2020-07-23 01:42:00
142
原创 [LeetCode]（面试题63）股票的最大利润
题目假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？示例 1:输入: [7,1,5,3,6,4]输出: 5解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。示例 2:输入: [7,6,4,3,1]输出: 0解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。限制：0 <=
2020-07-23 01:40:01
139
原创 [LeetCode]96. 不同的二叉搜索树
题目给定一个整数 n，求以 1 … n 为节点组成的二叉搜索树有多少种？示例:输入: 3输出: 5解释:给定 n = 3, 一共有 5 种不同结构的二叉搜索树: 1 3 3 2 1 \ / / / \ \ 3 2 1 1 3 2 / / \ \ 2 1 2
2020-07-23 01:37:59
78
原创 [LeetCode]（面试题61）扑克牌中的顺子
题目从扑克牌中随机抽5张牌，判断是不是一个顺子，即这5张牌是不是连续的。2～10为数字本身，A为1，J为11，Q为12，K为13，而大、小王为 0 ，可以看成任意数字。A 不能视为 14。示例 1:输入: [1,2,3,4,5]输出: True示例 2:输入: [0,0,1,2,5]输出: True限制：数组长度为 5数组的数取值为 [0, 13] .解题思路1）先将数组排序；2）统计数组中0出现的次数，用来填补间隔数；3）统计数组中相邻数字之间的开那个数；4）如果数组中
2020-07-23 01:36:26
139
原创 [LeetCode]（面试题60）n个骰子的点数
题目把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s的所有可能的值出现的概率。你需要用一个浮点数数组返回答案，其中第 i 个元素代表这 n 个骰子所能掷出的点数集合中第 i 小的那个的概率。示例 1:输入: 1输出: [0.16667,0.16667,0.16667,0.16667,0.16667,0.16667]示例 2:输入: 2输出: [0.02778,0.05556,0.08333,0.11111,0.13889,0.16667,0.13889,0.11111,
2020-07-23 01:34:22
374
原创 [LeetCode]239. 滑动窗口最大值
题目给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。返回滑动窗口中的最大值。进阶：你能在线性时间复杂度内解决此题吗？示例:输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3输出: [3,3,5,5,6,7] 解释: 滑动窗口的位置 最大值--------------- -----[1 3
2020-07-14 01:42:11
103
原创 [LeetCode]（面试题59 - I）滑动窗口的最大值
题目给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。示例:输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3输出: [3,3,5,5,6,7] 解释: 滑动窗口的位置 最大值--------------- -----[1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -
2020-07-14 01:39:01
179
原创 [LeetCode]350. 两个数组的交集 II
题目给定两个数组，编写一个函数来计算它们的交集。示例 1：输入：nums1 = [1,2,2,1], nums2 = [2,2]输出：[2,2]示例 2:输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]输出：[4,9]说明：输出结果中每个元素出现的次数，应与元素在两个数组中出现次数的最小值一致。我们可以不考虑输出结果的顺序。进阶：如果给定的数组已经排好序呢？你将如何优化你的算法？如果 nums1 的大小比 nums2 小很多，哪种方法更优？
2020-07-14 01:35:45
157
原创 [LeetCode]（面试题58 - II）左旋转字符串
题目字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串"abcdefg"和数字2，该函数将返回左旋转两位得到的结果"cdefgab"。示例 1：输入: s = "abcdefg", k = 2输出: "cdefgab"示例 2：输入: s = "lrloseumgh", k = 6输出: "umghlrlose"限制：1 <= k < s.length <= 10000解题思路解法一：字符
2020-07-14 01:29:14
133
原创 [LeetCode]（面试题58 - I）翻转单词顺序
题目输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串"I am a student. “，则输出"student. a am I”。示例 1：输入: "the sky is blue"输出: "blue is sky the"示例 2：输入: " hello world! "输出: "world! hello"解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。示例 3：输入: "a
2020-07-14 01:25:47
137
原创 [LeetCode]309. 最佳买卖股票时机含冷冻期
题目给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。示例:输入: [1,2,3,0,2]输出: 3 解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]解题思路详细思路见注释代码class Solution { p
2020-07-14 01:21:22
79
原创 [LeetCode]（面试题54）二叉搜索树的第k大节点
题目给定一棵二叉搜索树，请找出其中第k大的节点。示例 1:输入: root = [3,1,4,null,2], k = 1 3 / \ 1 4 \ 2输出: 4示例 2:输入: root = [5,3,6,2,4,null,null,1], k = 3 5 / \ 3 6 / \ 2 4 / 1输出: 4限制：1 ≤ k ≤ 二叉搜索树元素个数解题思路因为二叉搜索树的中序遍历为递增序列，所以求
2020-07-14 01:19:00
113
原创 [LeetCode]（面试题 17.13）恢复空格
题目哦，不！你不小心把一个长篇文章中的空格、标点都删掉了，并且大写也弄成了小写。像句子"I reset the computer. It still didn’t boot!"已经变成了"iresetthecomputeritstilldidntboot"。在处理标点符号和大小写之前，你得先把它断成词语。当然了，你有一本厚厚的词典dictionary，不过，有些词没在词典里。假设文章用sentence表示，设计一个算法，把文章断开，要求未识别的字符最少，返回未识别的字符数。注意：本题相对原题稍作改动，只
2020-07-14 01:15:30
107
原创 [LeetCode]（面试题53 - II）0～n-1中缺失的数字
题目一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。示例 1:输入: [0,1,3]输出: 2示例 2:输入: [0,1,2,3,4,5,6,7,9]输出: 8限制：1 <= 数组长度 <= 10000解题思路因为数组中的数字是排好序的，所以数组开始的一部分一些数字与下标相同。设不在数组中的那个数字为m，那么所有比m小的数字都与它们的下标相同。由于m不
2020-07-14 01:12:44
186
原创 [LeetCode]34. 在排序数组中查找元素的第一个和最后一个位置
题目给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。你的算法时间复杂度必须是 O(log n) 级别。如果数组中不存在目标值，返回 [-1, -1]。示例 1:输入: nums = [5,7,7,8,8,10], target = 8输出: [3,4]示例 2:输入: nums = [5,7,7,8,8,10], target = 6输出: [-1,-1]解题思路详细思路请参考 （面试题53 - I）在排序数组中查找
2020-07-14 01:09:41
90
原创 [LeetCode]（面试题53 - I）在排序数组中查找数字 I
题目统计一个数字在排序数组中出现的次数。示例 1:输入: nums = [5,7,7,8,8,10], target = 8输出: 2示例 2:输入: nums = [5,7,7,8,8,10], target = 6输出: 0限制：0 <= 数组长度 <= 50000解题思路定义递归函数getFirst()，用来查找第一个 target对应的坐标 first：首先分析如何用二分查找算法在数组中找到第一个 target的坐标left。二分查找算法总是先拿数组中间的数
2020-07-14 01:07:16
100
原创 [LeetCode]160. 相交链表
题目输入两个链表，找出它们的第一个公共节点。如下面的两个链表：在节点 c1 开始相交。示例 1：输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3输出：Reference of the node with value = 8输入解释：相交节点的值为 8 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,
2020-07-14 01:02:38
69
原创 [LeetCode]（面试题52）两个链表的第一个公共节点
题目输入两个链表，找出它们的第一个公共节点。如下面的两个链表：在节点 c1 开始相交。示例 1：输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3输出：Reference of the node with value = 8输入解释：相交节点的值为 8 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,
2020-07-14 00:58:20
157
1
原创 [LeetCode]（面试题50）第一个只出现一次的字符
题目在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。示例:s = "abaccdeff"返回 "b"s = "" 返回 " "限制：0 <= s 的长度 <= 50000解题思路解法一：哈希表算法流程：1）初始化 HashMap，记为 map；2）遍历字符串 s 中的每个字符 c，统计字符；2.1）若 map 中不包含键 c ：则向 map中添加键值对 (c, True) ，代表字符 c 的数量为 1;2.2）若 m
2020-07-14 00:53:53
456
原创 [LeetCode]（面试题 16.11）跳水板
题目你正在使用一堆木板建造跳水板。有两种类型的木板，其中长度较短的木板长度为shorter，长度较长的木板长度为longer。你必须正好使用k块木板。编写一个方法，生成跳水板所有可能的长度。返回的长度需要从小到大排列。示例：输入：shorter = 1longer = 2k = 3输出： {3,4,5,6}提示：0 < shorter <= longer0 <= k <= 100000解题思路首先考虑两种边界情况。1）如果 k=0，则不能建造任何跳水
2020-07-14 00:51:39
189
原创 [LeetCode]264. 丑数 II
题目编写一个程序，找出第 n 个丑数。丑数就是质因数只包含 2, 3, 5 的正整数。示例:输入: n = 10输出: 12解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。说明:1 是丑数。n 不超过1690。解题思路详细思路请参考 （面试题49）丑数代码class Solution { public int nthUglyNumber(int n) { if(n<=0){ ret
2020-07-14 00:49:05
64
原创 [LeetCode]263. 丑数
题目编写一个程序判断给定的数是否为丑数。丑数就是只包含质因数 2, 3, 5 的正整数。示例 1:输入: 6输出: true解释: 6 = 2 × 3示例 2:输入: 8输出: true解释: 8 = 2 × 2 × 2示例 3:输入: 14输出: false 解释: 14 不是丑数，因为它包含了另外一个质因数 7。说明：1 是丑数。输入不会超过 32 位有符号整数的范围: [−2^31, 2^31 − 1]。解题思路根据定义，丑数只能被2,3,5整除，所以
2020-07-14 00:46:31
58
原创 [LeetCode]（面试题49）丑数
题目我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。示例:输入: n = 10输出: 12解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。说明:1 是丑数。n 不超过1690。解题思路要算出第n个丑数是多少，需要先算出前n-1个丑数。首先1是丑数，那么1乘以2,3,5得到的乘积也肯定是丑数，也就是说每一个已知的丑数，乘上2,3,5之后都会得到3个更大的丑数(可能有重复)。由于
2020-07-14 00:43:13
157
1
原创 [LeetCode]（面试题48）最长不含重复字符的子字符串
题目请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。示例 1:输入: "abcabcbb"输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。示例 2:输入: "bbbbb"输出: 1解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。示例 3:输入: "pwwkew"输出: 3解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。 请注意，你的答案必须是 子串 的长度，"pwke" 是一个
2020-07-12 19:37:57
224
原创 [LeetCode]（面试题47）礼物的最大价值
题目在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？示例 1:输入: [ [1,3,1], [1,5,1], [4,2,1]]输出: 12解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物提示：0 < grid.length <= 2000 < grid[
2020-07-12 19:33:56
164
原创 [LeetCode]（面试题45）把数组排成最小的数
题目输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。示例 1:输入: [10,2]输出: "102"示例 2:输入: [3,30,34,5,9]输出: "3033459"提示:0 < nums.length <= 100说明:输出结果可能非常大，所以你需要返回一个字符串而不是整数拼接起来的数字可能会有前导 0，最后结果不需要去掉前导 0解题思路设两个数字分别为 x, y，它们能拼接的数字分别为 xy和yx，
2020-07-12 19:31:46
317
原创 [LeetCode]44. 通配符匹配
题目给定一个字符串 (s) 和一个字符模式 (p) ，实现一个支持 '?' 和 '*' 的通配符匹配。'?' 可以匹配任何单个字符。'*' 可以匹配任意字符串（包括空字符串）。两个字符串完全匹配才算匹配成功。说明:s 可能为空，且只包含从 a-z 的小写字母。p 可能为空，且只包含从 a-z 的小写字母，以及字符 ? 和 *。示例 1:输入:s = "aa"p = "a"输出: false解释: "a" 无法匹配 "aa" 整个字符串。示例 2:输入:s = "aa"
2020-07-12 19:29:45
196
原创 [LeetCode]32. 最长有效括号
题目给定一个只包含 ‘(’ 和 ‘)’ 的字符串，找出最长的包含有效括号的子串的长度。示例 1:输入: "(()"输出: 2解释: 最长有效括号子串为 "()"示例 2:输入: ")()())"输出: 4解释: 最长有效括号子串为 "()()"解题思路解法一：动态规划定义 dp[i] 表示以下标 i 字符结尾的最长有效括号的长度，首先将 dp 数组全部初始化为 0 。显然有效的子串一定以 ‘)’ 结尾，因此以 ‘(’ 结尾的子串对应的 dp 值必定为 0 ，我们只需要求解 ‘)’
2020-07-12 19:26:31
75
原创 [LeetCode]（面试题44）数字序列中某一位的数字
题目数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中，第5位（从下标0开始计数）是5，第13位是1，第19位是4，等等。请写一个函数，求任意第n位对应的数字。示例 1：输入：n = 3输出：3示例 2：输入：n = 11输出：0限制：0 <= n < 2^31解题思路详细思路请参考 400. 第N个数字注：数据大时，可能会产生溢出，这时不能使用int，而需要改用long。代码代码1class Solution
2020-07-12 19:15:42
133
原创 [LeetCode]400. 第N个数字
题目在无限的整数序列 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, …中找到第 n 个数字。注意:n 是正数且在32位整数范围内 ( n < 2^31)。示例 1:输入:3输出:3示例 2:输入:11输出:0说明:第11个数字在序列 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ... 里是0，它是10的一部分。解题思路1位数：1~9，共9个，占了19=9位；2位数：10~99，共90个，占了290=180位
2020-07-12 19:13:13
190
原创 [LeetCode]233. 数字 1 的个数
题目给定一个整数 n，计算所有小于等于 n 的非负整数中数字 1 出现的个数。示例:输入: 13输出: 6 解释: 数字 1 出现在以下数字中: 1, 10, 11, 12, 13 。解题思路参考K神思路 面试题43. 1～n 整数中 1 出现的次数代码class Solution { public int countDigitOne(int n) { if(n<=0){ return 0; } int
2020-07-12 19:10:38
84
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人