يحتوي تحديد سلسلة على جميع الأحرف الفريدة دون استخدام هياكل بيانات إضافية وبدون افتراض الأحرف الصغيرة

Question

هذا هو واحد من الأسئلة في تكسير مقابلة الترميز كتاب بقلم غايل لاكمان ماكدويل:

قم بتنفيذ خوارزمية لتحديد ما إذا كانت السلسلة تحتوي على جميع الأحرف الفريدة.ماذا لو لم تتمكن من استخدام هياكل بيانات إضافية?

كتب المؤلف:

يمكننا تقليل استخدامنا للمساحة قليلا باستخدام متجه قليلا.سنفترض ، في الكود أدناه ، أن السلسلة هي حالة صغيرة فقط 'a' من خلال 'z'.وهذا سوف يسمح لنا لاستخدام واحد فقط كثافة العمليات.

المؤلف لديه هذا التنفيذ:

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;
}

لنفترض أننا تخلصنا من افتراض أن " السلسلة ليست سوى حالة صغيرة 'a' من خلال 'z'".بدلا من ذلك ، يمكن أن تحتوي السلسلة على أي نوع من أحرف أسي مثل الأحرف أو أحرف يونيكود.

هل هناك حل فعال مثل المؤلف (أو الحل الذي يقترب من كونها فعالة مثل المؤلف)?

أسئلة ذات صلة:

• اكتشاف ما إذا كانت السلسلة تحتوي على أحرف فريدة:مقارنة الحل الخاص بي بـ " تكسير مقابلة الترميز?"
• اشرح استخدام متجه بت لتحديد ما إذا كانت جميع الأحرف فريدة
• سلسلة أحرف فريدة من نوعها
• تنفيذ خوارزمية لتحديد ما إذا كانت السلسلة تحتوي على جميع الأحرف الفريدة
• حدد ما إذا كانت السلسلة تحتوي على جميع الأحرف الفريدة?

Answer 1

لمجموعة الأحرف أسكي يمكنك تمثيل 256 بت في 4 لونغ:كنت أساسا رمز اليد صفيف.

public static boolean isUniqueChars(String str) {
    long checker1 = 0;
    long checker2 = 0;
    long checker3 = 0;
    long checker4 = 0;
    for (int i = 0; i < str.length(); ++i) {
        int val = str.charAt(i);
        int toCheck = val / 64;
        val %= 64;
        switch (toCheck) {
            case 0:
                if ((checker1 & (1L << val)) > 0) {
                    return false;
                }
                checker1 |= (1L << val);
                break;
            case 1:
                if ((checker2 & (1L << val)) > 0) {
                    return false;
                }
                checker2 |= (1L << val);
                break;
            case 2:
                if ((checker3 & (1L << val)) > 0) {
                    return false;
                }
                checker3 |= (1L << val);
                break;
            case 3:
                if ((checker4 & (1L << val)) > 0) {
                    return false;
                }
                checker4 |= (1L << val);
                break;
        }            
    }
    return true;
}

يمكنك استخدام التعليمات البرمجية التالية لتوليد الجسم من طريقة مماثلة لأحرف يونيكود:

static void generate() {
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < 1024; i++) {
        sb.append(String.format("long checker%d = 0;%n", i));
    }
    sb.append("for (int i = 0; i < str.length(); ++i) {\n"
            + "int val = str.charAt(i);\n"
            + "int toCheck = val / 64;\n"
            + "val %= 64;\n"
            + "switch (toCheck) {\n");
    for (int i = 0; i < 1024; i++) {
        sb.append(String.format("case %d:\n"
                + "if ((checker%d & (1L << val)) > 0) {\n"
                + "return false;\n"
                + "}\n"
                + "checker%d |= (1L << val);\n"
                + "break;\n", i, i, i));
    }
    sb.append("}\n"
            + "}\n"
            + "return true;");
    System.out.println(sb);
}

Answer 2

ما عليك سوى سطر واحد...حسنا أقل من سطر واحد في الواقع:

if (str.matches("((.)(?!.*\\1))*"))

يستخدم هذا نظرة سلبية إلى الأمام لتأكيد أن كل حرف لا يتكرر لاحقا في السلسلة.

هذا النهج تعقيد وقت س (ن^2) ، لأنه بالنسبة للجميع ن الأحرف في الإدخال ، تتم مقارنة جميع الأحرف التالية (هناك ن من هؤلاء) من أجل المساواة.

Answer 3

أعتقد أننا بحاجة إلى تعريف عام وعملي لـ"هياكل البيانات الإضافية".حدسي ، ونحن لا نريد أن ندعو كل عدد صحيح العددية أو مؤشر "بنية البيانات" ، لأن ذلك يجعل هراء من أي حظر "هياكل البيانات الإضافية".

أقترح أن نستعير مفهوما من تدوين كبير:"بنية البيانات الإضافية" هي تلك التي تنمو مع حجم مجموعة البيانات.

في الحالة الحالية ، يبدو أن الكود المقتبس من البروتوكول الاختياري يحتوي على متطلبات مساحة س (1) لأن متجه البت يتناسب مع نوع عدد صحيح.ولكن كما يوحي البروتوكول الاختياري ، فإن الشكل العام للمشكلة هو حقا س (ن).

مثال على حل للحالة العامة هو استخدام مؤشرين وحلقة متداخلة لمقارنة كل حرف مع كل حرف آخر.شرط الفضاء هو س (1) ولكن شرط الوقت هو س(ن^2).

Answer 4

ماذا عن الخوارزمية التالية?

الخطوات:

تحويل السلسلة إلى أحرف صغيرة.

حلقة من خلال كل حرف في السلسلة

تعيين البيانات المتغيرة = 0

حساب الإزاحة = قيمة أسي من الحرف الأول في سلسلة-97

تعيين العلم لهذا الموقف مع قناع = 1 << الإزاحة

إذا بيتويز ويعود صحيح ، ثم حرف يتكرر (قناع والبيانات) ، لذلك كسر هنا.

آخر إذا لم نر تكرار الحرف حتى الآن ، تعيين بت لهذا الحرف عن طريق القيام قليلا أو عن طريق القيام البيانات = البيانات / قناع

استمر حتى نهاية الشخصيات.