- 博客(84)
- 资源 (1)
- 收藏
- 关注
RSS订阅原创 Bellman-Ford、Dijkstra、Floyd算法
文章目录Bellman-Ford算法解决的问题思路leetcode例题Dijkstra算法解决的问题思路leetcode例题Floyd算法解决的问题思路leetcode例题Bellman-Ford算法Bellman-Ford用于找出单源最短路径，即从源节点到图中每个节点的最短路径，支持边权重为负的情况。算法利用了动态规划的思想，实现简单，但时间复杂度为O(VE)O(VE)O(VE)，非常高。解决的问题从A出发是否可以到达各个节点从A出发到达各个节点的最短路径图中是否存在负环路（权重之和为负数
2021-03-15 15:09:11
1128
原创 [leetcode题解] 第995题Minimum Number of K Consecutive Bit Flips
https://leetcode-cn.com/problems/minimum-number-of-k-consecutive-bit-flips/文章目录分析差分数组解法代码分析不难想到这样一种解法:依次遍历数组A，如果A[i] == 0，第i个位置就需要翻转。此时若i + K > n，则无法实现翻转，返回-1；否则手动修改数组A[i: i+K-1]，再遍历下一个位置。在这个过程中直接统计出总的翻转次数即为答案。这个解法虽然直观，但是时间复杂度为O(nK)O(nK)O(nK)，不是一个好的
2021-02-18 23:38:09
252
1
原创 [leetcode题解] 第480题Sliding Window Median
https://leetcode-cn.com/problems/sliding-window-median/文章目录分析分析
2021-02-03 17:53:13
283
原创 [leetcode题解] 第1202题Smallest String With Swaps
https://leetcode-cn.com/problems/smallest-string-with-swaps/文章目录分析解法并查集排序思路一排序思路二排序思路三分析需要把这道题看成图论的题目才好做：将字符串中的索引视为图的节点，一个pair对意味着两个节点之间存在一条无向边。那么答案就可以这样来得到：对无向图中的每个连通分量所代表的字符串分别进行排序，再把字符按照索引填入原位置。这是因为交换具有传递性，即a与b可交换，b与c可交换，那么a一定可与c交换（交换次数不受限制）。因此在连通分量
2021-01-13 16:43:19
172
原创 二维离散傅里叶变换的权值矩阵计算
例题计算以下图像的离散傅里叶变换f=[1441244224421441]f=\begin{bmatrix}1&4&4&1\\2&4&4&2\\2&4&4&2\\1&4&4&1\end{bmatrix}f=⎣⎢⎢⎡1221444444441221⎦⎥⎥⎤计算方式当然不是通过原始公式硬算，而是构造权值矩阵来计算。考虑二维DFT的分解：F(u,v)=∑x=0M−1∑y=0N−1f(x,y)e−
2021-01-05 21:42:49
4329
1
原创 局部搜索解千万级别N皇后问题
作业10题目局部搜索解n皇后，并测试n的极限实验v0v0版本我实现了最基本的局部搜索算法，该版本解n=1000n=1000n=1000需要超过777分钟，n=10000n=10000n=10000时间太长，超过极限。 状态的表示首先，使用哪种数据结构表示n皇后问题的一个状态是很重要的，直接影响到算法的效率。我使用一个一维数组来表示状态，i, board[i]表示一个皇后的行、列位置。初始时要随机生成一个状态，此时就可以解决掉所有行和列上的冲突，即保证每一行、每
2021-01-01 15:02:54
1938
5
原创 ubuntu18.04修改MAC地址以及分辨率
实验室的电脑是通过固定MAC地址和IP地址来上网的，而我刚安装的ubuntu18.04要修改MAC地址还比较麻烦，记录一下这些问题。修改MAC地址安装ipconfig网上别人的教程都是互相抄来抄去，基本都是sudo ipconfig eno1 hw ether xxx那一套，如这篇博客。但首先，没网的电脑连ifconfig命令都没有，只能切换系统通过链接去下载net-tools工具，再拷贝到ubuntu下安装。此外，我用上述操作时，并不能实现每次开机都自动运行脚本，而且，就算是临时的修改MAC地址，
2020-11-16 17:24:35
415
原创 [leetcode题解] 第1648题Sell Diminishing Valued Colored Balls
https://leetcode-cn.com/problems/sell-diminishing-valued-colored-balls/文章目录分析解法一代码：解法二代码分析很容易找到这道题的贪心策略：每次卖出价值最大（数目最多）的那种球。我们可以使用最大堆来辅助获取最大的inventory[i]，把它加到ans后再把inventory[i] - 1放回堆中，同时orders--。这种思路很简单，但效率太低了，时间复杂度为O(orders⋅logn)O(orders\cdot logn)O(o
2020-11-09 11:22:56
625
原创 [总结] matlab转numpy代码的坑
最近在忙着把一个用matlab写的图像处理转numpy，由于自己此前对matlab并不熟悉，因此遇到了不少坑，在此总结一下。文章目录一、下标二、行、列顺序三、稀疏矩阵四、获取滤波核五、卷积一、下标matlab中下标从1开始，因此转成numpy时下标需要减一// matlabdx = diff(s,1,2);# numpydx = np.diff(img, 1, 1)二、行、列顺序这个很重要，matlab中列优先的，而numpy是行优先的，所以在用到reshape这种操作时就要非常注意。
2020-11-05 10:25:45
553
原创 [leetcode题解] 剑指offer20：表示数值的字符串
https://leetcode-cn.com/problems/biao-shi-shu-zhi-de-zi-fu-chuan-lcof/submissions/文章目录分析解法代码分析这道题主要考察思维全面性和编程能力，如果不能归纳出所有的案例，编码时就要处理各种细节，难以写出高质量的代码。举几个例子：3.2e+9、3.e9、.e8、+.3e-2这些都是有效的数值。乍一看很难理解，但只要我们明白数值由整数部分、小数部分、指数部分组成就容易理解了。去除字符串首尾的空格后，表示数值的字符串模式为
2020-10-17 10:52:54
117
原创 leetcode题解：剑指offer14: 剪绳子
https://leetcode-cn.com/problems/jian-sheng-zi-lcof/文章目录解法一代码解法二解法一这道题属于动态规划的经典面试题，考虑dp[i]表示对i进行划分得到的最大乘积，注意：dp[i]不一定大于i。因此将n划分为i和n-i后，我们要判断是否需要继续对i和n-i进行划分。注意：只需要在[1, n/2]的范围内寻找i，这样可以节省时间。代码class Solution { public int integerBreak(int n) {
2020-10-11 21:51:49
172
原创 卡特兰数通项公式详细推导过程
设法求解下面这个递归式或给出其最低上界的阶，设P(1)=1P(1)=1P(1)=1P(n)=∑k=1n−1P(k)P(n−k)\large{P(n)=\sum^{n-1}_{k=1}P(k)P(n-k)}P(n)=k=1∑n−1P(k)P(n−k)易知P(n)P(n)P(n)就是卡特兰数，下面用生成函数法求解出其通项公式。设生成函数为：g(x)=h(1)x+h(2)x2+...+h(k)xk+...\large{g(x)=h(1)x+h(2)x^2+...+h(k)x^k+...}g(x
2020-09-22 20:43:14
6418
2
原创 pytorch使用tensor作为tensor的索引
在使用pytorch时，我们经常会看到tensor1[tensor2]这样的代码，而不同的tensor2会导致不同的索引方式，本文详细介绍使用tensor作为索引的原理。首先构造tensor1：>>> a = torch.randn(10, 5)>>> atensor([[-0.9434, -2.8668, -0.4331, -1.6842, -0.1823], [-1.4545, -1.0065, 0.3228, 0.7457, 0.622
2020-09-12 22:15:28
4268
原创 pytorch中的gather和scatter函数
最近看代码时遇到了两个函数，查阅pytorch后一时半会儿也没弄懂，现在写篇笔记来加深一下印象。gathertorch.gather(input, dim, index, out=None, sparse_grad=False) → Tensor沿着给定的维度dim，将输入input指定位置的值聚合起来，指定位置由index决定。index和input必须有相同数量的维度，且满足1 <= index[dim] <= input[dim]、index[other_dims] == inpu
2020-09-12 16:24:40
703
原创 详解leetcode石头合并问题
https://leetcode-cn.com/problems/minimum-cost-to-merge-stones/文章目录分析区间动态规划三部曲分析这道题是一道经典的区间dp问题，旨在通过动态规划去求一个区间的最优解，通过将大区间划分为很多个小区间，再由小区间的解来组合出大区间的解，这体现了分支的思想。区间动态规划三部曲定义状态：dp[i, j]为区间[i, j]的最优解定义状态转移方程：最常见的写法为：dp[i,j] = max/min{dp[i,j], dp[i, k] + dp
2020-08-30 17:00:23
875
原创 leetcode题解：第301题Remove Invalid Parentheses
https://leetcode-cn.com/problems/remove-invalid-parentheses/文章目录解法一、BFS代码解法二、回溯代码解法三、有限制的回溯代码解法一、BFS这题要求所有的解，所以我们应当想到用搜索来解决，BFS的思想会比较直观：由题目要求易知：所有的解都是由原始字符串删除了相同数量的括号得到的对于删除的括号数量i，生成对应的所有的字符串，它们属于第i个level对于每个level，判断其中的字符串是否有解：若有，则所有的解都来自于这个level；否则
2020-08-26 09:55:23
304
原创 leetcode题解：第399题Evaluate Division
https://leetcode-cn.com/problems/evaluate-division/分析这道题的目的很明确，逻辑也容易理解，人可以很容易地计算出这种方程式的结果，但怎么把这种方程式在程序中表示是一个难题。换言之，正确地表示方程式，就能把这个看似难处理的问题转换成容易解决的问题。解法一、图遍历如果给出提示，把这题与图联系起来，能否快速找到解决办法呢？我们可以很自然地想到，可以用带权图来表示输入的所有方程式：a / b = value表示两条边：a->b，权重为value和b-
2020-08-22 23:14:48
215
原创 堆排序详解
上文提到的leetcode第215题除了快速排序的二分partition解法，还可以用堆排序来解决，小小一道medium题居然汇集了快排和堆排这两位卧龙凤雏，实属难得。文章目录数据结构-堆完全二叉树堆堆排序思想构造大根堆代码数据结构-堆完全二叉树首先，堆是一棵完全二叉树，因此其具备完全二叉树的全部特点：除了最后一层外，其余层的节点数都达到最大值，而最后一层的节点都集中在左边。节点的编号与其对应的满二叉树中节点编号相同若最后一个非叶子节点的编号为i，则编号0~i的节点都是非叶子节点，编号i+1
2020-08-12 19:59:25
594
原创 Partition算法详解
partition算法有着非常重要的应用，这个算法的思想虽然简单，但具体实现的细节却比较多，今天我重点复习了这个算法，本文记录我对这个算法的理解。文章目录Partition算法解析二分Partition三分Partition二分Partition应用时间复杂度代码三分Partition应用代码Partition算法解析二分Partition快速排序作为非常著名的排序算法，其思想却很简单：每次从数组中选一个数作为pivot，然后将数组划分为2部分，小于等于pivot数的在其左边，大于等于pivot的数
2020-08-11 17:05:54
3553
原创 leetcode题解：第142题Linked List Cycle II
https://leetcode-cn.com/problems/linked-list-cycle-ii/文章目录分析解法、双指针代码复杂度分析分析这道题在第141题环形链表的基础上，不仅要求判断链表是否有环，还要求在有环的情况下给出入环的节点。如果用哈希表的话，自然与第141题解法相同，但那并不是这种题目的本意。单纯用双指针，只能判断是否有环，但快慢指针的相遇点并不一定在入环处，需要巧妙地改进双指针的解法来完成本题。解法、双指针链表无环时自不必说，当链表有环时，我们分两个阶段来解决这个问题：
2020-08-07 23:08:49
144
原创 leetcode题解：第139题Word Break
https://leetcode-cn.com/problems/word-break/文章目录解法一、回溯代码解法二、动态规划代码复杂度分析解法一、回溯依照惯例，没有好的思路的时候，就先想想暴力解法怎么做。暴力解法无非是逐个单词地拆分字符串，每次选的单词可以重复。要实现暴力解法的话，肯定就是用回溯，因为回溯算法“撤销选择”的特点，保证了每次都能考虑到所有的单词。简而言之，对于字符串s和单词word，word长度为n，当word与s[:n]相同时，就可以把word选来进行一次拆分，紧接着继续判断s[
2020-08-07 20:40:58
340
原创 leetcode题解：第105题Construct Binary Tree from Preorder and Inorder Traversal
https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/文章目录解法一、递归代码复杂度分析解法二、迭代解法一、递归前序遍历的序列组成形式为：根, {左子树前序结果}, {右子树前序结果}中序遍历的序列组成形式为：{左子树中序结果}, 根, {右子树中序结果}把上面这两行写出来，递归解法就很容易想到了。很明显，我们需要知道左子树的节点个数，才好获取到左子树的前序结果。由于树
2020-08-05 22:48:02
177
原创 leetcode题解：第79题Minimum Window Substring
https://leetcode-cn.com/problems/minimum-window-substring/文章目录解法代码复杂度分析解法题意很容易理解，需要注意输入的T不会是空串，T中的字符有可能重复。对于子串问题，常用滑动窗口算法来解决滑动窗口算法的框架如下：int left = right = 0while right < s.size() { window.add(s[right]) while (window meed shrink) window.remove(s[
2020-08-02 17:28:37
148
原创 leetcode题解：第39题Combination Sum
https://leetcode-cn.com/problems/combination-sum/submissions/文章目录分析解法代码分析这道题也是典型的回溯算法代表题，题目要求找到所有的解，每一个解都是由候选数组中的元素组成的，因此我们可以利用回溯算法，一次将一个元素加入到组合中，再判断组合是否是一个解。在回溯过程中还需要剪枝，剪掉不可能找到解的分支和会产生重复解的分支。解法最容易想到的方法，把候选数组中的元素一个个加入到组合中，然后计算组合中所有元素之和：如果大于目标数，则这个搜索分支
2020-07-28 12:49:41
157
原创 C++容器作为引用传参时导致的迭代器失效问题
文章目录容器迭代器失效的几种情况总结一、序列型容器二、关联型容器三、链表型容器总结容器作为引用传参可能导致迭代器失效容器迭代器失效的几种情况总结一、序列型容器包括vector,deque,string等，其特点是元素存储在连续内存中，插入和删除会导致之后的元素移动，所以插入和删除都会导致插入/删除点及其之后的所有迭代器失效。在循环中删除元素的正确写法：for(auto it = nums.begin(); it != nums.end(); ) if (...) it = nums.erase(
2020-07-25 16:34:52
708
原创 leetcode题解：第22题Generate Parentheses
https://leetcode-cn.com/problems/generate-parentheses/submissions/文章目录解法一代码复杂度分析解法二代码复杂度分析解法三代码解法一采用暴力解法，即找出所有可能的组合，挑选出其中有效的作为答案。一共有n对括号，也即字符串长度为2n，每个位置2个选择，所以一共有22n2^{2n}22n个可能的组合。如何生成所有可能的组合？采用递归的深度优先搜索是最方便有效的方法。搜索的最大深度就是2n，此时判断组合 是否有效并添加到答案中。如何判
2020-07-22 21:02:00
173
原创 二叉树的前序遍历、中序遍历、后序遍历迭代实现
遍历树有DFS和BFS两种方法，而DFS又因为输出节点的先后顺序分为了3种，采用递归来实现前、中、后序遍历非常简单，本文记录一下这3种遍历的迭代实现。要点：树的前、中、后序遍历迭代实现要借助栈这个数据结构。以下面这棵树为例：前序遍历leetcode第144题：https://leetcode-cn.com/problems/binary-tree-preorder-traversal/前序遍历就是当访问到一个节点时，先输出该节点内容，再分别去访问其左右子节点。例子的遍历结果为：[1,4,2,3
2020-07-22 10:41:33
304
原创 leetcode题解：第15题3 Sum
https://leetcode-cn.com/problems/3sum/分析这道题与Two Sum很像，我们很容易想到利用Two Sum的程序来解答这个问题，对于a+b+c = 0，有-c = a+b，这相当于target设置为-c的Two Sum问题。区别在于，a和b的值不是唯一的，即这个Two Sum的答案不唯一。除了找到所有正确的a和b外，还要解决三元组重复的问题。解法一我们依然考虑在Two Sum的基础上解决这个问题。首先，Two Sum的核心代码是：for (int i = 0;
2020-07-20 15:37:43
117
原创 leetcode题解：第11题Container With Most Water
https://leetcode-cn.com/problems/container-with-most-water/分析这道题乍一看与接雨水那道题很像，但那题是求总共能接到的水量，这题则是要求两个边界组成的容器的最大容量。暴力解法是枚举所有的左右边界，计算其容器的容量，再取最大值，时间复杂度为O(n2)O(n^2)O(n2)，超时了。解法这道题要用双指针来解答， 如果给你双指针这个提示的话，你应该会容易想到每次移动更矮的那个边界会是正确的做法，但是怎么证明呢？对于所有的这些线，它们都有可能作为一
2020-07-19 11:46:22
147
原创 leetcode题解：第10题Regular Expression Matching
https://leetcode-cn.com/problems/regular-expression-matching/分析这道题的难点在于存在a*这样的组合，如何处理与这种组合匹配的字符数是很棘手的问题，例如：s = "aaa", p = "aa*"s = "baaa", p = "ba*"第一个例子中a*匹配2个字符，第二个例子中a*匹配3个字符。可以看出，匹配的字符数不仅与s有关，还与p中组合前面的字符有关（后面也有可能）。如果是.*这样的组合，会更加麻烦。我一开始的想法是用双指针分别
2020-07-18 17:27:45
148
原创 leetcode题解：第300题Longest Increasing Subsequence
https://leetcode-cn.com/problems/longest-increasing-subsequence/这道题是动态规划的典型例题，有O2O^2O2和O(nlogn)O(nlogn)O(nlogn)两种解法。解法一O(n2)O(n^2)O(n2)的解法比较容易想到，要找最长的上升子序列，我们维护一个dp[n]数组，用dp[i]来表示以第i个元素为结尾的最长上升子序列长度，例题中dp[0] = 1, dp[3] = 2。如何更新这个数组呢？按照定义，我们肯定要更新所有的dp[i
2020-07-17 11:01:50
186
原创 leetcode题解：第5题Longest Palindromic Substring
https://leetcode-cn.com/problems/longest-palindromic-substring/解法一采用动态规划的思路来优化暴力解法。暴力解法自然是找出所有的子串然后判断是否是回文串，子串可以用其开头start和结尾end两个变量来表示。找到所有子串这个过程是没法优化的，因此我们要思考如何优化判断回文串这个过程。对于dp[start][end]，必须满足end >= start（首尾不能颠倒）：易知start == end时dp[start][end] =
2020-07-16 15:26:20
137
1
原创 leetcode题解：第169题Majority Element
https://leetcode-cn.com/problems/majority-element/解法一最容易想到的解法，用哈希表存下每个元素出现的次数，当次数超过n/2时，找到答案，算法效率也高，复杂度均为O(n)O(n)O(n)。class Solution {public: int majorityElement(vector<int>& nums) { unordered_map<int, int> count; fo
2020-07-14 21:30:30
154
原创 leetcode题解：第236题Lowest Common Ancestor of a Binary Tree
https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/解法一本题意在为两个节点找到最近的共同祖先，我们需知两点来完成这个任务：除非另找存储结构，树只能从root开始从上往下遍历，一般采用递归完成如何判断一个节点是否是p或q的祖先要判断是否为祖先，我们可以利用递归的特性，当遇到p或q时，返回值为真，再一层层送上去，就找到了其祖先。本题自然也需利用递归完成，但要求返回的值是TreeNode*类型，不是bo
2020-07-14 21:10:06
172
原创 leetcode题解：第1题Two Sum
https://leetcode-cn.com/problems/two-sum/分析题目意思很明确，不考虑算法效率的话，这道题可以很容易用暴力解法做出来，两层循环获取两个整数，判断和是否等于目标值即可，时间复杂度为O(n2)O(n^2)O(n2)。解法为了得到更好的算法，我们转变思路，不是直接找两个整数然后判断它们的和，而是考虑对一个整数n，判断target-n是否在数组中，如果在，答案就是它们俩的下标。判断一个数是否存在于数组中的最好办法就是哈希表，所以我们要将数组转变为哈希表，key为数组元
2020-07-11 13:49:39
219
原创 win10自动修复失败 + ubuntu [Firmware Bug]
问题描述前两天在打游戏时电脑突然自动关机，重启好几次都是在windows启动界面后黑屏，连续3次强制关机重启后就出现了windows自动修复的画面，但很不幸，修复失败，而且也没有提示有什么文件缺失或者损坏，按照这位博主的方法试了之后出现了跟评论区一样的问题：出现代码0xc0000001，没有错误文件，且系统界面跟之前产生了变化，一些选项消失，没办法，只好重装系统了。不幸的是，在windows进不去之后我尝试进ubuntu去备份C盘里面的文件，但ubuntu系统也进不去了，出现的提示是 [firmware
2020-05-19 21:26:02
3266
原创 pytorch保存模型的坑
pytorch中保存模型相关的函数有3个：torch.save：利用python的pickle模块实现序列化并保存序列化后的objecttorch.load：利用pickle将保存的object反序列化torch.nn.Module.load_state_dict：通过反序列化得到的state_dict读取保存的训练参数有两种方法保存模型：1. torch.save(model, p...
2020-02-15 21:28:40
4820
4
原创 numpy数组索引遇到的问题
在使用numpy多维数组时我们常会需要获取数组中的元素，这一般有两种方法：import numpy as npa = np.random.randint(10, 20, size=[10, 20])print(a)print(a[2, 2])print(a[2][2])'''[[17 12 16 14 19 10 14 13 15 13 17 19 19 11 11 18 16 1...
2019-10-31 18:53:40
504
原创 Ubuntu远程服务器创建新用户并赋予权限
远程登陆服务器首先要有一个已获取sudo权限的用户，利用ssh命令来登陆服务器：ssh xxx@ipxxx为用户名，ip为服务器ip地址创建新用户sudo adduser username # username是你设置的用户名输入这个命令后会提示输入密码、确认密码，然后是设置个人信息，可以全部按enter设置为空。添加权限上面的步骤让我们可以通过新用户来登陆服务器，但在运行s...
2019-10-12 11:36:29
1263
原创 [线性代数]常用符号整理
x∈Rnx \in \Bbb R^nx∈Rn表示具有nnn个元素的列向量，行向量通常用列向量的转置来表示对于方阵A∈Rn×nA \in \Bbb R^{n\times n}A∈Rn×n,∣A∣|A|∣A∣或detA\det AdetA表示它的行列式I∈Rn×nI \in \Bbb R^{n\times n}I∈Rn×n表示单位矩阵，它是一个方阵对角矩阵通常表示为D=diag(d1,d2,...
2019-10-07 11:32:51
29564
1
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人