1. De corectat un program ✖️
A este un array de cifre 0 sau 1 (reprezentarea binară a unui număr, cu A[0] = LSB). Se cere să se afle prima poziție (de la LSB la MSB) de pe care apare cel mai lung șir de biți/cifre 1. De corectat maxim 2 linii (eu am corectat una).
class Solution {
int solution(int[] A) {
int n = A.length;
int i = n - 1;
int result = -1;
int k = 0, maximal = 0;
while (i > 0) {
if (A[i] == 1) {
k = k + 1;
if (k >= maximal) {
maximal = k;
result = i;
}
}
else
k = 0;
i = i - 1;
}
if (A[i] == 1 && k + 1 >= maximal) // correction >= instead of >
result = 0;
return result;
}
}
2. Repartizare pacienți într-un sanatoriu ✔️
Se dau N oaspeți (0... N-1) care așteaptă să fie repartizați pe camere, într-un sanatoriu. Într-o cameră se pot caza oricâți, dar nu toți pacienții vor să aibă mulți colegi de cameră.
Input: un array A cu N elemente, A[K] = numărul maxim de persoane într-o cameră, permis de pacientul K, inclusiv el însuși
Să se afle numărul minim de camere necesare pentru a caza toți pacienții.
import java.util.*;
import java.util.stream.Collectors;
class Solution {
public int solution(int[] A) {
int rooms = 0;
List<Integer> patients = Arrays.stream(A).boxed().collect(Collectors.toList());
Collections.sort(patients);
for (int i=0; i<patients.size(); i++) {
rooms++;
if (patients.get(i) == 1) {
continue;
}
i += patients.get(i);
}
return rooms;
}
}
3. Reducerea unui șir de caractere ✔️
Un șir S conține doar literele A, B, C, D. El se poate transforma eliminând un grup de litere adiacente „AB” sau „CD” (în orice ordine). Să se afle șirul final, după aplicarea tuturor reducerilor posibile. Algoritmul trebuie să fie eficient pt seturi mari de date (un șir de maxim 250.000 caractere).
class Solution {
public String solution2(String word) {
String copy;
do {
copy = word;
word = word.replaceAll("AB", "");
word = word.replaceAll("BA", "");
word = word.replaceAll("CD", "");
word = word.replaceAll("DC", "");
} while (!copy.equals(word));
return word;
}
public String solution(String word) {
if (word.isEmpty()) {
return word;
}
int[] marked = new int[word.length()];
marked[0] = 0;
for (int i=1; i<word.length(); i++) {
marked[i] = 0;
if (condition(word, i, i-1)) {
marked[i] = 1;
marked[i-1] = 1;
i++;
}
}
for (int i=0; i<word.length(); i++) {
if (marked[i] == 1) {
marked = circle(word, i, marked);
i++;
}
}
StringBuilder result = new StringBuilder();
for (int i=0; i<marked.length; i++) {
if (marked[i] == 0) {
result.append(word.charAt(i));
}
}
return result.toString();
}
private int[] circle(String word, int pos, int[] marked) {
int left = pos - 1;
int right = pos + 2;
while (left >= 0 && right < marked.length && marked[left] == 0) {
if (marked[left] == 0 && marked[right] == 0 && condition(word, left, right)) {
marked[left] = 1;
marked[right] = 1;
left--;
right--;
continue;
}
int r2 = right;
while (r2 < marked.length && marked[r2] == 1) {
r2++;
}
if (r2 != right) {
right = r2;
} else {
break;
}
}
return marked;
}
private boolean condition(String word, int i, int j) {
return word.charAt(i) == 'A' && word.charAt(j) == 'B' ||
word.charAt(i) == 'B' && word.charAt(j) == 'A' ||
word.charAt(i) == 'C' && word.charAt(j) == 'D' ||
word.charAt(i) == 'D' && word.charAt(j) == 'C';
}
}
4. Bonus (demo): First Missing Positive ✖️
Given an unsorted integer array nums, return the smallest positive integer that is not present in nums. You must implement an algorithm that runs in O(n) time and uses O(1) auxiliary space.
Prima implementare (firstMissingPositive2): O(n^2) timp și O(n) spațiu
A doua implementare (firstMissingPositive): O(n) timp și O(1) spațiu
class Solution {
public int firstMissingPositive2(int[] nums) {
if (initialCheck(nums) == 1) {
return 1;
}
Set<Integer> elems = new HashSet<>();
for (int num : nums) {
elems.add(num);
}
for (int i=1; ; i++) {
if (!elems.contains(i)) {
return i;
}
}
}
private int initialCheck(int[] nums) {
boolean allNegative = true;
int min = Integer.MAX_VALUE;
for (int i=0; i<nums.length; i++) {
if (nums[i] > 0) {
allNegative = false;
if (min > nums[i]) {
min = nums[i];
}
}
}
if (allNegative || min > 1) {
return 1;
}
return 0;
}
private boolean isArrayComplete(int[] nums, int max) {
int xor = 0;
int times = 0;
for (int i=0; i<nums.length; i++) {
if (nums[i] > 0) {
xor = xor ^ nums[i];
times++;
}
}
for (int i=1; i<=times; i++) {
xor = xor ^ i;
}
return xor == 0 && times == max;
}
public int firstMissingPositive(int[] nums) {
if (initialCheck(nums) == 1) {
return 1;
}
// find min, max
int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
for (int i=0; i<nums.length; i++) {
if (nums[i] < 0) {
nums[i] = 0;
}
if (max < nums[i]) {
max = nums[i];
}
if (min > nums[i] && min > 0) {
min = nums[i];
}
}
if (min == 1 && isArrayComplete(nums, max)) {
return max + 1;
}
// tag in place
int tag = max != Integer.MAX_VALUE ? max + 1 : max;
for (int i=0; i<nums.length; i++) {
int val = nums[i] >= tag ? nums[i]-tag : nums[i]; // untag/extract if already tagged
if (val > 0 && val < nums.length && nums[val-1] < tag) { // avoid duplicates
nums[val-1] += tag;
}
}
// find first untagged
for (int i=0; i<nums.length; i++) {
if (nums[i] < tag && nums[i] >= 0) {
return i+1;
}
}
return max + 1; // should not arrive here
}
}
Niciun comentariu:
Trimiteți un comentariu