# 111qqz的小窝

## leetcode 146. LRU Cache(list+unordered_map)

set,操作。
get 操作,给出 key,获取到相应的 value (value 为非负数),如果不存在返回-1,

set 操作,设置 key,如果 key 存在则覆盖之前的 value (此时相当于访问过一次)。

## 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.

## 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.

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同理

## 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"].

## 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.

## 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.

## 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.

## 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.

## 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.

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.

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.

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

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

## 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.