在O（n）

Question

中使用数据结构来解决这个问题，我们有4个字符（A，B，C和D）的序列，映射到数字形式1到n。 我们定义组件为：

Component(k) : 
A {cell[k]} 
if Color(left_k) = Color(k) 
then 
    A <-- A U Component(left_k) 
if Color(right_k) = Color(k) 
then 
    A <-- A U Component(left_k) 
return A 

有3种类型的操作（在列表中的数字表示输入）：

通过给索引

1. 应该删除的组件在索引（映射到字符的数字是固定的）

   例如：AABBBDA是字符串。如果索引是3应该通过给予指数应该旋转基于该索引组件上的串（数字映射到字符被固定）

   例如返回AADA

2. ：AABBBDA是字符串。如果索引是3，它应该返回DABBBAA

3. 它应该打印字符串。

输入是这样的：

1 2 --> first operation with index=2 
2 3 --> second operation with index=3 
3 --> third operation 

这是一个任务，高兴地得到帮助。

---

这是我试过到目前为止：

public static void main(String[] args) 
{ 
    int numberOfOps; 
    String[] print = new String[30]; 
    List list = new List(); 
    Scanner input = new Scanner(System.in); 
    int count = input.nextInt(); 
    String colors = new String(); 
    colors = input.next(); 
    for(int i = 0; i < count; i++) 
    { 
     list.add(colors.charAt(i)); 
    } 
    numberOfOps = input.nextInt(); 
    list.printElement(); 
    for (int i = 0; i < numberOfOps; i++) 
    { 
     int op = input.nextInt(); 
     if(op == 1) 
     { 
      int index = input.nextInt(); 
      char c = list.item[index]; 
      int temp = index; 
      int prevIndex = index; 
      int nexIndex = index; 
      if(index != 0) 
      { 
       while (list.item[--index] == c) 
       { 
        prevIndex--; 
       } 
       while (list.item[++temp] == c) 
       { 
        nexIndex++; 
       } 
       list.setNext(prevIndex-1, nexIndex+1); 
      } 
      else 
      { 
       while (list.item[++temp] == c) 
       { 
        nexIndex++; 
       } 
       list.setNext(prevIndex, nexIndex+1); 
      } 

     } 
     if(op == 2) 
     { 
      int index = input.nextInt(); 
     } 
     if(op == 3) 
     { 
      print[i] = list.printElement(); 
     } 
    } 

} 

这里是我的表类：

public class List { 
// reference to linked list of items 
public static final int MAX_LIST = 20; 
public static final int NULL = -1; 
public char item[] = new char[MAX_LIST]; // data 
public int avail; 
public int next[] = new int[MAX_LIST];  // pointer to next item 
private int numItems; // number of items in list 
public List() 
{ 
    int index; 
    for (index = 0; index < MAX_LIST-1; index++) 
     next[index] = index + 1; 
    next[MAX_LIST-1] = NULL; 
    numItems = 0; 
    avail = 0; 
} // end default constructor 
public void add(char e) 
{ 
    item[avail] = e; 
    avail = next[avail]; 
    numItems++; 
} 
public String printElement() 
{ 
    String temp = null; 
    int index = 0; 
    while(index<avail) 
    { 
     temp += item[index]; 
     System.out.println(item[index]); 
     index = next[index]; 
    } 
    return temp; 
} 
public int size() 
{ 
    return numItems; 
} 

public void setNext(int i, int value) 
{ 
    next[i] = value; 
} 
} 

如果你测试它，你会得到的，它有很多的问题，例如，我不知道做旋转操作，并且在中间组件被移除时连接两个组件有问题。

Answer 1

这是一个难以回答的问题，因为要求没有正确说明。

例如，第一批伪代码并不清楚A是一个集合，一个多集合还是一个列表。符号（使用大括号和U（联合？））似乎说设置...但输出似乎是一个列表。或者也许它应该是一个数据结构的模式？

甚至输入都没有清楚地描述。

---

但是把它放在一边，仍然有一些（希望）有帮助的建议的空间。

1. 请确保>>您< <了解要求。 （我想，对作业的真正要求比这更好地陈述，并且细节已经“在翻译中丢失”。）

2. 我实际上使用数组列表（或StringBuilder）而不是链接列表为了这。 （但一个正确实施的链表...实施List API ...将工作。）

3. 但是无论你选择什么样的数据结构，从头开始实施它没有意义......除非你是特别需要来做到这一点。 Java标准库中有完美的列表类。你应该重用它们，而不是试图重新发明轮子（并且做不好的工作）。

4. 如果你的是需要实现你自己的数据结构类型，那么你当前的尝试是一团糟。它看起来像是一个数组列表和一个链表之间的混合体......并且不能成功。 （例如，一个体面的数组列表实现不需要MAX_LIST，并且没有next指针/索引。而链表内部不具有任何阵列。）