请实现最近最少使用缓存(Least Recently Used (LRU) cache)类,需要支持 get, set,操作。 get 操作,给出 key,获取到相应的 value (value 为非负数),如果不存在返回-1, 如果存在此 key 算作被访问过。 set 操作,设置 key,如果 key 存在则覆盖之前的 value (此时相当于访问过一次)。 如果 key 不存在,需要进行插入操作,如果此时已经 key 的数量已经到达 capacity, 这样需要淘汰掉最近最少使用(也就是上次被使用的时间距离现在最久的)的那 一项。 要求get和set的时间复杂度都是O(1) /* …

随便记录一下面试中遇到的问题： 梯度下降和牛顿迭代的区别？为什么常用梯度下降？ **牛顿法是二阶收敛，梯度下降是一阶收敛，所以牛顿法就更快**。如果更通俗地说的话，比如你想找一条最短的路径走到一个盆地的最底部，梯度下降法每次只从你当前所处位置选一个坡度最大的方向走一步，牛顿法在选择方向时，不仅会考虑坡度是否够大，还会考虑你走了一步之后，坡度是否会变得更大。所以，可以说牛顿法比梯度下降法看得更远一点，能更快地走到最底部。 根据wiki上的解释，从几何上说，牛顿法就是用一个二次曲面去拟合你当前所处位置的局部曲面，而梯度下降法是用一个平面去拟合当前的局部曲面，通常情况下，二次曲面的拟合会比平面更好，所以牛顿法选择的下降路径会更符合真实的最 …

A peak element is an element that is greater than its neighbors. Given an input array where num[i] ≠ num[i+1], find a peak element and return its index. The array may contain multiple peaks, in that case return the index to any one of the peaks is fine. You may imagine that num[-1] = num[n] = -∞. For example, in array …

Find the contiguous subarray within an array (containing at least one number) which has the largest product. For example, given the array [2,3,-2,4], the contiguous subarray [2,3] has the largest product = 6. 思路：由于有正，有负，还有0.。。所以比最大子串之和要复杂一些。。。 dp[i].max表示到当前位置的最大乘积。 dp[i].min表示到当前位置的最小乘积。 dp[i].max = …

Given a sorted integer array without duplicates, return the summary of its ranges. For example, given [0,1,2,4,5,7], return ["0->2","4->5","7"]. 题意：把连续的数连续表示 思路：模拟。注意有负数，注意有-2147483648这种数据。 本来还想着，可能是leetcode加数据的审核机制太松，导致被人加了奇怪的数据。。。 结果发现出题人和加数据的人是一个人啊？ 不给数据范围，加这种奇怪的数据很有意思？ 分分钟卡掉你的标程 …

Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there isn't one, return 0 instead. For example, given the array [2,3,1,2,4,3] and s = 7, the subarray [4,3] has the minimal length under the problem constraint 思路：尺取即可。。好久没写，竟然调了半 …

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times. The algorithm should run in linear time and in O(1) space. 题意：给你n个数，要求找出出现此处大于n/3的。。。 思路：之前做过一个找出n个数出现此处大于n/2的题目，思想是“非吾族类，其心必异”。。 这道题类似。。。容易知道题目要求的数最多有2个，最少有0个。。。 由于最多两个“族类”，在更新的时候，要判断是不是友军的人...毕竟朋友妻不可欺嘛（什么鬼 最后记得扫一遍，check一下，检查出现此处是 …

Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue. Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively. 题意：一个数组，由0,1,2组成，现在要求升序排列 思路：无脑做法就是计数排序，扫两遍，时间复杂 …

Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water. Note: You may not …

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution. 思路： 排序，然后two pointer,复杂度 O(n^2) /* *********************************************** Author :111qqz Created …