wyf 的个人博客

AcWing 算法基础课题单练习（一） 1. 基础算法 1.1 排序 1.1.1 快速排序 快速排序 是一种基于分治思想的排序算法，其基本思想是通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序的目的。这个处理的过程是 自上而下 的。 123456789101112131415161718192021222324252627282930313233343536373839404142434445#include<iostream>#include<vector>using namespace std;const int N = 1e5+7;void quickSort(vector<int>& nums, int l, int r) { if(l >= r) { return; } // 随机选择一个数作为基准 int x =...

二进制问题 要点 二进制码：利用位运算，每次将数字与1进行与运算，如果结果为1，则表示该位为1，计数器加1，然后将数字右移一位，继续与1进行与运算，直到数字为0为止。 反码：将二进制码取反得到反码，注意 符号位不参与 翻转。 补码：正数的二进制码与补码相同，负数的绝对值的二进制码取反（符号位不翻转）加一得到补码 需要注意INT_MIN，因为INT_MIN在32位整型中没有对应的正数，取反加一后将溢出，所以需要将由负数转换成的正数以无符号整数的形式保存 例题1 二进制表示中1的个数 题目描述 编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为汉明重量）。 示例 123输入：00000000000000000000000000001011输出：3解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为...

背包问题 背包问题指的是给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。它是一个经典的动态规划问题，有很多种变体（如01背包，完全背包，多重背包等）。 一、01背包问题 01背包问题指的是给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价值最高。每种物品只能 选择一次。 例题1.1 2.01背包问题 有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。第 i 件物品的体积是 viv_ivi​，价值是 wiw_iwi​。求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。 输出最大价值。 输入格式 第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。接下来有 N 行，每行两个整数 viv_ivi​,wiw_iwi​，用空格隔开，分别表示第 i 件物品的体积和价值。 输出格式 输出一个整数，表示最大价值。 数据范围 0<N,V≤10000<N,...

ACM算法复习笔记——素数与合数 素数 素数是指大于1的自然数中，除了1和它本身外没有其他因数的数。 素数的判定 暴力求解法 单个数的判定：遍历从2到n的所有整数，判断n是否能被这些整数整除。 1234567891011121314# include <iostream>using namespace std;bool is_prime(int n) { // judge if n is a prime number if(n <= 1) return false; // 1 and less are not prime numbers for(int i=2; i*i <= n; i++) { if(n%i == 0) { return false; // n is divisible by i, so it's not a prime number } } return true; // n is a...

LZ 编码和解码 LZ编码是字典编码的一种方法，包括LZ77编码、LZ78编码和LZW编码。它将常用的符号模式存储在字典中，用其在字典中的码字作为标识符传递，对未命中内容使用缺省的编码方式（较为低效）。 LZ77编码 基本方法： 字典为先前已遍历序列的末尾定长的一段序列（搜索缓冲区），机制类似于滑动窗口。 算法： 滑动窗口从左到右依次是搜索缓冲区、搜索指针和前向缓冲区。在移动搜索指针到一个新位置以后，尝试从搜索缓冲区中找出与当前所指向的字符串匹配的最长字符串。 编码输出格式： 对每一个字符串，使用一个三元组<o,l,c>表示，例如下图的就是<7, 4, C(‘r’)>。其中： o表示offset=Search pointer - Match...

快速排序 快速排序算法 快速排序是一种基于分治思想的排序算法，其基本思想是选择一个基准元素，将数组分为两部分，一部分小于基准元素，一部分大于基准元素，然后对这两部分分别进行快速排序。 时间复杂度 O(nlog⁡n)O(n \log n)O(nlogn)，最坏情况下为...

堆 堆的定义 堆是一种特殊的完全二叉树，其中每个节点的值都大于或等于（最大堆）或小于或等于（最小堆）其子节点的值。 堆的性质 堆的根节点（最大堆的根节点是最大值，最小堆的根节点是最小值）。 堆的每个子树也是一个堆。 堆的节点数为 nnn，则其高度为 log⁡2n\log_2 nlog2​n。 堆的实现 堆的实现通常使用数组来表示，其中每个元素的索引表示节点在树中的位置。 堆的插入 堆的插入操作通常是将新元素添加到数组的末尾，然后通过上浮操作（sift up）将新元素移动到正确的位置。 堆的删除 堆的删除操作通常是将根节点删除，然后通过下沉操作（sift down）将最后一个元素移动到根节点的位置。

Manacher算法 Manacher算法是一种用于在字符串中查找最长回文子串的算法。它通过将字符串转换为一个新的字符串，并利用回文的对称性来加速查找过程。也是一种动态规划算法。 时间复杂度 O(n)O(n)O(n) 空间复杂度 O(n)O(n)O(n) 算法步骤 1. 预处理 当回文串的长度为奇数时，回文串的中心是唯一的，不会出现重复，因此要保证回文串的长度为奇数。一奇一偶相加，结果为奇数。 为此，在开头插入一个不存在于原字符串中的特殊字符（通常是^），在结尾插入一个不存在于原字符串中的特殊字符（通常是$），在原字符串的每个字符之间插入一个不存在于原字符串中的特殊字符（通常是#），这样回文串的长度就变成了奇数。 123456def manacher(s): # 预处理字符串 T = '^#' + '#'.join(s) + '#$' n = len(T) P = [0] * n # 回文半径数组 C, R = 0, 0 # 回文中心和回文右边界 2....

组合问题 一、问题特点 组合问题是回溯算法的典型应用，这类问题往往会给出一个元素的集合，要求找出所有满足指定条件的子集。其核心思想就是遍历整个树，找出所有满足情况的子集，在适当条件下也可能需要进行一些剪枝操作。 其中子集的选取通常有以下几个要点： 集合中是否有重复元素 子集中是否有重复元素 集合中任意一个元素在一个子集中是否只能出现一次（是否可以被无限次重复选取） 子集需要满足哪些特殊条件（元素和为target?/元素数量为k?） 二、相关例题 （一）组合 77.组合（LeetCode） 题目要求： 给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。 你可以按任何顺序返回答案。 示例： 输入：n = 4, k = 2 输出： [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ] 解题思路： 本题从集合[1,...

子集问题 一、问题特点 子集问题要求从指定的集合中找出所有满足特定条件的子集，当使用回溯算法解决子集问题的时候，相当于要获得搜索树上所有满足条件节点的值（在组合和切割问题中只求叶子结点的值） 子集问题有以下注意事项： 因为子集中元素是无序的，所以也需要用startIndex去重 将子集添加到结果数组中的操作应当在每一次回溯函数调用时都被执行 子集问题的搜索方式和组合问题大体相同，当原集合中存在重复元素时，也需要进行树层去重 当子集中不能有重复元素时，需要进行树枝去重 二、相关例题 （一）子集 78.子集（LeetCode） 问题描述： 给你一个整数数组 nums ，数组中的元素互不相同。返回该数组所有可能的子集（幂集）。 解集不能包含重复的子集。你可以按任意顺序返回解集。 示例： 输入：nums = [1,2,3] 输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]] 提示： 1 <= nums.length <= 10 -10 <= nums[i] <= 10 nums 中的所有元素...