第八周习题

客官°小女子只卖身不卖艺 2023-01-16 11:26 163阅读 0赞

### 记录： ###

*  A.解密
 *   *   *  参考代码
 *  B.最长公共子序列问题(LCS)之备忘录法
 *   *   *  参考代码
 *  C.最长公共子序列问题(LCS)之动态规划法
 *   *   *  参考代码
 *  D.最长公共子序列问题(LCS)-构造LCS
 *   *   *  参考代码
 *  E.牛牛的字符串（最大公共子串的长度）
 *   *   *  参考代码
 *  F.最大子段和
 *   *   *  参考代码

# A.解密 #

**1.题目描述**

*  湖南中医药大学有含浦、东塘 2 个校区，学校办学历史悠久，前身为 1934 年的湖南国医专科学校，1953年创办湖南中医进修学校，1960 年创建普通高等本科院校——湖南中医学院，1979 年成为全国首批取得中医类研究生学历教育资格的院校，1990 年原湖南科技大学成建制并入湖南中医学院，2002 年与湖南省 中医药研究院合并，2006年经教育部批准更名为湖南中医药大学，2012 年进入湖南省一本招生序列。目前，学校与湖南省中医药研究院实行校院合一的管理体制。学校学科门类齐全、中医药特色鲜明。学校 设有 18 个学院、24个本科专业，涵盖医、理、工、管、文等 5 大学科门类。中医诊断学在本学科研究领 域居国内领先水平。
 *  小 F居住在含浦校区，他想和东塘校区的同学小 L 聊天，为了保证沟通安全，他发明了一种加密方式，这 种加密方式是这样的：对于一个 01串，小 F 会将其从左到右每 8 位分成一组，最后一组可能不足 8 位， 对每组进行逆序操作，即如果原来是 bL bL+1 bL+2 · · · bR−1 bR, 逆序之后变成 bRbR−1bR−2 · · · bL−1bL。现在 小 F 已经加密好了一个串，并且将其发给了小 L，你能帮助小 L 得到这串密文对应的原始信息吗？

**2.输入**

*  单组数据。 一行一个 01 串，代表加密后的字符串，串长度大于 0, 小于等于 100。

**3.输出**

*  一行字符串，代表加密后的字符串所对应的原始信。

**4.样例输入 Copy**

100010110011101

**5.样例输出 Copy**

110100011011100

> 【这个题目嘛，ლ讲真的，第一眼我真的没看明白是个什么意思，然后我就直接CSDN了，不然我也不能自己死磕到底啊，我看了好几个人的代码，都没看懂（最近越来越看不懂C语言了，头疼~）然后好不容易找到了一个Java的代码，昨天晚上十点多，盯着代码看，总算是理解了一丢丢；在我看来，就是分成两半，前半部分倒过来，后半部分也倒过来，但是我发现我好像不会写呢，怎么办呢，于是乎，我的懒神触动了，是的没错，我直接照着大佬的代码敲了2，我对不起老师啊，QAQ，但是没办法啊，要冲业绩啊（开玩笑，哪来的业绩，就是个普通的周周练习题）好啦，就放一个我找到的博主的代码的——链接：[解密——戳我戳我！这里！][Link 1]】

### 参考代码 ###

import java.util.Scanner;
    
    public class Main { 
    	
    	public static void swap(char shuzu[],int i,int j) { //交换
    		
    		char ch = shuzu[i];
    		shuzu[i] = shuzu[j];
    		shuzu[j] = ch;
    	}
    	
    	public static void main(String[] args) { 
    		Scanner sc = new Scanner(System.in);
    		while(sc.hasNext()) { 
    			String string = sc.next();
    			char shuzu[] = string.toCharArray();//获取 字符串
    			
    			for(int i=0;i<shuzu.length;) { //在整个数组内进行分区
    				
    				int left = i;
    				int right = Math.min(shuzu.length-1,i+7);
    				
    				while(left<right) { //符合条件的进行逆序 //若大于一段分区，继续进行
    					
    					swap(shuzu,left,right);
    					left++;
    					right--;
    				}
    				
    				i += 8;  //若加8后超出范围，结束循环
    			}
    			for(int i=0;i<shuzu.length;i++) { 
    				if(i==shuzu.length-1) { //输出到数组最后一个
    					
    					System.out.print(shuzu[i] + "\n");
    				}else
    					System.out.print(shuzu[i]);
    			}
    		}
    	}
    }

# B.最长公共子序列问题(LCS)之备忘录法 #

**1.题目描述**

*  使用备忘录法求解两个序列的最长公共子序列的长度。

**2.输入**

*  每组输入包括两行，每行包括一个字符串。

**3.输出**

*  两个序列的最长公共子序列的长度。

**4.样例输入 Copy**

ACBCDABD
    ABDCABA

**5.样例输出 Copy**

> 【这个我们上课讲过了，那我就不唠嗑了，我唠嗑似乎也没得啥子用，直接上代码昂~一部分是我自己敲的，就是照着老师的PPT给的伪代码敲的，但是！不得不说，我只要一用数组，就必超限，怎么写我都超限，无奈啊，不得不CSDN了，戒不掉了，翻个链接哈，我敢保证，我只是对比了一下我的代码和人家的代码有什么区别，然后顺便改一下，就OK了，(\* ^▽ ^ \*)  
> 链接来啦：[戳这里，不记得原作者的标题了，就这个啦！][Link 2]】

### 参考代码 ###

import java.util.Scanner;
    
    public class Main { 
    	
    	public static int LCS(char []x,char []y,int i,int j){ 
    		
    		int [][]c = new int[i+1][j+1];
    		
    		if(i==0||j==0) 
    			return 0;
    		
    		else if(x[i-1]==y[j-1])
    			c[i][j] = LCS(x,y,i-1,j-1)+1;
    		else
    			c[i][j] = Math.max(LCS(x,y,i-1,j), LCS(x,y,i,j-1));
    		
    		return c[i][j];
       }
    
    
    	public static void main(String[] args) { 
    		
    		Scanner sc = new Scanner(System.in);
            while(sc.hasNext()){ 
            	String str1 = sc.next();
            	String str2 = sc.next();
    			char x[] = str1.toCharArray();//获取 字符串
    			char y[] = str2.toCharArray();//获取 字符串
    			int i = x.length;
    			int j = y.length;
    			System.out.println(LCS(x,y,i,j));
            }
    	}
    
    }

# C.最长公共子序列问题(LCS)之动态规划法 #

**1.题目描述**

*  使用动态规划算法求解两个序列的最长公共子序列的长度。

**2.输入**

*  每组输入包括两行，每行包括一个字符串。

**3.输出**

*  两个序列的最长公共子序列的长度。

**4.样例输入 Copy**

ACBCDABD
    ABDCABA

**5.样例输出 Copy**

> 【动态规划的代码就是在备忘录的基础上增加了一丢丢东西，（其实好像也没什么是吧）o(*￣︶￣*)o，记得戳链接哦：[戳小蓝——记得戳一戳，可以看看文章，当然不是本文作者的文章，是其他的大佬的文章][Link 2]】

### 参考代码 ###

import java.util.Scanner;
    
    public class Main { 
    public static int LCS(char []x,char []y,int m,int n){ 
    		
    		int [][]c = new int[m+1][n+1];
    			
    		for(int i=1;i<=m;i++)
    			for(int j=1;j<=n;j++){ 
    				if(x[i-1]==y[j-1])
    					c[i][j] = c[i-1][j-1]+1;
    				else
    					c[i][j] = Math.max(c[i-1][j],c[i][j-1]);
    			}
    		
    		return c[m][n];
    }
    
    	public static void main(String[] args) { 
    		// TODO Auto-generated method stub
            
    		Scanner sc = new Scanner(System.in);
            while(sc.hasNext()){ 
            	String str1 = sc.next();
            	String str2 = sc.next();
    			char x[] = str1.toCharArray();//获取 字符串
    			char y[] = str2.toCharArray();//获取 字符串
    			System.out.println(LCS(x,y,x.length,y.length));
            }
    	}
    
    }

# D.最长公共子序列问题(LCS)-构造LCS #

**1.题目描述**

*  使用动态规划算法求两个序列的最长公共子序列，需构造一条最长公共子序列。

**2.输入**

*  每组输入包括两行，每行包括一个字符串。

**3.输出**

*  两个字符序列的一条最长公共子序列。（输入已确保最长公共子序列的唯一性）

**4.样例输入 Copy**

acdbxx
    ccdxx

**5.样例输出 Copy**

cdxx

【基本上书本上的代码占了很大比重，但是没有CSDN上的大佬的帮助，我只是一位会超限的小朋友~，小伙伴们一定要多看书哦，冲鸭！！！戳个链接：[戳戳戳！！快来戳我呀！][Link 3]】

### 参考代码 ###

import java.util.Scanner;
    
    public class Main { 
    	public static int [][]b = new int[100][100];
    	
        public static int[][] LCSlength(char []x,char []y){ 
    		
        	int m = x.length-1;
        	int n = y.length-1;
    	
    		int [][]c = new int[m+1][n+1];
    		
    		for(int i=1;i<=m;i++)
    			c[i][0] = 0;
    		for(int i=1;i<=n;i++)
    			c[0][i] = 0;
    		for(int i=1;i<=m;i++)
    			for(int j=1;j<=n;j++){ 
    				if(x[i]==y[j]){ 
    					c[i][j] = c[i-1][j-1]+1;
    					b[i][j] = 1;
    				}
    				else if(c[i-1][j] >= c[i][j-1]){ 
    					c[i][j] = c[i-1][j];
    					b[i][j] = 2;
    				}
    				else{ 
    					c[i][j] = c[i][j-1];
    					b[i][j] = 3;
    				}
    					
    			}
    		
    		return b;
    }
    
    public static void LCS(char []x,int [][]b,int i,int j){ 
    	if(i==0||j==0)
    		return;
    	if(b[i][j]==1){ 
    		LCS(x,b,i-1,j-1);
    		System.out.print(x[i]);
    	}
    	else if(b[i][j]==2)
    		LCS(x,b,i-1,j);
    	else
    		LCS(x,b,i,j-1);
    }
    	public static void main(String[] args) { 
    		// TODO Auto-generated method stub
            
    		Scanner sc = new Scanner(System.in);
            while(sc.hasNext()){ 
            	String str1 = sc.next();
            	String str2 = sc.next();
    			char x[] = str1.toCharArray();//获取 字符串
    			char y[] = str2.toCharArray();//获取 字符串
    			
    			int[][] b = LCSlength(x, y);
    			
    			LCS(x, b, x.length - 1, y.length - 1);
    			
            }
    	}
    
    }

# E.牛牛的字符串（最大公共子串的长度） #

**1.题目描述**

*  牛牛有两个字符串(可能包含空格)，他想找出其中最长的公共连续子串的长度，希望你能帮助他。例如：两个字符串分别为"abede"和"abgde"，结果为2。

**2.输入**

*  每组数据包括两行，每行为一个字符串。

**3.输出**

*  输出最长的公共连续子串的长度。

**4.样例输入 Copy**

abede
    abgde

**5.样例输出 Copy**

【对不起我曾经翻阅过得博文，我忘记地址了，嗯。。。要不凑活着看？】

### 参考代码 ###

import java.util.Scanner;
    
    public class Main { 
    	
        public static int LCSlength(char []x,char []y){ 
    		
        	int m = x.length;
        	int n = y.length;
    	
    		int [][]c = new int[m+1][n+1];
    		
    		for(int i=0;i<=m;i++)
    			c[i][0] = 0;
    		for(int i=0;i<=n;i++)
    			c[0][i] = 0;
    		
    		for(int i=1;i<=m;i++)
    			for(int j=1;j<=n;j++){ 
    				if(x[i-1]==y[j-1])
    					c[i][j] = c[i-1][j-1]+1;
    				else 
    					c[i][j] = 0;
    			}
    		int max = 0;
    		for(int i=0;i<=m;i++)
    			for(int j=0;j<=n;j++){ 
    				if(c[i][j]>max){ 
    					max = c[i][j];
    				}
    			}
    		return max;
    }
    
    	public static void main(String[] args) { 
    
    		Scanner sc = new Scanner(System.in);
            while(sc.hasNext()){ 
            	String str1 = sc.next();
            	String str2 = sc.next();
    			char x[] = str1.toCharArray();//获取 字符串
    			char y[] = str2.toCharArray();//获取 字符串
    			System.out.println(LCSlength(x,y));
            }
    	}
    
    }

# F.最大子段和 #

**1.题目描述**

*  给定n个整数（可能是负数）组成的序列a\[1\], a\[2\], a\[3\], …,  
    a\[n\]，求该序列的子段和如a\[i\]+a\[i+1\]+…+a\[j\]的最大值。

**2.输入**

*  每组输入包括两行，第一行为序列长度n，第二行为序列。

**3.输出**

*  输出字段和的最大值。

**4.样例输入 Copy**

5
    -1 0 1 2 3

**5.样例输出 Copy**

> 【表示歉意，我找不到我参考的文章的链接了(＞人＜）】

### 参考代码 ###

import java.util.Scanner;
    
    public class Main { 
        
    	public static int []a = new int[105];
    	public static int []b = new int[105];
    	public static int n,maxSum;
    	
    	public static void main(String[] args) { 
    		// TODO Auto-generated method stub
    	   Scanner sc = new Scanner(System.in);
    	   Main main = new Main();
           while(sc.hasNext()){ 
               n = sc.nextInt();
        	   for(int i=0;i<n;i++)
        		   a[i] = sc.nextInt();
        	   
        	   b[0] = a[0];
       		   maxSum = b[0];
       		   
       		   for(int j=1;j<n;j++){ 
       			   
       			   if(b[j-1]>0)
       				  b[j] = b[j-1]+a[j];
       			   else
       				  b[j] = a[j];
       			   
       			   if(b[j]>maxSum)
       				  maxSum = b[j];
       		   }
       		   
        	   System.out.println(maxSum);
    		
        }
    }
    
    }

> 【小白今天去吃了螺蛳粉~啊这，臭臭的辣辣的，啊哈哈哈哈，下午吃了学校的卤肉卷，可好吃了，这种面皮之类的吃起来可香了!主要是我吃啥都吃的很香，以至于我的朋友们都说，看着我吃东西就很有食欲，(\# ^ . ^ \#)】
> 
> > 句子君：
> 
> ——“阿信说：“你们带电话了吗？拿出来。打给你们喜欢的人。我唱温柔给他听。” 全世界都暗了。只剩下全场观众手机屏幕发出的微弱亮光。那些亮光链接着自己和喜欢的人。 然后他站在一束光中。他说: 如果你对我说你想要一朵花。那么我就会给你一朵花。 如果你对我说你想要一颗星星。那么我就会给你一颗星星。 如果你说你想离开我。那么我会对你说: 瞬间灯全亮了起来 “我给你自由。我给你全部全部全部的自由。 这是我的温柔 ”接通电话那头无声的感动捂着嘴巴早已经泪流满面。有多少人的电话是没有打通的呢。会好遗憾吧。”  
> ——“看到路上尽情歌唱的，在路口弹着吉他的青年，感受到的是对梦想和远方的呼唤，在狭长的胡同小巷，看到的是生活的不易却乐观待人，面对起落却能够每天燃起新的希望，迎接新的挑战，因为还可以为想成为的人，想做的事而奋斗，甘之如饴。”

[Link 1]: https://blog.csdn.net/qq_46546793/article/details/105468781
[Link 2]: https://blog.csdn.net/qq_45353823/article/details/105217778
[Link 3]: https://blog.csdn.net/weixin_42510278/article/details/114076533