### leetcode_recode

main programming language: C++

#### 1. Two Sum

Easy

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

1. 我们可以建立一个 unorded_map 来存储数组里面每个值以及它所对应的位置关系。

2. 我们用 other_num = target - nums[i]。然后如果不是重复元素，就去找是否存在，如果存在就直接压入 vector。如果是重复元素，就遍历整个 vector 来找到位置，返回。

mySolution:

Medium

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example:

1. 这题是一个链表的形式的加法题
2. 整体就是一个加法进位，一个加法余位，两个位置分别保存。这题主要是长度的分类，我自己的思路就是对于较长的链表遍历完才结束遍历。对于短的链表就不停的加值为 0 的结点。

mySolution:

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

1. 这题是一个最长字符子串的问题。我个人想法使用一个字典来记录某字符出现次数。
2. 我们用 i、j 指向头部，不断增加 j 的大小，不断增加字典中字符的次数，如果出现某一个字符串出现次数大于两次，就不断移动 i 直到没有重复字符串为止。最后 maxlen 不停更新为最大的值。

mySolution:

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

1. 这题我个人的思路是非常蠢的。。。先合并，在排序，在去取值
2. 我在写这个文档的时候，也是不知道当时做这题是怎么想的。为什么用这种奇怪的方法，复杂度还高。
3. ！去看一下 find_k 算法

mySolution:

#### 5. Longest Palindromic Substring

Medium

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:

Example 2:

1. 这题我自己的做法，也是非常传统的想法实现，没有任何编程方面的技巧，就是硬想出来的

2. 设置边界，需要找到相关的边界，来进行记录。首先跳过中间相同的字符，因为这个不影响是不是回文字符串

3. 然后利用回文字符串的规则，进行比较，如果符合，就接着遍历。同时记录相关的位置信息

4. 最后利用 substring 返回子字符串

mySolution:

#### 6. ZigZag Conversion

Medium

The string `"PAYPALISHIRING"` is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

And then read line by line: `"PAHNAPLSIIGYIR"`

Write the code that will take a string and make this conversion given a number of rows:

Example 1:

Example 2:

1. 感觉自己在前期做题的时候，确实没有想任何相关的编程技巧。都是自己想逻辑，然后自己把实现了。
2. 这个自己的思路，就是申请一个 vector 来按一定的规则来存放传入的 s，因为我们看 Explanation 可以发现，这就是一种存储规则
3. 存储完后，在用 for-each 循环再传入到一个result就可以了。

mySolution:

#### 7. Reverse Integer

Easy

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

Example 1:

Example 2:

Example 3:

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.

1. 感觉自己也是挺赖的，用了 to_string 转字符串，然后还用了 stoi 转会 int。可能第一遍刷的时候确实只是在解决问题，却不是最好的解决问题。
2. 这题也就是简单的情况判断。大于 0 以及 小于 0 的情况，末尾几位为 0 的情况，最后如果溢出如何操作。

mySolution:

#### 8. String to Integer (atoi)

Medium

Implement `atoi` which converts a string to an integer.

The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value.

The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.

If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.

If no valid conversion could be performed, a zero value is returned.

Note:

• Only the space character `' '` is considered as whitespace character.
• Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−231, 231 − 1]. If the numerical value is out of the range of representable values, INT_MAX (231 − 1) or INT_MIN (−231) is returned.

Example 1:

Example 2:

Example 3:

Example 4:

Example 5:

1. 依然是自己硬想的逻辑，真的是太菜了。。。
2. 这个题目也是不断的逻辑处理。先是删除掉前面的所有空格。分正负情况，将数字提取出来，然后判断有没有溢出，就完成了。

mySolution:

#### 9. Palindrome Number

Easy

Determine whether an integer is a palindrome. An integer is a palindrome when it reads the same backward as forward.

Example 1:

Example 2:

Example 3:

Coud you solve it without converting the integer to a string?

1. 虽然题目说不要使用 integer to a string，但是那样自己想的办法也就是取出每一位，然后重新构造一个数，看是否相等。
2. 我这里直接也就直接转 string 然后 reverse 判断是否相等。

mySolution:

#### 10. Regular Expression Matching

Hard

Given an input string (`s`) and a pattern (`p`), implement regular expression matching with support for `'.'` and `'*'`.

The matching should cover the entire input string (not partial).

Note:

• `s` could be empty and contains only lowercase letters `a-z`.
• `p` could be empty and contains only lowercase letters `a-z`, and characters like `.` or `*`.

Example 1:

Example 2:

Example 3:

Example 4:

Example 5:

1. 这题我个人觉得也是非常好，刚开始结合自己刚刚学习编译原理的原因，想弄个递归下降子程序，以及弹栈的思想。后来发现 * 不是很好处理，所以干脆直接递归处理，这也算是动态规划了吧。
2. 首先将一些能直接返回的情况，判断完。然后就涉及到一些需要进一步判断的情况。
3. 正常的字母匹配都不是关键的地方，这题的难度在于 .* 以及 [a-z]* 的 处理。
4. 对于 [a-z]* 。因为 * 可以不匹配，所以我们还要判断不匹配的情况，是否能成功。这里直接使用递归，然后如果不匹配不成功的话，然后我们就需要接着判断到底匹配几个，这里又需要我们写循环，再循环里我们需要递归判断。成功的话，直接返回就好了。
5. 对于 .* 。同样也是要判断表示是否匹配，以及匹配几个的问题。所以同样是递归来进行判断。

mySolution:

#### 11. Container With Most Water

Medium

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. The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.

Example:

1. 这题就是一个数学题吧，整体思路也比较清晰。
2. 首先从头尾开始往中间进行遍历，因为宽度一直在减小，如果高度还减小，肯定是没有前种情况大的。所以我们一直遍历到，高度比前面大的情况。可以大大减少时间复杂度。

mySolution:

#### 12. Integer to Roman

Medium

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.

Example 1:

Example 2:

Example 3:

Example 4:

Example 5:

1. 同样是正常的分类逻辑，完成逻辑即可

mySolution:

#### 13. Roman to Integer

Easy

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.

Example 1:

Example 2:

Example 3:

Example 4:

Example 5:

1. 用两个 vector 来存储相关的字符与数字的对应关系。
2. 我们整体逻辑就是取位置的差距，然后去另一个 vector 找对应的值。当然要判断是不是特殊情况，整体逻辑也不是很难。

mySolution:

#### 14. Longest Common Prefix

Easy

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 1:

Example 2:

Note:

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

1. 首先取所有字符串的最短长度

2. 然后我们从 0 开始遍历，直到找到不是公共子串的长度。

mySolution:

#### 15. 3Sum

Medium

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:

1. 这题我们需要将数组进行排序来减小时间复杂度
2. 然后我们固定一个位置，将整个问题变成一个子问题。子问题就是在子数组里面找到对应的和为要求值的位置。然后不断增加 i 即可。

mySolution:

#### 16. 3Sum Closest

Medium

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:

1. 整体思路同样类似于上面那题

mySolution:

#### 17. Letter Combinations of a Phone Number

Medium

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:

1. 这题主要就是如何完成笛卡尔积，当然 python 很好完成
2. 在 c++ 中笛卡尔积可以用递归，或者我这种方法。就是将大小提取出来，然后写循环。

mySolution

#### 18. 4Sum

Medium

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

Example:

1. 我个人的想法就是将其转换成子问题
2. 子问题就是 3sum，然后就可以完成了。

mySolution:

#### 19. Remove Nth Node From End of List

Medium

Given a linked list, remove the n-th node from the end of list and return its head.

Example:

Note:

Given n will always be valid.

Could you do this in one pass?

1. 比较正常的链表题

mySolution:

#### 20. Valid Parentheses

Easy

Given a string containing just the characters `'('`, `')'`, `'{'`, `'}'`, `'['` and `']'`, determine if the input string is valid.

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.

Note that an empty string is also considered valid.

Example 1:

Example 2:

Example 3:

Example 4:

Example 5:

1. 如果学习过编译原理，很好理解，利用栈的语法判断

mySolution:

#### 21. Merge Two Sorted Lists

Easy

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

Example:

1. 常规的链表题

mySolution:

#### 22. Generate Parentheses

Medium

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

1. 我们确立是递归类型的问题
2. 我们寻找递归的规律，我们发现整体思路，就是要想是合法的就得一直确保插入过程当中剩下的左括号的数量不能多于右括号（想不明白，可以自己仔细思考一下），所以就写出了以下程序。

mySolution:

#### 28. Implement strStr()

Easy

Implement strStr().

Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Example 1:

Example 2:

Clarification:

What should we return when `needle` is an empty string? This is a great question to ask during an interview.

For the purpose of this problem, we will return 0 when `needle` is an empty string. This is consistent to C’s strstr() and Java’s indexOf().

1. 模拟strstr() 函数
2. 我个人的想法可能就是寻找第一个字符匹配的位置，匹配后面。
3. !KMP算法

mySolution: