基礎算法：求目标值 &字元串反轉

第1題

給出一個整型數組和一個目标值，判斷數組中是否有2個數之和等于目标值，若有就傳回true，否則傳回false。

解法：

方案一：如果2層for循環暴力解題，O(n*n)不是我們想要的解法

方案二：采用集合可以優化時間複雜度，即在周遊數組的過程中，用集合每次儲存目前的值。假如集合中已經有了一個數等于目标值減去目前值，則證明在之前的周遊中一定有一個數與目前值之和等于目标值。這種方法的時間複雜度是O(n).

func twosums(target: Int, nums: [Int]) -> Bool {
        var set = Set<Int>()
        for num in nums {
            if set.contains(target - num) {
                return true
            }
            set.insert(num)// 如果沒找到，周遊數組的過程中，用集合每次儲存目前的值
        }
        return false
    }
           

第2題：【稍微變型下】

給定一個整型數組中有且僅有倆個數之和等于目标值，求這兩個數在數組中的序号。

解法：

解題思路與上道題類似，但是為了得到序号，這裡就使用字典。并且key是num，value是下标

func twosumsForIndex(target: Int, nums: [Int]) -> [Int] {
        var dict = [Int:Int]()
        for ( i, num ) in nums.enumerated() {
            if let lastIndex = dict[target - num] {
                return [ i, lastIndex ]
            }else {
                dict[num] = i //key是num，value是下标
            }
        }
        return []
    }
           

第3題：

給出一個字元串，要求按照單詞順序進行反轉

解法：

eg: 字元串"the sky is blue"，反轉後的結果是"blue is sky the"

這個題想想就能感受到，不好動手呀。但是有一個很巧妙的辦法：

1. 先反轉整個字元串，"the sky is blue"變成 "eulb si yks eht"

2. 每個單詞在獨立反轉，"eulb si yks eht"變成 "blue is sky the"

   代碼如下：

   2個輔助函數：

   // 輔助函數：作用是反轉
   func reverse<T>( chars: inout [T], start: Int, end: Int) {
       var start = start, end = end
       while start < end {
           swap(chars: &chars, p: start, q: end)
           start += 1
           end -= 1
       }
   }
   func swap<T>(chars: inout [T], p: Int, q: Int) {
       (chars[p], chars[q]) = (chars[q], chars[p])
   }
              

   下面是主要的算法：

   func reverseWords(s: String?) -> String? {
       guard let s = s else { return nil }
       var chars = Array(s)
       var start = 0 , end = s.count - 1
       reverse(chars: &chars, start: start, end: end)
       /**
        * 如果  chars[i+1] == " " ,說明是一個單詞到了可以進行反轉了 ，這裡的 i+1很巧妙，後續的 i+2 也是是以而來
        */
       for i in 0..<chars.count {
           if i == chars.count - 1 || chars[i+1] == " " {
               reverse(chars: &chars, start: start, end: i)
               start = i + 2 //很巧妙
           }
       }
       return String(chars)
   }
              

歡迎關注【無量測試之道】公衆号，回複【領取資源】

Python程式設計學習資源幹貨、

Python+Appium架構APP的UI自動化、

Python+Selenium架構Web的UI自動化、

Python+Unittest架構API自動化、

資源和代碼 免費送啦~

文章下方有公衆号二維碼，可直接微信掃一掃關注即可。

備注：我的個人公衆号已正式開通，緻力于測試技術的分享，包含：大資料測試、功能測試，測試開發，API接口自動化、測試運維、UI自動化測試等，微信搜尋公衆号：“無量測試之道”，或掃描下方二維碼：

 添加關注，讓我們一起共同成長！