算法刷题2023-09-20

无重复字符的最长子串

方法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  -- 根据班级名字将结果分组,以获得每个班级的最高分数

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 211,423评论 6 491
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 90,147评论 2 385
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 157,019评论 0 348
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 56,443评论 1 283
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 65,535评论 6 385
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 49,798评论 1 290
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 38,941评论 3 407
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 37,704评论 0 266
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 44,152评论 1 303
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,494评论 2 327
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,629评论 1 340
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 34,295评论 4 329
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 39,901评论 3 313
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,742评论 0 21
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,978评论 1 266
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 46,333评论 2 360
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 43,499评论 2 348

推荐阅读更多精彩内容