BFS模板-宽度优先搜索（Breadth First Search）
1.模板
/// <summary>
/// BFS遍历
/// </summary>
/// <param name="start">开始节点</param>
/// <param name="target">目标节点</param>
/// <returns></returns>
public int BFS(Node start, Node target)
{
//利用队列先进先出（FIFO）的特点
Queue<Node> que = new Queue<Node>();
HashSet<Node> visited = new HashSet<Node>(); //避免走回头路
int leval = 0; // 记录遍历的层数
if (start != null)
{
que.Enqueue(start); //将起点加入队列
visited.Add(start);
}
while (que.Count > 0)
{
int len = que.Count;
//当前层中的所有节点
for (int i = 0; i < len; i++)
{
Node cur = que.Dequeue();
/* 划重点：这里判断是否到达终点 */
if (cur == target)
return leval;
/* 将 cur 的下一层子节点加入队列 */
foreach (Node x in cur.childList)
{
if (!visited.Contains(x))
{
que.Enqueue(x);
visited.Add(x);
}
}
}
/* 划重点：更新步数在这里 */
leval++;
}
return leval;
}
2.推荐题目
- https://leetcode.cn/problems/binary-tree-level-order-traversal/
- https://leetcode.cn/problems/minimum-depth-of-binary-tree/
- https://leetcode.cn/problems/open-the-lock/
回溯模板
通用模板
List<List<T>> res = new List<List<T>>();
List<T> path = new List<T>();
public void Backtracking(入参)
{
if (满足结束条件)
{
result.add(路径);
return;
}
for (选择 in 选择列表)
{
做选择
backtrack(路径, 选择列表)
撤销选择
}
}
无论是排列、组合还是子集问题，简单说无非就是让你从序列 nums 中以给定规则取若干元素
1. 元素无重不可复选
元素无重不可复选，即 nums 中的元素都是唯一的，每个元素最多只能被使用一次，这也是最基本的形式
组合、分割、子集
//问题：输入一个无重复元素的数组 nums，其中每个元素最多使用一次，请你返回 nums 的所有子集
List<List<int>> res = new List<List<int>>();
List<int> path = new List<int>();
public List<List<int>> Subsets(int[] nums)
{
BackTrack(nums, 0);
return res;
}
public void BackTrack(int[] nums, int start)
{
res.Add(new List<int>(path));
/*从入参下标开始*/
for (int i = start; i < nums.Length; i++)
{
path.Add(nums[i]);
BackTrack(nums, i + 1);
path.RemoveAt(path.Count - 1);
}
}
排列
/* 问题：输入一组不重复的数字，返回它们的全排列 */
List<List<int>> res = new List<List<int>>();
List<int> path = new List<int>();
//去重，记录元素是否被使用
bool[] used;
public List<List<int>> Permute(int[] nums)
{
used = new bool[nums.Length];
BackTrack(nums);
return res;
}
void BackTrack(int[] nums)
{
if (path.Count == nums.Length)
{
res.Add(new List<int>(path));
return;
}
/*排列 i从0开始*/
for (int i = 0; i < nums.Length; i++)
{
if (used[i])
continue;
//选择
used[i] = true;
path.Add(nums[i]);
//递归
BackTrack(nums);
//回溯
path.RemoveAt(path.Count-1);
used[i] = false;
}
}
2. 元素可重不可复选
组合、分割、子集
/*问题：给你一个整数数组 nums，其中可能包含重复元素，请你返回该数组所有可能的子集*/
List<List<int>> res = new List<List<int>>();
List<int> path = new List<int>();
public List<List<int>> subsetsWithDup(int[] nums)
{
// 先排序，让相同的元素靠在一起
Array.Sort(nums);
backtrack(nums, 0);
return res;
}
void backtrack(int[] nums, int start)
{
// 前序位置，每个节点的值都是一个子集
res.Add(new List<int>(path));
for (int i = start; i < nums.Length; i++)
{
// 剪枝逻辑，值相同的相邻树枝，只遍历第一条
if (i > start && nums[i] == nums[i - 1])
{
continue;
}
path.Add(nums[i]);
backtrack(nums, i + 1);
path.RemoveAt(path.Count);
}
}
排列
/*问题：给你输入一个可包含重复数字的序列 nums，请你写一个算法，返回所有可能的全排列，*/
List<List<int>> res = new List<List<int>>();
List<int> path = new List<int>();
bool[] used;
public List<List<int>> permuteUnique(int[] nums)
{
// 先排序，让相同的元素靠在一起
Array.Sort(nums);
used = new bool[nums.Length];
Backpath(nums);
return res;
}
void Backpath(int[] nums)
{
if (path.Count == nums.Length)
{
res.Add(new List<int>(path));
return;
}
for (int i = 0; i < nums.Length; i++)
{
// 新添加的剪枝逻辑，固定相同的元素在排列中的相对位置
if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1])
{
continue;
}
path.Add(nums[i]);
used[i] = true;
Backpath(nums);
path.RemoveAt(path.Count);
used[i] = false;
}
}
3. 元素无重可复选
组合、分割、子集
/*问题：给你一个无重复元素的整数数组 candidates 和一个目标和 target，找出 candidates 中可以使数字和为目标数 target 的所有组合*/
List<List<int>> res = new List<List<int>>();
List<int> path = new List<int>();
int sum = 0;
public List<List<int>> CombinationSum(int[] candidates, int target)
{
if (candidates.Length == 0)
{
return res;
}
BackTrack(candidates, 0, target);
return res;
}
void BackTrack(int[] nums, int start, int target)
{
// base case，找到目标和，记录结果
if (sum == target)
{
res.Add(new List<int>(path));
return;
}
// base case，超过目标和，停止向下遍历
if (sum > target)
{
return;
}
for (int i = start; i < nums.Length; i++)
{
// 选择 nums[i]
sum += nums[i];
path.Add(nums[i]);
// 递归遍历下一层回溯树
// 同一元素可重复使用，注意参数
BackTrack(nums, i, target);
// 撤销选择 nums[i]
sum -= nums[i];
path.RemoveAt(path.Count-1);
}
}
排列
List<List<int>> res =new List<List<int>>();
List<int> path =new List<int>();
public List<List<int>> permuteRepeat(int[] nums)
{
BackTrack(nums);
return res;
}
void BackTrack(int[] nums)
{
if (path.Count == nums.Length)
{
res.Add(new List<int>(path));
return;
}
// 回溯算法标准框架
for (int i = 0; i < nums.Length; i++)
{
// 做选择
path.Add(nums[i]);
// 进入下一层回溯树
BackTrack(nums);
// 取消选择
path.RemoveAt(path.Count-1);
}
}
4. 元素可重可复选
将元素去重后，执行元素无重可复选
二叉树遍历
DFS方法，前中后、层序遍历
/// <summary>
/// 前序遍历（中左右）
/// </summary>
/// <param name="root"></param>
/// <returns></returns>
public IList<int> PreorderTraversal(TreeNode root)
{
List<int> result = new List<int>();
Preorder(result, root);
return result;
}
public void Preorder(List<int> result, TreeNode node)
{
if (node == null) return;
result.Add(node.val);//中
Preorder(result, node.left);//左
Preorder(result, node.right);//右
}
/// <summary>
/// 中序遍历（左中右）
/// </summary>
/// <param name="root"></param>
/// <returns></returns>
public IList<int> InorderTraversal(TreeNode root)
{
List<int> result = new List<int>();
Inorder(result, root);
return result;
}
public void Inorder(List<int> result, TreeNode node)
{
if (node == null) return;
Inorder(result, node.left);//左
result.Add(node.val);//中
Inorder(result, node.right);//右
}
/// <summary>
/// 后序遍历（左右中）
/// </summary>
/// <param name="root"></param>
/// <returns></returns>
public IList<int> PostOrderTraversal(TreeNode root)
{
List<int> result = new List<int>();
PostOrder(result, root);
return result;
}
public void PostOrder(List<int> result, TreeNode node)
{
if (node == null) return;
PostOrder(result, node.left);//左
PostOrder(result, node.right);//右
result.Add(node.val);//中
}
/// <summary>
/// 层序遍历
/// </summary>
/// <param name="root"></param>
/// <returns></returns>
IList<IList<int>> res = new List<IList<int>>();
public IList<IList<int>> LevelOrder(TreeNode root)
{
LevelDFS(root, 0);
return res;
}
public void LevelDFS(TreeNode root, int deep)
{
if (root == null) return;
deep++;
if (res.Count < deep)
{
IList<int> item = new List<int>();
res.Add(item);
}
res[deep - 1].Add(root.val);
LevelDFS(root.left, deep);
LevelDFS(root.right, deep);
}
BFS方法，前中后、层序遍历
/// <summary>
/// 前序遍历（中左右）
/// </summary>
/// <param name="root"></param>
/// <returns></returns>
public IList<int> PreOrderTraversal(TreeNode root)
{
IList<int> res = new List<int>();
Stack<TreeNode> st = new Stack<TreeNode>();
if (root != null) st.Push(root);
while (st.Count > 0)
{
TreeNode node = st.Pop();
if (node != null)
{
if (node.right != null) st.Push(node.right);
if (node.left != null) st.Push(node.left);
st.Push(node);
st.Push(null);
}
else
{
node = st.Pop();
res.Add(node.val);
}
}
return res;
}
/// <summary>
/// 中序遍历（左中右）
/// </summary>
/// <param name="root"></param>
/// <returns></returns>
public IList<int> InorderTraversal(TreeNode root)
{
IList<int> res = new List<int>();
Stack<TreeNode> st = new Stack<TreeNode>();
if (root != null) st.Push(root);
while (st.Count > 0)
{
TreeNode node = st.Pop();
if (node != null)
{
if (node.right != null) st.Push(node.right);
st.Push(node);
st.Push(null);
if (node.left != null) st.Push(node.left);
}
else
{
node = st.Pop();
res.Add(node.val);
}
}
return res;
}
/// <summary>
/// 后序遍历（左右中）
/// </summary>
/// <param name="root"></param>
/// <returns></returns>
public IList<int> PostOrderTraversal(TreeNode root)
{
IList<int> res = new List<int>();
Stack<TreeNode> st = new Stack<TreeNode>();
if (root != null) st.Push(root);
while (st.Count > 0)
{
TreeNode node = st.Pop();
if (node != null)
{
st.Push(node);
st.Push(null);
if (node.right != null) st.Push(node.right);
if (node.left != null) st.Push(node.left);
}
else
{
node = st.Pop();
res.Add(node.val);
}
}
return res;
}
/// <summary>
/// 层序遍历
/// </summary>
/// <param name="root"></param>
/// <returns></returns>
IList<IList<int>> res = new List<IList<int>>();
public IList<IList<int>> LevelOrder(TreeNode root)
{
Queue<TreeNode> que = new Queue<TreeNode>();
if (root != null) que.Enqueue(root);
while (que.Count > 0)
{
IList<int> item = new List<int>();
int len = que.Count;
while (len > 0)
{
TreeNode node = que.Dequeue();
item.Add(node.val);
if (node.left != null) que.Enqueue(node.left);
if (node.right != null) que.Enqueue(node.right);
len--;
}
res.Add(item);
}
return res;
}
排序算法
快速排序
//right=Length-1;
public void QuickSort(int[] nums, int left, int right)
{
if (left >= right) return;
/*添加随机获取下标，变成随机快排*/
int s = new Random().Next(right - left + 1) + left;
int item = nums[s];
nums[s] = nums[right];
nums[right] = item;
//常规快排
int index = Sort(nums, left, right);
QuickSort(nums, left, index);
QuickSort(nums, index+1, right);
}
public int Sort(int[] nums, int left, int right)
{
int key = nums[left];//基准数
while (left < right)
{
while (left < right && nums[right] >= key) right--;
nums[left] = nums[right];
while (left < right && nums[left] <= key) left++;
nums[right] = nums[left];
}
nums[left] = key;
return right;//左开右闭 返回right
}
归并排序
int[] temp;
public int[] SortArray(int[] nums)
{
if (nums == null || nums.Length == 0) return nums;
temp = new int[nums.Length];
MergeSort(nums, 0, nums.Length - 1);
return nums;
}
public void MergeSort(int[] nums, int left, int right)
{
if (left == right) return;
int mid = left + (right - left) / 2;//中间节点
//类似二叉树后序遍历
MergeSort(nums, left, mid);
MergeSort(nums, mid + 1, right);
Merge(nums, left, mid, right);
}
//以mid为中间点合并[left..mid]和[mid+1..right]
public void Merge(int[] nums, int left, int mid, int right)
{
//nums [3,5,2,6]
//[left..mid]=[3,5]
//[mid+1..right]=[2,6]
for (int i = left; i <= right; i++)
{
temp[i] = nums[i];
}
//temp [3,5,6,2]
int rl = left;
int rr = mid+1;
for (int i = left; i <= right; i++)
{
if (rl == mid+1)//左指针到头
nums[i] = temp[rr++];
else if (rr == right+1)//右指针到头
nums[i] = temp[rl++];
else if (temp[rl] > temp[rr])//左大于右
nums[i] = temp[rr++];
else
nums[i] = temp[rl++];
}
}
堆排序
//对于大顶堆：arr[i] >= arr[2i + 1] && arr[i] >= arr[2i + 2]
//对于小顶堆：arr[i] <= arr[2i + 1] && arr[i] <= arr[2i + 2]
//1、将无序序列构建成一个大顶堆。
//2.将堆顶元素和最后一个元素交换，然后将剩下的节点重新构造成一个大顶堆；
//3.重复步骤2，如此反复，从第一次构建大顶堆开始，每一次构建，我们都能获得一个序列的最大值，然后把它放到大顶堆的尾部。最后，就得到一个有序的序列了
//3, 2, 3, 1, 2, 4, 5, 5, 6
public int[] HeapSort(int[] nums)
{
//这里元素的索引是从0开始的,所以最后一个非叶子结点array.length/2 - 1
for (int i = nums.Length / 2 - 1; i >= 0; i--)
{
adjustHeap(nums, i, nums.Length); //调整堆
}
// 上述逻辑，建堆结束
// 下面，开始排序逻辑
for (int j = nums.Length - 1; j > 0; j--)
{
// 元素交换,作用是去掉大顶堆
// 把大顶堆的根元素，放到数组的最后；换句话说，就是每一次的堆调整之后，都会有一个元素到达自己的最终位置
swap(nums, 0, j);
// 元素交换之后，毫无疑问，最后一个元素无需再考虑排序问题了。
// 接下来我们需要排序的，就是已经去掉了部分元素的堆了，这也是为什么此方法放在循环里的原因
// 而这里，实质上是自上而下，自左向右进行调整的
adjustHeap(nums, 0, j);
}
return nums;
}
public static void adjustHeap(int[] array, int i, int length)
{
// 先把当前元素取出来，因为当前元素可能要一直移动
int temp = array[i];
for (int k = 2 * i + 1; k < length; k = 2 * k + 1)
{ //2*i+1为左子树i的左子树(因为i是从0开始的),2*k+1为k的左子树
// 让k先指向子节点中最大的节点
if (k + 1 < length && array[k] < array[k + 1])
{ //如果有右子树,并且右子树大于左子树
k++;
}
//如果发现结点(左右子结点)大于根结点，则进行值的交换
if (array[k] > temp)
{
swap(array, i, k);
// 如果子节点更换了，那么，以子节点为根的子树会受到影响,所以，循环对子节点所在的树继续进行判断
i = k;
}
else
{ //不用交换，直接终止循环
break;
}
}
}
public static void swap(int[] arr, int a, int b)
{
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
滑动窗口
/* 滑动窗口算法框架 */
void SlidingWindow(string s)
{
Dictionary<char, int> window=new Dictionary<char, int>();
int left = 0, right = 0;
while (right < s.Length)
{
// c 是将移入窗口的字符
char c = s[right];
// 增大窗口
right++;
// 进行窗口内数据的一系列更新
/*
* ...
*/
/*** debug 输出的位置 ***/
// 注意在最终的解法代码中不要 print
// 因为 IO 操作很耗时，可能导致超时
Console.WriteLine("window: [%d, %d)\n", left, right);
/********************/
// 判断左侧窗口是否要收缩
while (window needs shrink) {
// d 是将移出窗口的字符
char d = s[left];
// 缩小窗口
left++;
// 进行窗口内数据的一系列更新
/*
* ...
*/
}
}
}
并查集模板
class UF
{
// 连通分量个数
private int count;
// 存储每个节点的父节点
private int[] parent;
// n 为图中节点的个数
public UF(int n)
{
count = n;
parent = new int[n];
for (int i = 0; i < n; i++)
{
parent[i] = i;
}
}
// 将节点 p 和节点 q 连通
public void Union(int p, int q)
{
int rootP = Find(p);
int rootQ = Find(q);
if (rootP == rootQ)
return;
parent[rootQ] = rootP;
// 两个连通分量合并成一个连通分量
count--;
}
// 判断节点 p 和节点 q 是否连通
public bool Connected(int p, int q)
{
int rootP = Find(p);
int rootQ = Find(q);
return rootP == rootQ;
}
public int Find(int x)
{
if (parent[x] != x)
{
parent[x] = Find(parent[x]);
}
return parent[x];
}
// 返回图中的连通分量个数
public int Count()
{
return count;
}
}
前缀和，差分数组模板
前缀和模板
/// <summary>
/// 前缀和模板
/// </summary>
class NumArray
{
// 前缀和数组
private int[] preSum;
/* 输入一个数组，构造前缀和 */
public NumArray(int[] nums)
{
// preSum[0] = 0，便于计算累加和
preSum = new int[nums.Length + 1];
// 计算 nums 的累加和
for (int i = 1; i < preSum.Length; i++)
{
preSum[i] = preSum[i - 1] + nums[i - 1];
}
}
/* 查询闭区间 [left, right] 的累加和 */
public int SumRange(int left, int right)
{
return preSum[right + 1] - preSum[left];
}
}
查分数组模板
/// <summary>
/// 查分数组模板
/// </summary>
class Difference
{
// 差分数组
private int[] diff;
/* 输入一个初始数组，区间操作将在这个数组上进行 */
public Difference(int[] nums)
{
diff = new int[nums.Length];
// 根据初始数组构造差分数组
diff[0] = nums[0];
for (int i = 1; i < nums.Length; i++)
{
diff[i] = nums[i] - nums[i - 1];
}
}
/* 给闭区间 [i, j] 增加 val（可以是负数）*/
public void Increment(int i, int j, int val)
{
diff[i] += val;
if (j + 1 < diff.Length)
{
diff[j + 1] -= val;
}
}
/* 返回结果数组 */
public int[] Result()
{
int[] res = new int[diff.Length];
// 根据差分数组构造结果数组
res[0] = diff[0];
for (int i = 1; i < diff.Length; i++)
{
res[i] = res[i - 1] + diff[i];
}
return res;
}
}
动态规划模板
基础问题
//不同的二叉搜索树
public int NumTrees(int n)
{
//初始化 dp 数组
int[] dp = new int[n + 1];
//初始化0个节点和1个节点的情况
dp[0] = 1;
dp[1] = 1;
for (int i = 2; i <= n; i++)
{
for (int j = 1; j <= i; j++)
{
//对于第i个节点，需要考虑1作为根节点直到i作为根节点的情况，所以需要累加
//一共i个节点，对于根节点j时,左子树的节点个数为j-1，右子树的节点个数为i-j
dp[i] += dp[j - 1] * dp[i - j];
}
}
return dp[n];
}
背包问题
01背包
class Solution
{
public static void Main(String[] args)
{
int[] weight = { 1, 3, 4 };
int[] value = { 15, 20, 30 };
int bagWight = 4;
TestWeightBagProblem(weight, value, bagWight);
}
public static void TestWeightBagProblem(int[] weight, int[] value, int bagWeight)
{
int wLen = weight.Length;
//定义dp数组：dp[j]表示背包容量为j时，能获得的最大价值
int[] dp = new int[bagWeight + 1];
//遍历顺序：先遍历物品，再遍历背包容量
for (int i = 0; i < wLen; i++)
{
for (int j = bagWeight; j >= weight[i]; j--)
{
dp[j] = Math.Max(dp[j], dp[j - weight[i]] + value[i]);
}
}
//打印dp数组
for (int j = 0; j <= bagWeight; j++)
{
Console.WriteLine(dp[j] + " ");
}
}
}
完全背包
private static void TestCompletePack()
{
int[] weight = { 1, 3, 4 };
int[] value = { 15, 20, 30 };
int bagWeight = 4;
int[] dp = new int[bagWeight + 1];
for (int i = 0; i < weight.Length; i++)
{ // 遍历物品
for (int j = weight[i]; j <= bagWeight; j++)
{ // 遍历背包容量
dp[j] = Math.Max(dp[j], dp[j - weight[i]] + value[i]);
}
}
}
打家劫舍
打家劫舍1
public int Rob(int[] nums)
{
if (nums == null || nums.Length == 0) return 0;
if (nums.Length == 1) return nums[0];
int[] dp = new int[nums.Length];
dp[0] = nums[0];
dp[1] = Math.Max(dp[0], nums[1]);
for (int i = 2; i < nums.Length; i++)
{
dp[i] = Math.Max(dp[i - 1], dp[i - 2] + nums[i]);
}
return dp[nums.Length - 1];
}
打家劫舍II
public int Rob(int[] nums)
{
if (nums == null || nums.Length == 0)
return 0;
int len = nums.Length;
if (len == 1)
return nums[0];
return Math.Max(RobAction(nums, 0, len - 1), RobAction(nums, 1, len));
}
int RobAction(int[] nums, int start, int end)
{
int x = 0, y = 0, z = 0;
for (int i = start; i < end; i++)
{
y = z;
z = Math.Max(y, x + nums[i]);
x = y;
}
return z;
}
打家劫舍 III
public int Rob3(TreeNode root)
{
int[] res = RobAction1(root);
return Math.Max(res[0], res[1]);
}
int[] RobAction1(TreeNode root)
{
int[] res = new int[2];
if (root == null)
return res;
int[] left = RobAction1(root.left);
int[] right = RobAction1(root.right);
res[0] = Math.Max(left[0], left[1]) + Math.Max(right[0], right[1]);
res[1] = root.val + left[0] + right[0];
return res;
}
股票问题
子序列问题
单调栈模板
int[] NextGreaterElement(int[] nums)
{
int n = nums.Length;
// 存放答案的数组
int[] res = new int[n];
Stack<int> s = new Stack<int>();
// 倒着往栈里放
for (int i = n - 1; i >= 0; i--)
{
// 判定个子高矮
while (s.Count>0 && s.Peek() <= nums[i])
{
// 矮个起开，反正也被挡着了。。。
s.Pop();
}
// nums[i] 身后的更大元素
res[i] = s.Count>0 ? -1 : s.Peek();
s.Push(nums[i]);
}
return res;
}
图遍历框架
// 记录被遍历过的节点
bool[] visited;
// 记录从起点到当前节点的路径
bool[] onPath;
/* 图遍历框架 */
void Traverse(Graph graph, int s)
{
if (visited[s]) return;
// 经过节点 s，标记为已遍历
visited[s] = true;
// 做选择：标记节点 s 在路径上
onPath[s] = true;
for (int neighbor : graph.neighbors(s))
{
bool(graph, neighbor);
}
// 撤销选择：节点 s 离开路径
onPath[s] = false;
}
常用的位运算
几个有趣的位操作
1. 利用或操作 | 和空格将英文字符转换为小写
('a' | ' ') = 'a'
('A' | ' ') = 'a'
2. 利用与操作 & 和下划线将英文字符转换为大写
('b' & '_') = 'B'
('B' & '_') = 'B'
3. 利用异或操作 ^ 和空格进行英文字符大小写互换
('d' ^ ' ') = 'D'
('D' ^ ' ') = 'd'
4. 判断两个数是否异号
int x = -1, y = 2;
bool f = ((x ^ y) < 0); // true
int x = 3, y = 2;
bool f = ((x ^ y) < 0); // false
5. 不用临时变量交换两个数
int a = 1, b = 2;
a ^= b;
b ^= a;
a ^= b;
// 现在 a = 2, b = 1
6. 加一
int n = 1;
n = -~n;
// 现在 n = 2
7. 减一
int n = 2;
n = ~-n;
// 现在 n = 1
n & (n-1) 的运用
n & (n-1) 这个操作是算法中常见的，作用是消除数字 n 的二进制表示中的最后一个 1。
1. 计算汉明权重（Hamming Weight）
int HammingWeight(int n) {
int res = 0;
while (n != 0) {
n = n & (n - 1);
res++;
}
return res;
}
2. 判断一个数是不是 2 的指数
//一个数如果是 2 的指数，那么它的二进制表示一定只含有一个 1：
bool IsPowerOfTwo(int n) {
if (n <= 0) return false;
return (n & (n - 1)) == 0;
}
a ^ a = 0的运用
1. 查找只出现一次的元素
int SingleNumber(int[] nums) {
int res = 0;
for (int n : nums) {
res ^= n;
}
return res;
}
求素数模板
//O(N * loglogN)
int CountPrimes(int n)
{
bool[] isPrime = new bool[n];
Array.Fill(isPrime, true);
for (int i = 2; i * i < n; i++)
if (isPrime[i])
for (int j = i * i; j < n; j += i)
isPrime[j] = false;
int count = 0;
for (int i = 2; i < n; i++)
if (isPrime[i]) count++;
return count;
}
最大公约数，最小公倍数
//获取最大公约数
static int GetLargestCommonDivisor(int n1, int n2)
{
int max = n1 > n2 ? n1 : n2;
int min = n1 < n2 ? n1 : n2;
int remainder;
while (min != 0)
{
remainder = max % min;
max = min;
min = remainder;
}
return max;
}
//获取最小公约数
static int GetLeastCommonMutiple(int n1, int n2)
{
return n1 * n2 / GetLargestCommonDivisor(n1, n2);
}
