Swift 算法刷题

作者: H丶ym | 来源:发表于2021-04-01 11:49 被阅读0次

Swift 算法刷题
LeetCode题一两数之和
2020-02-01关于刷题的几个建议
Best Time to Buy and Sell Stock
刷算法题
算法-刷题
刷题算法
字节总监首发1121道LeetCode算法刷题笔记（含答案）
字节总监首发1121道LeetCode算法刷题笔记（含答案）
看完谷歌大佬的Leetcode刷题笔记，我直接手撕了200道Le

目标一周刷2道题
也不知道能坚持几天，这玩意在leetcode做完怎么保存啊

给一个有序的数组，数组中有重复数字，输入一个无序没有重复的数组
百度的一个面试题，被无序搞懵逼了，哎

class Solution {
    func test(_ nums: [Int]) -> [Int] {
        
        var result:[Int] = []
        var index = 0
        
        while index<nums.count {
            
            result.append(nums[index])
            
            index = index + 1
            
            while index<nums.count && nums[index] == nums[index-1] {
                index = index + 1
            }
            
        }
        
        
        index = 0
        let randomNumber:Int = Int(arc4random()) % result.count + 1
        var t:Int = result[index]
        while index + randomNumber < result.count {
            t = result[index]
            result[index] = result[index + randomNumber]
            result[index + randomNumber] = t
            index = index + randomNumber
        }
        
        return result
    }
}

136. 只出现一次的数字

/*
 [4,1,2,1,2]
 4 ^ 1 ^ 1 ^ 2 ^ 2
 4 0 0
 4
 */
class Solution {
    func singleNumber(_ nums: [Int]) -> Int {
        var result = 0
        
        for num in nums {
            result ^= num
            
            print(result)
        }
        
        return result
    }
}

70. 爬楼梯

class Solution {
    func climbStairs(_ n: Int) -> Int {
        if n < 3 {
            return n
        }
        
        var dp = [0,1,2]
         
        for i in 3...n {
            dp.append(dp[i-1] + dp[i-2]) 
        }
        
        return dp[n]
    }
}

66. 加一

class Solution {
    func plusOne(_ digits: [Int]) -> [Int] {
        
        var digits = digits
        
        var index = digits.count - 1
        
        while index >= 0 {
            if digits[index] == 9 {
                digits[index] = 0
                index = index - 1
            }else{
                digits[index] = digits[index] + 1
                return digits
            }
        }
        
        digits.insert(1, at: 0)
        
        return digits
        
    }
}

35. 搜索插入位置

class Solution {
    func searchInsert(_ nums: [Int], _ target: Int) -> Int {
        var left = 0
        var right = nums.count - 1
        
        var result = nums.count
        
        while left <= right {

            let mid = (right - left)/2 + left
            
            if nums[mid] == target {
                return mid
            }else if nums[mid] < target {
                left = mid + 1
            }else{
                right = mid - 1
                result = mid
            }
        }
        
        return result
    }
}

26. 删除有序数组中的重复项

class Solution {
    func removeDuplicates(_ nums: inout [Int]) -> Int{
        
        if nums.count < 2 {
            return nums.count
        }
        
        var i = 0
        var j = 1
        
        while j<nums.count {
            
            if nums[i] == nums[j] {
                j = j + 1
                while j<nums.count && nums[j] == nums[i] {
                    j = j + 1
                }
                if j<nums.count {
                    nums[i+1] = nums[j]
                    i = i + 1
                }
            }else{
                i = i + 1
                j = j + 1
            }
            
        }

        return i+1
    }
}

20. 有效的括号

class Solution {
    func isValid(_ s: String) -> Bool {

        var stack:[Character] = []
        for char in s {
            
            if let t_char = stack.last,let c_char = change(char: char),t_char == c_char{
                stack.removeLast()
            }else{
                stack.append(char)
            }
        }
        
        return  stack.count==0 ? true : false
        
    }
    
    func change(char:Character) -> Character? {
        switch char {
        case ")":
            return "("
        case "]":
            return "["
        case "}":
            return "{"
        default:
            return nil
        }
    }
}

15. 三数之和

class Solution {
    func threeSum(_ num: [Int]) -> [[Int]] {
        var result:[[Int]] = []
        
        var num = num
        num.sort()
        
        for (index,n) in num.enumerated() {
            
            if index>0 && num[index] == num[index - 1] {
                continue
            }
            
            var left = index + 1
            
            var right = num.count - 1
            
            while left < right {
                
                let sum = n + num[left] + num[right]
                
                if sum > 0 {
                    repeat {
                        right = right - 1
                    }while right > 0 && right < num.count && num[right] == num[right + 1]
                }else{
                    if sum == 0 {
                        result.append([n,num[left],num[right]])
                    }
                    repeat {
                        left = left + 1
                    }while left > 0 && left < num.count && num[left] == num[left - 1]
                }
                
            }
        }
        return result
    }
}

13. 罗马数字转整数

class Solution {
    func romanToInt(_ s: String) -> Int {

        var str = s.replacingOccurrences(of: "CM", with: "a")
        str = str.replacingOccurrences(of: "CD", with: "b")
        str = str.replacingOccurrences(of: "XC", with: "c")
        str = str.replacingOccurrences(of: "XL", with: "d")
        str = str.replacingOccurrences(of: "IX", with: "e")
        str = str.replacingOccurrences(of: "IV", with: "f")

        let charArr:[Character] = Array(str)

        var index = charArr.count - 1

        var result = 0

        while index >= 0  {
            result = result + getVaule(char: charArr[index])
            index = index - 1
        }
        return result;
    }

    func getVaule(char:Character) -> Int {
        switch char {
        case "M":
            return 1000
        case "a":
            return 900
        case "D":
            return 500
        case "b":
            return 400
        case "C":
            return 100
        case "c":
            return 90
        case "L":
            return 50
        case "d":
            return 40
        case "X":
            return 10
        case "e":
            return 9
        case "V":
            return 5
        case "f":
            return 4
        case "I":
            return 1
        default:
            return -1
        }
    }
}

12. 整数转罗马数字

class Solution {
    func intToRoman(_ num: Int) -> String {
 
        let numArr = [1000,900,500,400,100,90,50,40,10,9,5,4,1]
        let luomaArr = ["M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"]
        
        var result = ""
        
        var t_index = 0
        
        var t_num = num
        
        while t_index < numArr.count {
            
            for index in t_index...(numArr.count-1) {
                
                if t_num >= numArr[index] {
                    result = result + luomaArr[index]
                    t_num = t_num - numArr[index]
                    break
                }else{
                    t_index = t_index + 1
                }
            }
        }
        
        return result
    }
}

11. 盛最多水的容器

class Solution {
    func maxArea(_ height: [Int]) -> Int {
        
        guard height.count > 1 else {
            return height.first ?? 0
        }
        
        var left = 0
        var right = height.count
        
        var result = 0
        
        while left != right {
            let t_result = min(height[left], height[right-1]) * (right-left - 1)
            
            if height[left] < height[right-1] {
                left = left + 1
            }else{
                right = right - 1
            }
            
            if t_result > result{
                result = t_result
            }
        }
        
        return result
    }
}

9. 回文数

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

7. 整数反转

class Solution {
    func reverse(_ x: Int) -> Int {

        var x:Int32 = Int32(x)
        var rev:Int32 = 0
        
        while x != 0 {
            
            let pushInt = push(x)
            
            if (x > 0 && rev > (Int32.max - pushInt)/10) || (x < 0 && rev < (Int32.max * -1 - pushInt)/10)  {
                rev = 0
            }
            else{
                rev = rev * 10 + pushInt
            }
            
            x = pop(x)
        }
//
//        rev * 10 + pushInt > Int32.max * -1
        
        return Int(rev)
    }
    
    
    func pop(_ x:Int32) -> Int32 {
        return x/10
    }
    
    func push(_ x:Int32) -> Int32 {
        return x%10
    }
    
}

将有序数组[1,3,5,7,9]和[2,4,6,8,10]合并为一个[1,2,3,4,5,6,7,8,9,10]

class Solution {
    func orderListMerage(_ list:[Int],_ list2:[Int]) -> [Int] {
       
        var index1 = 0
        var index2 = 0
        
        var result:[Int] = []
        
        while index1 < list.count && index2 < list2.count {
            if list[index1] < list2[index2] {
                result.append(list[index1])
                index1 += 1
            }else if list[index1] > list2[index2] {
                result.append(list2[index2])
                index2 += 1
            }else{
                result.append(list[index1])
                index1 += 1
                result.append(list2[index2])
                index2 += 1
            }
        }
        
        while index1 < list.count{
            result.append(list[index1])
            index1 += 1
        }
        
        while index2 < list2.count{
            result.append(list2[index2])
            index2 += 1
        }
        
        
        return result
    }
}

6. Z 字形变换

class Solution {
    func convert(_ s: String, _ numRows: Int) -> String {
        
        guard numRows>1 else { return s }
        
        var rows:[[Character]] = []
        for _ in 0..<min(numRows, s.count) {
            rows.append([Character]())
        }
        
        var curRow = 0
        var down = false
        
        for (char) in s {
            rows[curRow].append(char)
            if (curRow == 0 || curRow == numRows - 1){
                down = !down
            }
            curRow = down ? curRow + 1 : curRow - 1
        }
        
        var result:[Character] = []
        for charArr in rows {
            for char in charArr {
                result.append(char)
            }
        }
        
        return String(result)
    }
}

5. 最长回文子串

class Solution {
    func longestPalindrome(_ s: String) -> String {

        guard s.count > 1 else {
            return s
        }

        var index = 0
        var left = 0
        var right = 1
        
        let arr = Array(s.utf8)

        while index<s.count {
            let len1 = findStr(s: arr, left: index, right: index)
            let len2 = findStr(s: arr, left: index, right: index+1)

            let len = max(len1, len2)

            if len > right - left {
                left = index-(len-1)/2
                right = left + len
            }
            index = index + 1
        }
        let index1 = s.index(s.startIndex, offsetBy: left)
        let index2 = s.index(s.startIndex, offsetBy: right)
        return String(s[index1..<index2])
    }

    //aaaaaa   index = 2 len 6 左移 2
    //aaaaa   index 2    len 5  左移2位
    //babbd
    //cbb
    //cbbd
    //babad
    func findStr(s:[String.UTF8View.Element], left: Int,right: Int) -> Int {
        var t_left = left
        var t_right = right
        while t_left>=0 ,t_right < s.count,s[t_left] == s[t_right] {
            t_left = t_left - 1
            t_right = t_right + 1
        }

        return t_right - t_left - 1
    }
}

4. 寻找两个正序数组的中位数

class Solution {
    func findMedianSortedArrays(_ nums1: [Int], _ nums2: [Int]) -> Double {
        
        var arr = nums1 + nums2
        
        arr.sort(by: >)
        
        let m = arr.count/2
        
        if arr.count%2 == 0 {
            return (Double(arr[m]) + Double(arr[m-1]))/2
        }else{
            return Double(arr[m])
        }
    }
}

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

class Solution {
    func lengthOfLongestSubstring(_ s: String) -> Int {
        
        guard s.count > 1 else {
            return s.count
        }
        
        var right = 1
        var left = 0
        var i = 0
        var result = 1
        
        let chars = Array(s.utf8)

        while right < chars.count {
            i = left
            while i < right {
                //用当前子串的最后一个，与前面每一个比较
                if chars[right] == chars[i]{
                    left = i + 1
                    break
                }
                i = i + 1
            }
            result = max(result,right-left+1)
            right = right + 1
        }
        
        return result
    }
}

2. 两数相加

public class ListNode {
    public var val: Int
    public var next: ListNode?
    public init() { self.val = 0; self.next = nil; }
    public init(_ val: Int) { self.val = val; self.next = nil; }
    public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
}

//输入：l1 = [2,4,3], l2 = [5,6,4]
//输出：[7,0,8]
//解释：342 + 465 = 807

class Solution {
    func addTwoNumbers(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
        
        let header:ListNode = ListNode()
        
        var t_nextNode:ListNode = header
        
        var t = 0
        
        var t_l1:ListNode? = l1
        var t_l2:ListNode? = l2
        
        while t_l1 != nil || t_l2 != nil {
            if let t_t_l1 = t_l1 {
                t = t + t_t_l1.val
                t_l1 = t_t_l1.next
            }
            if let t_t_l2 = t_l2 {
                t = t + t_t_l2.val
                t_l2 = t_t_l2.next
            }
    
            t_nextNode.next = ListNode(t%10)
            t_nextNode = t_nextNode.next!
            
            t = t/10
            
            //t = 1
            //8 ,9 ,9,9 0, 0,,
        }
        
        if t > 0 {
            t_nextNode.next = ListNode(t)
        }
        
        return header.next
    }
}

1. 两数之和

func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
    
    for (index,num) in nums.enumerated() {
        for (t_index,t_num) in nums.enumerated() {
            if index != t_index ,num + t_num == target{
                return [index,t_index]
            }
        }
    }
    
    return []
    
}

字符串翻转，给定字符串“hello,world”，实现将其翻转。输出结果："dlrow,olleh"

class Solution {
    func reverse(_ str:String) -> String {
        guard str.count > 1 else { return str }
        
        var left = 0
        var right = str.count - 1
        
        var arr:[Character] = Array(str)
        
        while left<right {
            let temp = arr[right]
            arr[right] = arr[left]
            arr[left] = temp
            left += 1;
            right -= 1;
        }
        
        return String(arr)
    }
}

Swift 算法刷题
目标一周刷2道题也不知道能坚持几天，这玩意在leetcode做完怎么保存啊给一个有序的数组，数组中有重复数字，输...
LeetCode题一两数之和
由于自己关于算法方面确实非常薄弱，所以尝试在LeetCode上刷题，所有代码均是基于swift实现。（LeetCo...
2020-02-01关于刷题的几个建议
算法刷题针对性刷题，刻意练习。刻意刷题！不是麻木刷题！刷题前一定要先看书，清楚明白为什么要刷这些题，这些题刷完能...
Best Time to Buy and Sell Stock
tags: 算法, LeetCode, swift, 动态规划这是最近在学算法中完成的第一个系列题，系列题...
刷算法题
入门级难度的几道题目简单乘法->斐波那契数列->链表->整数排序->二叉树一点一点过度, 让思维进入到刷题状态. ...
算法-刷题
Day1:爬楼梯[https://leetcode-cn.com/problems/climbing-stairs...
刷题算法
2/n叉树遍历迭代方法关键词+思路，背是背不住的(没掌握核心思路是复写不出来的!!!)： 2/n叉树前序：栈、反...
字节总监首发1121道LeetCode算法刷题笔记（含答案）
关于算法刷题的困惑和疑问也经常听朋友们提及。这份笔记里面共包含作者刷LeetCode算法题后整理的数百道题，每道题...
字节总监首发1121道LeetCode算法刷题笔记（含答案）
关于算法刷题的困惑和疑问也经常听朋友们提及。这份笔记里面共包含作者刷LeetCode算法题后整理的数百道题，每道题...
看完谷歌大佬的Leetcode刷题笔记，我直接手撕了200道Le
关于算法刷题的困惑和疑问也经常听朋友们提及。这份笔记里面共包含作者刷LeetCode算法题后整理的数百道题，每道题...

Swift 算法刷题

136. 只出现一次的数字

70. 爬楼梯

66. 加一

35. 搜索插入位置

26. 删除有序数组中的重复项

20. 有效的括号

15. 三数之和

13. 罗马数字转整数

12. 整数转罗马数字

11. 盛最多水的容器

9. 回文数

7. 整数反转

将有序数组[1,3,5,7,9]和[2,4,6,8,10]合并为一个[1,2,3,4,5,6,7,8,9,10]

6. Z 字形变换

5. 最长回文子串

4. 寻找两个正序数组的中位数

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

2. 两数相加

1. 两数之和

字符串翻转，给定字符串“hello,world”，实现将其翻转。输出结果："dlrow,olleh"

相关文章

Swift 算法刷题

LeetCode题一两数之和

2020-02-01关于刷题的几个建议

Best Time to Buy and Sell Stock

刷算法题

算法-刷题

刷题算法

字节总监首发1121道LeetCode算法刷题笔记（含答案）

字节总监首发1121道LeetCode算法刷题笔记（含答案）

看完谷歌大佬的Leetcode刷题笔记，我直接手撕了200道Le

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读