Skip to content
Merged
Show file tree
Hide file tree
Changes from all commits
Commits
File filter

Filter by extension

Filter by extension

Conversations
Failed to load comments.
Loading
Jump to
The table of contents is too big for display.
Diff view
Diff view
  •  
  •  
  •  
109 changes: 66 additions & 43 deletions website/config.toml
Original file line number Diff line number Diff line change
Expand Up @@ -9,55 +9,78 @@ enableGitInfo = true
# Book configuration
disablePathToLower = true

# 多语言默认语言(必须放在任何 [table] 之前,否则会被误嵌套)。
# 英文为默认;英文在 /en/、中文在 /zh/,根路径 / 自动跳转到默认语言 /en/,
# 这样英文既是默认、又保留独立的 /en/ 入口(与 /zh/ 对称)。
defaultContentLanguage = "en"
defaultContentLanguageInSubdir = true

# Needed for mermaid/katex shortcodes
[markup]
[markup.goldmark.renderer]
unsafe = true

[markup.tableOfContents]
startLevel = 1

# Multi-lingual mode config
# There are different options to translate files
# See https://gohugo.io/content-management/multilingual/#translation-by-filename
# And https://gohugo.io/content-management/multilingual/#translation-by-content-directory
#[languages]
#[languages.en]
# languageName = 'English'
# contentDir = 'content'
# weight = 1

#[languages.ru]
# languageName = 'Russian'
# contentDir = 'content.ru'
# weight = 2

#[languages.cn]
# languageName = 'Chinese'
# contentDir = 'content.cn'
# weight = 3

[menu]
[[menu.before]]
name = "Blog"
url = "https://halfrost.com"
weight = 10
[[menu.before]]
name = "Github"
url = "https://github.com/halfrost"
weight = 20
[[menu.before]]
name = "WeChat Official Accounts"
url = "https://img.halfrost.com/wechat-qr-code.png"
weight = 30
[[menu.before]]
name = "Twitter"
url = "https://twitter.com/halffrost"
weight = 40
[[menu.before]]
name = "Weibo"
url = "https://weibo.com/halfrost"
weight = 50
# 从 2 级标题开始收录,右侧目录不再收录很长的 H1 题目标题(英文标题很长会撑出右边栏)
startLevel = 2

# Multi-lingual mode: 中文(默认, 根路径 /) + English(/en/),两套都预渲染成静态页面,
# 由主题右下角的语言下拉一键切换(footer 里 IsMultiLingual 时显示)。
# 中文内容在 content/,英文内容在 content.en/(由翻译脚本生成)。
[languages]
[languages.zh]
languageName = "中文"
languageCode = "zh-CN"
contentDir = "content"
weight = 2
[languages.zh.menu]
[[languages.zh.menu.before]]
name = "Blog"
url = "https://halfrost.com"
weight = 10
[[languages.zh.menu.before]]
name = "Github"
url = "https://github.com/halfrost"
weight = 20
[[languages.zh.menu.before]]
name = "WeChat Official Accounts"
url = "https://img.halfrost.com/wechat-qr-code.png"
weight = 30
[[languages.zh.menu.before]]
name = "Twitter"
url = "https://twitter.com/halffrost"
weight = 40
[[languages.zh.menu.before]]
name = "Weibo"
url = "https://weibo.com/halfrost"
weight = 50

[languages.en]
languageName = "English"
languageCode = "en-US"
contentDir = "content.en"
weight = 1
[languages.en.menu]
[[languages.en.menu.before]]
name = "Blog"
url = "https://halfrost.com"
weight = 10
[[languages.en.menu.before]]
name = "Github"
url = "https://github.com/halfrost"
weight = 20
[[languages.en.menu.before]]
name = "WeChat Official Accounts"
url = "https://img.halfrost.com/wechat-qr-code.png"
weight = 30
[[languages.en.menu.before]]
name = "Twitter"
url = "https://twitter.com/halffrost"
weight = 40
[[languages.en.menu.before]]
name = "Weibo"
url = "https://weibo.com/halfrost"
weight = 50
#[[menu.after]]
# name = "Github"
# url = "https://github.com/alex-shpak/hugo-book"
Expand Down
50 changes: 50 additions & 0 deletions website/content.en/ChapterFour/0001~0099/0001.Two-Sum.md
Original file line number Diff line number Diff line change
@@ -0,0 +1,50 @@
# [1. Two Sum](https://leetcode.com/problems/two-sum/)

## Problem

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

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

**Example**:

```

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1]

```



## Problem Summary

Find two numbers in an array whose sum equals the given value, and return the indices of the two numbers in the array.

## Solution Approach

The optimal time complexity for this problem is O(n).

Scan the array in order. For each element, look in the map for the other half of the number that can combine with it to make the given value. If it is found, directly return the indices of the two numbers. If it is not found, store this number in the map and wait until the “other half” number is encountered, then retrieve it and return the result.

## Code

```go

package leetcode

func twoSum(nums []int, target int) []int {
m := make(map[int]int)
for i := 0; i < len(nums); i++ {
another := target - nums[i]
if index, ok := m[another]; ok {
return []int{index, i}
}
m[nums[i]] = i
}
return nil
}

```
78 changes: 78 additions & 0 deletions website/content.en/ChapterFour/0001~0099/0002.Add-Two-Numbers.md
Original file line number Diff line number Diff line change
@@ -0,0 +1,78 @@
# [2. Add Two Numbers](https://leetcode.com/problems/add-two-numbers/)

## Problem

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

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

**Example**:

```

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.
```



## Problem Summary

Given 2 linked lists in reverse order, add them starting from the lowest digit. The result should also be output in reverse order, and the return value is the head node of the reversed result linked list.

## Solution Approach

What needs attention is the various carry issues.

Extreme case, for example

```

Input: (9 -> 9 -> 9 -> 9 -> 9) + (1 -> )
Output: 0 -> 0 -> 0 -> 0 -> 0 -> 1


```

To make the handling uniform, you can first create a dummy head node. The Next of this dummy head node points to the real head, so the head does not need to be handled separately, and you can directly use a while loop. In addition, the condition for determining loop termination should not be p.Next != nil; otherwise, the last digit still needs extra calculation. The loop termination condition should be p != nil.


## Code

```go

package leetcode

/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
head := &ListNode{Val: 0}
n1, n2, carry, current := 0, 0, 0, head
for l1 != nil || l2 != nil || carry != 0 {
if l1 == nil {
n1 = 0
} else {
n1 = l1.Val
l1 = l1.Next
}
if l2 == nil {
n2 = 0
} else {
n2 = l2.Val
l2 = l2.Next
}
current.Next = &ListNode{Val: (n1 + n2 + carry) % 10}
current = current.Next
carry = (n1 + n2 + carry) / 10
}
return head.Next
}

```
Original file line number Diff line number Diff line change
@@ -0,0 +1,128 @@
# [3. Longest Substring Without Repeating Characters](https://leetcode.com/problems/longest-substring-without-repeating-characters/)

## Problem

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



**Example 1**:

```

Input: "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

```

**Example 2**:

```

Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

```

**Example 3**:

```

Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

```

## Problem Summary


In a string, find the longest substring without repeating characters.

## Solution Approach

This problem is similar to problems 438, 3, 76, and 567. The idea used is "sliding window".

The right boundary of the sliding window keeps moving to the right. As long as there are no repeated characters, the window boundary continues to expand to the right. Once a repeated character appears, the left boundary needs to be shrunk until the repeated character has moved out of the left boundary, and then the right boundary of the sliding window continues to move. Repeat this process. Each movement requires calculating the current length and determining whether the maximum length needs to be updated. The final maximum value is the answer required by the problem.


## Code

```go

package leetcode

// Solution 1: Bitmap
func lengthOfLongestSubstring(s string) int {
if len(s) == 0 {
return 0
}
var bitSet [256]bool
result, left, right := 0, 0, 0
for left < len(s) {
// If the bitSet corresponding to the right-side character is marked true, it means this character repeats at position X; the left side needs to move forward until X is marked false
if bitSet[s[right]] {
bitSet[s[left]] = false
left++
} else {
bitSet[s[right]] = true
right++
}
if result < right-left {
result = right - left
}
if left+result >= len(s) || right >= len(s) {
break
}
}
return result
}

// Solution 2: Sliding window
func lengthOfLongestSubstring1(s string) int {
if len(s) == 0 {
return 0
}
var freq [127]int
result, left, right := 0, 0, -1

for left < len(s) {
if right+1 < len(s) && freq[s[right+1]] == 0 {
freq[s[right+1]]++
right++

} else {
freq[s[left]]--
left++
}
result = max(result, right-left+1)
}
return result
}

// Solution 3: Sliding window - hash bucket
func lengthOfLongestSubstring2(s string) int {
right, left, res := 0, 0, 0
indexes := make(map[byte]int, len(s))
for left < len(s) {
if idx, ok := indexes[s[left]]; ok && idx >= right {
right = idx + 1
}
indexes[s[left]] = left
left++
res = max(res, left-right)
}
return res
}

func max(a int, b int) int {
if a > b {
return a
}
return b
}

```
Loading
Loading