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

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/

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/

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/

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

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/

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/

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/

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/

Hybris: поиск Solr по составному полю

Понадобилось как-то в SAP Hybris настроить поиск по составному полю (состоящему из нескольких атрибутов продукта). Так, чтобы при запросе вида “желтый ботинок” в листинге товаров сначала выдавались не просто товары желтого цвета, а именно желтые ботинки (а затем – остальные ботинки). Решить это регулировкой коэффициентов усиления поиска по отдельным свойствам (boost) не удалось, пришлось городить огород с созданием и индексацией составного поля.

Модель товара ProductModel

Итак, в предлагаемом примере товар (Product) имеет два атрибута (помимо прочих), по которым надо искать в связке:

  • Name – название товара
  • Color – его цвет
Читать далее Hybris: поиск Solr по составному полю

Ограничение на минимальную цену в Hybris

Понадобилось добавить ограничение цены для товара в SAP Commerce (Hybris) – десятичная цена должна быть больше или равна нулю.
В принципе – это не сложно сделать через Backoffice (Система - Проверка - Ограничения), но тогда, при переиницаиализации платформы, внесённые изменения будут удалены. Поэтому – лучше создать файл impex, который автоматически накатится при обновлении или инициализации Hybris.
Чтобы не забыть – сохраню себе на память содержимое такого файла. Проверить работоспособность можно вручную – в HAC (Console - ImpEx Import), после чего надо перезагрузить механизм ограничений в Backoffice.
Что даёт это ограничение – при попытке задать товару нулевую или отрицательную цену – будет выскакивать соответствующее сообщение об ошибке (содержимое message[lang=en] или message[lang=ru], в зависимости от текущей локали).


INSERT_UPDATE DecimalMinConstraint;id[unique=true];severity(code,itemtype(code));active;annotation;descriptor(enclosingType(code),qualifier);message[lang=en];message[lang=ru];value;inclusive
;PriceMustBeGreaterThanZero;ERROR:Severity;true;javax.validation.constraints.DecimalMin;PriceRow:price;Price must be greater than zero;Цена должна быть больше нуля;0,00000000;false