LeetCode——每日一题

记录自己刷过的leetCode，作为菜鸡肯定是从简单开始啦。附上Github地址——LeetCodeRecord

1.两数之和

给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。
你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。

示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

func twoSum(_ nums: [Int], _ target: Int) -> [Int] {        
       for i in 0..<nums.count{          
         for j in i+1..<nums.count{          
             if (target - nums[i] == nums[j]) {
                 return [i, j]
             }
         }
       } 
        return [Int]()
    }

7.反转整数

给定一个 32 位有符号整数，将整数中的数字进行反转。

示例 1:
输入: 123
输出: 321

示例 2:
输入: -123
输出: -321

示例 3:
输入: 120
输出: 21

func reverse(_ x: Int) -> Int {
        var x = x
        var rev = 0
        while x != 0 {
            let p = x % 10
            x /= 10
            if (rev > Int32.max/10 || (rev == Int32.max/10 && p > 7)){
                return 0
            }
            if (rev < Int32.min/10 || (rev == Int32.min/10 && p < -8)){
                return 0
            }
            rev = rev * 10 + p
        }
        return rev
    }

9.回文数

判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。

示例 1:
输入: 121
输出: true

示例 2:
输入: -121
输出: false
解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。

示例 3:
输入: 10
输出: false
解释: 从右向左读, 为 01 。因此它不是一个回文数。

func isPalindrome(_ p: Int) -> Bool {
        if p < 0 || (p % 10 == 0 && p != 0){
            return false
        }
        var x = p
        var rev = 0
        while x > rev {
            rev = rev * 10 + x % 10
            x /= 10
        }
        return x == rev || x == rev/10
    }

13.罗马数字转整数

    func romanToInt(_ s: String) -> Int {
        var res = 0
        var dic:[String:Int] = ["I":1, "V":5, "X":10, "L":50, "C":100, "D":500, "M":1000]
        var arr = [String]()
        for str in s {
            arr.append(String.init(str))
        }
        for i in 0..<arr.count {
            /// 肯定有值，强转就好
            let val = dic[arr[i]]!
            if i == arr.count - 1 || (dic[arr[i+1]]! <= dic[arr[i]]!){
                res += val
            }else{
                res -= val
            }
        }
        return res
    }

14.最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 ""

示例 1:
输入: ["flower","flow","flight"]
输出: "fl"

示例 2:
输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。

func longestCommonPrefix(_ strs: [String]) -> String {
        if strs.count == 0 { return "" }
        var prefix = strs[0]
        
        for i in 0..<strs.count {
            while !strs[i].hasPrefix(prefix){
                
                prefix.removeLast()
                if prefix.isEmpty { return "" }
            }
        }
        return prefix
    }

20.有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。

示例 1:
输入: "()"
输出: true

示例 2:
输入: "()[]{}"
输出: true

示例 3:
输入: "(]"
输出: false

示例 4:
输入: "([)]"
输出: false

示例 5:
输入: "{[]}"
输出: true

func isValid(_ s: String) -> Bool {
        var arr = Array<String>()
        for i in s{
            if i == "(" || i == "[" || i == "{" {
                arr.append(String(i))
            }else{
                if arr.count == 0{
                    return false
                }
                let f = arr.last!
                if i == ")"{
                    if f != "("{
                        return false
                    }
                }
                if i == "]"{
                    if f != "["{
                        return false
                    }
                }
                if i == "}"{
                    if f != "{"{
                        return false
                    }
                }
                arr.removeLast()
            }
        }
        return arr.count == 0
    }

21.合并两个有序链表

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例：
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

递归

func mergeTwoLists(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
        guard let l1 = l1 else {
            return l2
        }
        guard let l2 = l2 else {
            return l1
        }
        if l1.val >= l2.val {
            l2.next = mergeTwoLists(l1, l2.next)
            return l2
        }else{
            l1.next = mergeTwoLists(l1.next, l2)
            return l1
        }
    }

迭代

func mergeTwoLists2(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
        var l1 = l1
        var l2 = l2
        if l1 == nil {
            return l2
        }
        if l2 == nil {
            return l1
        }
        let res:ListNode = ListNode.init(0)
        var cur:ListNode? = res
        
        while l1 != nil && l2 != nil {
            /*
             输出结果要求从小到大排序
             如果l1的值小，把l1加入新的链表 并把l1的链表头去掉，再循环
             */
            if l1!.val <= l2!.val {
                cur?.next = l1
                
                l1 = l1?.next
            }else{
                cur?.next = l2
                l2 = l2?.next
            }
            /*
             cur拷贝了res的next属性地址，所以每次修改cur.nextd值，res.next也会改变
             同时cur = cur?.next，所以执行cur = cur?.next时  cur的指针指向了下一个
             */
            cur = cur?.next
        }
        cur?.next = l1 == nil ? l2 : l1
        return res.next
    }