HJ70 矩阵乘法计算量估算
描述
矩阵乘法的运算量与矩阵乘法的顺序强相关。
例如：
A是一个50×10的矩阵，B是10×20的矩阵，C是20×5的矩阵
计算A*B*C有两种顺序：（（AB）C）或者（A（BC）），前者需要计算15000次乘法，后者只需要3500次。
编写程序计算不同的计算顺序需要进行的乘法次数。
本题含有多组样例输入！
数据范围：数据组数：1\le t\le 10\1≤t≤10 ，矩阵个数：1\le n\le 15 \1≤n≤15 ，行列数：1\le row_i,col_i\le 100\1≤rowi,coli≤100
进阶：时间复杂度：O(n)\O(n) ，空间复杂度：O(n)\O(n)
输入描述：
输入多行，先输入要计算乘法的矩阵个数n，每个矩阵的行数，列数，总共2n的数，最后输入要计算的法则
计算的法则为一个字符串，仅由左右括号和大写字母（'A'~'Z'）组成，保证括号是匹配的且输入合法！
输出描述：
输出需要进行的乘法次数
示例1
输入：
3
50 10
10 20
20 5
(A(BC))
复制
输出：
3500
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// Scanner sc = new Scanner(System.in);
String str = null;
while ((str = br.readLine()) != null) {
int num = Integer.parseInt(str);
int [][] arr = new int[num][2];
for(int i = 0;i<num;i++) {
String [] sa = br.readLine().split(" ");
arr[i][0] = Integer.parseInt(sa[0]);
arr[i][1] = Integer.parseInt(sa[1]);
}
int n = arr.length -1;
char [] ca = br.readLine(). toCharArray();
Stack<Integer> stack = new Stack<>();
int sum = 0;
for(int i = ca.length - 1;i>=0;i--) {
char one = ca[i];
if(one == ')') {
stack.push(-1);
}else if(one == '(') {
int n1 = stack.pop();
int n2 = stack.pop();
sum+= arr[n1][0]*arr[n2][0]*arr[n2][1];
arr[n1][1] = arr[n2][1];
stack.pop();
stack.push(n1);
}else {
stack.push(n);
n--;
}
}
System.out.println(sum);
}
}
}
HJ71 字符串通配符
描述
问题描述：在计算机中，通配符一种特殊语法，广泛应用于文件搜索、数据库、正则表达式等领域。现要求各位实现字符串通配符的算法。
要求：
实现如下2个通配符：
*：匹配0个或以上的字符（注：能被*和?匹配的字符仅由英文字母和数字0到9组成，下同）
？：匹配1个字符
注意：匹配时不区分大小写。
输入：
通配符表达式；
一组字符串。
输出：
返回不区分大小写的匹配结果，匹配成功输出true，匹配失败输出false
注意：本题含有多组样例输入！
数据范围：数据组数：1\le t\le 10\1≤t≤10 ，字符串长度：1\le s\le 100\1≤s≤100
进阶：时间复杂度：O(n^2)\O(n2) ，空间复杂度：O(n)\O(n)
输入描述：
先输入一个带有通配符的字符串，再输入一个需要匹配的字符串
输出描述：
返回不区分大小写的匹配结果，匹配成功输出true，匹配失败输出false
示例1
输入：
te?t*.*
txt12.xls
复制
输出：
false
复制
示例2
输入：
z
zz
复制
输出：
false
复制
示例3
输入：
pq
pppq
复制
输出：
false
复制
示例4
输入：
**Z
0QZz
复制
输出：
true
复制
示例5
输入：
?*Bc*?
abcd
复制
输出：
true
复制
示例6
输入：
h*?*a
h#a
复制
输出：
false
复制
说明：
根据题目描述可知能被*和?匹配的字符仅由英文字母和数字0到9组成，所以?不能匹配#，故输出false
示例7
输入：
p*p*qp**pq*p**p***ppq
pppppppqppqqppqppppqqqppqppqpqqqppqpqpppqpppqpqqqpqqp
复制
输出：
false
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException{
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
String str="";
while((str=bf.readLine())!=null){
str=str.toLowerCase();
String s=bf.readLine().toLowerCase();
boolean [][] flag=new boolean[str.length()+1][s.length()+1];
flag[0][0]=true;
if(str.charAt(0)=='*'){
flag[1][0]=true;
}
for(int i=1;i<=str.length();i++){
char ch=str.charAt(i-1);
for(int j=1;j<=s.length();j++){
char c=s.charAt(j-1);
if(ch=='?'){
if(check(c)){
flag[i][j]=flag[i-1][j-1];
}else{
flag[i][j]=false;
}
}else if(ch=='*'){
if(check(c)){
flag[i][j]=flag[i-1][j-1]||flag[i][j-1]||flag[i-1][j];
}else{
flag[i][j]=false;
}
}else if(ch==c){
flag[i][j]=flag[i-1][j-1];
}else{
flag[i][j]=false;
}
}
}
System.out.println(flag[str.length()][s.length()]);
}
}
public static boolean check(char ch){
if(ch>='a'&&ch<='z'||ch>='0'&&ch<='9'){
return true;
}
return false;
}
}
HJ74 参数解析
描述
在命令行输入如下命令：
xcopy /s c:\\ d:\\e，
各个参数如下：
参数1：命令字xcopy
参数2：字符串/s
参数3：字符串c:\\
参数4: 字符串d:\\e
请编写一个参数解析程序，实现将命令行各个参数解析出来。
解析规则：
1.参数分隔符为空格
2.对于用""包含起来的参数，如果中间有空格，不能解析为多个参数。比如在命令行输入xcopy /s "C:\\program files" "d:\"时，参数仍然是4个，第3个参数应该是字符串C:\\program files，而不是C:\\program，注意输出参数时，需要将""去掉，引号不存在嵌套情况。
3.参数不定长
4.输入由用例保证，不会出现不符合要求的输入
数据范围：字符串长度：1\le s\le 1000\1≤s≤1000
进阶：时间复杂度：O(n)\O(n) ，空间复杂度：O(n)\O(n)
输入描述：
输入一行字符串，可以有空格
输出描述：
输出参数个数，分解后的参数，每个参数都独占一行
示例1
输入：
xcopy /s c:\\ d:\\e
复制
输出：
4
xcopy
/s
c:\\
d:\\e
import java.io.*;
public class Main{
public static void main(String[] args)throws IOException{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
String s;
while((s=br.readLine())!=null){
char[] chars=s.toCharArray();
StringBuffer ana=new StringBuffer();
int flag=0;
int count=1;
for(int i=0;i<chars.length;i++){
if(chars[i]=='\"'){
flag++;
continue;
}
if(chars[i]!=' '){
ana.append(chars[i]);
}
if(chars[i]==' '&&flag%2!=0){
ana.append(chars[i]);
}
if(chars[i]==' '&&flag%2==0){
ana.append("\n");
count++;
}
}
System.out.println(count+"\n"+ana.toString());
}
}
}
HJ75 公共子串计算
描述
给定两个只包含小写字母的字符串，计算两个字符串的最大公共子串的长度。
注：子串的定义指一个字符串删掉其部分前缀和后缀（也可以不删）后形成的字符串。
数据范围：字符串长度：1\le s\le 150\1≤s≤150
进阶：时间复杂度：O(n^3)\O(n3) ，空间复杂度：O(n)\O(n)
输入描述：
输入两个只包含小写字母的字符串
输出描述：
输出一个整数，代表最大公共子串的长度
示例1
输入：
asdfas
werasdfaswer
复制
输出：
6
import java.io.*;
public class Main{
public static void main(String[] args)throws Exception{
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
String str1 = "";
String str2 = "";
while((str1 = bf.readLine())!= null && (str2 = bf.readLine())!= null){
int max = 0;
char[] cha1 = str1.toCharArray();
char[] cha2 = str2.toCharArray();
for(int i = 0; i < str1.length(); i++){
for(int j = 0; j < str2.length(); j++){
int t1 = i;
int t2 = j;
int count = 0;
while(cha1[t1] == cha2[t2]){
t1++;
t2++;
count++;
max = Math.max(count,max);
if(t1 == cha1.length || t2 == cha2.length) break;
}
}
}
System.out.println(max);
}
}
}
HJ77 火车进站
描述
给定一个正整数N代表火车数量，0<N<10，接下来输入火车入站的序列，一共N辆火车，每辆火车以数字1-9编号，火车站只有一个方向进出，同时停靠在火车站的列车中，只有后进站的出站了，先进站的才能出站。
要求输出所有火车出站的方案，以字典序排序输出。
数据范围：1\le n\le 10\1≤n≤10
进阶：时间复杂度：O(n!)\O(n!) ，空间复杂度：O(n)\O(n)
输入描述：
有多组测试用例，每一组第一行输入一个正整数N（0<n<10），第二行包括n个正整数，范围为1到9。< span="" style="--tw-border-opacity:1; border: 0px solid rgb(221, 221, 221); --tw-shadow:0 0 #0000; --tw-ring-inset:var(--tw-empty, ); --tw-ring-offset-width:0px; --tw-ring-offset-color:#fff; --tw-ring-color:rgba(59,151,255,0.5); --tw-ring-offset-shadow:0 0 #0000; --tw-ring-shadow:0 0 #0000;">
输出描述：
输出以字典序从小到大排序的火车出站序列号，每个编号以空格隔开，每个输出序列换行，具体见sample。
示例1
输入：
3
1 2 3
复制
输出：
1 2 3
1 3 2
2 1 3
2 3 1
3 2 1
复制
说明：
第一种方案：1进、1出、2进、2出、3进、3出
第二种方案：1进、1出、2进、3进、3出、2出
第三种方案：1进、2进、2出、1出、3进、3出
第四种方案：1进、2进、2出、3进、3出、1出
第五种方案：1进、2进、3进、3出、2出、1出
请注意，[3,1,2]这个序列是不可能实现的。
import java.util.*;
public class Main{
private static Stack<String> stack1=new Stack<String>();
private static Stack<String> stack2=new Stack<String>();
private static List<String> list=new ArrayList<String>();
public static void ff(String str){
if(stack1.isEmpty()&&stack2.isEmpty()){
list.add(str.trim());
return;
}
if(!stack2.isEmpty()){
String str1=stack2.pop();
ff(str+" "+str1);
stack2.push(str1);
}
if(!stack1.isEmpty()){
String str2=stack1.pop();
stack2.push(str2);
ff(str);
stack2.pop();
stack1.push(str2);
}
}
public static void main(String[] args){
Scanner scanner=new Scanner(System.in);
while(scanner.hasNext()){
int n=scanner.nextInt();
scanner.nextLine();
String str=scanner.nextLine();
String[] ss=str.split(" ");
for(int i=ss.length-1;i>=0;i--)
stack1.push(ss[i]);
ff("");
Collections.sort(list);
for(String s:list)
System.out.println(s);
}
}
}
HJ82 将真分数分解为埃及分数
描述
分子为1的分数称为埃及分数。现输入一个真分数(分子比分母小的分数，叫做真分数)，请将该分数分解为埃及分数。如：8/11 = 1/2+1/5+1/55+1/110。
注：真分数指分子小于分母的分数，分子和分母有可能gcd不为1！
如有多个解，请输出任意一个。
请注意本题含有多组样例输入！
输入描述：
输入一个真分数，String型
输出描述：
输出分解后的string
示例1
输入：
8/11
2/4
复制
输出：
1/2+1/5+1/55+1/110
1/3+1/6
复制
说明：
第二个样例直接输出1/2也是可以的
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
/**
* 真分数转埃及分数
* 先化简
* 步骤一： 用b除以a，得商数q1及余数r1,即b=a*q1+r1
* 步骤二： a/b=1/(q1+1）+(a-r1)/b(q1+1）
* 步骤三： 重复步骤2，直到分解完毕
* 3/7=1/3+2/21=1/3+1/11+1/231
* @author Admin
* @date 2020-12-20
*/
public class Main {
public static void main(String[] args){
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String str = null;
try {
while((str = br.readLine())!= null){
String[] strArr = str.split("\\/");
int a = Integer.parseInt(strArr[0]);
int b = Integer.parseInt(strArr[1]);
String[] resArr = new String[1];
f(a, b, "", resArr);
System.out.println(resArr[0]);
}
} catch (NumberFormatException e) {
e.printStackTrace();
} catch (IOException e) {
e.printStackTrace();
}
}
public static void f(int a, int b, String resStr, String[] resArr){
if(a==1 || b%a==0){
int val = b/a;
resStr += 1+"/"+val;
resArr[0] = resStr;
return ;
}
else{
int q1 = b/a;
int r1 = b%a;
int val1 = q1+1;
resStr += 1+"/"+val1+"+";
a = a - r1;
b = b*(q1+1);
f(a, b, resStr, resArr);
}
return;
}
}
HJ90 合法IP
描述
IPV4地址可以用一个32位无符号整数来表示，一般用点分方式来显示，点将IP地址分成4个部分，每个部分为8位，表示成一个无符号整数（因此正号不需要出现），如10.137.17.1，是我们非常熟悉的IP地址，一个IP地址串中没有空格出现（因为要表示成一个32数字）。
现在需要你用程序来判断IP是否合法。
注意本题有多组样例输入。
数据范围：数据组数：1\le t\le 18\1≤t≤18
进阶：时间复杂度：O(n)\O(n) ，空间复杂度：O(n)\O(n)
输入描述：
输入一个ip地址，保证不包含空格
输出描述：
返回判断的结果YES or NO
示例1
输入：
10.138.15.1
255.0.0.255
255.255.255.1000
复制
输出：
YES
YES
NO
描述
IPV4地址可以用一个32位无符号整数来表示，一般用点分方式来显示，点将IP地址分成4个部分，每个部分为8位，表示成一个无符号整数（因此正号不需要出现），如10.137.17.1，是我们非常熟悉的IP地址，一个IP地址串中没有空格出现（因为要表示成一个32数字）。
现在需要你用程序来判断IP是否合法。
注意本题有多组样例输入。
数据范围：数据组数：1\le t\le 18\1≤t≤18
进阶：时间复杂度：O(n)\O(n) ，空间复杂度：O(n)\O(n)
输入描述：
输入一个ip地址，保证不包含空格
输出描述：
返回判断的结果YES or NO
示例1
输入：
10.138.15.1
255.0.0.255
255.255.255.1000
复制
输出：
YES
YES
NO
HJ92 在字符串中找出连续最长的数字串
描述
输入一个字符串，返回其最长的数字子串，以及其长度。若有多个最长的数字子串，则将它们全部输出（按原字符串的相对位置）
本题含有多组样例输入。
数据范围：字符串长度 1 \le n \le 200 \1≤n≤200 ， 保证每组输入都至少含有一个数字
输入描述：
输入一个字符串。1<=len(字符串)<=200
输出描述：
输出字符串中最长的数字字符串和它的长度，中间用逗号间隔。如果有相同长度的串，则要一块儿输出（中间不要输出空格）。
示例1
输入：
abcd12345ed125ss123058789
a8a72a6a5yy98y65ee1r2
复制
输出：
123058789,9
729865,2
复制
说明：
样例一最长的数字子串为123058789，长度为9
样例二最长的数字子串有72,98,65，长度都为2
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
String str=null;
while((str=br.readLine())!=null){
char[] chars=str.toCharArray();
int max=0;
String res=null;
for(int i=0;i<chars.length;i++){
if(chars[i]>='0' && chars[i]<='9'){
int start=i;
while(i<chars.length && chars[i]>='0' && chars[i]<='9'){
i++;
}
int len=i-start;
if(len>max){
max=len;
res=str.substring(start,i);
}else if(len==max){
max=len;
res=res+str.substring(start,i);
}
}
}
System.out.println(res+","+max);
}
}
}
HJ103 Redraiment的走法
描述
Redraiment是走梅花桩的高手。Redraiment可以选择任意一个起点，从前到后，但只能从低处往高处的桩子走。他希望走的步数最多，你能替Redraiment研究他最多走的步数吗？
数据范围：每组数据长度满足 1 \le n \le 200 \1≤n≤200 ， 数据大小满足 1 \le val \le 350 \1≤val≤350
本题含有多组样例输入
输入描述：
输入多组数据，1组有2行，第1行先输入数组的个数，第2行再输入梅花桩的高度
输出描述：
一组输出一个结果
示例1
输入：
6
2 5 1 5 4 5
3
3 2 1
复制
输出：
3
1
复制
说明：
6个点的高度各为 2 5 1 5 4 5
如从第1格开始走,最多为3步, 2 4 5 ，下标分别是 1 5 6
从第2格开始走,最多只有1步,5
而从第3格开始走最多有3步,1 4 5， 下标分别是 3 5 6
从第5格开始走最多有2步,4 5， 下标分别是 5 6
所以这个结果是3。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
public class Main {
public static int LIS(int[] nums){
int len = nums.length;
if(len <= 1)
return 1;
int[] dp = new int[len];
for(int i = 0;i < len;++i){
dp[i] = 1;
}
for(int i = 1;i < len;++i){
for(int j = 0;j < i;++j){
if(nums[j] < nums[i]){
dp[i] = Math.max(dp[i],dp[j] + 1);
}
}
}
int max = 1;
for(int n : dp){
max = Math.max(max,n);
}
return max;
}
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String str;
while((str = br.readLine()) != null){
int len = Integer.parseInt(str);
int[] nums = new int[len];
String[] arr = br.readLine().split(" ");
for(int i = 0;i < len;++i){
nums[i] = Integer.parseInt(arr[i]);
}
System.out.println(LIS(nums));
}
}
}
HJ107 求解立方根
描述
计算一个浮点数的立方根，不使用库函数。
保留一位小数。
数据范围：|val| \le 20 \∣val∣≤20
输入描述：
待求解参数，为double类型（一个实数）
输出描述：
输入参数的立方根。保留一位小数。
示例1
输入：
216
复制
输出：
6.0
复制
示例2
输入：
2.7
复制
输出：
1.4
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main{
public static void main(String[]args) throws IOException {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
double input=Double.parseDouble(br.readLine());
boolean flag=false;
if(input<0) {
flag=true;
input=-input;
}
double distance=input;//误差或者增加的距离
double index=0;
double last=0;
while(true) {
last=index*index*index;
if(last>input) {
index-=distance;
distance/=10;
}
if(distance<0.001) {
break;
}
index+=distance;
}
double result=(int)((index+0.05)*10)/10.0;
if(flag) {
result=0-result;
}
System.out.println(result);
}
}
HJ16 购物单
描述
王强今天很开心，公司发给N元的年终奖。王强决定把年终奖用于购物，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的，下表就是一些主件与附件的例子：
主件 附件
电脑 打印机，扫描仪
书柜 图书
书桌 台灯，文具
工作椅 无
如果要买归类为附件的物品，必须先买该附件所属的主件，且每件物品只能购买一次。每个主件可以有 0 个、 1 个或 2 个附件。附件不再有从属于自己的附件。王强想买的东西很多，为了不超出预算，他把每件物品规定了一个重要度，分为 5 等：用整数 1 ~ 5 表示，第 5 等最重要。他还从因特网上查到了每件物品的价格（都是 10 元的整数倍）。他希望在不超过 N 元（可以等于 N 元）的前提下，使每件物品的价格与重要度的乘积的总和最大。
设第 j 件物品的价格为 v[j] ，重要度为 w[j] ，共选中了 k 件物品，编号依次为 j 1 ， j 2 ，……， j k ，则所求的总和为：
v[j 1 ]*w[j 1 ]+v[j 2 ]*w[j 2 ]+ … +v[j k ]*w[j k ] 。（其中 * 为乘号）
请你帮助王强设计一个满足要求的购物单。
输入描述：
输入的第 1 行，为两个正整数，用一个空格隔开：N m
（其中 N （ N<32000 ）表示总钱数， m （m <60 ）为希望购买物品的个数。）
从第 2 行到第 m+1 行，第 j 行给出了编号为 j-1 的物品的基本数据，每行有 3 个非负整数 v p q
（其中 v 表示该物品的价格（ v<10000 ）， p 表示该物品的重要度（ 1 ~ 5 ）， q 表示该物品是主件还是附件。如果 q=0 ，表示该物品为主件，如果 q>0 ，表示该物品为附件， q 是所属主件的编号）
输出描述：
输出文件只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值（ <200000 ）。
示例1
输入：
1000 5
800 2 0
400 5 1
300 5 1
400 3 0
500 2 0
复制
输出：
2200
复制
示例2
输入：
50 5
20 3 5
20 3 5
10 3 0
10 2 0
10 1 0
复制
输出：
130
复制
说明：
由第1行可知总钱数N为50以及希望购买的物品个数m为5；
第2和第3行的q为5，说明它们都是编号为5的物品的附件；
第4~6行的q都为0，说明它们都是主件，它们的编号依次为3~5；
所以物品的价格与重要度乘积的总和的最大值为10*1+20*3+20*3=130
import java.io.*;
class Good {
int v;
int p;
int q;
int a1=0;
int a2=0;
Good(int v,int p,int q){
this.v=v;
this.p=p;
this.q=q;
}
Good(){}
public void setV(int v){
this.v=v;
}
public void setP(int p){
this.p=p;
}
public void setQ(int q){
this.q=q;
}
public void setA1(int a1){
this.a1=a1;
}
public void setA2(int a2){
this.a2=a2;
}
}
public class Main{
public static int dw=100;//加快运行
public static void main(String[] args) throws IOException{
boolean flag=true;
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] strArr = br.readLine().split(" ");
int N = Integer.parseInt(strArr[0]);
int m = Integer.parseInt(strArr[1]);
Good[] A = new Good[m+1];
for(int i =1;i<=m;i++){
strArr = br.readLine().split(" ");
int v = Integer.parseInt(strArr[0]);
int p = Integer.parseInt(strArr[1]);
int q = Integer.parseInt(strArr[2]);
if(flag){
if(v%dw!=0){
flag=false;
dw=10;
for(int j=1;j<i;j++)
A[j].setV(A[j].v*10);
}
}
v=v/dw;
if(A[i]!=null){
A[i].setV(v);
A[i].setP(p);
A[i].setQ(q);
}else{
A[i]=new Good(v,p,q);
}
if(q>0){
if(A[q]==null){
A[q]=new Good();
}
if(A[q].a1==0){
A[q].setA1(i);
}else{
A[q].setA2(i);
}
}
}
N=N/dw;
dp(N,A);
}
public static void dp(int N,Good[] A){
int[][] dp = new int[N+1][A.length];
for(int i=1;i<A.length;i++){
int v=-1,v1=-1,v2=-1,v3=-1,tempdp=-1,tempdp1=-1,tempdp2=-1,tempdp3=-1;
v=A[i].v;
tempdp=v*A[i].p;
if(A[i].a1!=0&&A[i].a2!=0){
v3=v+A[A[i].a1].v+A[A[i].a2].v;
tempdp3=tempdp+A[A[i].a1].v*A[A[i].a1].p+A[A[i].a2].v*A[A[i].a2].p;
}
if(A[i].a1!=0){
v1 = v + A[A[i].a1].v;
tempdp1=tempdp+A[A[i].a1].v*A[A[i].a1].p;
}
if(A[i].a2!=0){
v2 = v + A[A[i].a2].v;
tempdp2=tempdp+A[A[i].a2].v*A[A[i].a2].p;
}
for(int j=1;j<N+1;j++){
if(A[i].q>0){
dp[j][i]=dp[j][i-1];
}else{
dp[j][i]=dp[j][i-1];
if(j>=v&&v!=-1) dp[j][i] = Math.max(dp[j][i],dp[j-v][i-1]+tempdp);
if(j>=v1&&v1!=-1) dp[j][i]=Math.max(dp[j][i],dp[j-v1][i-1]+tempdp1);
if(j>=v2&&v2!=-1) dp[j][i]=Math.max(dp[j][i],dp[j-v2][i-1]+tempdp2);
if(j>=v3&&v3!=-1) dp[j][i]=Math.max(dp[j][i],dp[j-v3][i-1]+tempdp3);
}
}
}
System.out.println(dp[N][A.length-1]*dw);
}
}
HJ17 坐标移动
描述
开发一个坐标计算工具， A表示向左移动，D表示向右移动，W表示向上移动，S表示向下移动。从（0,0）点开始移动，从输入字符串里面读取一些坐标，并将最终输入结果输出到输出文件里面。
输入：
合法坐标为A(或者D或者W或者S) + 数字（两位以内）
坐标之间以;分隔。
非法坐标点需要进行丢弃。如AA10; A1A; $%$; YAD; 等。
下面是一个简单的例子 如：
A10;S20;W10;D30;X;A1A;B10A11;;A10;
处理过程：
起点（0,0）
+ A10 = （-10,0）
+ S20 = (-10,-20)
+ W10 = (-10,-10)
+ D30 = (20,-10)
+ x = 无效
+ A1A = 无效
+ B10A11 = 无效
+ 一个空 不影响
+ A10 = (10,-10)
结果 （10， -10）
数据范围：每组输入的字符串长度满足 1\le n \le 10000 \1≤n≤10000 ，坐标保证满足 -2^{31} \le x,y \le 2^{31}-1 \−231≤x,y≤231−1 ，且数字部分仅含正数
输入描述：
一行字符串
输出描述：
最终坐标，以逗号分隔
示例1
输入：
A10;S20;W10;D30;X;A1A;B10A11;;A10;
复制
输出：
10,-10
复制
示例2
输入：
ABC;AKL;DA1;
复制
输出：
0,0
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String input;
while((input = br.readLine()) != null) {
int x = 0;
int y = 0;
String[] strs = input.split(";");
for(String str : strs) {
int v = 0;
if("".equals(str) || str.length() > 3) continue;
for(int i = 1; i < str.length(); i++) {
int t = str.charAt(i) - '0';
if(t >= 0 && t <= 9) {
if(i == 1 && str.length() != 2) v += t * 10;
else v += t;
} else {
v = 0;
break;
}
}
char c = str.charAt(0);
switch(c) {
case 'A':
x -= v;
break;
case 'D':
x += v;
break;
case 'W':
y += v;
break;
case 'S':
y -= v;
break;
default:
break;
}
}
System.out.println(x + "," + y);
}
}
}
HJ20 密码验证合格程序
描述
密码要求:
1.长度超过8位
2.包括大小写字母.数字.其它符号,以上四种至少三种
3.不能有长度大于2的不含公共元素的子串重复 （注：其他符号不含空格或换行）
数据范围：输入的字符串长度满足 1 \le n \le 100 \1≤n≤100
输入描述：
一组字符串。
输出描述：
如果符合要求输出：OK，否则输出NG
示例1
输入：
021Abc9000
021Abc9Abc1
021ABC9000
021$bc9000
复制
输出：
OK
NG
NG
OK
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
// 密码验证合格程序
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
String input = null;
StringBuffer sb = new StringBuffer();
while (null != (input = reader.readLine())) {
//设置四种类型数据初始为空即false，有数据了就更改为true
boolean[] flag = new boolean[4];
char[] chars = input.toCharArray();
// 第一个条件
if (chars.length < 9) {
sb.append("NG").append("\n");
continue;
}
// 第二个条件
for (int i = 0; i < chars.length; i++) {
if ('A' <= chars[i] && chars[i] <= 'Z') {
flag[0] = true;
} else if ('a' <= chars[i] && chars[i] <= 'z') {
flag[1] = true;
} else if ('0' <= chars[i] && chars[i] <= '9') {
flag[2] = true;
} else {
flag[3] = true;
}
}
int count = 0;
for (int i = 0; i < 4; i++) {
if (flag[i]) {
count++;
}
}
// 第三个条件
boolean sign = true; //不存在两个大于2的子串相同，即！（i=i+3,i+1=i+4,i+2=i+5）
for (int i = 0; i < chars.length - 5; i++) {
for (int j = i + 3; j < chars.length - 2; j++) {
if (chars[i] == chars[j] && chars[i + 1] == chars[j + 1] && chars[i + 2] == chars[j + 2]) {
sign = false;
}
}
} if (count >= 3 && sign) {
sb.append("OK").append("\n");
} else {
sb.append("NG").append("\n");
}
}
System.out.println(sb.toString());
}
}
