(第 1 题) 哈希查找(难度系数75)
(第 2 题) 图的广度优先搜索(难度系数100)
import com.sun.org.apache.xpath.internal.operations.Bool;import java.io.BufferedInputStream;
import java.util.*;public class BFS {public static void main(String[] args) {int[][] g;boolean[] st;String str;char[] s;int n;Scanner cin = new Scanner(System.in);n = cin.nextInt();g = new int[n][n];st = new boolean[n];str = cin.next();s=str.toCharArray();for (int i = 0; i < n; i++)for (int j = 0; j < n; j++)g[i][j] = cin.nextInt();char start = cin.next().charAt(0);Queue<Character> q = new LinkedList<>();q.add(start);while (!q.isEmpty()){Character t=q.poll();System.out.print(t+" ");int idx=str.indexOf(t);st[idx]=true;char[] temp=new char[27];for(int j=0;j<n;j++)if(g[idx][j]!=0)temp[s[j]-'A']=s[j];for(int i=0;i<26;i++)if(temp[i]!=0&&!st[str.indexOf(temp[i])]&&!q.contains(temp[i]))q.offer(temp[i]);}}
}
(第 3 题) 循环队列(难度系数75)
(第 4 题) 顺序查找(难度系数65)
(第 5 题) 希尔排序(难度系数85)
(第 6 题) 稀疏矩阵的操作(难度系数/65)
(第 7 题) 图的深度优先搜索(难度系数100)
import java.io.BufferedInputStream;
import java.util.Scanner;public class DFS {static int[][] g;static boolean[] st;static String s;static int n;static char start;static char[] a;public static void main(String[] args) {Scanner cin=new Scanner(new BufferedInputStream(System.in));n=cin.nextInt();g=new int[n][n];st=new boolean[n];s=cin.next();for(int i=0;i<n;i++)for(int j=0;j<n;j++)g[i][j]=cin.nextInt();start=cin.next().charAt(0);a=s.toCharArray();dfs(start);}static void dfs(char start){int idx=s.indexOf(start);st[idx]=true;System.out.print(start+" ");char[] temp=new char[27];for(int i=0;i<n;i++)if(g[idx][i]!=0)temp[a[i]-'A']=a[i];for(int i=0;i<26;i++)if(temp[i]!=0&&!st[s.indexOf(temp[i])])dfs(temp[i]);}
}
(第 8 题) 直接插入排序(难度系数75)
(第 9 题) 链式线性表的插入与删除(难度系数65)
(第 10 题)三元组的快速转置(难度系数/85)
(第 11 题) 哈夫曼编码大全(难度系数100)
题目: 哈夫曼编码大全
描述:
关于哈夫曼树的建立,编码,解码。
输入
第一行输入数字N,代表总共有多少个字符以及权值
第二第三行分别是一行字符串,以及每个字符对应的权值
接下来输入一个数M,表示接下来有M行字符串,要求你对每个字符串进行编码
再输入一个数X,表示接下来有X行编码,要求你对每行编码进行解码
输出
第一行输出所有节点的权重
接下来输出N行,每行以 “a:001”的格式输出每个字符对应的编码
接着输出M行,对输入的字符串的编码结果
最后,输出X行的解码结果
输入样例
6
abcdef
50 10 5 5 20 10
2
abcdef
defabaabbc
2
011001100100110110101101100
1100011000110101100101100
输出样例
50 10 5 5 20 10 10 20 30 50 100
a:0
b:100
c:1100
d:1101
e:111
f:101
010011001101111101
11011111010100001001001100
accbdfadb
cacadacfb
import java.io.BufferedInputStream;
import java.util.*;public class Huffman {static char[] s;static HashMap<Character,Integer>mpw=new HashMap<>();static HashMap<Character,String>mpCode=new HashMap<>();static HashMap<String,Character>mpC=new HashMap<>();static ArrayList<Node> list=new ArrayList<>();static Queue<Integer> q=new LinkedList<>();static int n;public static void main(String[] args) {Scanner cin=new Scanner(new BufferedInputStream(System.in));n=cin.nextInt();s=cin.next().toCharArray();for(int i=0;i<n;i++){int x=cin.nextInt();mpw.put(s[i],x);q.add(x);}bulidHuffman();buildCode(list.get(0));int t=cin.nextInt();for(int x:q)System.out.print(x+" ");System.out.println();for(char c:s)System.out.println(c+":"+mpCode.get(c));while(t--!=0){char[] str=cin.next().toCharArray();for (char c : str)System.out.print(mpCode.get(c));System.out.println();}t=cin.nextInt();while(t--!=0){String str=cin.next();String temp="";for(int i=0;i<str.length();i++){temp+=str.charAt(i);if(mpC.containsKey(temp)){System.out.print(mpC.get(temp));temp="";}}System.out.println();}}public static void bulidHuffman(){Node l,r;for(int i=0;i<n;i++)list.add(new Node(s[i],mpw.get(s[i])));while(list.size()!=1){Collections.sort(list, Comparator.comparingInt(o -> o.w));l=list.remove(0);l.code="0";r=list.remove(0);r.code="1";Node node=new Node(l.w+r.w,l,r);list.add(node);q.add(node.w);}}public static void buildCode(Node root){if(root.l!=null){root.l.code= root.code+root.l.code;buildCode(root.l);}if(root.r!=null){root.r.code= root.code+ root.r.code;buildCode(root.r);}if(root.l==null&&root.r==null){mpCode.put(root.ch,root.code);mpC.put(root.code,root.ch);}}
}
class Node{Character ch;Integer w;Node l;Node r;String code="";public Node(Character ch,Integer w){this.ch=ch;this.w=w;}public Node(Integer w,Node l,Node r){this.w=w;this.l=l;this.r=r;}
}