0 like 0 dislike
4,432 views

edited | 4,432 views

0 like 0 dislike

You are given an array of `logs`. Each log is a space-delimited string of words, where the first word is the identifier.

There are two types of logs:

• Letter-logs: All words (except the identifier) consist of lowercase English letters.
• Digit-logs: All words (except the identifier) consist of digits.

Reorder these logs so that:

1. The letter-logs come before all digit-logs.
2. The letter-logs are sorted lexicographically by their contents. If their contents are the same, then sort them lexicographically by their identifiers.
3. The digit-logs maintain their relative ordering.

Return the final order of the logs.

Example 1:

```Input: logs = ["dig1 8 1 5 1","let1 art can","dig2 3 6","let2 own kit dig","let3 art zero"]
Output: ["let1 art can","let3 art zero","let2 own kit dig","dig1 8 1 5 1","dig2 3 6"]
Explanation:
The letter-log contents are all different, so their ordering is "art can", "art zero", "own kit dig".
The digit-logs have a relative order of "dig1 8 1 5 1", "dig2 3 6".
```

Example 2:

```Input: logs = ["a1 9 2 3 1","g1 act car","zo4 4 7","ab1 off key dog","a8 act zoo"]
Output: ["g1 act car","a8 act zoo","ab1 off key dog","a1 9 2 3 1","zo4 4 7"]
```

Constraints:

• `1 <= logs.length <= 100`
• `3 <= logs[i].length <= 100`
• All the tokens of `logs[i]` are separated by a single space.
• `logs[i]` is guaranteed to have an identifier and at least one word after the identifier.
``````public String[] reorderLogFiles(String[] logs) {

Comparator<String> myComp = new Comparator<String>() {
@Override
public int compare(String s1, String s2) {
int s1SpaceIndex = s1.indexOf(' ');
int s2SpaceIndex = s2.indexOf(' ');
char s1FirstCharacter = s1.charAt(s1SpaceIndex+1);
char s2FirstCharacter = s2.charAt(s2SpaceIndex+1);

if (s1FirstCharacter <= '9') {
if (s2FirstCharacter <= '9') return 0;
else return 1;
}
if (s2FirstCharacter <= '9') return -1;

int preCompute = s1.substring(s1SpaceIndex+1).compareTo(s2.substring(s2SpaceIndex+1));
if (preCompute == 0) return s1.substring(0,s1SpaceIndex).compareTo(s2.substring(0,s2SpaceIndex));
return preCompute;
}
};

Arrays.sort(logs, myComp);
return logs;
}``````

by Expert (113,040 points)
0 like 0 dislike

You are given an undirected graph. You are given an integer `n` which is the number of nodes in the graph and an array `edges`, where each `edges[i] = [ui, vi]` indicates that there is an undirected edge between `ui` and `vi`.

connected trio is a set of three nodes where there is an edge between every pair of them.

The degree of a connected trio is the number of edges where one endpoint is in the trio, and the other is not.

Return the minimum degree of a connected trio in the graph, or `-1` if the graph has no connected trios.

Example 1:

```Input: n = 6, edges = [[1,2],[1,3],[3,2],[4,1],[5,2],[3,6]]
Output: 3
Explanation: There is exactly one trio, which is [1,2,3]. The edges that form its degree are bolded in the figure above.
```

Example 2:

```Input: n = 7, edges = [[1,3],[4,1],[4,3],[2,5],[5,6],[6,7],[7,5],[2,6]]
Output: 0
Explanation: There are exactly three trios:
1) [1,4,3] with degree 0.
2) [2,5,6] with degree 2.
3) [5,6,7] with degree 2.
```

Constraints:

• `2 <= n <= 400`
• `edges[i].length == 2`
• `1 <= edges.length <= n * (n-1) / 2`
• `1 <= ui, vi <= n`
• `ui != vi`
• There are no repeated edges.

Code :

``````int minTrioDegree(int n, vector<vector<int>>& edges) {
vector<set<int>> al(n + 1);
vector<int> cnt(n + 1);
int res = INT_MAX;
for (auto &e: edges) {
al[min(e[0], e[1])].insert(max(e[0], e[1]));
++cnt[e[0]];
++cnt[e[1]];
}
for (auto t1 = 1; t1 <= n; ++t1)
for (auto it2 = begin(al[t1]); it2 != end(al[t1]); ++it2)
for (auto it3 = next(it2); it3 != end(al[t1]); ++it3)
if (al[*it2].count(*it3))
res = min(res, cnt[t1] + cnt[*it2] + cnt[*it3] - 6);
return res == INT_MAX ? -1 : res;
}``````
by Expert (113,040 points)