最少数量货物装箱问题
题目描述
有重量分别为3，5，7公斤的三种货物，和一个载重量为X公斤的箱子（不考虑体积等其它因素，只计算重量）
需要向箱子内装满X公斤的货物，要求使用的货物个数尽可能少（三种货物数量无限）
输入描述:
输入箱子载重量X(1 <= X <= 10000)，一个整数。
输出描述:
如果无法装满，输出 -1。
如果可以装满，输出使用货物的总个数。
4
-1
import java.util.*;
public class Main {
// 完全背包问题，只是要求必须装满
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int x = in.nextInt();
if (x < 8){
if(x == 3 || x == 5 || x == 7){
System.out.println(1);
}else if (x == 6){
System.out.println(2);
}else{
System.out.println(-1);
}
}else {
// 使用贪心法
int[] dp = new int[x + 1];
// 求最小 先赋值最大
for (int i = 0; i <= x; i++) {
dp[i] = x + 1;
}
dp[3] = 1;
dp[5] = 1;
dp[7] = 1;
dp[6] = 2;
for (int i = 8; i < x + 1; i++) {
dp[i] = Math.min(dp[i - 3], Math.min(dp[i - 5], dp[i - 7]))+1;
}
System.out.println(dp[x]);
}
}
}
回文子串的个数
题目描述
给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。
("回文串”是一个正读和反读都一样的字符串，比如“level”或者“noon”等等就是回文串。)
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被计为是不同的子串。
可用C++,Java,C#实现相关代码逻辑
输入描述:
输入一个字符串S 例如“aabcb”(1 <= |S| <= 50), |S|表示字符串S的长度。
输出描述:
符合条件的字符串有"a","a","aa","b","c","b","bcb"
所以答案:7
import java.util.*;
public class Main {
// 完全字符串dp问题，
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String line = in.nextLine();
boolean[][] dp = new boolean[line.length()][line.length()];
int count = line.length();
for (int i=0;i<line.length();i++){
dp[i][i] = true;
}
// 这里一定要注意这里要逆序，否则，dp[i][j] = dp[i+1][j-1];，dp[i+1][] 还没计算
for (int i=line.length()-2;i>=0;i--){
for (int j=i+1;j<line.length();j++){
if (j - i <=1 && line.charAt(i) == line.charAt(j)){
dp[i][j] = true;
}else if (line.charAt(i) == line.charAt(j)){
dp[i][j] = dp[i+1][j-1];
}
if (dp[i][j]){
count++;
}
}
}
System.out.println(count);
}
}
字符串压缩
对字符串进行RLE压缩，将相邻的相同字符，用计数值和字符值来代替。例如：aaabccccccddeee，则可用3a1b6c2d3e来代替。
输入描述:
输入为a-z,A-Z的字符串，且字符串不为空，如aaabccccccddeee
输出描述:
压缩后的字符串，如3a1b6c2d3e
import java.util.*;
public class Main {
// 完全字符串dp问题，
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 字符串压缩，采用，顺序遍历的思路
String line = in.nextLine();
char[] lineChar = line.toCharArray();
int left = 0;
char pre = line.charAt(0);
StringBuilder res = new StringBuilder();
for(int i=1;i<lineChar.length;i++){
if (lineChar[i] != pre){
res.append(i-left);
res.append(pre);
pre = lineChar[i];
left = i;
}
}
res.append(lineChar.length-left);
res.append(pre);
System.out.println(res.toString());
}
}
解析加减法运算
解析加减法运算
如：
输入字符串："1+2+3" 输出："6"
输入字符串："1+2-3" 输出："0"
输入字符串："-1+2+3" 输出："4"
输入字符串："1" 输出："1"
输入字符串："-1" 输出："-1"
已知条件：输入的运算都是整数运算，且只有加减运算
要求：输出为String类型，不能使用内建的eval()函数
输入描述:
输入字符串："1+2+3"
输出描述:
输出："6"
import java.util.*;
public class Main {
// 解析加减法，转换为只有加法，减法转为负数即可
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String line = in.nextLine();
int sum = 0;
int i = 0;
while (i < line.length()){
int num = 0;int flag = 1;
if (line.charAt(i) == '-' || line.charAt(i) == '+'){
if(line.charAt(i) == '-')
flag = -1;
i++;
}
while (i < line.length() && line.charAt(i) >= '0' && line.charAt(i) <= '9'){
num = num * 10 + (line.charAt(i) - '0');
i++;
}
sum += flag * num;
}
System.out.println(sum);
}
}
求连续子数组的最大和
题目描述
一个非空整数数组，选择其中的两个位置，使得两个位置之间的数和最大。
如果最大的和为正数，则输出这个数；如果最大的和为负数或0，则输出0
输入描述:
3,-5,7,-2,8
输出描述:
13
import java.util.*;
public class Main {
// dp 连续子数组最大和
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String line = in.nextLine();
String[] numStrs = line.split(",");
int[] nums = new int[numStrs.length];
for (int i=0;i<numStrs.length;i++){
nums[i] = Integer.parseInt(numStrs[i]);
}
int curMax = 0;
int max = Integer.MIN_VALUE;
for (int x:nums){
if (curMax <= 0){
curMax = x;
}else {
curMax += x;
}
max = Math.max(max,curMax);
}
if (max <= 0){
System.out.println(0);
}else {
System.out.println(max);
}
}
}
网友评论