【唐叔学算法】第16天：枚举-探索所有可能性的艺术_枚举:使用loops穷举可能性来找到答案-CSDN博客

本文链接：https://blog.csdn.net/Tang_is_learning/article/details/144413361

大家好，我是唐叔。今天我们要探讨的是一个看似简单却非常实用的概念——枚举（Enumeration）。它不仅仅是一种数据类型，在算法设计中也是一种解决问题的策略。通过系统地遍历所有可能的情况，我们可以找到满足特定条件的答案。本文将带你深入了解枚举的基本原理、应用场景以及如何通过几个具体的LeetCode题目来实践这一技巧。

一、什么是枚举？

定义

枚举算法，也称为穷举算法，是一种通过遍历所有可能的候选解来寻找正确答案的算法。它的核心思想是检查所有可能的选项，直到找到满足条件的解。

应用场景

穷举搜索：如暴力破解密码。
组合与排列生成：生成所有可能的数字或字母组合。
验证唯一性：检查给定集合内的元素是否唯一。
路径寻找：探索图中的所有路径。

算法实现

使用枚举的关键在于确定问题的所有潜在解，并有效地对它们进行迭代。对于某些问题，这可能意味着逐个测试每一个输入值；而对于其他问题，则可能是构建和评估不同的结构或配置。

注意事项

性能考量：由于枚举往往涉及到大量的计算，因此需要特别注意效率问题，避免不必要的重复工作。
边界条件：确保处理所有特殊情况，比如空输入或其他极端情况。
剪枝优化：尽可能早地识别出不可能成功的路径，以减少不必要的计算。

二、实战解析

入门题：283. 移动零

题目链接：283. 移动零
题目描述：给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

解题思路

这个问题可以通过两次遍历来解决：第一次遍历时只保留非零元素的位置；第二次遍历时填充剩余位置为0。但是更高效的解决方案是使用单次遍历结合交换操作，这样可以保证非零元素的原始顺序不变。

Java代码实现

public class Solution {
    public void moveZeroes(int[] nums) {
        int insertPos = 0;
        for (int num : nums) {
            if (num != 0) {
                nums[insertPos++] = num;
            }
        }
        while (insertPos < nums.length) {
            nums[insertPos++] = 0;
        }
    }
}

中等题：46. 全排列

题目链接：46. 全排列
题目描述：给定一个没有重复数字的序列 nums，返回其所有可能的全排列。

解题思路

此题可以通过枚举来解决。我们从第一个位置开始，依次选择尚未使用的数字作为候选者，然后递归处理剩余的位置，直至完成整个排列。为了防止重复使用同一个数字，我们需要记录哪些数字已经被选中。

Java代码实现

import java.util.*;

public class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(result, new ArrayList<>(), nums, new boolean[nums.length]);
        return result;
    }

    private void backtrack(List<List<Integer>> result, List<Integer> tempList, int[] nums, boolean[] used) {
        if (tempList.size() == nums.length) {
            result.add(new ArrayList<>(tempList));
        } else {
            for (int i = 0; i < nums.length; ++i) {
                if (used[i]) continue;
                used[i] = true;
                tempList.add(nums[i]);
                backtrack(result, tempList, nums, used);
                used[i] = false;
                tempList.remove(tempList.size() - 1); // 撤销选择
            }
        }
    }
}