В силу определённых обстоятельств – периодически стал возникать вопрос, в каких временных рамках я занимался тем или иным проектом. И готового ответа на него у меня не было – как-то не приходило в голову фиксировать подобную информацию.
Но есть же git – ведь он поможет? Ведь поможет, да?
Вторая из ранее сохранённых и ныне обретённых задачек с 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
Очередная задачка уровня 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/
Ещё одна простая задачка – определение процентного содержания целевого символа в исходной строке. Пара решений:
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/
Тоже забавная задачка – со “сломанной клавиатурой”. Решил в ней 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/
Решил слегка “причесать” и обобщить свой опыт по этому вопросу. Чтобы удобней было пользоваться, как этакой краткой инструкцией, а не искать разрозненные ответы на SO и т.п.
Задача проста – сделать удобно 🙂
Приятная задачка выпала в поиске – хоть и 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;
}
}Возникла потребность настраивать по-разному конфиги гита для разных проектов (email контактный поменять, хотя бы, или хук на прогон тестов повесить).
Ну и понятно, что как-то эти конфиги подкладывать туда-сюда – не слишком увлекательно. К счастью, в свежих версиях гита – есть инклюды. В том числе – по условию – includeIf. Вот ими и стоит воспользоваться.
После долгих праздничных выходных – приходится “разогревать” голову задачками с высоким 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/
Да, с серединки 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/