xiaolei565

338. 比特位计数(一般)给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。 示例 1:输入: 2输出: [0,1,1] 示例 2:输入: 5输出: [0,1,1,2,1,2] 进阶:给出时间复杂度为O(n*sizeof(integer))的解答非常容易。但你可以在线性时间O(n)内用一趟扫描做到吗？要求算法的空间复杂度为O(n)。你能进一步完善解法吗？要求在C++或任何其他语言中不使用任何内置函数（如 C++ 中的 __builtin_popcount）来执行此操作。 来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/counting-bits 思路：用数组接收，每次i中的1个数一定比i&(i-1)中多1，动态规划思想 代码：1234567891011class Solution { public int[] countBits(int num) { //位运算，dp //去除末尾1中 ...

322. 零钱兑换(基础)给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。 示例 1:输入: coins = [1, 2, 5], amount = 11输出: 3 解释: 11 = 5 + 5 + 1 示例 2:输入: coins = [2], amount = 3输出: -1 说明:你可以认为每种硬币的数量是无限的。 来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/coin-change 思路：dp 用dp[i]表示目标金额为i时需要的硬币数量 这一题是动态规划中的最基础，最经典的，一定要掌握 注意：一定要将初始条件写上，之前调不出来就是没写dp[0]=0，这样就很难受 然后可以将dp数组初始化为amount+1，相当于无穷大 代码：12345678910111213141516171819class Solution { public int coinChange(int[] coins, i ...

309. 最佳买卖股票时机含冷冻期(基础)给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。 设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。 示例:输入: [1,2,3,0,2]输出: 3解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出] 来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown 思路：原本买卖股票的问题上加了一个冷冻期，所以dp[i] [1] =max（dp[i] [1],dp[i-2] [0]-price[i]） 代码后面需要加上熟悉的dp框架 代码：12345678910111213141516class Solution { public int maxProfit(int[] prices) &# ...

297. 二叉树的序列化与反序列化/面试题37. 序列化二叉树(困难)序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。 请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。 示例:你可以将以下二叉树： 1 / \ 2 3 / \ 4 5 序列化为 "[1,2,3,null,null,4,5]" 提示: 这与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。 说明: 不要使用类的成员 / 全局 / 静态变量来存储状态，你的序列化和反序列化算法应该是无状态的。 来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/serialize- ...

295. 数据流的中位数/面试题41. 数据流中的中位数(一般)如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。 例如， [2,3,4] 的中位数是 3 [2,3] 的中位数是 (2 + 3) / 2 = 2.5 设计一个支持以下两种操作的数据结构： void addNum(int num) - 从数据流中添加一个整数到数据结构中。double findMedian() - 返回目前所有元素的中位数。 示例 1：输入：["MedianFinder","addNum","addNum","findMedian","addNum","findMedian"] [[],[1],[2],[],[3],[]]输出：[null,null,null,1.50000,null,2.00000] 示例 2：输入：["MedianFinder ...

292. Nim 游戏(简单)你和你的朋友，两个人一起玩 Nim 游戏：桌子上有一堆石头，每次你们轮流拿掉 1 - 3 块石头。 拿掉最后一块石头的人就是获胜者。你作为先手。 你们是聪明人，每一步都是最优解。 编写一个函数，来判断你是否可以在给定石头数量的情况下赢得游戏。 示例:输入: 4输出: false解释: 如果堆中有 4 块石头，那么你永远不会赢得比赛； 因为无论你拿走 1 块、2 块 还是 3 块石头，最后一块石头总是会被你的朋友拿走。 来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/nim-game 思路1： 如果剩余的石头为0，则当前先手必败。 如果剩余石头为1-3，则当前先手必胜。 思路2：dp，未写 代码1：12345678class Solution { public boolean canWinNim(int n) { //组合数学，游戏平衡问题 //如果剩余的石头为0，则当前先手必败。 //如果剩余石头为1-3，则当前先手必胜。 ...

264. 丑数 II/面试题49. 丑数(简单)编写一个程序，找出第 n 个丑数。 丑数就是只包含质因数 2, 3, 5 的正整数。 示例:输入: n = 10输出: 12解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。说明: 1 是丑数。n 不超过1690。 来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/ugly-number-ii 思路：剑指offer思路：每一个丑数，都是前面某个丑数2，3或5得来的 我们用一个数组接收所有的丑数，设当前最大丑数为M，先考虑前面某个丑数*2，会得到若干小于等于M的数，这些数都不需要，还有若干大于M的数，我们需要第一个，同理 * 3 *5一样，求得了三个大于M的数，下一个丑数就是在三个丑数中取最小的，就是下一个丑数了 dp[i] 表示第i个丑数 那么dp[i] = min(2 * dp[l_2], 3 * dp[l_3], 5 * dp[l_5]) 这里 l_2, l_3, l_5是表示，指到的位置。 时间复杂度：O(n) 代码：12345678 ...

242. 有效的字母异位词(简单)给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。 示例 1:输入: s = “anagram”, t = “nagaram”输出: true 示例 2:输入: s = “rat”, t = “car”输出: false说明:你可以假设字符串只包含小写字母。 进阶:如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？ 来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/valid-anagram 思路：map的思路，用一个数组来实现，下表为key，值为value，循环两个字符串，一个+一个-，这样循环结束时如果数组中有为止出现的数的值为0，则代表匹配成功 代码：12345678910111213141516class Solution { public boolean isAnagram(String s, String t) { if(s.length()!=t.length()) ...

239. 滑动窗口最大值(一般)给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。 返回滑动窗口中的最大值。 示例:输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3输出: [3,3,5,5,6,7]解释: 12345678910滑动窗口的位置 最大值--------------- -----[1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 5 1 3 -1 [-3 5 3] 6 7 5 1 3 -1 -3 [5 3 6] 7 6 1 3 -1 -3 5 [3 6 7] 7 提示： 你可以假设 k 总是有效的，在输入数组不为空的情况下，1 ≤ k ≤ 输入数组的大小。 来源：力扣（Le ...

238. 除自身以外数组的乘积(中等)给你一个长度为 n 的整数数组 nums，其中 n > 1，返回输出数组 output ，其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。 示例:输入: [1,2,3,4]输出: [24,12,8,6] 提示：题目数据保证数组之中任意元素的全部前缀元素和后缀（甚至是整个数组）的乘积都在 32 位整数范围内。 说明: 请不要使用除法，且在 O(n) 时间复杂度内完成此题。 进阶：你可以在常数空间复杂度内完成这个题目吗？（ 出于对空间复杂度分析的目的，输出数组不被视为额外空间。） 来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/product-of-array-except-self 思路1：常规思路，就是先算总数，再除以当前数 思路2：分当前数左右来计算，两个数组left与right，后面循环一次，将对应位置相乘就是要求的数了 代码：1234567891011121314151617181920212223class Solution { ...