111qqz的小窝

老年咸鱼冲锋!

leetcode 146. LRU Cache(list+unordered_map)

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

要求get和set的时间复杂度都是O(1)

 

leetcode162. Find Peak Element (O(lgn)复杂度寻找峰值)

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 [1, 2, 3, 1], 3 is a peak element and your function should return the index number 2.

click to show spoilers.

Note:Your solution should be in logarithmic complexity.

思路:

为什么能lgn。。。

首先要想明白,这样的峰值是一定存在的(因为最左最右已经负无穷了。

如果中间元素的值,比它右边相邻元素的小,说明什么呢?

说明右边区间一定存在峰值。

为什么?

现在a[mid]<a[mid+1]

如果a[mid+1]>a[mid+2],那么 a[mid+1]就是峰值

如果a[mid+1]<=a[mid+2],那么可以继续缩小区间,到[mid+2,n-1]

由于a[n]为负无穷,因此至少会出现一个 a[x]>a[x+1]的情况,此时a[x]就是峰值。

想清楚了这点就好办了。二分就好。

 

leetcode 152. Maximum Product Subarray (最大连续子序列乘积,dp)

 

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 = max{dp[i-1].max*a[i],dp[i-1].min*a[i],a[i]};

dp[i].min同理

边界dp[i].max = dp[i].min = a[0]

 

 

leetcode 228. Summary Ranges

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加数据的审核机制太松,导致被人加了奇怪的数据。。。

结果发现出题人和加数据的人是一个人啊?

不给数据范围,加这种奇怪的数据很有意思? 分分钟卡掉你的标程啊?

感觉像吃了苍蝇一样恶心。。一句话,出题人傻逼

 

 

leetcode 209. Minimum Size Subarray Sum (尺取法)

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

 

思路:尺取即可。。好久没写,竟然调了半天。。。

 

leetcode 229. Majority Element II (O(1)空间找出现次数大于n/3的元素)

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一下,检查出现此处是否满足题意。

 

 

leetcode 75. Sort Colors

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组成,现在要求升序排列

思路:无脑做法就是计数排序,扫两遍,时间复杂度O(n),空间复杂度O(1)

如果只扫一遍呢?

一个容易想到的思路是两个指针:

需要注意 的是,交换2后要再次遍历到当前位置,或者说,只有当不交换2的时候,才执行cur++

 

 

 

还有一个神奇的思路:r,w,b分别表示下一个对应颜色要放的位置。

如果当前是0,那么0,1,2都要后移一个。

如果当前是1,那么1,2的位置需要后移。

如果当前是2,那么2的位置需要后移。

 

leetcode 11. Container With Most Water (two pointer)

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 slant the container and n is at least 2.

题意:n条竖直的线段 (i,0)->(i,a[i]),从中选2条,和x轴共同组成一个开口的容器,问容器的最大面积。

思路:一开始想错了,以为是最大连续矩形面积…还在想leetcode竟然考单调栈???

然而实际上只取两个线段,中间的线段有没有,长度,都是无所谓的。

因此two pointer就好了。。。

 

leetcode 16. 3Sum Closest (k-sum问题,two pointer)

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)

 

leetcode 18. 4Sum (k-sum问题,two pointer)

Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note: The solution set must not contain duplicate quadruplets.

思路: O(n^2)枚举两个元素,变成2-sum问题,总体复杂度O(n^3)

hash的解法以后补

 

leetcode 15. 3Sum (k-sum问题,two pointer)

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note: The solution set must not contain duplicate triplets.

 

思路:排序O(nlgn),然后枚举一个元素O(n),对于每个元素,在剩下的区间中 two pointer O(n)

整体复杂度 O(n^2)。

hash的解法以后补。

 

 

leetcode 216. Combination Sum III Add to List (枚举子集,限定集合大小,和为定值)

Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.

题意:1..9个数,从中选择k个,和为n,要求输出所有满足题意的集合。

思路:枚举子集,根据sum和集合元素个数剪枝即可。

 

leetcode 77. Combinations (枚举子集,限定集合大小)

Given two integers n and k, return all possible combinations of k numbers out of 1 … n.

思路:就是枚举子集,根据集合的大小剪枝。。。最后只要集合大小为k的集合

 

leetcode 60. Permutation Sequence (求第k个排列)

The set [1,2,3,,<i>n</i>] contains a total of n! unique permutations.

By listing and labeling all of the permutations in order,
We get the following sequence (ie, for n = 3):

  1. "123"
  2. "132"
  3. "213"
  4. "231"
  5. "312"
  6. "321"

Given n and k, return the kth permutation sequence.

Note: Given n will be between 1 and 9 inclusive.

 

思路:还是根据leetcode 31 解题报告 中的算法搞一下就好了。。

 

leetcode 47. Permutations II (生成全排列,有重复元素)

Given a collection of numbers that might contain duplicates, return all possible unique permutations.
思路:和leet code 46 类似,最后用set去个重即可。。

 

粤ICP备18103363