feat: update solutions to lc problem: No.1743

yanglbme · yanglbme · commit 201a40fd6762 · 2022-11-23T09:54:05.000+08:00
No.1743.Restore the Array From Adjacent Pairs
diff --git a/solution/1700-1799/1742.Maximum Number of Balls in a Box/README.md b/solution/1700-1799/1742.Maximum Number of Balls in a Box/README.md
@@ -60,9 +60,9 @@
 
 **方法一：数组 + 模拟**
 
-根据题意我们知道，小球的编号最大不超过 $10^5$，每个编号的各个位数之和的最大值小于 $50$，因此，我们可以用一个长度为 $50$ 的数组来统计每个编号的各个位数之和的数量。
+观察题目的数据范围，小球的编号最大不超过 $10^5$，那么每个编号的各个位数之和的最大值小于 $50$。因此，我们可以直接开一个长度为 $50$ 的数组 `cnt` 来统计每个编号的各个位数之和的数量。
 
-答案就是这个数组中的最大值。
+答案就是数组 `cnt` 中的最大值。
 
 时间复杂度 $O(n \times \log_{10}m)$。其中 $n = highLimit - lowLimit + 1$，而 $m = highLimit$。
 
@@ -94,8 +94,8 @@ class Solution {
     public int countBalls(int lowLimit, int highLimit) {
         int[] cnt = new int[50];
         for (int i = lowLimit; i <= highLimit; ++i) {
-            int x = i, y = 0;
-            for (; x > 0; x /= 10) {
+            int y = 0;
+            for (int x = i; x > 0; x /= 10) {
                 y += x % 10;
             }
             ++cnt[y];
@@ -114,8 +114,8 @@ public:
         int cnt[50] = {0};
         int ans = 0;
         for (int i = lowLimit; i <= highLimit; ++i) {
-            int x = i, y = 0;
-            for (; x; x /= 10) {
+            int y = 0;
+            for (int x = i; x; x /= 10) {
                 y += x % 10;
             }
             ans = max(ans, ++cnt[y]);
@@ -131,8 +131,8 @@ public:
 func countBalls(lowLimit int, highLimit int) (ans int) {
 	cnt := [50]int{}
 	for i := lowLimit; i <= highLimit; i++ {
-		x, y := i, 0
-		for ; x > 0; x /= 10 {
+		y := 0
+		for x := i; x > 0; x /= 10 {
 			y += x % 10
 		}
 		cnt[y]++
diff --git a/solution/1700-1799/1742.Maximum Number of Balls in a Box/README_EN.md b/solution/1700-1799/1742.Maximum Number of Balls in a Box/README_EN.md
@@ -76,8 +76,8 @@ class Solution {
     public int countBalls(int lowLimit, int highLimit) {
         int[] cnt = new int[50];
         for (int i = lowLimit; i <= highLimit; ++i) {
-            int x = i, y = 0;
-            for (; x > 0; x /= 10) {
+            int y = 0;
+            for (int x = i; x > 0; x /= 10) {
                 y += x % 10;
             }
             ++cnt[y];
@@ -96,8 +96,8 @@ public:
         int cnt[50] = {0};
         int ans = 0;
         for (int i = lowLimit; i <= highLimit; ++i) {
-            int x = i, y = 0;
-            for (; x; x /= 10) {
+            int y = 0;
+            for (int x = i; x; x /= 10) {
                 y += x % 10;
             }
             ans = max(ans, ++cnt[y]);
@@ -113,8 +113,8 @@ public:
 func countBalls(lowLimit int, highLimit int) (ans int) {
 	cnt := [50]int{}
 	for i := lowLimit; i <= highLimit; i++ {
-		x, y := i, 0
-		for ; x > 0; x /= 10 {
+		y := 0
+		for x := i; x > 0; x /= 10 {
 			y += x % 10
 		}
 		cnt[y]++
diff --git a/solution/1700-1799/1742.Maximum Number of Balls in a Box/Solution.cpp b/solution/1700-1799/1742.Maximum Number of Balls in a Box/Solution.cpp
@@ -4,8 +4,8 @@ class Solution {
         int cnt[50] = {0};
         int ans = 0;
         for (int i = lowLimit; i <= highLimit; ++i) {
-            int x = i, y = 0;
-            for (; x; x /= 10) {
+            int y = 0;
+            for (int x = i; x; x /= 10) {
                 y += x % 10;
             }
             ans = max(ans, ++cnt[y]);
diff --git a/solution/1700-1799/1742.Maximum Number of Balls in a Box/Solution.go b/solution/1700-1799/1742.Maximum Number of Balls in a Box/Solution.go
@@ -1,8 +1,8 @@
 func countBalls(lowLimit int, highLimit int) (ans int) {
 	cnt := [50]int{}
 	for i := lowLimit; i <= highLimit; i++ {
-		x, y := i, 0
-		for ; x > 0; x /= 10 {
+		y := 0
+		for x := i; x > 0; x /= 10 {
 			y += x % 10
 		}
 		cnt[y]++
diff --git a/solution/1700-1799/1742.Maximum Number of Balls in a Box/Solution.java b/solution/1700-1799/1742.Maximum Number of Balls in a Box/Solution.java
@@ -2,8 +2,8 @@ class Solution {
     public int countBalls(int lowLimit, int highLimit) {
         int[] cnt = new int[50];
         for (int i = lowLimit; i <= highLimit; ++i) {
-            int x = i, y = 0;
-            for (; x > 0; x /= 10) {
+            int y = 0;
+            for (int x = i; x > 0; x /= 10) {
                 y += x % 10;
             }
             ++cnt[y];
diff --git a/solution/1700-1799/1743.Restore the Array From Adjacent Pairs/README.md b/solution/1700-1799/1743.Restore the Array From Adjacent Pairs/README.md
@@ -93,26 +93,19 @@ class Solution:
 ```python
 class Solution:
     def restoreArray(self, adjacentPairs: List[List[int]]) -> List[int]:
-        def dfs(i):
-            if i in vis:
-                return
-            vis.add(i)
+        def dfs(i, fa):
             ans.append(i)
             for j in g[i]:
-                dfs(j)
+                if j != fa:
+                    dfs(j, i)
 
         g = defaultdict(list)
         for a, b in adjacentPairs:
             g[a].append(b)
             g[b].append(a)
+        i = next(i for i, v in g.items() if len(v) == 1)
         ans = []
-        vis = set()
-        start = -1
-        for i, v in g.items():
-            if len(v) == 1:
-                start = i
-                break
-        dfs(start)
+        dfs(i, 1e6)
         return ans
 ```
 
@@ -149,103 +142,37 @@ class Solution {
 
 ```java
 class Solution {
+    private Map<Integer, List<Integer>> g = new HashMap<>();
+    private int[] ans;
+
     public int[] restoreArray(int[][] adjacentPairs) {
-        int n = adjacentPairs.length + 1;
-        Map<Integer, List<Integer>> g = new HashMap<>();
-        for (int[] e : adjacentPairs) {
+        for (var e : adjacentPairs) {
             int a = e[0], b = e[1];
             g.computeIfAbsent(a, k -> new ArrayList<>()).add(b);
             g.computeIfAbsent(b, k -> new ArrayList<>()).add(a);
         }
-        List<Integer> ans = new ArrayList<>();
-        Set<Integer> vis = new HashSet<>();
-        int start = -1;
-        for (Map.Entry<Integer, List<Integer>> entry : g.entrySet()) {
-            if (entry.getValue().size() == 1) {
-                start = entry.getKey();
+        int n = adjacentPairs.length + 1;
+        ans = new int[n];
+        for (var e : g.entrySet()) {
+            if (e.getValue().size() == 1) {
+                dfs(e.getKey(), 1000000, 0);
                 break;
             }
         }
-        dfs(g, ans, vis, start);
-        return ans.stream().mapToInt(Integer::valueOf).toArray();
+        return ans;
     }
 
-    private void dfs(Map<Integer, List<Integer>> g, List<Integer> ans, Set<Integer> vis, int i) {
-        if (vis.contains(i)) {
-            return;
-        }
-        vis.add(i);
-        ans.add(i);
+    private void dfs(int i, int fa, int k) {
+        ans[k++] = i;
         for (int j : g.get(i)) {
-            dfs(g, ans, vis, j);
+            if (j != fa) {
+                dfs(j, i, k);
+            }
         }
     }
 }
 ```
 
-### **Go**
-
-```go
-func restoreArray(adjacentPairs [][]int) []int {
-	n := len(adjacentPairs) + 1
-	g := map[int][]int{}
-	for _, e := range adjacentPairs {
-		a, b := e[0], e[1]
-		g[a] = append(g[a], b)
-		g[b] = append(g[b], a)
-	}
-	ans := make([]int, n)
-	for k, v := range g {
-		if len(v) == 1 {
-			ans[0] = k
-			ans[1] = v[0]
-			break
-		}
-	}
-	for i := 2; i < n; i++ {
-		v := g[ans[i-1]]
-		ans[i] = v[0]
-		if v[0] == ans[i-2] {
-			ans[i] = v[1]
-		}
-	}
-	return ans
-}
-```
-
-```go
-func restoreArray(adjacentPairs [][]int) []int {
-	g := map[int][]int{}
-	for _, e := range adjacentPairs {
-		a, b := e[0], e[1]
-		g[a] = append(g[a], b)
-		g[b] = append(g[b], a)
-	}
-	ans := []int{}
-	vis := map[int]bool{}
-	var start int
-	for i, v := range g {
-		if len(v) == 1 {
-			start = i
-			break
-		}
-	}
-	var dfs func(i int)
-	dfs = func(i int) {
-		if vis[i] {
-			return
-		}
-		vis[i] = true
-		ans = append(ans, i)
-		for _, j := range g[i] {
-			dfs(j)
-		}
-	}
-	dfs(start)
-	return ans
-}
-```
-
 ### **C++**
 
 ```cpp
@@ -280,37 +207,91 @@ public:
 class Solution {
 public:
     vector<int> restoreArray(vector<vector<int>>& adjacentPairs) {
-        int n = adjacentPairs.size() + 1;
         unordered_map<int, vector<int>> g;
         for (auto& e : adjacentPairs) {
             int a = e[0], b = e[1];
-            g[a].push_back(b);
-            g[b].push_back(a);
+            g[a].emplace_back(b);
+            g[b].emplace_back(a);
         }
+        int n = adjacentPairs.size() + 1;
         vector<int> ans;
-        unordered_set<int> vis;
-        int start = -1;
-        for (auto& [k, v] : g) {
+        function<void(int, int)> dfs = [&](int i, int fa) {
+            ans.emplace_back(i);
+            for (int& j : g[i]) {
+                if (j != fa) {
+                    dfs(j, i);
+                }
+            }
+        };
+        for (auto& [i, v] : g) {
             if (v.size() == 1) {
-                start = k;
+                dfs(i, 1e6);
                 break;
             }
         }
-        dfs(g, ans, vis, start);
         return ans;
     }
-
-    void dfs(unordered_map<int, vector<int>>& g, vector<int>& ans, unordered_set<int>& vis, int i) {
-        if (vis.count(i)) return;
-        ans.push_back(i);
-        vis.insert(i);
-        for (int j : g[i]) {
-            dfs(g, ans, vis, j);
-        }
-    }
 };
 ```
 
+### **Go**
+
+```go
+func restoreArray(adjacentPairs [][]int) []int {
+	n := len(adjacentPairs) + 1
+	g := map[int][]int{}
+	for _, e := range adjacentPairs {
+		a, b := e[0], e[1]
+		g[a] = append(g[a], b)
+		g[b] = append(g[b], a)
+	}
+	ans := make([]int, n)
+	for k, v := range g {
+		if len(v) == 1 {
+			ans[0] = k
+			ans[1] = v[0]
+			break
+		}
+	}
+	for i := 2; i < n; i++ {
+		v := g[ans[i-1]]
+		ans[i] = v[0]
+		if v[0] == ans[i-2] {
+			ans[i] = v[1]
+		}
+	}
+	return ans
+}
+```
+
+```go
+func restoreArray(adjacentPairs [][]int) []int {
+	g := map[int][]int{}
+	for _, e := range adjacentPairs {
+		a, b := e[0], e[1]
+		g[a] = append(g[a], b)
+		g[b] = append(g[b], a)
+	}
+	ans := []int{}
+	var dfs func(i, fa int)
+	dfs = func(i, fa int) {
+		ans = append(ans, i)
+		for _, j := range g[i] {
+			if j != fa {
+				dfs(j, i)
+			}
+		}
+	}
+	for i, v := range g {
+		if len(v) == 1 {
+			dfs(i, 1000000)
+			break
+		}
+	}
+	return ans
+}
+```
+
 ### **...**
 
 ```
diff --git a/solution/1700-1799/1743.Restore the Array From Adjacent Pairs/README_EN.md b/solution/1700-1799/1743.Restore the Array From Adjacent Pairs/README_EN.md
