goMars的学习随记

差分差分和前缀和是密不可分的，如有一个数组a，就会对应有一个差分数组b。差分数组b的特性是： a[i]=b1+b2+b3+…+bi,即为将数组a看做b的前缀和数组,a与b互为逆运算. 一维差分简单分析一维差分就是由一维数组组成的差分，主要运用差分数组的特性将求原数组a(b的前缀和数组)的某子区间进行加减操作从O(n)转化为O(1). 如：输入一个长度为 n 的整数序列。接下来输入 m 个操作，每个操作包含三个整数 l,r,c，表示将序列中 [l,r]之间的每个数加上 c。请你输出进行完所有操作后的序列。 代码12345678910111213141516171819202122232425262728#include<iostream>#include<stdio.h>using namespace std;#define N 100010int a[N],b[N];void insert(int l,int r,int num){ b[l] += num; //将第l个加上num因为a为b的前缀和所以l之后所有a[i]都会加上num b[ ...

前缀和一维前缀和简单分析一维前缀和：该位之前所有数之和，需要拿一个数组来存，前缀和的目的就是为了方便之后需要求数组中某一段的和不再需要重新遍历，只需要利用前缀和进行操作。 如：输入一个长度为 n 的整数序列。接下来再输入 m 个询问，每个询问输入一对 l,r。对于每个询问，输出原序列中从第 l个数到第 r个数的和。 代码123456789101112131415161718#include <iostream>#include <stdio.h>using namespace std;#define N 100010int a[N],s[N]; //将比较大的数组定义为全局变量int main() { int n,m,l,r; scanf("%d%d",&n,&m); for (int i = 1; i <= n; ++i) scanf("%d",&a[i]); //录入数组 for (int i = 1; i <= n; ++i) s[i] = s[ ...

高精度大整数计算两个高精度大整数相加简单分析​ 由于两个都是大整数，需要用数组或容器来存。具体运算就跟手算一样，各位相加留下10的余数多于10的进位，从个位开始一直重复到最高位即可，最后需要注意进位是否还多出一位来。 代码12345678910111213141516171819202122232425262728293031// c++代码#include<iostream>#include<stdio.h>#include<string>#include<vector>using namespace std;vector<int> add(vector<int> &A,vector<int> &B){ vector<int> c; //用于存和 int t = 0; //进位 for(int i = 0;i < A.size() || i < B.size();i++){ //遍历从个位开始到最高位 ...

插值查找分析相当于对二分查找的一种优化，让mid指针更加精确 代码1234567891011121314151617181920212223242526272829303132package 算法;public class 插值查找 { public static void main(String[] args) { int[] arr = new int[100]; for (int i = 0; i <100 ; i++) { arr[i] = i+1; } int index = insertValueSearch(arr, 0, arr.length-1, 99999); System.out.println(index); } public static int insertValueSearch(int[] arr,int left,int right,int num){ if(num& ...

二分查找分析 首先必须是有序数组 先定义一个中心指针 循环看查找的数是否和中心点相等 若比中心点小肯定在它左边就继续对比左边，反之对比右边 如果左边界大于右边界了就退出循环 代码123456789101112131415161718192021222324252627package 算法;import java.util.Arrays;public class 二分查找 { public static void main(String[] args) { int[] arr = {3, 14, 53, 214, 542, 748}; System.out.println(binaryFind(arr, 111)); } public static int binaryFind(int[] arr, int num) { int l = 0, r = arr.length-1; int mid = (l + r) / 2; whi ...

归并排序分析 代码123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354package 算法;import java.util.Arrays;public class 归并排序 { public static void main(String[] args) { int[] nums = new int[]{6,2,1,5,3,4,9,8}; int[] temp = new int[nums.length]; sort(nums, 0,nums.length-1, temp); System.out.println(Arrays.toString(nums)); } private static void sort(int[] arr,int left,int right,int[] temp){ ...

希尔排序分析 先将数组分为length/2组，然后依次/2分组 每组进行插入排序 最后再进行总的插入排序 代码1234567891011121314151617181920212223242526272829package 算法;public class 希尔排序 { public static void main(String[] args) { int[] arr = new int[]{8,9,1,7,2,3,5,4,6,0}; shellSort(arr); for (int i : arr) { System.out.println(i); } } private static void shellSort(int[] arr){ int len = arr.length; //循环进行分组，i表示分组数 for (int i = len/2; i > ...

基数排序分析基数排序(Radix Sort)是桶排序的扩展，它的基本思想是：将整数按位数切割成不同的数字，然后按每个位数分别比较。具体做法是：将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。 代码123456789101112131415161718192021222324252627282930313233343536373839404142434445package 算法;import java.util.Arrays;public class 基数排序 { public static void main(String[] args) { int[] arr = {53,3,542,748,1114,214,1}; radixSort(arr); System.out.println(Arrays.toString(arr)); } public stat ...

快速排序分析1．先从数列中取出一个数作为基准数。 2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。 3．再对左右区间重复第二步，直到各区间只有一个数。 代码 双向划分(最基础版) 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849package 算法;public class 快速排序 { public static void main(String[] args) { int[] arr = new int[]{-9,78,0,23,-567,70}; quickSort(arr, 0, arr.length-1); for (int i : arr) { System.out.println(i); } } public static void quick ...

插入排序分析 遍历 len-1 次 每次将第i个插入数组，并判断与当前最前面的数的大小。 ​ 代码123456789101112131415161718192021package 算法;public class 插入排序 { public static void main(String[] args) { int[] arr = new int[]{101,34,119,1}; for(int i = 1;i<arr.length;i++){ int index = i; int num = arr[i]; for (int j = i-1; j >= 0 ; j--) { if(num<arr[j]){ arr[index] = arr[j]; index = j; ...