很巧妙的解决方法，也不是什么动态规划，只要想明白了这种子数组的出现规律就很好明白。 32位int塞不下某些数据，需要用64位long。 #include <vector> #include <climits> using namespace std; int main() { int n; scanf("%ld", &n); vector<long> arr(n); for (int i = 0; i < n; i++) { scanf("%ld", &arr[i]); } long max = 0; long cur = 0; for...

很经典的一道unordered_map题。 public: /** * * @param numbers int整型vector * @param target int整型 * @return int整型vector */ vector<int> twoSum(vector<int>& numbers, int target) { unordered_map<int, int> npos; vector<int> result(2,0); for (int i = 0; i < numbers.size(); i++) { if (...

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

快速选择(Quickselect)算法，C++ STL的nth_element正是这个。 平均时间复杂度O(n)，空间复杂度O(1)。 public: vector<int> GetLeastNumbers_Solution(vector<int> input, int k) { vector<int>::iterator target_pos = input.begin() + k - 1; nth_element(input.begin(), target_pos, input.end()); return vector<int>(input...

两个方法，一个快慢指针，一个把所有节点存起来。快慢指针会更省内存。 下面是最直观的把所有节点存起来的方法，如果想不到快慢指针至少也得想到这个。  * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: unordered_set<ListNode*> visited; bool hasCycle(ListNode *he...

一个list存数据，一个unordered_map存key和对应数据的引用。 这里最最最最最最最最最关键的一点就是List增删改元素是不会使迭代器无效的，只要知道这个，写出对应的数据结构和算法应该不会难。 下面的代码对于数据的pair做了移动处理，可能可以提升get太多情况下的效能。不过不太知道这会不会产生UB，还请大手子解答！ public: /** * lru design * @param operators int整型vector<vector<>> the ops * @param k int整型 the k * @return int整型vector */ ...

Priority Queue yyds # # max increasing subsequence # @param arr int整型一维数组 the array # @return int整型 # import heapq class Solution: def MLS(self , arr ): eleCount = len(arr) heapq.heapify(arr) count = 1 maxCount = 1 lastPop = heapq.heappop(arr) for _ in range(eleCount - 1): cur = heapq.heappop(arr) i...

随便乱打的，懒得优化了。花了大概40多分钟吧，我在算法上属实是极不擅长。 这方法是O(n)时间是O(1)空间没错，不过还是可以更快一些的，可以找个变量存储一下局部最高值，这样可以省去回扫的时间 # # max water # @param arr int整型一维数组 the array # @return long长整型 # class Solution: def maxWater(self , arr ): # write code here ls = arr[0] total = 0 total_cur = 0 lsDist = 0 for i in range(len(arr)): if...

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