最大子序列

[编程题]最大子序列

热度指数：3789 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

对于字符串x和y, 如果擦除x中的某些字母(有可能全擦掉或者都不擦)能够得到y,我们就称y是x的子序列。例如."ncd"是"nowcoder"的子序列,而"xt"不是。
现在对于给定的一个字符串s,请计算出字典序最大的s的子序列。

输入描述:

输入包括一行,一个字符串s,字符串s长度length(1 ≤ length ≤ 50).
s中每个字符都是小写字母

输出描述:

输出一个字符串,即字典序最大的s的子序列。

示例1

输入

test

输出

tt

算法知识视频讲解

Java

Ariana0106

用backtrack，每次找到当前字符串中最大的字母加到ret中，下一次backtrack的字符串就从最大字母的下一个字母开始

import java.util.*;
import java.lang.*;



public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		char[] s = sc.next().toCharArray();
		List<Character> ret = new ArrayList<>();
		backtrack(s, 'a', 0, ret);
		String ans = "";
		for(int i = 0; i < ret.size(); i++) {
			ans += ret.get(i);
		}
		System.out.println(ans);
	}	
	
	public static void backtrack(char[] s, char max, int maxIdx, List<Character> ret) {
		if(s.length == 0) return;
		for(int i = 0; i < s.length; i++) {
			if(s[i] > max) {
				max = s[i];
				maxIdx = i;
			} 
		}
		ret.add(max);
		//System.out.println(Arrays.copyOfRange(s, maxIdx, s.length));
		backtrack(Arrays.copyOfRange(s, maxIdx+1, s.length), 'a', maxIdx, ret);
	}
		
}

发表于 2020-09-03 15:29:42 回复(0)

Java

ybfq

import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
StringBuilder a = new StringBuilder(in.next());
for(int i=a.length()-2;i>=0;i--){
if(a.charAt(i)<a.charAt(i+1)){
a.delete(i,i+1);
}
}
System.out.println(a.toString());
}
}

发表于 2019-07-28 16:05:26 回复(0)

Java

羽墨如歌

这里我必须要说一个问题，字典序较大，就是两个字符串中比较大的元素，也就是java中compareTo的实现。好吧！我***了，哈哈哈。既然要找最的字典序，肯定要找开头最大。贪心算法，从后往前找，如果前者比后者大，则保留，否则就删除。

public class Main { 
public static void main(String[] args) { 
    Scanner input = new Scanner(System.in); 
    String str = input.nextLine(); 
    char[] res = str.toCharArray(); 
    ArrayList<Character> arr = new ArrayList<>(); 
    arr.add(res[res.length-1]); 
    for (int i = res.length-1; i > 0; i--){ 
        if ( arr.get(arr.size()-1) <= res[i-1]){ 
            arr.add(res[i-1]);             
        }         
    }         
    StringBuilder sb = new StringBuilder();         
    for (int i = 0; i < arr.size(); i++){             
        sb.append(arr.get(i));         
    }         
    System.out.println(sb.reverse().toString());     
    } 
}

编辑于 2018-07-12 09:31:29 回复(0)