LeetCode解题报告—— Group Anagrams & Pow(x, n) & Spiral Matrix

1. Group Anagrams

Given an array of strings, group anagrams together.

For example, given: ["eat", "tea", "tan", "ate", "nat", "bat"],

[

  ["ate", "eat","tea"],

  ["nat","tan"],

  ["bat"]

]

Note: All inputs will be in lower-case.

思路：利用一个map，key是构成字符串的字符，value是与之相对应的字符串集合。比如“ate”和“eat”对应的是aet。遍历所有字符串，将字符串分解为字符数组后排序，再转为字符串，如果再key中则将这个字符串添加到这个key所对应的集合中，如果不在则新增key即可。

import java.util.*;

public class LeetCode{

    public static void main(String[] args){

        Scanner sc=new Scanner(System.in);

        String str=sc.nextLine();

        String[] strs=str.split(",");

        List<List<String>> res=groupAnagrams(strs);

        for(List<String> list:res){

            for(String s:list)

                System.out.print(s+" ");

        System.out.println();

        }

    }

    static List<List<String>> groupAnagrams(String[] strs){

        if (strs == null || strs.length == ) return new ArrayList<List<String>>();

        Map<String, List<String>> map = new HashMap<String, List<String>>();

        for (String s : strs) {

            char[] ca = s.toCharArray();

            Arrays.sort(ca);

            String keyStr = String.valueOf(ca);

            if (!map.containsKey(keyStr)) map.put(keyStr, new ArrayList<String>());

            map.get(keyStr).add(s);

        }

        return new ArrayList<List<String>>(map.values());

    }

}

上面需要注意的是map的用法：

- map.containsKey(keyStr) 判断是否存在指定的key

- map.values() 以Collection<>集合的形式返回所有的value

- map.containsValue(Object value) 判断指定的value是否存在

2. Pow(x, n)

Implement pow(x, n).

Example 1:

Input: 2.00000, 10

Output: 1024.00000

Example 2:

Input: 2.10000, 3

Output: 9.26100

思路：实现指数计算函数，虽然可以使用遍历来乘，但肯定会超时，所以还得想别的办法。最简单的想法是，如果n能被2整除，那么pow(x,n)=pow(x*x, n/2)，如果不能整除则pow(x, n)=x*pow(x*x, n/2)，over。

public class Solution {

    public double pow(double x, int n) {

        if(n == 0)

            return 1;

        if(n<0){

            n = -n;

            x = 1/x;

        }

        return (n%2 == 0) ? pow(x*x, n/2) : x*pow(x*x, n/2);

    }

}

3. Spiral(漩涡，螺旋) Matrix

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

For example,
Given the following matrix:

[

 [ 1, 2, 3 ],

 [ 4, 5, 6 ],

 [ 7, 8, 9 ]

]

You should return [1,2,3,6,9,8,7,4,5].

思路：思路一是模拟，首先明确一点的是这个漩涡路径是方向的改变是顺时针，且遇到边界或者是遇到之前访问过的数字，从这个规律来入手模拟。设数组有R行和C列，seen[r][c]代表第r行第c列上的数字是访问过的。我们目前的位置是(r,c)，目前的方向是 di。当我们遍历整个矩阵时，我们候选的下个位置是(cr,cc)，如果它没有超出边界并且没有访问过，则下一个遍历的位置就是它，否则按顺时针旋转方向。

import java.util.*;

public class LeetCode{

    public static void main(String[] args){

        Scanner sc=new Scanner(System.in);

        int m=sc.nextInt();

        int n=sc.nextInt();

        sc.nextLine();

        int[][] matrix=new int[m][n];

        for(int i=0;i<m;i++){

            String input=sc.nextLine().replaceAll("\\]|\\[| ","");

            String[] inputs=input.split(",");

            for(int j=0;j<inputs.length;j++){

                matrix[i][j]=Integer.parseInt(inputs[j]);

            }

        }

        List<Integer> ans=spiralOrder(matrix);

        for(int a:ans)

            System.out.print(a+" ");

    }

    static List<Integer> spiralOrder(int[][] matrix){

        List ans=new ArrayList();

        if(matrix.length==0) return ans;

        int R=matrix.length, C=matrix[0].length;

        boolean[][] seen=new boolean[R][C];

        int[] dr={0,1,0,-1};　　// 这里用dr，dc的组合来代表上下左右四个方向

        int[] dc={1,0,-1,0};

        int r=0, c=0, di=0;

        for(int i=0;i<R*C;i++){

            ans.add(matrix[r][c]);

            seen[r][c]=true;

            int cr=r+dr[di];

            int cc=c+dc[di];

            if(0<=cr&&cr<R&&0<=cc&&cc<C&&!seen[cr][cc]){　　// 这里大小比较要分开写，不能写成0<=cr<R这种形式

                r=cr;

                c=cc;

            }else{

                di=(di+1)%4;

                r+=dr[di];

                c+=dc[di];

            }

        }

        return ans;

    }

}

巴特西

LeetCode解题报告—— Group Anagrams & Pow(x, n) & Spiral Matrix

最新文章

热门文章