The Pragmatic Programmer
Programming is a craft. At its simplest, it comes down to getting a computer to do what you want it to do (or what your user wants it to do). As a programmer, you are part listener, part advisor, part interpreter, and part dictator.You try to capture elusive requirements and find a way of expressing them so that a mere machine can do them justice. You try to document your work so that others can understand it, and you try to engineer your work so that others can build on it. What’s more, you...
毕业设计day0
Day 0此为记录毕业设计中代码实现功能记录的系列。 创建项目目前只是创建了项目初始文件和git仓库，由于尚未完成，所以github仓库暂为私有不公开状态。 后端 SpringBoot创建项目截图如下： Maven仓库，java17，jar包，Spring Boot 3.3.5，预装插件为 MySQL Driver，Lombok，Spring Web 前端 Android创建截图如下： java编写， Minimum SDK：API24(Android 7.0),Groovy DSL 构建。 因为感觉好玩，初始选了Android Studio给的Navigation Drawer Views Activity，现在用这种布局的软件比较少，打算做一个和小红书差不多的。
排序
排序在数据结构中，排序（Sorting）指的是将一个数据集合中的元素按指定顺序重新排列的过程。排序是计算机科学的基本操作之一，对数据处理和分析具有重要作用。排序的结果通常是按从小到大（升序）或从大到小（降序）排列的有序序列。 排序的基本概念 内部排序和外部排序： 内部排序：数据量较小，能够将所有待排序的记录一次性加载到内存中完成排序。 外部排序：数据量较大，无法一次加载到内存中，需要借助外存（如硬盘）分批次处理并排序。 稳定性： 稳定排序：若两个相等的元素在排序前后的相对位置不变，则排序算法是稳定的。例如，若记录有相同的键值，稳定排序会保持它们的初始顺序。 不稳定排序：可能会改变相等元素的相对位置。 时间复杂度：排序算法的时间复杂度通常以 $O(n^2)$ 或 $O(n \log n)$...
图
图图（Graph） 是一种用于表示关系的非线性数据结构，由顶点（节点，Vertices/Nodes）和边（Edges）组成，表示顶点之间的关系。图的概念适用于很多场景，比如社交网络（用户和好友关系）、地图（城市和路线）等。 图的基本概念 顶点（Vertex）：图中的基本单位，表示实体或对象。 边（Edge）：连接两个顶点的线，表示它们之间的关系或路径。 有向图（Directed Graph）：边有方向的图，边表示从一个顶点到另一个顶点的单向关系。 无向图（Undirected Graph）：边没有方向的图，边表示顶点之间的双向关系。 加权图（Weighted Graph）：每条边上都有一个权重或费用，用于表示顶点之间的距离或成本。 邻接：如果两个顶点之间有直接边相连，则称它们是邻接的。 路径（Path）：从一个顶点到另一个顶点的一条顶点序列，其中相邻顶点之间都有边相连。 环（Cycle）：从一个顶点出发经过若干边回到该顶点的路径。 连通图（Connected Graph）：在无向图中，任何两个顶点之间都可以找到路径的图。 图的存储 邻接矩阵（Adjacency...
并查集
并查集并查集（Disjoint Set Union, DSU）是一种数据结构，用于处理不相交集合（disjoint sets）的合并（union）和查询（find）操作。并查集特别适用于动态连通性问题，例如判断两个元素是否在同一个集合中或合并两个集合。广泛应用在图论算法中，比如 Kruskal 最小生成树算法。 并查集的概念并查集主要支持两个操作： 查找（Find）：确定元素所属的集合。通常返回集合的“代表元素”。 合并（Union）：将两个集合合并成一个集合。 并查集使用树结构来表示集合，每个集合中的元素都指向一个根节点，根节点代表该集合。为优化效率，通常使用以下两种技术： 路径压缩（Path Compression）：在查找操作中，将树的高度降低，使得查找的时间复杂度接近常数。 按秩合并（Union by Rank）：在合并操作中，将较小的树合并到较大的树上，避免树变得过于深。 并查集的性质 时间复杂度：使用路径压缩和按秩合并的并查集可以将单次操作的平均时间复杂度优化到几乎为常数，接近 $O(\alpha(n))$ ，其中 $(\alpha)$...
树
树在数据结构中，树（Tree）是一种分层的非线性数据结构，它由节点（node）和边（edge）组成，并且具有以下性质： 树的概念 节点和边：树包含一组节点，通过边连接，节点之间呈现出层级关系。 根节点：树的起始节点称为根节点（root），通常位于树的顶端。 父节点和子节点：每个节点可以连接其他节点，称为子节点（children）；连接它们的节点称为父节点（parent）。 叶子节点：没有子节点的节点称为叶子节点（leaf）。 层级：树的每一层从根节点开始，按层级关系排列。 路径：节点之间的路径由节点和边组成，从根节点到某个特定节点的路径是节点之间的唯一路径。 树的性质 唯一根节点：树中只有一个根节点，没有父节点。 节点数量关系：有 ( n ) 个节点的树，边的数量为 ( n - 1...
哈希表
哈希表（Hash Table）是一种用于存储键值对的数据结构，可以通过哈希函数快速地根据键找到对应的值。哈希表的查找、插入和删除操作在平均情况下具有 O(1) 的时间复杂度，非常高效。 1. 哈希表的基本概念哈希表的核心思想是将键通过一个哈希函数（Hash Function）映射到一个哈希表的索引位置上。若两个键映射到同一位置（即出现哈希冲突），则需要解决冲突以保证数据存储的正确性。 哈希表的术语 哈希函数：将键映射到表中某个位置的函数。 哈希冲突：两个不同的键被映射到同一个位置。 装载因子：表中已填充元素的数量与哈希表大小的比值。较高的装载因子会增加冲突发生的可能性。 2. 哈希表的实现方式哈希表的常用实现方式主要有两种： 开放寻址法：在发生冲突时，通过寻找其他空闲位置来存储元素。常见的开放寻址方法包括线性探测、二次探测和双重哈希。 链地址法（拉链法）：在每个哈希表位置存储一个链表，在发生冲突时将新元素插入到链表中。 3. 哈希表的 C++ 实现使用链地址法（拉链法）的 C++...
栈与队列
1. 栈的基本概念与操作栈（Stack）是一种后进先出（LIFO, Last In First Out）的数据结构，最后插入的元素最先被删除。 栈的基本操作 初始化：创建一个空栈。 入栈（Push）：将一个元素压入栈顶。 出栈（Pop）：从栈顶删除一个元素。 取栈顶元素（Top）：获取栈顶元素的值，但不删除它。 判断是否为空：检查栈是否为空。 2. 队列的基本概念与操作队列（Queue）是一种先进先出（FIFO, First In First Out）的数据结构，最先插入的元素最先被删除。 队列的基本操作 初始化：创建一个空队列。 入队（Enqueue）：将一个元素加入到队尾。 出队（Dequeue）：从队头删除一个元素。 取队头元素（Front）：获取队头元素的值，但不删除它。 判断是否为空：检查队列是否为空。 3. 栈的顺序存储结构栈的顺序存储结构通常使用数组实现，栈顶指针 top 用于指向栈顶元素。 栈的顺序存储结构的 C++...
线性表
线性表线性表是一种数据结构，表示由同一类型的元素按顺序排列的有限集合。线性表中的元素有顺序关系，可以通过顺序号访问。它是最常用的结构之一，常用于实现数据的顺序存储和查找操作。 线性表的定义一个线性表 $( L )$ 可以定义为一个具有相同类型的元素集合，其中第一个元素为 $( a_1 )$，第二个元素为 $( a_2 )$，依次排列，直到第 $( n )$ 个元素 $( a_n )$。线性表的长度是元素的个数，当长度为 0 时，称其为空表。 在数学上可以表示为：$[ L = { a_1, a_2, \dots, a_n }...
CCSP2024 赛后回忆
CCSP2024 赛后回忆这次是在浙江金华的浙江师范大学，虽然说这里可能有一点点偏僻，但是店铺什么的基本都有，奶茶店，肯德基什么的甚至开在了校内。 这应该是我大学最后一次参加国家级的赛事了吧。 题目I/O 任务调度队列按来的时间排个序，奇数放第一个队列，偶数放第二个队列，保证每个任务等待的时间最小就可以了，签到题。 12345678910111213141516171819202122232425262728293031323334353637#include<bits/stdc++.h>using namespace std;const int mxlen = 1e3+5;int t[mxlen];int n;int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int T = 1; while(T--){ cin>>n; for(int i=1;i<=n;i++){ ...
HDU 4870 概率DP
HDU 4870 概率DPProblem Link 题意新账号打rank，rank从0开始，打到1000分结束。每场rank增加50的概率为p，否则rank-100。新人用两个信号去打，每次用rank值低的账号，问任意一个账号达到rank1000分，新人要打的期望场数。 解答参考博客 将分数离散为赢了加1分，输了减2分。用dp[i]表示从i-1分到i分需要打的期望场数。 每次比赛有两种情况，一是p概率赢了加1分，二是(1-p)概率输了减2分。 dp[i]=1*p+(1-p)(1+dp[i-2]+dp[i-1]+dp[i]) 期望等于所有情况乘以概率的和。 一场就赢了，则是1*p 一场输了，则需要(1+dp[i-2]+dp[i-1]+dp[i])场才能赢回来。其中1是输了这场，然后从i-3打到i-2,从i-2打到i-1，从i-1打到i分。 化简得 dp[i]=(1+(1-p)*(dp[i-2]+dp[i-1]))/p dp[1] = 1/p, dp[2] =...
HDU 1024 M子段和最大
M子段和最大问题Problem Link Given an array and divide into m sequences. One sequences at least has one number and the sequences can’t contain the number with same index. And the index of the numbers in one sequence should be continuous. Notice that we don’t have to use all the numbers. N between 1 to 1e6. SOLUTIONDynamic programming. Let d[i][j] denote the maximum sum of the current array that is divided into i segments and the last segment ends with the jth number. When comes to the jth number,...
HDU 1029 寻找数列主元素
寻找数列主元素Problem link Finding a integer that appears at least (N+1)/2 times in the array. 摩尔投票法The Boyer-Moore Voting Algorithm (Moore’s Voting Algorithm) is a highly efficient method to find the majority element in a sequence (an element that appears more than half the time). It operates in O(n) time and uses O(1) space. Key Idea:The algorithm works by maintaining a candidate for the majority element and a counter to track its occurrences. It leverages a “pairing” or “cancellation” mechanism...
HDU 1465 (错位排列问题)
Derangement Problemproblem link Problem DescriptionYou have n letters, each with a different recipient. However, all the letters are delivered to the wrong recipients, meaning no one receives the letter intended for them. You need to determine how many possible ways this can happen. This problem can be simplified to a case where you have an array of numbers from 1 to n. For each position in the array(starting from index 1), the number in that position is different from its index. The goal is...
Notes of Lecture 23: Computational Complexity
Notes of Lecture 23: Computational Complexityvideo link P,EXP,RP = {problems solvable in at most(<=) polynomial time} EXP = {problems solvable in exponential(2^$n^c$) time} R = {problems solvable in finite time} The axis is computational difficulty. Most problems uncomputableExamples: negative-weight cycle detection (P) NxN Chess (EXP&!P) Tetris (EXP, don’t know whether is P) halting problem: given program, does it ever halt/stop? (not in R) Most decision problems are uncomputable...
HDU 1085 multiple knapsack problem
Multiple Knapsack Problemproblem link The Meaning of the problemYou have three kinds of coins. Their face values are 1,2 and 5. Of cause you only have a limited number of coins. You need to find the minimum value that you can’t represent exactly with these coins. SolutionThere are lots of people solve this problem using Generating function. That way is too hard to understand. We just need to think of this problem as a multiple knapsack problem. I learned from this blog dp[j] = 1 means that...
HDU 1025 longest increasing subsequence
Constructing Roads In JGShining’s Kingdomproblem link The meaning of the problemSo why this is longest increasing subsequence Problem ? Look at the picture below: As the problem described, we can’t have crossed lines. Each line has two endpoints. One is the “rich” endpoint above and the other is the “poor” endpoint below. The rich endpoints’ number of the lines we finally pick up should be monotonically increasing. The corresponding poor endpoints should be monotonically increasing too....
HDU 1023 Train Problem II 高精度卡特兰数
High-precision Catalan numberproblem link This is a classic problem of finding the number of stack push ans pop sequences. The only headache is that it requires high precision. How to determine whether it is a Catalan numberFor a more detailed introduction to the Catalan number,see oi-wiki and wikipedia I think there is another simple way to judge, which is to see whether the first few numbers are consistent with the Catalan number. If they are the same, then it is likely to be a correct...
HDOJ 1010 Tempter of the Bone 深搜&剪枝
细心和智慧并存的解答题目链接 题的大致意思是能不能从起点经过T时间精准到达终点，图中有一些障碍不能走，走过的格子也不能再走。 其中数据是最大7*7的迷宫，最多50个迷宫。 智慧之处——精准的剪枝类似全排列的深搜时间复杂度是O(n!)，7*7的数据是过不去的。 首先就是普通地剪枝： 如果时间已经大于T，就不用再走了 如果已经有正确答案，要及时地退出搜索 然后是奇偶剪枝，这里参考了其他博客 这里我重新画了一张图，如下： 图中的S可以代表任何你走到的位置，不一定是起点。就如图中的红色和蓝色路径，这两条路径是最少需要的时间。如果剩余时间少于最短路径长度，那么是一定不能到达终点的。 既然时间不够一定不能到达，时间刚好和剩余最少时间相等也能到达，那么还剩一种情况，就是时间大于剩余最少时间。这也应该是大概率会遇到的情况。根据题意我们只能在第T秒精准到达终点，我们时间多出来的怎么办呢？——我们需要在终点周围“徘徊”。 如图中的绿色和黄色箭头所示，你比最短路径多走出来的路径，一定是先“出去”，再“回来”。多走的路径是“对称的”，那多出来的路径长度一定是偶数。 ...