<jupyter_start><jupyter_text>213. 打家劫舍 test<jupyter_code>class Solution:
    def robrange(self, nums: list, start: int, end: int) -> int:
        dp_2 = 0
        dp_1 = 0
        dp = 0
        for i in range(start, end + 1):
            dp = max(dp_2 + nums[i], dp_1)
            dp_2 = dp_1
            dp_1 = dp
        return dp
        
    def rob(self, nums: list) -> int:
        if len(nums) == 1:
            return nums[0]
        if len(nums) == 2:
            return max(nums)
#         if len(nums) == 3:
#             return max(nums)
        return max(self.robrange(nums, 0, len(nums) - 2), 
                            self.robrange(nums, 1, len(nums) - 1))<jupyter_output><empty_output><jupyter_text>2. 两数相加- 给你两个非空的链表，表示两个非负的整数，它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。- 请将两个数相加，并以相同形式返回一个表示和的链表。- 你可以假设除了数字0之外，这两个数都不会以0开头<jupyter_code># Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution:
    def createListNode(self, nums):
        l1 = ListNode()
        head = l1
        for i in nums:
            l1.next = ListNode(i, None)
            l1 = l1.next
        return head.next

    def printListNode(shle, head):
        temp = head
        while temp:
            print(temp.val)
            temp = temp.next

    def addTwoNumbers(self, l1, l2):
        nums = []
        flag = 0
        l1_index = l1
        l2_index = l2
        while l1_index or l2_index:
            if flag == 1:
                if l1_index == None:
                    sums = l2_index.val + 1
                elif l2_index == None:
                    sums = l1_index.val + 1
                else:
                    sums = l1_index.val + l2_index.val + 1
            else:
                if l1_index == None:
                    sums = l2_index.val
                elif l2_index == None:
                    sums = l1_index.val
                else:
                    sums = l1_index.val + l2_index.val
            if sums >= 10:
                flag = 1
                nums.append(sums - 10)
            else:
                flag = 0
                nums.append(sums)
            if l1_index:
                l1_index = l1_index.next
            if l2_index:
                l2_index = l2_index.next
        if flag == 1:
            nums.append(1)
        return self.createListNode(nums)

s = Solution()
nums_l1 = [9, 9, 9, 9, 9, 9, 9]
nums_l2 = [9, 9, 9, 9]
l1 = s.createListNode(nums_l1)
l2 = s.createListNode(nums_l2)
result = s.addTwoNumbers(l1,l2)
s.printListNode(result)<jupyter_output>8
9
9
9
0
0
0
1<jupyter_text>题解 引用Leetcode“大神学费了的Kai”的代码- 连等赋值的大概规则就是先从左到右解析各个引用，然后再计算最右侧的表达式子的值，最后把值从右到左赋给各个引用- 关于连等赋值的详细规则请参考CSDNhttps://blog.csdn.net/bjiang927/article/details/79258036- ?divmod(x, y, /) 该函数会返回一个元组，两个值，前一个是x//y（整除操作），后一个是x%y（取余操作）<jupyter_code>class Solution:
    def addTwoNumbers(self, l1, l2):
        head = curr = ListNode()  
        carry = val = 0
        while carry or l1 or l2:
            val = carry
            if l1: l1, val = l1.next, l1.val + val
            if l2: l2, val = l2.next, l2.val + val
            carry, val = divmod(val, 10)
            curr.next = curr = ListNode(val)
        return head.next<jupyter_output><empty_output><jupyter_text>28. 实现strStr()- 给你两个字符串haystack和needle，请在haystack字符串找出needle字符串出现的第一个位置（下标从0开始）。如果不存在，则返回-1- 当needle是空字符串时，应当返回0，这是一个很好的面试题，对于本题而言，也很符合C中的strstr()以及Java的indexOf()<jupyter_code>class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        n = len(needle)
        if needle == "":
            return 0
        falg = False
        for j in range(len(haystack)-n+1):
            for i in range(n):
                if needle[i] == haystack[j+i]:
                    falg = True
                else:
                    falg = False
                    break
            if falg:
                return j
        return -1
# haystack, needle = "hello", "ll"
haystack, needle = "", ""
s = Solution()
print(s.strStr(haystack, needle))<jupyter_output>0<jupyter_text>题解- 暴力法- KMP<jupyter_code># 改进版暴力法
class Solution:
    def strStr(self, haystack, needle):
        for i in range(len(haystack)-len(needle)+1):
            if haystack[i:i+len(needle)] == needle:
                return i
        return -1<jupyter_output><empty_output><jupyter_text>关于前缀函数的性质几点说明：- 1.&pi;(i)&le;&pi;(i-1)+1。        &rArr;依据&pi;(i)定义得：s[0:&pi;(i)-1] = s[i-&pi;(i)+1:i]        &rArr;将两区间的右端点同时左移，可得：s[0:&pi;(i)-2] = s[i-&pi;(i)+1:i-1]        &rArr;依据&pi;(i-1)定义得：&pi;(i-1)&ge;&pi;(i)-1,即&pi;(i)&le;&pi;(i-1)+1    关于第三点的解释，第i个子串不可能比i-1个子串前缀长两个单位，因为第i个子串在增加前缀长度的时候务必会经过第i-1个子串，只有第i-1个子串达到最大长度时，第i个子串才能在它的基础上加1.实际上在增加前缀长度的时候，只需要看那增加的一个字符和第i个字符是否相等即可，若相等，则可以在i-1的最大前缀长度上加1，否则就只能减少，即i子串的最大前缀长度小于等于&pi:(i-1)+1的最大前缀长度- 2.如果s[i]=s[&pi;(i-1)],那么&pi;(i)=&pi;(i-1)+1.    &rArr;依据&pi;(i-1)定义得：s[0:&pi;(i-1)-1]=s[i-&pi;(i-1):i-1]    &rArr;因为s[&pi;(i-1)]=s[i],可得s[0:&pi;(i-1)]=s[i-&pi;(i-1):i]        &rArr;依据&pi;(i)定义得：&pi;(i)&ge;&pi;(i-1)+1,结合第一个性质可得&pi;(i)=&pi;(i-1)+1 &pi;   &iquest;   &raquo;  &laquo;  &rArr;   " “  &infin;  &fnof;(x)   &times;   &divide;  &radic;4   &ang;45&deg;  &int;&int;x&sup3;   &there4;   &ne;   &plusmn; 2&sup1;time&sup2;&rarr;&rArr;&sect;&frac12;&frac34;&para;&tau;<jupyter_code># KMP
class Solution:
    def strStr(self, haystack, needle):
        m, n = len(needle), len(haystack)
        if m == 0:
            return 0
        j = 0
        pi = [0 for i in range(m)]
        for i in range(1, len(needle)):
            while(j > 0 and needle[i] != needle[j]):
                j = pi[j-1]
            if needle[i] == needle[j]:
                j += 1
            pi[i] = j
        
        j = 0
        for i in range(n):
            while(j > 0 and needle[j] != haystack[i]):
                j = pi[j-1]
            if needle[j] == haystack[i]:
                j += 1
            if j == m:
                return i - m + 1
        return -1
# s = Solution()
# haystack, needle = "hello", "ll"
# haystack, needle = "aaaaa", "bba"
# haystack, needle = "", ""
# print(s.strStr(haystack, needle))<jupyter_output>0<jupyter_text>求解前缀函数F的思路https://www.cnblogs.com/SYCstudio/p/7194315.html:~:text=KMP%E7%AE%97%E6%B3%95%E5%B0%B1%E6%98%AF%E8%A7%A3%E5%86%B3%E4%B8%8A%E9%9D%A2%E7%9A%84%E9%97%AE%E9%A2%98%E7%9A%84%EF%BC%8C%E5%9C%A8%E8%AE%B2%E8%BF%B0%E4%B9%8B%E5%89%8D%EF%BC%8C%E6%88%91%E4%BB%AC%E5%85%88%E6%91%86%E5%87%BA%E4%B8%A4%E4%B8%AA%E6%A6%82%E5%BF%B5%EF%BC%9A.%20%E5%89%8D%E7%BC%80%EF%BC%9A%E6%8C%87%E7%9A%84%E6%98%AF%E5%AD%97%E7%AC%A6%E4%B8%B2%E7%9A%84%E5%AD%90%E4%B8%B2%E4%B8%AD%E4%BB%8E%E5%8E%9F%E4%B8%B2%E6%9C%80%E5%89%8D%E9%9D%A2%E5%BC%80%E5%A7%8B%E7%9A%84%E5%AD%90%E4%B8%B2%EF%BC%8C%E5%A6%82abcdef%E7%9A%84%E5%89%8D%E7%BC%80%E6%9C%89%EF%BC%9Aa%2Cab%2Cabc%2Cabcd%2Cabcde.,%E5%90%8E%E7%BC%80%EF%BC%9A%E6%8C%87%E7%9A%84%E6%98%AF%E5%AD%97%E7%AC%A6%E4%B8%B2%E7%9A%84%E5%AD%90%E4%B8%B2%E4%B8%AD%E5%9C%A8%E5%8E%9F%E4%B8%B2%E7%BB%93%E5%B0%BE%E5%A4%84%E7%BB%93%E5%B0%BE%E7%9A%84%E5%AD%90%E4%B8%B2%EF%BC%8C%E5%A6%82abcdef%E7%9A%84%E5%90%8E%E7%BC%80%E6%9C%89%EF%BC%9Af%2Cef%2Cdef%2Ccdef%2Cbcdef.%20KMP%E7%AE%97%E6%B3%95%E5%BC%95%E5%85%A5%E4%BA%86%E4%B8%80%E4%B8%AAF%E6%95%B0%E7%BB%84%EF%BC%88%E5%9C%A8%E5%BE%88%E5%A4%9A%E6%96%87%E7%AB%A0%E4%B8%AD%E4%BC%9A%E7%A7%B0%E4%B8%BAnext%2C%E4%BD%86%E7%AC%94%E8%80%85%E6%9B%B4%E4%B9%A0%E6%83%AF%E7%94%A8F%EF%BC%8C%E8%BF%99%E6%9B%B4%E6%96%B9%E4%BE%BF%E8%A1%A8%E8%BE%BE%EF%BC%89%EF%BC%8CF%5Bi%5D%E8%A1%A8%E7%A4%BA%E7%9A%84%E6%98%AF%E5%89%8Di%E7%9A%84%E5%AD%97%E7%AC%A6%E7%BB%84%E6%88%90%E7%9A%84%E8%BF%99%E4%B8%AA%E5%AD%90%E4%B8%B2%E6%9C%80%E9%95%BF%E7%9A%84%E7%9B%B8%E5%90%8C%E5%89%8D%E7%BC%80%E5%90%8E%E7%BC%80%E7%9A%84%E9%95%BF%E5%BA%A6%EF%BC%81.前缀函数是增量函数，故可以一边读入字符串一边求解当前读入位的前缀函数，实际上这里要注意的就是j角标即作为匹配字符串的角标，又作为前缀函数的值，它会在两个数组中来回跳跃，前缀函数中的值表示当前这个子串中的最大前缀的长度，要判断needle中的i字符是否可以接在j角标表示的needle后面作为前缀时，只需要取出j角标后面的一个字符进行判断即可。首先找出前缀中可以插入的位置角标，即当needle[i] != needle[j+1]同时当前子串还有前缀子串可以跳跃时（即前缀函数j>=0）j继续往前走，j=F[j]，否则要么是跳到最前面了没得跳了，或者是找到了可以插入的位置了，即当前needle角标i和目前的needle角标j有共同前缀，有可能可以在j后面接一个字符以增加最大前缀长度（还没有跳到最前面）。当跳到了最前面时，即没有前缀可跳跃了(j=0没有跳到最前面，还有相等前缀时needel[i]= needle[j+1]，则可以在j后面接上i作为此时的最大长度，跳出循环并F[i]=j+1，F[i]=j+1.不等则j还得继续往前跳跃直到退出循环。<jupyter_code>for i in range(len(needle)):
    j = F[i-1]
    while(needle[i] != needle[j+1] and j>= 0):  
        # 先找一下needle[i]看是否可以接在前面j子串的后面，
        # 如果可以则找出具体的接入位置并退出循环（判断条件会退出，此时needl[i]=needle[j+1]）,
        # 否则j就一直往前跳跃，直到没有了前缀位置退出循环
        j = F[j]  # j 往前跳跃
    if needle[i] == needle[j+1]:  # 如果是找到了接入位置，则此时判断为True，接入
        F[i] = j+1  
        # 在当前的j值上加1即可，j即使索引角标又是当前子串的最大前后缀长度
    else:
        F[i] = -1  # ro F[i] = j 
        # 否则，没有找到共同的前缀，即j跳到了最前面，此时直接给F[i]置-1即可，
        # 或者F[i]=j,因为此时j就等于-1
        
haystack = "abcdef"
needle = "abc"
# 模式匹配
i = 0
while i < len(haystack):
    if haystack[i] == needle[j]:
        i += 1
        j += 1
        if j == len(needle):
            print(i-len(needle))
            j = F[j-1] + 1
    else:
        if j == 0:
            # 如果j就是needle的第一个，即taystack[i]!=needle[0],那么i往后走就是，j不需要往前跳
            # 其实这里应该判断，因为如果不判断j-1=0-1=-1，F会越界
            i += 1
        j = F[j-1]+1  # 不相等同时j还有前缀可跳跃时，则j往前跳跃，<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.17402228533974218, 'fraction_numerical': 0.07876338212803147, 'mean_word_length': 2.7674897119341564, 'pattern_counts': {'":': 1, '<': 27, '<?xml version=': 0, '>': 34, 'https://': 2, 'lorem ipsum': 0, 'www.': 1, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '7', 'dir': 'jupyter-structured-clean-dedup', 'id': '33289', 'license': 'MIT', 'n_tokens_mistral': 5253, 'n_tokens_neox': 5297, 'n_words': 516, 'path': 'LeetCode/medium.ipynb', 'repo_name': 'zilongyuanboy/leetcode_2', 'size': '9154'}