LeetCode刷题心得 -- map的妙用

在LeetCode上刷了一波关于数组的题，我有一个好习惯，每次做完题都会去看一下官方的解法和其他大佬留在评论区的解法。
我发现，在和计数（我词汇量比较匮乏，这个“计数”，是一个横广阔的场景）的过程中，map出现的频率非常之高，和哈希表有的一拼。
我想可能是哈希表难度太高吧，为了照顾我们这些菜鸟看得懂，特地降低了难度。

在我前面几篇刷题笔记中，可以随便找些题目，看完之后，马上就可以学以致用（当然，代码别看）

笔记1
笔记2
笔记3
笔记4

我们先拿笔记2里面的第二题来说事儿：

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明：

你的算法应该具有线性时间复杂度。 

示例 1:

输入: [2,2,1]
输出: 1
示例 2:

输入: [4,1,2,1,2]
输出: 4

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
 

对于这题，完全可以把遍历得到的数全放进映射表（map）中，最后只要遍历一下映射表就好了，时间复杂度O(n).

再来看一下笔记4里那个数独的题目，那题我就是用映射表做的。

判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。


数独部分空格内已填入了数字，空白格用 '.' 表示。

示例 1:

输入:
[
  ["5","3",".",".","7",".",".",".","."],
  ["6",".",".","1","9","5",".",".","."],
  [".","9","8",".",".",".",".","6","."],
  ["8",".",".",".","6",".",".",".","3"],
  ["4",".",".","8",".","3",".",".","1"],
  ["7",".",".",".","2",".",".",".","6"],
  [".","6",".",".",".",".","2","8","."],
  [".",".",".","4","1","9",".",".","5"],
  [".",".",".",".","8",".",".","7","9"]
]
输出: true
示例 2:

输入:
[
  ["8","3",".",".","7",".",".",".","."],
  ["6",".",".","1","9","5",".",".","."],
  [".","9","8",".",".",".",".","6","."],
  ["8",".",".",".","6",".",".",".","3"],
  ["4",".",".","8",".","3",".",".","1"],
  ["7",".",".",".","2",".",".",".","6"],
  [".","6",".",".",".",".","2","8","."],
  [".",".",".","4","1","9",".",".","5"],
  [".",".",".",".","8",".",".","7","9"]
]
输出: false
解释: 除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。 但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。
说明:

一个有效的数独（部分已被填充）不一定是可解的。
只需要根据以上规则，验证已经填入的数字是否有效即可。
给定数独序列只包含数字 1-9 和字符 '.' 。
给定数独永远是 9x9 形式的。

> 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/valid-sudoku
> 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
 

如果将数独扩容两倍，三倍呢？就算不扩容，映射表也比暴力破解要好得多。

说了这么多，怎么用呢？

早已准备好了，走近STL–map，只愿一键对一值

当然，我有要补充的：

1. 看示例

map<char, int> ID_Num; ID_Num['1'] = 0; ID_Num['2'] = 0; ID_Num['3'] = 0; ID_Num['4'] = 0; ID_Num['5'] = 0; ID_Num['6'] = 0; ID_Num['7'] = 0; ID_Num['8'] = 0; ID_Num['9'] = 0;

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
 

可以这样进行初始化。

然后，

ai = board[i].at(j); ID_Num[ai]++;

  

 

  
1
  
2
 

如果map中没有ai这个键值的话，会进行插入，这一点一定要重视起来，今天就在这上面在了跟头。

2.在插入时，map会根据键值自动排序。我也不知道之前在哪里看到说不会自动排，真是坑死我。

文章来源: lion-wu.blog.csdn.net，作者：看，未来，版权归原作者所有，如需转载，请联系作者。

原文链接：lion-wu.blog.csdn.net/article/details/105738953