我正在研究 SPOJ 問題，您必須撰寫一個基于輸入字串條件輸出新字串的演算法，但您不能超過時間限制。 問題鏈接
我能得到的最快的是使用兩個堆疊，但仍然超過時間限制，現在我嘗試實作雙向鏈表，但它比我使用堆疊時慢兩倍。您對如何提高實作的鏈表的性能有任何想法，或者我應該使用其他資料結構來解決這個問題嗎？考慮將 Node 實作為一種結構，但不確定是否可以這樣做。
using System;
namespace spoj
{
class LinkedList
{
private Node head;
private Node tail;
private int length;
public Node Head { get => head; }
public Node Tail { get => tail; }
public int Length { get => length; }
public LinkedList(Node head = null, Node tail = null, int length = 0)
{
this.head = head;
this.tail = tail;
this.length = length;
}
public void AddFirst(char value)
{
var addFirst = new Node(value);
addFirst.Next = head;
addFirst.Previous = null;
if (head != null)
head.Previous = addFirst;
head = addFirst;
length ;
}
public void Remove(Node node)
{
if (node.Previous == null)
{
head = node.Next;
head.Previous = null;
length--;
}
else if (node.Next == null)
{
tail = node.Previous;
tail.Next = null;
length--;
}
else
{
Node temp1 = node.Previous;
Node temp2 = node.Next;
temp1.Next = temp2;
temp2.Previous = temp1;
length--;
}
}
public void AddAfter(Node node, char input)
{
var newNode = new Node(input);
if (node.Next == null)
{
node.Next = newNode;
newNode.Previous = node;
length ;
}
else
{
Node temp1 = node;
Node temp2 = node.Next;
temp1.Next = newNode;
newNode.Previous = temp1;
newNode.Next = temp2;
temp2.Previous = newNode;
length ;
}
}
public string Print()
{
string temp = "";
if (head == null)
return temp;
for (int i = 0; i < length; i )
{
temp = head.Value;
head = head.Next;
}
return temp;
}
}
class Node
{
private char value;
private Node next;
private Node previous;
public char Value { get => value; }
public Node Next { get => next; set { next = value; } }
public Node Previous { get => previous; set { previous = value; } }
public Node(char value)
{
this.value = value;
next = null;
previous = null;
}
}
class Program
{
static void Main(string[] args)
{
int testNum = Int32.Parse(Console.ReadLine());
for (int i = 0; i < testNum; i )
{
var list = new LinkedList();
string input = Console.ReadLine();
var node = list.Head;
for (int j = 0; j < input.Length; j )
{
if ((input[j] == '<' && node == null) | (input[j] == '>' && (node == null || node.Next == null)) | (input[j] == '-' && (node == null || node.Previous == null)))
continue;
else if (input[j] == '<')
{
node = node.Previous;
}
else if (input[j] == '>')
{
node = node.Next;
}
else if (input[j] == '-')
{
node = node.Previous;
list.Remove(node.Next);
}
else
{
if (node == null)
{
list.AddFirst(input[j]);
node = list.Head;
continue;
}
list.AddAfter(node, input[j]);
node = node.Next;
}
}
Console.WriteLine(list.Print());
}
}
}
}
uj5u.com熱心網友回復：
使用鏈表的實作不會像使用鏈表那樣快StringBuilder，但假設您詢問的是基于鏈表的實作，我建議不要重新實作LinkedList。就用原生的吧。
這意味著您不必對代碼進行太多更改，只需：
- 將串列節點的型別定義為
char：new LinkedList<char>(); - 而不是
.Head使用.First - 而不是
.Print使用string.Join("", list)
但是，您的代碼中存在以下問題：
當輸入為時，您應該允許邏輯在
>何時執行。目前 you , 但是 a可能意味著你的“游標”在非空串列前面，所以你仍然應該處理它，并將“游標”移動到nodenullcontinuenulllist.First當輸入是
-時，即使是 ，您仍然應該執行洗掉node.Previous，null因為被洗掉的不是前一個節點，而是當前節點。我們應該想象游標位于兩個連續節點之間，并且您的洗掉邏輯表明您將游標視為當前node和之間的規則node.Next。您也可以采用另一種方法（游標位于之前node），但重要的是您的所有邏輯都與此選擇一致。在執行
-與前一點一致的邏輯時，您應該考慮到node.Previous可能是null，在這種情況下，您無法按照自己的方式進行洗掉。相反，您可以先將節點參考分配給臨時變數，然后移動游標，然后洗掉臨時參考所參考的節點。
這是使用本機LinkedList實作的更正代碼。我在每個單獨的案例中移動了什么都不做（你的continue）的邏輯，因為我發現這更容易理解/除錯：
using System;
using System.Collections.Generic;
public class Test
{
public static void Main()
{
int testNum = Int32.Parse(Console.ReadLine());
for (int i = 0; i < testNum; i )
{
var list = new LinkedList<char>();
string input = Console.ReadLine();
var node = list.First;
for (int j = 0; j < input.Length; j )
{
if (input[j] == '<')
{
if (node != null)
node = node.Previous;
}
else if (input[j] == '>')
{
if (node == null || node.Next != null)
node = node == null ? list.First : node.Next;
}
else if (input[j] == '-')
{
if (node != null) {
var temp = node;
node = node.Previous;
list.Remove(temp);
}
}
else
{
node = node == null ? list.AddFirst(input[j])
: list.AddAfter(node, input[j]);
}
}
Console.WriteLine(string.Join("", list));
}
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/449952.html