无重复字符的最长子串
方法1
def length_of_longest_substring(s):
# 创建一个字典来存储字符和它们的索引
char_index = {}
max_length = 0
start = 0
for end in range(len(s)):
# 如果字符在字典中并且位于当前子串内，则更新子串的起始位置
if s[end] in char_index and char_index[s[end]] >= start:
start = char_index[s[end]] + 1
print(start,end)
# 在字典中记录字符的索引
char_index[s[end]] = end
print(char_index)
# 更新最大子串长度
max_length = max(max_length, end - start + 1)
print(max_length)
return max_length
# 测试示例
s = "abcabcbbabccdcbbae"
d = "123456789012345678"
result = length_of_longest_substring(s)
print(result)
#这段代码使用一个滑动窗口，通过移动start和end指针来维护一个不含重复字符的子串。当遇到重复字符时，将start指针移到重复字符的下一个位置，并继续检查。在遍历整个字符串的过程中，不断更新最长子串的长度。
方法2
class Solution(object):
def lengthOfLongestSubstring(self, s):
char_set = set()
max_length = 0
start = 0
for end in range(len(s)):
while s[end] in char_set:
# print(' s[end]=',s[end])
# print(char_set)
char_set.remove(s[start])
# print(char_set)
start += 1
# print(start)
char_set.add(s[end])
# print(char_set)
max_length = max(max_length, end - start + 1)
return max_length
s = "abcabcbb"
S = Solution()
print(S.lengthOfLongestSubstring(s))
# 测试示例
s = "abcabcbbbbcdeea"
result = length_of_longest_substring(s)
print(result)
#这段代码使用一个集合char_set来存储当前子串内的字符，如果遇到重复字符，就将start指针向右移动，同时从集合中移除重复字符，直到不再有重复字符。这种方法相对更简单，并且仍然具有线性时间复杂度。
寻找两个正序数组的中位数
我觉得我没错！！！！！
# 给定两个大小分别为m和n的正序（从小到大）数组nums1和
# nums2。请你找出并返回这两个正序数组的中位数 。
# 算法的时间复杂度应该为O(log(m + n)) 。
class Solution(object):
def findMedianSortedArrays(self, nums1, nums2):
list=nums1+nums2
long=len(list)
list.sort()
if long%2==0:
return (list[long//2-1]+list[long//2])/2
return list[long//2]
nums1=[1, 2]
nums2=[3, 4]
s=Solution()
res=s.findMedianSortedArrays(nums1,nums2)
print(res)
最长回文子串
获得两个字符串的最长公共回文子串，使用你认为的时间复杂度最低的算法。
例如：输入:参数1: abadefg 参数2: cabadefg 输出：aba
def longest_common_palindromic_substring(str1, str2):
def is_palindrome(s):
return s == s[::-1] # 检查字符串是否是回文串
def longest_common_substring(s1, s2):
n1, n2 = len(s1), len(s2)
dp = [[0] * (n2 + 1) for _ in range(n1 + 1)] # 创建动态规划表
max_length = 0 # 最长公共子串的长度
end = 0 # 最长公共子串的结束位置
for i in range(1, n1 + 1):
for j in range(1, n2 + 1):
if s1[i - 1] == s2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1 # 如果字符匹配，则在前一个状态的基础上加1
if dp[i][j] > max_length and is_palindrome(s1[i - dp[i][j]:i]):
# 如果找到更长的子串，并且是回文串，则更新最长子串信息
max_length = dp[i][j]
end = i
return s1[end - max_length:end] # 返回最长公共回文子串
result = ""
for i in range(len(str1)):
common = longest_common_substring(str1[i:], str2) # 在str1的每个子串上查找最长公共子串
if len(common) > len(result):
result = common # 如果找到更长的子串，更新结果
return result
# 示例输入
str1 = "abadefg"
str2 = "cabadefg"
result = longest_common_palindromic_substring(str1, str2)
print(result) # 输出 "aba"
使用json 代表一个有向图，结构如下:
nodes:[ (id; int, status: int) ].#节点列表
edges: [(from: int, to: int)]#边列表
Nodes:是代表点的数组，id 代表 node的 id，status 代表node 的状态 (3种)，1是待执行，2是成功，3是失败
edges:是代表边的数组，代表 to 节点依赖from节点执行成功后才能执行
dag 执行规则:当一个节点的所有前置节点的执行成功(2) 的时候，该节点才会被执行如果一个节点没有前置节点，那么它可以直接执行,当且仅当不存在可我行节点时，dag 结束，输出空列表
image.png
输入:"{
nodes:[{id:1,status:2},{id:2,status:2},{id:3,status:2},{id:4,status:1},{id:5,status:3},{id:6,status:1}],
edges:[{from:1,to:2},{from:1,to:3},{from:2,to:4},{from:3,to:5},{from:4,to:6},{from:5,to:6}]
}"
输出:[4]
import json
def execute_dag(dag_json):
# 解析JSON数据
dag_data = json.loads(dag_json) # 将JSON数据解析为Python数据结构
nodes = dag_data['nodes'] # 从JSON中获取节点列表
edges = dag_data['edges'] # 从JSON中获取边列表
# 创建字典来存储每个节点的状态
node_status = {node['id']: node['status'] for node in nodes} # 创建节点状态字典
# 创建字典来存储每个节点的前置节点
dependencies = {node['id']: [] for node in nodes} # 创建依赖关系字典
for edge in edges:dependencies[edge['to']].append(edge['from']) # 建立节点之间的依赖关系
# 创建一个空列表来存储可以执行的节点
executable_nodes = [] # 创建空的可执行节点列表
while True:
no_executable_nodes = True # 标记是否没有可执行的节点
for node_id, status in node_status.items():
if status == 1: # 如果节点状态为1（待执行）
# 获取该节点的前置节点
dependent_nodes = dependencies[node_id]
# 检查该节点的所有前置节点是否已经成功执行（状态为2）
if all(node_status[dep_node] == 2 for dep_node in dependent_nodes):
# 如果所有前置节点状态都为2（成功），则可以执行该节点
executable_nodes.append(node_id) # 将该节点添加到可执行节点列表
node_status[node_id] = 2 # 更新节点状态为2（成功）
no_executable_nodes = False
if no_executable_nodes: break # 如果没有可执行节点，结束循环
return executable_nodes # 返回可执行节点列表
# 示例输入
dag_json = '''
{ "nodes": [{"id": 1, "status": 2}, {"id": 2, "status": 2}, {"id": 3, "status": 2}, {"id": 4, "status": 1},{"id": 5, "status": 3}, {"id": 6, "status": 1}],
"edges": [{"from": 1, "to": 2},{"from": 1, "to": 3},{"from": 2, "to": 4},{"from": 3, "to": 5},{"from": 4, "to": 6},{"from": 5, "to": 6}]
}
'''
result = execute_dag(dag_json)
print(result) # 输出 [4]
SELECT c.class_name,
MAX(CASE WHEN sc.subject_id = 1 THEN sc.score END) AS subject1_maxscore,
MAX(CASE WHEN sc.subject_id = 2 THEN sc.score END) AS subject2_maxscore
FROM class c
JOIN student s ON c.class_id = s.class_id
JOIN Score sc ON s.student_id = sc.student_id
GROUP BY c.class_name
SELECT c.class_name, -- 选择查询结果中的列，这里选择班级名字
MAX(CASE WHEN sc.subject_id = 1 THEN sc.score END) AS subject1_maxscore, -- 计算第一个科目的最高分数
MAX(CASE WHEN sc.subject_id = 2 THEN sc.score END) AS subject2_maxscore -- 计算第二个科目的最高分数
FROM class c -- 从名为"class"的表中选择数据
JOIN student s ON c.class_id = s.class_id -- 将"class"表与"student"表关联，通过"class_id"列连接两个表
JOIN Score sc ON s.student_id = sc.student_id -- 将"student"表与"Score"表关联，通过"student_id"列连接两个表
GROUP BY c.class_name -- 根据班级名字将结果分组，以获得每个班级的最高分数
网友评论