华科不平凡 - 个人主页动态 - 牛客网

发布(141) 评论刷题

2020-09-24 11:05

已编辑

华中科技大学 C++

买卖股票的最佳时机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/24. // #include <vector> using namespace std; class Solution { public: /** * * @param prices int整型vector * @return int整型 ...

刷遍天下无敌手

0 点赞评论收藏

分享

2020-09-24 10:34

已编辑

华中科技大学 C++

从hit到cog之间有许多路径，我们可以将其想像成一个图： 两种方法： BFS记录每个单词所在层再DFS，176ms, 2924KB 构建图再回溯，156ms, 4580KB 方法一：BFS记录图中单词所在层再DFS 先通过BFS记录图里面单词所在的层，然后通过DFS找到所有的路径： BFS过程中需要记录历史节点及当前层次，最终获取每一个单词对应的层级 DFS的终止条件是搜索到了结束单词 // // Created by jt on 2020/9/23. // #include <vector> #include <string> #include <...

刷遍天下无敌手

0 点赞评论收藏

分享

2020-09-23 18:08

已编辑

华中科技大学 C++

最长的连续元素序列长度

采用哈希表存储每个元素，然后遍历整个数组，遍历的时候求当前元素所在连续序列的长度。 如[3, 1, 2, 8, 9]，存到哈希表之后，我们遍历这个数组，首先遇到的是3，我们在哈希表中查找3之前的连续数，以及查找3之后的连续数，查完就从哈希表中删除（因为是连续的，所以删除不会影响最终结果），并且更新结果。 代码如下： // // Created by jt on 2020/9/23. // #include <vector> #include <unordered_set> using namespace std; class Solution { public: ...

刷遍天下无敌手

0 点赞评论收藏

分享

2020-09-23 17:45

华中科技大学 C++

复制无向图

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

刷遍天下无敌手

0 点赞评论收藏

分享

2020-09-23 16:16

华中科技大学 C++

拷贝有随机指针的链表

细胞分裂法： 增殖：遍历next指针，拷贝旧节点，并将新节点插入到旧节点之后 复制：遍历next指针，如果某个节点的random不为空（旧节点），则下一个节点（新节点）的random指向该节点random指向节点的下一个节点 分裂：遍历next指针，将两个链表分裂开来 代码如下： // // Created by jt on 2020/9/23. // class Solution { public: RandomListNode *copyRandomList(RandomListNode *head) { // "增殖" if (!head)...

刷遍天下无敌手

0 点赞评论收藏

分享

2020-09-23 15:47

华中科技大学 C++

判断链表中是否有环

两步利用快慢指针判断是否存在环——如果快指针最后指向NULL，则不存在环，如果快慢指针相遇则存在环。 代码如下： // // Created by jt on 2020/9/23. // class Solution { public: bool hasCycle(ListNode *head) { if(!head) return false; ListNode *fast = head, *slow = head; while(fast && fast->next) { fast = fa...

刷遍天下无敌手

0 点赞评论收藏

分享

2020-09-23 15:43

华中科技大学 C++

链表中环的入口节点

两步走： 利用快慢指针判断是否存在环——如果快指针最后指向NULL，则不存在环，否则存在环 利用双指针判断入口节点 参照下图，假设图中存在环且快慢指针在C处相遇，设|AB|=a, |BC|=b, |CB|=c，有2(a+b)=a+b+n(b+c)，推出a=n(b+c)-b，因此让两个指针分别从A和C以相同速度前进，两个指针再次相遇的位置即为环的入口节点。 代码如下： // // Created by jt on 2020/9/23. // class Solution { public: ListNode *detectCycle(ListNode *head) { ...

刷遍天下无敌手

0 点赞评论收藏

分享

2020-09-18 13:44

华中科技大学 C++

矩阵中的路径

回溯法： // // Created by jt on 2020/9/18. // #include <vector> using namespace std; class Solution { public: bool hasPath(char* matrix, int rows, int cols, char* str) { vector<vector<int> > visited(rows, vector<int>(cols, 0)); for (int i = 0; i < rows...

刷遍天下无敌手

0 点赞评论收藏

分享

2020-09-18 10:55

华中科技大学 C++

连续子数组的最大和

设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. // #include <vector> using namespace std; class Solution { public: int FindGreatestSumOfSubArray(vector<int> array) { if (array....

刷遍天下无敌手

0 点赞评论收藏

分享

2020-09-18 10:46

已编辑

华中科技大学 C++

字符串的排列

三种方法； 基于库函数next_permutation(begin, end) 去重方法：先sort初始字符串再处理（本题初始字符串已经有序） 基于回溯 通过一个visited数组记录已经被选中的位置 去重方法：通过set进行去重 基于交换 去重方法：通过set进行去重 方法一的代码： // // Created by jt on 2020/9/18. // #include <string> #include <vector> #include <algorithm> using namespace std; class Solution...

刷遍天下无敌手

0 点赞评论收藏

分享

2020-09-15 16:07

华中科技大学 C++

设计LRU缓存结构

这是一道类的设计题，此类题目要求我们理解各个基本数据结构的用法及其复杂度，并且学会组合它们： 存储键值对——map/unordered_map 存储集合——set/unordered_set 查找最大/最小/topk值——大顶堆/小顶堆/平衡二叉树 序列结构——数组&链表 字符串索引——trie树（百度常考） 本题要求get和set的时间复杂度都是O(1)，我们可以采用unordered_map和双向链表的组合数据结构，原理如下图： 对于两个操作的解释如下： set操作： 如果key存在于map中，更新value，然后把节点移到双向链表头部 如果key不在map中且没有溢出，...

刷遍天下无敌手

0 点赞评论收藏

分享

2020-09-15 10:16

华中科技大学 C++

最长递增子序列

两步走： 第一步——求最长递增子序列长度 第二步——求字典序靠前的子序列 对于第一步，有两种解法： 动态规划，时间复杂度为O(n^2)，会超时 贪心+二分，时间复杂度为O(nlogn) 下面说说贪心+二分的解法，举例说明基本思路，假设数组arr为[2, 3, 1, 2, 3]，vec数组里面存放递增子序列，maxLen数组里存放以元素i结尾的最大递增子序列长度，那么遍历数组arr并执行如下更新规则: 初始情况下，vec为[2]，maxLen[1] 接下来遇到3，由于vec最后一个元素小于3，直接更新，vec为[2,3]，maxLen[1,2] 接下来遇到1，由于vec最后的元素大于...

牛客四二三号：该题解结合力扣官方题解+代码，看了一个小时才看懂= =

刷遍天下无敌手

0 点赞评论收藏

分享

2020-09-07 10:41

华中科技大学 C++

并查集的实现

我以前也不会呀，自从用了并查集之后，嗨，效果还真好！我们全家都用它！——某大佬 关于并查集，有以下题型： LeetCode130——Surrounded Regions——给了个二维 grid，把里面O全部变成X，但是边界和边界联通区域内的O保留（也能用DFS） LeetCode261——Graph Valid Tree——给了N个结点和一个边的集合，问这个边的集合能不能构成一棵树 ... 并查集是一种树形数据结构，它由一个整型数组和两种操作组成： 整型数组——记录每一个点对应前导点的下标 find——确定元素属于哪一个子集，可以使用它来确定两个元素是否属于同一个子集 union——将...

刷遍天下无敌手

0 点赞评论收藏

分享

2020-09-06 19:54

已编辑

华中科技大学 C++

设元素中除了某个孤立数外，其他数都出现过且只出现过N次，解题方法如下： 如果N为偶数，那么直接将每个元素异或后的结果即是最终结果 如果N为奇数，我们可以依次判断每一位为1还是为0 本题代码如下： // // Created by jt on 2020/9/6. // class Solution { public: /** * * @param A int整型一维数组 * @param n int A数组长度 * @return int整型 */ int singleNumber(int* A, int n) { ...

刷遍天下无敌手

0 点赞评论收藏

分享

2020-09-05 18:03

华中科技大学 C++

这一问题可以有如下问法（都是空间复杂度为常数级别）： 矩阵左旋/右旋90度 矩阵左旋/右旋180度 对于本题，有两种思路： 思路一：利用对称进行旋转——先根据主对角线互换元素，再根据垂直中线互换元素 思路二：利用坐标映射 强烈建议用第一种方法，因为找第二种方法的坐标关系特别特别特别麻烦 举一反三：面对旋转、填充一类的题型，一定要考虑对称这一“大杀器”，它能极大的减少工作量，提高解题正确率和解题效率 思路一的代码 // // Created by jt on 2020/9/5. // #include <vector> #include <algorithm&g...

刷遍天下无敌手

0 点赞评论收藏

分享

关注他的用户也关注了：

牛客网
牛客企业服务