提高程序員技能：3個適用於算法和數據結構練習的挑戰

一、字謎遊戲

字謎遊戲是一個非常好的練習數據結構和算法的挑戰，在這個遊戲中，玩家需要猜出一組由字母組成的單詞，每次猜測後會告訴玩家猜對的字母和猜錯的字母的數量。

為了實現這個遊戲，我們可以使用一個哈希表來存儲單詞和其中每個字母的出現次數。當玩家猜測單詞時，我們可以使用另一個哈希表來存儲猜測的字母和其出現的次數。然後我們將這兩個表進行比較，得到猜對的字母數量和猜錯的字母數量，重複此過程直到猜對全部字母。

class WordGame {
  public:
    bool guess(string secret, string guess) {
      unordered_map cnt;
      for (char c : secret) cnt[c]++;
      int a = 0, b = 0;
      for (int i = 0; i < guess.size(); i++) {
        if (guess[i] == secret[i]) {
          a++;
          cnt[guess[i]]--;
        }
        else if (cnt[guess[i]]) {
          b++;
          cnt[guess[i]]--;
        }
      }
      return a == secret.size() and b == secret.size();
    }
};

二、刪除排序鏈表中的重複元素

在鏈表相關的算法和數據結構中，刪除排序鏈表中的重複元素也是一個非常有趣的問題。我們需要將所有重複的元素僅保留一個，並返回去重後的鏈表。

為了解決這個問題，我們可以創建一個指針指向當前鏈表的首位，然後依次遍歷鏈表中的每個元素。如果當前元素的值和它下一個元素的值相同，那麼就將當前元素的下一個指針指向下下一個元素，直到找到一個和當前元素不同的元素。

class Solution {
  public:
    ListNode* deleteDuplicates(ListNode* head) {
      if (head == nullptr) return nullptr;
      ListNode* curr = head;
      while (curr->next != nullptr) {
        if (curr->val == curr->next->val) {
          ListNode* tmp = curr->next;
          curr->next = curr->next->next;
          delete tmp;
        } else {
          curr = curr->next;
        }
      }
      return head;
    }
};

三、最短路徑算法

最短路徑算法是計算從一個圖中一個節點到另一個節點的最短路徑的算法。其中，Dijkstra算法是一種非常著名的最短路徑算法，它可以在一個加權有向圖中，從一個源點出發，計算出到其他所有點的最短路徑。

為了實現Dijkstra算法，我們需要使用一個優先隊列來存儲每個節點到源點的距離。然後我們依次擴展隊列中距離源點最近的節點，並更新其周圍節點的距離和路徑。

#define N 100005
typedef pair PII;

int h[N], e[M], w[M], ne[M], idx;
int dist[N], cnt[N];
bool st[N];
int n;

void add(int a, int b, int c) {
  e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

void dijkstra() {
  memset(dist, 0x3f, sizeof dist);
  priority_queue<PII, vector, greater> q;
  dist[1] = 0;
  q.push({0, 1});
  while (q.size()) {
    auto t = q.top();
    q.pop();
    int ver = t.second, distance = t.first;
    if (st[ver]) continue;
    st[ver] = true;
    for (int i = h[ver]; i != -1; i = ne[i]) {
      int j = e[i];
      if (dist[j] > distance + w[i]) {
        dist[j] = distance + w[i];
        cnt[j] = cnt[ver] + 1;
        if (cnt[j] >= n) puts("exist negative cycle");
        q.push({dist[j], j});
      }
    }
  }
}

int main() {
  memset(h, -1, sizeof h);
  cin >> n >> m;
  while (m--) {
    int a, b, c;
    cin >> a >> b >> c;
    add(a, b, c);
  }
  dijkstra();
  return 0;
}