прямоугольное пересечение axis‐aligned
Я не знаю, почему все это так усложняет.
для большинства случаев простое выражение ([A-Z]+) выполнит трюк
>>> re.sub('([A-Z]+)', r'_\1','CamelCase').lower()
'_camel_case'
>>> re.sub('([A-Z]+)', r'_\1','camelCase').lower()
'camel_case'
>>> re.sub('([A-Z]+)', r'_\1','camel2Case2').lower()
'camel2_case2'
>>> re.sub('([A-Z]+)', r'_\1','camelCamelCase').lower()
'camel_camel_case'
>>> re.sub('([A-Z]+)', r'_\1','getHTTPResponseCode').lower()
'get_httpresponse_code'
Чтобы игнорировать первый символ просто добавьте look behind (?!^)
>>> re.sub('(?!^)([A-Z]+)', r'_\1','CamelCase').lower()
'camel_case'
>>> re.sub('(?!^)([A-Z]+)', r'_\1','CamelCamelCase').lower()
'camel_camel_case'
>>> re.sub('(?!^)([A-Z]+)', r'_\1','Camel2Camel2Case').lower()
'camel2_camel2_case'
>>> re.sub('(?!^)([A-Z]+)', r'_\1','getHTTPResponseCode').lower()
'get_httpresponse_code'
Если вы хотите отделить ALLCaps до all_caps и ожидать числа в вашей строке, вам все равно не нужно делать два отдельных прогона, просто используйте | Это выражение ((?<=[a-z0-9])[A-Z]|(?!^)[A-Z](?=[a-z])) может обрабатывать практически каждый сценарий в книге
>>> a = re.compile('((?<=[a-z0-9])[A-Z]|(?!^)[A-Z](?=[a-z]))')
>>> a.sub(r'_\1', 'getHTTPResponseCode').lower()
'get_http_response_code'
>>> a.sub(r'_\1', 'get2HTTPResponseCode').lower()
'get2_http_response_code'
>>> a.sub(r'_\1', 'get2HTTPResponse123Code').lower()
'get2_http_response123_code'
>>> a.sub(r'_\1', 'HTTPResponseCode').lower()
'http_response_code'
>>> a.sub(r'_\1', 'HTTPResponseCodeXYZ').lower()
'http_response_code_xyz'
Все зависит от того, что вы хотите, чтобы использовать решение, которое наилучшим образом соответствует вашим потребностям, поскольку оно не должно быть чрезмерно сложным.
NJoy!
3 ответа
Это может быть немного сложным для собеседования, зависит от того, какую работу, Это алгоритм геометрических вычислений,
Ответ можно найти здесь: http: // www. cs.princeton.edu/~rs/AlgsDS07/17GeometricSearch.pdf
Вот краткое описание алгоритма пересечения, представленного в ссылке DuduAlul .
Решение требует использования дерева поиска, способного выполнять диапазонные запросы. Запрос диапазона запрашивает все элементы со значениями между K1 и K2, и это должна быть операция O (R + log N), где N - общее количество элементов дерева, а R - количество результатов.
Алгоритм использует подход развертки:
1) Сортировать все левые и правые края прямоугольника в соответствии с их значением X в список L.
2) Создайте новое пустое дерево поиска диапазона T, для Y упорядочения вершин / низов прямоугольника
3) Создайте новый пустой набор результатов RS уникальных пар прямоугольников
4) Траверс L в порядке возрастания. Для всех V в L:
& nbsp; & nbsp; & V.bsRightEdge ()
& nbsp; & nbsp; & nbsp; & nbsp; T.remove (V.rectangle. top)
& nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; T.remove (V.rectangle.bottom)
& nbsp; & nbsp; & nbsp; & nbsp; & nbsp; else
& nbsp ; & NBSP; & NBSP; & NBSP; & NBSP; & NBSP; Для всех U в T.getRange (V.rectangle.top, V.rectangle.bottom)
& nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; RS.add (< V.rectangle, U.rectangle>)
& nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; Tadd (V.rectangle.top)
& nbsp; & nbsp; & nbsp; & nbsp; & nbsp; & nbsp; ; & nbsp; & nbsp; T.add (V.rectangle.bottom)
5) return RS
Сложность по времени составляет O (R + N log N), где R - это фактическое количество пересечений.
- РЕДАКТИРОВАТЬ -
Я только что выяснил, что решение не полностью корректно - тест пересечения в дереве T пропускает некоторые случаи. Дерево должно поддерживать интервалы Y, а не значения Y, и в идеале оно должно быть Interval Tree .
Очистить и отсечь - это метод, который используется многими физическими движками для решения такого рода проблем.
Есть хорошее объяснение в примечаниях Дэвида Бараффа SIGGRAPH в разделе 7.2 Ограничивающие прямоугольники.