wuxiawei / data-structures-and-algorithms Goto Github PK
View Code? Open in Web Editor NEW记录一些数据结构笔记和代码
记录一些数据结构笔记和代码
class ArrayQueue {
private int maxSize; // 表示数组的最大容量
private int front; // 队列头
private int rear; // 队列尾
private int[] arr; // 该数据用于存放数据, 模拟队列
// 创建队列的构造器
public ArrayQueue(int arrMaxSize) {
maxSize = arrMaxSize;
arr = new int[maxSize];
front = -1; // 指向队列头部,分析出 front 是指向队列头的前一个位置.
rear = -1; // 指向队列尾,指向队列尾的数据(即就是队列最后一个数据)
}
// 判断队列是否满
public boolean isFull() {
return rear == maxSize - 1;
}
// 判断队列是否空
public boolean isEmpty() {
return rear == front;
}
// 添加数据到队列
public void addQueue(int n) {
if (isFull()) {
System.out.println("队列满,不能加入数据~");
return;
}
rear++; // 让 rear 后移
arr[rear] = n;
}
// 获取队列的数据, 出队列
public int getQueue() {
if (isEmpty()) {
throw new RuntimeException("队列空,不能取数据");
}
front++; // front 后移
return arr[front];
}
// 显示队列的所有数据
public void showQueue() {
// 遍历
if (isEmpty()) {
System.out.println("队列空的,没有数据~~");
return;
}
for (int i = 0; i < arr.length; i++) {
System.out.printf("arr[%d]=%d\n", i, arr[i]);
}
}
// 显示队列的头数据, 注意不是取出数据
public int headQueue() {
if (isEmpty()) {
throw new RuntimeException("队列空的,没有数据~~");
}
return arr[front + 1];
}
}
将链表倒序再打印会破坏原有链表结构,不合适;
采用stack,遍历链表入栈,再按顺序出栈打印。
public void printReverse(){
HeroNode temp = head.next;
Stack<HeroNode> stack = new Stack<HeroNode>();
if(temp == null){
System.out.println("空链表");
return;
}
while (temp != null){
stack.add(temp);
temp = temp.next;
}
while (stack.size() > 0){
HeroNode node = stack.pop();
System.out.println(node);
}
}
双向链表:具有next和front节点,可以向前或者向后进行查找
单向链表不能自我删除,需要靠辅助节点 ,而双向链表则可以自我删除
public void addNode(HeroNode heroNode){
if(head.next == null) head.next = heroNode;
HeroNode temp = head.next;
while (true){
if(temp.next == null) break;
temp = temp.next;
}
temp.next = heroNode;
heroNode.front = temp;
}
public void deleteNode(int num){
if(head.next == null){
System.out.println("空链表");
return;
}
HeroNode temp = head.next;
while (true){
if(temp.no == num) break;
temp = temp.next;
}
temp.next.front = temp.front;
temp.front.next = temp.next;
}
节点类:
class HeroNode{
public int no;
public String name;
public String nickname;
public HeroNode next;
public HeroNode front;
public HeroNode(int no, String name, String nickname){
this.no = no;
this.name = name;
this.nickname = nickname;
}
@Override
public String toString(){
return "HeroNode [no=" + no + ", name=" + name + ", nickname=" + nickname + "]";
}
}
打开EXCEL,按alt+f11,左侧双击sheet1,将代码复制粘贴过去,按F5运行即可。
注:要从最高位的前一位最大值开始,例如有150个文件,则从99开始
Sub aFileNameA()
Dim Fso, Fldr, s
Set Fso = CreateObject("Scripting.FileSystemObject")
Set Fldr = Fso.GetFolder("C:\Users\12965\Desktop\案卷") '假设xls文件在xxxx文件夹
Application.ScreenUpdating = False
Application.DisplayAlerts = False
For Each s In Fldr.Files
If s.Name Like "*.xls" Then
Workbooks.Open s
With ActiveWorkbook
With ActiveWorkbook
.ActiveSheet.Rows("1:2").Delete '删除1至2行 数字在这修改
.Close SaveChanges:=True
End With
End With
End If
Next s
Application.DisplayAlerts = True
Application.ScreenUpdating = True
Set Fso = Nothing
End Sub
编辑距离(Edit Distance):又称Levenshtein距离,是指两个字串之间,由一个转成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符,插入一个字符,删除一个字符。一般来说,编辑距离越小,两个串的相似度越大。其中,字符编辑操作包括:① 删除一个字符 ② 插入一个字符 ③ 修改一个字符。
问题分析:
1)假设存在两个字符串A和B,他们的长度分别是lenA和lenB。首先考虑第一个字符,由于他们是一样的,所以只需要计算A[2...lenA]和B[2...lenB]之间的距离即可。那么如果两个字符串的第一个字符不一样怎么办?可以考虑把第一个字符变成一样的(这里假设从A串变成B串):
①修改A串的第一个字符成B串的第一个字符,之后仅需要计算A[2...lenA]和B[2...lenB]的距离即可;
②删除A串的第一个字符,之后仅需要计算A[2...lenA]和B[1...lenB]的距离即可;
③把B串的第一个字符插入到A串的第一个字符之前,之后仅需要计算A[1...lenA]和B[2...lenB]的距离即可。
2)接下来考虑A串的第i个字符和B串的第j个字符。
我们这个时候不考虑A的前i-1字符和B串的第j-1个字符。如果A串的第i个字符和B串的第j个字符相等,即A[i]=B[j],则只需要计算A[i...lenA]和B[j...lenB]之间的距离即可。如果不想等,则:
①修改A串的第i个字符成B串的第j个字符,之后仅需要计算A[i+1...lenA]和B[j+1...lenB]的距离即可;
②删除A串的第i个字符,之后仅需要计算A[i+1...lenA]和B[j...lenB]的距离即可;
③把B串的第j个字符插入到A串的第i个字符之前,之后仅需要计算A[i...lenA]和B[j+1...lenB]的距离即可。
写到这里,自然会想到用递归求解或者动态规划求解,由于用递归会产生很多重复解,所以用动态规划。
建立动态规划方程:
算法分析:
也就是说,就是将一个字符串变成另外一个字符串所用的最少操作数,每次只能增加、删除或者替换一个字符。
首先我们令word1和word2分别为:michaelab和michaelxy(为了理解简单,我们假设word1和word2字符长度是一样的),dis[i][j]作为word1和word2之间的Edit Distance,我们要做的就是求出michaelx到michaely的最小steps。
首先解释下dis[i][j]:它是指word1[i]和word2[j]的Edit Distance。dis[0][0]表示word1和word2都为空的时候,此时他们的Edit Distance为0。很明显可以得出的,dis[0][j]就是word1为空,word2长度为j的情况,此时他们的Edit Distance为j,也就是从空,添加j个字符转换成word2的最小Edit Distance为j;同理dis[i][0]就是,word1长度为i,word2为空时,word1需要删除i个字符才能转换成空,所以转换成word2的最小Edit Distance为i。下面及时初始化代码:
for (int i = 0; i < row; i++) dis[i][0] = i;
for (int j = 0; j < col; j++) dis[0][j] = j;
下面来分析下题目规定的三个操作:添加,删除,替换。
假设word1[i]和word2[j](此处i = j)分别为:michaelab和michaelxy
如果b==y,
那么:dis[i][j] = dis[i-1][j-1]。
如果b!=y,
那么:
添加:也就是在michaelab后面添加一个y,那么word1就变成了michaelaby,此时 dis[i][j] = 1 + dis[i][j-1];
上式中,1代表刚刚的添加操作,添加操作后,word1变成michaelaby,word2为michaelxy。
dis[i][j-1]代表从word1[i]转换成word2[j-1]的最小Edit Distance,也就是michaelab转换成michaelx的最小
Edit Distance,由于两个字符串尾部的y==y,所以只需要将michaelab变成michaelx就可以了,而他们之间的最
小Edit Distance就是dis[i][j-1]。
删除:也就是将michaelab后面的b删除,那么word1就变成了michaela,此时dis[i][j] = 1 + dis[i-1][j];
上式中,1代表刚刚的删除操作,删除操作后,word1变成michaela,word2为michaelxy。dis[i-1][j]代表从
word[i-1]转换成word[j]的最小Edit Distance,也就是michaela转换成michaelxy的最小Edit Distance,所以
只需要将michaela变成michaelxy就可以了,而他们之间的最小Edit Distance就是dis[i-1][j]。
替换:也就是将michaelab后面的b替换成y,那么word1就变成了michaelay,此时dis[i][j] = 1 + dis[i-1][j-1];
上式中,1代表刚刚的替换操作,替换操作后,word1变成michaelay,word2为michaelxy。dis[i-1][j-1]代表从
word[i-1]转换成word[j-1]的最小Edit Distance,也即是michaelay转换成michaelxy的最小Edit Distance,由
于两个字符串尾部的y==y,所以只需要将michaela变成michaelx就可以了,而他们之间的最小Edit Distance就是
dis[i-1][j-1]。
代码:
import java.util.*;
class EditDistance {
public static int EditDistance(String s, String t) {
/**
dis[0][0]表示word1和word2都为空的时候,此时他们的Edit Distance为0。
dis[0][j]就是word1为空,word2长度为j的情况,此时他们的Edit Distance为j,也就是从空添加j个字符转换成word2的最小Edit Distance为j;
dis[i][0]就是,word1长度为i,word2为空时,word1需要删除i个字符才能转换成空,所以转换成word2的最小Edit Distance为i
**/
int dp[][] = new int[s.length() + 1][t.length() + 1];//建好dp的二维数组,用于保存各种情况的Edit Distance
char sChar[] = new char[s.length()];
char tChar[] = new char[t.length()];
//将String转化成Char数组
for(int i = 0; i < s.length(); i++) sChar[i] = s.charAt(i);
for(int i = 0; i < t.length(); i++) tChar[i] = t.charAt(i);
//初始化dp(i = 0 和 j = 0 时的情况)
for(int i = 0; i <= s.length(); i++) dp[i][0] = i;
for(int j = 0; j <= t.length(); j++) dp[0][j] = j;
//动态规划方程
for(int i = 1; i <= s.length(); i++){
for(int j = 1; j <= t.length(); j++){
int flag;
if(sChar[i - 1] == tChar[j - 1])
flag = 0;
else
flag = 1;
//dp[i-1][j]+1表示删掉字符串a最后一个字符a[i]
//dp[i][j-1]+1表示给字符串添加b最后一个字符
//dp[i-1][j-1]+flag表示改变,相同则不需操作次数,不同则需要,用flag记录
dp[i][j]=Math.min(dp[i-1][j]+1,Math.min(dp[i][j-1]+1,dp[i-1][j-1]+flag));
}
}
return dp[s.length()][t.length()];
}
public static void main(String args[]) {
Scanner scan = new Scanner(System.in);
String s = scan.next();
String t = scan.next();
System.out.println(EditDistance(s, t));
}
}
稀疏数组:当一个数组中大部分元素为0,或者为同一个值的数组时,可以使用稀疏数组来保存该数组。
public class SparseArray {
public static void main(String[] args) {
//初始化新数组
int chessArr1[][] = new int[11][11];
chessArr1[1][2] = 1;
chessArr1[2][3] = 2;
//打印
for(int[] row: chessArr1){
for (int data: row){
System.out.printf("%d\t",data);
}
System.out.println();
}
//统计有多少个非0元素
int sum = 0;
for(int i = 0; i < chessArr1.length; i++){
for(int j = 0; j < chessArr1[0].length; j++){
if(chessArr1[i][j] != 0) sum++;
}
}
//创建稀疏数组,原数组转化成稀疏数组
int chessArr2[][] = new int [sum + 1][3];
chessArr2[0][0] = 11;
chessArr2[0][1] = 11;
chessArr2[0][2] = sum;
int count =0;
for(int i = 0; i < 11; i++){
for (int j = 0; j < 11; j++){
if(chessArr1[i][j] != 0){
count++;
chessArr2[count][0] = i;
chessArr2[count][1] = j;
chessArr2[count][2] = chessArr1[i][j];
}
}
}
//打印稀疏数组
System.out.println("稀疏数组:");
for(int[] row: chessArr2){
for (int data: row){
System.out.printf("%d\t", data);
}
System.out.println();
}
}
}
class CircleArrayQueue{
private int maxSize; // 表示数组的最大容量
private int front; // 队列头
private int rear; // 队列尾
private int[] arr; // 该数据用于存放数据, 模拟队列
public CircleArrayQueue(int len){
maxSize = len;
front = 0;
rear = 0;
arr = new int[maxSize];
}
//判断队列是否为满
public boolean isFull(){
if((rear + 1) % maxSize == front) return true;
return false;
}
//判断队列是否为空
public boolean isEmpty(){
if(rear == front) return true;
return false;
}
//数据个数
public int size(){
return (rear + maxSize - front) % front;
}
//加入数据
public void addQueueData(int data){
// 判断队列是否满
if (isFull()) {
System.out.println("队列满,不能加入数据~");
return;
}
arr[rear] = data;
rear = (rear + 1) % maxSize;
}
//取出数据
public int getQueueData(){
// 判断队列是否空
if (isEmpty()) {
throw new RuntimeException("队列为空,没有数据");
}
int value = arr[front];
front = (front + 1) % maxSize;
return value;
}
//显示所有数据
public void viewQueueData() {
// 判断队列是否空
if (isEmpty()) {
throw new RuntimeException("队列为空,没有数据");
}
for (int i = front; i < front + size(); i++) {
System.out.printf("arr[%d]=%d\n", i % maxSize, arr[i % maxSize]);
}
}
// 显示队列的头数据, 注意不是取出数据
public int headQueue() {
// 判断
if (isEmpty()) {
throw new RuntimeException("队列空的,没有数据~~");
}
return arr[front];
}
}
求出第n个斐波那契数的值(非常大)与 m 的余数(模),为了节约时间和避免内存溢出,通过Pisano period进行求解
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Pisano {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
final long n = scanner.nextLong();
final long m = scanner.nextLong();
System.out.println(computeFibonacciPisano(n, m));
}
private static long computeFibonacciPisano(long n, long m) {
final List<Long> pisanoPeriodValues = new ArrayList<>();
pisanoPeriodValues.add(0L);
pisanoPeriodValues.add(1L);
int i = 0;
while (!(i > 0 && pisanoPeriodValues.get(i) == 0 && pisanoPeriodValues.get(i + 1) == 1)) {
final long a = pisanoPeriodValues.get(i) % m;
final long b = pisanoPeriodValues.get(i + 1) % m;
final long sum = (a + b) % m;
pisanoPeriodValues.add(sum);
i++;
}
final long index = n % i;
return pisanoPeriodValues.get((int) index);
}
}
注意: 前端模版用templates的话,必须引入 thymeleaf依赖。
<dependency>
<groupId>org.springframework.boot</groupId>
<artifactId>spring-boot-starter-thymeleaf</artifactId>
</dependency>
import numpy as np
a = np.array([[1,0,2],[0,0,1],[0,0,1]]) # (3 * 3)
b = np.array([1,2,1]) # (3,) 抛开线性代数的行向量和列向量,这里他是二者都可以的
c1 = a * b # 相当于[1,2,1]这个数作用于每一列
c2 = b * a # 这里是作为一个行向量的, (1 * 3)@ (3 *3) = (1 * 3) 结果还是显示(3,)
# 这里的 c1 = c2
而
np.array([[0,0,0]])
——1行3列
倒序代码:
public void reverseNode(){
HeroNode newHeadNode = new HeroNode(0,"","");
HeroNode temp = head.next;
HeroNode temporaryNode = null;
while (true){
if(temp == null){
break;
}
//遍历原来的链表,每遍历一个节点,就将其取出,并放在新的链表 reverseHead 的最前端
temporaryNode = temp.next; //先暂时保存当前节点的下一个节点,因为后面需要使用
temp.next = newHeadNode.next; //将 temp 的下一个节点指向新的链表的最前节点(非头节点)
newHeadNode.next = temp; //将新头节点指向temp完成插入
temp = temporaryNode; //temp在原节点后移
}
head.next = newHeadNode.next; //最后将原头节点指向新链的第一个节点
}
类//节点类:
class HeroNode{
public int no;
public String name;
public String nickname;
public HeroNode next;
public HeroNode(int no, String name, String nickname){
this.no = no;
this.name = name;
this.nickname = nickname;
}
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.