Обнаружение, если строка имеет уникальные символы: сравнение моего решения с "Cracking the Coding Interview"?

Ответ 1

Здесь есть два отдельных вопроса: какова эффективность вашего решения и что такое эталонное решение? Дайте относиться каждому независимо.

Во-первых, ваше решение:

public static boolean checkForUnique(String str){
    boolean containsUnique = false;

    for(char c : str.toCharArray()){
        if(str.indexOf(c) == str.lastIndexOf(c)){
            containsUnique = true;
        } else {
            containsUnique = false;
        }
    }

    return containsUnique;
}

Ваше решение по существу состоит из цикла над всеми символами в строке (скажем, есть n из них), проверяя каждую итерацию, является ли первый и последний индекс символов одинаковыми. Для методов indexOf и lastIndexOf требуется время O (n), поскольку они должны сканировать все символы строки, чтобы определить, соответствует ли кто-либо из того, что вы ищете. Поэтому, поскольку в вашем цикле выполняется O (n) раз и выполняется O (n) на итерацию, его время выполнения равно O (n ²).

Однако в вашем коде есть что-то определенное. Попробуйте запустить его в строке aab. Правильно ли работает этот вход? Как подсказка, как только вы определяете, что есть два или более дублированных символа, вам гарантировано, что есть дубликаты, и вы можете вернуть, что не все символы уникальны.

Теперь посмотрим на ссылку:

public static boolean isUniqueChars(String str) {
    if (str.length() > 256) { // NOTE: Are you sure this isn't 26?
        return false;
    }
    int checker = 0;
    for (int i = 0; i < str.length(); i++) {
        int val = str.charAt(i) - 'a';
        if ((checker & (1 << val)) > 0) return false;
        checker |= (1 << val);
    }
    return true;
}

Это решение мило. Основная идея заключается в следующем: представьте, что у вас есть массив из 26 логических элементов, каждый из которых отслеживает, появился ли какой-либо конкретный символ в строке. Вы начинаете со всех ложных. Затем вы перебираете символы строки, и каждый раз, когда вы видите персонажа, вы смотрите в слот массива для этого символа. Если он false, это первый раз, когда вы видели символ, и вы можете установить слот на true. Если он true, вы уже видели этот символ, и вы можете сразу сообщить, что есть дубликат.

Обратите внимание, что этот метод не выделяет массив логических элементов. Вместо этого он выбирает умный трюк. Поскольку существует только 26 различных символов, а в int 32 бита, решение создает переменную int, где каждый бит переменной соответствует одному из символов в строке. Вместо чтения и записи массива решение считывает и записывает биты числа.

Например, посмотрите на эту строку:

if ((checker & (1 << val)) > 0) return false;

Что делает checker & (1 << val)? Ну, 1 << val создает значение int, которое имеет все биты нуль, кроме бит val th. Затем он использует побитовое И для И это значение с помощью checker. Если бит в позиции val в checker уже установлен, тогда это оценивается как ненулевое значение (что означает, что мы уже видели число), и мы можем вернуть false. В противном случае он будет равен 0, и мы не увидели его.

Следующая строка такова:

checker |= (1 << val);

В этом случае используется оператор "побитовое ИЛИ с присваиванием", что эквивалентно

checker = checker | (1 << val);

Этот ORs checker со значением, имеющим 1 бит, установленным только в позиции val, который включает бит. Это эквивалентно тому, что бит val th этого числа равен 1.

Этот подход намного быстрее, чем ваш. Во-первых, поскольку функция запускается, проверяя, имеет ли строка длину больше 26 (я предполагаю, что 256 является опечаткой), функция никогда не должна проверять ни одну строку длиной 27 или больше. Поэтому внутренний цикл работает не более 26 раз. Каждая итерация O (1) работает в побитовых операциях, поэтому общая работа выполнена O (1) (O (1) итераций, когда O (1) работает на итерацию), что значительно быстрее, чем ваша реализация.

Если вы не видели побитовые операции, используемые таким образом, я бы рекомендовал искать "побитовые операторы" в Google, чтобы узнать больше.

Надеюсь, это поможет!

Ответ 2

Решение книги - это то, что мне не нравится, и я считаю, что это неблагополучно..... templatetypedef опубликовал исчерпывающий ответ, который указывает, что решение является хорошим. Я не согласен, так как в ответе на книгу предполагается, что строка содержит только строчные символы (ascii) и не проверяет ее.

public static boolean isUniqueChars(String str) {
    // short circuit - supposed to imply that
    // there are no more than 256 different characters.
    // this is broken, because in Java, char are Unicode,
    // and 2-byte values so there are 32768 values
    // (or so - technically not all 32768 are valid chars)
    if (str.length() > 256) {
        return false;
    }
    // checker is used as a bitmap to indicate which characters
    // have been seen already
    int checker = 0;
    for (int i = 0; i < str.length(); i++) {
        // set val to be the difference between the char at i and 'a'
        // unicode 'a' is 97
        // if you have an upper-case letter e.g. 'A' you will get a
        // negative 'val' which is illegal
        int val = str.charAt(i) - 'a';
        // if this lowercase letter has been seen before, then
        // the corresponding bit in checker will have been set and
        // we can exit immediately.
        if ((checker & (1 << val)) > 0) return false;
        // set the bit to indicate we have now seen the letter.
        checker |= (1 << val);
    }
    // none of the characters has been seen more than once.
    return true;
}

В нижней строке, учитывая также templatedef ответ, заключается в том, что на самом деле нет достаточной информации для определения правильности ответа книги.

Я не доверяю ему, хотя.

templatedef ответ на сложность - это тот, с которым я согласен, хотя....; -)

EDIT: в качестве упражнения я преобразовал книгу в ответ на тот, который будет работать (хотя и медленнее, чем ответ книги - BigInteger медленный). Эта версия выполняет ту же логику, что и книга, но не имеет такие же проблемы проверки и допущения (но они медленнее). Полезно также показать логику.

public static boolean isUniqueChars(String str) {
    if (str.length() > 32768) {
        return false;
    }
    BigInteger checker = new BigInteger(0);
    for (int i = 0; i < str.length(); i++) {
        int val = str.charAt(i);
        if (checker.testBit(val)) return false;
        checker = checker.setBit(val);
    }
    // none of the characters has been seen more than once.
    return true;
}

Ответ 3

Так как значение char может содержать одно из 256 различных значений, любая строка длиной более 256 символов должна содержать по крайней мере один дубликат.

Остальная часть кода использует checker как последовательность бит, причем каждый бит представляет один символ. Кажется, что каждый символ преобразуется в целое число, начиная с a= 1. Затем он проверяет соответствующий бит в checker. Если он установлен, это означает, что символ уже был замечен, и поэтому мы знаем, что строка содержит по крайней мере один повторяющийся символ. Если символ еще не был замечен, код устанавливает соответствующий бит в checker и продолжается.

В частности, (1<<val) генерирует целое число с одним битом 1 в позиции val. Например, (1<<3) будет двоичным 1000 или 8. Выражение checker & (1<<val) будет возвращать ноль, если бит в позиции val не установлен (то есть имеет значение 0) в checker и (1<<val), который всегда отличен от нуля, если этот бит установлен. Выражение checker |= (1<<val) установит этот бит в checker.

Однако алгоритм кажется ошибочным: он, по-видимому, не учитывает символы верхнего регистра и знаки препинания (которые обычно идут до нижнего регистра лексикографически). Казалось бы, для этого требуется 256-битное целое число, которое не является стандартным.

Как rolfl упоминается в комментарии ниже, я предпочитаю ваше решение, потому что оно работает. Вы можете оптимизировать его, возвращая false, как только вы идентифицируете не уникальный символ.

Ответ 4

Это необходимая коррекция для кода книги:

public static boolean checkForUnique(String str){
    boolean containsUnique = false;

    for(char c : str.toCharArray()){
        if(str.indexOf(c) == str.lastIndexOf(c)){
            containsUnique = true;
        } else {
            return false;
        }
    }

    return containsUnique;
}

Ответ 5

Решение из книги нечувствительно к регистру. "A" и "a" считаются дублирующими в соответствии с реализацией.

Объяснение: для строки ввода с char 'A', 'A' - 'a' - -32 поэтому '1 < val 'будет оцениваться как 1 < -32. сдвиг на любое отрицательное число смещает биты в противоположном направлении. таким образом, 1 < -32 будет 1 → 32. Который установит первый бит в 1. Это также относится к char 'a'. Таким образом, "A" и "a" считаются повторяющимися символами. Аналогично для бит "B" и "b" второй бит равен 1 и т.д.

Ответ 6

Обновление шестого издания

    public static void main(String[] args) {
        System.out.println(isUniqueChars("abcdmc")); // false
        System.out.println(isUniqueChars("abcdm")); // true
        System.out.println(isUniqueChars("abcdm\u0061")); // false because \u0061 is unicode a
    }


    public static boolean isUniqueChars(String str) {
        /*
         You should first ask your interviewer if the string is an ASCII string or a Unicode string.
         Asking this question will show an eye for detail and a solid foundation in computer science.
         We'll assume for simplicity the character set is ASCII.
         If this assumption is not valid, we would need to increase the storage size.
         */
        // at 6th edition of the book, there is no pre condition on string length
        /*
         We can reduce our space usage by a factor of eight by using a bit vector.
         We will assume, in the below code, that the string only uses the lowercase letters a through z.
         This will allow us to use just a single int.
          */
        // printing header to provide nice csv format log, you may uncomment
//        System.out.println("char,val,valBinaryString,leftShift,leftShiftBinaryString,checker");
        int checker = 0;
        for (int i = 0; i < str.length(); i++) {
            /*
                Dec Binary Character
                97  01100001    a
                98  01100010    b
                99  01100011    c
                100 01100100    d
                101 01100101    e
                102 01100110    f
                103 01100111    g
                104 01101000    h
                105 01101001    i
                106 01101010    j
                107 01101011    k
                108 01101100    l
                109 01101101    m
                110 01101110    n
                111 01101111    o
                112 01110000    p
                113 01110001    q
                114 01110010    r
                115 01110011    s
                116 01110100    t
                117 01110101    u
                118 01110110    v
                119 01110111    w
                120 01111000    x
                121 01111001    y
                122 01111010    z
             */
            // a = 97 as you can see in ASCII table above
            // set val to be the difference between the char at i and 'a'
            // b = 1, d = 3.. z = 25
            char c = str.charAt(i);
            int val = c - 'a';
            // means "shift 1 val numbers places to the left"
            // for example; if str.charAt(i) is "m", which is the 13th letter, 109 (g in ASCII) minus 97 equals 12
            // it returns 1 and 12 zeros = 1000000000000 (which is also the number 4096)
            int leftShift = 1 << val;
            /*
                An integer is represented as a sequence of bits in memory.
                For interaction with humans, the computer has to display it as decimal digits, but all the calculations
                are carried out as binary.
                123 in decimal is stored as 1111011 in memory.

                The & operator is a bitwise "And".
                The result is the bits that are turned on in both numbers.

                1001 & 1100 = 1000, since only the first bit is turned on in both.

                It will be nicer to look like this

                1001 &
                1100
                =
                1000

                Note that ones only appear in a place when both arguments have a one in that place.

             */
            int bitWiseAND = checker & leftShift;
            String leftShiftBinaryString = Integer.toBinaryString(leftShift);
            String checkerBinaryString = leftPad(Integer.toBinaryString(checker), leftShiftBinaryString.length());
            String leftShiftBinaryStringWithPad = leftPad(leftShiftBinaryString, checkerBinaryString.length());
//            System.out.printf("%s &\n%s\n=\n%s\n\n", checkerBinaryString, leftShiftBinaryStringWithPad, Integer.toBinaryString(bitWiseAND));
            /*
            in our example with string "abcdmc"
            0 &
            1
            =
            0

            01 &
            10
            =
            0

            011 &
            100
            =
            0

            0111 &
            1000
            =
            0

            0000000001111 &
            1000000000000
            =
            0

            1000000001111 &
            0000000000100
            =
            100
             */
//            System.out.println(c + "," + val + "," + Integer.toBinaryString(val) + "," + leftShift + "," + Integer.toBinaryString(leftShift) + "," + checker);
            /*
            char val valBinaryString leftShift leftShiftBinaryString checker
            a   0       0               1       1                       0
            b   1       1               2       10                      1
            c   2       10              4       100                     3
            d   3       11              8       1000                    7
            m   12      1100            4096    1000000000000           15
            c   2       10              4       100                     4111
             */
            if (bitWiseAND > 0) {
                return false;
            }
            // setting 1 on on the left shift
            /*
            0000000001111 |
            1000000000000
            =
            1000000001111
             */
            checker = checker | leftShift;
        }
        return true;
        /*
        If we can't use additional data structures, we can do the following:
        1. Compare every character of the string to every other character of the string.
            This will take 0( n 2 ) time and 0(1) space
        2. If we are allowed to modify the input string, we could sort the string in O(n log(n)) time and then linearly
            check the string for neighboring characters that are identical.
            Careful, though: many sorting algorithms take up extra space.

        These solutions are not as optimal in some respects, but might be better depending on the constraints of the problem.
         */
    }

    private static String leftPad(String s, int i) {
        StringBuilder sb = new StringBuilder(s);
        int charsToGo = i - sb.length();
        while (charsToGo > 0) {
            sb.insert(0, '0');
            charsToGo--;
        }
        return sb.toString();
    }