案例1：接收用户输入的两个字符串（为九进制数），将两个字符串的相加的结果以九进制数输出。
功能分析
- 1.接受用户输入的两个数num1 num2 （字符串型）
- 2.设计按位相加函数实现逐位相加
- 3.将得到的结果以数字形式输出
逻辑分析
- 1.用prompt接受用户的输入（注意prompt接受为字符串型），将字符串以数组形式存入str1[] str2[]数组中 （string.split(“”)）
- 2.n进制数可以用遍历数组的方式对两个数组的对应位进行逐位相加操作，逢n进一，并将相加结果存入新数组str3[]中（本题n=9）
注意：相加操作应该从最后一个数组进行（因为防止后一位的进位影响前一位的进位）
注意：若当前位存储为小数点时应该将新数组中的对应位也应该为小数点
- 3.设置进位标志flag 标志是否有来自后一位的进位
注意：当数组第0位产生时，应在新数组str3前插入一个新的元素1
- 4.将得到的新数组str3用join(“”)方式变成数字形式
- 5.通过alert输出结果
详细代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
| <!DOCTYPE html>
<html>
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<meta http-equiv="X-UA-Compatible" content="ie=edge">
<title>Question1</title>
</head>
<body>
<script>
var num1 = prompt('请您输入第一个字符串：');
var num2 = prompt('请您输入第一个字符串：');
console.log(num1);
console.log(num2);
var str1 = num1.split("");;
var str2 = num2.split("");;
var i = ( num1.length > num2.length) ? num1.length : num2.length;
if(num1.length == num2.length){
}else if(i == num1.length){
do{
str2.unshift("0");
}while(str2.length < i)
}else{
do{
str1.unshift("0");
}while(str1.length < i)
}
function addString(x,y){
var str3 = [];
var j = x.length - 1;
var flag = 0;
for(var i = x.length - 1;i >= 0 ;i--){
if(x[i] == '.'){
str3[j] = '.';
j--;
}else{
str3[j] = Number(x[i]) + Number(y[i])+flag;
flag = 0;
if(str3[j] >= 9){
if(str3[j-1] != '.'){
if(j != 0){
str3[j] = str3[j] % 9;
flag = 1;
}else{
str3[j] = str3[j] % 9;
str3.unshift(1);
}
}
}
j--;
}
}
return str3;
}
var result = addString(str1,str2);
console.log(result.join(''));
alert('您输入的两个字符串相加后的和为：'+ result.join(''));
</script>
</body>
</html>
|
案例2 最小数位和
【题目描述】
定义S(n)，表示n在十进制下的各位数字和。
现在给定一个x,请你求出最小正整数n，满足x≤S(n).
【输入描述】
第一行数据组数T，对于每组数据，一行一个数字x。
1≤x≤10^5,1≤T≤10
【输出描述】
对于每组数据，一行一个整数表示最小的n。
【示例】
示例1：
输入：
2
7
9
输出：
7
9
【解决思路及要点】
- 【贪心】n要尽可能小，说明位数要尽可能少，在十进制中9最大，所以对x除9，就可以得到n中9的个数，n的最高位就是余数。（满足n最高位最小，位数最小）
- 可以直接从最高位开始一位一位的输出，先输出余数，再输出x/9个9不需要再整体转换为数字。
【解决代码】
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| public class Solution1 {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int T=sc.nextInt();
while(T-->0){
int x=sc.nextInt();
solve(x);
}
}
public static void solve(int x){
//余数做最高位
if(x%9>0){
System.out.print(x%9);
}
x-=x%9;
//x/9就是n中9的个数
for(int i=1;i<=x/9;i++){
System.out.print("9");
}
System.out.print("\n");
}
}
|
案例3 吃葡萄
【题目描述】
有三种葡萄，每种分别有a,b,c颗。有三个人，第一个人只吃第1,2种葡萄，第二个人只吃第2,3种葡萄，第三个人只吃第1,3种葡萄。
适当安排三个人使得吃完所有的葡萄,并且三个人中吃的最多的那个人吃得尽量少。
【输入描述】
第一行数字T，表示数据组数。
接下来T行，每行三个数a,b,c
1≤a,b,c≤10^18,1≤T≤10
【输出描述】
对于每组数据，输出一行一个数字表示三个人中吃的最多的那个人吃的数量。
【示例】
示例1：
输入：
2
1 2 3
1 2 6
输出：
2
3
【解决思路及要点】
- 如果两种较少葡萄的和比葡萄最多的一半要多，那么可以实现平分。【此时三人平分能够使得吃的最多的那个人吃得尽量少】
- 如果两种较少葡萄的和比葡萄最多的一半要少，那么结果是最多葡萄的一半。
- 注意要使用向上取整。（一颗葡萄也要单独吃一次）
- 也可以看成是三个人分别站在三角形的顶点，假设三角形两个短边是a,b，长边是c。则，若两短边之和大于等于长边的一半，可实现总数平分；反之，则结果为长边的一半。
【解决代码】
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| public class Solution2 {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int T=sc.nextInt();
while(T-->0){
long a,b,c;
a=sc.nextLong();
b=sc.nextLong();
c=sc.nextLong();
System.out.println(solve(a,b,c));
}
}
public static long solve(long a,long b,long c){
long maxx=Math.max(Math.max(a,b),c);
long minn=Math.min(Math.min(a,b),c);
long mid=a+b+c-maxx-minn;
if(minn+mid>=maxx/2){
return up(a+b+c,3);
}else{
return up(maxx,2);
}
}
//除法向上取整
private static long up(long a,long b){
return a%b>0?a/b+1:a/b;
}
}
|
案例4 圆环切割
【题目描述】
小易有n个数字排成一个环，你能否将它们分成连续的两个部分(即在环上必须连续)，使得两部分的和相等？
【输入描述】
第一行数据组数T，对于每组数据
第一行数字n，表示数字个数
接下来一行n个数，按顺序给出环上的数字。
2≤n≤100000,1≤Ai≤10^9
【输出描述】
对于每组数据，一行输出YES/NO
【示例】
示例1：
输入：
1
6
1 2 3 4 5 6
输出：
NO
示例2：
输入：
1
4
4 4 5 3
输出：
YES
【解决思路及要点】
- 维护一个前缀和数组，将每个前缀和与圆环和的一半做差，如果存在一个前缀和和这个差相等，那么就可以分割。【具体的原理自己在脑海中构造个圆环想一下】这里利用的是圆环起点可变的特性。
【解决代码】
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| public class Solution3 {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int T=sc.nextInt();
while(T-->0){
int n=sc.nextInt();
int[] pre=new int[n];
for(int i=0;i<n;i++){
int x=sc.nextInt();
pre[i]=(i>0)?pre[i-1]+x:x;
}
if(solve(pre)){
System.out.println("YES");
}else{
System.out.println("NO");
}
}
}
public static boolean solve(int[] pre){
int n=pre.length;
if((pre[n-1]&1)>0){
return false;
}
Set<Integer> set=new HashSet<>();
for(int i=0;i<n;i++){
int s=pre[i]-pre[n-1]/2;
if(set.contains(s)){
return true;
}
set.add(pre[i]);
}
return false;
}
}
|
【题目剖析】
- 这题思维性不是那么强，算是一个中等偏下的题，需要对前缀和应用比较熟悉。
- 这个题一步一步做，方法应该还有很多，总体而言不是很难。
案例5：跳柱子
【题目描述】
小易有n根柱子，第i根柱子的高度为hi。一开始小易站在第一根柱子上。小易能从第i根柱子跳到第j根柱子，当且仅当hj≤hi且1≤j−i≤k。其中k为指定的一个数字。
另外小易拥有一次释放超能力的机会。这个超能力能让小易从柱子i跳到任意满足1≤j−i≤k的柱子j而无视柱子高度的限制。
现在小易想知道，小易是否能到达第n根柱子。
【输入描述】
第一行数据组数T
对于每组数据，第一行数字n,k接下来一行n个数字表示hi。
1≤n≤1000,1≤hi≤10^9,1≤T≤10,1≤k≤n
【输出描述】
对于每组数据，输出YES或NO
【示例】
示例1：
输入：
1
5 3
6 2 4 3 8
输出：
YES
示例2：
输入：
1
5 2
1 8 2 3 4
输出：
NO
【解决思路及要点】
- 明显可以使用dp。
- dp[i][0]表示不使用超能力的情况下是否能到达柱子。
- dp[i][1]表示使用超能力的情况下是否能到达柱子。
- 对每个柱子，枚举前面的k个柱子，并更新dp即可。
- 具体细节见代码。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
| public class Solution4 {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int T=sc.nextInt();
while(T-->0){
int n=sc.nextInt();
int k=sc.nextInt();
int[] height=new int[n];
for(int i=0;i<n;i++){
height[i]=sc.nextInt();
}
if(solve(height,k)){
System.out.println("YES");
}else{
System.out.println("NO");
}
}
}
public static boolean solve(int[] height,int k){
int n=height.length;
boolean[][] dp=new boolean[n][2];
dp[0][0]=dp[0][1]=true;
for(int i=0;i<n;i++){
for(int j=i-1;j>=0 && j>=i-k;j--){
if(dp[j][0]){
dp[j][1]=true;
if(height[j]>=height[i]){
dp[i][0]=true;
}
}
if(dp[j][1]){
if(height[j]>=height[i]){
dp[i][1]=true;
}
}
}
}
return dp[n-1][1];
}
}
|
【题目剖析】
- 算是比较经典的dp，对dp熟悉的话，可以很快的做出。
- 整体来说，这题不是很难。
- 应该可以在比较快的时间内做出来。
案例6 乘积
【题目描述】
小易给定你一个长度为n的正整数序列Ai，你每次可以使用1的代价将某个数加一或者减一，你希望用最少的代价使得所有数的乘积等于B，求最小代价（操作结束后每个数也必须是正整数）。
【输入描述】
第一行数字n, B,表示序列长度和目标乘积。
接下来一行n个正整数表示初始序列。
1≤n≤10^3 , 1≤B≤ 10^5，1≤Ai≤ 10^5.
【输出描述】
一行一个数字表示答案
【示例】
示例1：
输入：
5 12
1 3 9 2 6
输出：
10
说明：
把3变为1需要2的代价，把9变为1需要8的代价，总代价为10。
示例2：
输入：
3 15
3 8 7
输出：
9
说明：
把8变为5需要3的代价，把7变为1需要6的代价，总代价为9。
【解决思路及要点】
- dp解决，dp[i][j]表示表示让前i个数字乘积为j的最小代价。
- 需要大量用到数的因子，故生成一个从1-B的所有数的因子的集合。
- 具体转移方程和其它细节在注释中。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
| public class Solution5 {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int B=sc.nextInt();
int[] a=new int[n+1];
for(int i=1;i<=n;i++){
a[i]=sc.nextInt();
}
System.out.println(solve(a,B));
}
public static int solve(int[] a,int B){
int n=a.length-1;
List<List<Integer>> v=new ArrayList<>();
for(int i=0;i<=B;i++){
v.add(new ArrayList<>());
}
for(int i=1;i<=B;i++){
for(int j=i;j<=B;j+=i){
v.get(j).add(i);
}
}
int m=v.get(B).size();
int[] num=new int[B+1];
for(int i=0;i<m;i++){
num[v.get(B).get(i)]=i;
}
int[][] dp=new int[n+1][m];
for(int i=1;i<m;i++){
dp[0][i]= (int) 1e9;
}
for(int i=1;i<=n;i++){
for(int j=0;j<m;j++){
dp[i][j]= (int) 1e9;
for(int k=0;k<v.get(v.get(B).get(j)).size();k++){
dp[i][j]=Math.min(dp[i][j],dp[i-1][num[v.get(v.get(B).get(j)).get(k)]]
+Math.abs(a[i]-v.get(B).get(j)/v.get(v.get(B).get(j)).get(k)));
}
}
}
return dp[n][m-1];
}
}
|
【题目剖析】
- 这个题开始我是完全没有做出来，想到dp的思路，但始终找不到转移的点。
- 这个题感觉还是比较难的dp了，估计在两小时内做出的人比较少，这场比试真正拉开算法能力强的人与普通人差距的题目。
- 算是一个难度dp了。
