Программирование, т. 6

[^\d]*(\d+)[^\d]*

?

 

а, если действует \D, то

\D*\d+\D*

 

дочитал наконец твой пост до конца

 

ты же сам и составил регулярку, в чем вопрос?

скопом пытался понять как это делается, час втыкал, не понял, решил спросить

 

	String str = "as asdfusdsplfosd asopd aspo d8712348971987489174897 ijuf 98 33333";
	ArrayList<String> arrayList = new ArrayList<String>();

	Matcher match = Pattern.compile("[0-9]+").matcher(str);
	while (match.find())
		arrayList.add(match.group());

 

или проще

 

String[] strings = "as asdfusdsplfosd asopd aspo d8712348971987489174897 ijuf 98 33333".split("[^0-9]+");

 

Но по факту ты же сам спросил - сам ответил.

вообще задача сохранить все подстроки (и буквенные и числовые), разбиаение производится как я сказал (подряд числа - отдельная подстрка, все что между такими числами - отдельные подстроки)

как "\d+" ("[0-9]+") сработает? это от 1 до бесконечности? и обязательно максимальная последовательность?

просто у меня сделано как в первом офтопе, только через match.start() match.end() и переменную в которую предыдущий end записан. в итоге у меня всегда начало буквенной подстроки, начало числовой подстроки, конец числовой подстроки и я с помощью этого разбиваю (в конце после цикла отдельно обрабатывается случай когда последний find не сработал, а у строки еще может быть хвост из букв)

как group работает я так и не понял (((

сам код вот. но тут немного по другому. мне в конечном счете надо сравнивать 2 строки по подстрокам (с описанным выше разбиением), я решил не делить сначала на подстроки а сразу сравнивать находя подстроки. числовые подстроки парсятся в число и сравниваются как числа (так по заданию надо)

int indexFirst1=0, indexFirst2=0;
int result;
Matcher matcher1 = pattern.matcher(col1),
matcher2 = pattern.matcher(col2);
boolean findFlag1,findFlag2;
// с помощью pattern.matcher последовательно находятся нужные (из задания) подстроки
while ((findFlag1 = matcher1.find()) & (findFlag2 = matcher2.find())){

result = col1.substring(indexFirst1,matcher1.start())
.compareTo(
col2.substring(indexFirst2,matcher2.start()));
if (result != 0) return result;

result = Integer.parseInt(col1.substring(matcher1.start(),matcher1.end()))
-
Integer.parseInt(col2.substring(matcher2.start(),matcher2.end()));
if (result != 0) return result;

indexFirst1 = matcher1.end();
indexFirst2 = matcher2.end();


}

паттерн для класса определен так

      private static final String REGEXP = ""; // регулярное выражение - последовательность чисел 
      private static final Pattern pattern = Pattern.compile(REGEXP);

щас подумал, хуевая идея сравнивать при делении. буду переделывать - тупо подстроки подряд, потом тупо сравнивать (инт парсится).

+ и означает от 1 до бесконечности

* от 0 до бесконечности

? от 0 до 1

регулярки по умолчанию "жадные", то есть на каждый свой элемент помеченный + или * они стараются сожрать как можно больше доступных символов.

Иногда это наоборот мешает, и тогда чтобы сделать какой-то элемент нежадным, добавляют после + или * еще дополнительно ?

спасибо

а теперь алгоритмическая задачка. мб тут кто знает подобное или имеет представление куда копать.

опишу не программно а типа как примерах.

суть такова:

у нас есть ряд пронумерованных ячеек (посути сколько угодно длинный одномерный массив)

и есть какое-то количество пронумерованных шаров (номера шаров не повторяются, вообще говоря шары пронумерованы от 0 до n-1, где n это колчиство шаров )

эти шары изначально лежат в ячейках в общем-то случайным образом (абсолютно случайным)

мы можем лишь перекладывать из одной ячейки в другую 1 шар за раз.

в одну ячейку, конечно же, помещается только 1 шар.

тоесть лежат шары с номерами в каких-то рандомных ячейках (ячейки пронумерованы), мы можем лишь совершать одно действие: переложить 1 шар в пустую ячейку

НЕОБХОДИМО : за минимальное количество действий переложить шары в ячейки с номером соответствующим номеру шара

сделал в екселе табличку для наглядности (сверху произвольная возможная ситуация, снизу как должно быть в итоге, )

а хуй с ним я уже решил

берется очередной шар. смотрится на какой он ячейке (на своей оставляем и переходим к след), если не на своей то смотрим в ячейке с его номером (пусто - перемещаем), если занято то применяем к этому шару предыдущий шаг. так у нас образуется цепочка, в обратную сторону идем каждый раз перемещая шар в свою ячейку

если достигли последнего шара и пустой так не нашлось - то выбираем любой свободный и по цепочке также все кладем на свои места, кроме одного - его дополнительной операцией перемещаем на свою.

да просто за один проход и менять местами ту что проходишь и та что годится

если я правильно понял твой метод в 3 раза не эффективнее

это смотря какой список

а я не дочитал

если достигли последнего шара и пустой так не нашлось

Этого никогда не случится, если есть хотя бы 1 пустая клетка.

Вот я решение накидал, ты вроде такое же описал

void sort(int[] a){
	for (int i = 0; i < a.length; i++) {
		/*-1 indicates an empty cell*/
		if (a[i] != i && a[i] != -1){
			if (!findPosition(a, i, i)){
				throw new IllegalArgumentException("There is no empty cell in the given array");
			}
		}
	}
}
boolean findPosition(int[] a, int cur, int from){
	if (a[cur] == -1){
		a[cur] = cur;
		return true;
	}
	/*if there is a cyclical dependence between the two items, just swap them*/
	if (a[cur] == from){
		for (int i = 0; i < a.length; i++){
			if (a[i] == -1){
				a[i] = a[cur];
				a[cur] = a[from];
				a[from] = a[i];
				a[i] = -1;
				return true;
			}
		}
		return false;
	}
	if (findPosition(a, a[cur], cur)){
		if (cur == from && a[cur] != cur){
			a[cur] = -1;
		} else {
			a[cur] = cur;
		}
		return true;
	}
	return false;
}

за раз только один элемент можно менять, а значит придется юзать стек

за раз только один элемент можно менять, а значит придется юзать стек

За "раз" можно только переложить шар в пустую клетку.

И стек тут вообще не нужен ни разу.

не думаю что можно менять местами, это слишком просто было бы

а так, задача типа [,2,1,0] не решается за o(n) если можно перекладывать только в пускую клетку

Сорри если не в этом топике. Хотел спросить где лучше всего зарегать домен?

Сорри если не в этом топике. Хотел спросить где лучше всего зарегать домен?

Сам не регал, но думаю тут норм

http://support.2domains.ru/knowledgebase.php?article=3

если достигли последнего шара и пустой так не нашлось

Этого никогда не случится, если есть хотя бы 1 пустая клетка.

Вот я решение накидал, ты вроде такое же описал

 

 

void sort(int[] a){
	for (int i = 0; i < a.length; i++) {
		/*-1 indicates an empty cell*/
		if (a[i] != i && a[i] != -1){
			if (!findPosition(a, i, i)){
				throw new IllegalArgumentException("There is no empty cell in the given array");
			}
		}
	}
}
boolean findPosition(int[] a, int cur, int from){
	if (a[cur] == -1){
		a[cur] = cur;
		return true;
	}
	/*if there is a cyclical dependence between the two items, just swap them*/
	if (a[cur] == from){
		for (int i = 0; i < a.length; i++){
			if (a[i] == -1){
				a[i] = a[cur];
				a[cur] = a[from];
				a[from] = a[i];
				a[i] = -1;
				return true;
			}
		}
		return false;
	}
	if (findPosition(a, a[cur], cur)){
		if (cur == from && a[cur] != cur){
			a[cur] = -1;
		} else {
			a[cur] = cur;
		}
		return true;
	}
	return false;
}

 

 

пример

не думаю что можно менять местами, это слишком просто было бы

 

а так, задача типа [,2,1,0] не решается за o(n) если можно перекладывать только в пускую клетку

а o(n) по операциям переноса шара

проходится по списку/мапе шар-ячейка, ячейка-шар можно сколько угодно как угодно

в общем мое решение вот

тестить лень, вроде нигде не накосячил.

а бля вы щас нихуя не поймете тк изначальная задача не про шары а про то что есть List elements соджержащий IElement, IElement - объект с которого можно получать его номер, а можно записывать. НО записываемый номер должен быть уникальным (тоесть одновременно только один элемент может иметь какойто один конкретный номер, тоесть связь 1к1, соответственно при назначении какого-то номера элементу надо ОБЯЗАТЕЛЬНО чтобы небыло другого элемента с таким номером. изначально переданный список и все элементы в нем этому соответствуют)

нужно переназначить номера элементов из списка в соответствии с его порядковым номером в листе

операция назначения номера относительно сильно трудоемкая и нужно свести к минимуму количество таких операций.

если переводить на шары, то порядковый номер элемента в листе (назван у меня index) - номер шара, текущий Nomber объекта IElement - номер ячейки, ячейка занята если есть элемент у которого Nomber = номеру ячейки.

 // отображение Number элемента в индекс(порядковый номер) этого элемента в списке
 Map<Integer,Integer> numberPositionMap = new HashMap<Integer,Integer>();
 for (int i=0 ; i<elements.size() ; i++){
 numberPositionMap.put(elements.get(i).getNumber(), i);
 }
 for (int i=0 ; i<elements.size() ; i++){
 // цикл проходится по всем элементам списка, если Nomber элемента и
 //его порядковый номер в списке совпадают то не делается ничего.
 // если не совпадает - то составляется цепочка последовательных замен,
 //а затем производятся последовательные замены по этой цепочке.
 //учтена ситуация с цикличной цепочкой замен.

 int index = i;
 boolean cycleChainFlag=false;
 int number = elements.get(index).getNumber();
 if (number!=index){
 LinkedList<Integer> chain = new LinkedList<Integer>();

 while (true) { //составляем цепочку последовательных замен номеров. последнее добавленное значение - обязательно пустая ячейка, кроме случая цикличной цепочки.
 chain.push(index);
 if(!numberPositionMap.containsKey(index)){ // если для текущего элемента есть свободный номер (Nomber) то цепочка завершена
break;
} else { //если для текущего эл. номер не свободен, текущий элемент(его индекс) меняем на индекс элемента который занимает нужный номер

index = numberPositionMap.get(index);
if (chain.contains(numberPositionMap.get(index))){ //проверка на цикличность цепочки
cycleChainFlag=true;
break;
}
}
}
 Integer randomNumber, cycleChainIndex = null;
 if (cycleChainFlag){ // в случае с цикличной цепочкой замен

 do { // берется случайный свободный номер
 randomNumber = new Random().nextInt();
 } while (numberPositionMap.containsKey(randomNumber));
 // запоминается новый номер (случайный свободный) и порядковый номер элемента (индекс)
 cycleChainIndex = numberPositionMap.get(chain.pop());
 elements.get(cycleChainIndex).setupNumber(randomNumber);
 numberPositionMap.put(randomNumber, cycleChainIndex);
 numberPositionMap.remove(elements.get(cycleChainIndex).getNumber());
 }
 while (!chain.isEmpty()){ // производим замены по цепочке
 Integer c = chain.pop();
 elements.get(c).setupNumber(c);
 numberPositionMap.put(c,c);
 numberPositionMap.remove(elements.get(c).getNumber());
 }
 if (cycleChainFlag){ //первый элемент цикличной цепи с рандомного номера переходит на нужный
 elements.get(cycleChainIndex).setupNumber(cycleChainIndex);
 numberPositionMap.put(cycleChainIndex, cycleChainIndex);
 numberPositionMap.remove(elements.get(cycleChainIndex).getNumber());

 }
 }
 }
}

(кто подскажет как нормально копировать из еклипса на пдшу ? )

>проходится по списку/мапе шар-ячейка, ячейка-шар можно сколько угодно как угодно

какой смысл тогда?

такой что прочитай блять

ты какойто дундук

когда есть бесплатный и функциональный и опенсорс Eclipse ?

ну типа преимущества, фишки. мб для каких-то задач он вообще единственно юзабительный

Тут все дело в личных предпочтениях и юзабилити. Рефакторинг, глобальный поиск, индексация, куча мелких незаметных плюшечек(автосейв, синхронизация файлов, глобальный go to def и т.п.), для особо привередливых можно чекофнуть ремаппинг хоткеев, и вот в уже встроенный эклипс. Из минусов разве что, память жрет за два эклипса+.

Ну и типо в эклипсе вообще для всего надо плагины ставить, когда в идеи основные фичи уже изначально включены.

Все равно вижла - топовая ИДЕ.

---

зачем нужен IntelliJ IDEA,

когда есть бесплатный и функциональный и опенсорс Eclipse ?

ну типа преимущества, фишки. мб для каких-то задач он вообще единственно юзабительный

Зачем нужна IDE когда есть sublime text ? Я серьезно, прост у меня очень плохие воспоминания о Microsoft Visual Studio. Пока что единственный плюс, о котором я знаю, это то, что они показывают список методов класса/функций, но это и без IDE очень легко посмотреть.

В идее код в 100 раз быстрее пишется, лол. Там пожалуй самый умный автокомплит который я видел + интеграция почти со всеми популярными фреймворками и тулзами.