-1

我对我的 Java 技能很生疏，但我试图编写一个程序，提示用户输入一个字符串并显示最大长度增加的有序字符子序列。例如，如果用户输入Welcome程序会输出Welo. 如果用户输入WWWWelllcommmeee，程序仍然会输出Welo。我已经完成了这么多，但它没有做它应该做的事情，老实说，我不知道为什么。

import java.util.ArrayList;
import java.util.Scanner;

public class Stuff {

public static void main(String[] args) {
    Scanner input = new Scanner(System.in);
    System.out.println("Please enter a string. ");
    String userString = input.next();
    ArrayList charList = new ArrayList();
    ArrayList finalList = new ArrayList();
    int currentLength = 0;
    int max = 0;

    for(int i = 0; i < userString.length(); i++){
        charList.add(userString.charAt(i));

        for(int j = i; j < userString.length(); j++){
            int k=j+1;
            if(k < userString.length() && userString.charAt(k) > userString.charAt(j)){
                charList.add(userString.charAt(j));
                currentLength++;
            }
        }
    }

    if(max < currentLength){
        max = currentLength;
        finalList.addAll(charList);
    }

    for (int i = 0; i < finalList.size(); i++){
        char item = (char) finalList.get(i);
        System.out.print(item);
    }

    int size1 = charList.size();
    int size2 = finalList.size();
    System.out.println("");
    System.out.println("Size 1 is: " + size1 + " Size 2 is : " + size2);    
  }
 }

我的代码，如果我输入Welcome，输出WWeceeclcccome。

有人对我做错了什么有一些提示吗？

4

3 回答 3

1

在这些情况下，离开键盘并考虑您尝试实现的算法往往会有所帮助。试着先用文字解释一下。

您正在构建一个单独的字符列表，方法是将输入字符串中的每个字符附加到其右侧的字符，这些字符与它们的后继字符按正确的字母顺序排列。对于输入“欢迎”，这意味着累积的输出将是，垂直显示外循环，水平显示内循环：

W W e c
e e c
l c
c c
o
m
e

总计：WWeceeclcome

于 2013-09-06T07:28:22.470 回答
0

我看不到这个实现的逻辑。这是一个在 O(nlogn) 时间内运行的更快的解决方案。

import java.util.Scanner;

public class Stuff
{   
    //return the index of the first element that's not less than the target element
    public static int bsearch(char[] arr, int size, int key)
    {
        int left = 0;
        int right = size - 1;
        int mid;
        while (left <= right)
        {
            mid = (left + right) / 2;
            if(arr[mid] < key)
                left = mid + 1;
            else
                right = mid - 1;
        }
        return left;
    }

    public static void main(String[] args) 
    {
        Scanner input = new Scanner(System.in);
        System.out.println("Please enter a string: ");
        String userString = input.next();


        char[] maxArr = new char[userString.length()];
        char[] precedent = new char[userString.length()];
        maxArr[0] = userString.charAt(0);
        precedent[0] = userString.charAt(0);
        int len = 1;
        for(int i = 1; i < userString.length(); i++)
        {
            if(userString.charAt(i) > maxArr[len - 1])
            {
                maxArr[len] = userString.charAt(i);
                precedent[len] = userString.charAt(i);
                len++;
            }
            else
                maxArr[bsearch(maxArr, len, userString.charAt(i))] = userString.charAt(i);
        }

        //System.out.println(len);
        for(int i = 0; i < len; i++)
            System.out.print(precedent[i]);

    }

 }
于 2013-09-10T07:15:33.903 回答
0

在词典顺序中使用动态编程 O(N^2) 意味着如果 i/p 是 abcbcbcd 则 o/p 可以是 abcccd、abbbcd、abbccd 但按照词典顺序 o/p 将是 abbbcd。

public static String longestIncreasingSubsequence(String input1) {
    int dp[] = new int[input1.length()];
    int i,j,max = 0;
    StringBuilder str = new StringBuilder();

    /* Initialize LIS values for all indexes */
     for ( i = 0; i < input1.length(); i++ )
        dp[i] = 1;

     /* Compute optimized LIS values in bottom up manner */
     for ( i = 1; i < input1.length(); i++ )
        for ( j = 0; j < i; j++ ) 
              if (input1.charAt(i) >= input1.charAt(j) && dp[i] < dp[j]+1)
                  dp[i] = dp[j] + 1;

     /* Pick maximum of all LIS values */
     for ( i = 0; i < input1.length(); i++ ) {
        if ( max < dp[i] ) {
             max = dp[i];
             if (i + 1 < input1.length() && max == dp[i+1] && input1.charAt(i+1) < input1.charAt(i)) {
                 str.append(input1.charAt(i+1));
                 i++;
             } else {
                 str.append(input1.charAt(i)); 
             }
        }
     }
     return str.toString();
}
于 2017-05-02T09:42:40.693 回答