技术标签： 算法 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;
}
}
文章浏览阅读429次。报错信息如下：[Code: 1093, SQL State: HY000] You can’t specify target table ‘bd_bankaccbas’ for update in FROM clause译文：不能在FROM子句中指定目标表‘bd_bankaccbas’进行更新。有问题的SQL语句如下，它在oracle数据库的语法是支持的，但是mysql就不支持直接这么写：from和update都是同一张表。<span style="col..._you can't specify target table 't_bill' for update in from clause
文章浏览阅读421次。为什么80%的码农都做不了架构师？>>> ..._@jmslistener rabitmq
文章浏览阅读414次。转载：https://mp.weixin.qq.com/s/VQb_mAFbStQXurtByBa0oQ_测试版cpu是怎么流出的?
文章浏览阅读1.5w次，点赞91次，收藏384次。Nginx - 学相伴分享人：秦疆（遇见狂神说）公司产品出现瓶颈？我们公司项目刚刚上线的时候，并发量小，用户使用的少，所以在低并发的情况下，一个jar包启动应用就够了，然后内部tomcat返回内容给用户。但是慢慢的，使用我们平台的用户越来越多了，并发量慢慢增大了，这时候一台服务器满足不了我们的需求了。于是我们横向扩展，又增加了服务器。这个时候几个项目启动在不同的服务器上，用户要访问，就需要增加一个代理服务器了，通过代理服务器来帮我们转发和处理请求。我们希望这个代理服务器可以帮助我们接_遇见狂神说 nginx
文章浏览阅读474次。一种基于北斗的低功耗双向非实时通信方法【技术领域】[0001]本发明涉及一种基于北斗的低功耗双向非实时通信方法，属于北斗系统通信技术领域。【背景技术】[0002]北斗卫星系统具备的短报文通信功能在水文、气象、海洋、林业领域的遥测系统已经广泛应用。但鉴于目前北斗通讯终端的功耗较大，发信频度受限的问题，这些遥测系统在应用北斗卫星作为数据传输载体时，一般只实现了野外遥测站向数据采集中心站的单向传输功能，..._北斗双向通信
文章浏览阅读981次，点赞2次，收藏2次。windows域名映射_windows域名映射文件
文章浏览阅读171次。1 安装在官网下载对应版本， 如果要破解，请找到破解用 charles.jar（charles用java写的），替换掉安装目录中 jar 文件2 取得管理权限下载证书pc移动端证书help -> proxy ssl -> 选择对应的选项，安装好选项，授权永久信任，再输入当前用户密，最后输入 grant 用户权限密码（如果自己的电脑无需）3 使用charles 配置..._macbook charles method connection
文章浏览阅读7.3k次，点赞30次，收藏133次。2023最新Android Studio安装、卸载、解决c盘占用教程，从安装到hello world运行_build configuration language
文章浏览阅读245次。摘要：这项工作解决了一个具有挑战性的问题，即从单目视频中估计完整的三维人体形状和姿态。由于现实世界的三维网格标记数据集有限，目前大多数的三维人体形状重建方法只关注单一的RGB图像，丢失了所有的时间信息。与此相反，我们提出了一种临时细化的图形网，包括图像级模块和视频级模块，来解决这一问题。imagelevel模块是用于从图像中进行人体形状和姿态估计的图U-Nets，其中图卷积神经网络(Graph CNN)有助于相邻顶点的信息交流，U-Nets架构扩大了每个顶点的接受域，融合了高层和低层特征。videolev_temporally refined graph u-nets for human shape and pose estimation from mon
文章浏览阅读2.0k次。注意：Oracle安装不能用root用户安装，必须新建用户安装1、 sqlplus命令不识别问题(bash ：sqlplus command not found)当你首次安装oracle后，也许会出现这种情况，第一次或许有点棘手，不知道如何改怎么办。这时不用着急，想想Linux里面的命令是如何运行的，如adduser等，我们发现是因为在/bin/文件夹下有这样的一个文件adduser，于是我们也想..._ubuntu中oracle提示sqlpus: command not found
文章浏览阅读2.6k次。elasticsearch-setup-passwords interactive[root@node-zwf ~]# su elasticsearch[elasticsearch@node-zwf root]$ cd /home/elasticsearch/elasticsearch-7.8.0/[elasticsearch@node-zwf elasticsearch-7.8.0]$ elasticsearch-setup-passwords interactiveba..._bash: elasticsearch-setup-passwords: command not found
文章浏览阅读922次。第一条为了进一步加强学校涉密计算机和涉密移动存储介质(移动硬盘、U盘、软盘、光盘、存储卡等)的安全保密工作，维护国家安全和利益，维护学校稳定和发展，结合我校工作实际，特制定本规定。第二条学校保密委员会负责全校涉密计算机、移动存储介质保密管理的指导、协调和监督工作。保密技术防范和管理工作由学校网络中心负责。第三条涉密计算机的日常管理制度(一)涉密计算机不得直接或间接接入国际互联网、校园网和其他公共信..._大学 涉密计算机安全保密策略