本文共 3273 字，大约阅读时间需要 10 分钟。

题目1：实现一个算法，确定一个字符串的所有字符是否全都不同。假使不允许使用额外的数据结构，又如何处理？

对于这样的题目，首先要考虑字符串的编码方式，是Unicode还是ASCⅡ。假设使用ASCⅡ，有256个字符。

package com.czl.question;public class TestStr {
       public boolean isUniqueChars(String str){        if (str.length() > 256) {            return false;        }        boolean[] char_set = new boolean[256];        for (int i = 0; i < str.length(); i++) {            int val = str.charAt(i);            if (char_set[val]) {
  //如果这个字符已经出现过，返回false                System.out.println("有重复");                return false;            }            char_set[val] = true;        }        System.out.println("没有重复");        return true;    }    public static void main(String[] args) {        String string = "14124235qwertymdaldnmzd";        TestStr testStr = new TestStr();        testStr.isUniqueChars(string);    }}

此种解法的时间复杂度为$O(n)$，其中$n$为字符串长度，空间复杂度为

如果，将字符串中的每一个字符与其余字符进行比较，不需要考虑字符类型，这种方法的时间复杂度为$O(n^2)$，空间复杂度为$O(1)$。

package com.czl.question;public class TestUniqueStr {
       public boolean isUnique(String str){        char[] tempchar = str.toString().toCharArray();        for (int i = 0; i < tempchar.length; i++) {            for (int j = i + 1; j < tempchar.length; j++) {                if (tempchar[i] == tempchar[j]) {                    System.out.println("有重复");                    return false;                }                System.out.println("没有重复");                return true;            }        }        return true;    }    public static void main(String[] args) {        String string = "qwerabc";        TestUniqueStr tus = new TestUniqueStr();        tus.isUnique(string);    }}

题目2：给定两个字符串，请编写程序，确实其中一个字符串的字符重新排列后，能否变成另一个字符串。

分析：首先，针对变位词比较是否区分大小写，一般字符串中存在的空格是否需要考虑，比较两个字符串时，只要两者长度不同，就不是变位词。

解法一：排序字符串

若两个字符串互为变位词，那么他们拥有同一组字符，自不过顺序不同。因此，对字符串排序，组成两个变位词的字符就会有相同的顺序，比较排序后的字符串即可。

public class Question2 {
       public String sort(String s){        char[] content = s.toString().toCharArray();        java.util.Arrays.sort(content);        return new String(content);    }    public boolean permutation(String s,String t){        if (s.length() != t.length()) {            return false;        }        return sort(s).equals(sort(t));    }    public static void main(String[] args) {        Question2 q = new Question2();        String s = "goodod";        String t = "doodog";        System.out.println(q.permutation(s, t));    }}

解法二：检查两个字符串的各字符数是否相同

根据变位词的定义，可以知道组成两个变位词的字符数相同。只需要遍历字母表，计算每个字符出现的次数，然后比较两个数组即可。

public class Question2_1 {
       public boolean permutation(String s,String t){        if (s.length() != t.length()) {            return false;        }        int[] letters = new int[256];//假设条件        char[] char_set = s.toString().toCharArray();        for (char c : char_set) {
  //计算字符串s中每个字符出现的次数            letters[c]++;        }        for (int i = 0; i < t.length(); i++) {            int c = (int)t.charAt(i);            if (--letters[c] < 0) {                return false;            }        }        return true;    }    public static void main(String[] args) {        Question2_1 q = new Question2_1();        String s = "goodmoon";        String t = "noom!doog";        String t1 = "nooomdog";        System.out.println(q.permutation(s, t));        System.out.println(q.permutation(s, t1));    }}

转载地址：http://cbrji.baihongyu.com/