只是个人的记录>_<
- A、数组合并
- 我的理解
- 代码
- B、归并排序
- 我的理解
- 代码
- C、第k小元素问题
- 我的理解
- 代码
- D、找中位数
- 我的理解
- 代码
- E、棋牌覆盖
- 我的理解
- 代码
- F、大整数乘法
- 我的理解
- 代码
A、数组合并
题目描述
- 编写一个程序，将两个有序数组合并成一个更大的有序数组，要求时间复杂度为O(n)。
输入
- 多组数据输入，每组输入包括两行，每行第一个数字为数组长度n，然后输入n个有序整数。
输出
- 输出合并后的数组（升序），每组输出用一个空行隔开。
样例输入 Copy
java">3 1 3 5
3 2 4 6
2 1 2
4 3 4 5 6
样例输出 Copy
java">1 2 3 4 5 6
1 2 3 4 5 6
我的理解
【作为一个周三学完的学生，我表示，我上课好像懂了，下课一碰代码就忘，我这个题刚开始想的是，直接用归并排序把他们归并到一起，然后我的explipse报错了一天，数组超限，我一脸懵逼，然后我就去CSDN了，果然，一搜，就是很快，我把链接放在这里哈，我这次学聪明了，学完一题就把人家的链接放在我的电脑桌面，我真聪明！(๑•̀ㅂ•́)و✧】
链接：数组合并戳这里哟(＾Ｕ＾)ノ~ＹＯ！
代码
java">import java.util.Scanner;
public class Main {
public static int[] hebingshuzu(int[] diyige, int[] dierge) {
int i=0,j=0,k=0;
int[] cbb = new int[diyige.length+dierge.length];
while(i<diyige.length&&j<dierge.length){
if(diyige[i]<dierge[j])
cbb[k]= diyige[i++];
else
cbb[k]= dierge[j++];
k++;
}
while(i<diyige.length){
cbb[k]= diyige[i++];
k++;
}
while(j<dierge.length){
cbb[k]= dierge[j++];
k++;
}
return cbb;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
Main main = new Main();
while(sc.hasNext()){
int m = sc.nextInt();
int diyige[] = new int[m];
for(int i=0;i<m;i++)
diyige[i] = sc.nextInt();
int n = sc.nextInt();
int dierge[] = new int[n];
for(int i=0;i<n;i++)
dierge[i] = sc.nextInt();
int cbb[] = Main.hebingshuzu(diyige, dierge);
for(int i=0;i<diyige.length+dierge.length;i++)
System.out.print(cbb[i]+" ");
System.out.println("\n");
}
}
}
B、归并排序
题目描述
- 编写一个程序，使用分治策略实现二路归并排序（升序）。
输入
- 多组输入，每组第一个数字为数组长度，然后输入一个一维整型数组。
输出
- 输出排序之后（升序）的一维整型数组，每组输出占一行。
样例输入 Copy
java">6 1 8 6 5 3 4
5 12 42 2 5 8
样例输出 Copy
java">1 3 4 5 6 8
2 5 8 12 42
我的理解
- 【这个题，提到这个题我就恼火，我刚开始的写的时候，就一直给我报错，老说我数组超限，我一直改改改，好家伙，我真的是气不过啊，都改到了周六了，我直接上演了CSDN的ctrl+c加ctrl+v，很明显是可以运行的，再然后，我把我之前的写的代码的名字挪过来了，结果就是直接输出全0，我傻眼了，我又改回去了，好吧，又可以运行成功了，我真服了，难道是java特有的名字？气得我建了个包名“见鬼了”，[○･｀Д´･○] 】
链接：归并排序要戳这里！这里！这里！
代码
java">import java.util.Scanner;
public class Main {
public static void Merge (int SR[ ], int TR[ ], int s, int m, int t )
{
int i=s;
int j=m+1;
int k=s;
while(i<=m&&j<=t){
if (SR[i]<=SR[j])
{
TR[k++]=SR[i++];
}
else
{
TR[k++]=SR[j++];
}
}
while (i<=m)
{
TR[k++]=SR[i++];
}
while (j<=t)
{
TR[k++]=SR[j++];
}
}
public static void MergeSort(int SR[],int TR[], int s, int t ) {
if (s < t) {
int m = (s+t)/2;
MergeSort(SR,TR, s, m);
MergeSort(SR,TR, m+1, t);
Merge(SR, TR, s, m, t);
for(int i=s;i<=t;i++)
{
SR[i] = TR[i];
}
}
}
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
while(sc.hasNext())
{
int n=sc.nextInt();
int SR[]=new int[n];
for(int i=0;i<n;i++)
{
SR[i]=sc.nextInt();
}
int[] TR=new int[n];
MergeSort(SR, TR, 0, n-1);
for(int j=0;j<n;j++)
{
System.out.print(TR[j]+" ");
}
System.out.println();
}
}
}
C、第k小元素问题
题目描述
- 输入一个整数数组，请求出该数组的第k小元素。要求时间复杂度为O(n)。
输入
- 每组输入包括两行，第一行为一个整数数组，两个数字之间用空格隔开；第二行为k值。数组中元素个数小于10^9。
输出
- 输出第k小元素的值。
样例输入 Copy
java">2 5 6 1 8 7 9
2
样例输出 Copy
java">2
我的理解
- 【得！二话不说，先表达一下我的感慨，有之前的包和java代码真好使，我直接把上周的快速排序代码copy过来了，然而，“阳光总在风雨后”，是的，我又化身成为了苦逼大学生，死抠着一句句代码，然后去了CSDN，果然，在翻阅了好多好多篇代码之后，我成功了！仅以次链接代表我的心~心飞扬！说真的，我本来也就是一个小菜鸟，遇到这个特殊的输入也搜了很多，刚开始还想用泛型，发现学了就忘了，也不会用，后来找到文章的时候，就知道自己一定赚到了，学无止境】
链接：第K小元素要戳蓝色字体！
代码
java">import java.util.Scanner;
public class Main {
public static void jiaohuan(int cbb[],int i,int j){//比較大小，小的在前，大的在后
int temp = cbb[i];
cbb[i] = cbb[j];
cbb[j] = temp;
}
public static int fenqu(int cbb[],int left,int right){//分區，前面都是小於基準的，後面都是大於基準的
int jizhun = cbb[left];//基準
while (left < right) {// 最终使得枢纽之前（后）的记录均不大（小）于它
while (left < right && cbb[right] >= jizhun)
right--;
jiaohuan(cbb, left, right);// 将比枢轴记录小的记录交换到低端
while (left < right && cbb[left] <= jizhun)
left++;
jiaohuan(cbb, left, right); // 将比枢轴大的记录交换到高端
}
return left;
}
private static int kuaipai(int cbb[],int left,int right,int key){
if(left==right)
return cbb[left];
int r = fenqu(cbb,left,right);//p,q兩個端點，分區縮小範圍
int j = r-left+1;
if(key<=j)
return kuaipai(cbb,left,r,key);
else
return kuaipai(cbb,r+1,right,key-j);
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
String str1 = sc.nextLine();//接收数据
String str2 = sc.nextLine();//接收第K个元素的k
int key = Integer.parseInt(str2);
String[] shuzu = str1.split(" ");//以空格分割数据
int[] cbb = new int[shuzu.length];
for (int i = 0; i < shuzu.length; i++) {
cbb[i] = Integer.parseInt(shuzu[i]);
}
shuzu = null;
System.out.println(kuaipai(cbb, 0, cbb.length - 1, key));
}
}
}
D、找中位数
题目描述
- 请设计一个算法，不排序，快速计算出一个无序数列的中位数。 时间复杂度要求为O(n)。
- 如果有奇数个元素，中位数则是数组排序后最中间的那个数字。
- 如果是偶数个元素，中位数则是数组排序后最中间两个元素的平均值。
输入
- 有多组输入，每组输入的第一行为n(1<=n<=1e5)，表示该数列的元素个数。
- 第二行为n个整数组成的无序数列
输出
- 每组样例输出一行，表示该无序数列的中位数。
- 若为偶数，请保留三位小数
- 若为奇数，直接输出
样例输入 Copy
java">5
5 3 2 1 4
样例输出 Copy
java">3
我的理解
- 【这个题目吧，我也不能说太多，毕竟这个我上课真的没有认真听讲，广大青年朋友别学我，这是不好的，我直接CSDN了，但是也有错误，就是输出的时候会报错，原因在输出的格式，如果有偶数个数据的话，输出不是要保留三位小数嘛，然后我之前找的那个代码的输出报错了，我又看到了别人的代码，所以也是改了一会儿，才输出正确的，（大家上课认真听讲可以做出来的）我也是找了挺久的代码，放个链接在下面，有需要自取(＾Ｕ＾)】
链接1：这是第一篇 戳一戳我
链接2：这是第二篇 两篇输出格式不一样哦，可以都看看！
代码
java">import java.text.DecimalFormat;
import java.util.Scanner;
public class Main {
public static void jiaohuan(int cbb[],int i,int j){
int temp = cbb[i];
cbb[i] = cbb[j];
cbb[j] = temp;
}
public static int fenqu(int cbb[],int left,int right) {
int wode = cbb[left];
int i = left,j;
for(j = left+1; j<=right;j++) {
if(cbb[j]<wode) {
i++;
jiaohuan(cbb,i,j);
}
}
jiaohuan(cbb,left,i);
return i;
}
public static void zhongweishu(int cbb[],int left,int right) {
int middle = (left+right)/2;
while(true) {
int ding = fenqu(cbb,left,right);
if(ding == middle)
break;
else if(ding >middle)
right = ding-1;
else
left = ding+1;
}
if(cbb.length%2!=0) {
System.out.println(cbb[middle]);
}
else {
DecimalFormat df = new DecimalFormat("#0.000");
System.out.println(df.format((double) (cbb[middle]+cbb[middle+1])/2));
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while(sc.hasNext()) {
int n=sc.nextInt();
int cbb[]=new int[n];
for(int i=0;i<n;i++)
cbb[i]=sc.nextInt();
zhongweishu(cbb,0,cbb.length-1);
}
}
}
E、棋牌覆盖
题目描述
- 在一个n×n (n = 2k)个方格组成的棋盘中，恰有一个方格与其他方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。
- 在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。
输入
- 多组测试用例，每组测试用例包括两部分，
- 第一部分为方格的宽度n，
- 第二部分则为方格，特殊方格为-1，其他方格为0。
输出
- 输出覆盖后的方案
样例输入 Copy
java">4
-1 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
样例输出 Copy
java">-1 2 4 4
2 2 1 4
3 1 1 5
3 3 5 5
我的理解
- 【没什么好说的，我们老师直接吧核心代码给我们了，但是我的问题出在，int t = ++title;我把这个放在了判断size是否等于1的前面，导致输出出错了，不管size等不等于1，title都会加1,果然我室有非常的聪明哈！】
放个链接：棋盘覆盖 要不要戳一戳！
代码
java">import java.util.Scanner;
public class Main {
static int board[][] = new int[100][101];
static int title =0;//用作标记L型骨牌编号
//tr，tc表示棋盘的起始位置(第tr行，第tc列)，dr，dc表示特殊格子所在位置(第dr行，第dc列)
//size表示棋盘大小，4*4的棋盘size为4
public static void chess(int tr,int tc,int dr,int dc,int size){
if(size==1)
return ;//递归出口
int t = ++title;
int s = size/2;
//如果特殊点的位置在左上方
if(dr<tr+s&&dc<tc+s){
chess(tr,tc,dr,dc,s);
}else{
//填充其右下角格子
board[tr+s-1][tc+s-1] = t;
chess(tr,tc,tr+s-1,tc+s-1,s);
}
//如果特殊点的位置在左下方
if(dr>=tr+s && dc<tc+s){
chess(tr+s,tc,dr,dc,s);
}else{
//填充其右上角格子
board[tr+s][tc+s-1] = t;
chess(tr+s,tc,tr+s,tc+s-1,s);
}
//如果特殊点的位置在右上方
if(dr<tr+s&&dc>=tc+s){
chess(tr,tc+s,dr,dc,s);
}else{
//填充其左下角格子
board[tr+s-1][tc+s] = t;
chess(tr,tc+s,tr+s-1,tc+s,s);
}
//如果特殊点的位置在右下方
if(dr>=tr+s && dc>=tc+s){
chess(tr+s,tc+s,dr,dc,s);
}else{
//填充其左上角格子
board[tr+s][tc+s] = t;
chess(tr+s,tc+s,tr+s,tc+s,s);
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
while(sc.hasNext()){
int size = sc.nextInt();
int x = 0;
int y = 0;
for(int i=0;i<size;i++){
for(int j=0;j<size;j++){
board[i][j] = sc.nextInt();
if(board[i][j]==-1){
//特殊点所在位置
x=i;
y=j;
}
}
}
chess(0,0,x,y,size);
//输出棋盘
for(int i=0;i<size;i++){
for(int j=0;j<size;j++){
System.out.print(board[i][j]+" ");
board[i][j]=0;
}
}
title=0;
}
}
}
F、大整数乘法
题目描述
- 使用分治算法实现两个大整数相乘。
输入
- 两个十进制大整数，满足每一个整数长度为2^n且两个大整数的长度相等。（多组数据）
输出
- 两个大整数的乘积。
样例输入 Copy
java">1234 5678
样例输出 Copy
java">7006652
我的理解
- 【我虽然是大自然的搬运工，但是我也是凭良心干活的，虽然我是照着老师给的代码敲的（千万别学我，这样不好，真的，相信我，别问我为什么不自己写，原因就是自己忘了，写不出来，还有就是时间不够了，我要去赚钱，我要流浪~哭唧唧）这我虽然也擦查找了几篇CSDN，但是我就是看了一下他们的输入没然后忘记了复制链接，对不起>o<】
代码
java">import java.util.Scanner;
public class Main {
public static int sign(long value){ //标志位
return value>0? 1:-1;
}
public static long jie(long x,long y,int n){
int s = sign(x)*sign(y);
x = Math.abs(x);
y = Math.abs(y);
if(x==0||y==0)
return 0;
else if(n==1)
return s*x*y;
else{
long A = (long)(x/Math.pow(10,n/2));
long B = (x%(long)Math.pow(10,n/2));
long C = (long)(y/Math.pow(10,n/2));
long D = (y%(long)Math.pow(10,n/2));
long AC = jie(A,C,n/2);
long BD = jie(B,D,n/2);
long ABCD = jie(A-B,D-C,n/2)+AC+BD;
return (long)(s*(AC*Math.pow(10,n)+ABCD*Math.pow(10,n/2)+BD));
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
while(sc.hasNext()){
long x = sc.nextLong();
long y = sc.nextLong();
System.out.println(x*y);
}
}
}
