_starstarli-CSDN博客

原创编译原理—— 有穷自动机（DFA）识别

编译原理—— 有穷自动机（DFA）识别实验目的熟练掌握有穷状态机的结构性质，并且能够推导出有限状态机能够识别的字符串格式实验内容编写程序实现有穷状态机判断该有穷状态机所实现的字符串检测格式算法描述及实验步骤输入任意字符串初始化状态。遍历输入的字符串，对该状态做相应的判断（以该有穷状态自动机为例）倘若该状态为0（初始状态），则进一步判断当前遍历到的字符，假若为a，则修改当前状态为1，假若为b则修改当前状态为2。倘若该状态为1，则进一步判断当前遍历到的

2021-06-18 17:41:06 2222 1

原创编译原理——语法分析器（SLR）

编译原理——语法分析器（SLR）识别语法结构：变量声明（不含变量初始化）if单条件分支语句以及if else 双条件分支语句for循环和while循环语句赋值语句，四则运算，逻辑判断复合语句函数声明函数调用文法//其中$作为标识符判断 @常数值判断Z->SS->while(E)SS->E;SS->;SS->for(E;E;E)SS->CM;SS->C$(W){SreturnE;}SS->$(H);SM->M,$

2021-06-18 17:11:45 6218 2

原创全排列算法

全排列算法1 问题内容输入：一个集合A，其元素类型为int输出：A的全排列2 问题分析算法设计：[1]通过输入获得一个数组集合[2]从数组中依次选择一个数，将其于第一个位置元素交换[3]通过递归的方式求出，剩下n-1个元素的全排列[4]回溯，将原本交换后的元素，交换回来[5]递归出口，当数组中只剩下唯一一个元素时，输出该数组中的元素的排列3 源代码#include <stdio.h>#include <stdlib.h>#define MAXSIZ

2021-04-17 22:03:31 206

原创素数筛模板

素数筛模板int prime[700000],pcnt;bool mark[10000007];// 如果变量名都相同的话,就不用传参了//void getPrimes(int prime[],int N,int &pcnt)int getPrimes(int N){ memset(mark,0,sizeof(mark)); mark[0] = mark[1] = 1; pcnt = 0; for(int i = 2; i <= N ; i ++)

2021-03-20 17:40:37 118

原创奇怪的汉诺塔

奇怪的汉诺塔汉诺塔问题，条件如下：1、这里有A、B、C和D四座塔。2、这里有n个圆盘，n的数量是恒定的。3、每个圆盘的尺寸都不相同。4、所有的圆盘在开始时都堆叠在塔A上，且圆盘尺寸从塔顶到塔底逐渐增大。5、我们需要将所有的圆盘都从塔A转移到塔D上。6、每次可以移动一个圆盘，当塔为空塔或者塔顶圆盘尺寸大于被移动圆盘时，可将圆盘移至这座塔上。请你求出将所有圆盘从塔A移动到塔D，所需的最小移动次数是多少。汉诺塔塔参考模型输入格式没有输入输出格式对于每一个整数n(1≤n≤121≤n≤12

2021-02-18 21:06:05 198

原创 acwing-19

acwing-19a^b(简单)求 aa 的 bb 次方对 pp 取模的值。输入格式三个整数 a,b,pa,b,p ,在同一行用空格隔开。输出格式输出一个整数，表示a^b mod p的值。数据范围0≤a,b≤10^9 0≤a,b≤10^91≤p≤10^9 1≤p≤10^9输入样例：3 2 7输出样例：2快速幂#include <iostream>using namespace std;int main(){ long long int a,b,p

2021-02-18 20:24:47 76

原创 acwing-18

acwing-18构建乘积数组(中等)给定一个数组A[0, 1, …, n-1]，请构建一个数组B[0, 1, …, n-1]，其中B中的元素B[i]=A[0]×A[1]×… ×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法。样例输入：[1, 2, 3, 4, 5]输出：[120, 60, 40, 30, 24]思考题：能不能只使用常数空间？（除了输出的数组之外）题解将结果分为两个部分一个是0 — i-1 一部分是i+1 — n-1所以这里设置两个数组，一个数组

2021-02-17 13:14:12 75

原创 acwing-17

acwing-17股票的最大利润(简单)假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖一次该股票可能获得的利润是多少？例如一只股票在某些时间节点的价格为[9, 11, 8, 5, 7, 12, 16, 14]。如果我们能在价格为5的时候买入并在价格为16时卖出，则能收获最大的利润11。样例输入：[9, 11, 8, 5, 7, 12, 16, 14]输出：11枚举可能会卖出的天数，假设第n天卖出，这样需要在前n天找一个最买入最小的一天，这样算法是O(n^2)我们在枚举卖

2021-02-15 22:04:49 55

原创 acwing-16

acwing-16骰子的点数（简单）将一个骰子投掷n次，获得的总点数为s，s的可能范围为n~6n。掷出某一点数，可能有多种掷法，例如投掷2次，掷出3点，共有[1,2],[2,1]两种掷法。请求出投掷n次，掷出n~6n点分别有多少种掷法。样例1输入：n=1输出：[1, 1, 1, 1, 1, 1]解释：投掷1次，可能出现的点数为1-6，共计6种。每种点数都只有1种掷法。所以输出[1, 1, 1, 1, 1, 1]。样例2输入：n=2输出：[1, 2, 3, 4, 5, 6, 5,

2021-02-15 00:29:45 130

原创 acwing-15

acwing-15翻转单词顺序(中等)输入一个英文句子，单词之前用一个空格隔开，且句首和句尾没有多余空格。翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串"I am a student."，则输出"student. a am I"。样例输入："I am a student."输出："student. a am I"第一种方法，是将字符串中的单词找出来放在临时的数组中，再将这个数组进行字符串的整合class Solution {p

2021-02-12 22:05:25 371

原创 acwing-14

acwing-14数组中唯一只出现一次的数字(困难)在一个数组中除了一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。你可以假设满足条件的数字一定存在。思考题：如果要求只使用 O(n) 的时间和额外 O(1) 的空间，该怎么做呢？样例输入：[1,1,1,2,2,2,3,4,4,4]输出：3因为每个数字都只出现三次，所以倘若我们通过计算元素（以二进制表示）中每一位出现1的个数，通过模3取余得出的就是只出现一次的元素（以二进制表示）中对应位上的值，这样我们便

2021-02-10 23:51:31 74

原创 acwing-13

acwing-13二叉树的深度(简单)输入一棵二叉树的根结点，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。样例输入：二叉树[8, 12, 2, null, null, 6, 4, null, null, null, null]如下图所示： 8 / \ 12 2 / \ 6 4输出：3采用深搜的思想，在遍历二叉树的同时，对当前节点的深度进行计算获取深度的最大值/** * Defin

2021-02-10 00:02:56 55

原创 acwing-12

acwing-120到n-1中缺失的数字(简单)一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0到n-1之内。在范围0到n-1的n个数字中有且只有一个数字不在该数组中，请找出这个数字。样例输入：[0,1,2,4]输出：3该数组具有nums[i]=i的特点采用二分法，将其中不满足nums[i]=i的点的第一个位置查找出来特判是数组最后一个缺失，还是数组中的某一个数缺失class Solution {public: int getMissingN

2021-02-07 23:43:52 128

原创 acwing-11

acwing-11数组中的逆序对（困难）在数组中的两个数字如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。样例输入：[1,2,3,4,5,6,0]输出：6暴历的解法class Solution {public: int inversePairs(vector<int>& nums) { int cnt=0; for(int i=0;i<nums.size();i

2021-02-06 22:32:36 68

原创 acwing-10

acwing-10丑数(中等)我们把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。求第n个丑数的值。样例输入：5输出：5注意：习惯上我们把1当做第一个丑数。因为我们是要求一个丑数，该数只包含2 3 5 三个质因子，那么我们只要用这三个数进行反复的计算，加入到结果集中比如一开始的丑数是1，那么下一个丑数是这1×2或者1×3或者1×5中最小的那个是2，将它添加到丑数集合中接下来的丑数判断应该是2×2或者1×3或者1×

2021-02-05 21:36:12 68

原创 acwing-07

acwing-07最小的k个数(简单)输入n个整数，找出其中最小的k个数。注意：数据保证k一定小于等于输入数组的长度;输出数组内元素请按从小到大顺序排序;样例输入：[1,2,3,4,5,6,7,8] , k=4输出：[1,2,3,4]对元素进行排序，获取k个元素即可采用**sort()**函数排序class Solution {public: vector<int> getLeastNumbers_Solution(vector<int>

2021-02-04 22:22:17 64

原创 acwing-09

acwing-09把数字翻译成字符串（中等）给定一个数字，我们按照如下规则把它翻译为字符串：0翻译成”a”，1翻译成”b”，……，11翻译成”l”，……，25翻译成”z”。一个数字可能有多个翻译。例如12258有5种不同的翻译，它们分别是”bccfi”、”bwfi”、”bczi”、”mcfi”和”mzi”。请编程实现一个函数用来计算一个数字有多少种不同的翻译方法。样例输入："12258"输出：5采用动态规划的思想考虑问题设置dp数组，dp[i]表示前i位数字有多少不同的翻译方式初

2021-02-04 22:20:41 70

原创 acwing-08

acwing-08从1到n整数中1出现的次数(困难)输入一个整数n，求从1到n这n个整数的十进制表示中1出现的次数。例如输入12，从1到12这些整数中包含“1”的数字有1，10，11和12，其中“1”一共出现了5次。样例输入： 12输出： 5直接暴力计算1-n个数，计算1的个数是会超时的这里采用遍历n的位数来计算1的个数例如n=123456假设当前遍历遍历到百位数4那么我们首先可以确定**_ _ _ 4 _ _中千位数，万位数，十万位数的取值范围是000-123**因为我

2021-02-03 22:05:40 61

原创 acwing-01

acwing-01翻转链表（简单）定义一个函数，输入一个链表的头结点，反转该链表并输出反转后链表的头结点。思考题：请同时实现迭代版本和递归版本。样例输入:1->2->3->4->5->NULL输出:5->4->3->2->1->NULL题解：迭代版本利用三个指针：p作为活动指针用于遍历链表pre用于指向活动指针的前一个结点cur用于获取活动指针的下一个结点反转后继结点指针实现反转链表的功能/** *

2021-01-31 22:09:27 61

原创 acwing-06

acwing-05二叉搜索树与双向链表(中等)输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。注意：需要返回双向链表最左侧的节点。例如，输入下图中左边的二叉搜索树，则输出右边的排序双向链表。题解二叉排序树的中序遍历的结果是升序的在进行二叉排序树的中序遍历的过程中，采用双向链表的指针的修改手段因为该结点的左子树指针已经是递归结束后的，所以修改左子树指针是不会有问题的/** * Definition for a

2021-01-31 22:08:59 60

原创 acwing-05

acwing-05二叉搜索树的后序遍历序列(简单)输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回true，否则返回false。假设输入的数组的任意两个数字都互不相同。样例输入：[4, 8, 6, 12, 16, 14, 10]输出：true二叉搜索树的特点就是，左子树的所有结点值都小于根节点，右子树的所有结点值都大于根节点后序遍历，根节点位于一棵树的最后一个值。class Solution {public: bool verifySeque

2021-01-31 22:04:14 64

原创 acwing-04

acwing-04不分行从上往下打印二叉树(简单)从上往下打印出二叉树的每个结点，同一层的结点按照从左到右的顺序打印。样例输入如下图所示二叉树[8, 12, 2, null, null, 6, null, 4, null, null, null] 8 / \ 12 2 / 6 / 4输出：[8, 12, 2, 6, 4]即为二叉树的层次遍历利用队列，将其逐个放入队列，每次从队列中取元素放入结果中class Solution {publ

2021-01-31 22:03:36 66

原创 acwing-03

acwing-03对称的二叉树请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。样例如下图所示二叉树[1,2,2,3,4,4,3,null,null,null,null,null,null,null,null]为对称二叉树： 1 / \ 2 2 / \ / \3 4 4 3如下图所示二叉树[1,2,2,null,4,4,3,null,null,null,null,null,null]不是对称二叉树： 1 /

2021-01-31 22:02:53 51

原创 acwing-02

acwing-02合并两个排序的链表（简单）输入两个递增排序的链表，合并这两个链表并使新链表中的结点仍然是按照递增排序的。样例输入：1->3->5 , 2->4->5输出：1->2->3->4->5->5设置哨兵指向头结点小的链表作为主链表遍历另一条链表，找到正确的位置将链表结点一个一个插到主链表中/** * Definition for singly-linked list. * struct ListNode { *

2021-01-31 22:01:54 50

原创动态规划——序列比对问题

序列比对问题问题要求输入：两个序列A和B，其长度分别为m和n输出：A和B的一种比对形式，其满足惩罚函数f(A,B)值最小。(1) 对A和B之间的每一个空隙匹配，计惩罚分2分；(2)对A和B之间的每一个错配，计惩罚分3分；(3)成功配对不计惩罚分问题分析本题采用动态规划的思想去做对于两个序列A：a1,a2,a3,a4…,anB：b1,b2,b3,b4…,bn在两个序列中当对比到相等元素的时候自然就可以直接匹配，本题所要探究的矛盾点在于当A序列元素与B序列中的元素不等的时候到底是采取将其

2020-12-02 21:44:32 3505

原创动态规划——01背包问题

动态规划——01背包问题问题内容给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大?0-1背包问题是一个特殊的整数规划问题。问题分析求物品的总价值采用动态规划的思想，维护一个二维数组dp[i][j]该数组表示为当有前i个物品选择且背包容量为j时最优价值例如，物品的价值：8,50,12,20,10物品的重量：3,20,5,10,5如dp[1][1]表示物品的选择范围只有第一个，且背包现在的容量为1，

2020-11-20 00:08:33 526

原创动态规划——最长连续上升子序列

动态规划——最长连续上升子序列问题内容输入: 一组可比较元素组成的序列输出: 元素连续上升的最长一段子序列的长度以及该子序列问题分析采用动态规划的思想，维护一个一维数组s[i]该数组记录的是原数组中对应位置的最长连续上升子序列的长度例如，原数组a[10]中的值为:12,15,10,18,20,8,16,14,24,18则对应的一维数组s[10]中的值应为:1,2,1,2,3,1,2,1,2,1其中s[1]的值为2表示从0开始到第二个位置最长连续子序列为2，即12，,15S[

2020-11-19 17:08:44 5383 6

原创整数划分算法

整数划分问题问题阐述将正整数n表示成一系列正整数之和：n=n1+n2+…+nk，其中n1≥n2≥…≥nk≥1，k≥1。正整数n的这种表示称为正整数n的划分。输入：一个正整数n输出：n不同划分个数以及n的划分结果。问题实例例如正整数6有如下11种不同的划分：6；5+1；4+2，4+1+1；3+3，3+2+1，3+1+1+1；2+2+2，2+2+1+1，2+1+1+1+1；1+1+1+1+1+1问题分析n的划分结果计算采用分治思想n本身作为一种划分即为一种，加上剩下种类的个数

2020-10-18 21:01:07 4676

原创棋盘覆盖算法

棋盘覆盖算法问题阐述在一个2k×2k 个方格组成的棋盘中，恰有一个方格与其它方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。求：请给出相应的覆盖方式。解题思路当k>0时，将2k×2k棋盘分割为4个2k-1×2k-1 子棋盘(a)所示。特殊方格必位于4个较小子棋盘之一中，其余3个子棋盘中无特殊方格。为了将这3个无特殊方格的子棋盘转化为特殊棋盘，可以用一个L

2020-09-27 13:07:17 5007

原创稳定婚姻匹配算法

稳定婚姻匹配算法问题概述n名男青年和n名女青年参加一个相亲会。经过了解，每名男青年在心目中都对所有女青年作了一个排序，而每名女青年同样也对男青年作了排序。问这些男女青年之间怎样才能进行理想的配对。给出男青年和女青年的偏好矩阵算法求解过程算法设计：[1]根据男性的偏好矩阵来进行遍历[2]在男性的偏好矩阵中依次寻找女青年，若该女青年没有被匹配便先将该女青年匹配给该男青年。[3]倘若该女青年已经匹配，便在该女青年的偏好矩阵中寻找已经匹配的男青年的优先级和该男青年的优先级，倘若该男青年的优先级更

2020-09-20 16:16:03 3111

原创 bugku web 多次

多次在本题中采用一般的sql注入语法好像无法实现sql注入，进而能够解决该题所以猜测是因为字段被过滤了异或为逻辑运算，当两个条件相同（同真或同假）时为假，当两个条件不同时为真。在mysql中异或用^或xor来表示。当url为http://123.206.87.240:9004/1ndex.php?id=1’^(length(‘and’)!=0)%23若and的长度为0（即为被过滤），则^(length(‘and’)!=0)为假，表达式就为id=1异或0=1，页面正常若and的长度为不为0（即

2020-09-06 20:50:58 346

原创 bugku-web-insert into 注入

insert into 注入题目分析题目地址http://123.206.87.240:8002/web15/首先题目中已经给出了php源码，先分析一下。我在原来的代码上做了一些修改，便于调试操作。<?php //隐藏报错信息 error_reporting(0); // 函数功能获取用户的ip地址 function getIp() { // PHP使用$_SERVER['HTTP_X_FORWARDED_FOR']获取IP //

2020-08-09 17:06:42 222

原创 CTF-入门九

CTF-入门九这里继续bugku web的题解记录.秋名山老司机拿到这道题，告诉你们在两秒之内提交答案，手动肯定是不行的。两秒内刷新是这样的页面，这里也可以知道是post方法传值这里给出脚本，网上的脚本大同小异，这里按照惯例优化了一下代码并给出完整的代码注释import requestsfrom bs4 import BeautifulSoup#获取网页内容，并且提取<div>内容'''通过我们对于题目的源代码的分析可知，在两秒内刷新页面会得到不一样的结果这里其实是会话

2020-07-19 14:19:51 1143

原创 CTF-入门八

CTF-入门八这篇博客是这周关于CTF的学习，其实题没有做多少但是我觉得，内容已经够发一篇博客了。主要的内容有（一）sqli-lab靶场的搭建（二）基于bugku web 成绩单的sql注入入门（三）输入密码查看flag的wp点击一百万次的wp听说备份是个好习惯的wp（一）sqli-lab靶场的搭建sqli-lab搭建这是一个sql注入的练习平台，有很多的关卡等你挑战，哈哈git clone https://github.com/Audi-1/sqli-labs.git这是sqli

2020-06-15 00:59:35 758

原创 python爬虫入门实例

python爬虫入门实例这周的CTF的web题没有写很多，因为要复习应考的原因，就零零碎碎的做了2、3题，等题目量多了在出一篇博客做记录叭，但是博客还是每周尽量出一篇叭，鞭策一下自己的课外学习。那么这篇博客主要是记录一下，如何用python做一个简易的爬虫，这里只是对一些网页中的静态数据的爬取，以后爬爬小论文，实验数据还是比较实用，所以在这里做一个小记录。相当一个入门的小实例，同时我发现，网上的的爬虫代码上的注释写的比较少，不适合初学者，我的代码还是写了一些比较详细的注释的，看起来比较简单叭。那么我们

2020-06-07 20:01:40 666 2

原创 CTF-入门七

CTF-入门七#写在前面的话#bugku上所有杂项题都已经记录完毕，其中无论是暂时做不出来的还是只做到一半的都先做好了记录，希望有时间的时候过去啃一下，但是这么久了还是非常有必要去接触一下CTF其他领域的题目，所以从本周开始会开始，记录WEB的题解，前八道题我之前已经写过了（CTF-入门一），虽然没有具体的解题步骤，但是现在看来前八道题确实是比较简单的题目，所以就没有过多地赘述了。（1）本地包含这道题bugku上面的链接已经失效了所以没有办法做，我也不好记录。有兴趣可以看看前人的博客，学习学习ht

2020-05-31 21:50:35 803

原创 CTF-入门六

CTF-入门六这篇博客是bugku最后剩下的杂项题，有几道题目我没有解出来的确因为一些原因没有什么时间去啃这些题目，因为下个星期就要开始学习WEB相关的内容了，现在这里做一个记录，但是我还是会尽量去花时间去解题，解出来还是会补充到上面来的。那就继续吧。（1）不简单的压缩包拿到zip文件，010编辑器打开pk头部信息，改成.zip后缀文件要密码，Advanced Archive Password Recovery暴力破解，不行啊。继续看010编辑器内的文件信息有没有提示信息，好像没有，不过好像还有p

2020-05-24 20:01:21 2133

操作系统复习资料以及算法

空空如也