leetCode算法题解

class 两数之和{
    func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
        guard !nums.isEmpty else {return []}
        var dict = [Int:Int]()
        for i in 0...nums.count - 1{
            dict[nums[i]] = i
        }
        
        for i in 0...nums.count - 1 {
            let aimNum = target - nums[i]
            if let index = dict[aimNum],index != i{
                return [i,index]
            }
        }
        return []
    }
}

class 归并排序{
    
    func sort(arr:[Int]) ->[Int]{
        guard arr.count > 1 else { return arr }
        //1 分解,采用左开右必原则
        let mid = (arr.count) / 2
        let leftArr = sort(arr: Array.init(arr[0 ..< mid])) //
        let rightArr = sort(arr: Array.init(arr[mid ..< arr.count ]))
        //合并
        return merge(leftArr: leftArr, rightArr: rightArr)
    }
    func merge(leftArr:[Int],rightArr:[Int]) ->[Int]{
        var finalArr = [Int]()
        var leftIndex = 0
        var rightIndex = 0
        while leftIndex < leftArr.count && rightIndex < rightArr.count { //终止条件 这里要并且(出现过错误,检查好久)
            if leftArr[leftIndex] < rightArr[rightIndex]{
                finalArr.append(leftArr[leftIndex])
                leftIndex += 1
            }else{
                finalArr.append(rightArr[rightIndex])
                rightIndex += 1
            }
        }
        //如果左边指针,或者右边指针指向数组末尾,则排序完毕,添加另外一个没有访问完毕的数组,并加入到final里面,最开始忘记加,半夜脑子不好使(错误二)
        if leftIndex == leftArr.count{
            finalArr += rightArr[rightIndex...]
        }else{
            finalArr += leftArr[leftIndex...]
        }
        return finalArr
    }
    
}

class 无重复最长子串{
    func lengthOfLongestSubstring(_ s: String) -> Int {
        var maxCount = 0
        guard s.count > 0 else {return maxCount }
        var maxString = String.init()
        for char in s {
            while maxString.contains(char) {
                maxString.removeFirst()
            }
            maxString.append(char)
            maxCount = max(maxString.count, maxCount)
        }
        return maxCount
    }
}

public class ListNode {
      public var val: Int
      public var next: ListNode?
      public init(_ val: Int) {
          self.val = val
          self.next = nil
      }
  }
 
class 两数相加 {
    func addTwoNumbers(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
        var l1Point = l1
        var l2Point = l2
        let finalList = ListNode.init(-1)
        var curListNode = finalList
        var needAddOne = 0
        while l1Point != nil || l2Point != nil || needAddOne == 1{ //第四遍,没有判断计算最后,有进位的情况
            let l1Value = l1Point == nil ? 0 : l1Point!.val
            let l2Value = l2Point == nil ? 0 : l2Point!.val
            let finalValue = (l1Value + l2Value + needAddOne) % 10 //第三遍没有加进位
            if finalList.val == -1{
                curListNode.val = finalValue
            }else{
                curListNode.next = ListNode.init(finalValue)
                curListNode = curListNode.next! //第一遍错误没有更新curnode
            }
            needAddOne = (l1Value + l2Value + needAddOne) > 9 ? 1 : 0 //第二遍错误,没有把上一次计算的进位加上
            if l1Point != nil{
                l1Point = l1Point!.next
            }
            if l2Point != nil{
                l2Point = l2Point!.next
            }
        }
        return finalList
    }
    
}