[UPLOAD] first

shevakuilin · Jan 29, 2019 · ac331d5 · ac331d5
1 parent 59d8ce1
commit ac331d5
Show file tree

Hide file tree

Showing 11 changed files with 233 additions and 0 deletions.
diff --git a/AddingTwoNumbers.playground/Contents.swift b/AddingTwoNumbers.playground/Contents.swift
@@ -0,0 +1,136 @@
+import UIKit
+
+// 题目：两数相加
+
+// 给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
+// 如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
+// 您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
+
+// 示例：
+// 输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
+// 输出：7 -> 0 -> 8
+// 原因：342 + 465 = 807
+
+class ListNode { // 链表节点
+    var val: Int
+    var next: ListNode?
+
+    init(_ val: Int) {
+        self.val = val
+        self.next = nil
+    }
+}
+
+class List { // 链表
+    var head: ListNode?
+    var tail: ListNode?
+
+    // 尾插法
+    func appendToTail(_ val: Int) {
+        if tail == nil {
+            tail = ListNode(val)
+            head = tail
+        } else {
+            tail?.next = ListNode(val)
+            tail = tail?.next
+        }
+    }
+
+//    func initListNodeFromTail2(_ array: [Int]) -> ListNode {
+//        var headNode:ListNode?
+//        var tail:ListNode?
+//        for data in array {
+//            let tempNode = ListNode(data)
+//            tempNode.val = data
+//            if tail == nil {
+//                tail = tempNode
+//                headNode = tail
+//            } else {
+//                tail?.next = tempNode
+//                tail = tempNode
+//            }
+//        }
+//        return headNode!
+//    }
+
+    // 头插法
+    func appendToHead(_ val: Int) {
+        if head == nil {
+            head = ListNode(val)
+            tail = head
+        } else {
+            let temp = ListNode(val)
+            temp.next = head
+            head = temp
+        }
+    }
+
+//    func initListNodeFromHead2(_ array: [Int]) -> ListNode {
+//        var headNode: ListNode?
+//        for data in array {
+//            let tempNode = ListNode(data)
+//            tempNode.val = data
+//            if headNode == nil {
+//                headNode = tempNode
+//            } else {
+//                tempNode.next = headNode
+//                headNode = tempNode
+//            }
+//        }
+//        return headNode!
+//    }
+//
+//    // 打印
+//    func printList(_ list: inout ListNode) {
+//        var tempList:ListNode? = list
+//        while tempList != nil {
+//            print("\(tempList!.val)")
+//            if tempList!.next == nil {
+//                break
+//            }
+//            tempList = tempList!.next!
+//        }
+//    }
+}
+
+// 参考: 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?
+    var l1 = list1
+    var l2 = list2
+
+    var carry: Int = 0
+    while l1 != nil || l2 != nil || carry != 0 {
+        let sum: Int = (l1 == nil ? 0 : (l1?.val)!) + (l2 == nil ? 0 : (l2?.val)!) + carry
+        carry = sum/10
+
+        let node = ListNode(sum % 10)
+        if tmp == nil {
+            tmp = node
+            result = tmp!
+        } else {
+            tmp?.next = node
+            tmp = tmp?.next
+        }
+
+        l1 = l1 == nil ? nil : l1?.next
+        l2 = l2 == nil ? nil : l2?.next
+    }
+
+    return result
+}
+
+// 验证
+// 输入：[2,4,3]，[5,6,4]
+// 输出: [7,0,8]
+// 预期结果：[7,0,8]
+// https://leetcode-cn.com/problems/add-two-numbers/
diff --git a/AddingTwoNumbers.playground/contents.xcplayground b/AddingTwoNumbers.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>
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
@@ -0,0 +1,8 @@
+<?xml version="1.0" encoding="UTF-8"?>
+<!DOCTYPE plist PUBLIC "-//Apple//DTD PLIST 1.0//EN" "http://www.apple.com/DTDs/PropertyList-1.0.dtd">
+<plist version="1.0">
+<dict>
+	<key>IDEDidComputeMac32BitWarning</key>
+	<true/>
+</dict>
+</plist>
diff --git a/.../playground.xcworkspace/xcuserdata/xiangkuilin.xcuserdatad/UserInterfaceState.xcuserstate b/.../playground.xcworkspace/xcuserdata/xiangkuilin.xcuserdatad/UserInterfaceState.xcuserstate
diff --git a/README.md b/README.md
@@ -1,2 +1,7 @@
 # LeetCode-Swift
 LeetCode算法题Swift版
+
+### 已上传的算法题
+
+- 《两数之和》
+- 《两数相加》
diff --git a/SumOfTwoNumbers.playground/Contents.swift b/SumOfTwoNumbers.playground/Contents.swift
@@ -0,0 +1,54 @@
+import UIKit
+
+// 题目：两数之和
+
+// 给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
+// 你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
+
+// 示例:
+// 给定 nums = [2, 7, 11, 15], target = 9
+// 因为 nums[0] + nums[1] = 2 + 7 = 9
+// 所以返回 [0, 1]
+
+func queryIndex(nums: [Int], target: Int) -> [Int]? {
+    var dic = [Int: Int]()
+    for i in 0..<nums.count {
+        let complement = target - nums[i]
+        if dic.keys.contains(complement) {
+            return [dic[complement]!, i]
+        }
+        dic[nums[i]] = i
+    }
+    return nil
+}
+
+// 参考： https://zhuanlan.zhihu.com/p/38094061
+// 解法：一遍哈希表：
+// 事实证明，我们可以一次完成。在进行迭代并将元素插入到表中的同时，我们还会回过头来检查表中是否已经存在当前元素所对应的目标元素。如果它存在，那我们已经找到了对应解，并立即将其返回。
+
+// 复杂度分析：
+// 时间复杂度：O(n)，我们只遍历了包含有 n 个元素的列表一次。在表中进行的每次查找只花费  O(1)  的时间。
+// 空间复杂度：O(n)，所需的额外空间取决于哈希表中存储的元素数量，该表最多需要存储  n 个元素。
+
+// 验证
+let scanArr = [2, 7, 11, 15]
+let result = queryIndex(nums: scanArr, target: 9)
+
+// 改进解法
+// 返回参数改进，数组 -> 元组
+// 改进内容，空间复杂读降低，省去一个数组的内存空间分配 [实际上只是换种参数传递]
+func queryIndex1(nums: [Int], target: Int) -> (Int?, Int)? {
+    var dic = [Int: Int]()
+    for i in 0..<nums.count {
+        let complement = target - nums[i]
+        if dic.keys.contains(complement) {
+            return (dic[complement], i)
+        }
+        dic[nums[i]] = i
+    }
+    return nil
+}
+
+// 验证
+let result1 = queryIndex1(nums: scanArr, target: 9)
+
diff --git a/SumOfTwoNumbers.playground/contents.xcplayground b/SumOfTwoNumbers.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>
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
@@ -0,0 +1,8 @@
+<?xml version="1.0" encoding="UTF-8"?>
+<!DOCTYPE plist PUBLIC "-//Apple//DTD PLIST 1.0//EN" "http://www.apple.com/DTDs/PropertyList-1.0.dtd">
+<plist version="1.0">
+<dict>
+	<key>IDEDidComputeMac32BitWarning</key>
+	<true/>
+</dict>
+</plist>
diff --git a/.../playground.xcworkspace/xcuserdata/xiangkuilin.xcuserdatad/UserInterfaceState.xcuserstate b/.../playground.xcworkspace/xcuserdata/xiangkuilin.xcuserdatad/UserInterfaceState.xcuserstate