本题使用核心代码模式

题目内容

微服务的运行规则如下：

• 部署:一个微服务在一台服务器上只能部署一个实例，但可部署在多台服务器上。

• 运行状态:一个微服务可以不依赖其它微服务独立启动并运行。

• 提供服务:一个微服务，当无依赖时，只要有一个实例运行即可提供服务;当有依赖时，当仅当其自身在运行及其所依赖的所有微服务都可提供服务，则该微服务才能提供服务。

如：某时刻，微服务 $A$ 依赖微服务 $B$ 、$B$ 依赖 $C$ 、$C$ 无依赖，则:

• 若 $C$ 至少有一个实例处于运行状态，则 $C$ 可提供服务:

• 同时，$B$ 至少有一个实例处于运行状态，则 $B$ 也可提供服务;

• 再者，$A$ 至少有一个实例处于运行状态，则 $A$ 也可提供服务。

然后，若把 $B$ 的所有实例停止，则 $A、B$ 都不能提供服务；但 $C$ 仍可提供服务。

模拟微服务运行、访问、服务器重启，请实现如下功能：

• $ServiceWgSys()-$系统初始化，假设机房内的所有服务器都已上传可供运行微服务。

• $rebootServers(int[]serverIds)-$服务器 $serverIds$ 批量重启，这些服务器上的微服务不会自动 启动。

• $startService(int$ $serverId$,$String$ $serviceName)$ 在指定的服务器 $serverId$上启动微服务$serviceName$；

如果此服务器上已运行该微服务，则直接返回 $false$ ;

否则，启动该微服务(可能是新的微服务实例，也可以是之前配置服务器重启而停止运行的微服务)，该微服务处于运行状态。返回 $true$。

$addDependency(String$ $fromServiceName，String$ $to$ $ServiceName)-$令微服务$fromService$ 依赖微服务 $toService$，输入保证无循环依赖。

如果此依赖关系已经存在，则直接返回 $false$;

否则，新添加此依赖关系(无论两个微服务是否启动过)，返回 $true$

$isServiceAvailable(String$ $serviceName)-$如果指定的微服务的提供服务，返回 $true$ ;否则，返回 $false$ 。

输入描述

每行表示一个函数调用，初始化函数仅首行调用一次，累计函数调用不超过 $1000$ 次。

$0<=serverId<=1000$，且是存在的服务器。

$0<serverIds.length<=500$；$0<=serverIds[i]<= 1000$，各不相同且是存在的服务器。

$serviceName、fromServiceName、toServiceName$ 由英文字母或数字组成，$0＜$长度$＜15$。

输出描述

答题时按照函数方法原型中的要求(含返回值)进行实现，输出由框架完成(其中首行固定输出 $null$)。

样例1

输入

ServiceWgSys()
startService(1, "serviceA")
startService(2, "serviceA")
startService(2, "serviceA")
addDependency("serviceB", "serviceA")
rebootServers([2])
isServiceAvailable("serviceA")
startService(2, "serviceB")
isServiceAvailable("serviceB")
rebootServers([2, 1])
isServiceAvailable("serviceA")
startService(1, "serviceA")
isServiceAvailable("serviceA")

输出

null
true
true
false
true
null
true
true
true
null
false
true
true

模板

Python

class ServiceMgrSys:
    def __init__(self):

    def rebootServers(self, serverIds):

    def startService(self, serverId, serviceName):
       
    def addDependency(self, fromServiceName, toServiceName):
       
    def isServiceAvailable(self, serviceName):
       

Java

import java.util.*;

class ServiceMgrSys {
    
    ServiceMgrSys() {
      
    }
    
    void rebootServers(int[] serverIds) {
      
    }
    
    boolean startService(int serverId, String serviceName) {
      
    }
    
    boolean addDependency(String fromServiceName, String toServiceName) {
       
    }
    

    boolean isServiceAvailable(String serviceName) {
       
    }
}

C++

#include<bits/stdc++.h>
using namespace std;

class ServiceMgrSys {
public:

    ServiceMgrSys(){}
    
    void rebootServers(vector<int>& serverIds) {
        
    }

    bool startService(int serverId, string serviceName) {
        
    }

    bool addDependency(string fromServiceName, string toServiceName) {
       
    }

    bool isServiceAvailable(string serviceName) {
       
    }
};

题解

题目描述

在微服务架构中，每个微服务可能有依赖关系，我们需要模拟微服务的运行、访问以及服务器重启的过程。微服务的运行规则如下：

1. 部署：一个微服务在一台服务器上只能部署一个实例，但可以部署在多台服务器上。
2. 运行状态：微服务可以独立启动并运行，也可以依赖其他微服务。
3. 提供服务：当微服务没有依赖时，只要有一个实例运行即可提供服务；当微服务有依赖时，它自身以及所有依赖的微服务都必须运行才能提供服务。

操作要求：

1. ServiceWgSys()：系统初始化，假设机房内的所有服务器都已上传可供运行微服务。
2. rebootServers(int[] serverIds)：批量重启指定服务器，重启后微服务实例不会自动启动。
3. startService(int serverId, String serviceName)：在指定的服务器上启动微服务，如果该服务已经在该服务器上运行，则返回 false，否则返回 true。
4. addDependency(String fromServiceName, String toServiceName)：为微服务添加依赖关系。
5. isServiceAvailable(String serviceName)：判断微服务是否可用，若可用则返回 true，否则返回 false。

题解思路

1. 数据结构设计：

• 使用 HashMap（或 unordered_map）来记录服务的状态、依赖关系、以及每台服务器上运行的服务：
  • counter：记录每个服务的实例数量，微服务在运行时，每个实例数量增加，停止时减少。
  • graph：记录服务之间的依赖关系，类似图的邻接表。
  • services：记录每台服务器上启动的服务。

2. 核心操作实现：

• startService：检查指定服务器是否已经启动了该服务，如果没有则启动服务并增加实例计数。
• addDependency：向依赖图中添加依赖关系，确保没有循环依赖。
• rebootServers：通过删除指定服务器上所有服务的实例来模拟服务器重启。
• isServiceAvailable：通过 DFS 或 BFS 遍历服务的依赖关系，确保该服务及其所有依赖都能正常运行。

3. 服务可用性判断：

• 对于一个服务 A，只有当 A 和它的所有依赖服务都在运行时，A 才能提供服务。这需要遍历所有依赖并判断它们的状态。

4. 边界处理：

• 服务的重启、依赖关系的添加以及服务的状态检查都需要特别小心处理，确保每个操作都正确更新状态。

具体实现请看下面的代码

Python 实现

class ServiceMgrSys:
    def __init__(self):
        # 记录每个服务的实例计数
        self.counter = {}
        # 记录服务间的依赖关系（图的邻接表）
        self.graph = {}
        # 记录每台服务器上运行的服务
        self.services = {}

    def rebootServers(self, serverIds):
        # 重启指定的服务器
        for serverId in serverIds:
            if serverId in self.services:
                for serviceName in self.services[serverId]:
                    self.counter[serviceName] = self.counter.get(serviceName, 0) - 1
                del self.services[serverId]

    def startService(self, serverId, serviceName):
        # 在指定的服务器上启动微服务
        if serverId not in self.services:
            self.services[serverId] = set()

        if serviceName in self.services[serverId]:
            return False  # 服务已在该服务器上运行

        self.services[serverId].add(serviceName)
        self.counter[serviceName] = self.counter.get(serviceName, 0) + 1
        return True

    def addDependency(self, fromServiceName, toServiceName):
        # 为 fromServiceName 添加到 toServiceName 的依赖关系
        if fromServiceName not in self.graph:
            self.graph[fromServiceName] = set()

        if toServiceName in self.graph[fromServiceName]:
            return False  # 依赖关系已存在

        self.graph[fromServiceName].add(toServiceName)
        return True

    def isServiceAvailable(self, serviceName):
        # 检查指定的服务是否可用
        visited = set()
        return self.dfs(visited, serviceName)

    def dfs(self, visited, now):
        # 深度优先搜索，检查服务是否可用
        if self.counter.get(now, 0) == 0:
            return False  # 没有实例可用
        if now in visited:
            return True  # 循环依赖，避免无限递归

        visited.add(now)
        for adj in self.graph.get(now, set()):
            if not self.dfs(visited, adj):
                return False  # 如果依赖的服务不可用，则当前服务也不可用
        return True

Java 实现

import java.util.*;

class ServiceMgrSys {
    // 用于记录每个服务实例的数量
    HashMap<String, Integer> counter;
    // 用于记录服务之间的依赖关系，图的结构
    HashMap<String, Set<String>> graph;
    // 用于记录每台服务器上启动的服务
    HashMap<Integer, Set<String>> services;
    
    // 构造函数，初始化数据结构
    ServiceMgrSys() {
        this.counter = new HashMap<>();  // 初始化服务实例计数器
        this.graph = new HashMap<>();    // 初始化服务依赖图
        this.services = new HashMap<>(); // 初始化服务器服务映射
    }
    
    // 重启服务器并清除服务器上的所有服务
    void rebootServers(int[] serverIds) {
        // 遍历需要重启的服务器 ID
        for (int id : serverIds) {
            // 检查服务器上是否有服务
            if (services.containsKey(id)) {
                // 遍历该服务器上的所有服务，将每个服务的实例数量减1
                for (String name : services.get(id)) {
                    counter.put(name, counter.get(name) - 1);
                }
                // 移除该服务器上的所有服务
                services.remove(id);
            }
        }
    }
    
    // 启动某个服务并将其绑定到指定的服务器
    boolean startService(int serverId, String serviceName) {
        // 获取该服务器上的服务集合，如果没有则创建一个新的集合
        Set<String> names = services.computeIfAbsent(serverId, (Integer key) -> new HashSet<>());
        // 如果该服务已经在服务器上运行，返回 false
        if (names.contains(serviceName)) return false;
        // 否则将该服务添加到服务器上
        names.add(serviceName);
        // 更新服务的实例数量
        counter.put(serviceName, counter.getOrDefault(serviceName, 0) + 1);
        return true;
    }
    
    // 添加服务之间的依赖关系
    boolean addDependency(String fromServiceName, String toServiceName) {
        // 获取某个服务的依赖关系集合，如果没有则创建新的集合
        Set<String> adj = graph.computeIfAbsent(fromServiceName, (String key) -> new HashSet<>());
        // 如果该依赖关系已经存在，则返回 false
        if (adj.contains(toServiceName)) return false;
        // 否则添加新的依赖关系
        adj.add(toServiceName);
        return true;
    }
    
    // 判断一个服务是否可用（是否可以满足所有依赖）
    boolean isServiceAvailable(String serviceName) {
        // 使用哈希集记录已访问的服务，避免循环依赖
        HashSet<String> vis = new HashSet<>();
        // 调用深度优先搜索（DFS）来检查服务是否可用
        return dfs(vis, serviceName);
    }
    
    // 深度优先搜索（DFS）用于判断服务是否可用
    boolean dfs(Set<String> vis, String now) {
        // 如果服务实例数量为 0，说明服务不可用
        if (counter.getOrDefault(now, 0) == 0) return false;
        // 如果该服务已经访问过，避免重复访问
        if (vis.contains(now)) return true;
        // 标记当前服务为已访问
        vis.add(now);
        // 遍历当前服务的所有依赖服务，判断依赖服务是否可用
        for (String adj : graph.getOrDefault(now, new HashSet<String>())) {
            // 如果某个依赖的服务不可用，则返回 false
            if (!dfs(vis, adj)) return false;
        }
        // 如果所有依赖的服务都可用，返回 true
        return true;
    }
}

C++ 实现

#include<bits/stdc++.h>
using namespace std;

class ServiceMgrSys {
public:
    unordered_map<string, int> counter;  // 服务实例数量，记录每个服务启动的数量
    unordered_map<string, unordered_set<string>> graph;  // 服务依赖图，记录服务之间的依赖关系
    unordered_map<int, unordered_set<string>> services;  // 服务器上的服务实例，记录每台服务器上运行的服务

    // 重启服务器
    void rebootServers(vector<int>& serverIds) {
        for (int serverId : serverIds) {
            // 检查服务器是否有运行的服务
            if (services.count(serverId)) {
                // 如果有服务，减少对应服务的计数
                for (const string& serviceName : services[serverId]) {
                    counter[serviceName]--;
                }
                // 删除该服务器上的所有服务实例
                services.erase(serverId);
            }
        }
    }

    // 启动服务
    bool startService(int serverId, string serviceName) {
        // 如果该服务器已经运行该服务，则不能重复启动
        if (services[serverId].count(serviceName)) return false;
        // 启动服务并更新服务实例数量
        services[serverId].insert(serviceName);
        counter[serviceName]++;
        return true;
    }

    // 添加依赖关系
    bool addDependency(string fromServiceName, string toServiceName) {
        // 如果已经存在依赖关系，不能重复添加
        if (graph[fromServiceName].count(toServiceName)) return false;
        // 添加依赖关系
        graph[fromServiceName].insert(toServiceName);
        return true;
    }

    // 判断服务是否可用
    bool isServiceAvailable(string serviceName) {
        unordered_set<string> visited;  // 用于记录访问过的服务，防止出现循环依赖
        return dfs(serviceName, visited);  // 深度优先搜索判断服务是否可用
    }

private:
    // 深度优先搜索，判断服务是否可用
    bool dfs(const string& serviceName, unordered_set<string>& visited) {
        // 如果服务实例数量为0，说明该服务不可用
        if (counter[serviceName] == 0) return false;
        // 如果该服务已经访问过，说明它是可用的（避免循环依赖）
        if (visited.count(serviceName)) return true;
        visited.insert(serviceName);
        
        // 递归检查该服务依赖的其他服务是否可用
        for (const string& dep : graph[serviceName]) {
            if (!dfs(dep, visited)) return false;  // 如果有一个依赖的服务不可用，当前服务也不可用
        }
        return true;
    }
};