amuleter

算法

Java(10) 操作系统(8) 未归档(21) 杂项(11) 计算机组成(3) 计算机网络(4)

/ 注册

全部文章 / 算法（共27篇）

[每日一题2020.06.27] leetcode #41 set 内部交换

方法一利用set 空间\(O(n)\) 时间 \(O(n)\) 利用一个set存储映射关系, 然后直接从1 - size遍历找出第一个不在set中的元素就可以 int firstMissingPositive(vector<int>& nums) { set<...

rocco------每日一题

2020-06-27

0 548

[每日一题2020.06.26]最大回文子串 manachar

题目 : 就是一个求最大回文子串的模板题 : 方法一 : 中心扩展时间复杂度\(O(n^2)\) 之前在leetcode上就是用的中心扩展做的, 勉强过了中心扩展思路很简单, 就是遍历一遍字符串, 然后对于每一个字符都向左右扩展求最大回文串这道题的中心扩展代码 : #inc...

rocco------每日一题

2020-06-26

0 550

manachar算法求最大回文子串

manachar算法本质上是利用了回文串的对称特性, 在不断向右遍历的同时求一个对称点从而减少操作. 从这个入手 : 可以看到, 在遍历到ptr所指的位置时, 由于右边和左边完全对称, 我们可以直接求ptr关于b对称的对称点处的最大回文长度, 就是ptr处的回文长度. 关于manac...

rocco-----算法

2020-06-26

0 567

[每日一题2020.06.25]leetcode #139 dp

dp的方式, dp[i]表示该位置之前的词是否可拆分, 每个位置都需要从头遍历到当前位置, 并判断dp[j] && substr(i,j-i)保证substr在字典. 时间复杂度\(O(n^2)\) 开始直接hashmap映射一下方便后面判断 unordered_map<st...

rocco------每日一题

2020-06-25

0 386

[每日一题2020.06.24]leetcode #46 dfs

题目 : https://leetcode-cn.com/problems/permutations/ 一道标准的dfs题, 用一个哈希map做标记, tmp用来记录路径过程 : 标记 -- 加入路径 -- 下一层 -- 解除标记回溯 unordered_map<int, bo...

rocco------每日一题

2020-06-24

0 469

[每日一题2020.06.23]leetcode #16 双指针

https://leetcode-cn.com/problems/3sum-closest/submissions/ 先对数组进行排序 $ O(nlogn) $ , 然后遍历 + 双指针 $ O (n^2) $ int threeSumClosest(vector<int>&...

rocco------每日一题

2020-06-24

0 434

[每日一题2020.06.22]leetcode #11 双指针

https://leetcode-cn.com/problems/container-with-most-water/ 解 : 移动高的那一端不会得到更优的结果, 所以我们每次只需要移动矮的那一端即可 class Solution { public: int maxArea...

rocco------每日一题

2020-06-22

0 558

[每日一题2020.06.20]BFS

一道典型的BFS题需要注意的是 : 记录路径, 采用记录上一个点是如何到这一个点的方式 ( 前驱 ) BFS求得的路一定是最短路, 因为采用的是层层扩展的方式然后就是一些细节问题了 #include<vector> #include<queue>...

rocco------每日一题

2020-06-19

0 348

[每日一题2020.06.19]leetcode #84 #121 单调栈

今天又做了两个单调栈的题目, 思路都不难, 就是有很多小细节需要注意的先放两道题的地址 : #84 ( hard ) #121 ( easy ) 121 买卖股票的最佳时机题意 : 一个固定顺序的数组找到一前以后两个元素差的最大值首先, 这个数组定序, 肯定不能直接遍历找最大...

rocco------每日一题

2020-06-18

0 532

[每日一题2020.06.18]leetcode #3 hash_map实现滑动窗口

题解 : 利用hashmap ( C++中的unordered map, map也行不过map基于红黑树速度慢点 ) 保存每一个字符第一次出现的位置, 用一个r ( 窗口右侧 ) 向后遍历, 找到第一个出现在map里的数, 更新l (窗口左侧) 为 map[s[r]] + 1, 实现窗口的...

rocco------每日一题

2020-06-17

0 447