剑指 Offer 62. 圆圈中最后剩下的数字

• https://algo.itcharge.cn/Solutions/Offer/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/

0 1 2 3 4 5 6

0 1 2 4 5 6 第1次 删除3
0 1 2 5 6 第2次 删除4
0 1 2 6 第3次 删除5
0 1 2 第4次 删除6

… 第n次

# 方法1: 递归 
def lastRemaining(n, m):
    # 递归方法，最后剩下的数字的编号
    if n == 1:
        return 0
    return (lastRemaining(n - 1, m) + m) % n

# 方法2: 动态规划
def lastRemaining(n, m):
    last = 0  # 当只剩下一个数字时，最后的数字是0
    for i in range(2, n + 1):  # 从2开始，因为我们已经知道当n=1时，结果是0
        last = (last + m) % i
    return last

0003. 无重复字符的最长子串

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        left = 0
        right = 0
        window = dict()
        ans = 0

        while right < len(s):
            if s[right] not in window:
                window[s[right]] = 1
            else:
                window[s[right]] += 1

            while window[s[right]] > 1:
                window[s[left]] -= 1
                left += 1

            ans = max(ans, right - left + 1)
            right += 1

        return ans

0014. 最长公共前缀

"""

1、依次遍历所有字符串的每一列，比较相同位置上的字符是否相同。
    如果相同，则继续对下一列进行比较。
    如果不相同，则当前列字母不再属于公共前缀，直接返回当前列之前的部分。
2、如果遍历结束，说明字符串数组中的所有字符串都相等，则可将字符串数组中的第一个字符串作为公共前缀进行返回。


"""

strs = ["flower", "flow", "flight"]

length = len(strs[0])
count = len(strs)
for i in range(length):
    c = strs[0][i]
    for j in range(1, count):
        if len(strs[j]) == i or strs[j][i] != c:
            result = strs[0][:i]
    result = strs[0]

0151. 反转字符串中的单词

• https://algo.itcharge.cn/Solutions/0100-0199/reverse-words-in-a-string/

s = "  hello world  "
print(" ".join(sorted(s.strip().split(" "),reverse=True)))

__END__