LeetCode usually gives you the function signature up front, so all you write is the algorithm. Switch to the ACM style and you have to read the input, call the function, and print the answer yourself. The algorithm has not changed; what tends to go wrong is all this outer scaffolding.
Here I will first turn the three hash problems into programs that can run on their own: Two Sum, Group Anagrams, and Longest Consecutive Sequence. This post covers all three.
The input and output formats below are conventions I set myself for local practice; LeetCode still judges by the function signature. Save each piece of code separately as main.go and run it with go run main.go.
1. Two Sum
Original problem: Two Sum.
Approach: when you reach x, first check whether target-x has already appeared. If it has, return these two positions; if not, store the current element. Only by checking before storing can you avoid using the same position twice.
Here the map lookup is counted as O(1) on average, so the whole algorithm is O(n) on average, with O(n) extra space.
Input convention: the first line holds the number of elements n and the target value, followed by n integers. The output is two 0-based indices. The original problem guarantees a solution; here, for local testing, the no-solution case prints -1 -1.
4 9
2 7 11 15Output:
0 1package main
import (
"bufio"
"fmt"
"os"
)
func twoSum(nums []int, target int) (int, int) {
seen := make(map[int]int, len(nums))
for i, x := range nums {
if j, ok := seen[target-x]; ok {
return j, i
}
seen[x] = i
}
return -1, -1
}
func main() {
in := bufio.NewReader(os.Stdin)
out := bufio.NewWriter(os.Stdout)
defer out.Flush()
var n, target int
if _, err := fmt.Fscan(in, &n, &target); err != nil || n < 0 {
return
}
nums := make([]int, n)
for i := range nums {
if _, err := fmt.Fscan(in, &nums[i]); err != nil {
return
}
}
i, j := twoSum(nums, target)
fmt.Fprintln(out, i, j)
}Testing again with 3 3, two 0s, negative numbers, and the no-solution case checks whether you mistakenly use one element twice.
2. Group Anagrams
Original problem: Group Anagrams.
Anagrams contain the same letters in the same counts, just in a different order. Given the original problem’s range of lowercase English letters, you can use [26]int to record how many times each letter appears. An array can be used as a Go map key, so you do not need to sort each word.
Grouping takes O(nL) on average, where L is the maximum word length. Below, to make the local output stable, I sort each group and then all the groups; that adds sorting overhead, so it would be wrong to call the entire program, formatted output included, only O(nL).
Input convention: the first line is the number of words, then each word occupies one line. An empty line represents the empty string, so here I read line by line with a Scanner; you cannot simply use Fscan to read words.
6
eat
tea
tan
ate
nat
batThe output is JSON, which makes it easy to preserve empty strings and group boundaries:
[["ate","eat","tea"],["bat"],["nat","tan"]]package main
import (
"bufio"
"encoding/json"
"fmt"
"os"
"sort"
"strconv"
"strings"
)
func groupAnagrams(words []string) [][]string {
groups := make(map[[26]int][]string)
for _, word := range words {
var key [26]int
for _, ch := range word {
key[ch-'a']++
}
groups[key] = append(groups[key], word)
}
result := make([][]string, 0, len(groups))
for _, group := range groups {
sort.Strings(group)
result = append(result, group)
}
sort.Slice(result, func(i, j int) bool {
return result[i][0] < result[j][0]
})
return result
}
func main() {
scanner := bufio.NewScanner(os.Stdin)
if !scanner.Scan() {
return
}
n, err := strconv.Atoi(strings.TrimSpace(scanner.Text()))
if err != nil || n < 0 {
return
}
words := make([]string, n)
for i := range words {
if !scanner.Scan() {
return
}
words[i] = scanner.Text()
for _, ch := range words[i] {
if ch < 'a' || ch > 'z' {
fmt.Fprintln(os.Stderr, "仅支持小写英文字母和空字符串")
return
}
}
}
if err := json.NewEncoder(os.Stdout).Encode(groupAnagrams(words)); err != nil {
fmt.Fprintln(os.Stderr, err)
}
}Enter 1 and then one empty line; the result should be [[""]]. A single ordinary word must also print correctly. These two cases are very easy to miss when reading input.
3. Longest Consecutive Sequence
Original problem: Longest Consecutive Sequence.
First put the numbers into a set. If x-1 exists, then x is not the start of a consecutive sequence, so skip it. Only a start keeps counting forward.
This way no number is repeatedly scanned as a starting point. Counting the hash set lookup as O(1) on average, the average time is O(n), and the extra space is O(n). The value range follows the original problem’s [-10^9, 10^9]; these are not arbitrary integers beyond the int bounds.
Input convention: read the number of elements first, then the corresponding integers. An empty array prints 0.
6
100 4 200 1 3 2Output:
4package main
import (
"bufio"
"fmt"
"os"
)
func longestConsecutive(nums []int) int {
set := make(map[int]bool, len(nums))
for _, x := range nums {
set[x] = true
}
best := 0
for x := range set {
if set[x-1] {
continue
}
length := 1
for next := x + 1; set[next]; next++ {
length++
}
if length > best {
best = length
}
}
return best
}
func main() {
in := bufio.NewReader(os.Stdin)
var n int
if _, err := fmt.Fscan(in, &n); err != nil || n < 0 {
return
}
nums := make([]int, n)
for i := range nums {
if _, err := fmt.Fscan(in, &nums[i]); err != nil {
return
}
}
fmt.Println(longestConsecutive(nums))
}Duplicate numbers do not increase the sequence length; the length for the input [1, 0, 1, 2] is still 3. You can also test an empty array, an array that is all the same number, and a consecutive run that includes negative numbers.
4. What Else Does the ACM Style Require You to Consider?
Once the algorithm is written, check the input and output separately: whether you read tokens or whole lines, whether the problem has multiple test cases, whether an empty string can appear, whether indices start at 0 or 1, and whether the output requires a fixed order.
bufio.Reader together with fmt.Fscan is relatively easy to write; if the amount of data is very large, switch to a faster integer reader depending on the judge. bufio.Scanner has a token length limit by default, so you need to set a Buffer when reading long text; the current short-word example cannot be applied directly to arbitrarily large files.
API documentation: fmt.Fscan, bufio.Scanner.