Java 遍历 HashMap 的方式，深度优先搜索（三色标记法）和广度优先搜索 2 种方法拓扑排序：求解《269. 火星词典》和《剑指 Offer II 114. 外星文字典》
2022-05-31 20:28:02
Java 遍历 HashMap 的方式，深度优先搜索（三色标记法）和广度优先搜索，拓扑排序的 2 种方法，求解《269. 火星词典》和《剑指 Offer II 114. 外星文字典》
Java 遍历 HashMap 的方式
Map<Integer, String> map = new HashMap();
map.put(1, "1")
map.put(2, "2")<br>map.put(3, "3")Iterator
Iterator - KeySet
Iterator<Integer> iterator = map.keySet().iterator();
while (iterator.hasNext()) {
Integer key = iterator.next();
System.out.print(key);
System.out.print(map.get(key));
}Iterator - EntrySet
Iterator<Map.Entry<Integer, String>> iterator = map.entrySet().iterator();
while (iterator.hasNext()) {
Map.Entry<Integer, String> iterator = map.entrySet().iterator();
while (iterator.hasNext()) {
Map.Entry<Integer, String> entry = iterator.next();
System.out.print(entry.getKey());
System.out.print(entry.getValue());
}
}For
For - KeySet
for (Integer key : map.keySet()) {<br> System.out.print(key);
System.out.print(map.get(key));
}For - EntrySet
for (Map.Entry<Integer, String> entry : map.entrySet()) {<br> System.out.print(entry.getKey());
System.out.print(entry.getValue());<br>}Lambda
map.forEach((key, value) -> {
System.out.print(key);
System.out.print(value);
});Streams API
Streams API - KeySet
map.entrySet().stream().forEach((entry) -> {
System.out.print(entry.getKey());
System.out.print(entry.getValue());
});Streams API - EntrySet
map.entrySet().parallelStream().forEach((entry) -> {
System.out.print(entry.getKey());
System.out.print(entry.getValue());
})例题
269. 火星词典
剑指 Offer II 114. 外星文字典
现有一种使用英语字母的火星语言，这门语言的字母顺序与英语顺序不同。
给你一个字符串列表 words ，作为这门语言的词典，words 中的字符串已经 按这门新语言的字母顺序进行了排序 。
请你根据该词典还原出此语言中已知的字母顺序，并 按字母递增顺序 排列。若不存在合法字母顺序，返回 "" 。若存在多种可能的合法字母顺序，返回其中 任意一种 顺序即可。
字符串 s 字典顺序小于 字符串 t 有两种情况：
在第一个不同字母处，如果 s 中的字母在这门外星语言的字母顺序中位于 t 中字母之前，那么 s 的字典顺序小于 t 。
如果前面 min(s.length, t.length) 字母都相同，那么 s.length < t.length 时，s 的字典顺序也小于 t 。
示例 1：
输入：words = ["wrt","wrf","er","ett","rftt"]
输出："wertf"
答案
拓扑排序 · 深度优先搜索
var alienOrder = function(words) { // Object 实现
const n = words.length, grah = Object.create(null)
for (let i = 0; i < n; i++) {
for (let j = 0, m = words[i].length; j < m; j++) {
if (grah[words[i][j]] === void 0) grah[words[i][j]] = []
}
}
const addEdge = (a, b) => {
const length = Math.min(a.length, b.length)
let i = -1
while (++i < length) {
if (a[i] !== b[i]) {
grah[a[i]].push(b[i])
break
}
}
return i < length || a.length <= b.length
}
for (let i = 1; i < n; i++) if (addEdge(words[i - 1], words[i]) === false) return ''
const r = [], visited = new Uint8Array(26)
let valid = true
;(function d (edges) {
if (edges === void 0) return
const n = edges.length
for (let i = 0; i < n; i++) {
const edge = edges[i], edgeCode = edge.charCodeAt() - 97
if (visited[edgeCode] === 1) return valid = false
if (visited[edgeCode] === 2) continue
visited[edgeCode] = 1
d(grah[edge])
visited[edgeCode] = 2
r.unshift(edge)
}
})(Object.keys(grah))
return valid ? r.join('') : ''
};function alienOrder(words: string[]): string { // Map 实现
const n = words.length, grah = new Map<string, string[]>()
for (let i = 0; i < n; i++) {
for (let j = 0, word = words[i], m = word.length; j < m; j++) {
grah.set(word[j], [])
}
}
const addEdge = (prev, next) => {
const length = Math.min(prev.length, next.length)
let i = -1
while (++i < length) {
if (prev[i] !== next[i]) {
grah.get(prev[i]).push(next[i])
break
}
}
return i < length || prev.length <= next.length
}
for (let i = 1; i < n; i++) if (addEdge(words[i - 1], words[i]) === false) return ''
const visited = new Uint8Array(26), r = []
let valid = true
;(function d(edges) {
if (edges === void 0) return
for (let i = 0, m = edges.length; i < m; i++) {
const edge = edges[i], edgeCode = edge.charCodeAt(0) - 97
if (visited[edgeCode] === 1) return valid = false
if (visited[edgeCode] === 2) continue
visited[edgeCode] = 1
d(grah.get(edge))
visited[edgeCode] = 2
r.unshift(edge)
}
})(Array.from(grah.keys()))
return valid ? r.join('') : ''
};class Solution {
private $grah = array();
private $visited = array();
private $valid = true;
private $r = array();
function alienOrder($words) {
$n = count($words);
$grah = array();
foreach ($words as $i => $word) {
$m = strlen($word);
for ($j = 0; $j < $m; $j++) {
$this->grah[$word[$j]] = array();
}
}
for ($i = 1; $i < $n; $i++) if ($this->addEdge($words[$i - 1], $words[$i]) === false) return '';
$this->d(array_keys($this->grah));
return $this->valid ? implode('', $this->r) : '';
}
function addEdge($prev, $next) {
$prevLength = strlen($prev);
$nextLength = strlen($next);
$length = min($prevLength, $nextLength);
$i = -1;
while (++$i < $length) {
if ($prev[$i] !== $next[$i]) {
$this->grah[$prev[$i]] []= $next[$i];
break;
}
}
return $i < $length || $prevLength <= $nextLength;
}
function d($edges) {
if ($edges === null) return;
foreach ($edges as $edge) {
if ($this->visited[$edge] === 1) return $this->valid = false;
if ($this->visited[$edge] === 2) continue;
$this->visited[$edge] = 1;
$this->d($this->grah[$edge]);
$this->visited[$edge] = 2;
array_unshift($this->r, $edge);
}
}
}func alienOrder(words []string) string {
n, grah := len(words), map[byte][]byte{}
for _, word := range words {
for i, m := 0, len(word); i < m; i++ {
grah[word[i]] = []byte{}
}
}
var addEdge func(prev string, next string) bool
addEdge = func(prev string, next string) bool {
prevLength, nextLength := len(prev), len(next)
length := min(prevLength, nextLength)
i := 0
for i < length {
if prev[i] != next[i] {
grah[prev[i]] = append(grah[prev[i]], next[i])
break
}
i++
}
return i < length || prevLength <= nextLength
}
for i := 1; i < n; i++ {
if addEdge(words[i - 1], words[i]) == false {
return ""
}
}
visited, valid, r := [26]int{}, true, []byte{}
var d func(edges []byte)
d = func(edges []byte) {
if len(edges) == 0 {
return
}
for _, edge := range edges {
edgeCode := edge - 97
if visited[edgeCode] == 1 {
valid = false
return
}
if visited[edgeCode] == 2 {
continue
}
visited[edgeCode] = 1
d(grah[edge])
visited[edgeCode] = 2
r = append([]byte{edge}, r...)
}
}
edges := []byte{}
for key := range grah {
edges = append(edges, key)
}
d(edges)
if valid {
return string(r)
}
return ""
}
func min(a int, b int) int {
if a < b {
return a
}
return b
}class Solution {
private Map<Character, List<Character>> grah = new HashMap<Character, List<Character>>();
private int visited[] = new int[26];
private boolean valid = true;
private StringBuilder r = new StringBuilder();
public String alienOrder(String[] words) {
int n = words.length;
for (String word : words) {
for (int j = 0, m = word.length(); j < m; j++) {
grah.put(word.charAt(j), new ArrayList<Character>());
}
}
for (int i = 1; i < n; i++) if (addEdge(words[i - 1], words[i]) == false) return "";
d(new ArrayList(grah.keySet()));
return valid ? r.toString() : "";
}
public boolean addEdge(String prev, String next) {
int length = Math.min(prev.length(), next.length());
int i = -1;
while (++i < length) {
if (prev.charAt(i) != next.charAt(i)) {
grah.get(prev.charAt(i)).add(next.charAt(i));
break;
}
}
return i < length || prev.length() <= next.length();
}
public void d(List<Character> edges) {
if (edges.size() == 0) return;
for (Character edge : edges) {
int edgeCode = (int) edge - 97;
if (visited[edgeCode] == 1) {
valid = false;
return;
}
if (visited[edgeCode] == 2) continue;
visited[edgeCode] = 1;
d(grah.get(edge));
visited[edgeCode] = 2;
r.insert(0, edge);
}
}
}class Solution:
def alienOrder(self, words: List[str]) -> str:
n, grah = len(words), {}
for i in range(0, n):
for _, char in enumerate(words[i]):
grah[char] = []
def addEdge(prev, next):
length, i = min(len(prev), len(next)), 0
while i < length:
if prev[i] != next[i]:
grah[prev[i]].append(next[i])
break
i += 1
return i < length or len(prev) <= len(next)
for i in range(1, n):
if addEdge(words[i - 1], words[i]) == False: return ""
visited, valid, r = [0] * 26, [True], []
def d(edges):
if len(edges) == 0: return
for _, edge in enumerate(edges):
edgeCode = ord(edge) - 97
if visited[edgeCode] == 1:
valid[0] = False
return
if visited[edgeCode] == 2: continue
visited[edgeCode] = 1
d(grah[edge])
visited[edgeCode] = 2
r.insert(0, edge)
d(grah.keys())
return "".join(r) if valid[0] else "" 拓扑排序 · 广度优先搜索
var alienOrder = function(words) { // Object 实现
const n = words.length, grah = Object.create(null), degree = new Uint8Array(26)
for (let i = 0; i < n; i++) {
for (let j = 0, word = words[i], m = word.length; j < m; j++) {
if (grah[word[j]] === void 0) grah[word[j]] = []
}
}
const addEdge = (a, b) => {
const length = Math.min(a.length, b.length)
let i = -1
while (++i < length) {
if (a[i] !== b[i]) {
grah[a[i]].push(b[i])
degree[b.charCodeAt(i) - 97]++
break
}
}
return i < length || a.length <= b.length
}
for (let i = 1; i < n; i++) if (addEdge(words[i - 1], words[i]) === false) return ''
const keys = Object.keys(grah), q = [], r = []
for(let i = 0, m = keys.length; i < m; i++) if (degree[keys[i].charCodeAt() - 97] === 0) q.push(keys[i])
while (q.length) {
const edge = q.shift()
r.push(edge)
for (let i = 0; i < grah[edge].length; i++) {
if (--degree[grah[edge][i].charCodeAt() - 97] === 0) q.push(grah[edge][i])
}
}
return r.length === keys.length ? r.join('') : ''
};function alienOrder(words: string[]): string {
const n = words.length, grah = new Map<string, string[]>(), degree = new Uint8Array(26)
for (let i = 0; i < n; i++) {
for (let j = 0, word = words[i], m = word.length; j < m; j++) {
grah.set(word[j], [])
}
}
const addEdge = (prev, next) => {
const length = Math.min(prev.length, next.length)
let i = -1
while (++i < length) {
if (prev[i] !== next[i]) {
grah.get(prev[i]).push(next[i])
degree[next.charCodeAt(i) - 97]++
break
}
}
return i < length || prev.length <= next.length
}
for (let i = 1; i < n; i++) if (addEdge(words[i - 1], words[i]) === false) return ''
const iterator = grah.keys(), q = []
let p = iterator.next(), count = 0, r = ''
while (p.done === false) {
if (degree[p.value.charCodeAt(0) - 97] === 0) q.push(p.value)
p = iterator.next()
count++
}
while (q.length) {
const edge = q.shift()
r += edge
for (let i = 0, a = grah.get(edge), m = a.length; i < m; i++) {
if (--degree[a[i].charCodeAt(0) - 97] === 0) q.push(a[i])
}
}
return count === r.length ? r : ''
};class Solution {
private $grah = array();
private $degree = array();
function alienOrder($words) {
$n = count($words);
$grah = array();
foreach ($words as $i => $word) {
$m = strlen($word);
for ($j = 0; $j < $m; $j++) {
$this->grah[$word[$j]] = array();
}
}
$this->degree = array_fill(0, 26, 0);
for ($i = 1; $i < $n; $i++) if ($this->addEdge($words[$i - 1], $words[$i]) === false) return '';
$q = [];
$r = '';
foreach (array_keys($this->grah) as $edge) {
if ($this->degree[ord($edge) - 97] === 0) $q []= $edge;
}
while (count($q) > 0) {
$edge = array_shift($q);
$r .= $edge;
foreach ($this->grah[$edge] as $v) {
if (--$this->degree[ord($v) - 97] === 0) $q []= $v;
}
}
return count($this->grah) === strlen($r) ? $r : '';
}
function addEdge($prev, $next) {
$prevLength = strlen($prev);
$nextLength = strlen($next);
$length = min($prevLength, $nextLength);
$i = -1;
while (++$i < $length) {
if ($prev[$i] !== $next[$i]) {
$this->grah[$prev[$i]] []= $next[$i];
$this->degree[ord($next[$i]) - 97]++;
break;
}
}
return $i < $length || $prevLength <= $nextLength;
}
}func alienOrder(words []string) string {
n, grah, degree := len(words), map[byte][]byte{}, [26]int{}
for _, word := range words {
for i, m := 0, len(word); i < m; i++ {
grah[word[i]] = []byte{}
}
}
var addEdge func(prev string, next string) bool
addEdge = func(prev string, next string) bool {
prevLength, nextLength := len(prev), len(next)
length := min(prevLength, nextLength)
i := 0
for i < length {
if prev[i] != next[i] {
grah[prev[i]] = append(grah[prev[i]], next[i])
degree[next[i] - 97]++
break
}
i++
}
return i < length || prevLength <= nextLength
}
for i := 1; i < n; i++ {
if addEdge(words[i - 1], words[i]) == false {
return ""
}
}
q, r := []byte{}, []byte{}
for key := range grah {
if degree[key - 97] == 0 {
q = append(q, key)
}
}
for len(q) > 0 {
edge := q[0]
q = q[1:]
r = append(r, edge)
for _, v := range grah[edge] {
degree[v - 97]--
if degree[v - 97] == 0 {
q = append(q, v)
}
}
}
if len(grah) == len(r) {
return string(r)
}
return ""
}
func min(a, b int) int {
if a < b {
return a
}
return b
}class Solution {
private Map<Character, List<Character>> grah = new HashMap<Character, List<Character>>();
private int degree[] = new int[26];
private StringBuilder r = new StringBuilder();
public String alienOrder(String[] words) {
int n = words.length;
for (String word : words) {
for (int j = 0, m = word.length(); j < m; j++) {
grah.put(word.charAt(j), new ArrayList<Character>());
}
}
for (int i = 1; i < n; i++) if (addEdge(words[i - 1], words[i]) == false) return "";
Deque<Character> q = new ArrayDeque<Character>();
for (Character key : grah.keySet()) {
if (degree[(int)key - 97] == 0) q.add(key);
}
while (q.isEmpty() == false) {
Character edge = q.poll();
r.append(edge);
for (Character v : grah.get(edge)) {
if (--degree[(int)v - 97] == 0) q.add(v);
}
}
return grah.size() == r.length() ? r.toString() : "";
}
public boolean addEdge(String prev, String next) {
int length = Math.min(prev.length(), next.length());
int i = -1;
while (++i < length) {
if (prev.charAt(i) != next.charAt(i)) {
grah.get(prev.charAt(i)).add(next.charAt(i));
degree[(int)next.charAt(i) - 97]++;
break;
}
}
return i < length || prev.length() <= next.length();
}
}class Solution:
def alienOrder(self, words: List[str]) -> str:
n, grah, degrees = len(words), {}, [0] * 26
for i in range(0, n):
for _, char in enumerate(words[i]):
grah[char] = []
def addEdge(prev, next):
length, i = min(len(prev), len(next)), 0
while i < length:
if prev[i] != next[i]:
grah[prev[i]].append(next[i])
degrees[ord(next[i]) - 97] += 1
break
i += 1
return i < length or len(prev) <= len(next)
for i in range(1, n):
if addEdge(words[i - 1], words[i]) == False: return ""
q, r = [], ''
for key in grah.keys():
if degrees[ord(key) - 97] == 0: q.append(key)
while len(q) > 0:
edge = q.pop(0)
r += edge
for _, v in enumerate(grah[edge]):
degrees[ord(v) - 97] -= 1
if degrees[ord(v) - 97] == 0: q.append(v)
return r if len(grah) == len(r) else ""