Ho un'idea di come implementare il sub array reverse con O (1), escludendo il calcolo preliminare come la lettura dell'input. Avrò molte operazioni inverse e non posso usare la soluzione banale di O (N).
Modifica: Per essere più chiaro, voglio costruire una struttura dati dietro l'array con un livello di accesso che sappia invertire le richieste e inverta la logica di indicizzazione quando è necessario che venga eseguita un'iterazione sull'array.
Modifica 2: la struttura dei dati verrà utilizzata solo per le iterazioni
Ho letto questo e questo e anche questa domande ma non aiutano.
Ci sono 3 casi che devono prendersi cura di:
- Operazione inversa regolare
- Inverti quella area inversa
- Intersezione tra inverso e parte di un'altra area inversa nell'array
Ecco la mia implementazione per le prime due parti, avrò bisogno del tuo aiuto con l'ultima.
Questa è la classe della regola:
class Rule {
public int startingIndex;
public int weight;
}
È usato nella mia struttura dati di base Città:
public class City {
Rule rule;
private static AtomicInteger _counter = new AtomicInteger(-1);
public final int id = _counter.incrementAndGet();
@Override
public String toString() {
return "" + id;
}
}
Questa è la classe principale:
public class CitiesList implements Iterable<City>, Iterator<City> {
private int position;
private int direction = 1;
private ArrayList<City> cities;
private ArrayDeque<City> citiesQeque = new ArrayDeque<>();
private LinkedList<Rule> rulesQeque = new LinkedList<>();
public void init(ArrayList<City> cities) {
this.cities = cities;
}
public void swap(int index1, int index2){
Rule rule = new Rule();
rule.weight = Math.abs(index2 - index1);
cities.get(index1).rule = rule;
cities.get(index2 + 1).rule = rule;
}
@Override
public void remove() {
throw new IllegalStateException("Not implemented");
}
@Override
public City next() {
City city = cities.get(position);
if (citiesQeque.peek() == city){
citiesQeque.pop();
changeDirection();
position += (city.rule.weight + 1) * direction;
city = cities.get(position);
}
if(city.rule != null){
if(city.rule != rulesQeque.peekLast()){
rulesQeque.add(city.rule);
position += city.rule.weight * direction;
changeDirection();
citiesQeque.push(city);
}
else{
rulesQeque.removeLast();
position += direction;
}
}
else{
position += direction;
}
return city;
}
private void changeDirection() {
direction *= -1;
}
@Override
public boolean hasNext() {
return position < cities.size();
}
@Override
public Iterator<City> iterator() {
position = 0;
return this;
}
}
Ed ecco un esempio di programma:
public static void main(String[] args) {
ArrayList<City> list = new ArrayList<>();
for(int i = 0 ; i < 20; i++){
list.add(new City());
}
CitiesList citiesList = new CitiesList();
citiesList.init(list);
for (City city : citiesList) {
System.out.print(city + " ");
}
System.out.println("\n******************");
citiesList.swap(4, 8);
for (City city : citiesList) {
System.out.print(city + " ");
}
System.out.println("\n******************");
citiesList.swap(2, 15);
for (City city : citiesList) {
System.out.print(city + " ");
}
}
Come gestisco le intersezioni inverse?