Given a string, find the length of the longest substring without repeating characters.
Examples: Given “abcabcbb”, the answer is “abc”, which the length is 3. Given “bbbbb”, the answer is “b”, with the length of 1. Given “pwwkew”, the answer is “wke”, with the length of 3. Note that the answer must be a substring, “pwke” is a subsequence and not a substring.
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.
res = max(res, min(height[low], height[high])*(high-low))
if height[low] > height[high]:
high -= 1
else:
low += 1
return res
16. 3Sum Cloest
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.
1
2
For example, given array S = {-1 2 1 -4}, and target = 1.
The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
Say you have an array for which the ith element is the price of a given stock on day i.
If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.
Example 1:
1
2
3
4
Input: [7, 1, 5, 3, 6, 4]
Output: 5
max. difference = 6-1 = 5 (not 7-1 = 6, as selling price needs to be larger than buying price)
Example 2:
1
2
3
4
Input: [7, 6, 4, 3, 1]
Output: 0
In this case, no transaction is done, i.e. max profit = 0.
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
Find the minimum element.
You may assume no duplicate exists in the array.
LeetCode原题的简化版。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
classSolution:
deffindMin(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
n = len(nums)
if n <= 2:
return min(nums)
low, high = 0, n-1
if nums[high] > nums[low]:
return nums[low]
while low <= high:
mid = (low+high)//2
if nums[mid] < nums[high]:
high = mid
else:
low = mid + 1
return nums[high]
198. House Robber
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.
Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.
这道题应该是用动态规划。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
classSolution(object):
defrob(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
n = len(nums)
if n == 0:
return0
elif n == 1:
return nums[0]
elif n == 2:
return max(nums)
prev, curr = nums[0], max(nums[0:2])
for i in range(2, n):
res = max(prev+nums[i], curr)
prev, curr = curr, res
return res
300. Longest Increasing Subsequence
Given an unsorted array of integers, find the length of longest increasing subsequence.
For example, Given [10, 9, 2, 5, 3, 7, 101, 18], The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4. Note that there may be more than one LIS combination, it is only necessary for you to return the length.
Your algorithm should run in O(n^2) complexity.
Follow up: Could you improve it to O(n log n) time complexity?
解题思路： tails is an array storing the smallest tail of all increasing subsequences with length i+1 in tails[i]. For example, say we have nums=[4, 5, 6, 3], then all the available increasing subsequences are:
1
2
3
len = 1: [4], [5], [6], [3] => tails[0] = 3
len = 2: [4, 5], [5, 6] => tails[1] = 5
len = 3: [4, 5, 6] => tails[2] = 6
We can easily prove that tails is an increeasing array. Therefore it is possible to do a binary search in tails array to find the one needs update. Each time we only do one of the two: 1) if x is larger than all tails, append it, increase the size by 1 2) if tails[i-1] < x <= tails[i], update tails[i]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
classSolution(object):
deflengthOfLIS(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
n = len(nums)
tails = [0] * n
size = 0
for x in nums:
i, j = 0, size
while i != j:
m = (i+j)/2
if tails[m] < x:
i = m+1
else:
j = m
tails[i] = x
size = max(i+1, size)
return size
303. Range Sum Query - Immutable
Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.
Example:
1
2
3
4
5
Given nums = [-2, 0, 3, -5, 2, -1]
sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3
Note:
You may assume that the array does not change.
There are many calls to sumRange function.
DP问题，我们可以用一个数组来存储前k个元素的和。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
classNumArray:
def__init__(self, nums):
"""
:type nums: List[int]
"""
self.dp, n = nums, len(nums)
for i in range(1, n):
self.dp[i] += self.dp[i-1]
defsumRange(self, i, j):
"""
:type i: int
:type j: int
:rtype: int
"""
return self.dp[j] - (self.dp[i-1] if i > 0else0)
# Your NumArray object will be instantiated and called as such:
# obj = NumArray(nums)
# param_1 = obj.sumRange(i,j)
392. Is Subsequence
Given a string s and a string t, check if s is subsequence of t.
You may assume that there is only lower case English letters in both s and t. t is potentially a very long (length ~= 500,000) string, and s is a short string (<=100).
A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, “ace” is a subsequence of “abcde” while “aec” is not).
Example 1:
1
2
3
s = "abc", t = "ahbgdc"
Return true.
Example 2:
1
2
3
s = "axc", t = "ahbgdc"
Return false.
Follow up: If there are lots of incoming S, say S1, S2, … , Sk where k >= 1B, and you want to check one by one to see if T has its subsequence. In this scenario, how would you change your code?
直接用两个指针分别去遍历两个字符串即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
classSolution:
defisSubsequence(self, s, t):
"""
:type s: str
:type t: str
:rtype: bool
"""
lens, lent = len(s), len(t)
index1, index2 = 0, 0
while index1 < lens and index2 < lent:
if s[index1] == t[index2]:
index1 += 1
index2 += 1
else:
index2 += 1
if index1 == lens:
returnTrue
else:
returnFalse
416. Partition Equal Subset Sum
Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.
Note:
Each of the array element will not exceed 100.
The array size will not exceed 200.
Example 1:
1
2
3
4
5
Input: [1, 5, 11, 5]
Output: true
Explanation: The array can be partitioned as [1, 5, 5] and [11].
Example 2:
1
2
3
4
5
Input: [1, 2, 3, 5]
Output: false
Explanation: The array cannot be partitioned into equal sum subsets.
d = [[Falsefor x in range(half_sum+1)] for y in range(n+1)]
for k in range(n+1):
d[k][0] = True
for i in range(1, n+1):
for j in range(0, half_sum+1):
d[i][j] = d[i-1][j]
if j >= nums[i-1]:
d[i][j] = d[i][j] | d[i-1][j-nums[i-1]]
print(d)
return d[len(nums)][half_sum]
646. Maximum Length of Pair Chain
You are given n pairs of numbers. In every pair, the first number is always smaller than the second number.
Now, we define a pair (c, d) can follow another pair (a, b) if and only if b < c. Chain of pairs can be formed in this fashion.
Given a set of pairs, find the length longest chain which can be formed. You needn’t use up all the given pairs. You can select pairs in any order.
Example 1:
1
2
3
Input: [[1,2], [2,3], [3,4]]
Output: 2
Explanation: The longest chain is [1,2] -> [3,4]
Note:
The number of given pairs will be in the range [1, 1000].
DP问题，下面是三种解法，后两种是一样的，只用一层for循环；第一种用了两层for循环，结果超时。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
classSolution:
deffindLongestChain(self, pairs):
"""
:type pairs: List[List[int]]
:rtype: int
"""
# 两层for循环的DP操作超时
n = len(pairs)
pairs = sorted(pairs, key=lambda x: x[0])
res = [1] * n
for i in range(n-1, -1, -1):
for j in range(i+1, n):
if pairs[i][1] < pairs[j][0]:
res[i] = max(res[i], res[j] + 1)
else:
res[i] = max(res[i], res[j])
return max(res)
deffindLongestChain2(self, pairs):
"""
:type pairs: List[List[int]]
:rtype: int
"""
cur, res, n= float('inf'), 0, len(pairs)
pairs = sorted(pairs, key=lambda x: x[0])
for i in range(n-1, -1, -1):
if cur > pairs[i][1]:
cur, res = pairs[i][0], res + 1
return res
deffindLongestChain3(self, pairs):
"""
:type pairs: List[List[int]]
:rtype: int
"""
cur, res = float('-inf'), 0
pairs = sorted(pairs, key=lambda x: x[1])
for p in pairs:
if cur < p[0]:
cur, res = p[1], res + 1
return res
740. Delete and Earn
Given an array nums of integers, you can perform operations on the array.
In each operation, you pick any nums[i] and delete it to earn nums[i] points. After, you must delete every element equal to nums[i] - 1 or nums[i] + 1.
You start with 0 points. Return the maximum number of points you can earn by applying such operations.
Example 1:
1
2
3
4
5
Input: nums = [3, 4, 2]
Output: 6
Explanation:
Delete 4 to earn 4 points, consequently 3 is also deleted.
Then, delete 2 to earn 2 points. 6 total points are earned.
Example 2:
1
2
3
4
5
6
Input: nums = [2, 2, 3, 3, 3, 4]
Output: 9
Explanation:
Delete 3 to earn 3 points, deleting both 2's and the 4.
Then, delete 3 again to earn 3 points, and 3 again to earn 3 points.
9 total points are earned.
Note:
The length of nums is at most 20000.
Each element nums[i] is an integer in the range [1, 10000].
On a staircase, the i-th step has some non-negative cost cost[i] assigned (0 indexed).
Once you pay the cost, you can either climb one or two steps. You need to find minimum cost to reach the top of the floor, and you can either start from the step with index 0, or the step with index 1.
Example 1:
1
2
3
**Input:** cost = [10, 15, 20]
**Output:** 15
**Explanation:** Cheapest is start on cost[1], pay that cost and go to the top.