算法初赛第十五题
2021/11/12 22:11:11
本文主要是介绍算法初赛第十五题,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
算法初赛第十五题
- 题目描述
- 解法一
- 解题思路
- python代码
题目描述
实现 strStr() 函数。
给你两个字符串 haystack 和 needle ,请你在 haystack 字符串中找出 needle 字符串出现的第一个位置(下标从 0 开始)。如果不存在,则返回 -1 。当 needle 是空字符串时我们应当返回 0 。
示例 1:
输入:haystack = “hello”, needle = “ll”
输出:2
示例 2:
输入:haystack = “aaaaa”, needle = “bba”
输出:-1
示例 3:
输入:haystack = “”, needle = “”
输出:0
解法一
解题思路
dfs算法 1.定义数组visited[n],表示数组isConnected中每个元素 的访问状态,visited初始值全为False,定义ans=0。 2.定义函数dfs(i),来将以isConnected[i]为核心的省份内的每个城市的访问状态标为True for j in range(len(isConnected)): if isConnected[i][j] and not visited[j]: visited[j] = True dfs(j) 3.遍历数组isConnected 3.1如果isConnected[i]还未被访问 3.1.1将isConnected[i]标记为以访问,即visited[i] = True 3.1.2调用函数dfs(i) 3.1.3 ans加上一 4.返回ans
python代码
def findCircleNum(self, isConnected: List[List[int]]) -> int: ans, visited = 0, [False] * len(isConnected) #以isConnected[i]为核心,将和isConnected[i]同一个省份的标记为以访问 def dfs(i): for j in range(len(isConnected)): if isConnected[i][j] and not visited[j]: visited[j] = True dfs(j) for i in range(len(isConnected)): if not visited[i]: #如果isConnected[i],没有被访问过 visited[i] = True dfs(i) ans += 1 return ans
运行结果
这篇关于算法初赛第十五题的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-04TiDB 资源管控的对撞测试以及最佳实践架构
- 2024-07-03万字长文聊聊Web3的组成架构
- 2024-07-02springboot项目无法注册到nacos-icode9专业技术文章分享
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现