Добрый день, неделю уже решаю эту задачу с переменным успехом, почему не проходит последний пункт? создал метод для проверки чисел из ответа и полученные мной. Я предполагаю что не прохожу проверку из-за памяти? P.s. пытался пройти валидацию когда время было 7 сек. с тех пор я поправил немного решение и время вышло за 10. в чем еще может быть причина последнего пункта? P.s код можно не читать потому что там столько костылей, может кто знает еще типичные ошибки. я вроде все комментарии прочитал и не знаю что делать
package com.javarush.task.task20.task2025;
import java.util.*;
/*
Алгоритмы-числа
*/
public class Solution {
//CHECK
static HashMap<Long, Long> massive = new HashMap<>();
static TreeSet<Long> firstResult = new TreeSet<>();
public static long[] getNumbers(long N) {
long[] result = null;
try {
int[] list = generatorChisel(N);
while (!(list[list.length-1] == (0))) {
newMethodofChek(list);
}
int len = 0;
for (long l : firstResult) {
if (l < N){
len++;
}
}
result = new long[len];
int i = 0;
for (Long l : firstResult){
result[i] = l;
i++;
}
cheeeeek(firstResult);
firstResult.clear();
massive.clear();
}catch (Exception e){}
return result;
}
public static void cheeeeek(TreeSet<Long> firstResult){
long[] temp = {1, 2, 3, 4, 5, 6, 7, 8, 9, 153, 370, 371, 407, 1634, 8208, 9474, 54748, 92727, 93084, 548834, 1741725, 4210818, 9800817, 9926315, 24678050, 24678051, 88593477, 146511208, 472335975, 534494836, 912985153, 4679307774L, 32164049650L, 32164049651L, 40028394225L, 42678290603L, 44708635679L, 49388550606L, 82693916578L, 94204591914L, 28116440335967L, 4338281769391370L, 4338281769391371L, 21897142587612075L, 35641594208964132L, 35875699062250035L, 1517841543307505039L, 3289582984443187032L, 4498128791164624869L, 4929273885928088826L};
int i = 0;
for (Long l : firstResult){
if (l != temp[i]){
System.out.println("False");
}
i++;
}
System.out.println("true");
}
public static void main(String[] args) {
long a = System.currentTimeMillis();
System.out.println(Arrays.toString(getNumbers(Long.MAX_VALUE)));
long b = System.currentTimeMillis();
System.out.println("memory " + (Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory()) / (8 * 1024));
System.out.println("time = " + (b - a) / 1000);
a = System.currentTimeMillis();
System.out.println(Arrays.toString(getNumbers(2)));
b = System.currentTimeMillis();
System.out.println("memory " + (Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory()) / (8 * 1024));
System.out.println("time = " + (b - a) / 1000);
}
public static int findRazr(long N) {
int razr = 0;
while (N > 0) {
razr++;
N /= 10;
}
return razr;
}
public static int[] generatorChisel(long N) { //Создает генератор из {9,9,9,9...}
int razryad = findRazr(N);
int[] collectionNumber = new int[razryad];
for (int i = 0; i < razryad; i++) {
collectionNumber[i] = 9;
}
return collectionNumber;
}
public static void decrementGenerator(int[] generator) { //находит след число
int i = 0;
while (i < generator.length) {
if (generator[i] > 0) {
generator[i] = generator[i] - 1;
return;
} else {
i++;
for (int j = 0; j < i; j++) {
generator[j] = generator[i] - 1;
}
}
}
} //находит след число
public static Long massivStepeney(int[] generatorBase, int degree) {
Long result = 0l;
long key = 0l;
for (int j : generatorBase) {
if (j == 0) {
continue;
}
if (j == 1) {
result++;
continue;
}
key = 100L * j + degree;
if (!massive.containsKey(key)){
long value = 1;
for (int i = 0; i < degree; i++) {
value *= j;
}
result += value;
massive.put(key,value);
}
else {
result += massive.get(key);
}
}
return result;
} // REZULT коллекция степеней массива
public static void newMethodofChek(int[] generatorBase) {
int stepen = degree(generatorBase);
int sizeGeneratora = generatorBase.length;
while (stepen <= sizeGeneratora) {
long longFULL = massivStepeney(generatorBase, stepen); //REZULT получаем сумму чисел в степени
//if (longFULL == 0 ){stepen++; continue;}
if(stepen == findRazr(longFULL)){
int[] stepenChisloInArr = new int[stepen];
if (fromLongtoArray(longFULL, stepenChisloInArr)) { //разбиваем число суммы обратно в массив
cheking(generatorBase, stepenChisloInArr, longFULL);
}
}
stepen++;
}
decrementGenerator(generatorBase);
}
public static void cheking(int[] generatorBase, int[] stepenChisloInArr,Long longFULL) {
Map<Integer, Integer> mapchek = new HashMap<>();
for (int j : generatorBase) {
if (j == 0) {
continue;
}
if (!mapchek.containsKey(j)) {
mapchek.put(j, 1);
} else {
mapchek.put(j, mapchek.get(j) + 1);
}
}
for (int j : stepenChisloInArr) {
if (j == 0) {
continue;
}
if (!(mapchek.containsKey(j))) {
return;
} else {
mapchek.put(j, mapchek.get(j) - 1);
}
}
for (int v : mapchek.values()) {
if (v != 0) return ;
}
firstResult.add(longFULL);
}
public static boolean fromLongtoArray(long N, int[] list) {
int i = 0;
try {
while (N > 0) {
list[i] = ( (int) (N % 10L));
N /= 10L;
i++;
}
}catch (Exception e){return false;}
return true;
}
public static int degree(int[] generatorBase) {
int degree = generatorBase.length;
for (int i : generatorBase){
if (i == 0) {
degree--;
} else break;
}
return degree;
} //в какую степень возводить число
}