0001-0100-Easy
1.两数之和(3)
给定一个整数数组 nums 和一个目标值 target，
请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
示例:给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
暴力法: 2层循环遍历 |
O(n^2) |
O(1) |
| 02 |
两遍哈希遍历 |
O(n) |
O(n) |
| 03(最优) |
一遍哈希遍历 |
O(n) |
O(n) |
# 暴力法: 2层循环遍历
func twoSum(nums []int, target int) []int {
for i := 0; i < len(nums); i++ {
for j := i + 1; j < len(nums); j++ {
if nums[i]+nums[j] == target {
return []int{i, j}
}
}
}
return []int{}
}
# 两遍哈希遍历
func twoSum(nums []int, target int) []int {
m := make(map[int]int,len(nums))
for k, v := range nums{
m[v] = k
}
for i := 0; i < len(nums); i++{
b := target - nums[i]
if num, ok := m[b]; ok && num != i{
return []int{i,m[b]}
}
}
return []int{}
}
# 一遍哈希遍历
func twoSum(nums []int, target int) []int {
m := make(map[int]int, len(nums))
for i, b := range nums {
if j, ok := m[target-b]; ok {
return []int{j, i}
}
m[b] = i
}
return nil
}
7.整数反转(2)
给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。
示例 1:输入: 123 输出: 321
示例 2:输入: -123 输出: -321
示例 3:输入: 120 输出: 21
注意:假设我们的环境只能存储得下 32 位的有符号整数，则其数值范围为 [−2^31, 2^31 − 1]。
请根据这个假设，如果反转后整数溢出那么就返回 0。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
使用符号标记，转成正数，循环得到%10的余数，再加上符号 |
O(log(x)) |
O(1) |
| 02(最优) |
对x进行逐个%10取个位，一旦溢出，直接跳出循环 |
O(log(x)) |
O(1) |
func reverse(x int) int {
flag := 1
if x < 0 {
flag = -1
x = -1 * x
}
result := 0
for x > 0 {
temp := x % 10
x = x / 10
result = result*10 + temp
}
result = flag * result
if result > math.MaxInt32 || result < math.MinInt32 {
result = 0
}
return result
}
func reverse(x int) int {
result := 0
for x != 0 {
temp := x % 10
result = result*10 + temp
if result > math.MaxInt32 || result < math.MinInt32 {
return 0
}
x = x / 10
}
return result
}
9.回文数(3)
判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
示例 1: 输入: 121 输出: true
示例 2:输入: -121 输出: false
解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。
示例 3:输入: 10 输出: false
解释: 从右向左读, 为 01 。因此它不是一个回文数。
进阶: 你能不将整数转为字符串来解决这个问题吗？
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01(最优) |
数学解法，取出后半段数字进行翻转，然后判断是否相等 |
O(log(x)) |
O(1) |
| 02 |
转成字符串，依次判断 |
O(log(x)) |
O(log(x)) |
| 03 |
转成byte数组，依次判断，同2 |
O(log(x)) |
O(log(x)) |
func isPalindrome(x int) bool {
if x < 0 || (x%10 == 0 && x != 0) {
return false
}
revertedNumber := 0
for x > revertedNumber {
temp := x % 10
revertedNumber = revertedNumber*10 + temp
x = x / 10
}
return x == revertedNumber || x == revertedNumber/10
}
func isPalindrome(x int) bool {
if x < 0 {
return false
}
s := strconv.Itoa(x)
for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
if s[i] != s[j] {
return false
}
}
return true
}
func isPalindrome(x int) bool {
if x < 0 {
return false
}
arrs := []byte(strconv.Itoa(x))
Len := len(arrs)
for i := 0; i < Len/2; i++ {
if arrs[i] != arrs[Len-i-1] {
return false
}
}
return true
}
13.罗马数字转整数(2)
罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。
字符 数值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。
27 写做 XXVII, 即为 XX + V + II 。
通常情况下，罗马数字中小的数字在大的数字的右边。
但也存在特例，例如 4 不写做 IIII，而是 IV。
数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。
同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：
I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。
给定一个罗马数字，将其转换成整数。输入确保在 1 到 3999 的范围内。
示例 1:输入: "III" 输出: 3
示例 2: 输入: "IV" 输出: 4
示例 3: 输入: "IX" 输出: 9
示例 4: 输入: "LVIII" 输出: 58 解释: L = 50, V= 5, III = 3.
示例 5: 输入: "MCMXCIV" 输出: 1994 解释: M = 1000, CM = 900, XC = 90, IV = 4.
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
本质上其实就是全部累加，然后遇到特殊的就做判断。使用一个字段记录递增 |
O(n) |
O(1) |
| 02(最优) |
从右到左遍历字符串，如果当前字符代表的值不小于其右边，就加上该值；否则就减去该值。 |
O(n) |
O(1) |
func romanToInt(s string) int {
m := map[byte]int{
'I': 1,
'V': 5,
'X': 10,
'L': 50,
'C': 100,
'D': 500,
'M': 1000,
}
result := 0
last := 0
for i := len(s) - 1; i >= 0; i-- {
current := m[s[i]]
flag := 1
if current < last {
flag = -1
}
result = result + flag*current
last = current
}
return result
}
func romanToInt(s string) int {
m := map[byte]int{
'I': 1,
'V': 5,
'X': 10,
'L': 50,
'C': 100,
'D': 500,
'M': 1000,
}
result := 0
last := 0
for i := len(s) - 1; i >= 0; i-- {
current := m[s[i]]
if current < last {
result = result - current
}else {
result = result + current
}
last = current
}
return result
}
14.最长公共前缀(6)
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。
示例 1:输入: ["flower","flow","flight"] 输出: "fl"
示例 2:输入: ["dog","racecar","car"] 输出: ""
解释: 输入不存在公共前缀。
说明: 所有输入只包含小写字母 a-z 。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
先找最短的一个字符串，依次比较最短字符串子串是否是其他字符串子串 |
O(n^2)/O(n*m) |
O(1) |
| 02 |
纵向扫描(暴力法):直接取第一个字符串作为最长公共前缀，将其每个字符遍历过一次 |
O(n^2)/O(n*m) |
O(1) |
| 03(最优) |
排序后，然后计算第一个，和最后一个字符串的最长前缀 |
O(nlog(n)) |
O(1) |
| 04 |
trie树 |
O(n^2) |
O(n^2) |
| 05 |
水平扫描法:比较前2个字符串得到最长前缀，然后跟第3个比较得到一个新的最长前缀，继续比较，直到最后 |
O(n^2)/O(n*m) |
O(1) |
| 06 |
分治法 |
O(n^2) |
O(1) |
func longestCommonPrefix(strs []string) string {
if len(strs) == 0{
return ""
}
if len(strs) == 1{
return strs[0]
}
short := strs[0]
for _, s := range strs{
if len(short) > len(s){
short = s
}
}
for i := range short{
shortest := short[:i+1]
for _,str := range strs{
if strings.Index(str,shortest) != 0{
return short[:i]
}
}
}
return short
}
func longestCommonPrefix(strs []string) string {
if len(strs) == 0 {
return ""
}
if len(strs) == 1 {
return strs[0]
}
length := 0
for i := 0; i < len(strs[0]); i++ {
char := strs[0][i]
for j := 1; j < len(strs); j++ {
if i >= len(strs[j]) || char != strs[j][i] {
return strs[0][:length]
}
}
length++
}
return strs[0][:length]
}
func longestCommonPrefix(strs []string) string {
if len(strs) == 0{
return ""
}
if len(strs) == 1{
return strs[0]
}
sort.Strings(strs)
first := strs[0]
last := strs[len(strs)-1]
i := 0
length := len(first)
if len(last) < length{
length = len(last)
}
for i < length{
if first[i] != last[i]{
return first[:i]
}
i++
}
return first[:i]
}
var trie [][]int
var index int
func longestCommonPrefix(strs []string) string {
if len(strs) == 0 {
return ""
}
if len(strs) == 1 {
return strs[0]
}
trie = make([][]int, 2000)
for k := range trie {
value := make([]int, 26)
trie[k] = value
}
insert(strs[0])
minValue := math.MaxInt32
for i := 1; i < len(strs); i++ {
retValue := insert(strs[i])
if minValue > retValue {
minValue = retValue
}
}
return strs[0][:minValue]
}
func insert(str string) int {
p := 0
count := 0
for i := 0; i < len(str); i++ {
ch := str[i] - 'a'
if value := trie[p][ch]; value == 0 {
index++
trie[p][ch] = index
} else {
count++
}
p = trie[p][ch]
}
return count
}
func longestCommonPrefix(strs []string) string {
if len(strs) == 0 {
return ""
}
if len(strs) == 1 {
return strs[0]
}
commonStr := common(strs[0], strs[1])
if commonStr == "" {
return ""
}
for i := 2; i < len(strs); i++ {
if commonStr == "" {
return ""
}
commonStr = common(commonStr, strs[i])
}
return commonStr
}
func common(str1, str2 string) string {
length := 0
for i := 0; i < len(str1); i++ {
char := str1[i]
if i >= len(str2) || char != str2[i] {
return str1[:length]
}
length++
}
return str1[:length]
}
func longestCommonPrefix(strs []string) string {
if len(strs) == 0 {
return ""
}
if len(strs) == 1 {
return strs[0]
}
return commonPrefix(strs, 0, len(strs)-1)
}
func commonPrefix(strs []string, left, right int) string {
if left == right {
return strs[left]
}
middle := (left + right) / 2
leftStr := commonPrefix(strs, left, middle)
rightStr := commonPrefix(strs, middle+1, right)
return commonPrefixWord(leftStr, rightStr)
}
func commonPrefixWord(leftStr, rightStr string) string {
if len(leftStr) > len(rightStr) {
leftStr = leftStr[:len(rightStr)]
}
if len(leftStr) < 1 {
return leftStr
}
for i := 0; i < len(leftStr); i++ {
if leftStr[i] != rightStr[i] {
return leftStr[:i]
}
}
return leftStr
}
20.有效的括号(3)
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
示例 1: 输入: "()" 输出: true
示例 2: 输入: "()[]{}" 输出: true
示例 3: 输入: "(]" 输出: false
示例 4: 输入: "([)]" 输出: false
示例 5: 输入: "{[]}" 输出: true
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
使用栈结构实现栈 |
O(n) |
O(n) |
| 02 |
借助数组实现栈 |
O(n) |
O(n) |
| 03 |
借助数组实现栈，使用数字表示来匹配 |
O(n) |
O(n) |
func isValid(s string) bool {
st := new(stack)
for _, char := range s {
switch char {
case '(', '[', '{':
st.push(char)
case ')', ']', '}':
ret, ok := st.pop()
if !ok || ret != match[char] {
return false
}
}
}
if len(*st) > 0 {
return false
}
return true
}
var match = map[rune]rune{
')': '(',
']': '[',
'}': '{',
}
type stack []rune
func (s *stack) push(b rune) {
*s = append(*s, b)
}
func (s *stack) pop() (rune, bool) {
if len(*s) > 0 {
res := (*s)[len(*s)-1]
*s = (*s)[:len(*s)-1]
return res, true
}
return 0, false
}
func isValid(s string) bool {
if s == "" {
return true
}
stack := make([]rune, len(s))
length := 0
var match = map[rune]rune{
')': '(',
']': '[',
'}': '{',
}
for _, char := range s {
switch char {
case '(', '[', '{':
stack[length] = char
length++
case ')', ']', '}':
if length == 0 {
return false
}
if stack[length-1] != match[char]{
return false
} else {
length--
}
}
}
return length == 0
}
func isValid(s string) bool {
if s == "" {
return true
}
stack := make([]int, len(s))
length := 0
var match = map[rune]int{
')': 1,
'(': -1,
']': 2,
'[': -2,
'}': 3,
'{': -3,
}
for _, char := range s {
switch char {
case '(', '[', '{':
stack[length] = match[char]
length++
case ')', ']', '}':
if length == 0 {
return false
}
if stack[length-1]+match[char] != 0 {
return false
} else {
length--
}
}
}
return length == 0
}
21.合并两个有序链表(3)
将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例：输入：1->2->4, 1->3->4 输出：1->1->2->3->4->4
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01(最优) |
迭代遍历 |
O(n) |
O(1) |
| 02 |
递归实现 |
O(n) |
O(n) |
| 03 |
迭代 |
O(n) |
O(1) |
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
if l1 == nil {
return l2
}
if l2 == nil {
return l1
}
var head, node *ListNode
if l1.Val < l2.Val {
head = l1
node = l1
l1 = l1.Next
} else {
head = l2
node = l2
l2 = l2.Next
}
for l1 != nil && l2 != nil {
if l1.Val < l2.Val {
node.Next = l1
l1 = l1.Next
} else {
node.Next = l2
l2 = l2.Next
}
node = node.Next
}
if l1 != nil {
node.Next = l1
}
if l2 != nil {
node.Next = l2
}
return head
}
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
if l1 == nil {
return l2
}
if l2 == nil {
return l1
}
if l1.Val < l2.Val{
l1.Next = mergeTwoLists(l1.Next,l2)
return l1
}else {
l2.Next = mergeTwoLists(l1,l2.Next)
return l2
}
}
#
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
res := &ListNode{}
temp := res
for l1 != nil && l2 != nil {
if l1.Val < l2.Val {
temp.Next = l1
l1 = l1.Next
} else {
temp.Next = l2
l2 = l2.Next
}
temp = temp.Next
}
if l1 != nil {
temp.Next = l1
} else {
temp.Next = l2
}
return res.Next
}
26.删除排序数组中的重复项(2)
给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。
不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
示例 1: 给定数组 nums = [1,1,2],
函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。
你不需要考虑数组中超出新长度后面的元素。
示例 2: 给定 nums = [0,0,1,1,1,2,2,3,3,4],
函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。
你不需要考虑数组中超出新长度后面的元素。
说明: 为什么返回数值是整数，但输出的答案是数组呢?
请注意，输入数组是以“引用”方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。
你可以想象内部操作如下:
// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
int len = removeDuplicates(nums);
// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。
for (int i = 0; i < len; i++) {
print(nums[i]);
}
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
双指针法 |
O(n) |
O(1) |
| 02(最优) |
计数法 |
O(n) |
O(1) |
func removeDuplicates(nums []int) int {
i , j , length := 0, 1, len(nums)
for ; j < length; j++{
if nums[i] == nums[j]{
continue
}
i++
nums[i] = nums[j]
}
return i+1
}
func removeDuplicates(nums []int) int {
count := 1
for i := 0; i < len(nums)-1; i++ {
if nums[i] != nums[i+1] {
nums[count] = nums[i+1]
count++
}
}
return count
}
27.移除元素(3)
给定一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，返回移除后数组的新长度。
不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
示例 1: 给定 nums = [3,2,2,3], val = 3,
函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。
你不需要考虑数组中超出新长度后面的元素。
示例 2: 给定 nums = [0,1,2,2,3,0,4,2], val = 2,
函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。
注意这五个元素可为任意顺序。
你不需要考虑数组中超出新长度后面的元素。
说明: 为什么返回数值是整数，但输出的答案是数组呢?
请注意，输入数组是以“引用”方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。
你可以想象内部操作如下:
// nums 是以“引用”方式传递的。也就是说，不对实参作任何拷贝
int len = removeElement(nums, val);
// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。
for (int i = 0; i < len; i++) {
print(nums[i]);
}
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01(最优) |
双指针，数字前移 |
O(n) |
O(1) |
| 02 |
双指针，出现重复最后数字前移 |
O(n) |
O(1) |
| 03 |
首位指针法 |
O(n) |
O(1) |
func removeElement(nums []int, val int) int {
i := 0
for j := 0; j < len(nums); j++{
if nums[j] != val{
nums[i] = nums[j]
i++
}
}
return i
}
func removeElement(nums []int, val int) int {
i := 0
n := len(nums)
for i < n{
if nums[i] == val{
nums[i] = nums[n-1]
n--
}else {
i++
}
}
return n
}
func removeElement(nums []int, val int) int {
i, j := 0, len(nums)-1
for {
for i < len(nums) && nums[i] != val {
i++
}
for j >= 0 && nums[j] == val {
j--
}
if i >= j {
break
}
nums[i], nums[j] = nums[j], nums[i]
}
return i
}
28.实现strStr()(4)
实现 strStr() 函数。
给定一个 haystack 字符串和一个 needle 字符串，
在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。
如果不存在，则返回-1。
示例 1:输入: haystack = "hello", needle = "ll" 输出: 2
示例 2: 输入: haystack = "aaaaa", needle = "bba" 输出: -1
说明: 当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。
对于本题而言，当 needle 是空字符串时我们应当返回 0 。
这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01(最优) |
Sunday算法 |
O(n) |
O(1) |
| 02 |
直接匹配 |
O(n) |
O(1) |
| 03 |
系统函数 |
O(n) |
O(1) |
| 04 |
kmp算法 |
O(n) |
O(n) |
func strStr(haystack string, needle string) int {
if needle == ""{
return 0
}
if len(needle) > len(haystack){
return -1
}
m := make(map[int32]int)
for k,v := range needle{
m[v] = len(needle)-k
}
index := 0
for index+len(needle) <= len(haystack){
str := haystack[index:index+len(needle)]
if str == needle{
return index
}else {
if index + len(needle) >= len(haystack){
return -1
}
next := haystack[index+len(needle)]
if nextStep,ok := m[int32(next)];ok{
index = index+nextStep
}else {
index = index+len(needle)+1
}
}
}
if index + len(needle) >= len(haystack){
return -1
}else {
return index
}
}
func strStr(haystack string, needle string) int {
hlen, nlen := len(haystack), len(needle)
for i := 0; i <= hlen-nlen; i++ {
if haystack[i:i+nlen] == needle {
return i
}
}
return -1
}
func strStr(haystack string, needle string) int {
return strings.Index(haystack, needle)
}
func strStr(haystack string, needle string) int {
if len(needle) == 0 {
return 0
}
next := getNext(needle)
i := 0
j := 0
for i < len(haystack) && j < len(needle) {
if j == -1 || haystack[i] == needle[j] {
i++
j++
} else {
j = next[j]
}
}
if j == len(needle) {
return i - j
}
return -1
}
func getNext(str string) []int {
var next = make([]int, len(str))
next[0] = -1
i := 0
j := -1
for i < len(str)-1 {
if j == -1 || str[i] == str[j] {
i++
j++
next[i] = j
} else {
j = next[j]
}
}
return next
}
35.搜索插入位置(3)
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。
如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。
示例 1: 输入: [1,3,5,6], 5 输出: 2
示例 2: 输入: [1,3,5,6], 2 输出: 1
示例 3: 输入: [1,3,5,6], 7 输出: 4
示例 4: 输入: [1,3,5,6], 0 输出: 0
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01(最优) |
二分查找 |
O(log(n)) |
O(1) |
| 02 |
顺序查找 |
O(n) |
O(1) |
| 03 |
顺序查找 |
O(n) |
O(1) |
func searchInsert(nums []int, target int) int {
low, high := 0, len(nums)-1
for low <= high {
mid := (low + high) / 2
switch {
case nums[mid] < target:
low = mid + 1
case nums[mid] > target:
high = mid - 1
default:
return mid
}
}
return low
}
func searchInsert(nums []int, target int) int {
i := 0
for i < len(nums) && nums[i] < target {
if nums[i] == target {
return i
}
i++
}
return i
}
func searchInsert(nums []int, target int) int {
for i := 0; i < len(nums); i++ {
if nums[i] >= target {
return i
}
}
return len(nums)
}
38.报数(2)
报数序列是一个整数序列，按照其中的整数的顺序进行报数，得到下一个数。其前五项如下：
1. 1
2. 11
3. 21
4. 1211
5. 111221
1 被读作 "one 1" ("一个一") , 即 11。
11 被读作 "two 1s" ("两个一"）, 即 21。
21 被读作 "one 2", "one 1" （"一个二" , "一个一") , 即 1211。
给定一个正整数 n（1 ≤ n ≤ 30），输出报数序列的第 n 项。
注意：整数顺序将表示为一个字符串。
示例 1:输入: 1 输出: "1"
示例 2: 输入: 4 输出: "1211"
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 (最优) |
递推+双指针计数 |
O(n^2) |
O(1) |
| 02 |
递归+双指针计数 |
O(n^2) |
O(n) |
func countAndSay(n int) string {
strs := []byte{'1'}
for i := 1; i < n; i++ {
strs = say(strs)
}
return string(strs)
}
func say(strs []byte) []byte {
result := make([]byte, 0, len(strs)*2)
i, j := 0, 1
for i < len(strs) {
for j < len(strs) && strs[i] == strs[j] {
j++
}
result = append(result, byte(j-i+'0'))
result = append(result, strs[i])
i = j
}
return result
}
func countAndSay(n int) string {
if n == 1 {
return "1"
}
strs := countAndSay(n - 1)
result := make([]byte, 0, len(strs)*2)
i, j := 0, 1
for i < len(strs) {
for j < len(strs) && strs[i] == strs[j] {
j++
}
result = append(result, byte(j-i+'0'))
result = append(result, strs[i])
i = j
}
return string(result)
}
53.最大子序和(5)
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例: 输入: [-2,1,-3,4,-1,2,1,-5,4], 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
进阶: 如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01(最优) |
贪心法 |
O(n) |
O(1) |
| 02 |
暴力法 |
O(n^2) |
O(1) |
| 03 |
动态规划 |
O(n) |
O(n) |
| 04 |
动态规划 |
O(n) |
O(1) |
| 05 |
分治 |
O(nlog(n)) |
O(log(n)) |
func maxSubArray(nums []int) int {
result := nums[0]
sum := 0
for i := 0; i < len(nums); i++ {
if sum > 0 {
sum += nums[i]
} else {
sum = nums[i]
}
if sum > result {
result = sum
}
}
return result
}
func maxSubArray(nums []int) int {
result := math.MinInt32
for i := 0; i < len(nums); i++ {
sum := 0
for j := i; j < len(nums); j++ {
sum += nums[j]
if sum > result {
result = sum
}
}
}
return result
}
func maxSubArray(nums []int) int {
dp := make([]int, len(nums))
dp[0] = nums[0]
result := nums[0]
for i := 1; i < len(nums); i++ {
if dp[i-1]+nums[i] > nums[i] {
dp[i] = dp[i-1] + nums[i]
} else {
dp[i] = nums[i]
}
if dp[i] > result {
result = dp[i]
}
}
return result
}
func maxSubArray(nums []int) int {
dp := nums[0]
result := dp
for i := 1; i < len(nums); i++ {
if dp+nums[i] > nums[i] {
dp = dp + nums[i]
} else {
dp = nums[i]
}
if dp > result {
result = dp
}
}
return result
}
func maxSubArray(nums []int) int {
result := maxSubArr(nums, 0, len(nums)-1)
return result
}
func maxSubArr(nums []int, left, right int) int {
if left == right {
return nums[left]
}
mid := (left + right) / 2
leftSum := maxSubArr(nums, left, mid)
rightSum := maxSubArr(nums, mid+1, right)
midSum := findMaxArr(nums, left, mid, right)
result := max(leftSum, rightSum)
result = max(result, midSum)
return result
}
func findMaxArr(nums []int, left, mid, right int) int {
leftSum := math.MinInt32
sum := 0
for i := mid; i >= left; i-- {
sum += nums[i]
leftSum = max(leftSum, sum)
}
rightSum := math.MinInt32
sum = 0
for i := mid + 1; i <= right; i++ {
sum += nums[i]
rightSum = max(rightSum, sum)
}
return leftSum + rightSum
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
58.最后一个单词的长度(2)
给定一个仅包含大小写字母和空格 ' ' 的字符串，返回其最后一个单词的长度。
如果不存在最后一个单词，请返回 0 。
说明：一个单词是指由字母组成，但不包含任何空格的字符串。
示例: 输入: "Hello World" 输出: 5
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01(最优) |
调用系统函数，切割为数组取最后一个值 |
O(n) |
O(1) |
| 02 |
遍历统计 |
O(n) |
O(1) |
func lengthOfLastWord(s string) int {
arr := strings.Split(strings.Trim(s, " "), " ")
return len(arr[len(arr)-1])
}
func lengthOfLastWord(s string) int {
length := len(s)
if length == 0 {
return 0
}
result := 0
for i := length - 1; i >= 0; i-- {
if s[i] == ' ' {
if result > 0 {
return result
}
continue
}
result++
}
return result
}
66.加一(2)
给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。
最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。
你可以假设除了整数 0 之外，这个整数不会以零开头。
示例 1: 输入: [1,2,3] 输出: [1,2,4] 解释: 输入数组表示数字 123。
示例 2: 输入: [4,3,2,1] 输出: [4,3,2,2] 解释: 输入数组表示数字 4321。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
直接模拟 |
O(n) |
O(1) |
| 02(最优) |
直接模拟 |
O(n) |
O(1) |
func plusOne(digits []int) []int {
length := len(digits)
if length == 0 {
return []int{1}
}
digits[length-1]++
for i := length - 1; i > 0; i-- {
if digits[i] < 10 {
break
}
digits[i] = digits[i] - 10
digits[i-1]++
}
if digits[0] > 9 {
digits[0] = digits[0] - 10
digits = append([]int{1}, digits...)
}
return digits
}
func plusOne(digits []int) []int {
for i := len(digits) - 1; i >= 0; i-- {
if digits[i] < 9 {
digits[i]++
return digits
} else {
digits[i] = 0
}
}
return append([]int{1}, digits...)
}
67.二进制求和(2)
给定两个二进制字符串，返回他们的和（用二进制表示）。
输入为非空字符串且只包含数字 1 和 0。
示例 1: 输入: a = "11", b = "1" 输出: "100"
示例 2:输入: a = "1010", b = "1011" 输出: "10101"
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
数组 |
O(n) |
O(n) |
| 02(最优) |
模拟 |
O(n) |
O(n) |
func addBinary(a string, b string) string {
if len(a) < len(b) {
a, b = b, a
}
length := len(a)
A := transToInt(a, length)
B := transToInt(b, length)
return makeString(add(A, B))
}
func transToInt(s string, length int) []int {
result := make([]int, length)
ls := len(s)
for i, b := range s {
result[length-ls+i] = int(b - '0')
}
return result
}
func add(a, b []int) []int {
length := len(a) + 1
result := make([]int, length)
for i := length - 1; i >= 1; i-- {
temp := result[i] + a[i-1] + b[i-1]
result[i] = temp % 2
result[i-1] = temp / 2
}
i := 0
for i < length-1 && result[i] == 0 {
i++
}
return result[i:]
}
func makeString(nums []int) string {
bytes := make([]byte, len(nums))
for i := range bytes {
bytes[i] = byte(nums[i]) + '0'
}
return string(bytes)
}
func addBinary(a string, b string) string {
i := len(a) - 1
j := len(b) - 1
result := ""
flag := 0
current := 0
for i >= 0 || j >= 0 {
intA, intB := 0, 0
if i >= 0 {
intA = int(a[i] - '0')
}
if j >= 0 {
intB = int(b[j] - '0')
}
current = intA + intB + flag
flag = 0
if current >= 2 {
flag = 1
current = current - 2
}
cur := strconv.Itoa(current)
result = cur + result
i--
j--
}
if flag == 1 {
result = "1" + result
}
return result
}
69.x的平方根 (5)
实现 int sqrt(int x) 函数。
计算并返回 x 的平方根，其中 x 是非负整数。
由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
示例 1:输入: 4 输出: 2
示例 2:输入: 8 输出: 2
说明: 8 的平方根是 2.82842...,
由于返回类型是整数，小数部分将被舍去。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
系统函数 |
O(log(n)) |
O(1) |
| 02 |
系统函数 |
O(log(n)) |
O(1) |
| 03(最优) |
牛顿迭代法 |
O(log(n)) |
O(1) |
| 04 |
二分查找法 |
O(log(n)) |
O(1) |
| 05 |
暴力法:遍历 |
O(n) |
O(1) |
func mySqrt(x int) int {
result := int(math.Sqrt(float64(x)))
return result
}
func mySqrt(x int) int {
result := math.Floor(math.Sqrt(float64(x)))
return int(result)
}
func mySqrt(x int) int {
result := x
for result*result > x {
result = (result + x/result) / 2
}
return result
}
func mySqrt(x int) int {
left := 1
right := x
for left <= right {
mid := (left + right) / 2
if mid == x/mid {
return mid
} else if mid < x/mid {
left = mid + 1
} else {
right = mid - 1
}
}
if left * left <= x{
return left
}else {
return left-1
}
}
func mySqrt(x int) int {
result := 0
for i := 1; i <= x/i; i++ {
if i*i == x {
return i
}
result = i
}
return result
}
70.爬楼梯(3)
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
示例 1： 输入： 2 输出： 2 解释： 有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶
示例 2： 输入： 3 输出： 3 解释： 有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
递归 |
O(n) |
O(n) |
| 02 |
动态规划 |
O(n) |
O(n) |
| 03(最优) |
斐波那契 |
O(n) |
O(1) |
var arr []int
func climbStairs(n int) int {
arr = make([]int, n+1)
return climbStart(0, n)
}
func climbStart(i, n int) int {
if i > n {
return 0
}
if i == n {
return 1
}
if arr[i] > 0 {
return arr[i]
}
arr[i] = climbStart(i+1, n) + climbStart(i+2, n)
return arr[i]
}
func climbStairs(n int) int {
if n == 1 {
return 1
}
if n == 2 {
return 2
}
dp := make([]int, n+1)
dp[1] = 1
dp[2] = 2
for i := 3; i <= n; i++ {
dp[i] = dp[i-1] + dp[i-2]
}
return dp[n]
}
func climbStairs(n int) int {
if n == 1 {
return 1
}
first := 1
second := 2
for i := 3; i <= n; i++ {
third := first + second
first = second
second = third
}
return second
}
83.删除排序链表中的重复元素(3)
给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。
示例 1:输入: 1->1->2 输出: 1->2
示例 2:输入: 1->1->2->3->3 输出: 1->2->3
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01( 最优) |
直接法 |
O(n) |
O(1) |
| 02 |
递归法 |
O(n) |
O(1) |
| 03 |
双指针法 |
O(n) |
O(1) |
func deleteDuplicates(head *ListNode) *ListNode {
if head == nil {
return nil
}
temp := head
for temp.Next != nil {
if temp.Val == temp.Next.Val {
temp.Next = temp.Next.Next
} else {
temp = temp.Next
}
}
return head
}
func deleteDuplicates(head *ListNode) *ListNode {
if head == nil || head.Next == nil{
return head
}
head.Next = deleteDuplicates(head.Next)
if head.Val == head.Next.Val{
head = head.Next
}
return head
}
func deleteDuplicates(head *ListNode) *ListNode {
if head == nil || head.Next == nil{
return head
}
p := head
q := head.Next
for p.Next != nil{
if p.Val == q.Val{
if q.Next == nil{
p.Next = nil
}else {
p.Next = q.Next
q = q.Next
}
}else {
p = p.Next
q = q.Next
}
}
return head
}
88.合并两个有序数组(3)
给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。
说明:
初始化 nums1 和 nums2 的元素数量分别为 m 和 n。
你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。
示例:输入: nums1 = [1,2,3,0,0,0], m = 3 nums2 = [2,5,6], n = 3
输出: [1,2,2,3,5,6]
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
合并后排序 |
O(nlog(n)) |
O(1) |
| 02(最优) |
双指针法 |
O(n) |
O(1) |
| 03 |
拷贝后插入 |
O(n) |
O(n) |
func merge(nums1 []int, m int, nums2 []int, n int) {
nums1 = nums1[:m]
nums1 = append(nums1, nums2[:n]...)
sort.Ints(nums1)
}
func merge(nums1 []int, m int, nums2 []int, n int) {
for m > 0 && n > 0 {
if nums1[m-1] < nums2[n-1] {
nums1[m+n-1] = nums2[n-1]
n--
} else {
nums1[m+n-1] = nums1[m-1]
m--
}
}
if m == 0 && n > 0 {
for n > 0 {
nums1[n-1] = nums2[n-1]
n--
}
}
}
func merge(nums1 []int, m int, nums2 []int, n int) {
temp := make([]int, m)
copy(temp, nums1)
if n == 0 {
return
}
first, second := 0, 0
for i := 0; i < len(nums1); i++ {
if second >= n {
nums1[i] = temp[first]
first++
continue
}
if first >= m {
nums1[i] = nums2[second]
second++
continue
}
if temp[first] < nums2[second] {
nums1[i] = temp[first]
first++
} else {
nums1[i] = nums2[second]
second++
}
}
}
100.相同的树(2)
给定两个二叉树，编写一个函数来检验它们是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
示例 1:
输入: 1 1
/ \ / \
2 3 2 3
[1,2,3], [1,2,3]
输出: true
示例 2:
输入: 1 1
/ \
2 2
[1,2], [1,null,2]
输出: false
示例 3:
输入: 1 1
/ \ / \
2 1 1 2
[1,2,1], [1,1,2]
输出: false
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
递归(深度优先) |
O(n) |
O(log(n)) |
| 02 |
层序遍历(宽度优先) |
O(n) |
O(log(n)) |
func isSameTree(p *TreeNode, q *TreeNode) bool {
if p == nil && q == nil {
return true
}
if p == nil || q == nil {
return false
}
return p.Val == q.Val && isSameTree(p.Left, q.Left) &&
isSameTree(p.Right, q.Right)
}
func isSameTree(p *TreeNode, q *TreeNode) bool {
if p == nil && q == nil {
return true
}
if p == nil || q == nil {
return false
}
var queueP, queueQ []*TreeNode
if p != nil {
queueP = append(queueP, p)
queueQ = append(queueQ, q)
}
for len(queueP) > 0 && len(queueQ) > 0 {
tempP := queueP[0]
queueP = queueP[1:]
tempQ := queueQ[0]
queueQ = queueQ[1:]
if tempP.Val != tempQ.Val {
return false
}
if (tempP.Left != nil && tempQ.Left == nil) ||
(tempP.Left == nil && tempQ.Left != nil) {
return false
}
if tempP.Left != nil {
queueP = append(queueP, tempP.Left)
queueQ = append(queueQ, tempQ.Left)
}
if (tempP.Right != nil && tempQ.Right == nil) ||
(tempP.Right == nil && tempQ.Right != nil) {
return false
}
if tempP.Right != nil {
queueP = append(queueP, tempP.Right)
queueQ = append(queueQ, tempQ.Right)
}
}
return true
}
0001-0100-Medium
2.两数相加(2)
给出两个 非空 的链表用来表示两个非负的整数。
其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例：输入：(2 -> 4 -> 3) + (5 -> 6 -> 4) 输出：7 -> 0 -> 8
原因：342 + 465 = 807
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(n) |
O(n) |
| 02 |
递归 |
O(n) |
O(n) |
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
res := &ListNode{}
cur := res
carry := 0
for l1 != nil || l2 != nil || carry > 0 {
sum := carry
if l1 != nil {
sum += l1.Val
l1 = l1.Next
}
if l2 != nil {
sum += l2.Val
l2 = l2.Next
}
carry = sum / 10
cur.Next = &ListNode{Val: sum % 10}
cur = cur.Next
}
return res.Next
}
#
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
if l1 == nil && l2 == nil {
return nil
}
if l1 == nil {
return l2
}
if l2 == nil {
return l1
}
sum := l1.Val + l2.Val
res := &ListNode{Val: sum % 10}
if sum >= 10 {
l1.Next = addTwoNumbers(l1.Next, &ListNode{Val: 1})
}
res.Next = addTwoNumbers(l1.Next, l2.Next)
return res
}
3.无重复字符的最长子串(4)
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:输入: "abcabcbb"输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:输入: "bbbbb" 输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:输入: "pwwkew" 输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
同剑指offer面试题48.最长不含重复字符的子字符串
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
双指针 |
O(n) |
O(1) |
| 02 |
双指针-内置函数 |
O(n^2) |
O(1) |
| 03 |
哈希辅助-双指针 |
O(n) |
O(1) |
| 04 |
动态规划 |
O(n) |
O(n) |
| 05 |
双指针 |
O(n) |
O(1) |
func lengthOfLongestSubstring(s string) int {
arr := [256]int{}
for i := range arr {
arr[i] = -1
}
max, j := 0, 0
for i := 0; i < len(s); i++ {
if arr[s[i]] >= j {
j = arr[s[i]] + 1
} else if i+1-j > max {
max = i + 1 - j
}
arr[s[i]] = i
}
return max
}
# 2
func lengthOfLongestSubstring(s string) int {
max, j := 0, 0
for i := 0; i < len(s); i++ {
index := strings.Index(s[j:i], string(s[i]))
if index == -1 {
continue
}
if i-j > max {
max = i - j
}
j = j + index + 1
}
if len(s)-j > max {
max = len(s) - j
}
return max
}
# 3
func lengthOfLongestSubstring(s string) int {
m := make(map[uint8]int)
max, j := 0, 0
for i := 0; i < len(s); i++ {
if v, ok := m[s[i]]; ok && v >= j {
j = v + 1
} else if i+1-j > max {
max = i + 1 - j
}
m[s[i]] = i
}
return max
}
# 4
func lengthOfLongestSubstring(s string) int {
if len(s) < 1 {
return 0
}
dp := make([]int, len(s))
dp[0] = 1
res := 1
m := make(map[byte]int)
m[s[0]] = 0
for i := 1; i < len(s); i++ {
index := -1
if value, ok := m[s[i]]; ok {
index = value
}
if i-index > dp[i-1] {
dp[i] = dp[i-1] + 1
} else {
dp[i] = i - index
}
m[s[i]] = i
if dp[i] > res {
res = dp[i]
}
}
return res
}
# 5
func lengthOfLongestSubstring(s string) int {
arr := [256]int{}
for i := range arr {
arr[i] = -1
}
res, j := 0, -1
for i := 0; i < len(s); i++ {
if arr[s[i]] > j {
j = arr[s[i]]
} else {
res = max(res, i-j)
}
arr[s[i]] = i
}
return res
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
5.最长回文子串(5)
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1：输入: "babad"输出: "bab" 注意: "aba" 也是一个有效答案。
示例 2：输入: "cbbd" 输出: "bb"
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
动态规划 |
O(n^2) |
O(n^2) |
| 02 |
中心扩展 |
O(n^2) |
O(1) |
| 03 |
暴力法 |
O(n^3) |
O(1) |
| 04 |
Manacher算法 |
O(n^2) |
O(n) |
| 05 |
Manacher算法 |
O(n) |
O(n) |
func longestPalindrome(s string) string {
if len(s) <= 1 {
return s
}
dp := make([][]bool, len(s))
start := 0
max := 1
for r := 0; r < len(s); r++ {
dp[r] = make([]bool, len(s))
dp[r][r] = true
for l := 0; l < r; l++ {
if s[l] == s[r] && (r-l <= 2 || dp[l+1][r-1] == true) {
dp[l][r] = true
} else {
dp[l][r] = false
}
if dp[l][r] == true {
if r-l+1 > max {
max = r - l + 1
start = l
}
}
}
}
return s[start : start+max]
}
# 2
func longestPalindrome(s string) string {
if len(s) <= 1 {
return s
}
start := 0
end := 0
for i := 0; i < len(s); i++ {
left1, right1 := find(s, i, i)
left2, right2 := find(s, i, i+1)
if right1-left1 > end-start {
start, end = left1, right1
}
if right2-left2 > end-start {
start, end = left2, right2
}
}
return s[start : end+1]
}
func find(s string, left, right int) (int, int) {
for ; 0 <= left && right < len(s) && s[left] == s[right]; left, right = left-1, right+1 {
}
return left + 1, right - 1
}
# 3
func longestPalindrome(s string) string {
if len(s) <= 1 {
return s
}
res := ""
for i := 0; i < len(s); i++ {
for j := i; j < len(s); j++ {
str := s[i : j+1]
if len(str) < len(res) && res != "" {
continue
}
if judge(str) == true && len(res) < len(str) {
res = str
}
}
}
return res
}
func judge(s string) bool {
for i := 0; i < len(s)/2; i++ {
if s[i] != s[len(s)-1-i] {
return false
}
}
return true
}
# 4
func longestPalindrome(s string) string {
if len(s) <= 1 {
return s
}
str := add(s)
length := len(str)
max := 1
begin := 0
for i := 0; i < length; i++ {
curLength := search(str, i)
if curLength > max {
max = curLength
begin = (i - max) / 2
}
}
return s[begin : begin+max]
}
func search(s string, center int) int {
i := center - 1
j := center + 1
step := 0
for ; i >= 0 && j < len(s) && s[i] == s[j]; i, j = i-1, j+1 {
step++
}
return step
}
func add(s string) string {
var res []rune
for _, v := range s {
res = append(res, '#')
res = append(res, v)
}
res = append(res, '#')
return string(res)
}
#
func longestPalindrome(s string) string {
if len(s) <= 1 {
return s
}
str := add(s)
length := len(str)
temp := make([]int, length)
maxRight := 0
center := 0
max := 1
begin := 0
for i := 0; i < length; i++ {
if i < maxRight {
mirror := 2*center - i
temp[i] = min(maxRight-i, temp[mirror])
}
left := i - (1 + temp[i])
right := i + (1 + temp[i])
for left >= 0 && right < len(str) && str[left] == str[right] {
temp[i]++
left--
right++
}
if i+temp[i] > maxRight {
maxRight = i + temp[i]
center = i
}
if temp[i] > max {
max = temp[i]
begin = (i - max) / 2
}
}
return s[begin : begin+max]
}
func add(s string) string {
var res []rune
for _, v := range s {
res = append(res, '#')
res = append(res, v)
}
res = append(res, '#')
return string(res)
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
6.Z字形变换(2)
将一个给定字符串根据给定的行数，以从上往下、从左到右进行 Z 字形排列。
比如输入字符串为 "LEETCODEISHIRING" 行数为 3 时，排列如下：
L C I R
E T O E S I I G
E D H N
之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："LCIRETOESIIGEDHN"。
请你实现这个将字符串进行指定行数变换的函数：
string convert(string s, int numRows);
示例 1:输入: s = "LEETCODEISHIRING", numRows = 3 输出: "LCIRETOESIIGEDHN"
示例 2:输入: s = "LEETCODEISHIRING", numRows = 4 输出: "LDREOEIIECIHNTSG"
解释:
L D R
E O E I I
E C I H N
T S G
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(n) |
O(n) |
| 02 |
遍历 |
O(n) |
O(n) |
func convert(s string, numRows int) string {
if numRows == 1 {
return s
}
arr := []rune(s)
total := numRows*2 - 2
res := make([]string, numRows)
for i := 0; i < len(arr); i++ {
index := i % total
if index < numRows {
res[index] = res[index] + string(arr[i])
} else {
res[total-index] = res[total-index] + string(arr[i])
}
}
return strings.Join(res, "")
}
#
func convert(s string, numRows int) string {
if numRows == 1 {
return s
}
arr := []rune(s)
res := make([]string, numRows)
flag := -1
index := 0
for i := 0; i < len(arr); i++ {
res[index] = res[index] + string(arr[i])
if index == 0 || index == numRows-1 {
flag = -flag
}
index = index + flag
}
return strings.Join(res, "")
}
8.字符串转换整数 (atoi)(3)
请你来实现一个 atoi 函数，使其能将字符串转换成整数。
首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。接下来的转化规则如下：
如果第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字字符组合起来，形成一个有符号整数。
假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成一个整数。
该字符串在有效的整数部分之后也可能会存在多余的字符，那么这些字符可以被忽略，它们对函数不应该造成影响。
注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，
则你的函数不需要进行转换，即无法进行有效转换。
在任何情况下，若函数不能进行有效的转换时，请返回 0 。
提示：
本题中的空白字符只包括空格字符 ' ' 。
假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 [−231, 231 − 1]。
如果数值超过这个范围，请返回 INT_MAX (231 − 1) 或 INT_MIN (−231) 。
示例 1:输入: "42" 输出: 42
示例 2:输入: " -42" 输出: -42
解释: 第一个非空白字符为 '-', 它是一个负号。
我们尽可能将负号与后面所有连续出现的数字组合起来，最后得到 -42 。
示例 3:输入: "4193 with words" 输出: 4193
解释: 转换截止于数字 '3' ，因为它的下一个字符不为数字。
示例 4:输入: "words and 987" 输出: 0
解释: 第一个非空字符是 'w', 但它不是数字或正、负号。
因此无法执行有效的转换。
示例 5:输入: "-91283472332" 输出: -2147483648
解释: 数字 "-91283472332" 超过 32 位有符号整数范围。
因此返回 INT_MIN (−231) 。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(n) |
O(n) |
| 02 |
正则 |
O(n) |
O(n) |
| 03 |
遍历 |
O(n) |
O(n) |
func myAtoi(str string) int {
i := 0
for i < len(str) && str[i] == ' ' {
i++
}
str = str[i:]
arr := make([]byte, 0)
isFlag := byte(' ')
for j := 0; j < len(str); j++ {
if str[j] >= '0' && str[j] <= '9' {
arr = append(arr, str[j])
} else {
if len(arr) > 0 {
break
}
if str[j] != ' ' && str[j] != '+' && str[j] != '-' {
return 0
}
if isFlag != ' ' {
return 0
}
isFlag = str[j]
}
}
res := 0
for i := 0; i < len(arr); i++ {
value := int(arr[i] - '0')
res = res*10 + value
if isFlag == '-' {
if -1*res < math.MinInt32 {
return math.MinInt32
}
} else if isFlag == ' ' || isFlag == '+' {
if res > math.MaxInt32 {
return math.MaxInt32
}
}
}
if isFlag == '-' {
return -1 * res
}
return res
}
#
func myAtoi(str string) int {
re := regexp.MustCompile(`^[+-]?\d+`)
arrS := re.FindAllString(strings.Trim(str, " "), -1)
if len(arrS) == 0{
return 0
}
arr := arrS[0]
res := 0
isFlag := byte(' ')
if !(arr[0] >= '0' && arr[0] <= '9') {
isFlag = arr[0]
arr = arr[1:]
}
for i := 0; i < len(arr); i++ {
value := int(arr[i] - '0')
if isFlag == '-' {
if res > 214748364 || (res==214748364 && value >= 8) {
return math.MinInt32
}
} else if isFlag == ' ' || isFlag == '+' {
if res > 214748364 || (res==214748364 && value >= 7) {
return math.MaxInt32
}
}
res = res*10 + value
}
if isFlag == '-' {
return -1 * res
}
return res
}
#
func myAtoi(str string) int {
str = strings.TrimSpace(str)
result := 0
flag := 1
for i, v := range str {
if v >= '0' && v <= '9' {
result = result*10 + int(v-'0')
} else if v == '-' && i == 0 {
flag = -1
} else if v == '+' && i == 0 {
flag = 1
} else {
break
}
if result > math.MaxInt32 {
if flag == -1 {
return math.MinInt32
}
return math.MaxInt32
}
}
return flag * result
}
11.盛最多水的容器(2)
给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。
在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
说明：你不能倾斜容器，且 n 的值至少为 2。
图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
示例：输入：[1,8,6,2,5,4,8,3,7] 输出：49
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历-双指针 |
O(n) |
O(1) |
| 02 |
遍历-暴力法 |
O(n^2) |
O(1) |
func maxArea(height []int) int {
i := 0
j := len(height) - 1
res := 0
for i < j {
area := (j - i) * min(height[i], height[j])
if area > res {
res = area
}
if height[i] > height[j] {
j--
} else {
i++
}
}
return res
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
#
func maxArea(height []int) int {
res := 0
for i := 0; i < len(height); i++ {
for j := i + 1; j < len(height); j++ {
area := (j - i) * min(height[i], height[j])
if area > res {
res = area
}
}
}
return res
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
12.整数转罗马数字(2)
罗马数字包含以下七种字符： I， V， X， L，C，D 和 M。
字符 数值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。
27 写做 XXVII, 即为 XX + V + II 。
通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。
数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。
同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：
I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。
给定一个整数，将其转为罗马数字。输入确保在 1 到 3999 的范围内。
示例 1:输入: 3输出: "III"
示例 2:输入: 4 输出: "IV"
示例 3:输入: 9 输出: "IX"
示例 4:输入: 58 输出: "LVIII"
解释: L = 50, V = 5, III = 3.
示例 5:输入: 1994 输出: "MCMXCIV"
解释: M = 1000, CM = 900, XC = 90, IV = 4.
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(log(n)) |
O(1) |
| 02 |
枚举 |
O(1) |
O(1) |
func intToRoman(num int) string {
m := map[int]string{
1: "I",
4: "IV",
5: "V",
9: "IX",
10: "X",
40: "XL",
50: "L",
90: "XC",
100: "C",
400: "CD",
500: "D",
900: "CM",
1000: "M",
}
arr := []int{1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1}
result := ""
for i := 0; i < len(arr); i++ {
if num == 0 {
break
}
value := num / arr[i]
for j := 0; j < value; j++ {
result = result + m[arr[i]]
}
num = num - value*arr[i]
}
return result
}
#
func intToRoman(num int) string {
res := ""
arr1 := []string{"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"}
arr2 := []string{"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"}
arr3 := []string{"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"}
arr4 := []string{"", "M", "MM", "MMM"}
res = arr4[num/1000] + arr3[num%1000/100] + arr2[num%100/10] + arr1[num%10]
return res
}
15.三数之和(2)
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？
请你找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例：
给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
双指针 |
O(n^2) |
O(n^2) |
| 02 |
哈希辅助 |
O(n^2) |
O(n^2) |
func threeSum(nums []int) [][]int {
res := make([][]int, 0)
sort.Ints(nums)
for i := 0; i < len(nums)-1; i++ {
target := 0 - nums[i]
left := i + 1
right := len(nums) - 1
if nums[i] > 0 || nums[i]+nums[left] > 0 {
break
}
if i > 0 && nums[i] == nums[i-1] {
continue
}
for left < right {
if left > i+1 && nums[left] == nums[left-1] {
left++
continue
}
if right < len(nums)-2 && nums[right] == nums[right+1] {
right--
continue
}
if nums[left]+nums[right] > target {
right--
} else if nums[left]+nums[right] < target {
left++
} else {
res = append(res, []int{nums[i], nums[left], nums[right]})
left++
right--
}
}
}
return res
}
#
func threeSum(nums []int) [][]int {
res := make([][]int, 0)
m := make(map[[2]int]int)
p := make(map[int]int)
sort.Ints(nums)
for k, v := range nums {
p[v] = k
}
for i := 0; i < len(nums); i++ {
for j := i + 1; j < len(nums); j++ {
if j != i+1 && nums[j] == nums[j-1] {
continue
}
sum := nums[i] + nums[j]
if sum > 0 {
break
}
if value, ok := p[-sum]; ok && value > j {
if _, ok2 := m[[2]int{nums[i], nums[j]}]; !ok2 {
res = append(res, []int{nums[i], nums[j], 0 - nums[i] - nums[j]})
m[[2]int{nums[i], nums[j]}] = 1
}
}
}
}
return res
}
16.最接近的三数之和(2)
给定一个包括 n 个整数的数组 nums 和 一个目标值 target。
找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。
示例：输入：nums = [-1,2,1,-4], target = 1 输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。
提示：
3 <= nums.length <= 10^3
-10^3 <= nums[i] <= 10^3
-10^4 <= target <= 10^4
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
双指针 |
O(n^2) |
O(1) |
| 02 |
暴力法 |
O(n^3) |
O(1) |
func threeSumClosest(nums []int, target int) int {
sort.Ints(nums)
res := nums[0] + nums[1] + nums[2]
for i := 0; i < len(nums); i++ {
left := i + 1
right := len(nums) - 1
for left < right {
sum := nums[i] + nums[left] + nums[right]
if sum > target {
right--
} else if sum < target {
left++
} else {
return target
}
if abs(sum, target) < abs(res, target) {
res = sum
}
}
}
return res
}
func abs(a, b int) int {
if a > b {
return a - b
}
return b - a
}
#
func threeSumClosest(nums []int, target int) int {
res := nums[0] + nums[1] + nums[2]
for i := 0; i < len(nums); i++ {
for j := i + 1; j < len(nums); j++ {
for k := j + 1; k < len(nums); k++ {
sum := nums[i] + nums[j] + nums[k]
if abs(sum, target) < abs(res, target) {
res = sum
}
}
}
}
return res
}
func abs(a, b int) int {
if a > b {
return a - b
}
return b - a
}
17.电话号码的字母组合(2)
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例:输入："23"输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
说明:尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(4^n) |
O(4^n) |
| 02 |
递归-回溯 |
O(4^n) |
O(4^n) |
func letterCombinations(digits string) []string {
if len(digits) == 0 {
return nil
}
arr := []string{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}
res := []string{""}
for i := 0; i < len(digits); i++ {
length := len(res)
for j := 0; j < length; j++ {
for k := 0; k < len(arr[digits[i]-'0']); k++ {
res = append(res, res[j]+string(arr[digits[i]-'0'][k]))
}
}
res = res[length:]
}
return res
}
#
var res []string
var arr = []string{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}
func letterCombinations(digits string) []string {
if len(digits) == 0 {
return nil
}
res = make([]string, 0)
dfs(digits, 0, "")
return res
}
func dfs(digits string, index int, str string) {
if index == len(digits) {
res = append(res, str)
return
}
for i := 0; i < len(arr[digits[index]-'0']); i++ {
dfs(digits, index+1, str+string(arr[digits[index]-'0'][i]))
}
}
18.四数之和(3)
给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，
使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。
注意：答案中不可以包含重复的四元组。
示例：给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。
满足要求的四元组集合为：
[
[-1, 0, 0, 1],
[-2, -1, 1, 2],
[-2, 0, 0, 2]
]
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
双指针 |
O(n^3) |
O(n^3) |
| 02 |
哈希辅助 |
O(n^3) |
O(n^3) |
| 03 |
全排列+递归 |
O(n^3) |
O(n^3) |
func fourSum(nums []int, target int) [][]int {
sort.Ints(nums)
res := make([][]int, 0)
for i := 0; i < len(nums); i++ {
if i > 0 && nums[i] == nums[i-1] {
continue
}
for j := i + 1; j < len(nums); j++ {
if j > i+1 && nums[j] == nums[j-1] {
continue
}
temp := target - nums[i] - nums[j]
left := j + 1
right := len(nums) - 1
for left < right {
if left > j+1 && nums[left] == nums[left-1] {
left++
continue
}
if right < len(nums)-2 && nums[right] == nums[right+1] {
right--
continue
}
if nums[left]+nums[right] > temp {
right--
} else if nums[left]+nums[right] < temp {
left++
} else {
res = append(res, []int{nums[i], nums[j], nums[left], nums[right]})
left++
right--
}
}
}
}
return res
}
#
func fourSum(nums []int, target int) [][]int {
m := make(map[[3]int]int)
p := make(map[int]int)
sort.Ints(nums)
for k, v := range nums {
p[v] = k
}
res := make([][]int, 0)
for i := 0; i < len(nums); i++ {
for j := i + 1; j < len(nums); j++ {
for k := j + 1; k < len(nums); k++ {
sum := nums[i] + nums[j] + nums[k]
if value, ok := p[target-sum]; ok && value > k {
if _, ok2 := m[[3]int{nums[i], nums[j], nums[k]}]; !ok2 {
res = append(res, []int{nums[i], nums[j], nums[k], target - nums[i] - nums[j] - nums[k]})
m[[3]int{nums[i], nums[j], nums[k]}] = 1
}
}
}
}
}
return res
}
#
var res [][]int
func fourSum(nums []int, target int) [][]int {
sort.Ints(nums)
res = make([][]int, 0)
dfs(nums, target, []int{}, 0)
return res
}
func dfs(nums []int, target int, arr []int, level int) {
if len(arr) == 4 {
sum := 0
for i := 0; i < len(arr); i++ {
sum = sum + arr[i]
}
if sum == target {
tempArr := make([]int, len(arr))
copy(tempArr, arr)
res = append(res, tempArr)
}
return
}
prev := math.MaxInt32
for i := level; i < len(nums); i++ {
if nums[i] != prev {
prev = nums[i]
arr = append(arr, nums[i])
dfs(nums, target, arr, i+1)
arr = arr[:len(arr)-1]
}
}
}
19.删除链表的倒数第N个节点(3)
给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
示例：给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1->2->3->5.
说明：给定的 n 保证是有效的。
进阶：你能尝试使用一趟扫描实现吗？
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(n) |
O(1) |
| 02 |
快慢指针 |
O(n) |
O(1) |
| 03 |
递归 |
O(n) |
O(n) |
func removeNthFromEnd(head *ListNode, n int) *ListNode {
temp := &ListNode{Next: head}
cur := temp
total := 0
for cur.Next != nil {
cur = cur.Next
total++
}
cur = temp
count := 0
for cur.Next != nil {
if total-n == count {
cur.Next = cur.Next.Next
break
}
cur = cur.Next
count++
}
return temp.Next
}
#
func removeNthFromEnd(head *ListNode, n int) *ListNode {
temp := &ListNode{Next: head}
fast, slow := temp, temp
for i := 0; i < n; i++ {
fast = fast.Next
}
for fast.Next != nil {
fast = fast.Next
slow = slow.Next
}
slow.Next = slow.Next.Next
return temp.Next
}
#
var count int
func removeNthFromEnd(head *ListNode, n int) *ListNode {
if head == nil {
count = 0
return nil
}
head.Next = removeNthFromEnd(head.Next, n)
count = count + 1
if count == n {
return head.Next
}
return head
}
22.括号生成(3)
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例：输入：n = 3
输出：[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
全排列-递归 |
O(4^n/n^(1/2)) |
O(4^n/n^(1/2)) |
| 02 |
动态规划 |
O(4^n/n^(1/2)) |
O(4^n/n^(1/2)) |
| 03 |
广度优先搜索 |
O(4^n/n^(1/2)) |
O(4^n/n^(1/2)) |
var res []string
func generateParenthesis(n int) []string {
res = make([]string, 0)
dfs(0, 0, n, "")
return res
}
func dfs(left, right, max int, str string) {
if left == right && left == max {
res = append(res, str)
return
}
if left < max {
dfs(left+1, right, max, str+"(")
}
if right < left {
dfs(left, right+1, max, str+")")
}
}
#
func generateParenthesis(n int) []string {
dp := make([][]string, n+1)
dp[0] = make([]string, 0)
if n == 0 {
return dp[0]
}
dp[0] = append(dp[0], "")
for i := 1; i <= n; i++ {
dp[i] = make([]string, 0)
for j := 0; j < i; j++ {
for _, a := range dp[j] {
for _, b := range dp[i-j-1] {
str := "(" + a + ")" + b
dp[i] = append(dp[i], str)
}
}
}
}
return dp[n]
}
#
type Node struct {
str string
left int
right int
}
func generateParenthesis(n int) []string {
res := make([]string, 0)
if n == 0 {
return res
}
queue := make([]*Node, 0)
queue = append(queue, &Node{
str: "",
left: n,
right: n,
})
for len(queue) > 0 {
node := queue[0]
queue = queue[1:]
if node.left == 0 && node.right == 0 {
res = append(res, node.str)
}
if node.left > 0 {
queue = append(queue, &Node{
str: node.str + "(",
left: node.left - 1,
right: node.right,
})
}
if node.right > 0 && node.left < node.right {
queue = append(queue, &Node{
str: node.str + ")",
left: node.left,
right: node.right - 1,
})
}
}
return res
}
24.两两交换链表中的节点(2)
给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例:给定 1->2->3->4, 你应该返回 2->1->4->3.
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(n) |
O(1) |
| 02 |
递归 |
O(n) |
O(n) |
func swapPairs(head *ListNode) *ListNode {
temp := &ListNode{Next: head}
prev := temp
for head != nil && head.Next != nil {
first, second := head, head.Next
prev.Next = second
first.Next, second.Next = second.Next, first
prev, head = first, first.Next
}
return temp.Next
}
#
func swapPairs(head *ListNode) *ListNode {
if head == nil || head.Next == nil {
return head
}
first, second := head, head.Next
first.Next, second.Next = swapPairs(second.Next), first
return second
}
29.两数相除(2)
给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。
返回被除数 dividend 除以除数 divisor 得到的商。
整数除法的结果应当截去（truncate）其小数部分，
例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2
示例 1:输入: dividend = 10, divisor = 3输出: 3
解释: 10/3 = truncate(3.33333..) = truncate(3) = 3
示例 2:输入: dividend = 7, divisor = -3 输出: -2
解释: 7/-3 = truncate(-2.33333..) = -2
提示：
被除数和除数均为 32 位有符号整数。
除数不为 0。
假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−2^31, 2^31 − 1]。
本题中，如果除法结果溢出，则返回 2^31 − 1。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(log(n)) |
O(1) |
| 02 |
计算 |
O(1) |
O(1) |
func divide(dividend int, divisor int) int {
if divisor == 0 || dividend == 0 {
return 0
}
if divisor == 1 {
return dividend
}
flag, count := 1, 1
if dividend < 0 {
flag = -flag
dividend = -dividend
}
if divisor < 0 {
flag = -flag
divisor = -divisor
}
a, b, c := dividend, divisor, 0
temp := b
for a-b >= 0 {
for a-b >= 0 {
a = a - b
c = c + count
b = b + b
count = count + count
}
b = temp
count = 1
}
if c > math.MaxInt32 {
return math.MaxInt32
}
if flag < 0 {
return -c
}
return c
}
#
func divide(dividend int, divisor int) int {
res := dividend / divisor
if res > math.MaxInt32 {
return math.MaxInt32
}
return res
}
31.下一个排列(2)
实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
必须原地修改，只允许使用额外常数空间。
以下是一些例子，输入位于左侧列，其相应输出位于右侧列。
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(n) |
O(1) |
| 02 |
遍历 |
O(n) |
O(1) |
func nextPermutation(nums []int) {
n := len(nums)
left := n - 2
for left >= 0 && nums[left] >= nums[left+1] {
left--
}
if left == -1 {
sort.Ints(nums)
return
}
right := n - 1
for right >= 0 && nums[right] <= nums[left] {
right--
}
nums[left], nums[right] = nums[right], nums[left]
count := 0
for i := left + 1; i <= (left+1+n-1)/2; i++ {
nums[i], nums[n-1-count] = nums[n-1-count], nums[i]
count++
}
}
# 2
func nextPermutation(nums []int) {
n := len(nums)
left := n - 2
for left >= 0 && nums[left] >= nums[left+1] {
left--
}
if left >= 0 {
right := n - 1
for right >= 0 && nums[right] <= nums[left] {
right--
}
nums[left], nums[right] = nums[right], nums[left]
}
reverse(nums, left+1, n-1)
}
func reverse(nums []int, left, right int) {
for left < right {
nums[left], nums[right] = nums[right], nums[left]
left++
right--
}
}
33.搜索旋转排序数组(2)
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。
你可以假设数组中不存在重复的元素。
你的算法时间复杂度必须是 O(log n) 级别。
示例 1:输入: nums = [4,5,6,7,0,1,2], target = 0 输出: 4
示例 2:输入: nums = [4,5,6,7,0,1,2], target = 3 输出: -1
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
二分查找 |
O(log(n)) |
O(1) |
| 02 |
遍历 |
O(n) |
O(1) |
func search(nums []int, target int) int {
left, right := 0, len(nums)-1
for left <= right {
mid := left + (right-left)/2
if nums[mid] == target {
return mid
}
if nums[left] <= nums[mid] {
if nums[left] <= target && target < nums[mid] {
right = mid - 1
} else {
left = mid + 1
}
} else {
if nums[mid] < target && target <= nums[right] {
left = mid + 1
} else {
right = mid - 1
}
}
}
return -1
}
#
func search(nums []int, target int) int {
for i := 0; i < len(nums); i++{
if nums[i] == target{
return i
}
}
return -1
}
34.在排序数组中查找元素的第一个和最后一个位置(4)
给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
你的算法时间复杂度必须是 O(log n) 级别。
如果数组中不存在目标值，返回 [-1, -1]。
示例 1:输入: nums = [5,7,7,8,8,10], target = 8 输出: [3,4]
示例 2:输入: nums = [5,7,7,8,8,10], target = 6 输出: [-1,-1]
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
双指针 |
O(n) |
O(1) |
| 02 |
遍历 |
O(n) |
O(1) |
| 03 |
二分查找 |
O(log(n)) |
O(1) |
| 04 |
二分查找 |
O(log(n)) |
O(1) |
func searchRange(nums []int, target int) []int {
left := 0
right := len(nums) - 1
for left <= right {
if nums[left] != target {
if target > nums[left] {
left++
}
}
if nums[right] != target {
if target < nums[right] {
right--
}
}
if left < len(nums) && right >= 0 &&
nums[left] == nums[right] && nums[left] == target {
break
}
}
if right < left {
return []int{-1, -1}
}
return []int{left, right}
}
#
func searchRange(nums []int, target int) []int {
left := -1
right := -1
for i := 0; i < len(nums); i++ {
if nums[i] == target {
right = i
} else if nums[i] > target {
break
}
}
for i := len(nums) - 1; i >= 0; i-- {
if nums[i] == target {
left = i
} else if nums[i] < target {
break
}
}
return []int{left, right}
}
# 3
func searchRange(nums []int, target int) []int {
if len(nums) == 0 || nums[0] > target || nums[len(nums)-1] < target {
return []int{-1, -1}
}
left := leftSearch(nums, target)
right := rightSearch(nums, target)
return []int{left, right}
}
func leftSearch(nums []int, target int) int {
left, right := 0, len(nums)-1
for left <= right {
mid := left + (right-left)/2
if target > nums[mid] {
left = mid + 1
} else {
right = mid - 1
}
}
if left < len(nums) && nums[left] == target {
return left
}
return -1
}
func rightSearch(nums []int, target int) int {
left, right := 0, len(nums)-1
for left <= right {
mid := left + (right-left)/2
if target < nums[mid] {
right = mid - 1
} else {
left = mid + 1
}
}
if right >= 0 && nums[right] == target {
return right
}
return -1
}
#
func searchRange(nums []int, target int) []int {
left := -1
right := -1
for i, j := 0, len(nums)-1; i <= j; {
mid := i + (j-i)/2
if nums[mid] < target {
i = mid + 1
} else if nums[mid] > target {
j = mid - 1
} else {
for temp := mid; temp >= 0; temp-- {
if target == nums[temp] {
left = temp
} else {
break
}
}
for temp := mid; temp < len(nums); temp++ {
if target == nums[temp] {
right = temp
} else {
break
}
}
break
}
}
return []int{left, right}
}
36.有效的数独(1)
判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
上图是一个部分填充的有效的数独。
数独部分空格内已填入了数字，空白格用 '.' 表示。
示例 1:输入:
[
["5","3",".",".","7",".",".",".","."],
["6",".",".","1","9","5",".",".","."],
[".","9","8",".",".",".",".","6","."],
["8",".",".",".","6",".",".",".","3"],
["4",".",".","8",".","3",".",".","1"],
["7",".",".",".","2",".",".",".","6"],
[".","6",".",".",".",".","2","8","."],
[".",".",".","4","1","9",".",".","5"],
[".",".",".",".","8",".",".","7","9"]
]
输出: true
示例 2:输入:
[
["8","3",".",".","7",".",".",".","."],
["6",".",".","1","9","5",".",".","."],
[".","9","8",".",".",".",".","6","."],
["8",".",".",".","6",".",".",".","3"],
["4",".",".","8",".","3",".",".","1"],
["7",".",".",".","2",".",".",".","6"],
[".","6",".",".",".",".","2","8","."],
[".",".",".","4","1","9",".",".","5"],
[".",".",".",".","8",".",".","7","9"]
]
输出: false
解释: 除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。
但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。
说明:
一个有效的数独（部分已被填充）不一定是可解的。
只需要根据以上规则，验证已经填入的数字是否有效即可。
给定数独序列只包含数字 1-9 和字符 '.' 。
给定数独永远是 9x9 形式的。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(1) |
O(1) |
func isValidSudoku(board [][]byte) bool {
var row, col, arr [9][9]int
for i := 0; i < 9; i++ {
for j := 0; j < 9; j++ {
if board[i][j] != '.' {
num := board[i][j] - '1'
index := (i/3)*3 + j/3
if row[i][num] == 1 || col[j][num] == 1 || arr[index][num] == 1 {
return false
}
row[i][num] = 1
col[j][num] = 1
arr[index][num] = 1
}
}
}
return true
}
39.组合总和(2)
给定一个无重复元素的数组 candidates 和一个目标数 target ，
找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
说明：
所有数字（包括 target）都是正整数。
解集不能包含重复的组合。
示例 1:输入: candidates = [2,3,6,7], target = 7, 所求解集为:
[
[7],
[2,2,3]
]
示例 2:输入: candidates = [2,3,5], target = 8, 所求解集为:
[
[2,2,2,2],
[2,3,3],
[3,5]
]
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
递归 |
O(2^n) |
O(2^n) |
| 02 |
递归 |
O(2^n) |
O(2^n) |
var res [][]int
func combinationSum(candidates []int, target int) [][]int {
res = make([][]int, 0)
sort.Ints(candidates)
dfs(candidates, target, []int{}, 0)
return res
}
func dfs(candidates []int, target int, arr []int, index int) {
if target == 0 {
temp := make([]int, len(arr))
copy(temp, arr)
res = append(res, temp)
return
}
if target < 0{
return
}
for i := index; i < len(candidates); i++ {
arr = append(arr, candidates[i])
dfs(candidates, target-candidates[i], arr, i)
arr = arr[:len(arr)-1]
}
}
#
var res [][]int
func combinationSum(candidates []int, target int) [][]int {
res = make([][]int, 0)
sort.Ints(candidates)
dfs(candidates, target, []int{}, 0)
return res
}
func dfs(candidates []int, target int, arr []int, index int) {
if target == 0 {
temp := make([]int, len(arr))
copy(temp, arr)
res = append(res, temp)
return
}
for i := index; i < len(candidates); i++ {
if target < candidates[i] {
return
}
dfs(candidates, target-candidates[i], append(arr, candidates[i]), i)
}
}
40.组合总和II(2)
给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。
说明：
所有数字（包括目标数）都是正整数。
解集不能包含重复的组合。
示例 1:输入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]
示例 2:输入: candidates = [2,5,2,1,2], target = 5,
所求解集为:
[
[1,2,2],
[5]
]
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
递归 |
O(n!) |
O(n!) |
| 02 |
递归 |
O(n!) |
O(n!) |
var res [][]int
func combinationSum2(candidates []int, target int) [][]int {
res = make([][]int, 0)
sort.Ints(candidates)
dfs(candidates, target, []int{}, 0)
return res
}
func dfs(candidates []int, target int, arr []int, index int) {
if target == 0 {
temp := make([]int, len(arr))
copy(temp, arr)
res = append(res, temp)
return
}
if target < 0 {
return
}
for i := index; i < len(candidates); i++ {
origin := i
for i < len(candidates)-1 && candidates[i] == candidates[i+1] {
i++
}
arr = append(arr, candidates[i])
dfs(candidates, target-candidates[i], arr, origin+1)
arr = arr[:len(arr)-1]
}
}
#
var res [][]int
func combinationSum2(candidates []int, target int) [][]int {
res = make([][]int, 0)
sort.Ints(candidates)
dfs(candidates, target, []int{}, 0)
return res
}
func dfs(candidates []int, target int, arr []int, index int) {
if target == 0 {
temp := make([]int, len(arr))
copy(temp, arr)
res = append(res, temp)
return
}
for i := index; i < len(candidates); i++ {
if i != index && candidates[i] == candidates[i-1] {
continue
}
if target < 0 {
return
}
arr = append(arr, candidates[i])
dfs(candidates, target-candidates[i], arr, i+1)
arr = arr[:len(arr)-1]
}
}
43.字符串相乘(1)
给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，
它们的乘积也表示为字符串形式。
示例 1:输入: num1 = "2", num2 = "3"输出: "6"
示例 2:输入: num1 = "123", num2 = "456"输出: "56088"
说明：
num1 和 num2 的长度小于110。
num1 和 num2 只包含数字 0-9。
num1 和 num2 均不以零开头，除非是数字 0 本身。
不能使用任何标准库的大数类型（比如 BigInteger）或直接将输入转换为整数来处理。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
模拟 |
O(n^2) |
O(n) |
| 02 |
内置函数 |
O(n^2) |
O(n) |
func multiply(num1 string, num2 string) string {
if num1 == "0" || num2 == "0" {
return "0"
}
arr := make([]int, len(num1)+len(num2))
for i := len(num1) - 1; i >= 0; i-- {
a := int(num1[i] - '0')
for j := len(num2) - 1; j >= 0; j-- {
b := int(num2[j] - '0')
value := a*b + arr[i+j+1]
arr[i+j+1] = value % 10
arr[i+j] = value/10 + arr[i+j]
}
}
res := ""
for i := 0; i < len(arr); i++ {
if i == 0 && arr[i] == 0 {
continue
}
res = res + string(arr[i]+'0')
}
return res
}
# 2
func multiply(num1 string, num2 string) string {
a, b := new(big.Int), new(big.Int)
a.SetString(num1, 10)
b.SetString(num2, 10)
a.Mul(a, b)
return a.String()
}
46.全排列(3)
给定一个 没有重复 数字的序列，返回其所有可能的全排列。
示例:输入: [1,2,3]输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
回溯 |
O(n^n) |
O(n*n!) |
| 02 |
递归 |
O(n!) |
O(n*n!) |
| 03 |
回溯 |
O(n!) |
O(n*n!) |
var res [][]int
func permute(nums []int) [][]int {
res = make([][]int, 0)
arr := make([]int, 0)
visited := make(map[int]bool)
dfs(nums, 0, arr, visited)
return res
}
func dfs(nums []int, index int, arr []int, visited map[int]bool) {
if index == len(nums) {
temp := make([]int, len(arr))
copy(temp, arr)
res = append(res, temp)
return
}
for i := 0; i < len(nums); i++ {
if visited[i] == false {
arr = append(arr, nums[i])
visited[i] = true
dfs(nums, index+1, arr, visited)
arr = arr[:len(arr)-1]
visited[i] = false
}
}
}
#
func permute(nums []int) [][]int {
if len(nums) == 1 {
return [][]int{nums}
}
res := make([][]int, 0)
for i := 0; i < len(nums); i++ {
tempArr := make([]int, len(nums)-1)
copy(tempArr[0:], nums[:i])
copy(tempArr[i:], nums[i+1:])
arr := permute(tempArr)
for _, v := range arr {
res = append(res, append(v, nums[i]))
}
}
return res
}
#
var res [][]int
func permute(nums []int) [][]int {
res = make([][]int, 0)
arr := make([]int, len(nums))
dfs(nums, 0, arr)
return res
}
func dfs(nums []int, index int, arr []int) {
if index == len(nums) {
temp := make([]int, len(arr))
copy(temp, arr)
res = append(res, temp)
return
}
for i := index; i < len(nums); i++ {
arr[index] = nums[i]
nums[i], nums[index] = nums[index], nums[i]
dfs(nums, index+1, arr)
nums[i], nums[index] = nums[index], nums[i]
}
}
47.全排列II(3)
给定一个可包含重复数字的序列，返回所有不重复的全排列。
示例:输入: [1,1,2] 输出:
[
[1,1,2],
[1,2,1],
[2,1,1]
]
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
回溯 |
O(n!) |
O(n!) |
| 02 |
回溯 |
O(n!) |
O(n!) |
| 03 |
回溯 |
O(n!) |
O(n!) |
var res [][]int
func permuteUnique(nums []int) [][]int {
res = make([][]int, 0)
sort.Ints(nums)
dfs(nums, 0, make([]int, len(nums)), make([]int, 0))
return res
}
func dfs(nums []int, index int, visited []int, arr []int) {
if len(nums) == index {
temp := make([]int, len(arr))
copy(temp, arr)
res = append(res, temp)
return
}
for i := 0; i < len(nums); i++ {
if visited[i] == 1 {
continue
}
if i > 0 && nums[i] == nums[i-1] && visited[i-1] == 0 {
continue
}
arr = append(arr, nums[i])
visited[i] = 1
dfs(nums, index+1, visited, arr)
visited[i] = 0
arr = arr[:len(arr)-1]
}
}
# 2
var res [][]int
func permuteUnique(nums []int) [][]int {
res = make([][]int, 0)
sort.Ints(nums)
dfs(nums, 0)
return res
}
func dfs(nums []int, index int) {
if index == len(nums) {
temp := make([]int, len(nums))
copy(temp, nums)
res = append(res, temp)
return
}
m := make(map[int]int)
for i := index; i < len(nums); i++ {
if _, ok := m[nums[i]]; ok {
continue
}
m[nums[i]] = 1
nums[i], nums[index] = nums[index], nums[i]
dfs(nums, index+1)
nums[i], nums[index] = nums[index], nums[i]
}
}
# 3
var res [][]int
func permuteUnique(nums []int) [][]int {
res = make([][]int, 0)
sort.Ints(nums)
dfs(nums, make([]int, 0))
return res
}
func dfs(nums []int, arr []int) {
if len(nums) == 0 {
temp := make([]int, len(arr))
copy(temp, arr)
res = append(res, temp)
return
}
for i := 0; i < len(nums); i++ {
if i != 0 && nums[i] == nums[i-1] {
continue
}
tempArr := make([]int, len(nums))
copy(tempArr, nums)
arr = append(arr, nums[i])
dfs(append(tempArr[:i], tempArr[i+1:]...), arr)
arr = arr[:len(arr)-1]
}
}
48.旋转图像(3)
给定一个 n × n 的二维矩阵表示一个图像。
将图像顺时针旋转 90 度。
说明：你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。
示例 1:给定 matrix =
[
[1,2,3],
[4,5,6],
[7,8,9]
],
原地旋转输入矩阵，使其变为:
[
[7,4,1],
[8,5,2],
[9,6,3]
]
示例 2:给定 matrix =
[
[ 5, 1, 9,11],
[ 2, 4, 8,10],
[13, 3, 6, 7],
[15,14,12,16]
],
原地旋转输入矩阵，使其变为:
[
[15,13, 2, 5],
[14, 3, 4, 1],
[12, 6, 8, 9],
[16, 7,10,11]
]
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(n^2) |
O(1) |
| 02 |
遍历 |
O(n^2) |
O(1) |
| 03 |
数组辅助 |
O(n^2) |
O(n^2) |
func rotate(matrix [][]int) {
n := len(matrix)
for i := 0; i < n; i++ {
for j := 0; j < n/2; j++ {
matrix[i][j], matrix[i][n-1-j] = matrix[i][n-1-j], matrix[i][j]
}
}
for i := 0; i < n-1; i++ {
for j := 0; j < n-1-i; j++ {
matrix[i][j], matrix[n-1-j][n-1-i] = matrix[n-1-j][n-1-i], matrix[i][j]
}
}
}
# 2
func rotate(matrix [][]int) {
n := len(matrix)
for start, end := 0, n-1; start < end; {
for s, e := start, end; s < end; {
matrix[start][s], matrix[e][start], matrix[end][e], matrix[s][end] =
matrix[e][start], matrix[end][e], matrix[s][end], matrix[start][s]
s++
e--
}
start++
end--
}
}
# 3
func rotate(matrix [][]int) {
n := len(matrix)
arr := make([][]int, n)
for i := 0; i < n; i++ {
arr[i] = make([]int, n)
}
for i := 0; i < n; i++ {
for j := 0; j < n; j++ {
arr[j][n-1-i] = matrix[i][j]
}
}
copy(matrix, arr)
}
49.字母异位词分组(2)
给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。
示例:输入: ["eat", "tea", "tan", "ate", "nat", "bat"]
输出:
[
["ate","eat","tea"],
["nat","tan"],
["bat"]
]
说明：
所有输入均为小写字母。
不考虑答案输出的顺序。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
哈希辅助 |
O(n^2log(n)) |
O(n^2) |
| 02 |
哈希辅助 |
O(n^2) |
O(n^2) |
func groupAnagrams(strs []string) [][]string {
m := make(map[string]int)
res := make([][]string, 0)
for i := 0; i < len(strs); i++ {
arr := []byte(strs[i])
sort.Slice(arr, func(i, j int) bool {
return arr[i] < arr[j]
})
newStr := string(arr)
if _, ok := m[newStr]; ok {
res[m[newStr]] = append(res[m[newStr]], strs[i])
} else {
m[newStr] = len(res)
res = append(res, []string{strs[i]})
}
}
return res
}
#
func groupAnagrams(strs []string) [][]string {
m := make(map[[26]int]int)
res := make([][]string, 0)
for i := 0; i < len(strs); i++ {
arr := [26]int{}
for j := 0; j < len(strs[i]); j++{
arr[strs[i][j]-'a']++
}
if _, ok := m[arr]; ok {
res[m[arr]] = append(res[m[arr]], strs[i])
} else {
m[arr] = len(res)
res = append(res, []string{strs[i]})
}
}
return res
}
50.Pow(x,n)(4)
实现 pow(x, n) ，即计算 x 的 n 次幂函数。
示例 1:输入: 2.00000, 10 输出: 1024.00000
示例 2:输入: 2.10000, 3 输出: 9.26100
示例 3:输入: 2.00000, -2 输出: 0.25000
解释: 2-2 = 1/22 = 1/4 = 0.25
说明: -100.0 < x < 100.0
n 是 32 位有符号整数，其数值范围是 [−231, 231 − 1] 。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
递归 |
O(log(n)) |
O(1) |
| 02 |
迭代 |
O(log(n)) |
O(1) |
| 03 |
计算 |
O(log(n)) |
O(1) |
| 04 |
递归 |
O(log(n)) |
O(log(n)) |
func myPow(x float64, n int) float64 {
if n == 0 {
return 1
}
if n < 0 {
return 1 / myPow(x, -n)
}
if n%2 == 1 {
return x * myPow(x, n-1)
}
return myPow(x*x, n/2)
}
#
func myPow(x float64, n int) float64 {
if n < 0 {
x = 1 / x
n = -n
}
res := float64(1)
for n > 0 {
if n%2 == 1 {
res = res * x
}
x = x * x
n = n / 2
}
return res
}
#
func myPow(x float64, n int) float64 {
return math.Pow(x, float64(n))
}
#
func myPow(x float64, n int) float64 {
if n == 0 {
return 1
}
if n == 1 {
return x
}
res := 1.0
if n > 0 {
res = myPow(x, n/2)
return res * res * myPow(x, n%2)
} else {
res = myPow(x, -n/2)
res = res * res * myPow(x, -n%2)
return 1 / res
}
}
54.螺旋矩阵(2)
给定一个包含 m x n 个元素的矩阵（m 行, n 列），请按照顺时针螺旋顺序，返回矩阵中的所有元素。
示例 1:输入:
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
输出: [1,2,3,6,9,8,7,4,5]
示例 2:输入:
[
[1, 2, 3, 4],
[5, 6, 7, 8],
[9,10,11,12]
]
输出: [1,2,3,4,8,12,11,10,9,5,6,7]
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(n^2) |
O(n^2) |
| 02 |
遍历 |
O(n^2) |
O(n^2) |
var res []int
func spiralOrder(matrix [][]int) []int {
res = make([]int, 0)
rows := len(matrix)
if rows == 0 {
return res
}
cols := len(matrix[0])
if cols == 0 {
return res
}
start := 0
for cols > start*2 && rows > start*2 {
printCircle(matrix, cols, rows, start)
start++
}
return res
}
func printCircle(matrix [][]int, cols, rows, start int) {
x := cols - 1 - start
y := rows - 1 - start
for i := start; i <= x; i++ {
res = append(res, matrix[start][i])
}
if start < y {
for i := start + 1; i <= y; i++ {
res = append(res, matrix[i][x])
}
}
if start < x && start < y {
for i := x - 1; i >= start; i-- {
res = append(res, matrix[y][i])
}
}
if start < x && start < y-1 {
for i := y - 1; i >= start+1; i-- {
res = append(res, matrix[i][start])
}
}
}
#
func spiralOrder(matrix [][]int) []int {
res := make([]int, 0)
rows := len(matrix)
if rows == 0 {
return res
}
cols := len(matrix[0])
if cols == 0 {
return res
}
x1, x2, y1, y2 := 0, rows-1, 0, cols-1
direct := 0
for x1 <= x2 && y1 <= y2 {
direct = (direct + 4) % 4
if direct == 0 {
for i := y1; i <= y2; i++ {
res = append(res, matrix[x1][i])
}
x1++
} else if direct == 1 {
for i := x1; i <= x2; i++ {
res = append(res, matrix[i][y2])
}
y2--
} else if direct == 2 {
for i := y2; i >= y1; i-- {
res = append(res, matrix[x2][i])
}
x2--
} else if direct == 3 {
for i := x2; i >= x1; i-- {
res = append(res, matrix[i][y1])
}
y1++
}
direct++
}
return res
}
55.跳跃游戏(4)
给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个位置。
示例 1:输入: [2,3,1,1,4] 输出: true
解释: 我们可以先跳 1 步，从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。
示例 2:输入: [3,2,1,0,4] 输出: false
解释: 无论怎样，你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 ，
所以你永远不可能到达最后一个位置。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历-贪心 |
O(n) |
O(1) |
| 02 |
动态规划 |
O(n^2) |
O(n) |
| 03 |
遍历-贪心 |
O(n) |
O(1) |
| 04 |
遍历 |
O(n) |
O(1) |
func canJump(nums []int) bool {
j := len(nums) - 1
for i := len(nums) - 2; i >= 0; i-- {
if nums[i]+i >= j {
j = i
}
}
return j <= 0
}
#
func canJump(nums []int) bool {
if len(nums) <= 1 {
return true
}
dp := make([]bool, len(nums))
dp[0] = true
for i := 1; i < len(nums); i++ {
flag := false
for j := 0; j < i; j++ {
if dp[j] && nums[j]+j >= i {
flag = true
break
}
}
dp[i] = flag
}
return dp[len(nums)-1]
}
#
func canJump(nums []int) bool {
max := 0
for i := 0; i < len(nums); i++ {
if i <= max {
if i+nums[i] > max {
max = i + nums[i]
}
if max >= len(nums)-1 {
return true
}
}
}
return false
}
#
func canJump(nums []int) bool {
zero := -1
for i := len(nums) - 2; i >= 0; i-- {
if zero > 0 {
if i+nums[i] > zero {
zero = -1
}
continue
}
if nums[i] == 0 {
zero = i
continue
}
}
return zero < 0
}
56.合并区间(2)
给出一个区间的集合，请合并所有重叠的区间。
示例 1:输入: [[1,3],[2,6],[8,10],[15,18]] 输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2:输入: [[1,4],[4,5]] 输出: [[1,5]]
解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
排序遍历 |
O(nlog(n)) |
O(n) |
| 02 |
排序-双指针 |
O(nlog(n)) |
O(n) |
func merge(intervals [][]int) [][]int {
res := make([][]int, 0)
if len(intervals) == 0 {
return nil
}
sort.Slice(intervals, func(i, j int) bool {
return intervals[i][0] < intervals[j][0]
})
res = append(res, intervals[0])
for i := 1; i < len(intervals); i++ {
arr := res[len(res)-1]
if intervals[i][0] > arr[1] {
res = append(res, intervals[i])
} else if intervals[i][1] > arr[1] {
res[len(res)-1][1] = intervals[i][1]
}
}
return res
}
#
func merge(intervals [][]int) [][]int {
res := make([][]int, 0)
if len(intervals) == 0 {
return nil
}
sort.Slice(intervals, func(i, j int) bool {
return intervals[i][0] < intervals[j][0]
})
for i := 0; i < len(intervals); {
end := intervals[i][1]
j := i + 1
for j < len(intervals) && intervals[j][0] <= end {
if intervals[j][1] > end {
end = intervals[j][1]
}
j++
}
res = append(res, []int{intervals[i][0], end})
i = j
}
return res
}
59.螺旋矩阵II(2)
给定一个正整数 n，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。
示例:输入: 3 输出:
[
[ 1, 2, 3 ],
[ 8, 9, 4 ],
[ 7, 6, 5 ]
]
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(n^2) |
O(n^2) |
| 02 |
遍历模拟 |
O(n^2) |
O(n^2) |
func generateMatrix(n int) [][]int {
res := make([][]int, n)
for i := 0; i < n; i++ {
res[i] = make([]int, n)
}
count := 1
level := 1
for count <= n*n {
top, bottom, left, right := level-1, n-level, level-1, n-level
for i := left; i <= right && left <= right; i++ {
res[top][i] = count
count++
}
for i := top + 1; i <= bottom && top <= bottom; i++ {
res[i][right] = count
count++
}
for i := right - 1; i >= left && left <= right; i-- {
res[bottom][i] = count
count++
}
for i := bottom - 1; i >= top+1 && top <= bottom; i-- {
res[i][left] = count
count++
}
level++
}
return res
}
#
func generateMatrix(n int) [][]int {
res := make([][]int, n)
for i := 0; i < n; i++ {
res[i] = make([]int, n)
}
count := 1
top, bottom, left, right := 0, n-1, 0, n-1
for count <= n*n {
for i := left; i <= right; i++ {
res[top][i] = count
count++
}
top++
for i := top; i <= bottom; i++ {
res[i][right] = count
count++
}
right--
for i := right; i >= left; i-- {
res[bottom][i] = count
count++
}
bottom--
for i := bottom; i >= top; i-- {
res[i][left] = count
count++
}
left++
}
return res
}
60.第k个排列(1)
给出集合 [1,2,3,…,n]，其所有元素共有 n! 种排列。
按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：
"123"
"132"
"213"
"231"
"312"
"321"
给定 n 和 k，返回第 k 个排列。
说明：
给定 n 的范围是 [1, 9]。
给定 k 的范围是[1, n!]。
示例 1:输入: n = 3, k = 3 输出: "213"
示例 2:输入: n = 4, k = 9 输出: "2314"
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历计算 |
O(n) |
O(n) |
func getPermutation(n int, k int) string {
res := ""
arr := []string{"1", "2", "3", "4", "5", "6", "7", "8", "9"}
times := make([]int, 0)
times = append(times, 1)
value := 1
for i := 1; i <= 9; i++ {
times = append(times, value*i)
value = value * i
}
k--
for n > 0 {
i := k / times[n-1]
k = k % times[n-1]
n--
res = res + arr[i]
arr = append(arr[:i], arr[i+1:]...)
}
return res
}
61.旋转链表(2)
给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。
示例 1:
输入: 1->2->3->4->5->NULL, k = 2
输出: 4->5->1->2->3->NULL
解释:
向右旋转 1 步: 5->1->2->3->4->NULL
向右旋转 2 步: 4->5->1->2->3->NULL
示例 2:
输入: 0->1->2->NULL, k = 4
输出: 2->0->1->NULL
解释:
向右旋转 1 步: 2->0->1->NULL
向右旋转 2 步: 1->2->0->NULL
向右旋转 3 步: 0->1->2->NULL
向右旋转 4 步: 2->0->1->NULL
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
统计遍历 |
O(n) |
O(1) |
| 02 |
数组辅助 |
O(n) |
O(n) |
func rotateRight(head *ListNode, k int) *ListNode {
if head == nil || k == 0 {
return head
}
temp := head
count := 1
for temp.Next != nil {
temp = temp.Next
count++
}
temp.Next = head
k = k % count
for i := 0; i < count-k; i++ {
temp = temp.Next
}
head, temp.Next = temp.Next, nil
return head
}
#
func rotateRight(head *ListNode, k int) *ListNode {
if head == nil || k == 0 {
return head
}
temp := head
count := 0
arr := make([]*ListNode, 0)
for temp != nil {
arr = append(arr, temp)
temp = temp.Next
count++
}
k = k % count
if k == 0 {
return head
}
arr[count-1].Next = head
temp = arr[count-1-k]
head, temp.Next = temp.Next, nil
return head
}
62.不同路径(4)
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
问总共有多少条不同的路径？
例如，上图是一个7 x 3 的网格。有多少可能的路径？
示例 1:输入: m = 3, n = 2 输出: 3
解释:
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向右 -> 向下
2. 向右 -> 向下 -> 向右
3. 向下 -> 向右 -> 向右
示例 2:输入: m = 7, n = 3 输出: 28
提示：
1 <= m, n <= 100
题目数据保证答案小于等于 2 * 10 ^ 9
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
动态规划 |
O(n^2) |
O(n^2) |
| 02 |
动态规划 |
O(n^2) |
O(n) |
| 03 |
数学 |
O(n) |
O(1) |
| 04 |
递归 |
O(n^2) |
O(n^2) |
func uniquePaths(m int, n int) int {
if m <= 0 || n <= 0 {
return 0
}
dp := make([][]int, n)
for i := 0; i < n; i++ {
dp[i] = make([]int, m)
dp[i][0] = 1
}
for i := 0; i < m; i++ {
dp[0][i] = 1
}
for i := 1; i < n; i++ {
for j := 1; j < m; j++ {
dp[i][j] = dp[i-1][j] + dp[i][j-1]
}
}
return dp[n-1][m-1]
}
#
func uniquePaths(m int, n int) int {
if m <= 0 || n <= 0 {
return 0
}
dp := make([]int, n)
for i := 0; i < n; i++ {
dp[i] = 1
}
for i := 1; i < m; i++ {
for j := 1; j < n; j++ {
dp[j] = dp[j] + dp[j-1]
}
}
return dp[n-1]
}
# 3
func uniquePaths(m int, n int) int {
if m == 1 || n == 1 {
return 1
}
if m > n {
m, n = n, m
}
a := 1
for i := 1; i <= m-1; i++ {
a = a * i
}
b := 1
for i := n; i <= m+n-2; i++ {
b = b * i
}
return b / a
}
# 4
var arr [][]int
func uniquePaths(m int, n int) int {
arr = make([][]int, n+1)
for i := 0; i <= n; i++ {
arr[i] = make([]int, m+1)
}
return dfs(m, n)
}
func dfs(m, n int) int {
if m <= 0 || n <= 0 {
return 0
}
if m == 1 || n == 1 {
return 1
}
if arr[n][m] > 0 {
return arr[n][m]
}
arr[n][m] = dfs(m, n-1) + dfs(m-1, n)
return arr[n][m]
}
63.不同路径II(3)
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
网格中的障碍物和空位置分别用 1 和 0 来表示。
说明：m 和 n 的值均不超过 100。
示例 1:
输入:
[
[0,0,0],
[0,1,0],
[0,0,0]
]
输出: 2
解释:
3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
动态规划 |
O(n^2) |
O(n^2) |
| 02 |
动态规划 |
O(n^2) |
O(n) |
| 03 |
动态规划 |
O(n^2) |
O(1) |
func uniquePathsWithObstacles(obstacleGrid [][]int) int {
n := len(obstacleGrid)
if n < 1 {
return 0
}
m := len(obstacleGrid[0])
if m < 1 {
return 0
}
if obstacleGrid[0][0] == 1 {
return 0
}
dp := make([][]int, n)
for i := 0; i < n; i++ {
dp[i] = make([]int, m)
for j := 0; j < m; j++ {
if i == 0 && j == 0 {
dp[i][j] = 1
} else if i == 0 && j != 0 {
if obstacleGrid[i][j] == 0 {
dp[i][j] = dp[i][j-1]
}
} else if i != 0 && j == 0 {
if obstacleGrid[i][j] == 0 {
dp[i][j] = dp[i-1][j]
}
} else {
if obstacleGrid[i][j] == 0 {
dp[i][j] = dp[i-1][j] + dp[i][j-1]
}
}
}
}
return dp[n-1][m-1]
}
# 2
func uniquePathsWithObstacles(obstacleGrid [][]int) int {
n := len(obstacleGrid)
if n < 1 {
return 0
}
m := len(obstacleGrid[0])
if m < 1 {
return 0
}
if obstacleGrid[0][0] == 1 {
return 0
}
dp := make([]int, m)
dp[0] = 1
for i := 0; i < n; i++ {
for j := 0; j < m; j++ {
if obstacleGrid[i][j] == 1 {
dp[j] = 0
continue
}
if j >= 1 && obstacleGrid[i][j-1] == 0 {
dp[j] = dp[j] + dp[j-1]
}
}
}
return dp[m-1]
}
# 3
func uniquePathsWithObstacles(obstacleGrid [][]int) int {
n := len(obstacleGrid)
if n < 1 {
return 0
}
m := len(obstacleGrid[0])
if m < 1 {
return 0
}
if obstacleGrid[0][0] == 1 {
return 0
}
for i := 0; i < n; i++ {
for j := 0; j < m; j++ {
if obstacleGrid[i][j] == 1 {
obstacleGrid[i][j] = 0
continue
}
if i == 0 {
if j == 0 {
obstacleGrid[i][j] = 1
} else {
obstacleGrid[i][j] += obstacleGrid[i][j-1]
}
} else {
if j == 0 {
obstacleGrid[i][j] += obstacleGrid[i-1][j]
} else {
obstacleGrid[i][j] += obstacleGrid[i][j-1] + obstacleGrid[i-1][j]
}
}
}
}
return obstacleGrid[n-1][m-1]
}
64.最小路径和(4)
给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
示例:
输入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 7解释: 因为路径 1→3→1→1→1 的总和最小。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
动态规划 |
O(n^2) |
O(n^2) |
| 02 |
动态规划 |
O(n^2) |
O(1) |
| 03 |
动态规划 |
O(n^2) |
O(n) |
| 04 |
递归 |
O(n^2) |
O(n^2) |
func minPathSum(grid [][]int) int {
n := len(grid)
if n == 0 {
return 0
}
m := len(grid[0])
dp := make([][]int, n)
for i := 0; i < n; i++ {
dp[i] = make([]int, m)
}
dp[0][0] = grid[0][0]
for i := 0; i < n; i++ {
for j := 0; j < m; j++ {
if i == 0 && j != 0 {
dp[i][j] = dp[i][j-1] + grid[i][j]
} else if i != 0 && j == 0 {
dp[i][j] = dp[i-1][j] + grid[i][j]
} else if i != 0 && j != 0 {
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
}
}
}
return dp[n-1][m-1]
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
#
func minPathSum(grid [][]int) int {
n := len(grid)
if n == 0 {
return 0
}
m := len(grid[0])
for i := 0; i < n; i++ {
for j := 0; j < m; j++ {
if i == 0 && j != 0 {
grid[i][j] = grid[i][j-1] + grid[i][j]
} else if i != 0 && j == 0 {
grid[i][j] = grid[i-1][j] + grid[i][j]
} else if i != 0 && j != 0 {
grid[i][j] = min(grid[i-1][j], grid[i][j-1]) + grid[i][j]
}
}
}
return grid[n-1][m-1]
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
# 3
func minPathSum(grid [][]int) int {
n := len(grid)
if n == 0 {
return 0
}
m := len(grid[0])
dp := make([]int, m)
dp[0] = grid[0][0]
for i := 1; i < m; i++ {
dp[i] = dp[i-1] + grid[0][i]
}
for i := 1; i < n; i++ {
dp[0] = dp[0] + grid[i][0]
for j := 1; j < m; j++ {
dp[j] = min(dp[j-1], dp[j]) + grid[i][j]
}
}
return dp[m-1]
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
# 4
var arr [][]int
func minPathSum(grid [][]int) int {
n := len(grid)
if n == 0 {
return 0
}
m := len(grid[0])
arr = make([][]int, n)
for i := 0; i < n; i++ {
arr[i] = make([]int, m)
}
return dfs(grid, n-1, m-1)
}
func dfs(grid [][]int, n, m int) int {
if m == 0 && n == 0 {
arr[0][0] = grid[0][0]
return grid[0][0]
}
if n == 0 {
return grid[0][m] + dfs(grid, 0, m-1)
}
if m == 0 {
return grid[n][0] + dfs(grid, n-1, 0)
}
if arr[n][m] > 0 {
return arr[n][m]
}
arr[n][m] = min(dfs(grid, n-1, m), dfs(grid, n, m-1)) + grid[n][m]
return arr[n][m]
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
71.简化路径(2)
以 Unix 风格给出一个文件的绝对路径，你需要简化它。或者换句话说，将其转换为规范路径。
在 Unix 风格的文件系统中，一个点（.）表示当前目录本身；
此外，两个点 （..） 表示将目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。
更多信息请参阅：Linux / Unix中的绝对路径 vs 相对路径
请注意，返回的规范路径必须始终以斜杠 / 开头，并且两个目录名之间必须只有一个斜杠 /。
最后一个目录名（如果存在）不能以 / 结尾。此外，规范路径必须是表示绝对路径的最短字符串。
示例 1：输入："/home/" 输出："/home"
解释：注意，最后一个目录名后面没有斜杠。
示例 2：输入："/../" 输出："/"
解释：从根目录向上一级是不可行的，因为根是你可以到达的最高级。
示例 3：输入："/home//foo/" 输出："/home/foo"
解释：在规范路径中，多个连续斜杠需要用一个斜杠替换。
示例 4：输入："/a/./b/../../c/" 输出："/c"
示例 5：输入："/a/../../b/../c//.//" 输出："/c"
示例 6：输入："/a//b////c/d//././/.." 输出："/a/b/c"
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
栈辅助 |
O(n) |
O(n) |
| 02 |
内置函数 |
O(n) |
O(n) |
func simplifyPath(path string) string {
stack := make([]string, 0)
arr := strings.Split(path, "/")
for i := 0; i < len(arr); i++ {
if arr[i] == "." || arr[i] == "" {
continue
}
if arr[i] == ".." {
if len(stack) > 0 {
stack = stack[:len(stack)-1]
}
} else {
stack = append(stack, arr[i])
}
}
return "/" + strings.Join(stack, "/")
}
#
func simplifyPath(path string) string {
return filepath.Clean(path)
}
73.矩阵置零(4)
给定一个 m x n 的矩阵，如果一个元素为 0，则将其所在行和列的所有元素都设为 0。请使用原地算法。
示例 1:
输入:
[
[1,1,1],
[1,0,1],
[1,1,1]
]
输出:
[
[1,0,1],
[0,0,0],
[1,0,1]
]
示例 2:
输入:
[
[0,1,2,0],
[3,4,5,2],
[1,3,1,5]
]
输出:
[
[0,0,0,0],
[0,4,5,0],
[0,3,1,0]
]
进阶:
一个直接的解决方案是使用 O(mn) 的额外空间，但这并不是一个好的解决方案。
一个简单的改进方案是使用 O(m + n) 的额外空间，但这仍然不是最好的解决方案。
你能想出一个常数空间的解决方案吗？
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
哈希辅助 |
O(n^2) |
O(n) |
| 02 |
暴力法 |
O(n^4) |
O(1) |
| 03 |
遍历 |
O(n^2) |
O(1) |
| 04 |
遍历 |
O(n^2) |
O(1) |
func setZeroes(matrix [][]int) {
x := make(map[int]int)
y := make(map[int]int)
for i := 0; i < len(matrix); i++ {
for j := 0; j < len(matrix[i]); j++ {
if matrix[i][j] == 0 {
x[i] = 1
y[j] = 1
}
}
}
for i := 0; i < len(matrix); i++ {
for j := 0; j < len(matrix[i]); j++ {
if x[i] == 1 || y[j] == 1 {
matrix[i][j] = 0
}
}
}
}
#
func setZeroes(matrix [][]int) {
m := make(map[[2]int]bool)
for i := 0; i < len(matrix); i++ {
for j := 0; j < len(matrix[i]); j++ {
if matrix[i][j] == math.MinInt32 {
m[[2]int{i, j}] = true
}
}
}
for i := 0; i < len(matrix); i++ {
for j := 0; j < len(matrix[i]); j++ {
if matrix[i][j] == 0 {
for k := 0; k < len(matrix); k++ {
for l := 0; l < len(matrix[k]); l++ {
if (k == i || l == j) && matrix[k][l] != 0 {
delete(m, [2]int{k, l})
matrix[k][l] = math.MinInt32
}
}
}
}
}
}
for i := 0; i < len(matrix); i++ {
for j := 0; j < len(matrix[i]); j++ {
if matrix[i][j] == math.MinInt32 && m[[2]int{i, j}] == false {
matrix[i][j] = 0
}
}
}
}
# 3
func setZeroes(matrix [][]int) {
flag := false
for i := 0; i < len(matrix); i++ {
if matrix[i][0] == 0 {
flag = true
}
for j := 1; j < len(matrix[i]); j++ {
if matrix[i][j] == 0 {
matrix[i][0] = 0
matrix[0][j] = 0
}
}
}
for i := 1; i < len(matrix); i++ {
for j := 1; j < len(matrix[i]); j++ {
if matrix[i][0] == 0 || matrix[0][j] == 0 {
matrix[i][j] = 0
}
}
}
if matrix[0][0] == 0 {
for j := 0; j < len(matrix[0]); j++ {
matrix[0][j] = 0
}
}
if flag == true {
for i := 0; i < len(matrix); i++ {
matrix[i][0] = 0
}
}
}
# 4
func setZeroes(matrix [][]int) {
flag := false
for i := 0; i < len(matrix); i++ {
if matrix[i][0] == 0 {
flag = true
}
for j := 1; j < len(matrix[i]); j++ {
if matrix[i][j] == 0 {
matrix[i][0] = 0
matrix[0][j] = 0
}
}
}
for i := len(matrix) - 1; i >= 0; i-- {
for j := len(matrix[i]) - 1; j >= 1; j-- {
if matrix[i][0] == 0 || matrix[0][j] == 0 {
matrix[i][j] = 0
}
}
}
if flag == true {
for i := 0; i < len(matrix); i++ {
matrix[i][0] = 0
}
}
}
74.搜索二维矩阵(6)
编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：
每行中的整数从左到右按升序排列。
每行的第一个整数大于前一行的最后一个整数。
示例 1:输入:
matrix = [
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
target = 3
输出: true
示例 2:输入:
matrix = [
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
target = 13
输出: false
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
暴力法 |
O(n^2) |
O(1) |
| 02 |
暴力法-优化 |
O(n^2) |
O(1) |
| 03 |
二分查找 |
O(nlog(n)) |
O(1) |
| 04 |
左下角查找 |
O(n) |
O(1) |
| 05 |
右上角查找 |
O(n) |
O(1) |
| 06 |
内置函数 |
O(n^2) |
O(1) |
func searchMatrix(matrix [][]int, target int) bool {
if len(matrix) == 0 {
return false
}
if len(matrix[0]) == 0 {
return false
}
for i := 0; i < len(matrix); i++ {
for j := 0; j < len(matrix[i]); j++ {
if matrix[i][j] == target {
return true
}
}
}
return false
}
# 2
func searchMatrix(matrix [][]int, target int) bool {
if len(matrix) == 0 {
return false
}
if len(matrix[0]) == 0 {
return false
}
for i := 0; i < len(matrix); i++ {
if matrix[i][0] <= target && matrix[i][len(matrix[i])-1] >= target {
for j := 0; j < len(matrix[i]); j++ {
if matrix[i][j] == target {
return true
}
}
}
}
return false
}
# 3
func searchMatrix(matrix [][]int, target int) bool {
if len(matrix) == 0 {
return false
}
if len(matrix[0]) == 0 {
return false
}
for i := 0; i < len(matrix); i++ {
if matrix[i][0] <= target && matrix[i][len(matrix[i])-1] >= target {
res := binarySearch(matrix[i], target)
if res == true {
return true
}
}
}
return false
}
func binarySearch(arr []int, target int) bool {
left := 0
right := len(arr) - 1
for left <= right {
mid := left + (right-left)/2
if arr[mid] == target {
return true
} else if arr[mid] > target {
right = mid - 1
} else {
left = mid + 1
}
}
return false
}
# 4
func searchMatrix(matrix [][]int, target int) bool {
if len(matrix) == 0 {
return false
}
if len(matrix[0]) == 0 {
return false
}
i := len(matrix) - 1
j := 0
for i >= 0 && j < len(matrix[0]) {
if matrix[i][j] == target {
return true
} else if matrix[i][j] > target {
i--
} else {
j++
}
}
return false
}
# 5
func searchMatrix(matrix [][]int, target int) bool {
if len(matrix) == 0 {
return false
}
if len(matrix[0]) == 0 {
return false
}
i := 0
j := len(matrix[0]) - 1
for j >= 0 && i < len(matrix) {
if matrix[i][j] == target {
return true
} else if matrix[i][j] > target {
j--
} else {
i++
}
}
return false
}
# 6
func searchMatrix(matrix [][]int, target int) bool {
if len(matrix) == 0 {
return false
}
if len(matrix[0]) == 0 {
return false
}
for i := 0; i < len(matrix); i++ {
index := sort.SearchInts(matrix[i], target)
if index < len(matrix[i]) && target == matrix[i][index] {
return true
}
}
return false
}
75.颜色分类(3)
给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，
使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
注意:
不能使用代码库中的排序函数来解决这道题。
示例:输入: [2,0,2,1,1,0] 输出: [0,0,1,1,2,2]
进阶：
一个直观的解决方案是使用计数排序的两趟扫描算法。
首先，迭代计算出0、1 和 2 元素的个数，然后按照0、1、2的排序，重写当前数组。
你能想出一个仅使用常数空间的一趟扫描算法吗？
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
排序 |
O(nlog(n)) |
O(1) |
| 02 |
双指针 |
O(n) |
O(1) |
| 03 |
数组辅助 |
O(n) |
O(1) |
func sortColors(nums []int) {
sort.Ints(nums)
}
# 2
func sortColors(nums []int) {
left := 0
right := len(nums) - 1
for i := 0; i <= right; i++ {
if nums[i] == 0 {
nums[left], nums[i] = nums[i], nums[left]
left++
} else if nums[i] == 2 {
nums[right], nums[i] = nums[i], nums[right]
right--
i--
}
}
}
# 3
func sortColors(nums []int) {
arr := make([]int, 3)
for i := 0; i < len(nums); i++ {
arr[nums[i]]++
}
count := 0
for i := 0; i < len(arr); i++ {
for j := 0; j < arr[i]; j++ {
nums[count] = i
count++
}
}
}
77.组合(5)
给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。
示例:输入: n = 4, k = 2 输出:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
回溯-递归 |
O(kC(n,k)) |
O(C(n,k)) |
| 02 |
回溯 |
O(kC(n,k)) |
O(C(n,k)) |
| 03 |
回溯 |
O(kC(n,k)) |
O(C(n,k)) |
| 04 |
迭代 |
O(kC(n,k)) |
O(C(n,k)) |
| 05 |
回溯 |
O(kC(n,k)) |
O(C(n,k)) |
var res [][]int
func combine(n int, k int) [][]int {
res = make([][]int, 0)
nums := make([]int, 0)
for i := 1; i <= n; i++ {
nums = append(nums, i)
}
dfs(nums, 0, k)
return res
}
func dfs(nums []int, index, k int) {
if index == k {
temp := make([]int, k)
copy(temp, nums[:k])
res = append(res, temp)
return
}
for i := index; i < len(nums); i++ {
if index == 0 || nums[i] > nums[index-1] {
nums[i], nums[index] = nums[index], nums[i]
dfs(nums, index+1, k)
nums[i], nums[index] = nums[index], nums[i]
}
}
}
# 2
var res [][]int
func combine(n int, k int) [][]int {
res = make([][]int, 0)
dfs(n, k, 1, make([]int, 0))
return res
}
func dfs(n, k, index int, arr []int) {
if len(arr) == k {
temp := make([]int, k)
copy(temp, arr)
res = append(res, temp)
return
}
for i := index; i <= n; i++ {
arr = append(arr, i)
dfs(n, k, i+1, arr)
arr = arr[:len(arr)-1]
}
}
# 3
var res [][]int
func combine(n int, k int) [][]int {
res = make([][]int, 0)
nums := make([]int, 0)
for i := 1; i <= n; i++ {
nums = append(nums, i)
}
dfs(nums, 0, k, make([]int, 0))
return res
}
func dfs(nums []int, index, k int, arr []int) {
if len(arr) == k {
temp := make([]int, k)
copy(temp, arr)
res = append(res, temp)
return
}
for i := index; i < len(nums); i++ {
arr = append(arr, nums[i])
dfs(nums, i+1, k, arr)
arr = arr[:len(arr)-1]
}
}
# 4
func combine(n int, k int) [][]int {
res := make([][]int, 0)
arr := make([]int, 0)
for i := 1; i <= k; i++ {
arr = append(arr, 0)
}
i := 0
for i >= 0 {
arr[i]++
if arr[i] > n {
i--
} else if i == k-1 {
temp := make([]int, k)
copy(temp, arr)
res = append(res, temp)
} else {
i++
arr[i] = arr[i-1]
}
}
return res
}
# 5
var res [][]int
func combine(n int, k int) [][]int {
res = make([][]int, 0)
dfs(n, k, 1, make([]int, 0))
return res
}
func dfs(n, k, index int, arr []int) {
if index > n+1 {
return
}
if len(arr) == k {
temp := make([]int, k)
copy(temp, arr)
res = append(res, temp)
return
}
dfs(n, k, index+1, arr)
arr = append(arr, index)
dfs(n, k, index+1, arr)
}
78.子集(4)
给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。
示例:输入: nums = [1,2,3] 输出:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
回溯 |
O(n*2^n) |
O(n*2^n) |
| 02 |
迭代 |
O(n*2^n) |
O(n*2^n) |
| 03 |
位运算 |
O(n*2^n) |
O(n*2^n) |
| 04 |
回溯 |
O(n*2^n) |
O(n*2^n) |
var res [][]int
func subsets(nums []int) [][]int {
res = make([][]int, 0)
dfs(nums, make([]int, 0), 0)
return res
}
func dfs(nums []int, arr []int, level int) {
temp := make([]int, len(arr))
copy(temp, arr)
res = append(res, temp)
for i := level; i < len(nums); i++ {
dfs(nums, append(arr, nums[i]), i+1)
}
}
# 2
func subsets(nums []int) [][]int {
res := make([][]int, 0)
res = append(res, []int{})
for i := 0; i < len(nums); i++ {
temp := make([][]int, len(res))
for key, value := range res {
value = append(value, nums[i])
temp[key] = append(temp[key], value...)
}
for _, v := range temp {
res = append(res, v)
}
}
return res
}
# 3
func subsets(nums []int) [][]int {
res := make([][]int, 0)
n := len(nums)
left := 1 << n
right := 1 << (n + 1)
for i := left; i < right; i++ {
temp := make([]int, 0)
for j := 0; j < n; j++ {
if i&(1<<j) != 0 {
temp = append(temp, nums[j])
}
}
res = append(res, temp)
}
return res
}
# 4
var res [][]int
func subsets(nums []int) [][]int {
res = make([][]int, 0)
dfs(nums, make([]int, 0), 0)
return res
}
func dfs(nums []int, arr []int, level int) {
if level >= len(nums) {
temp := make([]int, len(arr))
copy(temp, arr)
res = append(res, temp)
return
}
dfs(nums, arr, level+1)
dfs(nums, append(arr, nums[level]), level+1)
}
79.单词搜索(2)
给定一个二维网格和一个单词，找出该单词是否存在于网格中。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。
同一个单元格内的字母不允许被重复使用。
示例:board =
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]
给定 word = "ABCCED", 返回 true
给定 word = "SEE", 返回 true
给定 word = "ABCB", 返回 false
提示：
board 和 word 中只包含大写和小写英文字母。
1 <= board.length <= 200
1 <= board[i].length <= 200
1 <= word.length <= 10^3
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
深度优先搜索+回溯 |
O(n^2) |
O(n) |
| 02 |
深度优先搜索+回溯+数组辅助 |
O(n^2) |
O(n^2) |
func exist(board [][]byte, word string) bool {
for i := 0; i < len(board); i++ {
for j := 0; j < len(board[0]); j++ {
if dfs(board, i, j, word, 0) {
return true
}
}
}
return false
}
func dfs(board [][]byte, i, j int, word string, level int) bool {
if i < 0 || i >= len(board) || j < 0 || j >= len(board[0]) ||
board[i][j] != word[level] {
return false
}
if level == len(word)-1 {
return true
}
temp := board[i][j]
board[i][j] = ' '
res := dfs(board, i+1, j, word, level+1) ||
dfs(board, i-1, j, word, level+1) ||
dfs(board, i, j+1, word, level+1) ||
dfs(board, i, j-1, word, level+1)
board[i][j] = temp
return res
}
#
func exist(board [][]byte, word string) bool {
visited := make([][]bool, len(board))
for i := 0; i < len(board); i++ {
visited[i] = make([]bool, len(board[0]))
}
for i := 0; i < len(board); i++ {
for j := 0; j < len(board[0]); j++ {
if dfs(board, i, j, word, 0, visited) {
return true
}
}
}
return false
}
func dfs(board [][]byte, i, j int, word string, level int, visited [][]bool) bool {
res := false
if i >= 0 && i < len(board) && j >= 0 && j < len(board[0]) &&
visited[i][j] == false && board[i][j] == word[level] {
if level == len(word)-1 {
return true
}
visited[i][j] = true
level = level + 1
res = dfs(board, i+1, j, word, level, visited) ||
dfs(board, i-1, j, word, level, visited) ||
dfs(board, i, j+1, word, level, visited) ||
dfs(board, i, j-1, word, level, visited)
if !res {
visited[i][j] = false
level = level - 1
}
}
return res
}
80.删除排序数组中的重复项II(2)
给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素最多出现两次，返回移除后数组的新长度。
不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
示例 1:给定 nums = [1,1,1,2,2,3],
函数应返回新长度 length = 5, 并且原数组的前五个元素被修改为 1, 1, 2, 2, 3 。
你不需要考虑数组中超出新长度后面的元素。
示例 2:给定 nums = [0,0,1,1,1,1,2,3,3],
函数应返回新长度 length = 7, 并且原数组的前五个元素被修改为 0, 0, 1, 1, 2, 3, 3 。
你不需要考虑数组中超出新长度后面的元素。
说明:为什么返回数值是整数，但输出的答案是数组呢?
请注意，输入数组是以“引用”方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。
你可以想象内部操作如下:
// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
int len = removeDuplicates(nums);
// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。
for (int i = 0; i < len; i++) {
print(nums[i]);
}
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
双指针 |
O(n) |
O(1) |
| 02 |
双指针 |
O(n) |
O(1) |
func removeDuplicates(nums []int) int {
if len(nums) == 0 {
return 0
}
if len(nums) == 1 {
return 1
}
n := 2
i := n
for j := n; j < len(nums); j++ {
if nums[i-n] != nums[j] {
nums[i] = nums[j]
i++
}
}
return i
}
#
func removeDuplicates(nums []int) int {
if len(nums) == 0 {
return 0
}
prev := nums[0]
count := 1
j := 1
for i := 1; i < len(nums); i++ {
if nums[i] == prev {
count = count + 1
} else {
count = 1
prev = nums[i]
}
if count <= 2 {
nums[j] = nums[i]
j++
}
}
return j
}
81.搜索旋转排序数组II(2)
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0,0,1,2,2,5,6] 可能变为 [2,5,6,0,0,1,2] )。
编写一个函数来判断给定的目标值是否存在于数组中。若存在返回 true，否则返回 false。
示例 1:输入: nums = [2,5,6,0,0,1,2], target = 0 输出: true
示例 2:输入: nums = [2,5,6,0,0,1,2], target = 3 输出: false
进阶:
这是 搜索旋转排序数组 的延伸题目，本题中的 nums 可能包含重复元素。
这会影响到程序的时间复杂度吗？会有怎样的影响，为什么？
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(n) |
O(1) |
| 02 |
二分查找 |
O(log(n)) |
O(1) |
func search(nums []int, target int) bool {
for i := 0; i < len(nums); i++ {
if target == nums[i] {
return true
}
}
return false
}
#
func search(nums []int, target int) bool {
left, right := 0, len(nums)-1
for left <= right {
for left < right && nums[left] == nums[left+1] {
left++
}
for left < right && nums[right] == nums[right-1] {
right--
}
mid := left + (right-left)/2
if nums[mid] == target {
return true
}
if nums[left] <= nums[mid] {
if nums[left] <= target && target < nums[mid] {
right = mid - 1
} else {
left = mid + 1
}
} else {
if nums[mid] < target && target <= nums[right] {
left = mid + 1
} else {
right = mid - 1
}
}
}
return false
}
82.删除排序链表中的重复元素II(3)
给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。
示例 1:输入: 1->2->3->3->4->4->5 输出: 1->2->5
示例 2:输入: 1->1->1->2->3 输出: 2->3
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(n) |
O(1) |
| 02 |
递归 |
O(n) |
O(n) |
| 03 |
双指针 |
O(n) |
O(1) |
func deleteDuplicates(head *ListNode) *ListNode {
if head == nil || head.Next == nil {
return head
}
temp := &ListNode{Next: head}
cur := temp
value := 0
for cur.Next != nil && cur.Next.Next != nil {
if cur.Next.Val == cur.Next.Next.Val {
value = cur.Next.Val
for cur.Next != nil && cur.Next.Val == value {
cur.Next = cur.Next.Next
}
} else {
cur = cur.Next
}
}
return temp.Next
}
#
func deleteDuplicates(head *ListNode) *ListNode {
if head == nil || head.Next == nil {
return head
}
flag := false
for head.Next != nil && head.Val == head.Next.Val{
head = head.Next
flag = true
}
head.Next = deleteDuplicates(head.Next)
if flag{
return head.Next
}
return head
}
#
func deleteDuplicates(head *ListNode) *ListNode {
if head == nil || head.Next == nil {
return head
}
flag := false
for head.Next != nil && head.Val == head.Next.Val{
head = head.Next
flag = true
}
head.Next = deleteDuplicates(head.Next)
if flag{
return head.Next
}
return head
}
86.分隔链表(2)
给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。
你应当保留两个分区中每个节点的初始相对位置。
示例:
输入: head = 1->4->3->2->5->2, x = 3
输出: 1->2->2->4->3->5
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
双指针 |
O(n) |
O(1) |
| 02 |
数组辅助 |
O(n) |
O(n) |
func partition(head *ListNode, x int) *ListNode {
first := &ListNode{}
second := &ListNode{}
a := first
b := second
for head != nil {
if head.Val < x {
a.Next = head
a = head
} else {
b.Next = head
b = head
}
head = head.Next
}
b.Next = nil
a.Next = second.Next
return first.Next
}
#
func partition(head *ListNode, x int) *ListNode {
a := make([]*ListNode, 0)
b := make([]*ListNode, 0)
for head != nil {
if head.Val < x {
a = append(a, head)
} else {
b = append(b, head)
}
head = head.Next
}
temp := &ListNode{}
node := temp
for i := 0; i < len(a); i++ {
node.Next = a[i]
node = node.Next
}
for i := 0; i < len(b); i++ {
node.Next = b[i]
node = node.Next
}
node.Next = nil
return temp.Next
}
89.格雷编码(3)
格雷编码是一个二进制数字系统，在该系统中，两个连续的数值仅有一个位数的差异。
给定一个代表编码总位数的非负整数 n，打印其格雷编码序列。即使有多个不同答案，你也只需要返回其中一种。
格雷编码序列必须以 0 开头。
示例 1:输入: 2 输出: [0,1,3,2]
解释:
00 - 0
01 - 1
11 - 3
10 - 2
对于给定的 n，其格雷编码序列并不唯一。例如，[0,2,3,1] 也是一个有效的格雷编码序列。
00 - 0
10 - 2
11 - 3
01 - 1
示例 2:输入: 0 输出: [0]
解释: 我们定义格雷编码序列必须以 0 开头。
给定编码总位数为 n 的格雷编码序列，其长度为 2n。当 n = 0 时，长度为 20 = 1。
因此，当 n = 0 时，其格雷编码序列为 [0]。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历-推导 |
O(2^n) |
O(2^n) |
| 02 |
公式 |
O(2^n) |
O(2^n) |
| 03 |
遍历 |
O(2^n) |
O(2^n) |
func grayCode(n int) []int {
if n == 0 {
return []int{0}
}
res := []int{0, 1}
for i := 1; i < n; i++ {
temp := make([]int, 0)
value := 1 << i
for j := len(res) - 1; j >= 0; j-- {
temp = append(temp, res[j]+value)
}
res = append(res, temp...)
}
return res
}
# 2
func grayCode(n int) []int {
total := 1 << n
res := make([]int, 0)
for i := 0; i < total; i++ {
res = append(res, i^(i>>1))
}
return res
}
# 3
func grayCode(n int) []int {
if n == 0 {
return []int{0}
}
res := []int{0, 1}
for i := 1; i < n; i++ {
value := 1 << i
for j := len(res) - 1; j >= 0; j-- {
res= append(res, res[j]+value)
}
}
return res
}
90.子集II(2)
给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。
示例:输入: [1,2,2] 输出:
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
回溯 |
O(n*2^n) |
O(n*2^n) |
| 02 |
回溯 |
O(n*2^n) |
O(n*2^n) |
var res [][]int
func subsetsWithDup(nums []int) [][]int {
sort.Ints(nums)
res = make([][]int, 0)
dfs(nums, make([]int, 0), 0)
return res
}
func dfs(nums []int, arr []int, level int) {
temp := make([]int, len(arr))
copy(temp, arr)
res = append(res, temp)
for i := level; i < len(nums); i++ {
if i > level && nums[i] == nums[i-1] {
continue
}
arr = append(arr, nums[i])
dfs(nums, arr, i+1)
arr = arr[:len(arr)-1]
}
}
# 2
var res [][]int
func subsetsWithDup(nums []int) [][]int {
sort.Ints(nums)
res = make([][]int, 0)
dfs(nums, make([]int, 0))
return res
}
func dfs(nums []int, arr []int) {
temp := make([]int, len(arr))
copy(temp, arr)
res = append(res, temp)
for i := 0; i < len(nums); i++ {
if i > 0 && nums[i] == nums[i-1] {
continue
}
arr = append(arr, nums[i])
dfs(nums[i+1:], arr)
arr = arr[:len(arr)-1]
}
}
91.解码方法(3)
一条包含字母 A-Z 的消息通过以下方式进行了编码：
'A' -> 1
'B' -> 2
...
'Z' -> 26
给定一个只包含数字的非空字符串，请计算解码方法的总数。
示例 1:输入: "12" 输出: 2
解释: 它可以解码为 "AB"（1 2）或者 "L"（12）。
示例 2:输入: "226" 输出: 3
解释: 它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
动态规划 |
O(n) |
O(1) |
| 02 |
动态规划 |
O(n) |
O(n) |
| 03 |
递归 |
O(n) |
O(n) |
func numDecodings(s string) int {
if s[0] == '0' {
return 0
}
pre := 1
cur := 1
for i := 1; i < len(s); i++ {
temp := cur
if s[i] == '0' {
if s[i-1] == '1' || s[i-1] == '2' {
cur = pre
} else {
return 0
}
} else if s[i-1] == '1' ||
(s[i-1] == '2' && s[i] >= '1' && s[i] <= '6') {
cur = cur + pre
}
pre = temp
}
return cur
}
# 2
func numDecodings(s string) int {
if s[0] == '0' {
return 0
}
dp := make([]int, len(s)+1)
dp[0] = 1
for i := 0; i < len(s); i++{
if s[i] == '0' {
if i == 0 || s[i-1] == '1' || s[i-1] == '2' {
return 0
}
dp[i+1] = dp[i-1]
} else{
if i > 0 && (s[i-1] == '2' && s[i] >= '1' && s[i] <= '6') {
dp[i+1] = dp[i-1]+dp[i]
}else {
dp[i+1] = dp[i]
}
}
}
return dp[len(s)]
}
# 3
var m map[string]int
func numDecodings(s string) int {
m = make(map[string]int)
return dfs(s)
}
func dfs(s string) int {
if m[s] > 0 {
return m[s]
}
if len(s) == 0 {
return 1
}
if s[0] == '0' {
return 0
}
if len(s) == 1 {
return 1
}
if (s[0]-'0')*10+s[1]-'0' > 26 {
return dfs(s[1:])
}
m[s] = dfs(s[1:]) + dfs(s[2:])
return m[s]
}
92.反转链表II(2)
反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
说明: 1 ≤ m ≤ n ≤ 链表长度。
示例:输入: 1->2->3->4->5->NULL, m = 2, n = 4 输出: 1->4->3->2->5->NULL
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(n) |
O(1) |
| 02 |
递归 |
O(n) |
O(n) |
func reverseBetween(head *ListNode, m int, n int) *ListNode {
if m == n || head == nil {
return head
}
temp := &ListNode{Next: head}
prev := temp
for i := 1; i < m; i++ {
prev = prev.Next
}
head = prev.Next
for i := m; i < n; i++ {
next := head.Next
head.Next = next.Next
next.Next = prev.Next
prev.Next = next
}
return temp.Next
}
# 2
func reverseBetween(head *ListNode, m int, n int) *ListNode {
if m == 1 {
return reverseN(head, n)
}
head.Next = reverseBetween(head.Next, m-1, n-1)
return head
}
var next *ListNode
func reverseN(head *ListNode, n int) *ListNode {
if n == 1 {
next = head.Next
return head
}
prev := reverseN(head.Next, n-1)
head.Next.Next = head
head.Next = next
return prev
}
93.复原IP地址(2)
给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。
有效的 IP 地址正好由四个整数（每个整数位于 0 到 255 之间组成），整数之间用 '.' 分隔。
示例:输入: "25525511135" 输出: ["255.255.11.135", "255.255.111.35"]
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
回溯 |
O(1) |
O(1) |
| 02 |
暴力法 |
O(1) |
O(1) |
var res []string
func restoreIpAddresses(s string) []string {
res = make([]string, 0)
if len(s) < 4 || len(s) > 12 {
return nil
}
dfs(s, make([]string, 0), 0)
return res
}
func dfs(s string, arr []string, level int) {
if level == 4 {
if len(s) == 0 {
str := strings.Join(arr, ".")
res = append(res, str)
}
return
}
for i := 1; i <= 3; i++ {
if i <= len(s) {
value, _ := strconv.Atoi(s[:i])
if value <= 255 {
str := s[i:]
dfs(str, append(arr, s[:i]), level+1)
}
if value == 0 {
break
}
}
}
}
# 2
func restoreIpAddresses(s string) []string {
res := make([]string, 0)
if len(s) < 4 || len(s) > 12 {
return nil
}
for i := 1; i <= 3 && i < len(s)-2; i++ {
for j := i + 1; j <= i+3 && j < len(s)-1; j++ {
for k := j + 1; k <= j+3 && k < len(s); k++ {
if judge(s[:i]) && judge(s[i:j]) &&
judge(s[j:k]) && judge(s[k:]) {
res = append(res, s[:i]+"."+s[i:j]+"."+s[j:k]+"."+s[k:])
}
}
}
}
return res
}
func judge(s string) bool {
if len(s) > 1 && s[0] == '0' {
return false
}
value, _ := strconv.Atoi(s)
if value > 255 {
return false
}
return true
}
94.二叉树的中序遍历(3)
给定一个二叉树，返回它的中序 遍历。
示例:输入: [1,null,2,3]
1
\
2
/
3
输出: [1,3,2]
进阶: 递归算法很简单，你可以通过迭代算法完成吗？
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
递归 |
O(n) |
O(n) |
| 02 |
迭代 |
O(n) |
O(n) |
| 03 |
递归 |
O(n) |
O(n) |
func inorderTraversal(root *TreeNode) []int {
if root == nil {
return nil
}
left := inorderTraversal(root.Left)
right := inorderTraversal(root.Right)
res := left
res = append(res, root.Val)
res = append(res, right...)
return res
}
# 2
func inorderTraversal(root *TreeNode) []int {
if root == nil {
return nil
}
stack := make([]*TreeNode, 0)
res := make([]int, 0)
for len(stack) > 0 || root != nil {
for root != nil {
stack = append(stack, root)
root = root.Left
}
last := len(stack) - 1
res = append(res, stack[last].Val)
root = stack[last].Right
stack = stack[:last]
}
return res
}
# 3
var res []int
func inorderTraversal(root *TreeNode) []int {
res = make([]int, 0)
dfs(root)
return res
}
func dfs(root *TreeNode) {
if root != nil {
dfs(root.Left)
res = append(res, root.Val)
dfs(root.Right)
}
}
95.不同的二叉搜索树II(2)
给定一个整数 n，生成所有由 1 ... n 为节点所组成的 二叉搜索树 。
示例：输入：3
输出：
[
[1,null,3,2],
[3,2,null,1],
[3,1,null,null,2],
[2,1,3],
[1,null,2,null,3]
]
解释：以上的输出对应以下 5 种不同结构的二叉搜索树：
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3
提示：
0 <= n <= 8
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
递归 |
O(C(2n,n)/(n+1)) |
O(n) |
| 02 |
动态规划 |
O(C(2n,n)/(n+1)) |
O(n^2) |
func generateTrees(n int) []*TreeNode {
if n == 0 {
return nil
}
return dfs(1, n)
}
func dfs(left, right int) []*TreeNode {
if left > right {
return []*TreeNode{nil}
}
if left == right {
return []*TreeNode{
{Val: left},
}
}
arr := make([]*TreeNode, 0)
for i := left; i <= right; i++ {
leftTree := dfs(left, i-1)
rightTree := dfs(i+1, right)
for j := 0; j < len(leftTree); j++ {
for k := 0; k < len(rightTree); k++ {
node := &TreeNode{Val: i}
node.Left = leftTree[j]
node.Right = rightTree[k]
arr = append(arr, node)
}
}
}
return arr
}
# 2
func generateTrees(n int) []*TreeNode {
if n == 0 {
return nil
}
dp := make([][]*TreeNode, n+1)
dp[1] = append(dp[1], &TreeNode{Val: 1})
for i := 2; i <= n; i++ {
for _, node := range dp[i-1]{
root := &TreeNode{Val:i}
root.Left = node
dp[i] = append(dp[i], copyTree(root))
root = node
temp := root
newNode := &TreeNode{Val:i}
for temp != nil{
newNode.Left = temp.Right
temp.Right = newNode
dp[i] = append(dp[i], copyTree(root))
temp.Right = newNode.Left
newNode.Left = nil
temp = temp.Right
}
}
}
return dp[n]
}
func copyTree(node *TreeNode) *TreeNode {
if node == nil {
return nil
}
newNode := &TreeNode{Val: node.Val}
newNode.Left = copyTree(node.Left)
newNode.Right = copyTree(node.Right)
return newNode
}
96.不同的二叉搜索树(3)
给定一个整数 n，求以 1 ... n 为节点组成的二叉搜索树有多少种？
示例:输入: 3 输出: 5
解释: 给定 n = 3, 一共有 5 种不同结构的二叉搜索树:
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
动态规划 |
O(n^2) |
O(n) |
| 02 |
公式 |
O(n) |
O(1) |
| 03 |
公式 |
O(n) |
O(1) |
func numTrees(n int) int {
dp := make([]int, n+1)
dp[0] =1
dp[1] =1
for i := 2; i <= n;i++{
for j := 1; j <= i; j++{
dp[i] = dp[i] + dp[j-1]*dp[i-j]
}
}
return dp[n]
}
#
func numTrees(n int) int {
c := 1
for i := 1; i < n;i++{
c = c * 2 * (2*i+1)/(i+2)
}
return c
}
#
func numTrees(n int) int {
c := 1
for i := 1; i <= n;i++{
c = c * (n+i)/i
}
return c/(n+1)
}
98.验证二叉搜索树(5)
给定一个二叉树，判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征：
节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
示例 1:输入:
2
/ \
1 3
输出: true
示例 2:输入:
5
/ \
1 4
/ \
3 6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
根节点的值为 5 ，但是其右子节点值为 4 。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
递归 |
O(n) |
O(log(n)) |
| 02 |
递归 |
O(n) |
O(n) |
| 03 |
迭代 |
O(n) |
O(n) |
| 04 |
迭代 |
O(n) |
O(n) |
| 05 |
递归 |
O(n) |
O(log(n)) |
func isValidBST(root *TreeNode) bool {
return dfs(root, math.MinInt64, math.MaxInt64)
}
func dfs(root *TreeNode, left, right int) bool {
if root == nil {
return true
}
if left >= root.Val || right <= root.Val {
return false
}
return dfs(root.Left, left, root.Val) && dfs(root.Right, root.Val, right)
}
# 2
var res []int
func isValidBST(root *TreeNode) bool {
res = make([]int, 0)
dfs(root)
for i := 0; i < len(res)-1; i++ {
if res[i] >= res[i+1] {
return false
}
}
return true
}
func dfs(root *TreeNode) {
if root != nil {
dfs(root.Left)
res = append(res, root.Val)
dfs(root.Right)
}
}
# 3
func isValidBST(root *TreeNode) bool {
if root == nil {
return true
}
stack := make([]*TreeNode, 0)
res := make([]int, 0)
for len(stack) > 0 || root != nil {
for root != nil {
stack = append(stack, root)
root = root.Left
}
last := len(stack) - 1
res = append(res, stack[last].Val)
root = stack[last].Right
stack = stack[:last]
}
for i := 0; i < len(res)-1; i++ {
if res[i] >= res[i+1] {
return false
}
}
return true
}
# 4
func isValidBST(root *TreeNode) bool {
if root == nil {
return true
}
stack := make([]*TreeNode, 0)
pre := math.MinInt64
for len(stack) > 0 || root != nil {
for root != nil {
stack = append(stack, root)
root = root.Left
}
last := len(stack) - 1
if stack[last].Val <= pre {
return false
}
pre = stack[last].Val
root = stack[last].Right
stack = stack[:last]
}
return true
}
# 5
var pre int
func isValidBST(root *TreeNode) bool {
pre = math.MinInt64
return dfs(root)
}
func dfs(root *TreeNode) bool {
if root == nil {
return true
}
if dfs(root.Left) == false {
return false
}
if root.Val <= pre {
return false
}
pre = root.Val
return dfs(root.Right)
}
0001-1000-Hard
4.寻找两个正序数组的中位数(4)
给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。
请你找出这两个正序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
你可以假设 nums1 和 nums2 不会同时为空。
示例 1:nums1 = [1, 3] nums2 = [2]
则中位数是 2.0
示例 2:nums1 = [1, 2] nums2 = [3, 4]
则中位数是 (2 + 3)/2 = 2.5
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
排序 |
O(nlog(n)) |
O(n) |
| 02 |
二分查找 |
O(log(n)) |
O(1) |
| 03 |
遍历 |
O(n) |
O(1) |
| 04 |
二分查找 |
O(log(n)) |
O(1) |
func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
nums1 = append(nums1, nums2...)
sort.Ints(nums1)
if len(nums1)%2 == 1 {
return float64(nums1[len(nums1)/2])
}
return float64(nums1[len(nums1)/2]+nums1[len(nums1)/2-1]) / 2
}
# 2
func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
total := len(nums1) + len(nums2)
if total%2 == 1 {
mid := total / 2
return float64(getKth(nums1, nums2, mid+1))
}
mid1, mid2 := total/2-1, total/2
return float64(getKth(nums1, nums2, mid1+1)+getKth(nums1, nums2, mid2+1)) / 2.0
}
func getKth(nums1 []int, nums2 []int, k int) int {
a, b := 0, 0
for {
if a == len(nums1) {
return nums2[b+k-1]
}
if b == len(nums2) {
return nums1[a+k-1]
}
if k == 1 {
return min(nums1[a], nums2[b])
}
mid := k / 2
newA := min(a+mid, len(nums1)) - 1
newB := min(b+mid, len(nums2)) - 1
valueA, valueB := nums1[newA], nums2[newB]
if valueA < valueB {
k = k - (newA - a + 1)
a = newA + 1
} else {
k = k - (newB - b + 1)
b = newB + 1
}
}
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
# 3
func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
total := len(nums1) + len(nums2)
a, b := total/2, (total-1)/2
count := 0
res := 0
for i, j := 0, 0; i < len(nums1) || j < len(nums2); count++ {
if i < len(nums1) && (j == len(nums2) || nums1[i] < nums2[j]) {
if count == a {
res = res + nums1[i]
}
if count == b {
res = res + nums1[i]
}
i++
} else {
if count == a {
res = res + nums2[j]
}
if count == b {
res = res + nums2[j]
}
j++
}
}
return float64(res) / 2
}
# 4
func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
n, m := len(nums1), len(nums2)
if n > m {
return findMedianSortedArrays(nums2, nums1)
}
left, right := 0, n
a, b := 0, 0
for left <= right {
i := left + (right-left)/2
j := (n+m+1)/2 - i
if j != 0 && i != n && nums1[i] < nums2[j-1] {
left = i + 1
} else if i != 0 && j != m && nums1[i-1] > nums2[j] {
right = i - 1
} else {
if i == 0 {
a = nums2[j-1]
} else if j == 0 {
a = nums1[i-1]
} else {
a = max(nums1[i-1], nums2[j-1])
}
if (n+m)%2 == 1 {
return float64(a)
}
if i == n {
b = nums2[j]
} else if j == m {
b = nums1[i]
} else {
b = min(nums1[i], nums2[j])
}
return float64(a+b) / 2.0
}
}
return 0.0
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
10.正则表达式匹配(3)
给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
'.' 匹配任意单个字符
'*' 匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。
说明:
s 可能为空，且只包含从 a-z 的小写字母。
p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。
示例 1:输入:s = "aa" p = "a" 输出: false
解释: "a" 无法匹配 "aa" 整个字符串。
示例 2:输入: s = "aa" p = "a*" 输出: true
解释: 因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。
因此，字符串 "aa" 可被视为 'a' 重复了一次。
示例 3:输入: s = "ab" p = ".*" 输出: true
解释: ".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。
示例 4:输入:s = "aab"p = "c*a*b" 输出: true
解释: 因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。
示例 5:输入:s = "mississippi"p = "mis*is*p*." 输出: false
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
递归 |
O(n) |
O(n) |
| 02 |
动态规划 |
O(n^2) |
O(n^2) |
| 03 |
递归 |
O(n) |
O(n) |
func isMatch(s string, p string) bool {
return dfs(s, p, 0, 0)
}
func dfs(s string, p string, i, j int) bool {
if i >= len(s) && j >= len(p) {
return true
}
if i <= len(s) && j >= len(p) {
return false
}
if j+1 < len(p) && p[j+1] == '*' {
if (i < len(s) && p[j] == s[i]) || (p[j] == '.' && i < len(s)) {
return dfs(s, p, i+1, j+2) ||
dfs(s, p, i+1, j) ||
dfs(s, p, i, j+2)
} else {
return dfs(s, p, i, j+2)
}
}
if (i < len(s) && s[i] == p[j]) || (p[j] == '.' && i < len(s)) {
return dfs(s, p, i+1, j+1)
}
return false
}
# 2
func isMatch(s string, p string) bool {
dp := make([][]bool, len(p)+1)
for i := 0; i < len(p)+1; i++ {
dp[i] = make([]bool, len(s)+1)
}
dp[0][0] = true
for i := 2; i < len(p)+1; i++ {
if i%2 == 0 && p[i-1] == '*' {
dp[i][0] = dp[i-2][0]
}
}
for i := 1; i < len(p)+1; i++ {
for j := 1; j < len(s)+1; j++ {
if p[i-1] == s[j-1] || p[i-1] == '.' {
dp[i][j] = dp[i-1][j-1]
} else if p[i-1] == '*' {
if i > 1 {
if p[i-2] == s[j-1] || p[i-2] == '.' {
dp[i][j] = dp[i][j-1] || dp[i-2][j-1] || dp[i-2][j]
} else {
dp[i][j] = dp[i-2][j]
}
}
}
}
}
return dp[len(p)][len(s)]
}
# 3
func isMatch(s string, p string) bool {
if len(s) == 0 && len(p) == 0 {
return true
} else if len(p) == 0 {
return false
}
match := false
if len(s) > 0 && (s[0] == p[0] || p[0] == '.') {
match = true
}
if len(p) > 1 && p[1] == '*' {
return (match && isMatch(s[1:], p)) || isMatch(s, p[2:])
}
return match && isMatch(s[1:], p[1:])
}
23.合并K个排序链表(4)
合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。
示例:输入:
[
1->4->5,
1->3->4,
2->6
]
输出: 1->1->2->3->4->4->5->6
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
顺序合并 |
O(n^2) |
O(1) |
| 02 |
归并(分治)合并 |
O(nlog(n)) |
O(log(n)) |
| 03 |
堆辅助 |
O(nlog(n)) |
O(log(n)) |
| 04 |
自定义排序 |
O(nlog(n)) |
O(n) |
func mergeKLists(lists []*ListNode) *ListNode {
if len(lists) == 0 {
return nil
}
temp := &ListNode{}
for i := 0; i < len(lists); i++ {
temp.Next = mergeTwoLists(temp.Next, lists[i])
}
return temp.Next
}
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
res := &ListNode{}
temp := res
for l1 != nil && l2 != nil {
if l1.Val < l2.Val {
temp.Next = l1
l1 = l1.Next
} else {
temp.Next = l2
l2 = l2.Next
}
temp = temp.Next
}
if l1 != nil {
temp.Next = l1
} else {
temp.Next = l2
}
return res.Next
}
# 2
func mergeKLists(lists []*ListNode) *ListNode {
if len(lists) == 0 {
return nil
}
if len(lists) == 1 {
return lists[0]
}
first := mergeKLists(lists[:len(lists)/2])
second := mergeKLists(lists[len(lists)/2:])
return mergeTwoLists(first, second)
}
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
res := &ListNode{}
temp := res
for l1 != nil && l2 != nil {
if l1.Val < l2.Val {
temp.Next = l1
l1 = l1.Next
} else {
temp.Next = l2
l2 = l2.Next
}
temp = temp.Next
}
if l1 != nil {
temp.Next = l1
} else {
temp.Next = l2
}
return res.Next
}
# 3
func mergeKLists(lists []*ListNode) *ListNode {
if len(lists) == 0 {
return nil
}
var h IntHeap
heap.Init(&h)
for i := 0; i < len(lists); i++ {
if lists[i] != nil {
heap.Push(&h, lists[i])
}
}
res := &ListNode{}
temp := res
for h.Len() > 0 {
minItem := heap.Pop(&h).(*ListNode)
temp.Next = minItem
temp = temp.Next
if minItem.Next != nil {
heap.Push(&h, minItem.Next)
}
}
return res.Next
}
type IntHeap []*ListNode
func (h IntHeap) Len() int { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i].Val < h[j].Val }
func (h IntHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *IntHeap) Push(x interface{}) { *h = append(*h, x.(*ListNode)) }
func (h *IntHeap) Pop() interface{} {
old := *h
n := len(old)
x := old[n-1]
*h = old[0 : n-1]
return x
}
# 4
func mergeKLists(lists []*ListNode) *ListNode {
if len(lists) == 0 {
return nil
}
arr := make([]*ListNode, 0)
for i := 0; i < len(lists); i++ {
temp := lists[i]
for temp != nil {
arr = append(arr, temp)
temp = temp.Next
}
}
if len(arr) == 0 {
return nil
}
sort.Slice(arr, func(i, j int) bool {
return arr[i].Val < arr[j].Val
})
for i := 0; i < len(arr)-1; i++ {
arr[i].Next = arr[i+1]
}
arr[len(arr)-1].Next = nil
return arr[0]
}
25.K个一组翻转链表(4)
给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
k 是一个正整数，它的值小于或等于链表的长度。
如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
示例：
给你这个链表：1->2->3->4->5
当 k = 2 时，应当返回: 2->1->4->3->5
当 k = 3 时，应当返回: 3->2->1->4->5
说明：
你的算法只能使用常数的额外空间。
你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
递归 |
O(n) |
O(n) |
| 02 |
递归 |
O(n) |
O(n) |
| 03 |
遍历 |
O(n) |
O(1) |
| 04 |
遍历 |
O(n) |
O(1) |
func reverseKGroup(head *ListNode, k int) *ListNode {
length := getLength(head)
if length < k || k <= 1 {
return head
}
pre := &ListNode{}
cur := head
for i := 0; i < k; i++ {
temp := cur
cur = cur.Next
temp.Next = pre
pre = temp
}
head.Next = reverseKGroup(cur, k)
return pre
}
func getLength(head *ListNode) int {
if head == nil {
return 0
}
temp := head
res := 0
for temp != nil {
res++
temp = temp.Next
}
return res
}
# 2
func reverseKGroup(head *ListNode, k int) *ListNode {
res := 0
temp := head
for temp != nil {
res++
temp = temp.Next
}
if res < k || k <= 1 {
return head
}
pre := &ListNode{}
cur := head
for i := 0; i < k; i++ {
next := cur.Next
cur.Next = pre
pre = cur
cur = next
}
head.Next = reverseKGroup(cur, k)
return pre
}
# 3
func reverseKGroup(head *ListNode, k int) *ListNode {
res := &ListNode{Next: head}
prev := res
for head != nil {
tail := prev
for i := 0; i < k; i++ {
tail = tail.Next
if tail == nil {
return res.Next
}
}
next := tail.Next
head, tail = reverse(head, tail)
prev.Next = head
tail.Next = next
prev = tail
head = tail.Next
}
return res.Next
}
func reverse(head, tail *ListNode) (*ListNode, *ListNode) {
prev := tail.Next
temp := head
for prev != tail {
next := temp.Next
temp.Next = prev
prev = temp
temp = next
}
return tail, head
}
# 4
func reverseKGroup(head *ListNode, k int) *ListNode {
res := &ListNode{Next: head}
prev, end := res, res
for end.Next != nil {
for i := 0; i < k && end != nil; i++ {
end = end.Next
}
if end == nil {
break
}
start := prev.Next
next := end.Next
end.Next = nil
prev.Next = reverse(start)
start.Next = next
prev = start
end = prev
}
return res.Next
}
func reverse(head *ListNode) *ListNode {
var result *ListNode
for head != nil {
temp := head.Next
head.Next = result
result = head
head = temp
}
return result
}
30.串联所有单词的子串(2)
给定一个字符串 s 和一些长度相同的单词 words。
找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。
注意子串要与 words 中的单词完全匹配，中间不能有其他字符，但不需要考虑 words 中单词串联的顺序。
示例 1：输入：s = "barfoothefoobarman",words = ["foo","bar"] 输出：[0,9]
解释：从索引 0 和 9 开始的子串分别是 "barfoo" 和 "foobar" 。
输出的顺序不重要, [9,0] 也是有效答案。
示例 2：输入：s = "wordgoodgoodgoodbestword",words = ["word","good","best","word"]输出：[]
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(n^2) |
O(n) |
| 02 |
滑动窗口 |
O(n^2) |
O(n) |
func findSubstring(s string, words []string) []int {
res := make([]int, 0)
length,n := len(s),len(words)
if length == 0 || n == 0 || len(words[0]) == 0 {
return res
}
single := len(words[0])
m := make(map[string]int)
for i := 0; i < len(words); i++ {
m[words[i]]++
}
for i := 0; i <= length-n*single; i++ {
temp := make(map[string]int)
for j := 0; j < n; j++ {
l := i + j*single
str := s[l : l+single]
if _, ok := m[str]; !ok {
break
}
temp[str]++
if temp[str] > m[str] {
break
}
if compare(m, temp) == true {
res = append(res, i)
break
}
}
}
return res
}
func compare(m1, m2 map[string]int) bool {
if len(m1) != len(m2) {
return false
}
for k, v := range m1 {
if m2[k] != v {
return false
}
}
return true
}
# 2
func findSubstring(s string, words []string) []int {
res := make([]int, 0)
length := len(s)
n := len(words)
if length == 0 || n == 0 || len(words[0]) == 0 {
return res
}
single := len(words[0])
m := make(map[string]int)
for i := 0; i < len(words); i++ {
m[words[i]]++
}
for i := 0; i < single; i++ {
left, right, count := i, i, 0
temp := make(map[string]int)
for right+single <= length {
str := s[right : right+single]
right = right + single
if m[str] > 0 {
temp[str]++
if temp[str] == m[str] {
count++
}
}
if right-left == n*single {
if count == len(m) {
res = append(res, left)
}
leftStr := s[left : left+single]
left = left + single
if m[leftStr] > 0 {
if temp[leftStr] == m[leftStr] {
count--
}
temp[leftStr]--
}
}
}
}
return res
}
32.最长有效括号(4)
给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。
示例 1:输入: "(()"输出: 2
解释: 最长有效括号子串为 "()"
示例 2:输入: ")()())" 输出: 4
解释: 最长有效括号子串为 "()()"
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
栈辅助 |
O(n) |
O(n) |
| 02 |
动态规划 |
O(n) |
O(n) |
| 03 |
遍历 |
O(n) |
O(1) |
| 04 |
暴力法 |
O(n^2) |
O(1) |
func longestValidParentheses(s string) int {
res := 0
stack := make([]int, 0)
stack = append(stack, -1)
for i := 0; i < len(s); i++ {
if s[i] == '(' {
stack = append(stack, i)
} else {
stack = stack[:len(stack)-1]
if len(stack) == 0 {
stack = append(stack, i)
} else {
res = max(res, i-stack[len(stack)-1])
}
}
}
return res
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
# 2
func longestValidParentheses(s string) int {
res := 0
dp := make([]int, len(s))
for i := 1; i < len(s); i++ {
if s[i] == ')' {
if s[i-1] == '(' {
if i < 2 {
dp[i] = 2
} else {
dp[i] = dp[i-2] + 2
}
} else {
if i-dp[i-1] > 0 && s[i-dp[i-1]-1] == '(' {
if i-dp[i-1] < 2 {
dp[i] = dp[i-1] + 2
} else {
dp[i] = dp[i-1] + dp[i-dp[i-1]-2] + 2
}
}
}
}
res = max(res, dp[i])
}
return res
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
# 3
func longestValidParentheses(s string) int {
res := 0
left, right := 0, 0
for i := 0; i < len(s); i++ {
if s[i] == '(' {
left++
} else {
right++
}
if left == right {
res = max(res, 2*left)
} else if right > left {
left, right = 0, 0
}
}
left, right = 0, 0
for i := len(s) - 1; i >= 0; i-- {
if s[i] == '(' {
left++
} else {
right++
}
if left == right {
res = max(res, 2*left)
} else if left > right {
left, right = 0, 0
}
}
return res
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
# 4
func longestValidParentheses(s string) int {
res := 0
for i := 0; i < len(s); i++ {
count := 0
for j := i; j < len(s); j++ {
if s[j] == '(' {
count++
} else {
count--
}
if count < 0 {
break
}
if count == 0 {
res = max(res, j+1-i)
}
}
}
return res
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
37.解数独(2)
编写一个程序，通过已填充的空格来解决数独问题。
一个数独的解法需遵循如下规则：
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
空白格用 '.' 表示。
一个数独。
答案被标成红色。
Note:给定的数独序列只包含数字 1-9 和字符 '.' 。
你可以假设给定的数独只有唯一解。
给定数独永远是 9x9 形式的。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
回溯 |
O((9!)^9) |
O(1) |
| 02 |
回溯 |
O((9!)^9) |
O(1) |
var rows, cols, arrs [9][9]int
func solveSudoku(board [][]byte) {
rows = [9][9]int{}
cols = [9][9]int{}
arrs = [9][9]int{}
for i := 0; i < 9; i++ {
for j := 0; j < 9; j++ {
if board[i][j] != '.' {
num := board[i][j] - '1'
index := (i/3)*3 + j/3
rows[i][num] = 1
cols[j][num] = 1
arrs[index][num] = 1
}
}
}
dfs(board, 0)
}
func dfs(board [][]byte, index int) bool {
if index == 81 {
return true
}
row := index / 9
col := index % 9
c := (row/3)*3 + col/3
if board[row][col] != '.' {
return dfs(board, index+1)
}
for i := 0; i < 9; i++ {
if rows[row][i] == 1 || cols[col][i] == 1 || arrs[c][i] == 1 {
continue
}
board[row][col] = byte(i + '1')
rows[row][i], cols[col][i], arrs[c][i] = 1, 1, 1
if dfs(board, index+1) == true {
return true
}
rows[row][i], cols[col][i], arrs[c][i] = 0, 0, 0
board[row][col] = '.'
}
return false
}
# 2
func solveSudoku(board [][]byte) {
dfs(board, 0)
}
func dfs(board [][]byte, index int) bool {
if index == 81 {
return true
}
row := index / 9
col := index % 9
if board[row][col] != '.' {
return dfs(board, index+1)
}
for i := 0; i < 9; i++ {
board[row][col] = byte(i + '1')
if isValidSudoku(board) == false {
board[row][col] = '.'
continue
}
if dfs(board, index+1) == true {
return true
}
board[row][col] = '.'
}
return false
}
func isValidSudoku(board [][]byte) bool {
var row, col, arr [9][9]int
for i := 0; i < 9; i++ {
for j := 0; j < 9; j++ {
if board[i][j] != '.' {
num := board[i][j] - '1'
index := (i/3)*3 + j/3
if row[i][num] == 1 || col[j][num] == 1 || arr[index][num] == 1 {
return false
}
row[i][num] = 1
col[j][num] = 1
arr[index][num] = 1
}
}
}
return true
}
41.缺失的第一个正数(5)
给你一个未排序的整数数组，请你找出其中没有出现的最小的正整数。
示例 1:输入: [1,2,0] 输出: 3
示例 2:输入: [3,4,-1,1]输出: 2
示例 3:输入: [7,8,9,11,12]输出: 1
提示：你的算法的时间复杂度应为O(n)，并且只能使用常数级别的额外空间。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
标负 |
O(n) |
O(1) |
| 02 |
置换 |
O(n) |
O(1) |
| 03 |
哈希辅助 |
O(n) |
O(n) |
| 04 |
暴力法 |
O(n^2) |
O(1) |
| 05 |
桶 |
O(n) |
O(n) |
func firstMissingPositive(nums []int) int {
n := len(nums)
for i := 0; i < n; i++ {
if nums[i] <= 0 {
nums[i] = n + 1
}
}
for i := 0; i < n; i++ {
value := abs(nums[i])
if value <= n {
nums[value-1] = -abs(abs(nums[value-1]))
}
}
for i := 0; i < n; i++ {
if nums[i] > 0 {
return i + 1
}
}
return n + 1
}
func abs(a int) int {
if a >= 0 {
return a
}
return -a
}
# 2
func firstMissingPositive(nums []int) int {
n := len(nums)
for i := 0; i < n; i++ {
for nums[i] > 0 && nums[i] <= n && nums[nums[i]-1] != nums[i] {
nums[i], nums[nums[i]-1] = nums[nums[i]-1], nums[i]
}
}
for i := 0; i < n; i++ {
if nums[i] != i+1 {
return i + 1
}
}
return n + 1
}
# 3
func firstMissingPositive(nums []int) int {
n := len(nums)
m := make(map[int]int)
for i := 0; i < n; i++ {
m[nums[i]] = 1
}
for i := 1; i <= n; i++ {
if m[i] == 0 {
return i
}
}
return n + 1
}
# 4
func firstMissingPositive(nums []int) int {
n := len(nums)
for i := 1; i <= n; i++ {
flag := false
for j := 0; j < n; j++ {
if i == nums[j] {
flag = true
break
}
}
if flag == false {
return i
}
}
return n + 1
}
# 5
func firstMissingPositive(nums []int) int {
n := len(nums)
arr := make([]int, n+1)
for i := 0; i < n; i++ {
if 1 <= nums[i] && nums[i] <= n {
arr[nums[i]] = 1
}
}
for i := 1; i <= n; i++ {
if arr[i] == 0 {
return i
}
}
return n + 1
}
42.接雨水(4)
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，
在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 感谢 Marcos 贡献此图。
示例:输入: [0,1,0,2,1,0,1,3,2,1,2,1]输出: 6
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
暴力法 |
O(n^2) |
O(1) |
| 02 |
数组辅助 |
O(n) |
O(n) |
| 03 |
栈辅助 |
O(n) |
O(n) |
| 04 |
双指针 |
O(n) |
O(1) |
func trap(height []int) int {
res := 0
for i := 0; i < len(height); i++ {
left, right := 0, 0
for j := i; j >= 0; j-- {
left = max(left, height[j])
}
for j := i; j < len(height); j++ {
right = max(right, height[j])
}
area := min(left, right) - height[i]
res = res + area
}
return res
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
# 2
func trap(height []int) int {
res := 0
if len(height) == 0{
return 0
}
left := make([]int, len(height))
right := make([]int, len(height))
left[0] = height[0]
right[len(right)-1] = height[len(height)-1]
for i := 1; i < len(height); i++ {
left[i] = max(height[i], left[i-1])
}
for i := len(height) - 2; i >= 0; i-- {
right[i] = max(height[i], right[i+1])
}
for i := 0; i < len(height); i++ {
area := min(left[i], right[i]) - height[i]
res = res + area
}
return res
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
# 3
func trap(height []int) int {
res := 0
stack := make([]int, 0)
for i := 0; i < len(height); i++ {
for len(stack) > 0 && height[i] > height[stack[len(stack)-1]] {
bottom := height[stack[len(stack)-1]]
stack = stack[:len(stack)-1]
if len(stack) > 0 {
prev := stack[len(stack)-1]
h := min(height[i], height[prev]) - bottom
w := i - prev - 1
area := h * w
res = res + area
}
}
stack = append(stack, i)
}
return res
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
# 4
func trap(height []int) int {
res := 0
if len(height) == 0 {
return 0
}
left := 0
right := len(height) - 1
leftMax := 0
rightMax := 0
for left < right {
if height[left] < height[right] {
if height[left] >= leftMax {
leftMax = height[left]
} else {
res = res + leftMax - height[left]
}
left++
} else {
if height[right] >= rightMax {
rightMax = height[right]
} else {
res = res + rightMax - height[right]
}
right--
}
}
return res
}
44.通配符匹配(3)
给定一个字符串 (s) 和一个字符模式 (p) ，实现一个支持 '?' 和 '*' 的通配符匹配。
'?' 可以匹配任何单个字符。
'*' 可以匹配任意字符串（包括空字符串）。
两个字符串完全匹配才算匹配成功。
说明:s 可能为空，且只包含从 a-z 的小写字母。
p 可能为空，且只包含从 a-z 的小写字母，以及字符 ? 和 *。
示例 1: 输入:s = "aa" p = "a" 输出: false
解释: "a" 无法匹配 "aa" 整个字符串。
示例 2: 输入: s = "aa" p = "*" 输出: true
解释: '*' 可以匹配任意字符串。
示例 3:输入: s = "cb" p = "?a" 输出: false
解释: '?' 可以匹配 'c', 但第二个 'a' 无法匹配 'b'。
示例 4:输入:s = "adceb" p = "*a*b" 输出: true
解释: 第一个 '*' 可以匹配空字符串, 第二个 '*' 可以匹配字符串 "dce".
示例 5:输入:s = "acdcb" p = "a*c?b" 输出: false
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
动态规划 |
O(n^2) |
O(n^2) |
| 02 |
递归 |
O(n^2) |
O(n^2) |
| 03 |
贪心 |
O(n^2) |
O(1) |
func isMatch(s string, p string) bool {
n, m := len(s), len(p)
dp := make([][]bool, n+1)
for i := 0; i <= n; i++ {
dp[i] = make([]bool, m+1)
}
dp[0][0] = true
for i := 1; i <= m; i++ {
if p[i-1] == '*' {
dp[0][i] = true
} else {
break
}
}
for i := 1; i <= n; i++ {
for j := 1; j <= m; j++ {
if p[j-1] == '*' {
dp[i][j] = dp[i][j-1] || dp[i-1][j]
} else if p[j-1] == '?' || s[i-1] == p[j-1] {
dp[i][j] = dp[i-1][j-1]
}
}
}
return dp[n][m]
}
# 2
var dp [][]int
func isMatch(s string, p string) bool {
n, m := len(s), len(p)
dp = make([][]int, n+1)
for i := 0; i <= n; i++ {
dp[i] = make([]int, m+1)
}
return dfs(s, p, 0, 0)
}
func dfs(s, p string, i, j int) bool {
if i == len(s) && j == len(p) {
return true
}
if dp[i][j] > 0 {
if dp[i][j] == 1 {
return false
} else {
return true
}
}
if i >= len(s) {
return p[j] == '*' && dfs(s, p, i, j+1)
}
if j >= len(p) {
return false
}
res := false
if p[j] == '*' {
res = dfs(s, p, i+1, j) || dfs(s, p, i, j+1)
} else {
res = (s[i] == p[j] || p[j] == '?') && dfs(s, p, i+1, j+1)
}
if res == true {
dp[i][j] = 2
} else {
dp[i][j] = 1
}
return res
}
# 3
func isMatch(s string, p string) bool {
i, j := 0, 0
start, last := 0, 0
for i = 0; i < len(s); {
if j < len(p) && (s[i] == p[j] || p[j] == '?') {
i++
j++
} else if j < len(p) && p[j] == '*' {
last = i
j++
start = j
} else if start != 0 {
last++
i = last
j = start
} else {
return false
}
}
for ; j < len(p) && p[j] == '*'; j++ {
}
return j == len(p)
}
45.跳跃游戏II(4)
给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
示例:输入: [2,3,1,1,4] 输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
说明:假设你总是可以到达数组的最后一个位置。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(n^2) |
O(1) |
| 02 |
遍历 |
O(n) |
O(1) |
| 03 |
动态规划 |
O(n^2) |
O(n) |
| 04 |
迭代 |
O(n^2) |
O(n) |
func jump(nums []int) int {
last := len(nums) - 1
res := 0
for last > 0 {
for i := 0; i < last; i++ {
if i+nums[i] >= last {
last = i
res++
break
}
}
}
return res
}
# 2
func jump(nums []int) int {
res := 0
end := 0
maxValue := 0
for i := 0; i < len(nums)-1; i++ {
maxValue = max(maxValue, i+nums[i])
if i == end {
end = maxValue
res++
}
}
return res
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
# 3
func jump(nums []int) int {
dp := make([]int, len(nums))
dp[0] = 0
for i := 1; i < len(nums); i++ {
dp[i] = i
for j := 0; j < i; j++ {
if nums[j]+j >= i {
dp[i] = min(dp[i], dp[j]+1)
}
}
}
return dp[len(nums)-1]
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
# 4
func jump(nums []int) int {
if len(nums) <= 1 {
return 0
}
dp := make([]int, len(nums))
for i := 1; i < len(nums); i++ {
dp[i] = math.MaxInt32
}
dp[0] = 0
for i := 0; i < len(nums)-1; i++ {
if i+nums[i] >= len(nums)-1 {
return dp[i] + 1
}
for j := i + 1; j <= i+nums[i]; j++ {
if j < len(nums) {
dp[j] = min(dp[j], dp[i]+1)
} else {
break
}
}
}
return dp[len(nums)-1]
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
51.N皇后(3)
n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
上图为 8 皇后问题的一种解法。
给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。
每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
示例:
输入: 4
输出: [
[".Q..", // 解法 1
"...Q",
"Q...",
"..Q."],
["..Q.", // 解法 2
"Q...",
"...Q",
".Q.."]
]
解释: 4皇后问题存在两个不同的解法。
提示：
皇后，是国际象棋中的棋子，意味着国王的妻子。皇后只做一件事，那就是“吃子”。
当她遇见可以吃的棋子时，就迅速冲上去吃掉棋子。当然，她横、竖、斜都可走一到七步，可进可退。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
回溯 |
O(n^n) |
O(n^2) |
| 02 |
回溯 |
O(n^n) |
O(n^2) |
| 03 |
回溯 |
O(n^n) |
O(n^2) |
var res [][]string
func solveNQueens(n int) [][]string {
res = make([][]string, 0)
arr := make([][]string, n)
for i := 0; i < n; i++ {
arr[i] = make([]string, n)
for j := 0; j < n; j++ {
arr[i][j] = "."
}
}
dfs(arr, 0)
return res
}
func dfs(arr [][]string, row int) {
if len(arr) == row {
temp := make([]string, 0)
for i := 0; i < len(arr); i++ {
str := ""
for j := 0; j < len(arr[i]); j++ {
str = str + arr[i][j]
}
temp = append(temp, str)
}
res = append(res, temp)
return
}
for col := 0; col < len(arr[0]); col++ {
if valid(arr, row, col) == false {
continue
}
arr[row][col] = "Q"
dfs(arr, row+1)
arr[row][col] = "."
}
}
func valid(arr [][]string, row, col int) bool {
n := len(arr)
for row := 0; row < n; row++ {
if arr[row][col] == "Q" {
return false
}
}
for row, col := row-1, col-1; row >= 0 && col >= 0; row, col = row-1, col-1 {
if arr[row][col] == "Q" {
return false
}
}
for row, col := row-1, col+1; row >= 0 && col < n; row, col = row-1, col+1 {
if arr[row][col] == "Q" {
return false
}
}
return true
}
# 2
var res [][]string
var rows, left, right []bool
func solveNQueens(n int) [][]string {
res = make([][]string, 0)
rows, left, right = make([]bool, n), make([]bool, 2*n-1), make([]bool, 2*n-1)
arr := make([][]string, n)
for i := 0; i < n; i++ {
arr[i] = make([]string, n)
for j := 0; j < n; j++ {
arr[i][j] = "."
}
}
dfs(arr, 0)
return res
}
func dfs(arr [][]string, row int) {
n := len(arr)
if len(arr) == row {
temp := make([]string, 0)
for i := 0; i < n; i++ {
str := ""
for j := 0; j < n; j++ {
str = str + arr[i][j]
}
temp = append(temp, str)
}
res = append(res, temp)
return
}
for col := 0; col < n; col++ {
if rows[col] == true || left[row-col+n-1] == true || right[row+col] == true {
continue
}
rows[col], left[row-col+n-1], right[row+col] = true, true, true
arr[row][col] = "Q"
dfs(arr, row+1)
arr[row][col] = "."
rows[col], left[row-col+n-1], right[row+col] = false, false, false
}
}
# 3
var res [][]string
func solveNQueens(n int) [][]string {
res = make([][]string, 0)
arr := make([][]string, n)
for i := 0; i < n; i++ {
arr[i] = make([]string, n)
for j := 0; j < n; j++ {
arr[i][j] = "."
}
}
dfs(arr, 0, 0, 0, 0)
return res
}
func dfs(arr [][]string, row int, rows, left, right int) {
n := len(arr)
if len(arr) == row {
temp := make([]string, 0)
for i := 0; i < n; i++ {
str := ""
for j := 0; j < n; j++ {
str = str + arr[i][j]
}
temp = append(temp, str)
}
res = append(res, temp)
return
}
for col := 0; col < n; col++ {
a := uint(col)
b := uint(row - col + n - 1)
c := uint(row + col)
if ((rows>>a)&1) != 0 || ((left>>b)&1) != 0 || ((right>>c)&1) != 0 {
continue
}
arr[row][col] = "Q"
dfs(arr, row+1, rows^(1<<a), left^(1<<b), right^(1<<c))
arr[row][col] = "."
}
}
52.N皇后II(3)
n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
上图为 8 皇后问题的一种解法。
给定一个整数 n，返回 n 皇后不同的解决方案的数量。
示例:输入: 4 输出: 2 解释: 4 皇后问题存在如下两个不同的解法。
[
[".Q..", // 解法 1
"...Q",
"Q...",
"..Q."],
["..Q.", // 解法 2
"Q...",
"...Q",
".Q.."]
]
提示：皇后，是国际象棋中的棋子，意味着国王的妻子。皇后只做一件事，那就是“吃子”。
当她遇见可以吃的棋子时，就迅速冲上去吃掉棋子。当然，她横、竖、斜都可走一或 N-1 步，可进可退。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
回溯 |
O(n^n) |
O(n^2) |
| 02 |
回溯 |
O(n^n) |
O(n^2) |
| 03 |
回溯-位运算 |
O(n^n) |
O(n) |
var res int
var rows, left, right []bool
func totalNQueens(n int) int {
res = 0
rows, left, right = make([]bool, n), make([]bool, 2*n-1), make([]bool, 2*n-1)
arr := make([][]string, n)
for i := 0; i < n; i++ {
arr[i] = make([]string, n)
for j := 0; j < n; j++ {
arr[i][j] = "."
}
}
dfs(arr, 0)
return res
}
func dfs(arr [][]string, row int) {
n := len(arr)
if len(arr) == row {
res++
return
}
for col := 0; col < n; col++ {
if rows[col] == true || left[row-col+n-1] == true || right[row+col] == true {
continue
}
rows[col], left[row-col+n-1], right[row+col] = true, true, true
arr[row][col] = "Q"
dfs(arr, row+1)
arr[row][col] = "."
rows[col], left[row-col+n-1], right[row+col] = false, false, false
}
}
# 2
var res int
func totalNQueens(n int) int {
res = 0
arr := make([][]string, n)
for i := 0; i < n; i++ {
arr[i] = make([]string, n)
for j := 0; j < n; j++ {
arr[i][j] = "."
}
}
dfs(arr, 0)
return res
}
func dfs(arr [][]string, row int) {
if len(arr) == row {
res++
return
}
for col := 0; col < len(arr[0]); col++ {
if valid(arr, row, col) == false {
continue
}
arr[row][col] = "Q"
dfs(arr, row+1)
arr[row][col] = "."
}
}
func valid(arr [][]string, row, col int) bool {
n := len(arr)
for row := 0; row < n; row++ {
if arr[row][col] == "Q" {
return false
}
}
for row, col := row-1, col-1; row >= 0 && col >= 0; row, col = row-1, col-1 {
if arr[row][col] == "Q" {
return false
}
}
for row, col := row-1, col+1; row >= 0 && col < n; row, col = row-1, col+1 {
if arr[row][col] == "Q" {
return false
}
}
return true
}
# 3
var res int
func totalNQueens(n int) int {
res = 0
dfs(0, n, 0, 0, 0)
return res
}
func dfs(row, n int, rows, left, right int) {
if n == row {
res++
return
}
for col := 0; col < n; col++ {
a := uint(col)
b := uint(row - col + n - 1)
c := uint(row + col)
if ((rows>>a)&1) != 0 || ((left>>b)&1) != 0 || ((right>>c)&1) != 0 {
continue
}
dfs(row+1, n, rows^(1<<a), left^(1<<b), right^(1<<c))
}
}
57.插入区间(3)
给出一个无重叠的 ，按照区间起始端点排序的区间列表。
在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。
示例 1： 输入：intervals = [[1,3],[6,9]], newInterval = [2,5] 输出：[[1,5],[6,9]]
示例 2： 输入：intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
输出：[[1,2],[3,10],[12,16]]
解释：这是因为新的区间 [4,8] 与 [3,5],[6,7],[8,10] 重叠。
注意：输入类型已在 2019 年 4 月 15 日更改。请重置为默认代码定义以获取新的方法签名。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(n) |
O(n) |
| 02 |
遍历 |
O(n) |
O(n) |
| 03 |
排序遍历 |
O(nlog(n)) |
O(n) |
func insert(intervals [][]int, newInterval []int) [][]int {
res := make([][]int, 0)
if len(intervals) == 0 {
res = append(res, newInterval)
return res
}
i := 0
for ; i < len(intervals) && intervals[i][1] < newInterval[0]; i++ {
res = append(res, intervals[i])
}
for ; i < len(intervals) && intervals[i][0] <= newInterval[1]; i++ {
newInterval[0] = min(newInterval[0], intervals[i][0])
newInterval[1] = max(newInterval[1], intervals[i][1])
}
res = append(res, newInterval)
for ; i < len(intervals); i++ {
res = append(res, intervals[i])
}
return res
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
# 2
func insert(intervals [][]int, newInterval []int) [][]int {
if len(intervals) == 0 {
return [][]int{newInterval}
}
i := 0
for ; i < len(intervals) && intervals[i][1] < newInterval[0]; i++ {
}
left := i
i = len(intervals) - 1
for ; i >= 0 && intervals[i][0] > newInterval[1]; i-- {
}
right := i
if left > right {
return append(intervals[:left], append([][]int{newInterval}, intervals[left:]...)...)
}
newInterval[0] = min(newInterval[0], intervals[left][0])
newInterval[1] = max(newInterval[1], intervals[right][1])
return append(intervals[:left], append([][]int{newInterval}, intervals[right+1:]...)...)
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
# 3
func insert(intervals [][]int, newInterval []int) [][]int {
res := make([][]int, 0)
intervals = append(intervals, newInterval)
sort.Slice(intervals, func(i, j int) bool {
return intervals[i][0] < intervals[j][0]
})
res = append(res, intervals[0])
for i := 1; i < len(intervals); i++ {
arr := res[len(res)-1]
if intervals[i][0] > arr[1] {
res = append(res, intervals[i])
} else if intervals[i][1] > arr[1] {
res[len(res)-1][1] = intervals[i][1]
}
}
return res
}
65.有效数字(1)
验证给定的字符串是否可以解释为十进制数字。
例如:
"0" => true
" 0.1 " => true
"abc" => false
"1 a" => false
"2e10" => true
" -90e3 " => true
" 1e" => false
"e3" => false
" 6e-1" => true
" 99e2.5 " => false
"53.5e93" => true
" --6 " => false
"-+3" => false
"95a54e53" => false
说明: 我们有意将问题陈述地比较模糊。在实现代码之前，你应当事先思考所有可能的情况。
这里给出一份可能存在于有效十进制数字中的字符列表：
数字 0-9
指数 - "e"
正/负号 - "+"/"-"
小数点 - "."
当然，在输入中，这些字符的上下文也很重要。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历 |
O(n) |
O(n) |
func isNumber(s string) bool {
s = strings.Trim(s, " ")
if s == "" || len(s) == 0 || len(s) == 0 {
return false
}
arr := []byte(s)
i := 0
numeric := scanInteger(&arr, &i)
if i < len(arr) && arr[i] == '.' {
i++
numeric = scanUnsignedInteger(&arr, &i) || numeric
}
if i < len(arr) && (arr[i] == 'e' || arr[i] == 'E') {
i++
numeric = numeric && scanInteger(&arr, &i)
}
return numeric && len(arr) == i
}
func scanInteger(arr *[]byte, index *int) bool {
if len(*arr) <= *index {
return false
}
if (*arr)[*index] == '+' || (*arr)[*index] == '-' {
*index++
}
return scanUnsignedInteger(arr, index)
}
func scanUnsignedInteger(arr *[]byte, index *int) bool {
j := *index
for *index < len(*arr) {
if (*arr)[*index] < '0' || (*arr)[*index] > '9' {
break
}
*index++
}
return j < *index
}
68.文本左右对齐(1)
给定一个单词数组和一个长度 maxWidth，重新排版单词，使其成为每行恰好有 maxWidth 个字符，
且左右两端对齐的文本。
你应该使用“贪心算法”来放置给定的单词；也就是说，尽可能多地往每行中放置单词。
必要时可用空格 ' ' 填充，使得每行恰好有 maxWidth 个字符。
要求尽可能均匀分配单词间的空格数量。
如果某一行单词间的空格不能均匀分配，则左侧放置的空格数要多于右侧的空格数。
文本的最后一行应为左对齐，且单词之间不插入额外的空格。
说明:单词是指由非空格字符组成的字符序列。
每个单词的长度大于 0，小于等于 maxWidth。
输入单词数组 words 至少包含一个单词。
示例:输入: words = ["This", "is", "an", "example", "of", "text", "justification."]
maxWidth = 16
输出:
[
"This is an",
"example of text",
"justification. "
]
示例 2:输入: words = ["What","must","be","acknowledgment","shall","be"] maxWidth = 16
输出:
[
"What must be",
"acknowledgment ",
"shall be "
]
解释: 注意最后一行的格式应为 "shall be " 而不是 "shall be",
因为最后一行应为左对齐，而不是左右两端对齐。
第二行同样为左对齐，这是因为这行只包含一个单词。
示例 3:
输入:words = ["Science","is","what","we","understand","well","enough","to","explain",
"to","a","computer.","Art","is","everything","else","we","do"]
maxWidth = 20
输出:
[
"Science is what we",
"understand well",
"enough to explain to",
"a computer. Art is",
"everything else we",
"do "
]
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
遍历模拟 |
O(n) |
O(n) |
func fullJustify(words []string, maxWidth int) []string {
res := make([]string, 0)
count := 0
start := 0
for i := 0; i < len(words); i++ {
count = count + len(words[i])
if count > maxWidth {
temp := justify(words, start, i-1, maxWidth)
res = append(res, temp)
start = i
if i == len(words)-1 {
count = 0
i--
} else {
count = len(words[i]) + 1
}
} else if i == len(words)-1 {
temp := justify(words, start, i, maxWidth)
res = append(res, temp)
} else {
count++
}
}
return res
}
func justify(words []string, start, end int, maxWidth int) string {
arr := make([]byte, maxWidth)
for i := 0; i < len(arr); i++ {
arr[i] = byte(' ')
}
index := 0
if start == end || end == len(words)-1 {
for i := start; i <= end; i++ {
copy(arr[index:], words[i])
index = index + len(words[i]) + 1
}
} else {
count := end - start + 1
left := maxWidth - count + 1
for i := start; i <= end; i++ {
left = left - len(words[i])
}
space := left / (count - 1)
mod := left % (count - 1)
for i := start; i <= end; i++ {
copy(arr[index:], words[i])
index = index + len(words[i]) + 1 + space
if mod > 0 {
index++
mod--
}
}
}
return string(arr)
}
72.编辑距离(2)
给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
插入一个字符
删除一个字符
替换一个字符
示例 1：输入：word1 = "horse", word2 = "ros" 输出：3
解释：horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')
示例 2：输入：word1 = "intention", word2 = "execution" 输出：5
解释： intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
动态规划 |
O(n^2) |
O(n^2) |
| 02 |
递归 |
O(n^2) |
O(n^2) |
func minDistance(word1 string, word2 string) int {
n1 := len(word1)
n2 := len(word2)
dp := make([][]int, n1+1)
for i := 0; i < n1+1; i++ {
dp[i] = make([]int, n2+1)
}
dp[0][0] = 0
for i := 1; i <= n1; i++ {
dp[i][0] = i
}
for i := 1; i <= n2; i++ {
dp[0][i] = i
}
for i := 1; i <= n1; i++ {
for j := 1; j <= n2; j++ {
if word1[i-1] == word2[j-1] {
dp[i][j] = dp[i-1][j-1]
} else {
dp[i][j] = dp[i-1][j-1] + 1
dp[i][j] = min(dp[i][j], dp[i][j-1]+1)
dp[i][j] = min(dp[i][j], dp[i-1][j]+1)
}
}
}
return dp[n1][n2]
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
# 2
var dp [][]int
func minDistance(word1 string, word2 string) int {
dp = make([][]int, len(word1)+1)
for i := 0; i < len(word1)+1; i++ {
dp[i] = make([]int, len(word2)+1)
}
return helper(word1, word2, 0, 0)
}
func helper(word1, word2 string, i, j int) int {
if dp[i][j] > 0 {
return dp[i][j]
}
if i == len(word1) || j == len(word2) {
return len(word1) - i + len(word2) - j
}
if word1[i] == word2[j] {
return helper(word1, word2, i+1, j+1)
}
inserted := helper(word1, word2, i, j+1)
deleted := helper(word1, word2, i+1, j)
replaced := helper(word1, word2, i+1, j+1)
dp[i][j] = min(inserted, min(deleted, replaced)) + 1
return dp[i][j]
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
76.最小覆盖子串(2)
给你一个字符串 S、一个字符串 T 。
请你设计一种算法，可以在 O(n) 的时间复杂度内，从字符串 S 里面找出：包含 T 所有字符的最小子串。
示例：输入：S = "ADOBECODEBANC", T = "ABC" 输出："BANC"
提示：如果 S 中不存这样的子串，则返回空字符串 ""。
如果 S 中存在这样的子串，我们保证它是唯一的答案。
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
滑动窗口 |
O(n^2) |
O(n) |
| 02 |
滑动窗口 |
O(n) |
O(n) |
func minWindow(s string, t string) string {
if len(s) < len(t) {
return ""
}
window := make(map[byte]int)
need := make(map[byte]int)
for i := 0; i < len(t); i++ {
need[t[i]]++
}
left, right := -1, -1
minLength := math.MaxInt32
for l, r := 0, 0; r < len(s); r++ {
if r < len(s) && need[s[r]] > 0 {
window[s[r]]++
}
for check(need, window) == true && l <= r {
if r-l+1 < minLength {
minLength = r - l + 1
left, right = l, r+1
}
if _, ok := need[s[l]]; ok {
window[s[l]]--
}
l++
}
}
if left == -1 {
return ""
}
return s[left:right]
}
func check(need, window map[byte]int) bool {
for k, v := range need {
if window[k] < v {
return false
}
}
return true
}
# 2
func minWindow(s string, t string) string {
if len(s) < len(t) {
return ""
}
arr := make(map[byte]int)
for i := 0; i < len(t); i++ {
arr[t[i]]++
}
l, count := 0, 0
res := ""
minLength := math.MaxInt32
for r := 0; r < len(s); r++ {
arr[s[r]]--
if arr[s[r]] >= 0 {
count++
}
for count == len(t) {
if minLength > r-l+1 {
minLength = r - l + 1
res = s[l : r+1]
}
arr[s[l]]++
if arr[s[l]] > 0 {
count--
}
l++
}
}
return res
}
84.柱状图中最大的矩形(5)
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。
图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。
示例:输入: [2,1,5,6,2,3]输出: 10
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
暴力法 |
O(n^2) |
O(1) |
| 02 |
暴力法 |
O(n^2) |
O(1) |
| 03 |
单调栈 |
O(n) |
O(n) |
| 04 |
单调栈 |
O(n) |
O(n) |
| 05 |
单调栈 |
O(n) |
O(n) |
func largestRectangleArea(heights []int) int {
n := len(heights)
res := 0
for i := 0; i < n; i++ {
height := heights[i]
for j := i; j < n; j++ {
width := j - i + 1
height = min(height, heights[j])
res = max(res, width*height)
}
}
return res
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
# 2
func largestRectangleArea(heights []int) int {
n := len(heights)
res := 0
for i := 0; i < n; i++ {
height := heights[i]
left, right := i, i
for left > 0 && heights[left-1] >= height {
left--
}
for right < n-1 && heights[right+1] >= height {
right++
}
width := right - left + 1
res = max(res, width*height)
}
return res
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
# 3
func largestRectangleArea(heights []int) int {
n := len(heights)
res := 0
left := make([]int, n)
right := make([]int, n)
stack := make([]int, 0)
for i := 0; i < n; i++ {
for len(stack) > 0 && heights[stack[len(stack)-1]] >= heights[i] {
stack = stack[:len(stack)-1]
}
if len(stack) == 0 {
left[i] = -1
} else {
left[i] = stack[len(stack)-1]
}
stack = append(stack, i)
}
stack = make([]int, 0)
for i := n - 1; i >= 0; i-- {
for len(stack) > 0 && heights[stack[len(stack)-1]] >= heights[i] {
stack = stack[:len(stack)-1]
}
if len(stack) == 0 {
right[i] = n
} else {
right[i] = stack[len(stack)-1]
}
stack = append(stack, i)
}
for i := 0; i < n; i++ {
res = max(res, heights[i]*(right[i]-left[i]-1))
}
return res
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
# 4
func largestRectangleArea(heights []int) int {
n := len(heights)
res := 0
left := make([]int, n)
right := make([]int, n)
stack := make([]int, 0)
for i := 0; i < n; i++ {
right[i] = n
}
for i := 0; i < n; i++ {
for len(stack) > 0 && heights[stack[len(stack)-1]] >= heights[i] {
right[stack[len(stack)-1]] = i
stack = stack[:len(stack)-1]
}
if len(stack) == 0 {
left[i] = -1
} else {
left[i] = stack[len(stack)-1]
}
stack = append(stack, i)
}
for i := 0; i < n; i++ {
res = max(res, heights[i]*(right[i]-left[i]-1))
}
return res
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
# 5
func largestRectangleArea(heights []int) int {
heights = append([]int{0}, heights...)
heights = append(heights, 0)
n := len(heights)
res := 0
stack := make([]int, 0)
for i := 0; i < n; i++ {
for len(stack) > 0 && heights[stack[len(stack)-1]] > heights[i] {
height := heights[stack[len(stack)-1]]
stack = stack[:len(stack)-1]
width := i - stack[len(stack)-1] - 1
res = max(res, height*width)
}
stack = append(stack, i)
}
return res
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
85.最大矩形(2)
给定一个仅包含 0 和 1 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
示例:输入:
[
["1","0","1","0","0"],
["1","0","1","1","1"],
["1","1","1","1","1"],
["1","0","0","1","0"]
]
输出: 6
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
单调栈 |
O(n^2) |
O(n) |
| 02 |
动态规划 |
O(n^2) |
O(n) |
func maximalRectangle(matrix [][]byte) int {
if len(matrix) == 0 || len(matrix[0]) == 0 {
return 0
}
res := 0
n, m := len(matrix), len(matrix[0])
height := make([]int, m)
for i := 0; i < n; i++ {
for j := 0; j < m; j++ {
if matrix[i][j] == '0' {
height[j] = 0
} else {
height[j] = height[j] + 1
}
}
res = max(res, getMaxArea(height))
}
return res
}
func getMaxArea(heights []int) int {
heights = append([]int{0}, heights...)
heights = append(heights, 0)
n := len(heights)
res := 0
stack := make([]int, 0)
for i := 0; i < n; i++ {
for len(stack) > 0 && heights[stack[len(stack)-1]] > heights[i] {
height := heights[stack[len(stack)-1]]
stack = stack[:len(stack)-1]
width := i - stack[len(stack)-1] - 1
res = max(res, height*width)
}
stack = append(stack, i)
}
return res
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
# 2
func maximalRectangle(matrix [][]byte) int {
if len(matrix) == 0 || len(matrix[0]) == 0 {
return 0
}
res := 0
n, m := len(matrix), len(matrix[0])
left, right, height := make([]int, m), make([]int, m), make([]int, m)
for i := 0; i < m; i++ {
right[i] = m
}
for i := 0; i < n; i++ {
curLeft, curRight := 0, m
for j := 0; j < m; j++ {
if matrix[i][j] == '1' {
height[j]++
} else {
height[j] = 0
}
}
for j := 0; j < m; j++ {
if matrix[i][j] == '1' {
left[j] = max(left[j], curLeft)
} else {
left[j] = 0
curLeft = j + 1
}
}
for j := m - 1; j >= 0; j-- {
if matrix[i][j] == '1' {
right[j] = min(right[j], curRight)
} else {
right[j] = m
curRight = j
}
}
for j := 0; j < m; j++ {
res = max(res, height[j]*(right[j]-left[j]))
}
}
return res
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
87.扰乱字符串(2)
给定一个字符串 s1，我们可以把它递归地分割成两个非空子字符串，从而将其表示为二叉树。
下图是字符串 s1 = "great" 的一种可能的表示形式。
great
/ \
gr eat
/ \ / \
g r e at
/ \
a t
在扰乱这个字符串的过程中，我们可以挑选任何一个非叶节点，然后交换它的两个子节点。
例如，如果我们挑选非叶节点 "gr" ，交换它的两个子节点，将会产生扰乱字符串 "rgeat" 。
rgeat
/ \
rg eat
/ \ / \
r g e at
/ \
a t
我们将 "rgeat” 称作 "great" 的一个扰乱字符串。
同样地，如果我们继续交换节点 "eat" 和 "at" 的子节点，将会产生另一个新的扰乱字符串 "rgtae" 。
rgtae
/ \
rg tae
/ \ / \
r g ta e
/ \
t a
我们将 "rgtae” 称作 "great" 的一个扰乱字符串。
给出两个长度相等的字符串 s1 和 s2，判断 s2 是否是 s1 的扰乱字符串。
示例 1:输入: s1 = "great", s2 = "rgeat" 输出: true
示例 2:输入: s1 = "abcde", s2 = "caebd" 输出: false
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
动态规划 |
O(n^4) |
O(n^3) |
| 02 |
递归 |
O(5^n) |
O(n) |
func isScramble(s1 string, s2 string) bool {
n, m := len(s1), len(s2)
if n != m {
return false
}
dp := make([][][]bool, n+1)
for i := 0; i <= n; i++ {
dp[i] = make([][]bool, n+1)
for j := 0; j <= n; j++ {
dp[i][j] = make([]bool, n+1)
}
}
for i := 0; i < n; i++ {
for j := 0; j < n; j++ {
dp[i][j][1] = s1[i] == s2[j]
}
}
for k := 2; k <= n; k++ {
for i := 0; i <= n-k; i++ {
for j := 0; j <= n-k; j++ {
dp[i][j][k] = false
for w := 1; w <= k-1; w++ {
if (dp[i][j][w] == true && dp[i+w][j+w][k-w] == true) ||
(dp[i][j+k-w][w] == true && dp[i+w][j][k-w] == true) {
dp[i][j][k] = true
}
}
}
}
}
return dp[0][0][n]
}
# 2
func isScramble(s1 string, s2 string) bool {
return dfs([]byte(s1), []byte(s2))
}
func dfs(arr1, arr2 []byte) bool {
if compare(arr1, arr2) == false {
return false
}
if len(arr1) <= 2 {
return (len(arr1) == 2 && ((arr1[0] == arr2[0] && arr1[1] == arr2[1]) ||
(arr1[0] == arr2[1] && arr1[1] == arr2[0]))) ||
(len(arr1) == 1 && arr1[0] == arr2[0])
}
for i := 1; i < len(arr1); i++ {
leftA, rightA := arr1[:i], arr1[i:]
leftB, rightB := arr2[:i], arr2[i:]
LB, RB := arr2[len(arr1)-i:], arr2[:len(arr1)-i]
if (dfs(leftA, leftB) && dfs(rightA, rightB)) || (dfs(leftA, LB) && dfs(rightA, RB)) {
return true
}
}
return false
}
func compare(arr1, arr2 []byte) bool {
if len(arr1) != len(arr2) {
return false
}
arrA := make([]byte, 26)
arrB := make([]byte, 26)
for i := 0; i < len(arr1); i++ {
arrA[arr1[i]-'a']++
arrB[arr2[i]-'a']++
}
for i := 0; i < len(arrA); i++ {
if arrA[i] != arrB[i] {
return false
}
}
return true
}
97.交错字符串(3)
给定三个字符串 s1, s2, s3, 验证 s3 是否是由 s1 和 s2 交错组成的。
示例 1：输入：s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac" 输出：true
示例 2：输入：s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc" 输出：false
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
动态规划 |
O(n^2) |
O(n^2) |
| 02 |
动态规划-一维 |
O(n^2) |
O(n) |
| 03 |
递归 |
O(n) |
O(n) |
func isInterleave(s1 string, s2 string, s3 string) bool {
n, m, t := len(s1), len(s2), len(s3)
if n+m != t {
return false
}
dp := make([][]bool, n+1)
for i := 0; i <= n; i++ {
dp[i] = make([]bool, m+1)
}
dp[0][0] = true
for i := 0; i <= n; i++ {
for j := 0; j <= m; j++ {
total := i + j - 1
if i > 0 && dp[i-1][j] == true && s1[i-1] == s3[total] {
dp[i][j] = true
}
if j > 0 && dp[i][j-1] == true && s2[j-1] == s3[total] {
dp[i][j] = true
}
}
}
return dp[n][m]
}
# 2
func isInterleave(s1 string, s2 string, s3 string) bool {
n, m, t := len(s1), len(s2), len(s3)
if n+m != t {
return false
}
dp := make([]bool, m+1)
dp[0] = true
for i := 0; i <= n; i++ {
for j := 0; j <= m; j++ {
total := i + j - 1
if i > 0 {
if dp[j] == true && s1[i-1] == s3[total] {
dp[j] = true
} else {
dp[j] = false
}
}
if j > 0 {
if dp[j] == true || (dp[j-1] == true && s2[j-1] == s3[total]) {
dp[j] = true
} else {
dp[j] = false
}
}
}
}
return dp[m]
}
# 3
func isInterleave(s1 string, s2 string, s3 string) bool {
if len(s1)+len(s2) != len(s3) {
return false
}
return dfs(s1, s2, s3, 0, 0, 0)
}
func dfs(s1, s2, s3 string, i, j, k int) bool {
if k == len(s3) && i == len(s1) && j == len(s2) {
return true
}
if k >= len(s3) {
return false
}
if i < len(s1) {
if s1[i] == s3[k] {
if dfs(s1, s2, s3, i+1, j, k+1) {
return true
}
}
}
if j < len(s2) {
if s2[j] == s3[k] {
if dfs(s1, s2, s3, i, j+1, k+1) {
return true
}
}
}
return false
}
99.恢复二叉搜索树(4)
二叉搜索树中的两个节点被错误地交换。
请在不改变其结构的情况下，恢复这棵树。
示例 1:输入: [1,3,null,null,2]
1
/
3
\
2
输出: [3,1,null,null,2]
3
/
1
\
2
示例 2:输入: [3,1,4,null,null,2]
3
/ \
1 4
/
2
输出: [2,1,4,null,null,3]
2
/ \
1 4
/
3
进阶:使用 O(n) 空间复杂度的解法很容易实现。你能想出一个只使用常数空间的解决方案吗？
| No. |
思路 |
时间复杂度 |
空间复杂度 |
| 01 |
递归 |
O(n) |
O(n) |
| 02 |
递归 |
O(n) |
O(log(n)) |
| 03 |
迭代 |
O(n) |
O(n) |
| 04 |
迭代 |
O(n) |
O(1) |
var arr []*TreeNode
func recoverTree(root *TreeNode) {
arr = make([]*TreeNode, 0)
dfs(root)
a, b := -1, -1
for i := 0; i < len(arr)-1; i++ {
if arr[i].Val > arr[i+1].Val {
b = i + 1
if a == -1 {
a = i
}
}
}
arr[a].Val, arr[b].Val = arr[b].Val, arr[a].Val
}
func dfs(root *TreeNode) {
if root == nil {
return
}
dfs(root.Left)
arr = append(arr, root)
dfs(root.Right)
}
# 2
var prev, first, second *TreeNode
func recoverTree(root *TreeNode) {
prev, first, second = nil, nil, nil
dfs(root)
first.Val, second.Val = second.Val, first.Val
}
func dfs(root *TreeNode) {
if root == nil {
return
}
dfs(root.Left)
if prev != nil && prev.Val > root.Val {
second = root
if first == nil {
first = prev
} else {
return
}
}
prev = root
dfs(root.Right)
}
# 3
func recoverTree(root *TreeNode) {
var prev, first, second *TreeNode
stack := make([]*TreeNode, 0)
for len(stack) > 0 || root != nil {
for root != nil {
stack = append(stack, root)
root = root.Left
}
root = stack[len(stack)-1]
stack = stack[:len(stack)-1]
if prev != nil && root.Val < prev.Val {
second = root
if first == nil {
first = prev
} else {
break
}
}
prev = root
root = root.Right
}
first.Val, second.Val = second.Val, first.Val
}
# 4
func recoverTree(root *TreeNode) {
var prev, temp, first, second *TreeNode
for root != nil {
temp = root.Left
if temp != nil {
for temp.Right != nil && temp.Right != root {
temp = temp.Right
}
if temp.Right == nil {
temp.Right = root
root = root.Left
continue
} else {
temp.Right = nil
}
}
if prev != nil && prev.Val > root.Val {
second = root
if first == nil {
first = prev
}
}
prev = root
root = root.Right
}
first.Val, second.Val = second.Val, first.Val
}