【LeetCode】Reorder Log Files(重新排列日志文件)

这道题是LeetCode里的第937道题。

题目描述：

你有一个日志数组 logs。每条日志都是以空格分隔的字串。

对于每条日志，其第一个字为字母数字标识符。然后，要么：

标识符后面的每个字将仅由小写字母组成，或；

标识符后面的每个字将仅由数字组成。

我们将这两种日志分别称为字母日志和数字日志。保证每个日志在其标识符后面至少有一个字。

将日志重新排序，使得所有字母日志都排在数字日志之前。字母日志按字母顺序排序，忽略标识符，标识符仅用于表示关系。数字日志应该按原来的顺序排列。

返回日志的最终顺序。

示例：
输入：["a1 9 2 3 1","g1 act car","zo4 4 7","ab1 off key dog","a8 act zoo"]

输出：["g1 act car","a8 act zoo","ab1 off key dog","a1 9 2 3 1","zo4 4 7"]
提示：

0 <= logs.length <= 100

3 <= logs[i].length <= 100

logs[i] 保证有一个标识符，并且标识符后面有一个字。

题目的意思很简单，但是由于处理的是字符串，处理起来就会相对的麻烦一些。

首先我们先要用一个 List 结构来保存日志的文章开头下标，即除去标识符和一个空格，例如：日志 "a1 9 2 3 1" 我们保存它的下标为3，其它的日志也是相同的道理。保存后在转成一个 Object[] 数组，因为对 List 不是很熟练而且 List 不支持下标访问，所以使用了这个方法来简化后面的操作。然后就是排序了，我这里使用的排序方法类似于插入排序：就是抽取一本日志，然后在把这本日志合适的插入已经排好序的日志堆里。排序遍历的时候需要注意的几个问题：

拿到的日志是那种日志
日志插在哪个位置才合适
要如何处理逻辑关系

解题代码：

class Solution {

	public static String[] reorderLogFiles(String[] logs){

		List<Integer>recodeIndex = new ArrayList<>();

		for(String log : logs) {

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

				if(log.charAt(i) == ' ') {

					recodeIndex.add(i + 1);

					break;

				}

			}

		}

		Object[] recode = recodeIndex.toArray();

		for(int i = 0; i < logs.length; i++) {//遍历logs

			if(logs[i].charAt((int) recode[i])>='0'&&logs[i].charAt((int) recode[i])<='9')continue;

			int insert = i;

			int numCount = 0;

			for(int j = 0; j < i; j++) {//遍历已排序好的logs

				if(logs[j].charAt((int) recode[j])>='0'&&logs[j].charAt((int) recode[j])<='9')

				{numCount++;continue;}//判断是否为数字日志

				int len = logs[j].length();//另一本日志的长度

				int sortIndex = (int) recode[j];//另一本日志的开头位置

				for(int k = (int) recode[i]; k < logs[i].length(); k++) {//寻找插入位

					if(len < k || logs[i].charAt(k) > logs[j].charAt(sortIndex)){break;}

					else if(logs[i].charAt(k) == logs[j].charAt(sortIndex)) {sortIndex++;continue;}

					else {insert = j;break;}

				}

				if(insert < i)break;

			}

			int tempIndex = recodeIndex.get(i);

			String temp = new String(logs[i]);

			for(int l = i;l > insert - numCount; l--) {

				logs[l] = logs[l - 1];

				recode[l] = recode[l - 1];

			}

			logs[insert - numCount] = temp;//同时不要忘记交换对应的日志开头下标数组

			recode[insert - numCount] = tempIndex;

		}

		return logs;

	}

}

解题结果：

过程感悟：

我在编写算法的过程中一部分时间浪费在忘记处理 recode 数组上了，调试后才发现问题，在一个就是交换的 for 循环的循环次数和上下界，当时由于代码的逻辑混乱造成了一些失误，现在的代码是我简化后的结果，当然可以再次简化。或许这道题可以使用哈希表或者队列来解决。

附记：lambda表达式

巴特西