技术标签： 算法 java 复试 上海交通大学考研复试机考
问题一：
题目描述
对于一个字符串，将其后缀子串进行排序，例如grain 其子串有： grain rain ain in n 然后对各子串按字典顺序排序，即： ain,grain,in,n,rain
输入描述:
每个案例为一行字符串。
输出描述:
将子串排序输出
示例1
输入
grain
输出
ain
grain
in
n
rain
import java.io.*;
import java.util.*;
public class Main
{
public static void main(String[] args){
try {
BufferedReader br = new BufferedReader(new BufferedReader(new InputStreamReader(System.in)));
String str = br.readLine();
int len = str.length();
String[] subs = new String[len];
for(int i = 0; i < len; i++) {
subs[i] = str.substring(i);
}
Arrays.parallelSort(subs);
for(int i = 0; i < len; i++) {
System.out.println(subs[i]);
}
} catch (IOException e) {
e.printStackTrace();
}
}
}
问题二：
题目描述
N个城市，标号从0到N-1，M条道路，第K条道路（K从0开始）的长度为2^K，求编号为0的城市到其他城市的最短距离
输入描述:
第一行两个正整数N（2<=N<=100）M(M<=500),表示有N个城市，M条道路
接下来M行两个整数，表示相连的两个城市的编号
输出描述:
N-1行，表示0号城市到其他城市的最短路，如果无法到达，输出-1，数值太大的以MOD 100000 的结果输出。
示例1
输入
4 4
1 2
2 3
1 3
0 1
输出
8
9
11
Kruskal算法
import java.util.*;
import java.io.*;
import java.text.* ;
public class Main
{
public static void main(String[] args) throws ParseException{
try {
BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
String str;
while((str = br.readLine()) != null) {
String[] parts = str.split(" ");
int n = Integer.parseInt(parts[0]);
int len = Integer.parseInt(parts[1]);
int[][] dis = new int[n][n];
int[] tree = new int[n];
int lens = 1;
int i;
for(i = 0; i < n; i++) {
tree[i] = -1;
for(int j = 0; j < n; j++) dis[i][j] = -1;
dis[i][i] = 0;
}
int x, y;
for(i = 0; i < len; i++) {
parts = br.readLine().split(" ");
int a = Integer.parseInt(parts[0]);
int b = Integer.parseInt(parts[1]);
x = findRoot(a, tree);
y = findRoot(b, tree);
if(i>0){
lens = (lens*2)%100000;
}
if(x != y) {
for(int j = 0; j < n; j++) {
if(x == findRoot(j, tree)) {
for(int k = 0; k < n; k++) {
if(y == findRoot(k, tree)){
dis[j][k]=(dis[j][a]+dis[b][k]+lens)%100000;
dis[k][j]=dis[j][k];
}
}
}
}
tree[y] = x;
}
}
for(i = 1; i < n; i++)
System.out.println(dis[0][i]);
}
} catch (IOException e) {
e.printStackTrace();
}
}
public static int findRoot(int x, int[] tree) {
if(tree[x] == -1) return x;
else {
tree[x] = findRoot(tree[x], tree);
return tree[x];
}
}
}
问题三：
题目描述
对于一个不存在括号的表达式进行计算
输入描述:
存在多种数据，每组数据一行，表达式不存在空格
输出描述:
输出结果
示例1
输入
6/2+3+3*4
输出
18
计算中缀表达式
import java.util.*;
import java.io.*;
import java.text.* ;
public class Main
{
public static int[] pos = {
0};
public static char[] ch;
public static int len;
public static int i;
public static void main(String[] args) throws ParseException{
try {
BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
ch = br.readLine().toCharArray();
System.out.println((int)compute());
} catch (IOException e) {
e.printStackTrace();
}
}
//转换小数
public static double translation() {
double integer = 0.0;
double remainder = 0.0;
while(i < len && ch[i] >= '0' && ch[i] <= '9') {
integer *= 10;
integer += (ch[i] - '0');
i++;
}
if(i < len && ch[i] == '.') {
i++;
double c = 0.1;
while(ch[i] >= '0' && ch[i] <= '9') {
double t = ch[i] -'0';
t *= c;
c *= 0.1;
remainder += t;
i++;
}
}
return integer + remainder;
}
//计算优先级
public static int getLevel(char ch)
{
switch (ch)
{
case '+':
case '-':
return 1;
case '*':
case '/':
return 2;
case '(':
return 0;
};
return -1;
}
public static double operate(double a1, char op, double a2)
{
switch (op)
{
case '+':
return a1 + a2;
case '-':
return a1 - a2;
case '*':
return a1 * a2;
case '/':
return a1 / a2;
};
return 0;
}
public static double compute() {
Stack<Character> optr = new Stack<>();
Stack<Double> opnd = new Stack<>();
len = ch.length;
boolean isMinus = true; // 判断'-'是减号还是负号, true表示负号
for(i = 0; i < len;) {
if(ch[i] == '-' && isMinus) {
opnd.push(0.0);
optr.push('-');
i++;
}
else if(ch[i] == ')') {
isMinus = false;
i++;
while(optr.peek() != '(') {
double a2 = opnd.pop();
double a1 = opnd.pop();
char op = optr.pop();
double result = operate(a1, op, a2);
opnd.push(result);
}
optr.pop();
}
else if(ch[i] >= '0' && ch[i] <= '9') {
isMinus = false;
opnd.push(translation());
}
else if(ch[i] == '(') {
isMinus = true;
optr.push(ch[i]);
i++;
}
else {
while(!optr.empty() && getLevel(ch[i]) <= getLevel(optr.peek())) {
double a2 = opnd.pop();
double a1 = opnd.pop();
char op = optr.pop();
double result = operate(a1, op, a2);
opnd.push(result);
}
optr.push(ch[i]);
i++;
}
}
while(!optr.empty()) {
double a2 = opnd.pop();
double a1 = opnd.pop();
char op = optr.pop();
double result = operate(a1, op, a2);
opnd.push(result);
}
return opnd.pop();
}
}
后缀表达式计算
import java.util.*;
import java.io.*;
import java.text.* ;
public class Main
{
public static char[] ch;
public static int len;
public static int i;
public static void main(String[] args) throws ParseException{
try {
BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
ch = br.readLine().toCharArray();
System.out.println((int)compute());
} catch (IOException e) {
e.printStackTrace();
}
}
public static double operate(double a1, char op, double a2) {
switch(op) {
case '+': return a1+a2;
case '-': return a1-a2;
case '*': return a1*a2;
case '/': return a1/a2;
};
return 0;
}
public static double compute() {
Stack<Double> opnd = new Stack<>();
len = ch.length;
for(i = 0; i < len;) {
if(ch[i] >= '0' && ch[i] <= '9') {
opnd.push((double)(ch[i]-'0'));
i++;
}
else {
double a2 = opnd.pop();
double a1 = opnd.pop();
char op = ch[i];
double result = operate(a1, op, a2);
opnd.push(result);
i++;
}
}
return opnd.pop();
}
}
前缀表达式转中缀表达式
import java.util.*;
import java.io.*;
import java.text.* ;
public class Main
{
public static char[] ch;
public static int len;
public static int i;
public static void main(String[] args) throws ParseException{
try {
BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
ch = br.readLine().toCharArray();
System.out.println(compute());
} catch (IOException e) {
e.printStackTrace();
}
}
//计算优先级
public static int getLevel(char ch) {
switch(ch) {
case '+':
case '-':
return 1;
case '*':
case '/':
return 2;
case '(':
return 0;
};
return -1;
}
public static StringBuilder compute() {
StringBuilder res = new StringBuilder();
Stack<Character> optr = new Stack<>();
Stack<Character> opnd = new Stack<>();
len = ch.length;
boolean isMinus = true;
for(i = 0; i < len;) {
System.out.println(res);
if(ch[i] == '-' && isMinus) {
opnd.push('0');
optr.push('-');
i++;
}
else if(ch[i] == ')') {
isMinus = false;
i++;
while(optr.peek() != '(') {
char a2 = opnd.pop();
char a1 = opnd.pop();
char op = optr.pop();
if(a1 != ' ') res.append(a1);
if(a2 != ' ') res.append(a2);
res.append(op);
opnd.push(' ');
}
optr.pop();
}
else if(ch[i] >= '0' && ch[i] <= '9') {
isMinus = false;
opnd.push(ch[i]);
i++;
}
else if(ch[i] == '(') {
isMinus = true;
optr.push(ch[i]);
i++;
}
else {
while(!optr.empty() && getLevel(ch[i]) <= getLevel(optr.peek())) {
char a2 = opnd.pop();
char a1 = opnd.pop();
char op = optr.pop();
if(a1 != ' ') res.append(a1);
if(a2 != ' ') res.append(a2);
res.append(op);
opnd.push(' ');
}
optr.push(ch[i]);
i++;
}
}
while(!optr.empty()) {
char a2 = opnd.pop();
char a1 = opnd.pop();
char op= optr.pop();
if(a1 != ' ') res.append(a1);
if(a2 != ' ') res.append(a2);
res.append(op);
opnd.push(' ');
}
return res;
}
}
题目描述
一个N*M的矩阵，找出这个矩阵中所有元素的和不小于K的面积最小的子矩阵（矩阵中元素个数为矩阵面积）
输入描述:
每个案例第一行三个正整数N,M<=100，表示矩阵大小，和一个整数K
接下来N行，每行M个数，表示矩阵每个元素的值
输出描述:
输出最小面积的值。如果出现任意矩阵的和都小于K，直接输出-1。
示例1
输入
4 4 10
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
输出
1
暴力解法：
import java.util.*;
import java.io.*;
import java.text.* ;
public class Main
{
static int n;
static int m;
static int[][] matrix;
static int res = Integer.MAX_VALUE;
static int k;
public static void main(String[] args){
try {
BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
String[] parts = br.readLine().split(" ");
n = Integer.parseInt(parts[0]);
m = Integer.parseInt(parts[1]);
k = Integer.parseInt(parts[2]);
matrix = new int[n][m];
for(int i = 0; i < n; i++) {
String[] lines = br.readLine().split(" ");
for(int j = 0; j < m; j++) {
matrix[i][j] = Integer.parseInt(lines[j]);
}
}
System.out.println(matrixSum());
} catch (IOException e) {
e.printStackTrace();
}
}
public static int matrixSum() {
int ans = m*n+1;
for(int i = 0; i < n; i++) {
int[] tmp = new int[m];
for(int j = i; j < n; j++) {
for(int l = 0; l < m; l++)
tmp[l] += matrix[j][l];
int len = getLen(tmp);
ans = Math.min(ans, len*(j-i+1));
}
}
if(ans == m*n+1) return -1;
return ans;
}
private static int getLen(int[] a) {
int low = 0, high = 0;
int len = m*n+1;
int s = 0;
while ( high<m ) {
while ( s<k && high<m ) {
s += a[high];
high ++;
}
while ( s>=k && low<high) {
len = Math.min(len, high-low);
s -= a[low];
low ++;
}
//先往后扩，再往后缩
}
return len;
}
}
文章浏览阅读2w次，点赞7次，收藏51次。四个步骤1.创建C++ Win32项目动态库dll 2.在Win32项目动态库中添加 外部依赖项 lib头文件和lib库3.导出C接口4.c#调用c++动态库开始你的表演...①创建一个空白的解决方案，在解决方案中添加 Visual C++ , Win32 项目空白解决方案的创建：添加Visual C++ , Win32 项目这......_c#调用lib
文章浏览阅读4.6k次。苹方字体是苹果系统上的黑体，挺好看的。注重颜值的网站都会使用，例如知乎：font-family: -apple-system, BlinkMacSystemFont, Helvetica Neue, PingFang SC, Microsoft YaHei, Source Han Sans SC, Noto Sans CJK SC, W..._ubuntu pingfang
文章浏览阅读159次。表单表单概述表单标签表单域按钮控件demo表单标签表单标签基本语法结构<form action="处理数据程序的url地址“ method=”get|post“ name="表单名称”></form><!--action,当提交表单时，向何处发送表单中的数据，地址可以是相对地址也可以是绝对地址--><!--method将表单中的数据传送给服务器处理，get方式直接显示在url地址中，数据可以被缓存，且长度有限制；而post方式数据隐藏传输，_html表单的处理程序有那些
文章浏览阅读1.2k次。使用说明:开启Google的登陆二步验证（即Google Authenticator服务）后用户登陆时需要输入额外由手机客户端生成的一次性密码。实现Google Authenticator功能需要服务器端和客户端的支持。服务器端负责密钥的生成、验证一次性密码是否正确。客户端记录密钥后生成一次性密码。下载谷歌验证类库文件放到项目合适位置(我这边放在项目Vender下面)https://github.com/PHPGangsta/GoogleAuthenticatorPHP代码示例://引入谷_php otp 验证器
文章浏览阅读4.3k次，点赞5次，收藏11次。matplotlib.plot画图横坐标混乱及间隔处理_matplotlib更改横轴间距
文章浏览阅读2.2k次。①Storage driver 处理各镜像层及容器层的处理细节，实现了多层数据的堆叠，为用户 提供了多层数据合并后的统一视图②所有 Storage driver 都使用可堆叠图像层和写时复制（CoW）策略③docker info 命令可查看当系统上的 storage driver主要用于测试目的，不建议用于生成环境。_docker 保存容器
文章浏览阅读834次，点赞27次，收藏13次。网络拓扑结构是指计算机网络中各组件（如计算机、服务器、打印机、路由器、交换机等设备）及其连接线路在物理布局或逻辑构型上的排列形式。这种布局不仅描述了设备间的实际物理连接方式，也决定了数据在网络中流动的路径和方式。不同的网络拓扑结构影响着网络的性能、可靠性、可扩展性及管理维护的难易程度。_网络拓扑csdn
文章浏览阅读1.8k次，点赞5次，收藏8次。IOS系统Date的坑要创建一个指定时间的new Date对象时，通常的做法是：new Date("2020-09-21 11:11:00")这行代码在 PC 端和安卓端都是正常的，而在 iOS 端则会提示 Invalid Date 无效日期。在IOS年月日中间的横岗许换成斜杠，也就是new Date("2020/09/21 11:11:00")通常为了兼容IOS的这个坑，需要做一些额外的特殊处理，笔者在开发的时候经常会忘了兼容IOS系统。所以就想试着重写Date函数，一劳永逸，避免每次ne_date.prototype 将所有 ios
文章浏览阅读5.3k次。方法一：用PLSQL Developer工具。 1 在PLSQL Developer的sql window里输入select * from test for update; 2 按F8执行 3 打开锁, 再按一下加号. 鼠标点到第一列的列头，使全列成选中状态，然后粘贴，最后commit提交即可。（前提..._excel导入pl/sql
文章浏览阅读83次。Git常用命令速查手册1、初始化仓库git init2、将文件添加到仓库git add 文件名 # 将工作区的某个文件添加到暂存区 git add -u # 添加所有被tracked文件中被修改或删除的文件信息到暂存区，不处理untracked的文件git add -A # 添加所有被tracked文件中被修改或删除的文件信息到暂存区，包括untracked的文件...
文章浏览阅读202次。分享119个ASP.NET源码总有一个是你想要的_千博二手车源码v2023 build 1120
文章浏览阅读1.8k次。版权声明：转载请注明出处 http://blog.csdn.net/irean_lau。目录(?)[+]1、缺省构造函数。2、缺省拷贝构造函数。3、 缺省析构函数。4、缺省赋值运算符。5、缺省取址运算符。6、 缺省取址运算符 const。[cpp] view plain copy_空类默认产生哪些类成员函数