传送门:4. Median of Two Sorted Arrays这是一道 Hard 级别的题目,主要难点是要求实现 $O(\log(m+n))$ 的时间复杂度。暴力算法最容易想到的就是双指针,分别指向两个数组的首个元素。比较两个指针元素的大小,向后移动较小的一个并计数。此算法时间复杂度为 $O(m+n)$,其实不算差,但不满足题目要求。二分排除时间复杂度:$ O(\log(k)) $ =...
传送门:4. Median of Two Sorted Arrays这是一道 Hard 级别的题目,主要难点是要求实现 $O(\log(m+n))$ 的时间复杂度。暴力算法最容易想到的就是双指针,分别指向两个数组的首个元素。比较两个指针元素的大小,向后移动较小的一个并计数。此算法时间复杂度为 $O(m+n)$,其实不算差,但不满足题目要求。二分排除时间复杂度:$ O(\log(k)) $ =...
总结回溯问题通常包含对某一集合的递归遍历,在遍历的过程中选取元素,在回溯的过程中撤销选取。最终达到遍历所有可选取的组合,记录符合条件的那些。排列与组合递归遍历的过程中,每次都从第一个元素开始,还是从上一层遍历的位置开始呢?对于排列问题,每次都要从头开始;对于组合问题,需要接续遍历,因此递归函数需要一个参数指明从哪开始遍历。排列:选中集合的不同顺序视为多个有效答案。组合:选中集合的不同顺序只视...
动态规划通过保存已经计算过的结果,优化计算所有可能性的过程。 下面几种问题都牵扯所有可能性的计算:优化问题:在所有可能的解决方案中,寻找用时最短/代价最少的等。【例】爬楼的最低成本求所有解:需要求出所有的情况,而不是选出其中的一个。【例】斐波那契数列背包问题:给定候选物品与限制,求最佳选择方案。解题步骤动态规划是一个思想,不是某个具体的算法。它分为好几个步骤,不同步骤要寻找各自的算法。寻找递...
传送门Given an integer array nums, return an integer array counts where counts[i] is the number of smaller elements to the right of nums[i].这是一个 Hard 级别的题,描述很简单,暴力解法也比较容易想出来:遍历数组,针对每个元素,遍历它后面的元素得出小于它的...
当我们感觉局部最优可以推出全局最优,一时找不到反例时就可以使用贪心算法。所谓「贪心」就是只在眼下找到最好的方法。贪心算法相对比较抽象,不像滑动窗口那么好识别有套路。局部最优有很多种表现形式:例如先处理一部分元素,再处理其他部分。或者先从一个维度处理全部元素,再从另一个维度处理。不要把「局部」狭义地理解成「一部分元素」。一般来说贪心算法需要先进行某种形式的排序,因为只有在有序序列中才可能找到局...
传送门According to Wikipedia, every level, except possibly the last, is completely filled in a complete binary tree, and all nodes in the last level are as far left as possible. It can have between 1 ...
梦开始的地方 (LeetCode 第一题)传送门Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.You may assume that each input would have exactly on...
传送门You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each...