前缀和
有一个半月没有更新了，可能是因为前段时间琐碎的事情比较多，本文介绍一下前缀和，前缀和是处理数组的一种技巧，用一个数组来存储下标从1到i的和，通常情况下这样可以减少时间复杂度，下面通过列举几道题来感受一下这个方法，下面的题目大多来自于Acwing。
Acwing3723 字符串查询给你单词S和Q个询问，每次询问时，你会得到整数A、B、C和D。我们令单词X是由S的第A到B个字母组成，单词Y是由S的第C到D个字母组成。你需要回答，是否能够重新排列单词Y中的字母，得到单词X。
输入格式：第一行输入一个单词S，仅由小写字母组成。第二行输入一个正整数Q。接下来的Q行，每行四个整数A，B，C，D。
输出格式：每次询问，如果能，输出DA，否则输出NE。 1<=|S|<=50000。
题目分析：简单来说，就是看这两个区间内的(a,z)的字符个数是否相同，一个最朴实无华的方法就是把这两个字字符串截下来，然后对其进行排序，最后再挨个比较，当然，不出意外的话会超时。这种情况下的时间复杂度是O((b-a)*log(b-a))，最差情况就是 O(nlog(n)),比这个复杂度小 ...
二叉树的遍历
本文中，我将要介绍一下关于二叉树遍历的先关知识，包括bfs和dfs，以及递归等方法。这些知识和题目在初学时可能有些难度，但通过循序渐进的学习，每天的积累也能done it.我在写这篇文章的时候也发现之前忽略的细节，也收获不少。
遍历二叉树：是按照某条搜索路径巡访树中的每个结点，使得每个结点均被访问一次，而且仅被访问一次。常见的遍历方法有先序遍历，中序遍历和后序遍历。这三种遍历方法通过树的结构用递归可以简单实现，非递归方法可以用栈和队列。下面从层序遍历开始讲起。
Leetcode102二叉树的层序遍历有一个二叉树的根结点root，返回其结点值的层序遍历。即逐层地，从左到右访问所有节点。
eg.输入：root=[3,9,20,null,null,15,7]。输出:[[3],[9,20],[15,7]]
题目分析层序遍历是一种典型的广度优先搜索方法，可以通过队列先进先出的性质来进行层序遍历（当一个节点的左右节点入栈后，将其本身弹出栈），如下图所示:
vector<vector<int>>levelOrder(TreeNode *root)
{
vector& ...
栈
在本文中，我将介绍一下栈的基本用法以及单调栈相关的知识
Leetcode1047.删除字符串中的所有相邻重复项给出由小写字母组成的字符串 s，重复项删除操作会选择两个相邻且相同的字母，并删除它们。在 s 上反复执行重复项删除操作，直到无法继续删除。在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
eg.输入：“abbaca” 输出：“ca”
此题比较明显可以用栈数据结构来解决，对于每个字符依次压入栈，并判断和栈顶的元素是否相等，相等则pop。需要注意的一点是字符串已经内置了栈的操作，vector也是。
string removeDuplicates(string s)
{
string stk;
for(char x:s)
{
if(!stk.empty() &&x==stk.back())
{
stk.pop_back();
}
else
{
stk.push_back(x);
}
}
return stk;
}
leetco ...
链表
在本文中，我将介绍几道链表相关的题目，由浅入深，有些题也比较巧妙，可以学到一些好的思想和解题方法。
Leetcode21 合并两个升序链表将两个升序链表合并成一个新的升序链表并返回。
代码部分ListNode *MergetwoList(ListNode*head1,ListNode*head2)
{
ListNode*dummy=new ListNode(0);
ListNode*p=dummy;
while(head1 && head2)
{
if(head1->val<head2->val)
{
p->next=new ListNode(head1->val);
head1=head1->next;
}
else
{
p->next=new ListNode(head2->val);
head2=head2->next;
}
p=p->next;
}
p->next=head1?head1:head2;
return du ...
排序题目
本文介绍几道排序相关的练习题，这几道题也比较有趣。
错误票据题目描述某涉密单位下发了某种票据，并要在年终全部收回。每张票据有唯一的 ID号。全年所有票据的 ID 号是连续的，但 ID 的开始数码是随机选定的。因为工作人员疏忽，在录入 ID 号的时候发生了一处错误，造成了某个 ID 断号，另外一个 ID 重号。你的任务是通过编程，找出断号的 ID 和重号的 ID 。假设断号不可能发生在最大和最小号。
输入描述：要求程序首先输入一个整数N(N<100)表示后面的行数，接着读入N行数据。每行数据长度不相等，是用空格分开的若干个(不大于100个)正整数(不大于10e5)。
输出描述：要求程序输出1行，含两个整数m，n,用空格分隔，其中，m表示断号ID，n表示重号ID。
题目分析这道题如果能直接得到一个数组，那就很容易就可以解决，不管是排序还是什么。这道题的难点在于怎么读入数据。
介绍一下怎么按行读入，getline()，接收一个字符串，可以接收空格并输出，需要包含”#include< string >”。需要注意的是当同时使用cin>>和getline()时，在c ...
十大排序算法
在本文中，我将介绍10种经典的排序方法，一个很简单的排序，却有很多方法可以解决，每种方法也各有优缺点，每种方法也体现了一种思想，我认为算法中最重要的就是学会一些思想，这样才能做到以不变应万变。本文中的代码均是使用的C/C++(文章中的动图参考 https://github.com/hustcc/JS-Sorting-Algorithm 。若是侵权，我立刻删除)
冒泡排序算法思想
从列表第一个元素开始，比较相邻两个元素值的大小，让小的到前面。
当遍历完一轮后，最大的元素就已经到最后一个了，所以共需遍历n-1次。
动图展示
代码部分#include<iostream>
using namespace std;
void bubblesort(int data [],int n)
{
int temp;
for(int j=0;j<n-1;j++)
{
for(int i=0;i<n-1;i++)
{
if(data[i]>data[i+1])
{
temp=da ...