asto18089

题解

/ 注册

全部文章 / 题解（共9篇）

题解 | #连续子数组最大和(ACM版本)#

很巧妙的解决方法，也不是什么动态规划，只要想明白了这种子数组的出现规律就很好明白。 32位int塞不下某些数据，需要用64位long。 #include <vector> #include <climits> using namespace std; int main()...

C++

2022-01-12

0 505

题解 | #两数之和#

很经典的一道unordered_map题。 public: /** * * @param numbers int整型vector * @param target int整型 * @return int整型vector */ ve...

C++

2022-01-12

0 387

题解 | #寻找第K大#

快速选择(Quickselect)算法，快速排序的近亲。C++ STL的nth_element正是这个功能。时间复杂度O(N)，空间复杂度O(1)，题目的O(NlogN)有问题。 public: int findKth(vector<int> a, int n, int K) ...

C++

2022-01-12

0 279

题解 | #最小的K个数#

快速选择(Quickselect)算法，C++ STL的nth_element正是这个。平均时间复杂度O(n)，空间复杂度O(1)。 public: vector<int> GetLeastNumbers_Solution(vector<int> input, in...

C++

2022-01-12

0 297

题解 | #判断链表中是否有环#

两个方法，一个快慢指针，一个把所有节点存起来。快慢指针会更省内存。下面是最直观的把所有节点存起来的方法，如果想不到快慢指针至少也得想到这个。 * Definition for singly-linked list. * struct ListNode { * int val; * ...

C++

2022-01-12

1 394

题解 | #设计LRU缓存结构#

一个list存数据，一个unordered_map存key和对应数据的引用。这里最最最最最最最最最关键的一点就是List增删改元素是不会使迭代器无效的，只要知道这个，写出对应的数据结构和算法应该不会难。下面的代码对于数据的pair做了移动处理，可能可以提升get太多情况下的效能。不过不太知道这会...

C++

2022-01-12

0 302

题解 | #数组中的最长连续子序列#

Priority Queue yyds # # max increasing subsequence # @param arr int整型一维数组 the array # @return int整型 # import heapq class Solution: def MLS(self , ...

Python3

2021-10-12

0 309

题解 | #接雨水问题#

随便乱打的，懒得优化了。花了大概40多分钟吧，我在算法上属实是极不擅长。这方法是O(n)时间是O(1)空间没错，不过还是可以更快一些的，可以找个变量存储一下局部最高值，这样可以省去回扫的时间 # # max water # @param arr int整型一维数组 the array # @ret...

Python3

2021-10-12

0 393

题解 | #子数组的最大累加和问题#

此题本质上并不是一道正儿八经的动态规划题。不需要分治，从头扫到尾，记住一些状态变量即可轻松完成。 int maxsumofSubarray(int* arr, int arrLen ) { &...

2021-07-12

0 329