- 博客(222)
- 资源 (5)
- 收藏
- 关注
RSS订阅原创 leetcode 128 最长连续序列（hash）
128. 最长连续序列难度困难437给定一个未排序的整数数组，找出最长连续序列的长度。要求算法的时间复杂度为O(n)。示例:输入:[100, 4, 200, 1, 3, 2]输出: 4解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。解题思路：我们首先走一遍数列，打一个hash，知道有什么数后，我们就遍历数列，然后尝试从这个点左右延伸，延伸的长度范围内的数字我们下次都可以不用走，可以证明这样我们每个数字最多遍历2次。至于延伸的时候我们需要判断数字在不在数..
2020-06-23 09:41:01
228
原创 O(1)空间复杂度找到相交链表的交点
相交链表编写一个程序，找到两个单链表相交的起始节点。如下面的两个链表：在节点 c1 开始相交。解题思路：首先将一条链首尾连起来，这时候就变成了找环的入口点的问题。我们可以用快慢指针先判断有没有环，然后再用快慢指针的交点poi开始和链表头开始找，找到的交点即为环的入口点。/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; *..
2020-06-22 16:26:25
263
原创 剑指 Offer 56 - II. 数组中数字出现的次数 II(状态转移 位运算)
剑指 Offer 56 - II. 数组中数字出现的次数 II难度中等38在一个数组nums中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。示例 1：输入：nums = [3,4,3,3]输出：4示例 2：输入：nums = [9,1,7,9,7,9,7]输出：1解题思路：我们可以发现，最后的数字假如第i位是1（二进制表示），那么第i位肯定有3*x+1个1，那么我们就思考第i位能不能进行转台转移。最终转...
2020-06-21 19:19:07
254
原创 打印数组中出现超过N/K的数字（复杂度O(n*k) 空间复杂度O(k)）
先看一到入门题，这里k=2剑指 Offer 39. 数组中出现次数超过一半的数字难度简单34数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。你可以假设数组是非空的，并且给定的数组总是存在多数元素。示例1:输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]输出: 2解题思路：对于一般的k=2，我们都知道需要有一个候选人，其实k>2我们只需要k-1个候选人即可。所以我们可以用k个桶做个hash，存放这k-1个候选人，桶容量够我们就...
2020-06-21 17:19:18
250
原创 剑指offer 数组中的逆序对（归并排序）
剑指 Offer 51. 数组中的逆序对难度困难176在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。示例 1:输入: [7,5,6,4]输出: 5解题思路：统计逆序对时候，答案的贡献以左半部分为基准。class Solution {public: vector<int> arrmv; int ans; void merge_sort(int l,int .
2020-06-20 16:12:01
137
原创 leetcode 42 接雨水（单调栈）
42. 接雨水难度困难1369给定n个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。感谢 Marcos贡献此图。示例:输入: [0,1,0,2,1,0,1,3,2,1,2,1]输出: 6解题思路：我们希望找到每根柱子从左往右所做的贡献，很显然，当我们在第i根柱子向右拓展找到第1根比第i根...
2020-06-20 11:38:38
163
原创 数字序列中某一位的数字（找规律）
面试题44. 数字序列中某一位的数字难度中等32数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中，第5位（从下标0开始计数）是5，第13位是1，第19位是4，等等。请写一个函数，求任意第n位对应的数字。示例 1：输入：n = 3输出：3示例 2：输入：n = 11输出：0限制：0 <= n <2^31解题思路：我们首先需要定位到这个数字属于哪一个大区间[1,9], [10,99],[1...
2020-06-19 10:09:31
404
原创 剑指offer面试题38. 字符串的排列（回溯）
面试题38. 字符串的排列难度中等48输入一个字符串，打印出该字符串中字符的所有排列。你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。示例:输入：s = "abc"输出：["abc","acb","bac","bca","cab","cba"]限制：1 <= s 的长度 <= 8解题思路：假如这里全是不同的字母，我们可以用简单的打标记回溯的方法来解决，但是这里会有重复的字母，这就需要我们先对字符串进行排序，本次回溯选择的时候 ...
2020-06-17 21:34:11
183
原创 表示数值的字符串（状态转移）
面试题20. 表示数值的字符串难度中等19请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串"+100"、"5e2"、"-123"、"3.1416"、"0123"都表示数值，但"12e"、"1a3.14"、"1.2.3"、"+-5"、"-1E-16"及"12e+5.4"都不是。注意：本题与主站 65 题相同：https://leetcode-cn.com/problems/valid-number/状态转移在dp中用的比较多，不过dp里面的状态没有像这题一样这么多.
2020-06-13 17:21:14
231
原创 拼多多 2020校园招聘 二维表第k大数（二分）
在一块长为n，宽为m的场地上，有n✖️m个1✖️1的单元格。每个单元格上的数字就是按照从1到n和1到m中的数的乘积。具体如下n = 3, m = 31 2 32 4 63 6 9给出一个查询的值k，求出按照这个方式列举的的数中第k大的值v。例如上面的例子里，从大到小为(9, 6, 6, 4, 3, 3, 2, 2, 1)k = 1, v = 9k = 2, v = 6k = 3, v = 6...k = 8, v = 2...
2020-06-09 19:22:10
988
原创 拼多多 2020校园招聘 骰子期望（古典概型，互斥）
扔n个骰子，第i个骰子有可能投掷出Xi种等概率的不同的结果，数字从1到Xi。所有骰子的结果的最大值将作为最终结果。求最终结果的期望。解题思路：这里我们需要用古典概型计算每一个取值的概率，然后再算期望。我们知道，总共的可能性是：...
2020-06-09 17:37:14
1096
原创 拼多多 2020校招 多多的电子字典（字典树前缀搜索，DP）
多多鸡打算造一本自己的电子字典，里面的所有单词都只由a和b组成。每个单词的组成里a的数量不能超过N个且b的数量不能超过M个。多多鸡的幸运数字是K，它打算把所有满足条件的单词里的字典序第K小的单词找出来，作为字典的封面。解题思路：首先，答案最终的输出为上面这棵字典树的先序输出第k次。当然这棵树的a.b数量不能超过题目给的a,b数量。我们在先序输出的时候可以判断它的左子树的节点数是否小于k，是的话，我们左子树就可以不访问了。为此我们需要计算一个量dp[n][m][sta]；当sta == 0时，
2020-06-09 17:27:31
2105
原创 拼多多 2020校招 多多的排列函数（找规律 构造）
数列 {An}为N的一种排列。例如N=3，可能的排列共6种： 1 2 3 4 5 6 1, 2, 3 1, 3, 2 2, 1, 3 2, 3, 1 3, 1, 2 3, 2, 1 定义函数F:其中|X|表示X的绝对值。现在多多鸡想知道，在所有可能的数列 {An} 中，F(N)的最小值和最大值分别是多少。解题思路：我们发现，只要把连续的4个数倒着放...
2020-06-09 17:15:22
1395
8
原创 leetcode 437路径总和（前缀和，hash，复杂度O(n)做法）
437. 路径总和 III难度简单424给定一个二叉树，它的每个结点都存放着一个整数值。找出路径和等于给定数值的路径总数。路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。二叉树不超过1000个节点，且节点数值范围是 [-1000000,1000000] 的整数。示例：root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8 10 / \ 5 -3
2020-06-06 20:24:55
852
原创 leetcode 338. 比特位计数（dp）
338. 比特位计数难度中等318给定一个非负整数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++或任何其他语...
2020-06-05 11:51:23
117
原创 leetcode 312 戳气球（区间dp）
312. 戳气球难度困难297有n个气球，编号为0到n-1，每个气球上都标有一个数字，这些数字存在数组nums中。现在要求你戳破所有的气球。每当你戳破一个气球i时，你可以获得nums[left] * nums[i] * nums[right]个硬币。这里的left和right代表和i相邻的两个气球的序号。注意当你戳破了气球i后，气球left和气球right就变成了相邻的气球。求所能获得硬币的最大数量。说明:你可以假设nums[-1] =...
2020-06-04 22:45:20
222
原创 leetcode 309. 最佳买卖股票时机含冷冻期（DP）
给定一个整数数组，其中第i个元素代表了第i天的股票价格 。设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。示例:输入: [1,2,3,0,2]输出: 3解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]解题思路：假设DP状态为dp[n][sta]表示走到第n天 sta==1 表...
2020-06-03 17:50:14
161
原创 leetcode 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) 。数组中只有一个重复的数字，但它可能不止重复出现一次。解题思路：我们建立一个数组cnt[i]，表示数组中小...
2020-06-03 11:02:07
157
原创 leetcode 283. 移动零（思维）
题目大意：给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。示例:输入: [0,1,0,3,12]输出: [1,3,12,0,0]说明:必须在原数组上操作，不能拷贝额外的数组。尽量减少操作次数。解题思路：我们需要维护一个变量是 在我们遍历的过程中出现的第一个0的位置lsz，然后每次交换lsz和当前遍历的元素，假如当前遍历的元素不为0.class Solution {public: void moveZeroes(vect
2020-06-01 21:42:16
127
原创 leetcode 238. 除自身以外数组的乘积（前缀乘积，思维）
题目大意：给你一个长度为n的整数数组nums，其中n > 1，返回输出数组output，其中 output[i]等于nums中除nums[i]之外其余各元素的乘积。示例:输入: [1,2,3,4]输出: [24,12,8,6]提示：题目数据保证数组之中任意元素的全部前缀元素和后缀（甚至是整个数组）的乘积都在 32 位整数范围内。说明: 请不要使用除法，且在O(n) 时间复杂度内完成此题。进阶：你可以在常数空间复杂度内完成这个题目吗？（ 出于对空间...
2020-06-01 16:24:28
176
原创 leetcode 146. LRU缓存机制（双向链表 + hash）
题目大意：运用你所掌握的数据结构，设计和实现一个LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。获取数据 get(key) - 如果关键字 (key) 存在于缓存中，则获取关键字的值（总是正数），否则返回 -1。写入数据 put(key, value) - 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字/值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。进阶...
2020-05-30 18:54:49
151
原创 leetcode 155. 最小栈(辅助栈)
题目大意：设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。push(x) —— 将元素 x 推入栈中。pop()—— 删除栈顶的元素。top()—— 获取栈顶元素。getMin() —— 检索栈中的最小元素。解题思路：一个栈sta1是用来模拟栈操作的。另一个 栈sta2用来返回最小值，每次push的值比sta2.top()要下就push进去否则push sta2.top()，这样的好处是我们的sta2维护了每个最值的适用域。class M..
2020-05-29 15:19:56
210
原创 leetcode 139. 单词拆分(BFS 或者 DP)
题目大意：给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，判定s 是否可以被空格拆分为一个或多个在字典中出现的单词。说明：拆分时可以重复使用字典中的单词。你可以假设字典中没有重复的单词。示例 1：输入: s = "leetcode", wordDict = ["leet", "code"]输出: true解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。示例 2：输入: s = "applepenapple",.
2020-05-27 09:53:08
251
原创 原地合并两个排序数组 O（1）空间复杂度，O(n)时间复杂度
问题：给你两个从小到大的数组a，b。在不申请额外空间下，往a填充a和b合并后的排序数组（假设a的空间是足够的）。第一种方法：很直觉的思路是，我们采取和归并排序时同样的策略，每次拿出最小的元素放进去即可。但是由于每次渴望拿最小，每填充一个元素后，需要重新维护有个冒泡的过程。第二种方法：每次拿a,b最大的元素，好处是省略了维护冒泡的过程，复杂度降低了。#include <bits/stdc++.h>using namespace std;//复杂度O(m*n)//需要
2020-05-26 10:46:01
1347
2
原创 leetcode 128. 最长连续序列 （hash，暴力）
题目大意：给定一个未排序的整数数组，找出最长连续序列的长度。要求算法的时间复杂度为O(n)。解题思路：我们每次枚举数字的第一个，然后往后数有多少个。可以证明每个数字只会被枚举一次。注意，中间用hash。class Solution {public: unordered_set<int> ms; int longestConsecutive(vector<int>& nums) { int ans = 0; .
2020-05-25 19:45:09
157
原创 leetcode 买卖股票的最佳时机 IV （DP）
题目大意：给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。注意:你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。解题思路：首先，我们列出简单的DP的方法：假设dp[n][k]代表第n天还有k次交易额可以用。那么状态转移为：dp[n][k] = dp[n-1][k] //代表我们不用这次交易名额if(k){ //代表我们使用这次的交易名额for (i = 1；i<...
2020-05-25 17:25:04
140
原创 剑指offer 二叉搜索树的第k个结点（二叉搜索树的中序遍历）
题目描述给定一棵二叉搜索树，请找出其中的第k小的结点。例如， （5，3，7，2，4，6，8） 中，按结点数值大小顺序第三小结点的值为4。解题思路：我们知道二叉搜索树的中序遍历就是排序好的数列。所以我们只需中序遍历到第k个，我们就认为得到答案了。/*struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : ..
2020-05-23 19:09:25
102
原创 剑指offer 数据流中的中位数（思维，堆）
题目描述如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。解题思路：假设我们已经有数字 1 2 3 4 5 6 7 8，那么我们可以把前半部分的4个数字做一个大堆big，后4个数字做一个小堆small。然后(big.top()+small.top())/2即为答案。这
2020-05-23 18:45:16
148
原创 剑指offer 序列化二叉树
题目描述请实现两个函数，分别用来序列化和反序列化二叉树二叉树的序列化是指：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树遍历方式来进行修改，序列化的结果是一个字符串，序列化时通过 某种符号表示空节点（#），以 ！ 表示一个结点值的结束（value!）。二叉树的反序列化是指：根据某种遍历顺序得到的序列化字符串结果str，重构二叉树。例如，我们可以把一个只有根节点为1的二叉树序列化为"1,..
2020-05-23 16:06:57
103
原创 剑指offer 对称的二叉树（思维）
题目描述请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。解题思路：正规的解法是传入两个节点，然后判断它们是不是对称的。因为按照对称二叉树的定义，就是需要一层一层判断是否是对称的。/*struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(
2020-05-23 14:23:24
106
原创 codeforces 1354D - Multiset (线段树或者2分)
题目大意：已知一个数列an,我们每次可以添加一个数k，或者把第k大的数字去掉。问我们经过k次操作后，数列中任意1个剩余的数字。n,q<=1e6解题思路：首先最简单的思路是线段树。线段树我们可以在每一个叶子节点用数字表示这个区间有多少个数字比如an：1 1 1我们的区间[1:1]就是3。然后做一个区间求和树即可。单点修改就在对应位置加1，去掉数字的话，我们就询问一下子节点中的左右节点，若左节点的和大于我们需要取出的第k个数，我们就往左走，否则k-=left_tree[root]（表示我们
2020-05-22 20:06:39
166
原创 剑指offer 字符流中第一个不重复的字符（思维，队列）
题目描述请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符"go"时，第一个只出现一次的字符是"g"。当从该字符流中读出前六个字符“google"时，第一个只出现一次的字符是"l"。解题思路：容易想到用队列来存储返回字符，但是一旦字符出现2次，我们总不能又把队列重新扔出来再扔回去（其实可以，复杂度同样是常数），这里我们可以用一个小技巧，每次检查队列的首个元素时，我们可以检查它的重复出现次数，若出现多于1次，我们就pop队列。class Solution
2020-05-20 19:31:29
145
原创 剑指offer 正则表达式匹配 （思维，动态规划）
题目描述请实现一个函数用来匹配包括'.'和'*'的正则表达式。模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（包含0次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但是与"aa.a"和"ab*a"均不匹配解题思路：首先，我们必须发现一些事实。在从左往右匹配中只可能出现这两种情况。我们假设str1为字符串，str2为模式串。pos1为str1开始匹配的位置，pos2为str2开始匹配的位置。（1
2020-05-20 18:37:24
228
原创 剑指offer 数组中只出现一次的数字（位运算）
题目描述一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。解题思路：无脑map可以做，这里不讨论。另外，我们可以根据异或的性质，相同的数字异或为0，所以我们将所有的数字异或得到一个结果，找到结果中的二进制表示位中的第一个1的位置pos（其实任意位置的1都可以，注意肯定有1，不可能为0），然后把数字分为两组，第一组是pos位置为1的，以及剩下的。然后第一组内的数字进行异或得到答案1，第二组数字内的数字异或得到答案2.class Solution
2020-05-19 17:58:53
131
原创 非递归方式实现二叉树的中序遍历
这里的关键点是维护一个栈，栈中的元素是仍未访问右节点的节点，每次我们不断地往左走的时候，就不断地压栈就可以了，模拟dfs的过程。/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} *
2020-05-18 09:24:35
273
原创 leetcode 最小覆盖子串（双指针）
76. 最小覆盖子串给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字符的最小子串。示例：输入: S = "ADOBECODEBANC", T = "ABC"输出: "BANC"说明：如果 S 中不存这样的子串，则返回空字符串""。 如果 S 中存在这样的子串，我们保证它是唯一的答案解题思路：这题可以使用双指针解决，有点类似于找最长公共串。我们可以用左指针lf，右指针rg。我们不断拓展右指针，直到[lf,rg]的串满足要求，我们认为可以用lf指针.
2020-05-10 10:40:23
223
原创 无法连接到本地daytime服务 connect到daytime时返回-1 处理
太长不看版：检查是否有安装xinetd，具体地怎么检查可以用 locate xinetd命令。若没有安装使用 apt-get install xinetd. 安装完毕后，打开路径 /etc/xinetd.d/ 接着打开daytime文件，把里面的 disable = yes 改为 disable = no. 注意总共有2个。之后，我们重启服务，用命令systemctl restart xinetd.最后我们可以检查一下用命令 telnet 127.0.0.1 13.若返回正确时间，则证明本次
2020-05-08 17:45:43
347
2
原创 剑指offer 整数中1出现的次数（思维）
题目大意：在[1,n]中，统计 所有 数位上包含的1数字，总共1的个数。比如 [1,11] 数位包含1的数字有： 1 10 11 总共有1 + 1 + 2 = 4 个1.解题思路：这题我们需要逐个数字位置上思考，个位对答案的贡献，十位对答案的贡献。。。这里有一个key，我们这样最后答案的组成。比如数字 n = 2134：那么从个位开始看：所有的数字的组成可以看为 [0,2130] ...
2020-05-07 11:53:01
152
原创 剑指offer 字符串的排列（思维）
题目大意：有n个字母，现在让我们从从字典序由小到大输出。n<=9.解题思路：输出全排列那么复杂度O(n!)肯定逃不掉，这里提供一个O(n * n!)输出字典序从小到大的方法。那么已知一个排列，怎么输出比它大的字典序的排列呢？首先，我们从右到左扫，维护一个后缀最大值，假如当前元素小于后缀最大值，那么我们认为这个元素是可以被后面的较大的元素替换，从而找到字典序更大的。（为...
2020-05-05 21:18:05
103
原创 最长公共子串（包含连续子串和非连续子串）
题目大意：有两个序列，现在我们找到公共的子序列，使得这个子序列最长。首先我们看一下假如这个序列是非连续的序列。https://www.nowcoder.com/questionTerminal/c996bbb77dd447d681ec6907ccfb488a非连续子序列解题思路：首先定义dp状态dp[i][j]，表示我们可以从a序列长度为i的前缀和b序列中长度为j的前缀得到的...
2020-05-05 14:07:46
385
正交匹配追踪(OMP)的matlab程序
2018-11-01
db小波去噪后信噪比输出matlab程序
2018-11-01
图解机器学习
2018-05-08
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人