- 博客(271)
- 资源 (2)
- 收藏
- 关注
RSS订阅原创 43. 字符串相乘
题目给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。分析1、去年10月份的时候的做法，涉及到了很多string的加法运算，由于每次string相加，都会设计内存的分配与拷贝，效率很差。因此这次用数组保存中间计算结果，最后再用stringstream拼接到一起，效率会提升很多。2、这里引用LeetCode评论区一位朋友的图。可见，我们可以把每一位的计算结果保存在数组里，最后遍历一遍数组，该进位的进位，该相加的相加。3、用
2022-04-15 01:38:30
972
原创 962. 最大宽度坡
题目给定一个整数数组AAA，坡是元组 (i,j)(i, j)(i,j)，其中 i<ji < ji<j且 A[i]<=A[j]A[i] <= A[j]A[i]<=A[j]。这样的坡的宽度为 j−ij - ij−i。找出 AAA 中的坡的最大宽度，如果不存在，返回 0 。思路先遍历一遍数组，讲单调递减的元素放入栈中，然后从数组末尾开始遍历，用endendend表示末尾开始的元素indexindexindex。当endendend表示的元素不小于栈顶元素的时候，计算一个
2021-11-30 00:45:09
662
原创 leetcode84、85两道单调栈简单记录
简单记录一下，明早还要上班。。。题目：84. 柱状图中最大的矩形给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。求在该柱状图中，能够勾勒出来的矩形的最大面积。解法这道题使用一个栈，遍历一遍高度数组，栈元素为高度对应的index，栈的特点是进栈的高度保持单调递增。所以若当前元素元素大于栈顶元素，则先不进栈，这会破坏栈的单调性。如何操作呢，计算当前栈顶元素为高度的矩形面积。这样高度已经确定了为height[stk.top()],下面确定宽度。注意到，在栈里，s
2021-08-01 23:49:04
268
1
原创 记第一次分手
那天我心里想，2020年的前一半，自己仿佛得到了一切，2020年的后一半，自己仿佛又失去了一切。 一个月前的下午两点零五分，我打开深信服公司的面试链接，约定的面试时间过了五分钟，面试官还没来。虽然我已经签了一个公司，但是不在深圳，我有点后悔之前为什么那么害怕找不到更好的，就草草签了一个薪资还不错的但并不是很大的公司，关键还不在对象所在的城市深圳，一个月前的我，肯定不会想到，在深圳实习了几个月的我，会在深圳找不到一份满意的工作。惯性的想要划开手机，心里想再等十分钟不来小爷不面...
2020-12-07 12:46:08
587
10
原创 下一个更大的元素(1,2,3)
下一个更大的元素1题目给定两个 没有重复元素 的数组 nums1 和 nums2 ，其中nums1 是 nums2 的子集。找到 nums1 中每个元素在 nums2 中的下一个比其大的值。nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。如果不存在，对应位置输出 -1 。示例输入: nums1 = [4,1,2], nums2 = [1,3,4,2].输出: [-1,3,-1]解释: 对于num1中的数字4，你无法在第二个数组
2020-09-09 16:06:52
114
原创 60. 第k个排列
题目给出集合 [1,2,3,…,n]，其所有元素共有 n! 种排列。按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：“123”“132”“213”“231”“312”“321”给定 n 和 k，返回第 k 个排列。说明：给定 n 的范围是 [1, 9]。给定 k 的范围是[1, n!]。示例1输入: n = 3, k = 3输出: "213"示例2输入: n = 4, k = 9输出: "2314"牢骚每天就处于，看过的知识点，看
2020-09-07 16:07:41
192
原创 记鹅厂实习失败转正的一些思绪
前一次去家不远处的小公园时，湖面还结着冰，和爸妈在冰面上行走，20年来无数次这样走，有一段时间我觉得这有何意义，无所事事，平白消磨着时间。但是看着他们卧室上摆的全家福，我又觉得一阵心软，光阴蹉跎，岁月无情。后来新冠突然的爆发，从只有年轻人群注意，到所有人都意识到严重性时，再也出不了家门了。 第二次出门时，明晃晃的阳光让我800度的老近视睁不开眼，我又走到小公园的湖旁，抽芽的树，初开的花，风起带来湖水的阵阵涟漪，让我有一种魔幻的感觉，春天就这样来了吗。 当我意识到要投简历的时候，许多提前批已经将要
2020-08-18 21:49:11
473
5
原创 202.快乐数
题目编写一个算法来判断一个数 n 是不是快乐数。「快乐数」定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。如果 可以变为 1，那么这个数就是快乐数。如果 n 是快乐数就返回 True ；不是，则返回 False 。思考看到这道题，第一时间不能确定的是，循环的终止条件。因为计算个位的平方和是简单的，知道了怎么停下来，这道题就解完了。看了下题解，主要的思想是，证明求平方和的这个过程，是循环的，当发现循环的
2020-06-21 00:07:31
152
原创 ubuntu18.04安装JDK14
下载JDK14链接：https://pan.baidu.com/s/1eb37CvB0xVwzD9H6qLmmYQ提取码：v3r5解压。我解压后拷贝到了/usr/local下修改/etc/profile，在末尾增加下面几行有些博客里面还有jre的相关内容，现在比较新的jdk已经没有jre了。使用source profile来生效。source的作用是在当前bash下，读取并执行脚本...
2020-05-04 22:06:19
1094
原创 739. 每日温度
题目根据每日 气温 列表，请重新生成一个列表，对应位置的输出是需要再等待多久温度才会升高超过该日的天数。如果之后都不会升高，请在该位置用 0 来代替。例如，给定一个列表 temperatures=[73,74,75,71,69,72,76,73]temperatures = [73, 74, 75, 71, 69, 72, 76, 73]temperatures=[73,74,75,71,69...
2020-04-30 09:31:17
210
原创 394. 字符串解码
题目给定一个经过编码的字符串，返回它解码后的字符串。编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4...
2020-04-29 11:44:12
174
原创 347. 前 K 个高频元素
题目给定一个非空的整数数组，返回其中出现频率前 k 高的元素。示例1输入: nums = [1,1,1,2,2,3], k = 2输出: [1,2]实例2输入: nums = [1], k = 1输出: [1]思路一可以通过nums构造一个pair对数组。一个pair对包括<元素频数，元素值>。通过元素频数进行排序，取最高的k个数。排序的效率为 O(nlogn)...
2020-04-29 11:01:48
169
原创 338. 比特位计数
题目给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。示例1输入: 2输出: [0,1,1]示例2输入: 5输出: [0,1,1,2,1,2]思路给定一个数n，就算0~n每个数二进制1的个数，保存在数组res中。有一个规律，如果k为奇数，那么k-1为偶数，那么k的二进制的最低位比k-1多一个...
2020-04-29 10:44:40
111
原创 337. 打家劫舍 III
题目在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。 除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。示例1输入: [3,2,3,...
2020-04-29 10:38:02
125
原创 309. 最佳买卖股票时机含冷冻期
题目给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。示例输入: [1,2,3,0,2]输出: 3解释: 对应的交易状态为: [买入, 卖出...
2020-04-29 09:53:34
103
原创 322. 零钱兑换
题目给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。示例1输入: coins = [1, 2, 5], amount = 11输出: 3 解释: 11 = 5 + 5 + 1示例2输入: coins = [2], amount = 3输出: -1思路看到一个...
2020-04-29 09:09:02
107
原创 301. 删除无效的括号
题目删除最小数量的无效括号，使得输入的字符串有效，返回所有可能的结果。说明输入可能包含了除 ( 和 ) 以外的字符。示例1输入: "()())()"输出: ["()()()", "(())()"]示例2输入: "(a)())()"输出: ["(a)()()", "(a())()"]示例3输入: ")("输出: [""]思路用一个队列保存，每次删除一个括号时的字符...
2020-04-29 08:57:41
339
原创 312. 戳气球
题目有 n 个气球，编号为0 到 n-1，每个气球上都标有一个数字，这些数字存在数组 nums 中。现在要求你戳破所有的气球。每当你戳破一个气球 i 时，你可以获得 nums[left] * nums[i] * nums[right] 个硬币。 这里的 left 和 right 代表和 i 相邻的两个气球的序号。注意当你戳破了气球 i 后，气球 left 和气球 right 就变成了相邻的气球...
2020-04-29 08:53:27
114
原创 300. 最长上升子序列
题目给定一个无序的整数数组，找到其中最长上升子序列的长度。示例输入: [10,9,2,5,3,7,101,18]输出: 4 解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。说明可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。你算法的时间复杂度应该为 O(n2) 。思路一动态规划。dp[i]dp[i]dp[i]表示第i个数为结尾的最长上升...
2020-04-28 23:08:23
103
原创 297. 二叉树的序列化与反序列化
题目序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。示例你可以将以下二叉树： ...
2020-04-28 22:33:32
143
原创 287. 寻找重复数
题目给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。示例1输入: [1,3,4,2,2]输出: 2示例2输入: [3,1,3,4,2]输出: 3说明不能更改原数组（假设数组是只读的）。只能使用额外的 O(1) 的空间。时间复杂度小于 O(n2) 。...
2020-04-28 22:00:59
126
原创 283. 移动零
题目给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。示例输入: [0,1,0,3,12]输出: [1,3,12,0,0]说明必须在原数组上操作，不能拷贝额外的数组。尽量减少操作次数。思路使用双指针left、right。left首先指向第一个元素，如果right不为0，那么right把值覆盖到left上，left和right同时...
2020-04-28 21:44:05
94
原创 279. 完全平方数
题目给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, …）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。示例1输入: n = 12输出: 3 解释: 12 = 4 + 4 + 4.示例2输入: n = 13输出: 2解释: 13 = 4 + 9.思路用平方数填满n，使得用到的平方数最少。则用动态规划，依次计算填满1，2，…，n需要的最少...
2020-04-28 21:37:05
115
原创 240. 搜索二维矩阵 II
题目编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性：每行的元素从左到右升序排列。每列的元素从上到下升序排列。示例现有矩阵 matrix 如下：[ [1, 4, 7, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9, 16, 22], [10, 13, 14, 17...
2020-04-28 21:10:46
122
原创 239. 滑动窗口最大值
题目给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。返回滑动窗口中的最大值。示例输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3输出: [3,3,5,5,6,7] 解释: 滑动窗口的位置 最大值---------...
2020-04-28 21:05:24
140
原创 238. 除自身以外数组的乘积
题目给你一个长度为 n 的整数数组 nums，其中 n > 1，返回输出数组 output ，其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。示例输入: [1,2,3,4]输出: [24,12,8,6]思路正着乘一遍，倒着乘一遍。代码class Solution {public: vector<int> pro...
2020-04-28 20:58:41
101
原创 647. 回文子串
题目给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被计为是不同的子串。示例1输入: "abc"输出: 3解释: 三个回文子串: "a", "b", "c".示例2输入: "aaa"输出: 6说明: 6个回文子串: "a", "a", "a", "aa", "aa", "aaa".注意输入的字符...
2020-04-28 20:44:51
108
原创 621. 任务调度器
题目给定一个用字符数组表示的 CPU 需要执行的任务列表。其中包含使用大写的 A - Z 字母表示的26 种不同种类的任务。任务可以以任意顺序执行，并且每个任务都可以在 1 个单位时间内执行完。CPU 在任何一个单位时间内都可以执行一个任务，或者在待命状态。然而，两个相同种类的任务之间必须有长度为 n 的冷却时间，因此至少有连续 n 个单位时间内 CPU 在执行不同的任务，或者在待命状态。你...
2020-04-28 17:55:56
102
原创 617. 合并二叉树
题目给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。示例1输入: Tree 1 Tree 2 1 ...
2020-04-28 10:19:44
146
原创 581. 最短无序连续子数组
题目给定一个整数数组，你需要寻找一个连续的子数组，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。你找到的子数组应是最短的，请输出它的长度。示例1输入: [2, 6, 4, 8, 10, 9, 15]输出: 5解释: 你只需要对 [6, 4, 8, 10, 9] 进行升序排序，那么整个表都会变为升序排序。说明输入的数组长度范围在 [1, 10,000]。输入的数组...
2020-04-28 09:55:13
100
原创 560. 和为K的子数组
题目给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。示例1输入:nums = [1,1,1], k = 2输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。说明数组的长度为 [1, 20,000]。数组中元素的范围是 [-1000, 1000] ，且整数 k 的范围是 [-1e7, 1e7]。通过次数25,231提交次数）思路一...
2020-04-27 21:19:44
124
原创 543. 二叉树的直径
题目给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。示例给定二叉树 1 / \ 2 3 / \ 4 5 返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。思路计算每个节点的最大直径...
2020-04-26 23:51:32
107
原创 538. 把二叉搜索树转换为累加树
题目给定一个二叉搜索树（Binary Search Tree），把它转换成为累加树（Greater Tree)，使得每个节点的值是原来的节点值加上所有大于它的节点值之和。例如输入: 原始二叉搜索树: 5 / \ 2 13输出: 转换为累加树: 18 / ...
2020-04-26 22:50:01
108
原创 494. 目标和
题目给定一个非负整数数组，a1, a2, …, an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。返回可以使最终数组和为目标数 S 的所有添加符号的方法数。示例输入: nums: [1, 1, 1, 1, 1], S: 3输出: 5解释: -1+1+1+1+1 = 3+1-1+1+1+1 = 3+1...
2020-04-26 22:29:45
141
原创 461. 汉明距离
题目两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。给出两个整数 x 和 y，计算它们之间的汉明距离。注意都是大于0的数。思路两个数直接异或，看二进制中1的个数。代码class Solution {public: int hammingDistance(int x, int y) { int res = 0; int...
2020-04-25 10:37:42
275
原创 448. 找到所有数组中消失的数字
题目给定一个范围在 1 ≤ a[i] ≤ n ( n = 数组大小 ) 的 整型数组，数组中的元素一些出现了两次，另一些只出现一次。找到所有在 [1, n] 范围之间没有出现在数组中的数字。您能在不使用额外空间且时间复杂度为O(n)的情况下完成这个任务吗? 你可以假定返回的数组不算在额外空间内。示例输入:[4,3,2,7,8,2,3,1]输出:[5,6]思路因为数组大小...
2020-04-25 10:30:00
139
原创 438. 找到字符串中所有字母异位词
题目给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。字符串只包含小写英文字母，并且字符串 s 和 p 的长度都不超过 20100。说明字母异位词指字母相同，但排列不同的字符串。不考虑答案输出的顺序。示例1输入:s: "cbaebabacd" p: "abc"输出:[0, 6]解释:起始索引等于 0 的子串...
2020-04-25 09:55:37
161
原创 437. 路径总和 III
题目给定一个二叉树，它的每个结点都存放着一个整数值。找出路径和等于给定数值的路径总数。路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。二叉树不超过1000个节点，且节点数值范围是 [-1000000,1000000] 的整数。示例root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8 ...
2020-04-24 10:23:04
112
原创 234. 回文链表
题目请判断一个链表是否为回文链表。示例1输入: 1->2输出: false示例2输入: 1->2->2->1输出: true进阶你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？思路遍历一遍链表，计算长度。找到链表中间位置，遍历到中间位置截断，遍历的过程中，将遍历过的节点反向。链表长度为奇数时，链表断开后，后半部分比前半部分多一...
2020-04-24 10:17:27
193
原创 226. 翻转二叉树
题目翻转一棵二叉树。示例输入： 4 / \ 2 7 / \ / \1 3 6 9输出： 4 / \ 7 2 / \ / \9 6 3 1思路递归每个节点交换左右子树代码/** * Definition for a binary tree node. * struct Tree...
2020-04-23 11:06:11
75
林轩田LearningFromData作业代码基石和技法
2019-04-16
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人