倒计时9
一、剪邮票
深度优先和广度优先，可以解决连通性问题。稍后补充地接斯特拉的最短路径问题
这里用的是递归的深度优先（dfs）
public class Main {
static int a[] = new int[5];
public static void main(String[] args) {
int count = 0;
for (a[0] = 0; a[0] < 12; a[0]++) {
for (a[1] = a[0] + 1; a[1] < 12; a[1]++) {
for (a[2] = a[1] +1 ; a[2] < 12; a[2]++) {
for (a[3] = a[2]+1; a[3] < 12; a[3]++) {
for (a[4] = a[3]+1; a[4] < 12; a[4]++) {
if (judge()) {
count++;
}
}
}
}
}
}
System.out.println(count);
}
// 检测连通性
private static boolean judge() {
boolean visit[] = new boolean[5];
dfs(visit,0);
return visit[0]&&visit[1]&&visit[2]&&visit[3]&&visit[4];
}
// dfs
private static void dfs(boolean[] visit, int i) {
visit[i] = true;
for (int j = 0; j < visit.length; j++) {
// 不是4和8的时候
if (!visit[j] && (a[i]/4==a[j]/4) && (a[i]==a[j]+1 || a[i]==a[j]-1)) {
dfs(visit, j);
}
// 是4和8的时候
if (!visit[j] && (a[i] == a[j]+4 || a[i]==a[j]-4)) {
dfs(visit, j);
}
}
}
}
二、对深度优先与广度优先的补充
致敬前辈
广度优先 （非递归）
// LinkedList实现了Queue接口 FIFO
Queue queue = new LinkedList();
深度优先（非递归）
Stack stack = new Stack();
1、构建、查询矩阵的函数，包含点与连接的边，用于之后的查询
太长了…运行2来看
package buchong;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
public class GraphByMatrix {
public static final boolean UNDIRECTED_GRAPH = false;//无向图标志
public static final boolean DIRECTED_GRAPH = true;//有向图标志
public static final boolean ADJACENCY_MATRIX = true;//邻接矩阵实现
public static final boolean ADJACENCY_LIST = false;//邻接表实现
public static final int MAX_VALUE = Integer.MAX_VALUE;
private boolean graphType;
private boolean method;
private int vertexSize;
private int matrixMaxVertex;
//存储所有顶点信息的一维数组
private Object[] vertexesArray;
//存储图中顶点之间关联关系的二维数组,及边的关系
private int[][] edgesMatrix;
// 记录第i个节点是否被访问过
private boolean[] visited;
/**
* @param graphType 图的类型：有向图/无向图
* @param method 图的实现方式：邻接矩阵/邻接表
*/
public GraphByMatrix(boolean graphType, boolean method, int size) {
this.graphType = graphType;
this.method = method;
this.vertexSize = 0;
this.matrixMaxVertex = size;
if (this.method) {
visited = new boolean[matrixMaxVertex];
vertexesArray = new Object[matrixMaxVertex];
edgesMatrix = new int[matrixMaxVertex][matrixMaxVertex];
//对数组进行初始化，顶点间没有边关联的值为Integer类型的最大值
for (int row = 0; row < edgesMatrix.length; row++) {
for (int column = 0; column < edgesMatrix.length; column++) {
edgesMatrix[row][column] = MAX_VALUE;
}
}
}
}
/**
* 深度优先搜索DFS（depth-first search），递归
*/
public void DFS() {
//这里是从第一上添加的顶点开始搜索
DFS(vertexesArray[0]);
}
/**
* 以obj为开始
* */
public void DFS(Object obj) {
int index = -1;
for (int i = 0; i < vertexSize; i++) {
if (vertexesArray[i].equals(obj)) {
index = i;
break;
}
}
if (index == -1) {
throw new NullPointerException("没有这个值: " + obj);
}
for (int i = 0; i < vertexSize; i++) {
visited[i] = false;
}
//这里要想清楚，不能放下面if else的后面！
traverse(index);
//graphType为true为有向图
if (graphType) {
for (int i = 0; i < vertexSize; i++) {
if (!visited[i])
traverse(i);
}
}
}
/**
* 深度优先就是由开始点向最深处遍历，没有了就回溯到上一级顶点
* */
private void traverse(int i) {
visited[i] = true;
System.out.print(vertexesArray[i] + " ");
//由于是递归，如果j=-1,该方法仍然会运行，会回溯到上一级顶点！！！
for (int j = firstAdjVex(i); j >= 0; j = nextAdjVex(i, j)) {
if (!visited[j]) {
traverse(j);
}
}
}
/**
* 广度优先遍历算法 Breadth-first search（非递归）
*/
public void BFS() {
// LinkedList实现了Queue接口 FIFO
Queue<Integer> queue = new LinkedList<Integer>();
for (int i = 0; i < vertexSize; i++) {
visited[i] = false;
}
//这个循环是为了确保每个顶点都被遍历到
for (int i = 0; i < vertexSize; i++) {
if (!visited[i]) {
queue.add(i);
visited[i] = true;
System.out.print(vertexesArray[i] + " ");
while (!queue.isEmpty()) {
int row = queue.remove();
for (int k = firstAdjVex(row); k >= 0; k = nextAdjVex(row, k)) {
if (!visited[k]) {
queue.add(k);
visited[k] = true;
System.out.print(vertexesArray[k] + " ");
}
}
}
}
}
}
private int firstAdjVex(int row) {
for (int column = 0; column < vertexSize; column++) {
if (edgesMatrix[row][column] == 1)
return column;
}
return -1;
}
private int nextAdjVex(int row, int k) {
for (int j = k + 1; j < vertexSize; j++) {
if (edgesMatrix[row][j] == 1)
return j;
}
return -1;
}
/*********************************************************************/
// 深度非递归遍历
public void DFS2() {
Stack<Integer> stack = new Stack<Integer>();
for (int i = 0; i < vertexSize; i++) {
visited[i] = false;
}
for (int i = 0; i < vertexSize; i++) {
if (!visited[i]) {
stack.add(i);
// 设置第i个元素已经进栈
visited[i] = true;
while (!stack.isEmpty()) {
int j = stack.pop();
System.out.print(vertexesArray[j] + " ");
for (int k = lastAdjVex(j); k >= 0; k = lastAdjVex(j, k)) {
if (!visited[k]) {
stack.add(k);
visited[k] = true;
}
}
}
}
}
}
// 最后一个
public int lastAdjVex(int i) {
for (int j = vertexSize - 1; j >= 0; j--) {
if (edgesMatrix[i][j] == 1)
return j;
}
return -1;
}
// 上一个
public int lastAdjVex(int i, int k) {
for (int j = k - 1; j >= 0; j--) {
if (edgesMatrix[i][j] == 1)
return j;
}
return -1;
}
public boolean addVertex(Object val) {
assert (val != null);
vertexesArray[vertexSize] = val;
vertexSize++;
return true;
}
public boolean addEdge(int vnum1, int vnum2) {
assert (vnum1 >= 0 && vnum2 >= 0 && vnum1 != vnum2);
//有向图
if (graphType) {
edgesMatrix[vnum1][vnum2] = 1;
} else {
edgesMatrix[vnum1][vnum2] = 1;
edgesMatrix[vnum2][vnum1] = 1;
}
return true;
}
}
2、对造图和查询的操作~
package buchong;
public class test_3{
public static void main(String[] args) {
boolean DIRECTED_GRAPH=false;
boolean ADJACENCY_MATRIX=true;
GraphByMatrix g = new GraphByMatrix(DIRECTED_GRAPH, ADJACENCY_MATRIX, 6);
g.addVertex("1");
g.addVertex("2");
g.addVertex("3");
g.addVertex("4");
g.addVertex("5");
g.addVertex("6");
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 3);
g.addEdge(1, 4);
g.addEdge(2, 1);
g.addEdge(2, 4);
g.addEdge(3, 5);
g.addEdge(2, 4);
g.addEdge(4, 5);
// g.DFS();
// System.out.println();
// g.DFS2();
// System.out.println();
// g.DFS("2");
// System.out.println();
g.BFS();
}
}
三、 带分数 （正确）
思路：N=A+B/C;
1、首先1-9全排列
2、A的长度（i）：1-7；
3、BC的长度：9-i;
4、B的长度（j）：((9-i)/2—7)或者（(9-i)/2+1—7），分9-i的奇偶
5、C的长度（k）：9-i-j
6、如果B%C==0；那么是不可以的…
时间限制：1.0s 内存限制：256.0MB
问题描述
100 可以表示为带分数的形式：100 = 3 + 69258 / 714。
还可以表示为：100 = 82 + 3546 / 197。
注意特征：带分数中，数字1~9分别出现且只出现一次（不包含0）。
类似这样的带分数，100 有 11 种表示法。
输入格式
从标准输入读入一个正整数N (N<1000*1000)
输出格式
程序输出该数字用数码1~9不重复不遗漏地组成带分数表示的全部种数。
注意：不要求输出每个表示，只统计有多少表示法！
样例输入1
100
样例输出1
11
样例输入2
105
样例输出2
6
package lijie_2;
import java.util.Scanner;
public class t3 {
static int res=0;
static int sr=0;
public static void main(String[] args) {
int []num={1,2,3,4,5,6,7,8,9};
Scanner sc=new Scanner(System.in);
sr=sc.nextInt();
qp(num, 0);
System.out.println(res);
}
public static void test(int []num){
for(int i=1;i<=8;i++){//定义A的长
//BC共有9-i位长,j为B的长，k是C的长
int j,k;
if((9-i)%2==0){
j=(9-i)/2;
}else{
j=(9-i)/2+1;
}
for(;j<=(9-i-1);j++){
k=9-i-j;
// if(num[i+j-1]%num[num.length-1]==0){
int A=0;
for(int a=0;a<i;a++){
A+=num[a];
if(a!=i-1){
A*=10;
}
}
int B=0;
for(int a=i;a<i+j;a++){
B+=num[a];
if(a!=i+j-1){
B*=10;
}
}
int C=0;
for(int a=i+j;a<num.length;a++){
C+=num[a];
if(a!=num.length-1){
C*=10;
}
}
// if(A==82&&B==3456){
// System.out.println(A+","+B+","+C);
// }
if(B%C==0){
if(A+B/C==sr){
res++;
// System.out.println(A+","+B+","+C);
}
}
// }else{
//
// }
}
}
}
/**
* 全排列
* */
public static void qp(int []num,int i){
if(i==num.length){
test(num);
// if(num[0]==8&&num[1]==2&&num[2]==3&&num[3]==4&&num[4]==5&&num[5]==6){
// for(int j=0;j<num.length;j++){
// System.out.print(num[j]+" ");
// }
// System.out.println();
// }
}else{
for(int t=i;t<num.length;t++){
swap(num, i, t);
// qp(num,t+1); //不许在这里再出错了！！！！！
qp(num,i+1);
swap(num, i, t);
}
}
}
public static void swap(int []num,int i,int j){
int t=num[i];
num[i]=num[j];
num[j]=t;
}
}
四、剪格子 （正确）
对 舞动的心 大神的敬佩！
思路：从0,0这个位置开始（-1,0）（1,0），（0,1），（0，-1），分别代表着去左右上下，直到和大于等于一半（这其实是一个递归过程）。和等于一半的时候再去判断另一半是否连通，使用dfs。
时间限制：1.0s 内存限制：256.0MB
问题描述
如下图所示，3 x 3 的格子中填写了一些整数。
±-–±-+
|10 1|52|
±-***–+
|20|30 1|
*******–+
| 1| 2| 3|
±-±-±-+
我们沿着图中的星号线剪开，得到两个部分，每个部分的数字和都是60。
本题的要求就是请你编程判定：对给定的m x n 的格子中的整数，是否可以分割为两个部分，使得这两个区域的数字和相等。
如果存在多种解答，请输出包含左上角格子的那个区域包含的格子的最小数目。
如果无法分割，则输出 0。
输入格式
程序先读入两个整数 m n 用空格分割 (m,n<10)。
表示表格的宽度和高度。
接下来是n行，每行m个正整数，用空格分开。每个整数不大于10000。
输出格式
输出一个整数，表示在所有解中，包含左上角的分割区可能包含的最小的格子数目。
样例输入1
3 3
10 1 52
20 30 1
1 2 3
样例输出1
3
样例输入2
4 3
1 1 1 1
1 30 80 2
1 1 1 100
样例输出2
10
package lijie_2;
import java.util.Scanner;
public class t4 {
public static int n, m;
public static int SUM;
public static int[][] step = {{-1,0},{1,0},{0,-1},{0,1}};
public static int[][] map;
public static int[][] visited;
public static int result = 10000;
public void testDFS(int x, int y, int[][] v) { //完成剪切后的另一部分是否是连通的
v[x][y] = 2;
for(int i = 0;i < 4;i++) {
int x1 = x + step[i][0];
int y1 = y + step[i][1];
if(x1 < 0 || x1 >= n || y1 < 0 || y1 >= m)
continue;
if(v[x1][y1] == 0)
testDFS(x1, y1, v);
}
}
public void dfs(int startX, int startY, int count, int sum) {
if(sum == SUM / 2) {
int x = 0, y = 0, step = 0;
int[][] v = new int[n][m];
for(int i = 0;i < n;i++) {
for(int j = 0;j < m;j++) {
if(visited[i][j] == 0) {
x = i;
y = j;
}
v[i][j] = visited[i][j];
}
}
testDFS(x, y, v);
for(int i = 0;i < n;i++)
for(int j = 0;j < m;j++)
if(v[i][j] == 2)
step++;
if(step + count == n * m) {
if(visited[0][0] == 1)
result = Math.min(result, count);
else {
result = Math.min(result, step);
}
}
return;
} else if(sum > SUM / 2)
return;
for(int i = 0;i < 4;i++) {
int x1 = startX + step[i][0];
int y1 = startY + step[i][1];
if(x1 < 0 || x1 >= n || y1 < 0 || y1 >= m)
continue;
if(visited[x1][y1] == 1)
continue;
visited[x1][y1] = 1;
count++;
sum += map[x1][y1];
dfs(x1, y1, count, sum);
sum -= map[x1][y1];
count--;
visited[x1][y1] = 0;
}
}
public static void main(String[] args) {
t4 test = new t4();
Scanner in = new Scanner(System.in);
m = in.nextInt();
n = in.nextInt();
map = new int[n][m];
SUM = 0;
for(int i = 0;i < n;i++) {
for(int j = 0;j < m;j++) {
map[i][j] = in.nextInt();
SUM += map[i][j];
}
}
if(SUM % 2 == 0) {
for(int i = 0;i < n;i++) {
for(int j = 0;j < m;j++) {
visited = new int[n][m];
int sum = map[i][j];
int count = 1;
visited[i][j] = 1;
test.dfs(i, j, count, sum);
}
}
if(result != 10000){
System.out.println(result);
}else{
System.out.println("-1");
}
} else{
System.out.println("-1");
}
}
}
五、循环节长度
package buchong;
import java.util.Vector;
/**
* 求解循环节长度
* n÷m
* 11÷13=0.846153846153846153846153....
* 循环节就是846153，共六位长
* 21÷13=1.846153846153846153846153....
* 循环节也是846153，共六位长
*
*
* 那么如果n>m先 n=n%m
* 循环节的每一位都可以用n=n*10,n/m n=n%m来解决
*
* 110÷13 整位得8 余数为6
* 60÷13 整位得4 余数为8
*
*
* 关键在于如何存储....嘿嘿嘿...我想到了字符串KMP匹配...
* 其实有更简单的办法，就是在每一步中，一旦发现 余数相同了，那后面肯定也相同了！！！
* 所以循环节就是从第一个相等的余数到本余数之间~
* */
public class xhj {
public static void main(String[] args) {
int n=11;
int m=13;
System.out.println(f(n,m));
}
public static int f(int n, int m)
{
n = n % m;
Vector v = new Vector();
for(;;)
{
v.add(n);
n *= 10;
n = n % m;
if(n==0) return 0;
if(v.indexOf(n)>=0) return v.size()-v.indexOf(n); //填空
}
}
}
六、查询字符串出现次数
package buchong;
/***
* String的CompareTo,charAt,indexOf
*
*
* 1.查询oppo在oppoppo中出现次数为2
* 2.查询oppo在oppoppo中出现次数为1
* */
public class Strings {
public static void main(String[] args) {
String s="oppoppo";
// System.out.println(s.compareTo("c"));
// System.out.println(s.compareTo("ac"));
// System.out.println(s.compareTo(s));
// System.out.println(s.indexOf("ba"));
// System.out.println(s.indexOf("c"));
String z="oppo";
System.out.println(sub1(z, s));
System.out.println(sub2(z, s));
}
/**
* 1.查询oppo在oppoppo中出现次数为2
* */
public static int sub1(String z,String s){
int num=0;
while(s.indexOf(z)>=0){
num++;
s=s.substring(s.indexOf(z)+1);
}
return num;
}
/**
* 2.查询oppo在oppoppo中出现次数为1
* */
public static int sub2(String z,String s){
int num=0;
while(s.indexOf(z)>=0){
num++;
s=s.substring(s.indexOf(z)+z.length());
// System.out.println(s);
}
return num;
}
}
七、查询周几
package buchong;
/**
* 计算y m d是周几
* 0-6代表 7-6
* */
public class time_1 {
public static void main(String[] args) {
int y=2018,m=3,d=31;
System.out.println(week(y,m,d));
}
/**
* 计算y m d是周几
* 以前是求出来共有多少天，再计算。现在是年计算 月计算 日计算
* */
public static int week(int y,int m,int d){
int ans=0;
for(int i=1;i<y;i++){
if((i%400==0)||((i%100!=0)&&(i%4==0))){
ans+=366;
ans%=7;
}else{
ans+=365;
ans%=7;
}
}
for(int i=1;i<m;i++){
if(i==1||i==3||i==5||i==7||i==8||i==10||i==12){
ans+=31;
ans%=7;
}else if((y%400==0)||((y%100!=0)&&(y%4==0))||i==2){
ans+=29;
ans%=7;
}else if(!((y%400==0)||((y%100!=0)&&(y%4==0)))||i==2){
ans+=28;
ans%=7;
}else{
ans+=30;
ans%=7;
}
}
ans+=d-1;
ans%=7;
return ans;
}
}
八、 错误票据
用到了之前提到的自动排序的TreeMap，进行键值对匹配
时间限制：1.0s 内存限制：256.0MB
问题描述
某涉密单位下发了某种票据，并要在年终全部收回。
每张票据有唯一的ID号。全年所有票据的ID号是连续的，但ID的开始数码是随机选定的。
因为工作人员疏忽，在录入ID号的时候发生了一处错误，造成了某个ID断号，另外一个ID重号。
你的任务是通过编程，找出断号的ID和重号的ID。
假设断号不可能发生在最大和最小号。
输入格式
要求程序首先输入一个整数N(N<100)表示后面数据行数。
接着读入N行数据。
每行数据长度不等，是用空格分开的若干个（不大于100个）正整数（不大于100000），请注意行内和行末可能有多余的空格，你的程序需要能处理这些空格。
每个整数代表一个ID号。
输出格式
要求程序输出1行，含两个整数m n，用空格分隔。
其中，m表示断号ID，n表示重号ID
样例输入1
2
5 6 8 11 9
10 12 9
样例输出1
7 9
样例输入2
6
164 178 108 109 180 155 141 159 104 182 179 118 137 184 115 124 125 129 168 196
172 189 127 107 112 192 103 131 133 169 158
128 102 110 148 139 157 140 195 197
185 152 135 106 123 173 122 136 174 191 145 116 151 143 175 120 161 134 162 190
149 138 142 146 199 126 165 156 153 193 144 166 170 121 171 132 101 194 187 188
113 130 176 154 177 120 117 150 114 183 186 181 100 163 160 167 147 198 111 119
样例输出2
105 120
package lijie_2;
import java.util.Scanner;
import java.util.TreeMap;
public class t5 {
public static void main(String[] args) {
TreeMap<Integer,Integer> tm=new TreeMap<Integer, Integer>();
Scanner sc=new Scanner(System.in);
int n=Integer.parseInt(sc.nextLine());
int d=-1,s;
while(n>0){
String ss=sc.nextLine();
String []ssc=ss.split(" ");
for(int i=0;i<ssc.length;i++){
int t=Integer.parseInt(ssc[i]);
if(tm.get(t)!=null){
d=t;
}else{
tm.put(t, 1);
}
}
n--;
}
java.util.Iterator<Integer> it=tm.keySet().iterator();
int f=it.next();
// System.out.println(f+" first");
while(it.hasNext()){
int ff=it.next();
// System.out.println(ff+" ff");
if(ff-f==1){
f=ff;
}else{
System.out.println(ff-1+" "+d);
break;
}
}
}
}