刷题过程中学了很多算法，但是都没有做个笔记==，写一下稍微留个印象~1.曼彻斯特算法首先用一个非常巧妙的方式，将所有可能的奇数/偶数长度的回文子串都转换成了奇数长度：在每个字符的两边都插入一个特殊的符号。比如 abba 变成 #a#b#b#a#， aba变成 #a#b#a#。 为了进一步减少编码的复杂度，可以在字符串的开始加入另一个特殊字符，这样就不用特殊处理越界问题，比如$#a#b#a#（注意，下面的代码是用C语言写 就，由于C语言规范还要...
一些常见的基础算法(未完待续)快速排序int partition(int left,int right,int arr[]) {int i = left;int j = right;int value = arr[left];while (j > i){//从右边j开始找到一个比value小的值while (j > i && arr[j] >= value)j--;if (j > i){arr[i] = arr[j];i++;}//从左边i开始找到一个比value大的值while (j > i && arr[i] i){arr[j] = arr[i];j--;}}//i=j时代表所有比value大的值都到了右边，比value小的到了左边arr[i] = val...
本人第一篇博客，刚学算法半年的蒟蒻，用于进一步学习交流。 分~界~线~~~ 进制转换 题目描述： 将一个长度最多为30位数字的十进制非负整数转换为二进制数输出。 输入： 多组数据，每行为一个长度不超过30位的十进制非负整数。（注意是10进制数字的个数可能有30个，而非30bits的整数） 输出： 每行输出对应的二进制数。 样例输入：985 211 1126样例输出：1111011001 11010011 10001100110 注：每段代码变量不一致，以最后Code为标...
4.3 递归 4.3.1 分治(divide and conquer): 分治法将原问题划分成若干个规模较小而结构与原问题相似的子问题，然后分别解决这些子问题，最后合并子问题的解，即可得到原问题的解。 分治大体上有三步走：分解、解决、合并（这个方法貌似我一直都有在用，只不过用在了不对的地方，把简单的问题复杂化了，不能怪分治，怪就怪我的变成思想有问题） 4.3.2 递归：“要理解递归，你要先理解递归，直到你能理解递归”——一个笑话。 总之，...
提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档 目录 前言 一、串的结构 二、基本操作 三、串的匹配算法 1.朴素模式匹配算法 2.RabinKarp(滚动哈希) 3.KMP算法 4.字典树（前缀树） 5.后缀数组 6.后缀自动机 四、字符串的经典问题 总结 前言 串即字符串，由零个或多个字符组成的有限序列，属于线性表，以下为有关串的结构、基本操作实现和串的匹配算法。一、串的结构 顺序存储： typedef struct{char ch[M...
语法 char str[25] = "hello"; //字符数组 printf("%s", str); #define pi 3.24 const double pi=3.24; //设置常量 const int INF=0x3fffffff; //无穷大常用2^30-1 printf("%5d\n",a);//使a占5位，高位用空格补齐（超过5位则不变），%05d 高位0补齐 ，%.1f 保留一位小数 struct node{node n; //错误表述，不可定义自身node* next; //正确，可定义自身类型的指针 }; 结构体的优先级设置 struct fruit{string name;int price;f...
问题 F: 例题5-6 矩阵输出 题目描述输入输出样例输入样例输出示例代码题目描述 输出以下4*5的矩阵 1 2 3 4 5 2 4 6 8 10 3 6 9 12 15 4 8 12 16 20 要求使用循环实现，注意每行输出5个数字，每个数字占3个字符的宽度，右对齐。 输入 无 输出 每行输出5个数字，每个数字占3个字符的宽度，右对齐。 样例输入 无 样例输出示例代码 #include<iostream> using namespace std; int main(){int i,n,sum=0;for(i=1;i<=4;i++){for(n=i;n<=i+...
1.实现数组拷贝 private static int[] copyArray(int[] a){if(a == null || a.length == 0 ){return null;}int[] b = new int[a.length];for(int i = 0;i<a.length;i++){b[i] = a[i];}System.out.println(JSONObject.toJSONString(b));return b;} 2.转换首尾顺序 private static int[] transferHeadToTail(int[] b){if(b == null || b.length == 0){return null;}int k = b.length/2;int[] t = new int[b.length...
前言： 欢迎光临大千小熊的博客，我是一只又会MMD又会C++的正派熊，B站和CSDN同步更新，欢迎关注。 幂运算含义： 形如xnx^nxn 指数是x，底数是x的一个幂。（nnn是变量） 例如24=16，22=42^4=16，2^2=424=16，22=4这样的运算。 计算幂运算的方法： 例如，我们想去计算242^424。我们可以循环4次，另res=1，然后res*=4。 但是这样的算法是不高效率的。 这是因为，我们想计算2?2?2?22*2*2*22?2?2?2的时候，人类一般都会用2?2=42*2=42?2...
4.1小节：排序（对应编号581） A题 排序 #include <stdio.h> #include <stdlib.h>int main() {int temp,k,j,i,n,a[100];while(scanf("%d",&n)!=EOF){for(i=0;i<n;i++) scanf("%d",&a[i]);for(i=0;i<n;i++){k=i;for(j=i+1;j<n;j++){if(a[j]<a[k]) k=j;}temp=a[i];a[i]=a[k];a[k]=temp;}for(i=0;i<n;i++) printf("%d ",a[i]);printf("\n");}return 0; }总结：输入多组数据用while控制，本题选用的排序算法是选择排序。
组合问题： 给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合。问题分析： 经典的纯组合问题，可判断为回溯问题，所有回溯问题都可以抽象为树结构，是在一棵树上的深度优先遍历，那么在这里我们先画出一个简单的树结构，再进一分析问题。 然后进行我们回溯的三个步骤：回溯函数的终止条件 从图中可以看出，回溯的终止条件也就是达到了树的根节点。 在这道题目中，当我们从集合中选取到两元素时就到达了叶子节点，也就...
对于学习算法或者做一些查找题喜欢从头做遍历，这种算法的时间复杂度为O(N),这是一个普适性的算法，几乎所有的查找都可以用它，而且时间复杂不高在我们能够接受的范围之内。但我下面介绍的是另外一个特殊的算法，它不具备普适性，它只适合查找那些已经排好序的元素并且查找的数据元素量很庞大，这种情况下用二分查找将在时间效率方面体现巨大优势，因为它的时间复杂度为O(logN)，而且很多学校程序语言期末考试大题都会考到，所以建...
散列（hash）是常用算法之一。简单来说，散列就是将一个元素通过一个函数转换为整数，使得该整数可以尽量唯一的代表这个元素。将这个函数成为散列函数H，元素转换前为key，转换后为H（key）。 key为整数时，常用的散列函数有直接定址法、平方取中法、除留余数法等。 直接定址法有恒等变换H(key)=key和线性变换H(key)=a*key+b; 平方取中法是指取key平方中间若干位作为hash值，很少使用。 除留余数法是H(key)=key%mod,表长TSize必须不...
前置芝士 欧几里得算法 又称辗转相除法，举例如gcd求法，基本递归函数为\(f(a,b)=f(b,a\mod b)\)； 证明：a可以表示成\(a = kb + r\)（a,b,k,r皆为正整数，且\(r<b\)），则\(r = a \mod b\)。假设d是a,b的一个公约数，记作\(d|a\),\(d|b\)，即a和b都可以被d整除。而r = \(a - kb\)，两边同时除以d，\(r/d=a/d-kb/d=m\)，由等式右边可知m为整数，因此\(d|r\)因此d也是\(b,a \mod b\)的公约数。因\((a,b)\)和\((b,a\mod b)\)的公约数...
JS算法笔记—二分查找//二分查找是一种基于比较目标值和数组中间元素的教科书式算法。 //如果目标值等于中间元素，则找到目标值。 //如果目标值较小，继续在左侧搜索。 //如果目标值较大，则继续在右侧搜索。 //时间复杂度：O(logN)。 空间复杂度：O(1)。//二分查找var search = function(nums, target) {let left = 0; // 初始左边界let right = nums.length - 1; // 初始右边界// 如果left > right 证明整个数组结束了仍没有找到...