0%

# 007. Reverse Integer

## 刷题内容

Given a 32-bit signed integer, reverse digits of an integer.

#### Example 1:

`````` Input: 123
Output: 321
``````

#### Example 2:

`````` Input: -123
Output: -321

``````

#### Example 3:

`````` Input: 120
Output: 21
``````

#### Note:

`````` Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−231,  231 − 1]. For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.
``````

## 解题方案

**- 时间复杂度: O(1)**- 空间复杂度: O(N)**

# 008. String to Integer (atoi)

## 解题方案

**- 时间复杂度: O(1)**- 空间复杂度: O(N)**

# 9. Palindrome Number

## 解题方案

**- 时间复杂度: O(log2 N)**- 空间复杂度: O(1)**

• 不使用字符串,使用除法分别从首尾获得数字，最后对比是否相同

**- 时间复杂度: O(N)**- 空间复杂度: O(N)**

• 转化为字符串，reverse字符串

# 11. Container With Most Water

## 解题方案

**- 时间复杂度: O(N)**- 空间复杂度: O(1)**

• 从数组两层对向查找，直到找到最大乘积

**- 时间复杂度: O(N²)**- 空间复杂度: O(1)**

# 12. Integer to Roman

## 刷题内容

Roman numerals are represented by seven different symbols: `I`, `V`, `X`, `L`, `C`, `D` and `M`.

For example, two is written as `II` in Roman numeral, just two one’s added together. Twelve is written as, `XII`, which is simply `X` + `II`. The number twenty seven is written as `XXVII`, which is `XX` + `V` + `II`.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not `IIII`. Instead, the number four is written as `IV`. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as `IX`. There are six instances where subtraction is used:

• `I` can be placed before `V` (5) and `X` (10) to make 4 and 9.
• `X` can be placed before `L` (50) and `C` (100) to make 40 and 90.
• `C` can be placed before `D` (500) and `M` (1000) to make 400 and 900.

Given an integer, convert it to a roman numeral. Input is guaranteed to be within the range from 1 to 3999.

## 解题方案

**- 时间复杂度: O(N)**- 空间复杂度: O(1)**

# 13. Roman to Integer

## 刷题内容

Roman numerals are represented by seven different symbols: `I`, `V`, `X`, `L`, `C`, `D` and `M`.

For example, two is written as `II` in Roman numeral, just two one’s added together. Twelve is written as, `XII`, which is simply `X` + `II`. The number twenty seven is written as `XXVII`, which is `XX` + `V` + `II`.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not `IIII`. Instead, the number four is written as `IV`. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as `IX`. There are six instances where subtraction is used:

• `I` can be placed before `V` (5) and `X` (10) to make 4 and 9.
• `X` can be placed before `L` (50) and `C` (100) to make 40 and 90.
• `C` can be placed before `D` (500) and `M` (1000) to make 400 and 900.

Given a roman numeral, convert it to an integer. Input is guaranteed to be within the range from `1` to `3999`.

## 解题方案

**- 时间复杂度: O(N)**- 空间复杂度: O(1)**

# 014. Longest Common Prefix

## 刷题内容

Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string `""`.

#### Example 2:

##### Note:

All given inputs are in lowercase letters `a-z`.

## 解题方案

**- 时间复杂度: O(N)**- 空间复杂度: O(N)**

# 015. 3Sum

## 刷题内容

Given an array nums of n integers, are there elements a, b, c in nums 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.
``````

#### Example:

`````` Given array nums = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]
``````

## 解题方案

**- 时间复杂度: O(N²)**- 空间复杂度: O(N)**

# 016. 3Sum Closest

## 刷题内容

Given an array `nums` of n integers and an integer `target`, find three integers in `nums` such that the sum is closest to `target`. Return the sum of the three integers. You may assume that each input would have exactly one solution.

#### Example:

`````` Given array nums = [-1, 2, 1, -4], and target = 1.

The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
``````

## 解题方案

**- 时间复杂度: O(N²)**- 空间复杂度: O(N)**

# 017. Letter Combinations of a Phone Number

## 刷题内容

Given a string containing digits from `2-9` inclusive, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

#### Example:

`````` Input: "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

``````

#### Note:

Although the above answer is in lexicographical order, your answer could be in any order you want.

## 解题方案

**- 时间复杂度: O(N²)**- 空间复杂度: O(N)**

**- 时间复杂度: O(N²)**- 空间复杂度: O(N)**