Leetcode练习册。

Find All Numbers Disappeared in an Array (easy)

Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.

Find all the elements of [1, n] inclusive that do not appear in this array.

Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.

Example:

Code $O(n)+O(1)$ 归位法

Python为什么不需要swap(a, b) - 追寻真理之美- CSDN博客 Code MLE $O(n)+O(n)$ 集合运算

TimeComplexity - Python WikiDifference s-t

jump Game (medium)

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

Example 1:

Example 2:（注意，有0。但有0只是必要条件）

jump Game2 (hard)

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

Example:

Note:

You can assume that you can always reach the last index.（其实只要不含0就一定能抵达）

k：平均跳跃距离。

Longest Substring Without Repeating Characters (medium)

Given a string, find the length of the longest substring without repeating characters.

Example 1:

Example 2:

Example 3:

Code $O(n)+O(dict)$ 减治+Hash

hash集存储每个字符对应的最大出现位置。

Substring with Concatenation of All Words (hard)

You are given a string, s, and a list of words, words, that are all of the same length. Find all starting indices of substring(s) in s that is a concatenation(级联,一连串) of each word in words exactly once and without any intervening(介入的) characters.

Example 1:

Example 2:

Maximum Subarray (easy)

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

Code $O(n)+O(1)$ 减治 Code $O(nlogn)$ 分治 Count Primes (easy)

Count the number of prime numbers less than a non-negative number, n.

Example:

Python 类变量与实例变量

Code $O(logP)+O(P)$ 打表

P是所有质数的数量。二分查找。

Next Permutation (medium)

Implement next permutation（置换）, which rearranges numbers into the lexicographically（字典序） next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place and use only constant extra memory（就地算法）.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.

H-Index (medium)

Given an array of citations (each citation is a non-negative integer) of a researcher, write a function to compute the researcher’s h-index.

According to the definition of h-index on Wikipedia: “A scientist has index h if h of his/her N papers have at least h citations each, and the other N − h papers have no more than h citations each.”

Example:

Note: If there are several possible values for h, the maximum one is taken as the h-index.

Code $O(n)$ Median of Two Sorted Arrays (hard)

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

You may assume nums1 and nums2 cannot be both empty.

Example 1:

Example 2:

Search Insert Position (easy)

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

Example 1:

Example 2:

Example 3:

Example 4:

Max Consecutive Ones (easy)

Given a binary array, find the maximum number of consecutive(连续) 1s in this array.

Example 1:

Note:

• The input array will only contain 0 and 1.
• The length of input array is a positive integer and will not exceed 10,000

Permutation Sequence(medium)

The set [1,2,3,...,*n*] contains a total of n! unique permutations.

By listing and labeling all of the permutations in order, we get the following sequence 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.
• Given k will be between 1 and n! inclusive.

Example 1:

Example 2:

Permutations II (medium)

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

Example:

Max Points on a Line (hard)

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

Example 1:

Example 2:

Contains Duplicate (Easy)

Given an array of integers, find if the array contains any duplicates.

Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.

Example 1:

Example 2:

Example 3:

Contains Duplicate II (Easy)

Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the absolute difference between i and j is at most k.

Example 1:

Example 2:

Example 3:

Combination Sum (Medium)

Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.

The same repeated number may be chosen from candidates unlimited number of times.

Note:

• All numbers (including target) will be positive integers.
• The solution set must not contain duplicate combinations.

Example 1:

Example 2:

Combination Sum II (Medium)

Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.

Each number in candidates may only be used once in the combination.

Note:

• All numbers (including target) will be positive integers.
• The solution set must not contain duplicate combinations.

Example 1:

Example 2:

Minimum Window Substring (hard)

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

Example:

Note:

• If there is no such window in S that covers all characters in T, return the empty string "".
• If there is such window, you are guaranteed that there will always be only one unique minimum window in S.

0%