第六周习题

﹏ヽ暗。殇╰゛Y 2022-11-18 01:19 236阅读 0赞

### 只是个人的记录>\_< ###

*  A、数组合并
 *   *  我的理解
     *   *  代码
 *  B、归并排序
 *   *  我的理解
     *   *  代码
 *  C、第k小元素问题
 *   *  我的理解
     *   *  代码
 *  D、找中位数
 *   *  我的理解
     *   *  代码
 *  E、棋牌覆盖
 *   *  我的理解
     *   *  代码
 *  F、大整数乘法
 *   *  我的理解
     *   *  代码

# A、数组合并 #

**题目描述**

*  编写一个程序，将两个有序数组合并成一个更大的有序数组，要求时间复杂度为O(n)。

**输入**

*  多组数据输入，每组输入包括两行，每行第一个数字为数组长度n，然后输入n个有序整数。

**输出**

*  输出合并后的数组（升序），每组输出用一个空行隔开。

**样例输入 Copy**

3 1 3 5
    3 2 4 6
    2 1 2
    4 3 4 5 6

**样例输出 Copy**

1 2 3 4 5 6
    
    1 2 3 4 5 6

## 我的理解 ##

> 【作为一个周三学完的学生，我表示，我上课好像懂了，下课一碰代码就忘，我这个题刚开始想的是，直接用归并排序把他们归并到一起，然后我的explipse报错了一天，数组超限，我一脸懵逼，然后我就去CSDN了，果然，一搜，就是很快，我把链接放在这里哈，我这次学聪明了，学完一题就把人家的链接放在我的电脑桌面，我真聪明！(๑•̀ㅂ•́)و✧】  
> 链接：[数组合并戳这里哟(＾Ｕ＾)ノ~ＹＯ！][Link 1]

### 代码 ###

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**

6 1 8 6 5 3 4
    5 12 42 2 5 8

**样例输出 Copy**

1 3 4 5 6 8
    2 5 8 12 42

## 我的理解 ##

*  【这个题，提到这个题我就恼火，我刚开始的写的时候，就一直给我报错，老说我数组超限，我一直改改改，好家伙，我真的是气不过啊，都改到了周六了，我直接上演了CSDN的ctrl+c加ctrl+v，很明显是可以运行的，再然后，我把我之前的写的代码的名字挪过来了，结果就是直接输出全0，我傻眼了，我又改回去了，好吧，又可以运行成功了，我真服了，难道是java特有的名字？气得我建了个包名“见鬼了”，\[○･｀Д´･○\] 】  
    链接：[归并排序要戳这里！这里！这里！][Link 2]

### 代码 ###

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**

2 5 6 1 8 7 9
    2

**样例输出 Copy**

## 我的理解 ##

*  【得！二话不说，先表达一下我的感慨，有之前的包和java代码真好使，我直接把上周的快速排序代码copy过来了，然而，“阳光总在风雨后”，是的，我又化身成为了苦逼大学生，死抠着一句句代码，然后去了CSDN，果然，在翻阅了好多好多篇代码之后，我成功了！仅以次链接代表我的心~心飞扬！说真的，我本来也就是一个小菜鸟，遇到这个特殊的输入也搜了很多，刚开始还想用泛型，发现学了就忘了，也不会用，后来找到文章的时候，就知道自己一定赚到了，学无止境】

链接：[第K小元素要戳蓝色字体！][K]

### 代码 ###

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**

5
    5 3 2 1 4

**样例输出 Copy**

## 我的理解 ##

*  【这个题目吧，我也不能说太多，毕竟这个我上课真的没有认真听讲，广大青年朋友别学我，这是不好的，我直接CSDN了，但是也有错误，就是输出的时候会报错，原因在输出的格式，如果有偶数个数据的话，输出不是要保留三位小数嘛，然后我之前找的那个代码的输出报错了，我又看到了别人的代码，所以也是改了一会儿，才输出正确的，（大家上课认真听讲可以做出来的）我也是找了挺久的代码，放个链接在下面，有需要自取(＾Ｕ＾)】  
    链接1：[这是第一篇 戳一戳我][Link 3]  
    链接2：[这是第二篇 两篇输出格式不一样哦，可以都看看！][Link 4]

### 代码 ###

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**

4
    -1 0 0 0
    0 0 0 0
    0 0 0 0
    0 0 0 0

**样例输出 Copy**

-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,果然我室有非常的聪明哈！】  
    放个链接：[棋盘覆盖 要不要戳一戳！][Link 5]

### 代码 ###

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**

1234 5678

**样例输出 Copy**

7006652

## 我的理解 ##

*  【我虽然是大自然的搬运工，但是我也是凭良心干活的，虽然我是照着老师给的代码敲的（千万别学我，这样不好，真的，相信我，别问我为什么不自己写，原因就是自己忘了，写不出来，还有就是时间不够了，我要去赚钱，我要流浪~哭唧唧）这我虽然也擦查找了几篇CSDN，但是我就是看了一下他们的输入没然后忘记了复制链接，对不起>o<】

### 代码 ###

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);
            }
    	}
    
    }

[Link 1]: https://blog.csdn.net/love_life_forever/article/details/107074276
[Link 2]: https://blog.csdn.net/qq_45353823/article/details/106273915
[K]: https://blog.csdn.net/weixin_43394832/article/details/105317385
[Link 3]: https://blog.csdn.net/ZHANGQIANYI2020/article/details/112506204
[Link 4]: https://blog.csdn.net/qq_43461438/article/details/113914556
[Link 5]: https://blog.csdn.net/qq_41377858/article/details/89068637