【每日算法Day 22】字符串基础4

hashCode()与equals()的关系，Arrays.hashCode()的使用；有时对数字拼接或比较可以转为字符串的拼接或比较；字符与字符串相关API的使用。

# LeeetCode 49. 字母异位词分组 (opens new window)

# 题目描述

给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。所有输入均为小写字母。不考虑答案输出的顺序。

# 示例

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

1
2
3
4
5
6
7

# 解题思路

昨天的上一题已经通过哈希数组统计两个字符串中各字符的出现次数，来进一步比较两个字符串是否是字母异位词。然而这一题需要同时比较多个字符串间的哈希数组，显然两两比较是效率很低的，因此需要用到Map，把哈希数组的哈希值作为key存起来，扫描的过程中发现有key相同的字符串，就放入同一个List容器（value）中。

不过这边学习到了一个新的点。我们在自己编写的getHash()中可以得到统计各字符的出现次数的哈希数组，我们都知道Java中数组也是对象，因此Map<int[],String>语法上是没有问题的，然而数组的hashCode()没有重写，所以两个内容相同的数组其实不能作为同一个key插入到map中。执行下面的程序：

public static void main(String[] args) {
    System.out.println(new String("text").hashCode());
    System.out.println(new String("text").hashCode());
    System.out.println(new int[]{1,2}.hashCode());
    System.out.println(new int[]{1,2}.hashCode());
    System.out.println(Arrays.hashCode(new int[]{1, 2}));
    System.out.println(Arrays.hashCode(new int[]{1, 2}));
}

1
2
3
4
5
6
7
8

得到的输出如下：

-1004677520
-1004677520
1118140819
1975012498
994
994

1
2
3
4
5
6

可以看到只有euqals()相同的两个对象的hashCode()才相同，这在Object类下的hashCode()方法也有说明。不重写equals()方法，hashCode只能基于对象的地址，因而上面的两个数组的hashCode不同。想要得到逻辑意义上的数组的hashCode，可以使用Arrays.hashCode()得到。

回到本题，编写程序如下：

public List<List<String>> groupAnagrams(String[] strs) {
    Map<Integer,List<String>> map =new HashMap<>();
    for (String str : strs) {
        int hashcode = Arrays.hashCode(getHash(str));
        if (!map.containsKey(hashcode)) {
            map.put(hashcode, new ArrayList<>());
        }
        map.get(hashcode).add(str);
    }
    return new ArrayList<>(map.values());
}

private int[] getHash(String s) {
    int[] hash = new int[128];
    for (int i = 0; i < s.length(); i++) {
        hash[s.charAt(i)]++;
    }
    return hash;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

# LeetCode 179. 最大数 (opens new window)

# 题目描述

给定一组非负整数，重新排列它们的顺序使之组成一个最大的整数。输出结果可能非常大，所以你需要返回一个字符串而不是整数。

# 示例

示例 1:
输入: [10,2]
输出: 210

示例 2:
输入: [3,30,34,5,9]
输出: 9534330

1
2
3
4
5
6
7

# 解题思路

一开始想到贪心思想，尽量把最高位大的数字放前面，最高位相同时比较次高位；没有次高位的>次高位为9的>...>次高位为0的，但是想到这样比较可能编写起来比较麻烦。后来想到直接做字符串连接并比较就可以了，例如10 9 < 9 10 , 10 19 < 19 10，这样就可以自定义排序，使得排序后的数组首位是“最大”的数字，最后再输出字符串的拼接结果就可以了。

public String largestNumber(int[] nums) {
    String[] strs=new String[nums.length];
    for (int i=0;i<nums.length;i++) {
        strs[i]=String.valueOf(nums[i]);
    }
    Arrays.sort(strs,new numComparator());
    if(strs[0].equals("0")) return "0";
    StringBuilder sb=new StringBuilder();
    for (String str : strs) {
        sb.append(str);
    }
    return sb.toString();
}

private class numComparator implements Comparator<String> {
    @Override
    public int compare(String o1, String o2) {
        return (o2+o1).compareTo(o1+o2);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

# LeetCode 125. 验证回文串 (opens new window)

# 题目描述

给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。说明：本题中，我们将空字符串定义为有效的回文串。

# 示例

示例 1:
输入: "A man, a plan, a canal: Panama"
输出: true

示例 2:
输入: "race a car"
输出: false

1
2
3
4
5
6
7

# 解题思路

双指针法，从字符两边向中间扫描，遇到非字母或数字则跳过，两字符忽略大小写相同则继续。时间复杂度为O(s.length)，空间复杂度为O(1)。不过这一题考查的是对API的熟练程度，显然我第一次写的还有问题。

public boolean isPalindrome(String s) {
    if (s==null) return false;
    if (s.length()==0) return true;
    int left=0,right=s.length()-1;
    while (true) {
        while (left < s.length()&&!inRange(s.charAt(left))) {
            left++;
        }
        while (right >=0&&!inRange(s.charAt(right))) {
            right--;
        }
        if (right < left) {
            return true;
        } else {
            //这里的判断方法有问题，测试用例"0P"不通过
            //可以使用Character.toLowerCase()再比较
            int distance = Math.abs(s.charAt(right)-s.charAt(left));
            if (!(distance==0||distance==32)) return false;
            left++;
            right--;
        }
    }
}

//可以用Character.isLetterOrDigit(c)代替，API底层用了位运算效率更高
private boolean inRange(char c) {
    return (c>='0'&&c<='9')||(c>='A'&&c<='Z')||(c>='a'&&c<='z');
}

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

此外，还可以使用StringBuffer/StringBuilder判断去除非数字和字母的字符串翻转之后是否和自身相同，不过会使用额外的O(n)空间。

public boolean isPalindrome(String s) {
    StringBuffer sgood = new StringBuffer();
    int length = s.length();
    for (int i = 0; i < length; i++) {
        char ch = s.charAt(i);
        if (Character.isLetterOrDigit(ch)) {
            sgood.append(Character.toLowerCase(ch));
        }
    }
    StringBuffer sgood_rev = new StringBuffer(sgood).reverse();
    return sgood.toString().equals(sgood_rev.toString());
}

1
2
3
4
5
6
7
8
9
10
11
12

Wallace's Blog

Choose mode