Есть метод, который считает хедеры для таблицы
private List headers(String html)
{
Document doc = Jsoup.parse(html);
ArrayList result = new ArrayList<>();
Elements header;
Element firstThead = doc.select("thead").first();
Elements trOfFirstThead = firstThead.children();
for (Element tr : firstThead.children())
{
Elements select = tr.select("th");
for (Element th : select)
{
String s = th.attributes().get("rowspan");
if (!s.isEmpty() && s.equals(String.valueOf(trOfFirstThead.size())))
{
result.add(th.text());
}
}
}
header = trOfFirstThead.last().children();
for (Element element : header)
{
if (element.tag().getName().equals(tag_th))
{
result.add(element.text());
}
}
return result;
}
Суть метода такова - на вход поступает таблица, у которой есть раздел thead и из
него необходимо получить хедеры в виде коллекции строк. Если хедеры расположены в несколько
рядов, то выбирается нижний ряд, и по нему берутся названия.
Данный алгоритм работает для таблиц, представленых под номерами 1, 2, и 3 ( см. вложение).
Но для таблицы типа 4 хедеры находятся не правильно.
Требуемая коллекция :
h4 h10 h11 h12 h6 h7.
При работе алгоритма получается следующая коллекция :
h4 h7 h10 h11 h12.
Прошу помочь советом/алгоритмом, как можно реализовать нужное поведение.
P.S. исходный код таблиц.
-
Таблица 1
| h1 |
h2 |
h3 |
| 1 |
2 |
3 |
| 4 |
5 |
6 |
| 7 |
8 |
9 |
-
Таблица 2
| h4 |
h5 |
| h1 |
h2 |
h3 |
| 1 |
2 |
3 |
| 4 |
5 |
6 |
| 7 |
8 |
9 |
-
Таблица 3
| h4 |
h5 |
| h1 |
h2 |
| 1 |
2 |
3 |
| 4 |
5 |
6 |
| 7 |
8 |
9 |
-
Таблица 4
| h4 |
h5 |
h7 |
| h1 |
h2 |
h8 |
h6 |
| h10 |
h11 |
h12 |
| 1 |
2 |
3 |
4 |
5 |
6 |
| 7 |
8 |
9 |
10 |
11 |
12 |
Ответы
Ответ 1
По-моему, решением будет реализация в каком-то объеме прописанного в HTML5 алгоритма
построения таблицы, благо обработка там простая. Вот этот код выдает нужный
результат на ваших примерах:
static class TableHeader {
private String[][] cells;
private int y_height = 0;
private int x_width = 0;
public TableHeader( int rows, int columns, Element thead ) {
cells = new String[rows][columns];
parseTHead( thead );
}
private void ensureCapacity( int rows, int columns ) {
if ( rows <= cells.length && columns <= cells[0].length ) return;
int nRows = Math.max( cells.length, rows );
int nColumns = Math.max( cells[0].length, columns );
String[][] newCells = new String[nRows][nColumns];
for ( int row = 0; row < cells.length; row++ ) {
System.arraycopy(cells[row], 0, newCells[row], 0, cells[row].length );
}
cells = newCells;
}
private void fill( String cellValue, int row, int col, int rowspan, int colspan ) {
ensureCapacity( row + rowspan, col + colspan );
for ( int r = 0; r < rowspan; r++ ) {
for ( int c = 0; c < colspan; c++ ) {
cells[row + r][col + c] = cellValue;
}
}
}
private int cellSpan( Element th, String attrName ) {
String attrValue = th.attr( attrName );
int result = 1;
if ( attrValue.isEmpty() ) return result;
try {
result = Integer.parseInt( attrValue );
} catch ( NumberFormatException ex ) { /*ignore*/ };
return result;
}
// http://www.w3.org/TR/html5/tabular-data.html#algorithm-for-processing-row-groups
private void parseTHead( Element thead ) {
//int y_start = y_height; // #1
int y_current = 0;
final Elements rows = thead.children().select( "tr" );
final int rowsNumber = rows.size();
ensureCapacity(rowsNumber, x_width);
for ( Element tr : rows ) { // #2
//http://www.w3.org/TR/html5/tabular-data.html#algorithm-for-processing-rows
if ( y_height == y_current ) {
y_height += 1;
}
int x_current = 0;
//TODO: Run the algorithm for growing 'downward-growing cells'.
for ( Element currentCell : tr.children().select( "td, th" ) ) {
//6. While xcurrent is less than xwidth and the slot with coordinate
(xcurrent, ycurrent)
// already has a cell assigned to it, increase xcurrent by 1.
while ( x_current < x_width && cells[y_current][x_current] != null
) x_current += 1;
if ( x_current == x_width ) {
x_width += 1; //# 7
}
int colspan = cellSpan( currentCell, "colspan" ); //#8
int rowspan = cellSpan( currentCell, "rowspan" ); //#9
if (colspan == 0) colspan = 1;
//TODO: 10. If rowspan is zero and the table element's Document is
not set to quirks mode,
// then let 'cell grows downward' be true, and set rowspan to 1.
// Otherwise, let cell grows downward be false.
//FIXME: не позволяем rowspan создавать больше строк, чем есть
// как этот вопрос решен в стандарте?
rowspan = Math.min( rowsNumber - y_current, rowspan );
if ( x_width < x_current + colspan ) x_width = x_current + colspan;
if ( y_height < y_current + rowspan ) y_height = y_current + rowspan;
// TODO: If any of the slots involved already had a cell covering them,
// then this is a table model error.
// Those slots now have two cells overlapping.
fill( currentCell.text(), y_current, x_current, rowspan, colspan
); // #13
// TODO: If 'cell grows downward' is true, then add the tuple
// {c, xcurrent, colspan} to the list of 'downward-growing cells'.
x_current += colspan; //#15
}
y_current += 1;
}
}
public List lastRow() {
return Arrays.stream( cells[y_height - 1]).limit( x_width ).collect( Collectors.toList());
}
}
private static List headers3(String html) {
Document doc = Jsoup.parse(html);
Element firstThead = doc.select("thead").first();
TableHeader header = new TableHeader(10, 10, firstThead);
return header.lastRow();
}
В реализации не обрабатывается случай с rowspan="0", вроде как все манипуляции с
шириной и высотой можно закинуть в fill, и ни на чем, кроме ваших примеров я ее не
проверял. В качестве бонуса, такой подход позволяет легко получить полный заголовок
столбца.
upd: есть очевидная проблема со случаем, когда y_current + rowspan превышает количество
, в результате fill создает лишние ряды, чего в браузере не наблюдается. С colspan
наверняка та же ситуация. Пока просто ограничил rowspan сверху, но я явно чего-то не
понимаю в стандарте.
#cpp #алгоритм
При помощи очереди с нахождением максимума за O(1) надо обрабатывать миллиарды элементов.
Чтобы программа работала быстрее, нужно придать фиксированный размер двум стекам, при
помощи которых моделируется очередь. Как это сделать правильно? Мои попытки:
AmpQueue(int size){
std::vector< std::pair > v_temp;
v_temp.resize(size);
std::stack< std::pair, std::vector< std::pair > > s_temp(std::move(v_temp));
s1.swap(s_temp);
s2.swap(s_temp);
}
А вот и сама программа:
#include
#include
#include
#include
// Класс для эффективного нахождения максимальной
// амплитуды на подотрезке
class AmpQueue{
private:
std::stack< std::pair, std::vector< std::pair > > s1, s2;
public:
AmpQueue();
AmpQueue(int size){
std::vector< std::pair > v_temp;
v_temp.resize(size);
std::stack< std::pair, std::vector< std::pair > > s_temp(std::move(v_temp));
s1.swap(s_temp);
s2.swap(s_temp);
}
// Загрузка нового элемента в очередь с поддержной нахождения максимума
void push(int new_element){
int max = s1.empty() ? new_element : std::max (new_element, s1.top().second);
s1.push(std::make_pair(new_element, max));
}
// Удаляет элемент из очереди и возвращает значение удаленного элемента
int pop(){
if(s2.empty())
while(!s1.empty()){
int element = s1.top().first;
s1.pop();
int max = s2.empty() ? element : std::max(element, s2.top().second);
s2.push(std::make_pair(element, max));
}
int result = s2.top().first;
s2.pop();
return result;
}
// Получение текущего максимума в очереди за O(1)
int max(){
if(s1.empty() || s2.empty())
return s1.empty() ? s2.top().second : s1.top().second;
else
return std::max(s1.top().second, s2.top().second);
}
// Проверка: пуста ли очередь
bool empty(){
return (s1.empty() && s2.empty());
}
// Загрузка в очередь последовательности из n чисел
void load(int n){
int value;
while(n--){
std::cin >> value;
push(value);
}
}
};
int main(){
int n, current, maximum, element;
std::cin.sync_with_stdio(false);
std::cin >> n;
AmpQueue q(n);
// Загрузим в очередь первые n значение амплитуды
q.load(n);
// Выведем текущий максимум
std::cout << q.max() << std::endl;
// Загружаем следующий элемент последовательности и ищем максимум
std::cin >> current;
while(current != -1){
q.pop();
q.push(current);
std::cout << q.max() << std::endl;
std::cin >> current;
}
}
Программа сначала крашилась при запуске, а после исправлений стала выдавать одни
и те же числа. Возможно, этот код совсем плохой, потому что вчера я редактировал его
уже только на идеоне. Поэтому показываю код на идеоне:
https://ideone.com/bJUpwL
Предполагаю, что проблема в том, что два стека уже заполнены нулевыми парами и имеют
размер n, поэтому при добавлении новых элементов они укладываются сверху на существующие
нулевые элемента. Из-за этого алгоритм работает неправильно (точнее, из-за условия empty).
Как все исправить?
Ответы
Ответ 1
Попробуйте использовать std::vector::reserve() вместо std::vector::resize(). Но в
push() вам нужно контроллировать верхний размер в любом случае.
Ваш поправленный пример, не могу оценить насколько он работающий: https://ideone.com/uF09OU
#php #алгоритм #cookie #защита #csrf
почему некоторые сайты хранят CSRF-токен в куках?
Ведь если отправить, к примеру, GET-запрос - 
Ответы
Ответ 1
Само по себе это действительно бесполезно, если сервер помнит соответствие токен-пользователь
и проверяет только его.
Но в сочетании с передачей такого же токена в параметрах это становится быстрым и
простым способом защиты от CSRF: вы ставите пользователю в куки совершенно случайный
токен и проверяете, что в параметрах запроса впоследствии приходит точно такой же.
Проверяется соответствие запрос-кука.
Потенциальный атакующий не сможет достать его из-за Same Origin Policy (можно ещё
досыпать сверху HttpOnly, чтобы не получить дыр из-за JS), а потому не сможет его продублировать
в запросе. И нет необходимости запоминать что-либо на сервере.
#cpp #алгоритм #геометрия #2d
Я имею неравномерную сетку в виде координат узлов в двумерном пространстве
Узлы сетки хранятся в одномерном векторе, где нумерация снизу-вверх слева-направо
Также мне дана ломаная монотонная линия (обозначена синим цветом на рисунке), из
которой необходимо получить ломаную линию, проходящую через узлы сетки (обозначено
красной линией на рисунке).
Количество точек ломаной линии не совпадает с количеством точек результирующей ломаной.
Есть ли у кого-нибудь идеи по решению данной задачи?
Ответы
Ответ 1
Алгоритм:
Выбираем клетки, через которые проходит ломаная.
Циклично проверяем выбранные клетки:
2.1 Берем на границах клетки две точки, в которых ломаная пересекает эту клетку (или
одну из крайних точек ломаной) и соединяем отрезком.
2.2 Сдвигаем отрезок так, чтоб обе точки находились на границах клетки (в случае
с крайними точками ломаной).
2.3 Считаем углы между отрезком и границами к летки, к которым прилегает отрезок
(достаточно неточного расчета в три варианта >45|=45|<45).
2.4 "основная" граница будет та, у которой угол <45 (обведено красным). Если угол
=45, то обе границы равнозначны.
Повторяем для всех клеток
На основе полученных выборок по две границы строим ломаную
Может получиться, что ломаная пройдет "вдоль" нескольких клеток, в этом случаем сравниваем
результаты проверки текущей клетки и предыдущей. Если сторона клетки с минимальным
углом одинаковая в обоих клетках, то вторую сторону не учитываем.
Ответ 2
Проведите дополнительные воображаемые вертикальные и горизонтальные линии посередине
каждого столбца и строки. У вас получится вдвое более плотная сетка. Каждый узел исходной
сетки окажется заключен в ячейку новой сетки.
Если синяя линия проходит через этот прямоугольник, значит, она задействует соответствующий
узел основной сетки.
Каждый сегмент синей линии пересекается с одним или более полученных прямоугольников.
Зная это, можно написать функцию, возвращающую по каждому сегменту массив узлов основной
сетки, связанных с этими прямоугольниками.
Обходя все сегменты синей линии мы получаем несколько таких массивов. Нужно их слить
в один. Если последний узел в предыдущем массиве равен первому узлу в последующем массиве,
записывать этот узел в результирующий массив всего один раз.
Ответ 3
#include
#include
#include
using namespace std;
int main()
{
// вообше то с такими задачами хранить лучше в std::valarray
// допустим количество узловых точек = 4 * 4 и для примера приведу
//конкретные цифры
// в задаче же уже заданы эти цифры, я лишь для демонстрации идеи
const int n = 4;
valarray< int > matrix(n * n);
// инициализируем первую строку снизу от нулевого индекса `n` штук
valarray row{ 2, 4, 7, 8 };
// теперь учитываем что разница между соответствующим элементами
// следующей строки должны быть одинаковыми.
// и допустим эти цифры заданы в векторе
vector dif{ 3, 2, 4 };
// инициализируем последовательность по срезам
for (int i = 0; i < n; ++i) {
matrix[slice(i * n, n, 1)] = row;
if (i == n - 1) break;
row += dif[i];
}
// точки на кривой лучше хранить в map, так как кривая монотонно растет
map curve{{ 3.4, 2.7 }, {4.1, 6}, {5, 9.3}};
// для первой точки на кривой
auto para = curve.begin();
// теперь берем ближайшие целые этих точек
int x = lround(para->first), y = lround(para->second);
//...
return 0;}
теперь чтобы знать к каким элементам нашей последовательности ближе точка с
координатами (x, y) всего лишь дело техники... для сравнения y наверняка понадобится
dif, а
STL альгоритмы дадут нам возможность рассмотреть любое количество точек
с соответствующими предикатами. Вообшем идея такая, дальше подумайте сами
Ответ 4
0) Учащаем точки ломаной: в цикле определяем расстояние между соседними точками (D)
у ломаной, если это расстояние больше, чем расстояние диагонали ячейки сетки (d), то
вставляем дополнительною точку.
Это шаг предобработки ломаной. В конце объясню зачем это нужно
1) Определяем ближайший узел (curr_node) к начальной точке (p) исходной ломаной
Далее в цикле:
2) Определяем соседние узлы для curr_node (соседями не считать предыдущий посещенный
узел)
3) Определяем расстояние от curr_node и от его соседних узлов до следующей точки
ломаной (p_next).
4) Если расстояние от curr_node до p_next меньше, чем минимальное расстояние от его
соседей до p_next, то p_next станет следующей точкой ломаной, иначе "посещаю" следующий
узел сетки (тот соседний узел, который ближе всего к точке p_next)
Далее возвращаемся к шагу 2
В итоге получаем такую картину посещения узлов
т.е. собирая посещенные узлы (черные), получаем такую ломаную, проходящую по узлам сетки:
А теперь покажу зачем нужно было делать нулевой шаг:
Как видно из этих двух рисунков, первый вариант неверный. Вставкой дополнительных
точек, добьемся правильного результата
