Add solution 0791

halfrost · halfrost · commit eda4953c3d64 · 2021-07-18T18:13:55.000+08:00
diff --git a/leetcode/0791.Custom-Sort-String/791. Custom Sort String.go b/leetcode/0791.Custom-Sort-String/791. Custom Sort String.go
@@ -0,0 +1,15 @@
+package leetcode
+
+import "sort"
+
+func customSortString(order string, str string) string {
+	magic := map[byte]int{}
+	for i := range order {
+		magic[order[i]] = i - 30
+	}
+	byteSlice := []byte(str)
+	sort.Slice(byteSlice, func(i, j int) bool {
+		return magic[byteSlice[i]] < magic[byteSlice[j]]
+	})
+	return string(byteSlice)
+}
diff --git a/leetcode/0791.Custom-Sort-String/791. Custom Sort String_test.go b/leetcode/0791.Custom-Sort-String/791. Custom Sort String_test.go
@@ -0,0 +1,43 @@
+package leetcode
+
+import (
+	"fmt"
+	"testing"
+)
+
+type question791 struct {
+	para791
+	ans791
+}
+
+// para 是参数
+// one 代表第一个参数
+type para791 struct {
+	order string
+	str   string
+}
+
+// ans 是答案
+// one 代表第一个答案
+type ans791 struct {
+	one string
+}
+
+func Test_Problem791(t *testing.T) {
+
+	qs := []question791{
+
+		{
+			para791{"cba", "abcd"},
+			ans791{"cbad"},
+		},
+	}
+
+	fmt.Printf("------------------------Leetcode Problem 791------------------------\n")
+
+	for _, q := range qs {
+		_, p := q.ans791, q.para791
+		fmt.Printf("【input】:%v       【output】:%v\n", p, customSortString(p.order, p.str))
+	}
+	fmt.Printf("\n\n\n")
+}
diff --git a/leetcode/0791.Custom-Sort-String/README.md b/leetcode/0791.Custom-Sort-String/README.md
@@ -0,0 +1,55 @@
+# [791. Custom Sort String](https://leetcode.com/problems/custom-sort-string/)
+
+
+## 题目
+
+`order` and `str` are strings composed of lowercase letters. In `order`, no letter occurs more than once.
+
+`order` was sorted in some custom order previously. We want to permute the characters of `str` so that they match the order that `order` was sorted. More specifically, if `x` occurs before `y` in `order`, then `x` should occur before `y` in the returned string.
+
+Return any permutation of `str` (as a string) that satisfies this property.
+
+```
+Example:Input:
+order = "cba"
+str = "abcd"
+Output: "cbad"
+Explanation:
+"a", "b", "c" appear in order, so the order of "a", "b", "c" should be "c", "b", and "a".
+Since "d" does not appear in order, it can be at any position in the returned string. "dcba", "cdba", "cbda" are also valid outputs.
+
+```
+
+**Note:**
+
+- `order` has length at most `26`, and no character is repeated in `order`.
+- `str` has length at most `200`.
+- `order` and `str` consist of lowercase letters only.
+
+## 题目大意
+
+字符串 S 和 T 只包含小写字符。在 S 中，所有字符只会出现一次。S 已经根据某种规则进行了排序。我们要根据 S 中的字符顺序对 T 进行排序。更具体地说，如果 S 中 x 在 y 之前出现，那么返回的字符串中 x 也应出现在 y 之前。返回任意一种符合条件的字符串 T。
+
+## 解题思路
+
+- 题目只要求 T 中包含 S 的字符串有序，所以可以先将 T 中包含 S 的字符串排好序，然后再拼接上其他字符。S 字符串最长为 26 位，先将 S 中字符的下标向左偏移 30，并将偏移后的下标值存入字典中。再把 T 字符串按照字典中下标值进行排序。S 中出现的字符对应的下标经过处理以后变成了负数，S 中未出现的字符的下标还是正数。所以经过排序以后，S 中出现的字符按照原有顺序排列在前面，S 中未出现的字符依次排在后面。
+
+## 代码
+
+```go
+package leetcode
+
+import "sort"
+
+func customSortString(order string, str string) string {
+	magic := map[byte]int{}
+	for i := range order {
+		magic[order[i]] = i - 30
+	}
+	byteSlice := []byte(str)
+	sort.Slice(byteSlice, func(i, j int) bool {
+		return magic[byteSlice[i]] < magic[byteSlice[j]]
+	})
+	return string(byteSlice)
+}
+```
diff --git a/leetcode/1846.Maximum-Element-After-Decreasing-and-Rearranging/1846. Maximum Element After Decreasing and Rearranging.go b/leetcode/1846.Maximum-Element-After-Decreasing-and-Rearranging/1846. Maximum Element After Decreasing and Rearranging.go
@@ -2,12 +2,12 @@ package leetcode
 
 func maximumElementAfterDecrementingAndRearranging(arr []int) int {
 	n := len(arr)
-	cnt := make([]int, n+1)
+	count := make([]int, n+1)
 	for _, v := range arr {
-		cnt[min(v, n)]++
+		count[min(v, n)]++
 	}
 	miss := 0
-	for _, c := range cnt[1:] {
+	for _, c := range count[1:] {
 		if c == 0 {
 			miss++
 		} else {
diff --git a/website/content/ChapterFour/0700~0799/0786.K-th-Smallest-Prime-Fraction.md b/website/content/ChapterFour/0700~0799/0786.K-th-Smallest-Prime-Fraction.md
@@ -122,5 +122,5 @@ func (a SortByFraction) Less(i, j int) bool {
 ----------------------------------------------
 <div style="display: flex;justify-content: space-between;align-items: center;">
 <p><a href="https://books.halfrost.com/leetcode/ChapterFour/0700~0799/0785.Is-Graph-Bipartite/">⬅️上一页</a></p>
-<p><a href="https://books.halfrost.com/leetcode/ChapterFour/0700~0799/0792.Number-of-Matching-Subsequences/">下一页➡️</a></p>
+<p><a href="https://books.halfrost.com/leetcode/ChapterFour/0700~0799/0791.Custom-Sort-String/">下一页➡️</a></p>
 </div>
diff --git a/website/content/ChapterFour/0700~0799/0791.Custom-Sort-String.md b/website/content/ChapterFour/0700~0799/0791.Custom-Sort-String.md
@@ -0,0 +1,62 @@
+# [791. Custom Sort String](https://leetcode.com/problems/custom-sort-string/)
+
+
+## 题目
+
+`order` and `str` are strings composed of lowercase letters. In `order`, no letter occurs more than once.
+
+`order` was sorted in some custom order previously. We want to permute the characters of `str` so that they match the order that `order` was sorted. More specifically, if `x` occurs before `y` in `order`, then `x` should occur before `y` in the returned string.
+
+Return any permutation of `str` (as a string) that satisfies this property.
+
+```
+Example:Input:
+order = "cba"
+str = "abcd"
+Output: "cbad"
+Explanation:
+"a", "b", "c" appear in order, so the order of "a", "b", "c" should be "c", "b", and "a".
+Since "d" does not appear in order, it can be at any position in the returned string. "dcba", "cdba", "cbda" are also valid outputs.
+
+```
+
+**Note:**
+
+- `order` has length at most `26`, and no character is repeated in `order`.
+- `str` has length at most `200`.
+- `order` and `str` consist of lowercase letters only.
+
+## 题目大意
+
+字符串 S 和 T 只包含小写字符。在 S 中，所有字符只会出现一次。S 已经根据某种规则进行了排序。我们要根据 S 中的字符顺序对 T 进行排序。更具体地说，如果 S 中 x 在 y 之前出现，那么返回的字符串中 x 也应出现在 y 之前。返回任意一种符合条件的字符串 T。
+
+## 解题思路
+
+- 题目只要求 T 中包含 S 的字符串有序，所以可以先将 T 中包含 S 的字符串排好序，然后再拼接上其他字符。S 字符串最长为 26 位，先将 S 中字符的下标向左偏移 30，并将偏移后的下标值存入字典中。再把 T 字符串按照字典中下标值进行排序。S 中出现的字符对应的下标经过处理以后变成了负数，S 中未出现的字符的下标还是正数。所以经过排序以后，S 中出现的字符按照原有顺序排列在前面，S 中未出现的字符依次排在后面。
+
+## 代码
+
+```go
+package leetcode
+
+import "sort"
+
+func customSortString(order string, str string) string {
+	magic := map[byte]int{}
+	for i := range order {
+		magic[order[i]] = i - 30
+	}
+	byteSlice := []byte(str)
+	sort.Slice(byteSlice, func(i, j int) bool {
+		return magic[byteSlice[i]] < magic[byteSlice[j]]
+	})
+	return string(byteSlice)
+}
+```
+
+
+----------------------------------------------
+<div style="display: flex;justify-content: space-between;align-items: center;">
+<p><a href="https://books.halfrost.com/leetcode/ChapterFour/0700~0799/0786.K-th-Smallest-Prime-Fraction/">⬅️上一页</a></p>
+<p><a href="https://books.halfrost.com/leetcode/ChapterFour/0700~0799/0792.Number-of-Matching-Subsequences/">下一页➡️</a></p>
+</div>
diff --git a/website/content/ChapterFour/0700~0799/0792.Number-of-Matching-Subsequences.md b/website/content/ChapterFour/0700~0799/0792.Number-of-Matching-Subsequences.md
@@ -68,6 +68,6 @@ func numMatchingSubseq(s string, words []string) int {
 
 ----------------------------------------------
 <div style="display: flex;justify-content: space-between;align-items: center;">
-<p><a href="https://books.halfrost.com/leetcode/ChapterFour/0700~0799/0786.K-th-Smallest-Prime-Fraction/">⬅️上一页</a></p>
+<p><a href="https://books.halfrost.com/leetcode/ChapterFour/0700~0799/0791.Custom-Sort-String/">⬅️上一页</a></p>
 <p><a href="https://books.halfrost.com/leetcode/ChapterFour/0700~0799/0793.Preimage-Size-of-Factorial-Zeroes-Function/">下一页➡️</a></p>
 </div>
