Вопрос по java – уникальные символы со смещением и операторами: не понимаю этот код

3

Я не понимаю строки в цикле: мы берем символ и вычитаемaтак что "10" ? (Зачем?)
затем1 << val : мы сдвигаем 1 на val? (Зачем?)
и проверка равна 0, так как мы достигаем> 0 в состоянии?

    public static boolean isUniqueChars(String str) {
    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;
}

Спасибо

Этот код будет работать правильно только тогда, когда строка состоит из строчных символов. kenor

Ваш Ответ

3   ответа
1

str.charAt(i) - 'a' более или менее возвращает "букву в алфавите": еслиstr.charAt(i) является'a', это0если это'b', val является1если этоz, val является25, и так далее.

Остальная часть этого использует технику немного-переворота: еслиvalй битchecker является1мы увиделиvalй персонаж уже. Такchecker & (1 << val) отличен от нуля тогда и только тогда, когдаvalй битchecker установлено, что означает, что мы уже видели этот символ. В противном случае мы устанавливаемvalй битchecker и продолжить цикл.

Error: User Rate Limit ExceededintError: User Rate Limit Exceeded+ (1 << val)Error: User Rate Limit Exceeded| (1 << val)Error: User Rate Limit Exceeded|Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded Paul
Error: User Rate Limit Exceeded Paul
0

Вопрос довольно старый, но я думаю, что мой ответ правильный и понятный. Мы имеем дело с строчными буквами только в этом случае. Как сказал Павел,(1 << val) означает сдвиг 1 на «val» не сдвиг 'val' одним. Так, например, «привет» дает:

1st loop: val = 111 in binary, 7 in decimal
          1 << val = 10000000  <-- here one is shifted by 7
          checker = 10000000 
2nd loop: val = 100 in binary, 4 in decimal
          1 << val = 10000
          checker = 10010000
3rd loop: val = 1011 in binary, 11 in decimal
          1 << val = 100000000000
          checker = 100010010000
4th loop: val = 1011 in binary, 11 in decimal
          1 << val = 100000000000
         (checker & (1 << val)) gives 100000000000 which is greater than 0
The loop is over because 'l' is not unique after 'hel' in 'hello'.

Я надеюсь, что это проясняет вещи. У меня есть исходный код, если вы хотите точно узнать, что происходит.

public class one_one_one {

    public static void main(String[] args) {
    String chars = "hello"; 
    if (isUniqueChars(chars)) {
        System.out.println("Unique");
    } else {
        System.out.println("Not Unique");
    }
    }

    public static boolean isUniqueChars(String str) {
    int checker = 0;
    for (int i = 0; i < str.length(); i++) {
        int val = str.charAt(i) - 'a';
        System.out.println(Integer.toBinaryString(val)); //debug printout
        int temp = 1 << val;
        System.out.println(Integer.toBinaryString(temp)); //debug printout
        System.out.println(checker & (1 << val)); //debug printout
        if ((checker & (1 << val)) > 0) {
        return false;
        }
        checker |= (1 << val);
        System.out.println(Integer.toBinaryString(checker)); //debug printout
        System.out.println(' '); //debug printout
    }
    return true;
    }
}
Error: User Rate Limit Exceeded
7

Код предполагает, чтоstr состоит из строчных букв и возвращает истину, если нет повторяющихся букв. Это работает так:

checker используется в качестве растрового изображения, то есть каждый бит в этой переменной используется для отслеживания одной буквы. Вычитая "а"; из символа дает 0 для «a», 1 для «b», 2 для «c»; и т. д. Сдвиг 1 влево на это число дает 1 для «a», 2 для «b», 4 для «c»; и т.п.

По oring (|) это значение сchecker код отслеживает ранее встреченные символы. Таким образом, если мы сталкиваемся со вторым 'a'; например,checker имеет первый установленный бит (который проверяется& в операторе if), поэтому мы знаем, чтоstr есть дубликаты.

Короче,checker используется в качестве более быстрого и более компактного массива bool. Это и подобные методы называютсянемного манипуляций.

Error: User Rate Limit Exceeded|Error: User Rate Limit Exceeded1Error: User Rate Limit Exceeded0Error: User Rate Limit ExceededcheckerError: User Rate Limit Exceeded Paul
Error: User Rate Limit ExceededintError: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded
Error: User Rate Limit Exceeded Paul

Похожие вопросы