LeetCode 49字母異位詞分組&50pow(x,n)&51八皇后

原創公眾號：bigsai 如果不錯記得點贊收藏！
關注回復 bigsai 領取Java進階pdf資源，回復進群加入力扣打卡群，
上周打卡內容：43字串相乘&44通配符匹配 45跳躍游戲&46全排列
昨天打卡內容：LeetCode 47全排列Ⅱ&48旋轉影像

字母異位詞分組

給定一個字串陣列，將字母異位詞組合在一起，字母異位詞指字母相同，但排列不同的字串，

示例:

輸入: ["eat", "tea", "tan", "ate", "nat", "bat"]
輸出:
[
  ["ate","eat","tea"],
  ["nat","tan"],
  ["bat"]
]

說明：

所有輸入均為小寫字母，
不考慮答案輸出的順序，

分析

題目的意思就是給若干個字串單詞，然后將含有全部相同的字母放到一個List<String>中，我們的核心問題是將這個放到哪里？

你可以使用暴力列舉，每次遍歷判斷，但是那樣效率太低，所以我們可以進行哈希 存盤，創建一個Map<String,List<String>>型別的HashMap進行存盤，

實作代碼為：

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

執行結果：

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);
 }

N皇后

n 皇后問題研究的是如何將 n 個皇后放置在 n×n 的棋盤上，并且使皇后彼此之間不能相互攻擊，

上圖為 8 皇后問題的一種解法，
給定一個整數 n，回傳所有不同的 n 皇后問題的解決方案，
每一種解法包含一個明確的 n 皇后問題的棋子放置方案，該方案中 ‘Q’ 和 ‘.’ 分別代表了皇后和空位，

示例：

輸入：4
輸出：[
 [".Q..",  // 解法 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // 解法 2
  "Q...",
  "...Q",
  ".Q.."]
]
解釋: 4 皇后問題存在兩個不同的解法，

提示：
皇后彼此不能相互攻擊，也就是說：任何兩個皇后都不能處于同一條橫行、縱行或斜線上，

八皇后問題我再這篇：回溯演算法 | 追憶那些年曾難倒我們的八皇后問題 講的已經很清楚了，不懂的可以詳細看看，

在具體的實作上，就是需要一個map[][]的地圖記錄各個位置的符號，然后按照規則存盤進去，但我這里用了個StringBuilder[]陣列來完成，
另外，判斷方向的時候因為從一行一行來，如果判斷橫方向就是多此一舉，
附上代碼：

// boolean heng[];
 boolean shu[];
 boolean zuoxie[];
 boolean youxie[];

 	 public List<List<String>> solveNQueens(int n) {
	List<List<String>> list=new ArrayList<List<String>>();
	StringBuilder stringBuilder[]=new StringBuilder[n];
	for(int i=0;i<n;i++)
	{
		stringBuilder[i]=new StringBuilder();
		for(int j=0;j<n;j++)
		{
			stringBuilder[i].append('.');
		}
	}
	shu=new boolean[n];
	zuoxie=new boolean[n*2];
	youxie=new boolean[n*2];
	dfs(0,stringBuilder,list,n);
	return list;
 }

private void dfs(int index, StringBuilder sBuilder[], List<List<String>> list,int n) {
	// TODO Auto-generated method stub
	if(index==n)//存入
	{
		List<String>val=new ArrayList<String>();
		//StringBuilder sBuilder=new StringBuilder();
		for(int i=0;i<n;i++)
		{
			val.add(sBuilder[i].toString());
			
		}
		list.add(val);
	}
	else {
		for(int j=0;j<n;j++)
		{
			if(!shu[j]&&!zuoxie[index+j]&&!youxie[index+(n-1-j)])
			{
				shu[j]=true;
				zuoxie[index+j]=true;
				youxie[index+(n-1-j)]=true;
				//map[index][j]='Q';
				sBuilder[index].setCharAt(j, 'Q');
				dfs(index+1,sBuilder, list, n);
				shu[j]=false;
				zuoxie[index+j]=false;
				youxie[index+(n-1-j)]=false;
				sBuilder[index].setCharAt(j, '.');
				//map[index][j]='.';
				
			}
		}
	}	
}

總是熟悉的100%：

結語：好了今天就到這里了，歡迎關注原創技術公眾號：【bigsai】，回復進群加筆者微信一起加入打卡！回復「bigsai」，領取進階資源，