算法小题（一）：按字典排序的子字符串

朱雀 2022-05-12 07:00 111阅读 0赞

# 用友2018秋招算法小题 #

## 原题目： ##

/\*\*  
 \* 找出连续数字字串的\[开始元素,连续个数\]  
 \* 样例:  
 \* input:    8 3 4 5 6 9 12 16【一行输入，按空格分隔】  
 \* output:  \[3,4\]  
 \*/

注意：遍历下一个元素时，数组越界问题

public class Main {
    	public static void main(String[] args){
    		Scanner sc =new Scanner(System.in);
    		String str[] = sc.nextLine().split(" ");
    		int nums[] = new int[str.length];
    		// 放入整型数组
    		for(int i=0; i<str.length; i++){
    			nums[i] = Integer.parseInt(String.valueOf(str[i]));
    //			System.out.println(str[i]);
    		}
    		
    		getResult(nums);	
    	}
    	
    	static public void getResult(int num[]){
    		int start= 0;	// 连续数字的开始下标
    		int max = 0;    // 记录连续数字的最大个数
    		int temp= 0 ;	// temp加载每个数组元素
    		int next= 0;	// temp的下一个元素
    		int count = 1; 	
    		
    		for(int i = 1; i <num.length; i++){	// i为下标,遍历数组,注意数组不能越界
    			temp = num[i-1];	
    			next = num[i];
    			if((next-temp) == 1){
    				count ++;
    			}else{
    				if(max < count){
    					max = count;
    					start = i - count;
    				}
    //				count = 1;
    			}
    		}
    		max = max>count? max:count;
    		for(int i = start; i<start+max; i++){
    			System.out.print(num[i]+" ");
    		}
    		System.out.println("["+num[start]+","+count+"]");
    	}
    	
    }

input：8 3 4 5 6 9 12 16

输出结果为：

![70][]

========================= =================================================

## 若题目改成——找出按字典排序的字串： ##

/\*\*  
 \* 找出按字典排序数字最大字串的\[开始元素,连续个数\]  
 \* 样例:  
 \* input:    1 3 4 5 6 9 12 16 10 18  
 \* output:  \[1,8\]  
 \*/

package Yonyou;
    
    import java.util.Scanner;
    /**
     * 找出按字典排序数字最大字串的[开始元素,连续个数]
     * 样例:
     * input:	1 3 4 5 6 9 12 16 10 18
     * output:  [1,8]
     */
    public class Main2 {
    	public static void main(String[] args){
    		Scanner sc =new Scanner(System.in);
    		String str[] = sc.nextLine().split(" ");
    		int nums[] = new int[str.length];
    		// 放入整型数组
    		for(int i=0; i<str.length; i++){
    			nums[i] = Integer.parseInt(String.valueOf(str[i]));
    //			System.out.println(str[i]);
    		}
    		
    		getResult(nums);	
    	}
    	
    	static public void getResult(int num[]){
    		int start= 0;	// 连续数字的开始下标
    		int max = 0;    // 记录连续数字的最大个数
    		int temp= 0 ;	// temp加载每个数组元素
    		int next= 0;	// temp的下一个元素
    		int count = 1; 	
    		
    		for(int i = 1; i <num.length; i++){	// i为下标,遍历数组,注意数组不能越界
    			temp = num[i-1];	
    			next = num[i];
    			if((next-temp) > 0){
    				count ++;
    			}else{
    				if(max < count){
    					max = count;
    					start = i - count;
    				}
    				count = 1;
    			}
    		}
    		max = max>count? max:count;
    		for(int i = start; i<start+max; i++){
    			System.out.print(num[i]+" ");
    		}
    		System.out.println("["+num[start]+","+max+"]");
    	}
    	
    }

input：1 3 4 5 6 9 12 16 10 18

输出结果为：

![70 1][]

[70]: /images/20220512/6b8e2250e1ff4678adacd127ea19bf11.png
[70 1]: /images/20220512/f831f9b238ea4a4798d2de9c0dc86fdc.png