脚撕LeetCode(937)Easy
脚撕LeetCode(937)Easy
JathonKatu
发布于 2021-07-14 15:32:18
发布于 2021-07-14 15:32:18
题目地址：https://leetcode-cn.com/problems/reorder-data-in-log-files/
给你一个日志数组 logs。每条日志都是以空格分隔的字串，其第一个字为字母与数字混合的 标识符 。 有两种不同类型的日志： 字母日志：除标识符之外，所有字均由小写字母组成 数字日志：除标识符之外，所有字均由数字组成 请按下述规则将日志重新排序：所有 字母日志 都排在 数字日志 之前。 字母日志 在内容不同时，忽略标识符后，按内容字母顺序排序；在内容相同时，按标识符排序。 数字日志 应该保留原来的相对顺序。返回日志的最终顺序。
示例 1： 输入：logs = ["dig1 8 1 5 1","let1 art can","dig2 3 6","let2 own kit dig","let3 art zero"] 输出：["let1 art can","let3 art zero","let2 own kit dig","dig1 8 1 5 1","dig2 3 6"] 解释：字母日志的内容都不同，所以顺序为 "art can", "art zero", "own kit dig" 。数字日志保留原来的相对顺序 "dig1 8 1 5 1", "dig2 3 6" 。
示例 2： 输入：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"] 提示： 1 <= logs.length <= 100 3 <= logs[i].length <= 100 logs[i] 中，字与字之间都用 单个 空格分隔 题目数据保证 logs[i] 都有一个标识符，并且在标识符之后至少存在一个
题目意思：给你一个字符串数组，重新排序，字符串的第一个空格之前的为标识位，后面的为内容，标识位是小写字母+数字，内容只能是纯数字或者纯小写字母。
让你将内容纯数字的放在最后（纯数字的字符串之间保持原来的顺序），纯字母的按照内容排序，如果内容一致就按照标识符排序。字符串中一定会有标识符和内容。
一、爆破法
爆破法很简单，将纯数字的内容放进一个list里面排序。纯字母内容的放入map，key为内容，value为Set，Set的内容为整个字符串。我们利用TreeMap的有序性，String提供的compareTo方法与题目要求一致，所以直接用TreeMap和TreeSet就可以。
执行结果如下：
64 / 64 个通过测试用例
状态：通过
执行用时: 5 ms
内存消耗: 38.6 MB
public String[] reorderLogFilesMe(String[] logs) {
Map<String, Set<String>> map = new TreeMap<>();
List<String> numlist = new ArrayList<>();
int item;
for (String log : logs) {
item = log.indexOf(" ") + 1;
if (log.charAt(item) <= '9') {
numlist.add(log);
} else {
Set<String> set;
String substring = log.substring(item);
if((set = map.get(substring)) == null) {
set = new TreeSet<>();
map.put(substring,set);
}
set.add(log);
}
}
item = 0;
for (Map.Entry<String,Set<String>> entry : map.entrySet()) {
Set<String> value = entry.getValue();
for (String s : value) {
logs[item++] = s;
}
}
for (int i = 0; i < numlist.size(); i++) {
logs[item++] = numlist.get(i);
}
return logs;
}不出意外的双85，用了集合太多就注定时间和内存得分都高不了。
优化一下，我们不用TreeSet，改用list，然后取出来的时候转数组再sort
二、Map-List法
执行结果如下：
64 / 64 个通过测试用例
状态：通过
执行用时: 5 ms
内存消耗: 38.3 MB
public static String[] reorderLogFilesMe(String[] logs) {
Map<String, List<String>> map = new TreeMap<>();
List<String> numlist = new ArrayList<>();
int item;
for (String log : logs) {
item = log.indexOf(" ") + 1;
if (log.charAt(item) <= '9') {
numlist.add(log);
} else {
List<String> set;
String substring = log.substring(item);
if((set = map.get(substring)) == null) {
set = new ArrayList<>();
map.put(substring,set);
}
set.add(log);
}
}
item = 0;
for (Map.Entry<String,List<String>> entry : map.entrySet()) {
List<String> value = entry.getValue();
String[] ar = value.toArray(new String[value.size()]);
Arrays.sort(ar);
for (String s : ar) {
logs[item++] = s;
}
}
for (int i = 0; i < numlist.size(); i++) {
logs[item++] = numlist.get(i);
}
return logs;
}时间90，内存98，行吧，看看还能不能优化一下。
三、魔改TreeSet法
这个方法主要是魔改了一下Comparator，自己根据规则写了一个compare方法，数字部分还是不变的
执行结果如下：
64 / 64 个通过测试用例
状态：通过
执行用时: 4 ms
内存消耗: 38.3 MB
public static String[] reorderLogFilesMe(String[] logs) {
Set<String> set = new TreeSet<>(
new Comparator<String>() {
@Override
public int compare(String o1, String o2) {
String subString1 = o1.substring(o1.indexOf(" ") + 1);
String subString2 = o2.substring(o2.indexOf(" ") + 1);
return subString1.compareTo(subString2) != 0 ? subString1.compareTo(subString2) : o1.compareTo(o2);
}
}
);
List<String> numlist = new ArrayList<>();
int item;
for (String log : logs) {
item = log.indexOf(" ") + 1;
if (log.charAt(item) <= '9') {
numlist.add(log);
} else {
set.add(log);
}
}
item = 0;
for (String string : set) {
logs[item++] = string;
}
for (int i = 0; i < numlist.size(); i++) {
logs[item++] = numlist.get(i);
}
return logs;
}时间90，内存97，emmmmmmmmmm这也不行？用了一个set 没有用map也不行？
那我zhou？
算了还是看看有没有更好的办法。
四、官方方法，Arrays.sort魔改
执行结果如下：
64 / 64 个通过测试用例
状态：通过
执行用时: 7 ms
内存消耗: 38.9 MB
public String[] reorderLogFiles(String[] logs) {
Arrays.sort(logs, (log1, log2) -> {
String[] split1 = log1.split(" ", 2);
String[] split2 = log2.split(" ", 2);
boolean isDigit1 = Character.isDigit(split1[1].charAt(0));
boolean isDigit2 = Character.isDigit(split2[1].charAt(0));
if (!isDigit1 && !isDigit2) {
int cmp = split1[1].compareTo(split2[1]);
if (cmp != 0) return cmp;
return split1[0].compareTo(split2[0]);
}
return isDigit1 ? (isDigit2 ? 0 : 1) : -1;
});
return logs;
}内存75，时间56，看起来骚的一批的代码居然还不如我自己的。。。。诶。。。转战评论区
不过这里也看出了我对Arrays的api不是特别特别熟悉
五、评论区大佬接近双百法
具体思路是，归并排序（分治算法）
通过分治把数字内容放在后面，把英文内容放在前面，如果两个都是数字就不改变方式。
循环英文内容，逐个char对比，如果英文内容都一致就对比标识符。
执行结果如下：
64 / 64 个通过测试用例
状态：通过
执行用时: 2 ms
内存消耗: 38.4 MB
public String[] reorderLogFiles(String[] logs) {
if(logs.length <= 1){
return logs;
}
return mergeSort(logs, 0, logs.length-1);
}
private String[] mergeSort(String[] logs, int left, int right){
if(left == right){
return new String[]{logs[left]};
}
int mid = (left+right)/2;
String[] leftRes = mergeSort(logs, left, mid);
String[] rightRes = mergeSort(logs, mid+1, right);
return merge(leftRes, rightRes);
}
private String[] merge(String[] a, String[] b){
String[] res = new String[a.length + b.length];
int aIndex = 0;
int bIndex = 0;
int rIndex = 0;
while(aIndex < a.length && bIndex < b.length){
if(compare(a[aIndex], b[bIndex])){//在此处调用自定义比较方法
res[rIndex] = a[aIndex];
aIndex++;
}else{
res[rIndex] = b[bIndex];
bIndex++;
}
rIndex++;
}
while(aIndex<a.length){
res[rIndex++] = a[aIndex++];
}
while(bIndex<b.length){
res[rIndex++] = b[bIndex++];
}
return res;
}
private boolean compare(String one, String two){
//如果String one应该出现在String two前面，则返回true，否则返回false
char a=' ',b=' ';//a,b代表两个String中第一个有效数据的内容
int x=0,y=0;//x,y代表两个String中第一个有效数据所在index。for(int i=0; i<one.length();i++){
if(one.charAt(i) == ' '){
x = i+1;
a = one.charAt(i+1);
break;
}
}
for(int i=0; i<two.length();i++){
if(two.charAt(i) == ' '){
y=i+1;
b = two.charAt(i+1);
break;
}
}
if((a<'0' || a>'9') && (b<'0'||b>'9')){
//如果ab均为字符，则逐个比较每个有效数据，
while(x<one.length() || y<two.length()){
char temp1,temp2;
if(x<one.length()){
temp1 = one.charAt(x);
x++;
}else{
temp1 = ' ';
}
if(y<two.length()){
temp2 = two.charAt(y);
y++;
}else{
temp2 = ' ';
}
if(temp1 < temp2){
return true;
}else if(temp1>temp2){
return false;
}
}
//如果有效数据全都相等，则比较标识符。if(x == one.length() && y == two.length()){
return one.charAt(0) <= two.charAt(0);
}
}else if(b<'0'||b>'9'){//如果b是字符a不是返回false
return false;
}
return true;//如果a是字符b不是，或者ab都是数字，返回true
}不得不说，大佬写的比较细，最重要的是人家想到了用分治但是我却什么都没用。
想来也是，如果想内存占用低和时间快，还是尽可能考虑能不能尽量的用数组比较好。
后续应该加强一下排序算法这块的内容。加上之前的树和图。（我怎么感觉我什么都不会了hhhh）
那么，next。
本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2021-06-16，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
