[CREATE] 无重复字符的最长子串

shevakuilin · Jan 29, 2019 · 180f826 · 180f826
1 parent c67ae8b
commit 180f826
Show file tree

Hide file tree

Showing 12 changed files with 64 additions and 39 deletions.
diff --git a/AddingTwoNumbers.playground/playground.xcworkspace/contents.xcworkspacedata b/AddingTwoNumbers.playground/playground.xcworkspace/contents.xcworkspacedata
diff --git a/AddingTwoNumbers.playground/playground.xcworkspace/xcshareddata/IDEWorkspaceChecks.plist b/AddingTwoNumbers.playground/playground.xcworkspace/xcshareddata/IDEWorkspaceChecks.plist
diff --git a/.../playground.xcworkspace/xcuserdata/xiangkuilin.xcuserdatad/UserInterfaceState.xcuserstate b/.../playground.xcworkspace/xcuserdata/xiangkuilin.xcuserdatad/UserInterfaceState.xcuserstate
diff --git a/SumOfTwoNumbers.playground/playground.xcworkspace/contents.xcworkspacedata b/SumOfTwoNumbers.playground/playground.xcworkspace/contents.xcworkspacedata
diff --git a/SumOfTwoNumbers.playground/playground.xcworkspace/xcshareddata/IDEWorkspaceChecks.plist b/SumOfTwoNumbers.playground/playground.xcworkspace/xcshareddata/IDEWorkspaceChecks.plist
diff --git a/.../playground.xcworkspace/xcuserdata/xiangkuilin.xcuserdatad/UserInterfaceState.xcuserstate b/.../playground.xcworkspace/xcuserdata/xiangkuilin.xcuserdatad/UserInterfaceState.xcuserstate
diff --git a/SumOfTwoNumbers.playground/Contents.swift → 算法练习题/两数之和.playground/Contents.swift b/SumOfTwoNumbers.playground/Contents.swift → 算法练习题/两数之和.playground/Contents.swift
diff --git a/...oNumbers.playground/contents.xcplayground → 算法练习题/两数之和.playground/contents.xcplayground b/...oNumbers.playground/contents.xcplayground → 算法练习题/两数之和.playground/contents.xcplayground
diff --git a/AddingTwoNumbers.playground/Contents.swift → 算法练习题/两数相加.playground/Contents.swift b/AddingTwoNumbers.playground/Contents.swift → 算法练习题/两数相加.playground/Contents.swift
@@ -93,15 +93,6 @@ class List { // 链表
 //    }
 }
 
-// 参考: https://www.jianshu.com/p/cf962aeff643
-// https://blog.csdn.net/biezhihua/article/details/79437867
-
-// 核心解析：
-// 1. 链表对应结点相加时增加前一个结点的进位，并保存下一个结点的进位；除法得进位，模得结果。
-// 2. 两个链表长度不一致时，要处理较长链表剩余的高位和进位计算的值；
-// 3. 如果最高位计算时还产生进位，则还需要添加一个额外结点。
-
-// 解法
 func addTwoNumbers(list1: ListNode?, list2: ListNode?) -> ListNode? {
     var tmp: ListNode?
     var result: ListNode?
@@ -129,12 +120,22 @@ func addTwoNumbers(list1: ListNode?, list2: ListNode?) -> ListNode? {
     return result
 }
 
+// 参考: https://www.jianshu.com/p/cf962aeff643
+// https://blog.csdn.net/biezhihua/article/details/79437867
+// 核心解析：
+// 1. 链表对应结点相加时增加前一个结点的进位，并保存下一个结点的进位；除法得进位，模得结果。
+// 2. 两个链表长度不一致时，要处理较长链表剩余的高位和进位计算的值；
+// 3. 如果最高位计算时还产生进位，则还需要添加一个额外结点。
+
 // 验证
 // 输入：[2,4,3]，[5,6,4]
 // 输出: [7,0,8]
 // 预期结果：[7,0,8]
 // https://leetcode-cn.com/problems/add-two-numbers/
 
+
+/*=====================*/
+
 // 备注参考
 // swift 实现单链表创建、插入、删除 https://www.jianshu.com/p/68de9b3daa13
 // Swift 链表 的制作 使用 https://blog.csdn.net/sunzhenglin2016/article/details/52690860

diff --git a/...oNumbers.playground/contents.xcplayground → 算法练习题/两数相加.playground/contents.xcplayground b/...oNumbers.playground/contents.xcplayground → 算法练习题/两数相加.playground/contents.xcplayground
diff --git a/算法练习题/无重复字符的最长子串.playground/Contents.swift b/算法练习题/无重复字符的最长子串.playground/Contents.swift
@@ -0,0 +1,50 @@
+import UIKit
+
+// 题目：无重复字符的最长子串
+
+// 给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
+
+// 示例 1:
+// 输入: "abcabcbb"
+// 输出: 3
+// 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
+
+// 示例 2:
+// 输入: "bbbbb"
+// 输出: 1
+// 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
+
+// 示例 3:
+// 输入: "pwwkew"
+// 输出: 3
+// 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
+// 请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
+
+func lengthOfLongestSubstring(_ s: String) -> Int {
+    var start: Int = 0
+    var maxLength: Int = 0
+    var usedChar: [Character:Int] = [:]
+    var index: Int = 0
+
+    for char in s {
+        if usedChar.keys.contains(char) && start <= usedChar[char]! {
+            start = usedChar[char]! + 1
+        } else {
+            maxLength = max(maxLength, index - start + 1)
+        }
+        usedChar[char] = index
+        index += 1
+    }
+    return maxLength
+}
+
+// 参考：https://blog.csdn.net/qq_17550379/article/details/80547777
+// https://zhuanlan.zhihu.com/p/35364681
+// 解析
+// 重点是 「最长」，这一点一定要注意，所以光筛选出不含重复的子串长度是没有用的，还要找出最长的子串
+// 也就是说，如果筛选出第一个不含重复的子串的长度后，如果之后没有（再找到重复的字符）更长的就不需要再更新这个长度了，如果有更长的就替换当前的长度即可
+// 可以利用之前「两数之和」中使用hash表的思想
+// 时间复杂度是O(n)，空间复杂度也是O(n)
+
+// 验证
+lengthOfLongestSubstring("pwwkew")
diff --git a/算法练习题/无重复字符的最长子串.playground/contents.xcplayground b/算法练习题/无重复字符的最长子串.playground/contents.xcplayground
@@ -0,0 +1,4 @@
+<?xml version="1.0" encoding="UTF-8" standalone="yes"?>
+<playground version='5.0' target-platform='ios' executeOnSourceChanges='false'>
+    <timeline fileName='timeline.xctimeline'/>
+</playground>