編碼
題目描述
假定一種編碼的編碼范圍是a ~ y的25個(gè)字母，從1位到4位的編碼，如果我們把該編碼按字典序排序，形成一個(gè)數(shù)組如下： a, aa, aaa, aaaa, aaab, aaac, … …, b, ba, baa, baaa, baab, baac … …, yyyw, yyyx, yyyy 其中a的Index為0，aa的Index為1，aaa的Index為2，以此類推。 編寫一個(gè)函數(shù)，輸入是任意一個(gè)編碼，輸出這個(gè)編碼對(duì)應(yīng)的Index.
輸入描述:
輸入一個(gè)待編碼的字符串,字符串長(zhǎng)度小于等于100.
輸出描述：
輸出這個(gè)編碼的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; // 記錄節(jié)點(diǎn)序號(hào)
List<DicNode> nodes; // 子節(jié)點(diǎn)list
public DicNode(int index, List<DicNode> nodes) {
this.index = index;
this.nodes = nodes;
}
}
}
復(fù)雜度太大了，因?yàn)樵诮⒆值錁涞臅r(shí)候太麻煩了...
只能換一種方法...
我們來分析樣例的輸入: baca
分析過程:
判斷第一位為b，我們可以知道他前面有: a, aX, aXX, aXXX
再判斷第二位a,他前面有：b，木有了...
第三位c, 他前面有ba, baM, baMX, 其中M為a或b...
按照這個(gè)分析思路我們可以先針對(duì)樣例輸入的baca做一次完整的分析:
算法實(shí)現(xiàn)
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);
}
}
素?cái)?shù)對(duì)
題目描述
給定一個(gè)正整數(shù)，編寫程序計(jì)算有多少對(duì)質(zhì)數(shù)的和等于輸入的這個(gè)正整數(shù)，并輸出結(jié)果。輸入值小于1000。
如，輸入為10, 程序應(yīng)該輸出結(jié)果為2。（共有兩對(duì)質(zhì)數(shù)的和為10,分別為(5,5),(3,7)）
輸入描述:
輸入包括一個(gè)整數(shù)n,(3 ≤ n < 1000)
輸出描述：
輸出對(duì)數(shù)
示例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;
// 這里是判斷質(zhì)數(shù)的重點(diǎn)
for (int i = 3; i <= Math.sqrt(num); i += 2) {
if (num % i == 0) return false;
}
return true;
}
}
游戲任務(wù)標(biāo)記
題目描述
游戲里面有很多各式各樣的任務(wù)，其中有一種任務(wù)玩家只能做一次，這類任務(wù)一共有1024個(gè)，任務(wù)ID范圍[1,1024]。請(qǐng)用32個(gè)unsigned int類型來記錄著1024個(gè)任務(wù)是否已經(jīng)完成。初始狀態(tài)都是未完成。 輸入兩個(gè)參數(shù)，都是任務(wù)ID，需要設(shè)置第一個(gè)ID的任務(wù)為已經(jīng)完成；并檢查第二個(gè)ID的任務(wù)是否已經(jīng)完成。 輸出一個(gè)參數(shù)，如果第二個(gè)ID的任務(wù)已經(jīng)完成輸出1，如果未完成輸出0。如果第一或第二個(gè)ID不在[1,1024]范圍，則輸出-1。
輸入描述:
輸入包括一行,兩個(gè)整數(shù)表示人物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常用于將二維的經(jīng)緯度轉(zhuǎn)換為字符串，分為兩步：第一步是經(jīng)緯度的二進(jìn)制編碼，第二步是base32轉(zhuǎn)碼。
此題考察緯度的二進(jìn)制編碼：算法對(duì)緯度[-90, 90]通過二分法進(jìn)行無(wú)限逼近（取決于所需精度，本題精度為6）。注意，本題進(jìn)行二分法逼近過程中只采用向下取整來進(jìn)行二分，針對(duì)二分中間值屬于右區(qū)間。算法舉例如下： 針對(duì)緯度為80進(jìn)行二進(jìn)制編碼過程：
- 區(qū)間[-90, 90]進(jìn)行二分為[-90, 0),[0, 90]，成為左右區(qū)間，可以確定80為右區(qū)間，標(biāo)記為1；
- 針對(duì)上一步的右區(qū)間[0, 90]進(jìn)行二分為[0, 45),[45, 90]，可以確定80是右區(qū)間，標(biāo)記為1；
- 針對(duì)[45, 90]進(jìn)行二分為[45, 67),[67,90],可以確定80為右區(qū)間，標(biāo)記為1；
- 針對(duì)[67,90]進(jìn)行二分為[67, 78),[78,90]，可以確定80為右區(qū)間，標(biāo)記為1；
- 針對(duì)[78, 90]進(jìn)行二分為[78, 84),[84, 90]，可以確定80為左區(qū)間，標(biāo)記為0；
- 針對(duì)[78, 84)進(jìn)行二分為[78, 81), [81, 84)，可以確定80為左區(qū)間，標(biāo)記為0；
輸入描述:
輸入包括一個(gè)整數(shù)n,(-90 ≤ n ≤ 90)
輸出描述:
輸出二進(jìn)制編碼
示例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());
}
}
