招商 目的地的最短步数
题目描述
考虑你从家出发步行去往一处目的地，该目的地恰好离你整数单位步长（大于等于1）。你只能朝向该目的地或者背向该目的地行走，而你行走的必须为单位步长的整数倍，且要求你第N次行走必须走N步。
请就给出目的地离你距离，判断你是否可以在有限步内到达该目的地。如果可以到达的话，请计算到达目的地的最短总步数(不能到达则输出-1)。
输入描述:
1个整数：目的地离你距离T
输出描述:
1个整数：最短总步数（进行了多少次行走）
2
3
思路是就是1~n的加或减是否可以得到x, 根据总结一定在一个范围内，一定会实现
package com.bupt.learn;
import java.util.Scanner;
public class Main {
/*
目的地的最短步数，第n次只能走n步，说白了就是在1~n间添加加减来达到目标值
总结已知，最大的步数是 2n -1, 最小的数是sqrt(2n)
*/
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int start = (int) Math.sqrt(2 * n);
int end = 2*n - 1;
boolean dfs = false;
for (int i=start;i<=end;i++) {
dfs = dfs(i, 1, n, 0);
if (dfs == true){
System.out.println(i);
break;
}
}
if (!dfs) {
System.out.println(-1);
}
}
private static boolean dfs(int i, int cur, int n, int sum) {
if(cur == i+1){
if (sum == n){
return true;
}
}else{
boolean f = dfs(i, cur + 1, n, sum + cur);
if (f == true){
return f;
}
final boolean f1 = dfs(i, cur + 1, n, sum - cur);
if (f1 == true){
return f1;
}
}
return false;
}
}
直接找规律解题即可
import java.util.Scanner;
public class Main {
/*
可以直接总结，n 个数和 sum - target 如果是偶数，加一，奇数加二
*/
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int ans = 0;
int sum = 0;
while (sum < n) {
ans++;
sum += ans;
}
sum -= n;
if ((sum & 1)==1){
if ((ans & 1) == 1) System.out.println(ans +2);
else {
System.out.println(ans + 1);
}
}else{
System.out.println(ans);
}
}
}
序列找数
从非负整数序列 0, 1, 2, ..., n中给出包含其中n个数的子序列，请找出未出现在该子序列中的那个数。
输入描述:
输入为n+1个非负整数，用空格分开。
其中：首个数字为非负整数序列的最大值n，后面n个数字为子序列中包含的数字。
输出描述:
输出为1个数字，即未出现在子序列中的那个数。
3 3 0 1
2
思路是，有的数将对应位置标志位负数-1，主要避免是0的情况， 不用处理最后的n, 如果前面没输出停止，直接输出即可；
import java.util.Scanner;
public class Main {
/*
思路是使用本地数的正负来表示是否存在
*/
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String line = in.nextLine();
String[] lines = line.split(" ");
int[] nums = new int[lines.length-1];
int n = Integer.parseInt(lines[0]);
for (int i =0;i<lines.length-1;i++){
nums[i] = Integer.parseInt(lines[i+1]);
}
for (int i=0;i<nums.length;i++){
int x = nums[i] < 0 ? -(nums[i]+1) : nums[i];
if (n == x){
}else {
nums[x] = -(nums[x]+1);
}
}
for (int i=0;i<=n;i++){
if (i == n || nums[i] >= 0){
System.out.println(i);
break;
}
}
}
}
小招猫跑步
小招喵喜欢在数轴上跑来跑去，假设它现在站在点n处，它只会3种走法，分别是：
1.数轴上向前走一步，即n=n+1
2.数轴上向后走一步,即n=n-1
3.数轴上使劲跳跃到当前点的两倍，即n=2*n
现在小招喵在原点，即n=0，它想去点x处，快帮小招喵算算最快的走法需要多少步？
输入描述:
小招喵想去的位置x
输出描述:
小招喵最少需要的步数
3
3
import java.util.Scanner;
public class Main {
/*
思路是使用本地数的正负来表示是否存在
*/
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
n = n < 0 ? -n : n;
if (n < 2){
System.out.println(n);
}else {
int[] dp = new int[n + 1];
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
if (i % 2 == 0) {
dp[i] = Math.min(dp[i - 1], dp[i / 2]) + 1;
} else {
// 注意奇数使用除法需要两步
dp[i] = Math.min(dp[i - 1], dp[(i + 1) / 2] + 1) + 1;
}
}
System.out.println(dp[n]);
}
}
}
不想出差的HR
按照卡中心校园招聘的要求，HR小招和小商需要从三个科室中（分别为A、B、C）抽派面试官去往不同城市。
两名HR按照以下规定轮流从任一科室选择面试官：每次至少选择一位，至多选择该科室剩余面试官数。最先选不到面试官的HR需要自己出差。
假设HR小招和小商都不想出差且每次选择都采取最优策略，如果是小招先选，写一个函数来判断她是否需要出差。如果不需要出差，请给出第一步的最优策略。
输入描述:
输入为三个正整数，分别代表三个科室的面试官人数，用英文逗号分隔
输出描述:
若小招需要出差，则输出：1；
若小招不需要出差，则输出：第一步选择的科室名称和选择人数，用英文逗号分隔
1,8,9
1
package com.bupt.learn;
import java.util.Scanner;
public class Main {
/*
nim 游戏
*/
static String[] room = {"A", "B" , "C"};
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
final String[] lines = in.nextLine().split(",");
int[] nums = new int[lines.length];
int ans = 0;
for (int i = 0;i < nums.length; i++){
nums[i] = Integer.parseInt(lines[i]);
ans ^= nums[i];
}
if (ans == 0){
System.out.println(1);
}else{
// 第一个先手的就是 异或后 结果小于 当前这个数的，说明没有取完
for (int i=0;i < nums.length; i++){
int num = ans ^ nums[i];
if (nums[i] - num >= 0){
System.out.println(room[i]+ "," + (nums[i] - num));
break;
}
}
}
}
}
年会抢玩偶游戏
某公司年会上，组织人员安排了一个小游戏来调节气氛。游戏规则如下：
N个人参与游戏，站成一排来抢工作人抛来的M个小玩偶。为了增加游戏的趣味和难度，规则规定，参与游戏的人抢到的礼物不能比左右两边的人多两个或以上，否则会受到一定的惩罚。游戏结束时拥有玩偶最多的人将获得一份大奖。
假设大家都想赢得这份大奖，请问站在第K个位置的小招在赢得游戏时，最多能拥有几个玩偶？
输入描述:
输入为用空格分隔的3个正整数，依次为：参与游戏人数N、玩偶数M、小招所在位置K
输出描述:
输出为1个正整数，代表小招最多能够拥有的玩偶数。若没有，则输出0。
2 2 2
1
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int m = in.nextInt();
int k = in.nextInt();
if (n == 0 || m == 0 || k <= 0 || k >n){
System.out.println(0);
}else{
for (int max = m;max>=0;max--){
int sum = max;
for (int i=1; i <= k - 1; i++){
sum += (max - i) > 0 ?(max - i):0;
}
for (int i=1;i<= n-k;i++){
sum += (max - i) > 0 ?(max - i):0;
}
if (sum <= m){
System.out.println(max);
break;
}
}
}
}
}
网友评论