Lucky String -- 微软笔试

标签（空格分隔）：算法

A string s is LUCKY if and only if the number of different characters in s is a fibonacci number. Given a string consisting of only lower case letters , output all its lucky non-empty substrings in lexicographical order. Same substrings should be printed once.

输入描述:

a string consisting no more than 100 lower case letters.

输出描述:

output the lucky substrings in lexicographical order.one per line. Same substrings should be printed once.

输入例子:

aabcd

输出例子:

a

aa

aab

aabc

ab

abc

b

bc

bcd

c

cd

d

描述：

一个字符串是Lucky的当且仅当它里面字符的数目为Fibonacci数列中的一个数。如果给出一个字符串，它里面只包含小写字母，输出它所有的除空字符串外的Lucky SubString，每个子串只能被输出一次。并且输出的子串按照字典序列排序。

思路：

对于整个字符：

依次遍历字符串，截取子串
统计子串中的字符种类数，判断是否已经在结果集中出现或者是否符合Fibonacci数列
调用集合类的字符串排序算法，按照字典序列将结果集输出。

代码如下：

import java.util.ArrayList;

import java.util.Collections;

import java.util.List;

import java.util.Scanner;

public class LuckyString {

    /**

    * 给定一个字符串s，统计它里面一共出现了多少种字符

    * @param s

    * @return

    */

	public static int count(String s) {

	    char[] ch = s.toCharArray();

	    boolean[] letter = new boolean[26];

	    for(int i=0; i<26; i++)

	    	letter[i] = false;

    	int res = 0;

    	for(int i=0; i<ch.length; i++) {

	    	if(letter[ch[i]-'a'] == false) {

		    	letter[ch[i] -'a'] = true;

		    	res++;

	    	}

    	}

	    return res;

    }

	/**

	 * 二分查找一个数是否在给定数组中出现

     * @param nums

    * @param n

     * @return

     */

	public static int binearySearch(int[] nums, int n) {

	    int left = 0, right = nums.length-1, mid = (left+right)/2;

    	while(left <= right) {

	    	if(nums[mid] < n) {

	    		left = mid + 1;

	    	}

	    	else if(nums[mid] > n)

	    		right = mid - 1;

    		else return mid;

    		mid = (left + right) / 2;

    	}

    	return -1;

	}

	/**

	 * 解决问题的主要函数。

	 * 1. 依次遍历字符串，截取子串

	 * 2. 统计子串中的字符种类数，判断是否已经在结果集中出现或者是否符合Fibonacci数列

	 * 3. 调用集合类的字符串排序算法，按照字典序列将结果集输出。

     * @param s

     */

	public static void solve(String s) {

    	int[] fibo = {1,2,3,5,8,13,21,34,55,89};

    	List<String> res = new ArrayList<String>();

	    for(int i=0; i<s.length(); i++) {

		    for(int j=i+1; j<s.length()+1; j++) {

			    String sub = s.substring(i, j);

	    		int num = count(sub);

	    		if(binearySearch(fibo, num) >= 0 && !res.contains(sub)) //包含该数

		    		res.add(sub);

	    	}

    	}

	    Collections.sort(res);

		for(int i=0; i<res.size(); i++)

    		System.out.println(res.get(i));

	}

	public static void main(String[] args) {

    	// TODO Auto-generated method stub

		Scanner sc = new Scanner(System.in);

    	while(sc.hasNext()) {

	    	String s = sc.nextLine();

		    solve(s);

    	}

	}

}

巴特西

Lucky String

Lucky String -- 微软笔试

最新文章

热门文章