AE
В телеграмме можно так скидывать код? Это как?
Почитай про markdown разметку.
code
Size: a a a
2020 April 25
A(
AE
Привет!
Есть задача по поиску Z-функции строки, выполняю её на моей любимой джаве:
Для считывания и записи используется два файла, применяю буферизованны IO API:
Но вот если попробовать в input передать рандомную строку размеров 92670 символов, но алгоритм не проходит ограничение по времени. Может ли быть беда в алгоритме?
Есть задача по поиску Z-функции строки, выполняю её на моей любимой джаве:
private static int[] zFucntion(String s) {
int n = s.length();
int z[] = new int[n];
for (int i = 1, l = 0, r = 0; i < n; ++i) {
if (i <= r) {
z[i] = Math.min(r - i + 1, z[i - l]);
}
while (i + z[i] < n && s.split("")[z[i]].equals(s.split("")[i + z[i]])) {
++z[i];
}
if (i + z[i] - 1 > r) {
l = i;
r = i + z[i] - 1;
}
}
return z;
}Для считывания и записи используется два файла, применяю буферизованны IO API:
private static final File inputFile = new File("input.txt");
private static final File outputFile = new File("output.txt");
public static void main(String[] args) throws IOException {
BufferedReader input = new BufferedReader(new FileReader(inputFile));
BufferedWriter writer = new BufferedWriter(new FileWriter(outputFile));
String data;
try {
while ((data = input.readLine()) != null) {
int[] prefixes = zFucntion(data);
StringBuilder outputData = new StringBuilder();
for (int i = 1; i < prefixes.length; i++) {
outputData.append(prefixes[i]).append(" ");
}
writer.write(outputData.toString().trim() + "\n");
}
} finally {
input.close();
writer.close();
}
}Но вот если попробовать в input передать рандомную строку размеров 92670 символов, но алгоритм не проходит ограничение по времени. Может ли быть беда в алгоритме?
Так, вопрос отменяется, я тупанул)
AE
Два раза выполнял операцию split у строки)
AD
попробуй .charAt()
AE
Так можно ещё ускорить, да.
Ф
Добрый вечер. Не подскажите, как называется такая штука - запускаю поиск пути (А*) для персонажа -> получаю массив точек. Через некоторое время (т.е. первый персонаж уже прошёл какой-то путь) запускаю поиск пути для другого персонажа. И мне нужно узнать пересекутся ли эти пути во времени. Поскольку таких персонажей может быть довольно много, наивный способ на каждый шаг проверять - а не будет ли рядом в это же время других персонажей, - мне кажется будет довольно неторопливым. Есть ли уже что-то подобное A* для такой задачи, и если есть - по каким словам это гуглить. Спасибо ^_^
SE
Федор
Добрый вечер. Не подскажите, как называется такая штука - запускаю поиск пути (А*) для персонажа -> получаю массив точек. Через некоторое время (т.е. первый персонаж уже прошёл какой-то путь) запускаю поиск пути для другого персонажа. И мне нужно узнать пересекутся ли эти пути во времени. Поскольку таких персонажей может быть довольно много, наивный способ на каждый шаг проверять - а не будет ли рядом в это же время других персонажей, - мне кажется будет довольно неторопливым. Есть ли уже что-то подобное A* для такой задачи, и если есть - по каким словам это гуглить. Спасибо ^_^
на гпу считать)
Ф
я так понял, это про просто pathfinding. А мне бы коллизии результатов этих самых pathfinder'ов. Переделывать условия (непроходимые клетки) на каждый ход мне кажется тоже будет довольно дорогим развлечением... Но может я и ошибаюсь :-)
m
Федор
Добрый вечер. Не подскажите, как называется такая штука - запускаю поиск пути (А*) для персонажа -> получаю массив точек. Через некоторое время (т.е. первый персонаж уже прошёл какой-то путь) запускаю поиск пути для другого персонажа. И мне нужно узнать пересекутся ли эти пути во времени. Поскольку таких персонажей может быть довольно много, наивный способ на каждый шаг проверять - а не будет ли рядом в это же время других персонажей, - мне кажется будет довольно неторопливым. Есть ли уже что-то подобное A* для такой задачи, и если есть - по каким словам это гуглить. Спасибо ^_^
Мне кажется, можно динамически менять веса в графе. Кажется, это нарушит оптимальность, но на первый взгляд будет работать.
2020 April 26
ML
nihao
V🇺
Привет!
Есть задача по поиску Z-функции строки, выполняю её на моей любимой джаве:
Для считывания и записи используется два файла, применяю буферизованны IO API:
Но вот если попробовать в input передать рандомную строку размеров 92670 символов, но алгоритм не проходит ограничение по времени. Может ли быть беда в алгоритме?
Есть задача по поиску Z-функции строки, выполняю её на моей любимой джаве:
private static int[] zFucntion(String s) {
int n = s.length();
int z[] = new int[n];
for (int i = 1, l = 0, r = 0; i < n; ++i) {
if (i <= r) {
z[i] = Math.min(r - i + 1, z[i - l]);
}
while (i + z[i] < n && s.split("")[z[i]].equals(s.split("")[i + z[i]])) {
++z[i];
}
if (i + z[i] - 1 > r) {
l = i;
r = i + z[i] - 1;
}
}
return z;
}Для считывания и записи используется два файла, применяю буферизованны IO API:
private static final File inputFile = new File("input.txt");
private static final File outputFile = new File("output.txt");
public static void main(String[] args) throws IOException {
BufferedReader input = new BufferedReader(new FileReader(inputFile));
BufferedWriter writer = new BufferedWriter(new FileWriter(outputFile));
String data;
try {
while ((data = input.readLine()) != null) {
int[] prefixes = zFucntion(data);
StringBuilder outputData = new StringBuilder();
for (int i = 1; i < prefixes.length; i++) {
outputData.append(prefixes[i]).append(" ");
}
writer.write(outputData.toString().trim() + "\n");
}
} finally {
input.close();
writer.close();
}
}Но вот если попробовать в input передать рандомную строку размеров 92670 символов, но алгоритм не проходит ограничение по времени. Может ли быть беда в алгоритме?
AE
EZ
Топ стикер
i
Какую метрику схожести можно определить на временных рядах SARIMA?
i
нужно для кластеринга
Д🍋
привет
вопрос такой:
задача https://leetcode.com/problems/diagonal-traverse-ii/
в Discussions есть такое решение
почему тут время NlogN?
вопрос такой:
задача https://leetcode.com/problems/diagonal-traverse-ii/
в Discussions есть такое решение
class Solution {
public:
vector<int> findDiagonalOrder(vector<vector<int>>& nums) {
// Time Complexity: O(n log n)
// Space Complexity: O(n)
map<pair<int, int>, int> diagonals;
// nums[i][j] is located at position j on the (i+j)-th diagonal
for (int i = 0; i < nums.size(); ++i)
for (int j = 0; j < nums[i].size(); ++j)
diagonals[{i + j, j}] = nums[i][j];
vector<int> ans;
for (const auto& [k, v]: diagonals) ans.emplace_back(v);
return ans;
}
};почему тут время NlogN?
Д🍋
тут же как минимум все клетки нужно обойти по разу