-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

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 に答える