一些LeetCode题目的实现

=Start=

缘由：

前段时间在做校招生的面试。因为大部分校招生的项目经历会比较简单，所以除了考察沟通表达能力之外，还会用一些代码题来考察编程能力（对于技术岗来说）。因为我们当前在招聘/面试的非专业研发方向（只需要具备一定的编程能力和逻辑思维能力，遇到一般问题能自己解决或者有思路解决即可），只是想了解候选人对于他写在简历里的常用编程语言掌握的熟练程度、解题思路逻辑是否清晰，所以出的题也不算难（不是那种一上来就让你手写动态规划、红黑树的风格）。因为有一段时间没写代码了，碰到这种题目我也想试一试，所以后来不太忙的时候也抽空写了几题，活动活动脑筋，在此简单记录一下，方便后面参考。

正文：

参考解答：

'''
93. 复原 IP 地址

有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。

例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "[email protected]" 是 无效 IP 地址。

给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。
'''

def restore_ipaddr(s):
    ret = set()
    s_len = len(s)
    if s_len > 12 or s_len < 4:
        return ret
    for i in range(1,s_len-2):
        for j in range(i+1,s_len-1): #从i+1开始，起始点应该是动态而非静态的，否则后面的字符串截取就可能出现空串的情况
            for k in range(j+1,s_len): #从j+1开始，起始点应该是动态而非静态的，否则后面的字符串截取就可能出现空串的情况
                a,b,c,d = s[0:i],s[i:j],s[j:k],s[k:]
                # print(a,b,c,d)
                # 前导0
                if str(int(a)) != a or \
                   str(int(b)) != b or \
                   str(int(c)) != c or \
                   str(int(d)) != d:
                    continue
                # 超255
                elif int(a)>255 or int(b)>255 or int(c)>255 or int(d)>255:
                    continue
                else:
                    ret.add(".".join([a,b,c,d]))
    return ret

print(restore_ipaddr("1111"))
print(restore_ipaddr("25525511135"))
print(restore_ipaddr("255255111135"))
print(restore_ipaddr("2552551111351"))
print(restore_ipaddr("101023"))

'''
209. 长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
'''

def min_len_sub_array(target,nums):
    if not nums:
        return 0

    left, right = 0, 0
    total = 0
    min_len = float('inf') #这个用法之前没见过，可以了解一下
    for idx,x in enumerate(nums):
        total += x
        right += 1
        while total >= target:
            total -= nums[left]
            left += 1
            print('last-min_len={}, sliding_window_len={}, left={}, right={}'.format(min_len, right-left+1,left,right))
            min_len = min(min_len, right-left+1) #右边减去左边之后要+1
        # print(idx,x,left,right,total,target)

    if min_len == float('inf'):
        return 0
    else:
        return min_len

print(min_len_sub_array(target = 7, nums = [2,3,1,2,4,3]))
print(min_len_sub_array(target = 4, nums = [1,4,4]))
print(min_len_sub_array(target = 11, nums = [1,1,1,1,1,1,1,1]))
print(min_len_sub_array(target = 11, nums = [1,1,1,1,1,1,1,1,1,1,1]))

参考链接：

Leetcode 902：最大为 N 的数字组合（超详细的解法！！！）
https://blog.csdn.net/qq_17550379/article/details/88657235
https://github.com/luliyucoordinate/Leetcode/blob/master/src/0902-Numbers-At-Most-N-Given-Digit-Set/0902.py

字符串比较
https://github.com/luliyucoordinate/Leetcode/blob/master/src/0165-Compare-Version-Numbers/0165.py

单字符重复子串的最大长度
https://leetcode.cn/problems/swap-for-longest-repeated-character-substring/

Leetcode 1156：单字符重复子串的最大长度（超详细的解法！！！）
https://blog.csdn.net/qq_17550379/article/details/99319452
https://github.com/luliyucoordinate/Leetcode/blob/master/src/1156-Swap-For-Longest-Repeated-Character-Substring/1156.py

What is the point of float(‘inf’) in Python?
https://stackoverflow.com/questions/34264710/what-is-the-point-of-floatinf-in-python

Python infinity
https://www.geeksforgeeks.org/python-infinity/

=END=

ASPIRE

一些LeetCode题目的实现

缘由：

正文：

参考解答：

参考链接：

发表回复取消回复

一些LeetCode题目的实现

缘由：

正文：

参考解答：

参考链接：

发表回复 取消回复

发表回复取消回复