字符串

发布： 分类： 评论： 阅读：

例题

leetcode 316. 删除字符串中的重复字符

1
2
3
Given a string which contains only lowercase letters, remove duplicate letters so that every letter appears once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.
Example 1:  Input: "bcabc"      Output: "abc"
Example 2:  Input: "cbacdcbc"   Output: "acdb"
  • 因为只有26个小写字母，所以可以用数组模拟 hashmap 先统计每个字符出现的次数。
  • 然后要用辅助栈。其实发现很多问题都是数组和栈辅助进行操作，来对比当前元素和栈顶元素的大小，从而进行相应的操作。删除栈顶元素还是向栈中添加元素。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public String removeDuplicateLetters(String s) {
    int[] count = new int[26];  // 统计每个字符出现的次数
    boolean[] visit = new boolean[26];  // 表示某个字符是否已经出现在栈中
    for(char ch : s.toCharArray())  
        count[ch-'a'] += 1;
    Stack<Character> sta = new Stack();
    for(char ch : s.toCharArray()) {
        count[ch-'a'] -= 1;
        if(visit[ch-'a']) continue;
        // 如果当前元素比栈顶元素小，并且栈顶元素次数不等0
        // 那么就把栈顶元素弹出来，把当前元素入栈
        while(!sta.isEmpty() && ch<sta.peek() && count[sta.peek()-'a']!=0) 
            visit[sta.pop()-'a'] = false;
        sta.push(ch);
        visit[ch-'a'] = true;
    }
    String res = "";
    while(!sta.isEmpty())
        res = sta.pop()+res;
    return res;
}

leetcode 567. 字符串中的全排列

1
Given two strings s1 and s2, write a function to return true if s2 contains the permutation of s1. In other words, one of the first string's permutations is the substring of the second string.
1
2
3
Input: s1 = "ab" s2 = "eidbaooo"
Output: True
Explanation: s2 contains one permutation of s1 ("ba").
  • 最直观的做法就是把s1的全排列都列出来，然后看每个全排列是不是s2的子串，但是当字符串的长度过长时，会超时。
  • 如何判断字符串m是不是字符串n的全排列，我们只要把字符串m和字符串n中的每个字符出现的次数做统计，如果两者每个字符出现的次数都相等，那么就证明字符串m是字符串n的一个全排列。
  • 如何判断字符串n是不是包含字符串m的全排列，也就是字符串m的全排列是不是字符串n的一个子串，那么我们就需要建立一个长度为m.length的滑动窗口，判断n的这个滑动窗口中n子串和m字符串每个字符出现的次数是不是相等。
  • 但每到一个滑动窗口都重新统计一次次数很麻烦，每次移动滑动窗口的时候，只有左侧被移出去的字符和右侧被移进来的字符的次数有变化，那么我们把左侧移出去的字符数-1，右侧移进来的字符数+1，即为当前窗口n的每个字符出现的次数。
  • 该题的类似题目：leetcode 438. 找到s1的全排列在s2中的位置
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public boolean checkInclusion(String s1, String s2) {
    if(s1.length()>s2.length())
        return false;
    //统计s1中每个字符出现的次数，s2中每个长度为s1.length的窗口中字符出现的次数
    int[] hash1 = new int[26];
    int[] hash2 = new int[26];
    for(int i=0;i<s1.length();i++) {
        hash1[s1.charAt(i)-'a'] ++;
        hash2[s2.charAt(i)-'a'] ++;
    }
    if(Arrays.equals(hash1, hash2))
        return true;
    for(int i=s1.length();i<s2.length();i++) {
        hash2[s2.charAt(i)-'a'] ++;
        hash2[s2.charAt(i-s1.length())-'a'] --;
        if(Arrays.equals(hash1, hash2))
            return true;
    }
    return false;
}

leetcode 179. 将数组进行排序，使之组成的数最大 (实则为对字符串排序)

  • 输入：[3,30,34,5,9]
  • 输出：9534330
  • 特殊问题：[2, 2281] [12, 121] [23, 234]
  • 碰到长度不等时，会有些问题，比如第一个要交换。第二个不要交换；第三个要交换
  • 最好的办法就是直接把两个字符串m和n拼接起来，然后比较mn和nm的大小即可，不存在长度不等的情况。
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
public void swap(String[] str, int i, int j) {
 String tmp = str[i];
 str[i] = str[j];
 str[j] = tmp;
}
//因为这道题涉及到了长度不同，谁放在前面的问题，不能简单地直接逐个字符比较
//那么，把m和n拼接成的mn和nm按照字符串大小的比较规则来处理即可。
//如果mn < nm,应该打印出nm,即n应该排在m前面，要交换顺序，反之，m应该排在n前面。
public boolean cmp(String a, String b) {
    String new_1 = a+b;
    String new_2 = b+a;
    for(int i=0;i<new_1.length();i++)  {
        if(new_1.charAt(i)==new_2.charAt(i)) continue;
        return new_1.charAt(i)<new_2.charAt(i);
    }
    return true;
}

public String largestNumber(int[] nums) {
    String[] str = new String[nums.length];
    for(int i=0;i<nums.length;i++) {  // 先将数组中的数字转为字符串，再去比较。
        str[i] = nums[i]+"";
    }
    //写个冒泡排序，任何一种排序算法都可以，只要把交换的条件变为我们的cmp条件即可。
    for(int i=nums.length-1;i>=0;i--) {
        boolean flag = false;
        for(int j=0;j<i;j++) {
            if(cmp(str[j], str[j+1])) {
                swap(str, j, j+1);
                flag = true;
            }
        }
        if(!flag) break;
    }
    String result = "";
    for(int i=0;i<str.length;i++) {
        result += str[i];
    }
    if(result.charAt(0)=='0') return "0"; //防止出现"00"的情况。
    else return result;
}