LeetCode 49字母异位词分组&;50pow(x,n)&51八皇后

字母异位词分组

给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。

示例: 输入: ["eat", "tea", "tan", "ate", "nat", "bat"] 输出: [ ["ate","eat","tea"], ["nat","tan"], ["bat"] ]

1

2

3

4

5

6

7

8

9

说明：

所有输入均为小写字母。

不考虑答案输出的顺序。

分析

题目的意思就是给若干个字符串单词，然后将含有全部相同的字母放到一个List中。我们的核心问题是将这个放到哪里？

你可以使用暴力枚举，每次遍历判断，但是那样效率太低，所以我们可以进行哈希 存储。创建一个Map>类型的HashMap进行存储。

实现代码为：

public List> groupAnagrams(String[] strs) { List>lists=new ArrayList<>(); Map>map=new HashMap<>(); for(String str: strs) { char vachar[]=str.toCharArray(); Arrays.sort(vachar); String team=String.copyValueOf(vachar); Listlist=map.getOrDefault(team,new ArrayList<>()); list.add(str); map.put(team,list); } // for(List list:map.values()) // { // lists.add(list); // } lists.addAll(map.values()); return lists; }

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

执行结果：

Pow(x,n)

很明显的快速幂算法，强烈推荐自己写的快速幂介绍：数据结构与算法—这可能是最易懂的快速幂讲解了

但是你需要注意一些地方：

负数处理，并且负数可能是int最小值加个符号转换数值越界出错。所以负数转正数的时候，将负数次幂拆分一个出来就可以转正数幂进行计算了。例如5-2147483648=5-1 x 5 -2147483647 =（1/5 ) x（1/5）2147483647 。int 范围为[-2147483648,2147483647].

注意好停止条件，这里理论上可以稍微重写个函数优化一下，但是由于快速幂logn级别的复杂度比较低，这里就不进行优化直接写了：

public double myPow(double x, int n) { if(n<0) return (1.0/x)*myPow(1.0/x,-(n+1)); if(n==0) return 1; else if(n%2==0) return myPow(x*x,n/2); else return x*myPow(x*x,n/2); }

1

2

3

4

5

6

7

8

9

10

N皇后

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

上图为 8 皇后问题的一种解法。

给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。

每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。

示例：

输入：4 输出：[ [".Q..", // 解法 1 "...Q", "Q...", "..Q."], ["..Q.", // 解法 2 "Q...", "...Q", ".Q.."] ] 解释: 4 皇后问题存在两个不同的解法。

1

2

3

4

5

6

7

8

9

10

11

12

13

提示：

皇后彼此不能相互攻击，也就是说：任何两个皇后都不能处于同一条横行、纵行或斜线上。

八皇后问题我再这篇：回溯算法 | 追忆那些年曾难倒我们的八皇后问题 讲的已经很清楚了，不懂的可以详细看看。

在具体的实现上，就是需要一个map[][]的地图记录各个位置的符号，然后按照规则存储进去，但我这里用了个StringBuilder[]数组来完成。

另外，判断方向的时候因为从一行一行来，如果判断横方向就是多此一举。

附上代码：

// boolean heng[]; boolean shu[]; boolean zuoxie[]; boolean youxie[]; public List> solveNQueens(int n) { List> list=new ArrayList>(); StringBuilder stringBuilder[]=new StringBuilder[n]; for(int i=0;i> list,int n) { // TODO Auto-generated method stub if(index==n)//存入 { Listval=new ArrayList(); //StringBuilder sBuilder=new StringBuilder(); for(int i=0;i

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

51

52

53

54

55

56

57

总是熟悉的100%：

数据结构

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。