Архив метки: algorithms

Problem solving, Алгосы

HackerRank Bit Manipulation: Counter game

Оставить комментарий

Вторая из ранее сохранённых и ныне обретённых задачек с HackerRank. Как понятно из заголовка — решается через битовые операции.

Хотя — теоретическим можно было бы помучиться с BigInteger и арифметикой… И посмотреть, какое время займёт поиск решения.

import java.util.Scanner;

public class Solution {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int t = in.nextInt();
        for (int a0 = 0; a0 < t; a0++) {
            long n = in.nextLong();
            String result = counterGame(n - 1);
            System.out.println(result);
        }
        in.close();
    }

    private static String counterGame(long n) {
        //long mask = 0x8000000000000000L; //2^63 in hex //W
        //eq:
        //long mask = -9223372036854775808L; //2^63 //W
        long mask;
        int step = 0;
        for (int i = 63; i >= 0; i--) {
            mask = 1L << i;
            //compare with 2 power i
            if ((n & mask) != 0) {
                //we max 2^i
                //step++;
                step = step ^ 1;
            }
            n -= mask;
            //mask >>>= 1;
        }

        return ((step & 1) != 0) ? "Louise" : "Richard";
    }

}

Традиционно — решение на Гитхабе.

https://www.hackerrank.com/challenges/counter-game/problem
Problem solving, Алгосы

LeetCode 125. Valid Palindrome

Оставить комментарий

Очередная задачка уровня Easy, но с довольно низким показателем Acceptance (44.4%). Что выражается в достаточно обширном наборе граничных случаев, некоторые из которых делают больно 🙂

Было желание сделать за один проход по исходной строке (без выделения дополнительно памяти). Вроде даже получилось, если ориентироваться на статистику запуска с LeetCode.

class Solution {

    private static final int LETTER_CASE_SHIFT = 32;

    public boolean isPalindrome(String s) {
        if (s.length() == 1) return true;
        char a, b;
        int mid = (s.length() - 1) >>> 1;
        for (int i = 0, j = s.length() - 1; i <= mid; i++, j--) {
            a = s.charAt(i);
            b = s.charAt(j);
            while (isNotAlphaNumeric(a) && i < j) {
                a = s.charAt(++i);
            }
            while (isNotAlphaNumeric(b) && i < j) {
                b = s.charAt(--j);
            }
            if (isComparable(a, b)) {
                if (!equalsIgnoreCase(a, b)) {
                    return false;
                }
            } else {
                return false;
            }
            mid = (i + j) / 2;
        }
        return true;
    }

    private static boolean equalsIgnoreCase(char a, char b) {
        return a == b
            || a - LETTER_CASE_SHIFT == b
            || a == b - LETTER_CASE_SHIFT;
    }

    private static boolean isComparable(char a, char b) {
        return (isLetter(a) && isLetter(b))
            || (!isLetter(a) && !isLetter(b));
    }

    private static boolean isLetter(char ch) {
        return 'a' <= ch && ch <= 'z'
            || 'A' <= ch && ch <= 'Z';
    }

    private static boolean isNotAlphaNumeric(char ch) {
        return !isLetter(ch) && ('0' > ch || ch > '9');
    }

}
Success:
    Runtime:2 ms, faster than 99.92% of Java online submissions.
    Memory Usage:42.3 MB, less than 87.41% of Java online submissions.

Ссылка на решение на Гитхаб.

A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.
Given a string s, return true if it is a palindrome, or false otherwise.
https://leetcode.com/problems/valid-palindrome/
Problem solving, Алгосы

LeetCode 2278. Percentage of Letter in String

Оставить комментарий

Ещё одна простая задачка — определение процентного содержания целевого символа в исходной строке. Пара решений:

  • через стримы (примитивно, без кастомной свёртки, да и помедленней)
  • и через цикл for.

Стримы

public int percentageLetter(String s, char letter) {
    long cnt = s.chars().filter(it -> it == (int) letter).count();
    return (int) (100 * cnt / s.length());
}
Success:
    Runtime:2 ms, faster than 12.22% of Java online submissions.
    Memory Usage:40.6 MB, less than 45.95% of Java online submissions.

Цикл

public int percentageLetter(String s, char letter) {
    int cnt = 0;
    for (char c : s.toCharArray()) {
        cnt += c == letter ? 1 : 0;
    }
    return 100 * cnt / s.length();
}
Success:
    Runtime:0 ms, faster than 100.00% of Java online submissions.
    Memory Usage:40.1 MB, less than 88.72% of Java online submissions.

Решение на гитхабе.

Given a string s and a character letter, return the percentage of characters in s that equal letter rounded down to the nearest whole percent.
https://leetcode.com/problems/percentage-of-letter-in-string/
Problem solving, Алгосы

LeetCode 1935. Maximum Number of Words You Can Type

Оставить комментарий

Тоже забавная задачка — со «сломанной клавиатурой». Решил в ней Arrays.binarySearch использовать для поиска буквы слова в наборе «сломанных клавишей», да и чтобы не забыть о его (метода) существовании в целом.

Судя по статистике — нормально получилось, в общем-то.

class Solution {
    public int canBeTypedWords(String text, String brokenLetters) {
        var brL = brokenLetters.toCharArray();
        Arrays.sort(brL);
        var words = text.split(" ");
        int canTypeCnt = 0;
        for (var word : words) {
            boolean canType = true;
            for (int i = 0; i < word.length(); i++) {
                if (Arrays.binarySearch(brL, word.charAt(i)) >= 0) {
                    canType = false;
                    break;
                }
            }
            if (canType) {
                canTypeCnt++;
            }
        }
        return canTypeCnt;
    }
}
Success:
	Runtime:2 ms, faster than 91.93% of Java online submissions.
	Memory Usage:42.7 MB, less than 23.23% of Java online submissions.

То же решение на гитхабе.

There is a malfunctioning keyboard where some letter keys do not work. All other keys on the keyboard work properly.

Given a string text of words separated by a single space (no leading or trailing spaces) and a string brokenLetters of all distinct letter keys that are broken, return the number of words in text you can fully type using this keyboard.
https://leetcode.com/problems/maximum-number-of-words-you-can-type/
Problem solving, Алгосы

LeetCode 13. Roman to Integer

Оставить комментарий

Приятная задачка выпала в поиске — хоть и easy, а сделать интересно. Какая-то «практическая применимость» в ней видится.

Вроде, там где-то и обратная проблема была — перевод записи арабскими цифрами в запись римскими.

В общем-то, список валидных префиксов там прямо в условии задачи описан, особо выдумывать тут ничего не требуется.

class Solution {
    private Map<Character, Integer> values = Map.of('I', 1, 'V', 5, 'X', 10, 'L', 50, 'C', 100, 'D', 500, 'M', 1000);
    private Map<Character, Set<Character>> prefixes = Map.of('I', Set.of('V', 'X'), 'X', Set.of('L', 'C'), 'C', Set.of('D', 'M'));

    public int romanToInt(String s) {
        int max = s.length() - 1;
        int sum = 0;
        int i = 0;
        while (i <= max) {
            char c = s.charAt(i);
            if (prefixes.containsKey(c) && i < max && prefixes.get(c).contains(s.charAt(i + 1))) {
                sum += values.get(s.charAt(++i)) - values.get(c);
            } else {
                sum += values.get(c);
            }
            i++;
        }
        return sum;
    }
}
Читать далее LeetCode 13. Roman to Integer →
Problem solving, Алгосы

Leetcode 1920. Build Array from Permutation

Оставить комментарий

После долгих праздничных выходных — приходится «разогревать» голову задачками с высоким Acceptance. И даже они — не сразу заходят. Со скрипом.

class Solution {
    public static int[] buildArray(int[] nums) {
        int[] ans = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            ans[i] = nums[nums[i]];
        }
        return ans;
    }
}
Given a zero-based permutation nums (0-indexed), build an array ans of the same length where ans[i] = nums[nums[i]] for each 0 <= i < nums.length and return it.

A zero-based permutation nums is an array of distinct integers from 0 to nums.length - 1 (inclusive).

https://leetcode.com/problems/build-array-from-permutation/description/
Problem solving, Алгосы

Leetcode 1360. Number of Days Between Two Dates

Оставить комментарий

Да, с серединки Acceptance начинается интересное уже. Процентов от 65 даже, и в сторону убывания.

Сомневаюсь, конечно, что в секции алгоритмических задач предполагался подобный подход… На это намекает и весьма нескромное время выполнения — 9ms.

Но оно работает. Для начала — уже недурно.

import java.time.Duration;
import java.time.LocalDate;

class Solution {
    public int daysBetweenDates(String date1, String date2) {
        return date1.equals(date2)
        ? 0
        : Math.abs((int) Duration.between(
            LocalDate.parse(date1).atStartOfDay(),
            LocalDate.parse(date2).atStartOfDay()
        ).toDays());
    }
}
Write a program to count the number of days between two dates.

The two dates are given as strings, their format is YYYY-MM-DD as shown in the examples.

https://leetcode.com/problems/number-of-days-between-two-dates/description/
Problem solving, Алгосы

Leetcode 2469. Convert the Temperature

Оставить комментарий

Мда… Надо, похоже, в обратном порядке по Acceptance сортировать. Это слишком уж просто, даже для меня, весьма неискушенного в подобных задачах.

You are given a non-negative floating point number rounded to two decimal places celsius, that denotes the temperature in Celsius.

You should convert Celsius into Kelvin and Fahrenheit and return it as an array ans = [kelvin, fahrenheit].

Return the array ans. Answers within 10^-5 of the actual answer will be accepted.
class Solution {
    public double[] convertTemperature(double celsius) {
        return new double[] {celsius + 273.15d, celsius * 1.80d + 32.00d};
    }
}
https://leetcode.com/problems/convert-the-temperature/description/
Problem solving, Алгосы

Leetcode 1929. Concatenation of Array

Оставить комментарий

В процессе потения над Advent of Code понял, что надо алгосы держать в тонусе — иначе задачи даются тяжко.

Рецепт давно известен — Литкод. Успел там челлендж на первый уровень алгосов пройти и решил, что неплохо бы посохранять это всё где-то. Почему бы не здесь?

Начнём с простого, даже — примитивного. Не особо понял, при чем тут объединение массивов, скорее — генерация какая-то.

class Solution {
    public static int[] getConcatenation(int[] nums) {
        int[] ans = new int[nums.length * 2];
        for (int i = 0; i < nums.length; i++) {
            ans[i] = ans[i + nums.length] = nums[i];
        }
        return ans;
    }
}
https://leetcode.com/problems/concatenation-of-array/description/