爱吃猫粮的小招猫
小招喵喜欢吃喵粮。这里有 N 堆喵粮，第 i 堆中有 p[i] 粒喵粮。喵主人离开了，将在 H 小时后回来。
小招喵可以决定她吃喵粮的速度 K （单位：粒/小时）。每个小时，她将会选择一堆喵粮，从中吃掉 K 粒。如果这堆喵粮少于 K 粒，她将吃掉这堆的所有喵粮，然后这一小时内不会再吃更多的喵粮。
小招喵喜欢慢慢吃，但仍然想在喵主人回来前吃掉所有的喵粮。
返回她可以在 H 小时内吃掉所有喵粮的最小速度 K（K 为整数）。
输入描述:
第一行输入为喵粮数组，以空格分隔的N个整数
第二行输入为H小时数
3 6 7 11
8
4
思路是，求出总和 最慢的情况下吃完
总和除以目标的时间h, 这是在理想情况下需要的速度会小一点，考虑到在不够吃的情况下，可以吃其他堆， 那么最大的情况一定是最大堆的量，这样可以保证一次可以吃一堆，然后采用二分法进行尝试吃，找到第一个可以吃完，而下一个不能吃完，就是我们要找的答案
import java.util.*;
public class Main {
// 使用二分法进行查找
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String[] numStr = in.nextLine().split(" ");
int h = in.nextInt();
int[] nums = new int[numStr.length];
int total = 0;
int max = 0;
for (int i=0;i<nums.length;i++){
nums[i] = Integer.parseInt(numStr[i]);
total += nums[i];
max = Math.max(nums[i],max);
}
int min = total % h == 0 ? total / h : total / h + 1;
int left = min; int right = max;
while (left < right){
int mid = left + (right - left)/2;
if (getTime(nums,mid) > h){
left = mid + 1;
}else{
right = mid;
}
}
System.out.println(left);
}
private static int getTime(int[] nums, int min) {
int count = 0;
for (int x:nums){
if(x >= min) {
count += x % min == 0 ? x / min : x / min + 1;
}else{
count += 1;
}
}
return count;
}
}
X 游戏
我们称一个数 X 为好数, 如果它的每位数字逐个地被旋转 180 度后，我们仍可以得到一个有效的，且和 X 不同的数。要求每位数字都要被旋转。
如果一个数的每位数字被旋转以后仍然还是一个数字， 则这个数是有效的。0, 1, 和 8 被旋转后仍然是它们自己；2 和 5 可以互相旋转成对方；6 和 9 同理，除了这些以外其他的数字旋转以后都不再是有效的数字。
现在我们有一个正整数 N, 计算从 1 到 N 中有多少个数 X 是好数？
输入描述:
输入正整数N
输出描述:
输出1到N中好数个数
10
4
思路直接暴力破解，优化的算法考察数学归纳，在时间不足时直接先暴力解决
import java.util.*;
public class Main {
// 先进行暴力
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int count = 0;
for (int i=2;i<=n;i++){
String line = String.valueOf(i);
int i3 = line.indexOf("3");
int i4 = line.indexOf("4");
int i7 = line.indexOf("7");
if (i3 * i4 * i7 == -1 && (line.contains("2") || line.contains("5") || line.contains("6") || line.contains("9"))){
count++;
}
}
System.out.println(count);
}
}
跳格子游戏
假设你正在玩跳格子（所有格子排成一个纵列）游戏。需要 跳完n 个格子你才能抵达终点。
每次你可以跳 1 或 2 个格子。你有多少种不同的方法可以到达终点呢？
注意：给定 n 是一个正整数。
输入描述:
格子数n
输出描述:
跳完n个格子到达终点的方法
2
2
可以不使用递归，减少迭代，
import java.util.*;
public class Main {
// 先进行暴力
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
System.out.println(f(n));
}
public static int f(int n){
if (n < 3){
return n;
}
return f(n-1) + f(n-2);
}
}
糖果分配
假设你是一位很有爱的幼儿园老师，想要给幼儿园的小朋友们一些小糖果。但是，每个孩子最多只能给一块糖果。对每个孩子 i ，都有一个胃口值 gi ，这是能让孩子们满足胃口的糖果的最小尺寸；并且每块糖果 j ，都有一个尺寸 sj 。如果 sj >= gi ，我们可以将这个糖果 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。
注意：
你可以假设胃口值为正。
一个小朋友最多只能拥有一块糖果。
输入描述:
第一行输入每个孩子的胃口值
第二行输入每个糖果的尺寸
孩子数和糖果数不超过1000
输出描述:
能满足孩子数量的最大值
1 2 3
1 1
1
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String[] kids = in.nextLine().split(" ");
String[] candy = in.nextLine().split(" ");
// 糖果分配使用贪心算法
int[] kidWants = new int[kids.length];
for (int i=0;i<kids.length;i++){
kidWants[i] = Integer.parseInt(kids[i]);
}
int[] candySizes = new int[candy.length];
for (int i=0;i<candy.length;i++){
candySizes[i] = Integer.parseInt(candy[i]);
}
// 贪心思路是，每一个最大糖果给最大需求的小孩
int pos = candySizes.length-1;
int i = kidWants.length - 1;
Arrays.sort(kidWants);
Arrays.sort(candySizes);
int ans = 0;
while (pos >= 0 && i >= 0){
if (candySizes[pos] >= kidWants[i]){
ans++;
pos--;
i--;
}else { // 不能满足当前
i--;
}
}
System.out.println(ans);
}
}
员工考勤记录
给定一个字符串来代表一个员工的考勤纪录，这个纪录仅包含以下两个字符：
'A' : Absent，缺勤
'P' : Present，到场
如果一个员工的考勤纪录中不超过两个'A'(缺勤),那么这个员工会被奖赏。
如果你作为一个员工，想在连续N天的考勤周期中获得奖赏，请问有多少种考勤的组合能够满足要求
输入描述:
考勤周期的天数N（正整数）
输出描述:
这N天里能获得奖赏的考勤组合数
3
7
思路 ： 全勤 1 种1情况， 缺一个勤 n, 缺两个勤 Cn2 = n(n-1)/2;
import java.util.*;
public class Main {
// 先进行暴力
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int ans = n;
int k = n * (n-1) /2;
System.out.println(ans + k + 1);
}
}
网友评论