编码
题目描述
假定一种编码的编码范围是a ~ y的25个字母，从1位到4位的编码，如果我们把该编码按字典序排序，形成一个数组如下： a, aa, aaa, aaaa, aaab, aaac, … …, b, ba, baa, baaa, baab, baac … …, yyyw, yyyx, yyyy 其中a的Index为0，aa的Index为1，aaa的Index为2，以此类推。 编写一个函数，输入是任意一个编码，输出这个编码对应的Index.
输入描述:
输入一个待编码的字符串,字符串长度小于等于100.
输出描述：
输出这个编码的index
示例1
输入
baca输出
16331
先来看哥的字典树大法:
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main {
private static int index = -1;
public static void main(String[] args) {
List<DicNode> dicNodes = new ArrayList<DicNode>(25);
DicNode root = new DicNode(index, dicNodes);
buildTree(root, 0);
Scanner sin = new Scanner(System.in);
String str = sin.nextLine();
int len = str.length();
DicNode node = root;
for (int i = 0; i < len; i++) {
int cur = str.charAt(i) - 'a';
node = node.nodes.get(cur);
}
System.out.println(node.index);
}
private static void buildTree(DicNode root, int degree) {
if (degree == 4) return;
for (int i = 0; i < 25; i++) {
index++;
DicNode node = new DicNode(index, new ArrayList<DicNode>(25));
root.nodes.add(node);
buildTree(node, degree + 1);
}
}
private static class DicNode {
private int index; // 记录节点序号
List<DicNode> nodes; // 子节点list
public DicNode(int index, List<DicNode> nodes) {
this.index = index;
this.nodes = nodes;
}
}
}
复杂度太大了，因为在建立字典树的时候太麻烦了...
只能换一种方法...
我们来分析样例的输入: baca
分析过程:
判断第一位为b，我们可以知道他前面有: a, aX, aXX, aXXX
再判断第二位a,他前面有：b，木有了...
第三位c, 他前面有ba, baM, baMX, 其中M为a或b...
按照这个分析思路我们可以先针对样例输入的baca做一次完整的分析:
算法实现
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String str = sc.nextLine();
int len = str.length();
int result = 0; // 输出的index
for (int i = 0; i < len; i++) {
int num = str.charAt(i) - 'a';
int sum = 0;
int times = 4 - i;
for (int j = 0; j < times; j++) {
sum += Math.pow(25, j);
}
result += (i == 0 ? num * sum : num * sum + 1);
}
System.out.println(result);
}
}
素数对
题目描述
给定一个正整数，编写程序计算有多少对质数的和等于输入的这个正整数，并输出结果。输入值小于1000。
如，输入为10, 程序应该输出结果为2。（共有两对质数的和为10,分别为(5,5),(3,7)）
输入描述:
输入包括一个整数n,(3 ≤ n < 1000)
输出描述：
输出对数
示例1
输入
10
输
2
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int num = sc.nextInt();
int mid = num / 2;
int sum = 0;
for (int a = mid; a > 2; a--) {
int b = num - a;
if (isPrime(a) && isPrime(b)) {
sum++;
}
}
System.out.println(sum);
}
public static boolean isPrime(int num) {
if (num == 2) return true;
if (num < 2 || num % 2 == 0) return false;
// 这里是判断质数的重点
for (int i = 3; i <= Math.sqrt(num); i += 2) {
if (num % i == 0) return false;
}
return true;
}
}
游戏任务标记
题目描述
游戏里面有很多各式各样的任务，其中有一种任务玩家只能做一次，这类任务一共有1024个，任务ID范围[1,1024]。请用32个unsigned int类型来记录着1024个任务是否已经完成。初始状态都是未完成。 输入两个参数，都是任务ID，需要设置第一个ID的任务为已经完成；并检查第二个ID的任务是否已经完成。 输出一个参数，如果第二个ID的任务已经完成输出1，如果未完成输出0。如果第一或第二个ID不在[1,1024]范围，则输出-1。
输入描述:
输入包括一行,两个整数表示人物ID.
输出描述:
输出是否完成
示例1
输入
1024 1024
输出
1
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sin = new Scanner(System.in);
int a = sin.nextInt();
int b = sin.nextInt();
if (a < 1 || b < 1 || a > 1024 || b > 1024) {
System.out.println(-1);
} else {
System.out.println(a == b ? 1 : 0);
}
}
}
geohash编码
题目描述
geohash编码：geohash常用于将二维的经纬度转换为字符串，分为两步：第一步是经纬度的二进制编码，第二步是base32转码。
此题考察纬度的二进制编码：算法对纬度[-90, 90]通过二分法进行无限逼近（取决于所需精度，本题精度为6）。注意，本题进行二分法逼近过程中只采用向下取整来进行二分，针对二分中间值属于右区间。算法举例如下： 针对纬度为80进行二进制编码过程：
- 区间[-90, 90]进行二分为[-90, 0),[0, 90]，成为左右区间，可以确定80为右区间，标记为1；
- 针对上一步的右区间[0, 90]进行二分为[0, 45),[45, 90]，可以确定80是右区间，标记为1；
- 针对[45, 90]进行二分为[45, 67),[67,90],可以确定80为右区间，标记为1；
- 针对[67,90]进行二分为[67, 78),[78,90]，可以确定80为右区间，标记为1；
- 针对[78, 90]进行二分为[78, 84),[84, 90]，可以确定80为左区间，标记为0；
- 针对[78, 84)进行二分为[78, 81), [81, 84)，可以确定80为左区间，标记为0；
输入描述:
输入包括一个整数n,(-90 ≤ n ≤ 90)
输出描述:
输出二进制编码
示例1
输入
80
输出
111100
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sin = new Scanner(System.in);
int input = sin.nextInt();
int min = -90, max = 90, mid = 0;
int count = 0;
int code;
StringBuilder builder = new StringBuilder();
while (true) {
if (input >= mid) {
code = 1;
if (max <= mid) {
builder.append(code);
break;
}
min = mid;
mid = (mid + max) / 2;
} else {
code = 0;
if (mid <= min) {
builder.append(code);
break;
}
max = mid;
mid = (mid + min) / 2;
}
builder.append(code);
if (++count == 6) {
break;
}
}
System.out.println(builder.toString());
}
}
