美团 8-22 编程题 后台开发

package LinkCode;

import java.util.*;

public class meituan1 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		String str = sc.nextLine();
		List<Integer> res = new ArrayList<Integer>();
		res = cal(str);
		for (Integer temp : res)
			System.out.print(temp + " ");
		sc.close();
	}

	public static List<Integer> cal(String str) {
		// TODO Auto-generated method stub
		int[] arr = new int[128];
		for (int i = 0; i < str.length(); i++)
			arr[str.charAt(i)] = i;
		List<Integer> list = new ArrayList<>();
		int low = 0, high = 0;
		for (int i = 0; i < str.length(); i++) {
			high = Math.max(high, arr[str.charAt(i)]);
			if (i == high) {
				list.add(high - low + 1);
				low = high + 1;
			}
		}
		return list;
	}
}

第二题  AC 73%

package LinkCode;

import java.util.*;

public class meituan2 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		while (sc.hasNext()) {
			String str = sc.nextLine().trim().toLowerCase();
			String[] words = str.split(" ");
			System.out.println(cal(words));
		}
		sc.close();
	}

	public static String cal(String[] words) {
		// TODO Auto-generated method stub
		Map<Character, Set<Character>> map1 = new HashMap<>();
		Map<Character, Integer> map2 = new HashMap<>();
		String key = "invalid";
		String dig = "0123456789";
		for (int i = 0; i < words.length; i++) {
			if (words[i].contains(dig))
				return key;
		}
		for (String word : words) {
			for (char c : word.toCharArray()) {
				if (map1.containsKey(c)) {
					continue;
				}
				map1.put(c, new HashSet<>());
				map2.put(c, 0);
			}
		}
		for (int i = 0; i < words.length - 1; ++i) {
			String temp = words[i];
			String str = words[i + 1];
			for (int j = 0; j < Math.min(temp.length(), str.length()); ++j) {
				char x = temp.charAt(j);
				char y = str.charAt(j);
				if (x != y) {
					if (map1.get(x).add(y)) {
						map2.put(y, map2.get(y) + 1);
					}
					break;
				}
			}
		}

		StringBuilder sb = new StringBuilder();
		Queue<Character> list = new LinkedList<>();
		for (Map.Entry<Character, Integer> entry : map2.entrySet()) {
			if (entry.getValue() == 0) {
				list.offer(entry.getKey());
			}
		}
		while (!list.isEmpty()) {
			char c = list.poll();
			sb.append(c);
			for (char ch : map1.get(c)) {
				map2.put(ch, map2.get(ch) - 1);
				if (map2.get(ch) == 0) {
					list.offer(ch);
				}
			}
		}
		return sb.length() < map2.size() ? key : sb.toString();
	}
}