二进制数
题目链接
思路解析
直接用javaInteger内置的toBinaryString函数就可以
AC代码
import java.util.Scanner;
public class Main{
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
Integer string = scanner.nextInt();
System.out.println(Integer.toBinaryString(string));
}
}哈夫曼树
题目链接
思路解析
求哈夫曼树的带权路径长度 = 所有叶子节点的带权路径长度之和。
每个节点的带权路径长度 = 节点的权值 * 路径长度（从根到该节点的分支数）
如果我们按照上面思路，就必须要构建完整的哈尔曼树了，还要计算每个节点的层数用层次遍历，很麻烦。
树的带权路径长度 = 所有非叶子节点的权值之和。
所以问题关键变成了：怎么计算所有非叶子节点的权值。
构建哈尔曼树，每次都是拿两个权值最小节点合并成一个非叶子节点（非叶子节点的权值是前面两个节点权值之和）。所以可以使用java的PriorityQueue优先队列。加入到优先队列，虽然队列内部顺序不清楚，但是每次出队（队首）的元素都是最小的。
AC代码
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
PriorityQueue<Integer> list = new PriorityQueue<Integer>();
for (int i = 0; i < n; i++) {
list.add(scanner.nextInt());
}
int result = 0;
while(list.size() > 1){
int a = list.poll();
int b = list.poll();
int temp = a+b;
list.add(temp);
result += temp;
}
System.out.println(result);
}
}比较奇偶数个数
题目链接
思路解析
这个太简单了，边输入，边统计就可以了
AC代码
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int odd = 0;
int even = 0;
for (int i = 0; i < n; i++) {
if (scanner.nextInt() % 2 == 0) {
even ++;
}else{
odd ++;
}
}
if (even > odd) {
System.out.println("NO");
}else {
System.out.println("YES");
}
}
}查找第K小数
题目链接
思路解析
我太喜欢java里面的list的sort方法，太方便了。
所以，我先对list进行去重，再排序，就可以直接输出第k-1个数就可以了
AC代码
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
List<Integer>list = new ArrayList<>();
for (int i = 0; i < n; i++) {
list.add(scanner.nextInt());
}
int k = scanner.nextInt();
list = new ArrayList<>(new LinkedHashSet<>(list));
Collections.sort(list);
System.out.println(list.get(k-1));
}
}矩阵幂
题目链接
思路解析
本题最重要的是实现，两个矩阵相乘。
相乘后的矩阵的某个元素result[i][j] 为A矩阵i行a[i][?] 与B矩阵j列b[?][j]对应相乘的结果。
AC代码
import java.util.Scanner;
public class Main {
public static int size = 0;
public static void main(String[] args) {
Main mutiple = new Main();
mutiple.handle();
}
public void handle(){
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
size = n;
int k = scanner.nextInt();
int [][] array = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
array[i][j] = scanner.nextInt();
}
}
int [][] origin = array;
for (int i = 1; i < k; i++) {
array = cheng(array, origin);
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
System.out.print(array[i][j]);
if (j!=n-1) {
System.out.print(" ");
}
}
System.out.println();
}
}
public int[][] cheng(int [][] arrayA,int [][]arrayB){
int[][] result = new int[size][size];
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
int temp = 0;
for (int l = 0; l < size; l++) {
temp += arrayA[i][l] * arrayB[l][j];
}
result[i][j] = temp;
}
}
return result;
}
}C翻转
题目链接
思路解析
在北邮2014年计院机试（上午） 的问题B：旋转图像 和这个其实是类似的：
都是寻找旋转90°后的矩阵和原矩阵的对应关系。
比如顺时针旋转90°，旋转后的矩阵就是以前矩阵按列输出，并且是按照最后一个数字输出。
比如下面的矩阵：
顺时针旋转90°，就是从第一列最后一个数字开始输出，7，4，1/ 8，5，2/9，6，3依次输出即可。
数字1是序号是(x-1,y-1) 则数字7的位置为(x-1+b-1,y-1)，（其中b=3）旋转后的矩阵的
第一行是(x-1+b-1-?, y-1+0)
第二行是(x-1+b-1-?, y-1+1)
第三行是(x-1+b-1-?, y-1+2)
?是表示这个元素在该行的位置，是该行的第?+1元素。代码中? = j - y + 1
旋转后的矩阵，每一行的第二个坐标规律为y-1+(i-x+1)
AC代码
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int[][] array = new int[5][5];
for(int i = 0; i <5;i++){
for (int j = 0; j < 5; j++) {
array[i][j] = scanner.nextInt();
}
}
int a = scanner.nextInt();
int b = scanner.nextInt();
String oper = a+""+b;
int x = scanner.nextInt();
int y = scanner.nextInt();
int [][] newArray = new int[5][5];
switch (a) {
case 1:
for (int i = x-1; i < x + b -1; i++) {
for (int j = y -1; j < y + b -1; j++) {
newArray[i][j] = array[x+b+y-j-3][y+i-x];
}
}
break;
case 2:
for (int i = x-1; i < x + b -1; i++) {
for (int j = y -1; j < y + b -1; j++) {
newArray[i][j] = array[j- y + x][x+y+b-i-3];
}
}
break;
default:
break;
}
for(int i = 0; i <5;i++){
for (int j = 0; j < 5; j++) {
if (i>= x-1 && i < x + b -1 && j>=y-1 && j < y + b -1) {
System.out.print(newArray[i][j]);
}else {
System.out.print(array[i][j]);
}
if (j != 4) {
System.out.print(" ");
}
}
System.out.println();
}
}
}打牌
题目链接
思路解析
这道题目已经简化了，给的数据一定是排序好的（手里拿着已经排好序的牌），所以在判断的时候，我们使用一个循环，在循环中构造中大于题目给的牌，然后用java的String.contains判断，自己手上的 牌有没有构造的牌即可。
AC代码
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String string = scanner.nextLine();
String string2 = scanner.nextLine();
char[] array = string2.toCharArray();
int lenght = array.length;
boolean isHave = false;
switch (lenght) {
case 1:
int value = Integer.parseInt(string2);
char[] arrayByhave = string.toCharArray();
for (int i = 0; i < arrayByhave.length; i++) {
if (Integer.parseInt(arrayByhave[i] + "") > value ) {
isHave = true;
break;
}
}
break;
case 2:
case 3:
case 4:
// System.out.println("ok");
int start = Integer.parseInt(array[0] + "");
for (int i = start + 1; i <= 9; i++) {
String temp = "";
for (int j = 0; j < lenght; j++) {
temp += i + "";
}
// System.out.println("临时生成的字符串" + temp);
if (string.contains(temp)) {
isHave = true;
break;
}
}
break;
case 5:
String[] strArray = new String[]{"12345", "23456", "34567","45678","56789"};
int flag = 0;
for (int i = 0; i < strArray.length; i++) {
if (string2.equals(strArray[i])) {
flag = i;
break;
}
}
String[] str1Array = string.split("");
List<String> list = new ArrayList<>(new LinkedHashSet<>(Arrays.asList(str1Array)));
StringBuilder sb = new StringBuilder();
for (int i = 0; i < list.size(); i++) {
sb.append(list.get(i));
}
String listToString = sb.toString();
// System.out.println("字符串" + listToString);
for (int i = flag + 1; i < strArray.length; i++) {
if (listToString.contains(strArray[i])) {
isHave = true;
break;
}
}
break;
default:
break;
}
if (isHave) {
System.out.println("YES");
}else {
System.out.println("NO");
}
}
}树查找
题目链接
思路解析
这道题目虽然是树的题目，但没必要构造出真实的树，因为题目说了是完全二叉树，输出某一深度的所有节点。某一深度k的所有节点编号是有范围的，起始编号是2^(k-1) ，终点编号是 min(节点总数-1，2^k -1)。
如果起始编号 > 终点编码，那就是不存在该深度的结点。
AC代码
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
List<Integer> list = new ArrayList<>();
for (int i = 0; i < n; i++) {
list.add(scanner.nextInt());
}
int depth = scanner.nextInt();
int vertexNumStart = 0;
int vertexNumEnd = 0;
for (int i = 1; i < depth; i++) {
vertexNumStart += vertexsInDepth(i);
}
vertexNumEnd = vertexNumStart + vertexsInDepth(depth);
int end = Math.min(list.size(), vertexNumEnd);
if (end <= vertexNumStart) {
System.out.println("EMPTY");
}else {
for (int i = vertexNumStart; i < end; i++) {
System.out.print(list.get(i));
if (i!=end -1) {
System.out.print(" ");
}
}
}
}
public static int vertexsInDepth(int depth) {
return (int) Math.pow(2, depth -1);
}
}查找
题目链接
思路解析
题目是查找，事实上内容是对字符串的操作。
一个是对字符串部分子串翻转，一个是对部分子串替换。
这个使用java的StringBuilder内置的reverse()和replace两个方法就很简单的完成了。
AC代码
import java.util.Scanner;
public class Main {
static Scanner scanner;
static String string;
public static void main(String[] args) {
scanner = new Scanner(System.in);
string = scanner.next();
int num = scanner.nextInt();
for (int i = 0; i < num; i++) {
Main search = new Main();
search.handle();
}
}
public void handle(){
String opration = scanner.next();
char[] toArray = opration.toCharArray();
switch (toArray[0]) {
case '0':
int start = Integer.parseInt(toArray[1] + "");
int end = Integer.parseInt(toArray[1] + "") + Integer.parseInt(toArray[2] + "");
String subString = string.substring(start,end);
subString = new StringBuilder(subString).reverse().toString();
string = new StringBuilder(string).replace(start, end, subString).toString();
break;
case '1':
int start1 = Integer.parseInt(toArray[1] + "");
int end1 = Integer.parseInt(toArray[1] + "") + Integer.parseInt(toArray[2] + "");
StringBuilder ToReplaceStrSb = new StringBuilder();
for (int i = 3; i < toArray.length; i++) {
ToReplaceStrSb.append(toArray[i]);
}
String toReplaceStr = ToReplaceStrSb.toString();
string = new StringBuilder(string).replace(start1, end1, toReplaceStr).toString();
break;
default:
break;
}
System.out.println(string);
}
}复数集合
题目链接
思路解析
这道题目很简单，就是新建一个复数的类，然后添加和删除复数，没什么好说了。
难点就是对输入进行处理。
AC代码
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Scanner;
public class Main {
List<Fu> fus = new ArrayList<>();
static Scanner scanner;
public static void main(String[] args) {
scanner = new Scanner(System.in);
Main fushu = new Main();
fushu.handle();
}
public void handle() {
fus.clear();
int num = scanner.nextInt();
scanner.nextLine();
for (int i = 0; i < num; i++) {
String oper = scanner.nextLine();
String[] operArray = oper.split(" ");
switch (operArray[0]) {
case "Pop":
Pop();
break;
case "Insert":
Insert(operArray[1]);
break;
default:
break;
}
}
}
public void Pop(){
if (fus.size() == 0) {
System.out.println("empty");
}else {
Collections.sort(fus,new Comparator<Fu>() {
@Override
public int compare(Fu o1, Fu o2) {
if (o1.getMoValue() < o2.getMoValue()){
return 1;
}else if (o1.getMoValue() > o2.getMoValue()) {
return -1;
}else {
if (o1.xu > o2.xu) {
return 1;
}else {
return -1;
}
}
}
});
System.out.println(fus.get(0).shi + "+i" + fus.get(0).xu);
fus.remove(0);
System.out.println("SIZE = " + fus.size());
}
}
public void Insert(String data){
String[] array = data.split("\\+");
fus.add(new Fu(Integer.parseInt(array[0]),getRealXu(array[1])));
System.out.println("SIZE = " + fus.size());
}
public int getRealXu(String str){
return Integer.parseInt(str.substring(1));
};
class Fu{
int shi;
int xu;
public int getMoValue(){
return (int) (Math.pow(shi, 2) + Math.pow(xu, 2));
}
public Fu() {
}
public Fu(int shi, int xu) {
super();
this.shi = shi;
this.xu = xu;
}
}
}二叉排序树
题目链接
思路解析
这道题有一点难度。
首先构造二叉排序树是一个递归的过程。不断的寻找插入位置，然后把节点插入到合适位置。
但是对于java这门语言，函数传参只能传值，不能传指针或者是引用，所以我们不能用课本上写的那样递归。
课本上递归的终止条件是bt == null，而我们的终止条件是bt.right == null || bt.left == null，因为课本上的函数都是传的引用进去的，所以bt == null的时候，后面给bt赋值一个新的节点，新的节点会自动的链接到他的父节点上！但是我们传的是值过去的就必须手动的链接新的节点。
这题的二叉树的结构就是用左右孩子结构。
AC代码
import java.util.Scanner;
public class Main {
static Scanner scanner;
TreeNode root;
public static void main(String[] args) {
scanner = new Scanner(System.in);
while (scanner.hasNext()) {
Main binarySortingTree = new Main();
binarySortingTree.handle();
}
}
public void handle() {
int num = scanner.nextInt();
int value = scanner.nextInt();
root = new TreeNode(value);
for (int i = 1; i < num; i++) {
int temp = scanner.nextInt();
BSTInsert(root,temp);
}
preoder(root);
System.out.println();
inorder(root);
System.out.println();
postOrder(root);
System.out.println();
}
public void preoder(TreeNode p) {
if (p != null) {
System.out.print(p.value + " ");
preoder(p.left);
preoder(p.right);
}
}
public void inorder(TreeNode p){
if (p != null) {
inorder(p.left);
System.out.print(p.value + " ");
inorder(p.right);
}
}
public void postOrder(TreeNode p){
if (p != null) {
postOrder(p.left);
postOrder(p.right);
System.out.print(p.value + " ");
}
}
public void BSTInsert(TreeNode bt, int value){
if (value != bt.value) {
if (value > bt.value) {
if (bt.right == null) {
bt.right = new TreeNode(value);
}else{
BSTInsert(bt.right, value);
}
}else if (value < bt.value) {
if (bt.left == null) {
bt.left = new TreeNode(value);
}else{
BSTInsert(bt.left, value);
}
}
}
}
class TreeNode{
int value;
TreeNode left;
TreeNode right;
public TreeNode(int value) {
this.value = value;
this.left = null;
this.right = null;
}
public TreeNode() {
}
}
}找最小数
题目链接
思路解析
这题很简单，仍然是一对数字，但不能使用Map，因为Map的key不能重复，所以不符合题目的输入。自建一个类。然后使用list的sort方法排序即可。
AC代码
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Main minPair = new Main();
minPair.handle();
}
public void handle(){
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
List<Pair> list = new ArrayList<>();
for (int i = 0; i < n; i++) {
Pair temp = new Pair(scanner.nextInt(), scanner.nextInt());
list.add(temp);
}
Collections.sort(list,new Comparator<Pair>() {
@Override
public int compare(Pair o1, Pair o2) {
if (o1.getKey() > o2.getKey()) {
return 1;
}else if (o1.getKey() < o2.getKey()) {
return -1;
}else {
return o1.getValue().compareTo(o2.getValue());
}
}
});
System.out.println(list.get(0).getKey() + " " + list.get(0).getValue());
}
class Pair{
int x;
int y;
Pair(int x, int y) {
super();
this.x = x;
this.y = y;
}
public Integer getKey(){
return x;
}
public Integer getValue(){
return y;
}
@Override
public String toString() {
// TODO 自动生成的方法存根
return "x=" + x + "y=" + y;
}
}
}查找
题目链接
AC代码
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
while (scanner.hasNext()) {
int n = scanner.nextInt();
List<Integer> list = new ArrayList<>();
for (int i = 0; i < n; i++) {
list.add(scanner.nextInt());
}
int m = scanner.nextInt();
for (int i = 0; i < m; i++) {
int temp = scanner.nextInt();
if (list.contains(temp)) {
System.out.println("YES");
}else {
System.out.println("NO");
}
}
}
}
}
2 条评论
写的很好，很喜欢
说到考研就有点头疼，我去学习了