技巧

解决 LeetCode 上的算法题通常需要遵循一些通用的思路和策略。以下是一些解题步骤和技巧，以及相应的 Go 语言代码示例。

通用解题思路：

理解题目：仔细阅读题目，理解题目的要求和限制条件。
确定算法策略：根据题目的特点选择合适的算法策略，如贪心、动态规划、回溯、分治等。
考虑边界情况：思考并处理输入数据的边界情况和特殊情况。
编写代码：根据选定的算法策略编写代码。
测试验证：对编写的代码进行测试，验证其正确性和性能。

Go 语言代码示例：

1. 只出现一次的数字

题目描述：给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

解题思路：使用位运算中的异或运算。异或运算有一个特性，两个相同的数字异或结果为 0，任何数字与 0 异或还是它本身。

Go 语言代码示例：

func singleNumber(nums []int) int {
    result := 0
    for _, num := range nums {
        result ^= num
    }
    return result
}

2. 多数元素

题目描述：给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

解题思路：使用摩尔投票法。维护一个候选众数和它出现的次数，遍历数组，如果次数为 0，则换一个候选众数，否则如果遇到相同的数则次数加 1，不同则减 1。

Go 语言代码示例：

func majorityElement(nums []int) int {
    count := 0
    candidate := 0

    for _, num := range nums {
        if count == 0 {
            candidate = num
        }
        if num == candidate {
            count++
        } else {
            count--
        }
    }

    return candidate
}

3. 颜色分类

题目描述：给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

解题思路：使用三指针方法，一个指针用于红色的右边界，一个指针用于蓝色的左边界，一个指针用于当前考虑的元素。

Go 语言代码示例：

func sortColors(nums []int) {
    red, white, blue := 0, 0, len(nums)-1

    for white <= blue {
        switch nums[white] {
        case 0:
            nums[red], nums[white] = nums[white], nums[red]
            red++
            white++
        case 1:
            white++
        case 2:
            nums[white], nums[blue] = nums[blue], nums[white]
            blue--
        }
    }
}

4. 下一个排列

题目描述：实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。

解题思路：从后向前查找第一个相邻升序的元素对 (i, i+1)，然后从后向前查找第一个大于 nums[i] 的元素并交换，最后将 i+1 到末尾的部分翻转。

Go 语言代码示例：

func nextPermutation(nums []int) {
    i := len(nums) - 2
    for i >= 0 && nums[i] >= nums[i+1] {
        i--
    }
    if i >= 0 {
        j := len(nums) - 1
        for j >= 0 && nums[i] >= nums[j] {
            j--
        }
        nums[i], nums[j] = nums[j], nums[i]
    }
    reverse(nums, i+1)
}

func reverse(nums []int, start int) {
    i, j := start, len(nums)-1
    for i < j {
        nums[i], nums[j] = nums[j], nums[i]
        i++
        j--
    }
}

5. 寻找重复数

题目描述：给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），假设只有一个重复的整数，找出这个重复的数。

解题思路：使用快慢指针法（Floyd's Tortoise and Hare），类似于链表找环的入口。

Go 语言代码示例：

func findDuplicate(nums []int) int {
    slow := nums[0]
    fast := nums[nums[0]]

    // Find the intersection point of the two runners.
    for slow != fast {
        slow = nums[slow]
        fast = nums[nums[fast]]
    }

    // Find the "entrance" to the cycle.
    slow = 0
    for slow != fast {
        slow = nums[slow]
        fast = nums[fast]
    }

    return slow
}

在解决算法问题时，理解问题和确定解题策略是至关重要的。上述代码示例展示了如何使用 Go 语言来实现这些策略。在实际编码时，还需要注意代码的整洁和性能优化。

hot-100