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小時內刪除侵權內容。