华科不平凡

分类

题解(135)

/ 注册

TA的专栏 135篇文章 8人订阅

刷遍天下无敌手

135篇文章 15888人学习

0篇文章 0人学习

全部文章（共135篇）

买卖股票的最佳时机ii 来自专栏

首先思考一个问题，假如让我们手动进行操作会怎么操作？比如[1, 4, 2, 1, 8, 7, 9, 2]，直观的感受是遇到递增序列即执行买入卖出，如： 1, 4递增，1买4卖 1, 8递增，1买8卖 7，9递增，7买9卖代码如下： // // Created by jt on 2020/9/...

单调栈

2020-09-24

1 855

词语序列ii 来自专栏

从hit到cog之间有许多路径，我们可以将其想像成一个图：两种方法： BFS记录每个单词所在层再DFS，176ms, 2924KB 构建图再回溯，156ms, 4580KB 方法一：BFS记录图中单词所在层再DFS 先通过BFS记录图里面单词所在的层，然后通过DFS找到所有的路径： BF...

DFS unordered_set unordered_map 深度优先搜索回溯图 BFS

2020-09-24

0 941

最长的连续元素序列长度来自专栏

采用哈希表存储每个元素，然后遍历整个数组，遍历的时候求当前元素所在连续序列的长度。如[3, 1, 2, 8, 9]，存到哈希表之后，我们遍历这个数组，首先遇到的是3，我们在哈希表中查找3之前的连续数，以及查找3之后的连续数，查完就从哈希表中删除（因为是连续的，所以删除不会影响最终结果），并且更新结...

unordered_set

2020-09-23

3 893

复制无向图来自专栏

首先，这是个图的问题，二话不说，咱先搬出BFS和DFS两大法宝。基本思路是：创建一个unordered_map，其中保存指向旧节点的指针到指向新节点的指针的映射，同时也用它来判断旧节点是否被遍历过。 BFS代码如下： // // Created by jt on 2020/9/23. // #in...

unordered_map 图

2020-09-23

0 667

拷贝有随机指针的链表来自专栏

细胞分裂法：增殖：遍历next指针，拷贝旧节点，并将新节点插入到旧节点之后复制：遍历next指针，如果某个节点的random不为空（旧节点），则下一个节点（新节点）的random指向该节点random指向节点的下一个节点分裂：遍历next指针，将两个链表分裂开来代码如下： // //...

链表

2020-09-23

7 827

判断链表中是否有环来自专栏

两步利用快慢指针判断是否存在环——如果快指针最后指向NULL，则不存在环，如果快慢指针相遇则存在环。代码如下： // // Created by jt on 2020/9/23. // class Solution { public: bool hasCycle(ListNode *hea...

快慢指针

2020-09-23

0 650

链表中环的入口节点来自专栏

两步走：利用快慢指针判断是否存在环——如果快指针最后指向NULL，则不存在环，否则存在环利用双指针判断入口节点参照下图，假设图中存在环且快慢指针在C处相遇，设|AB|=a, |BC|=b, |CB|=c，有2(a+b)=a+b+n(b+c)，推出a=n(b+c)-b，因此让两个指针分别从A...

快慢指针

2020-09-23

1 1012

矩阵中的路径来自专栏

回溯法： // // Created by jt on 2020/9/18. // #include <vector> using namespace std; class Solution { public: bool hasPath(char* matrix, int ro...

回溯

2020-09-18

0 531

连续子数组的最大和来自专栏

设dp[i]表示0..i以i结尾的连续子数组的最大序列和，那么有如下状态公式：当i=0时，dp[0] = arr[0] 当i>0时，dp[i] = max(dp[i], dp[i]+arr[i-1]) 代码如下： // // Created by jt on 2020/9/18. // ...

动态规划

2020-09-18

0 543

字符串的排列来自专栏

三种方法；基于库函数next_permutation(begin, end) 去重方法：先sort初始字符串再处理（本题初始字符串已经有序）基于回溯通过一个visited数组记录已经被选中的位置去重方法：通过set进行去重基于交换去重方法：通过set进行去重方法一的代码...

回溯库函数

2020-09-18

0 567