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

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

字母异位词分组



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


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


说明:

所有输入均为小写字母。

不考虑答案输出的顺序。


分析


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


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


20201101190232659.png


实现代码为:


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


执行结果:


20201101101916183.png


Pow(x,n)



20201101102327278.png


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


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


  • 负数处理,并且负数可能是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);
 }

20201101103616993.png


N皇后



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


20201101105845695.png


上图为 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%:


20201101111525758.png


结语:好了今天就到这里了,欢迎关注原创技术公众号:【bigsai】,回复进群加笔者微信一起加入打卡!回复「bigsai」,领取进阶资源。


20201101192021433.png


目录
相关文章
|
3月前
|
存储 算法
LeetCode第49题字母异位词分组
LeetCode第49题"字母异位词分组"的解题方法,通过将每个字符串的字符排序后作为键存储在HashMap中,有效地将所有字母异位词分组。
LeetCode第49题字母异位词分组
|
1月前
|
存储
Leetcode第49题(字母异位词分组)
LeetCode第49题要求将字符串数组中的字母异位词分组,可以通过将每个字符串排序后作为键存入哈希表,最后将哈希表中的值添加到结果列表中来实现。
15 1
|
1月前
|
算法
Leetcode第十七题(电话号码的字母组合)
这篇文章介绍了如何使用深度优先搜索(DFS)算法来解决LeetCode第17题——电话号码的字母组合问题,通过递归方法生成所有可能的字母组合。
18 0
Leetcode第十七题(电话号码的字母组合)
|
1月前
|
索引
【LeetCode 11】242.有效的字母异位词
【LeetCode 11】242.有效的字母异位词
15 0
【LeetCode 11】242.有效的字母异位词
|
1月前
|
算法
【LeetCode 52】17.电话号码的字母组合
【LeetCode 52】17.电话号码的字母组合
31 0
|
1月前
|
算法 C++
Leetcode第50题(Pow(x,n))
这篇文章介绍了如何使用快速幂算法解决LeetCode第50题,即实现函数pow(x, n)来计算x的n次幂,并提供了C++的代码实现。
14 0
|
3月前
|
算法 Java
LeetCode第50题Pow(x, n)
LeetCode第50题"Pow(x, n)"的解题方法,运用分而治之的策略,通过快速幂算法高效计算幂函数的结果。
LeetCode第50题Pow(x, n)
|
2月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
3月前
|
Python
【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III
本文介绍了两种Python实现方法,用于按照之字形顺序打印二叉树的层次遍历结果,实现了在奇数层正序、偶数层反序打印节点的功能。
57 6
|
3月前
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
114 2