算法模拟题

以下是一些经典的算法模拟题目，涵盖了不同类型的算法和数据结构问题，适合练习和提升编程能力：

1. 跳跃游戏（Jump Game）

问题描述：给定一个非负整数数组 nums，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个位置。

输入：nums = [2, 3, 1, 1, 4]
输出：True
解释：从位置 0 跳跃 1 步到达位置 1，然后从位置 1 跳跃 3 步到达最后一个位置。

2. 旋转排序数组的最小值（Find Minimum in Rotated Sorted Array）

问题描述：假设按照升序排序的数组在预先未知的某个点进行了旋转（例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2]）。请找出数组中的最小元素。你可以假设数组中不存在重复元素。

输入：nums = [4, 5, 6, 7, 0, 1, 2]
输出：0

3. 子集生成（Subsets Generation）

问题描述：给定一个整数数组 nums，所有元素互不相同，求所有可能的子集（即幂集）。

输入：nums = [1, 2, 3]
输出：[[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]]

4. 最长有效括号（Longest Valid Parentheses）

问题描述：给定一个只包含字符 ‘(‘ 和 ‘)’ 的字符串，找出最长的有效（格式正确且连续）括号子串的长度。

输入：s = "(()"
输出：2
解释：最长有效括号子串为 "()"。

5. 岛屿数量（Number of Islands）

问题描述：给定一个由 ‘1’（陆地）和 ‘0’（水）组成的二维网格，计算其中的岛屿数量。岛屿总是被水包围，并且每个岛屿只能由水平方向或垂直方向相邻的陆地连接形成。

输入：

grid = [  
  ['1', '1', '0', '0', '0'],  
  ['1', '1', '0', '0', '0'],  
  ['0', '0', '1', '0', '0'],  
  ['0', '0', '0', '1', '1']  
]  
```  
**输出**：`3`  
**解释**：分别有三个岛屿。

### 6. 无重复字符的最长子串（Longest Substring Without Repeating Characters）
**问题描述**：给定一个字符串 `s`，请你找出其中不含有重复字符的最长子串的长度。

**输入**：`s = "abcabcbb"`  
**输出**：`3`  
**解释**：答案是 `"abc"`，长度为 3。

### 7. 编辑距离（Edit Distance）
**问题描述**：给定两个单词 `word1` 和 `word2`，计算将 `word1` 转换为 `word2` 所使用的最少操作数。你可以对一个单词进行以下三种操作：插入一个字符、删除一个字符、替换一个字符。

**输入**：`word1 = "horse", word2 = "ros"`  
**输出**：`3`  
**解释**：  
1. 将 "horse" 变为 "rorse" （替换 'h' 为 'r'）  
2. 将 "rorse" 变为 "rose" （删除 'r'）  
3. 将 "rose" 变为 "ros" （删除 'e'）  

### 8. 最大矩形（Maximal Rectangle）
**问题描述**：给定一个仅包含 0 和 1 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。

**输入**：  

matrix = [
[‘1’, ‘0’, ‘1’, ‘0’, ‘0’],
[‘1’, ‘0’, ‘1’, ‘1’, ‘1’],
[‘1’, ‘1’, ‘1’, ‘1’, ‘1’],
[‘1’, ‘0’, ‘0’, ‘1’, ‘0’]
]
`` **输出**：6`
解释：最大矩形包含 6 个 1。

9. 字符串的全排列（Permutations of a String）

问题描述：给定一个字符串 s，求出该字符串的所有可能的排列。

输入：s = "abc"
输出：["abc", "acb", "bac", "bca", "cab", "cba"]

10. 零钱兑换（Coin Change）

问题描述：给定不同面额的硬币和一个总金额，计算凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

输入：coins = [1, 2, 5], amount = 11
输出：3
解释：11 = 5 + 5 + 1

这些问题涵盖了动态规划、回溯、贪心、图算法、字符串处理等不同类型的经典算法问题，非常适合用于面试准备和编程能力的提升。