1.[两数之和]
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
暴力法
public int[] TwoSum(int[] nums, int target)
{
// 第一层循环：遍历数组中的每个数
for (int i = 0; i < nums.Length; i++)
{
// 第二层循环：从i的下一个位置开始遍历
for (int j = i + 1; j < nums.Length; j++)
{
// 判断当前两个数的和是否等于目标值
if (nums[i] + nums[j] == target)
{
return new int[] { i, j }; // 找到答案就立即返回这两个数的索引
}
}
}
return new int[] { 0, 0 }; // 如果没找到，返回默认值
}
哈希法
public int[] TwoSum(int[] nums, int target)
{
// 创建字典，用于存储数字和它的索引
Dictionary<int, int> map = new Dictionary<int, int>();
// 只需要一次遍历
for (int i = 0; i < nums.Length; i++)
{
// 计算需要配对的数字
int complement = target - nums[i];
// 检查字典中是否已经存在配对的数字
if (map.ContainsKey(complement))
{
// 如果存在，返回配对数字的索引和当前数字的索引
return new int[] { map[complement], i };
}
// 如果当前数字不在字典中，将其加入字典
if (!map.ContainsKey(nums[i]))
{
map.Add(nums[i], i);
}
}
return new int[] { 0, 0 };
}
2.[移动零]
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]
双指针
public class Solution {
public void MoveZeroes(int[] nums)
{
// 慢指针指向要填入非零数的位置
int slow = 0;
// 快指针遍历数组寻找非零数
for (int fast = 0; fast < nums.Length; fast++)
{
// 当找到非零数时
if (nums[fast] != 0)
{
// 如果两个指针不同，进行交换
if (slow != fast)
{
nums[slow] = nums[fast];
nums[fast] = 0;
}
// 移动慢指针
slow++;
}
}
}
}
3.[有效的括号]
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。每个右括号都有一个对应的相同类型的左括号。
输入：s = "()[]{}"
输出：true
输入：s = "(]"
输出：false
栈
public class Solution {
public bool IsValid(string s)
{
// 创建一个栈来存储左括号
Stack<char> stack = new Stack<char>();
// 遍历字符串中的每个字符
foreach(char c in s)
{
// 如果是左括号，入栈
if(c == '(' || c == '[' || c == '{')
{
stack.Push(c);
}
// 如果是右括号
else
{
// 如果栈为空，说明没有匹配的左括号
if(stack.Count == 0) return false;
// 获取栈顶的左括号
char top = stack.Pop();
// 检查是否匹配
if(c == ')' && top != '(') return false;
if(c == ']' && top != '[') return false;
if(c == '}' && top != '{') return false;
}
}
// 最后检查栈是否为空
return stack.Count == 0;
}
}
4.[爬楼梯]
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶
动态规划
public class Solution {
public int ClimbStairs(int n) {
// 处理基础情况：如果台阶数小于等于2，直接返回n
if(n <= 2) return n;
// 创建动态规划数组，dp[i]表示爬到第i阶的方法数
int[] dp = new int[n + 1];
dp[1] = 1; // 爬到第1阶只有1种方法
dp[2] = 2; // 爬到第2阶有2种方法
// 从第3阶开始，每一阶的方法数是前两阶方法数的和
for(int i = 3; i <= n; i++) {
dp[i] = dp[i-1] + dp[i-2];
}
// 返回爬到第n阶的方法数
return dp[n];
}
}
递归
public class Solution {
public int ClimbStairs(int n) {
// 处理基础情况
if(n <= 2) return n;
// 只用两个变量记录前两阶的方法数
int prev = 1; // 记录i-2阶的方法数
int curr = 2; // 记录i-1阶的方法数
// 计算每一阶的方法数
for(int i = 3; i <= n; i++) {
int temp = curr; // 暂存当前值
curr = prev + curr; // 新的方法数
prev = temp; // 更新前一阶的方法数
}
return curr;
}
}
5.[杨辉三角]
输入: numRows = 5
输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]