一、字谜游戏
字谜游戏是一个非常好的练习数据结构和算法的挑战，在这个游戏中，玩家需要猜出一组由字母组成的单词，每次猜测后会告诉玩家猜对的字母和猜错的字母的数量。
为了实现这个游戏，我们可以使用一个哈希表来存储单词和其中每个字母的出现次数。当玩家猜测单词时，我们可以使用另一个哈希表来存储猜测的字母和其出现的次数。然后我们将这两个表进行比较，得到猜对的字母数量和猜错的字母数量，重复此过程直到猜对全部字母。
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;
}
原创文章，作者：小蓝，如若转载，请注明出处：https://www.506064.com/n/293977.html
微信扫一扫 
支付宝扫一扫 