airbnb刷题整理

class Solution
{
    func palindromePairs(_ input:[String]) -> [[Int]] {
        var result = [[Int]]()
        for i in 0..<(input.count-1) {
            for j in i+1..<input.count  {
                let strA = input[i] + input[j]
                let strB = input[j] + input[i]
                if isPalindrome(strA) {
                    result.append([i,j])
                }
                if isPalindrome(strB) {
                    result.append([j,i])
                }
            }
        }
        return result
    }
    func isPalindrome(_ input:String) -> Bool {
        for index in 0..<(input.count / 2) {
            let head = input.index(input.startIndex, offsetBy: index)
            let tail = input.index(input.startIndex, offsetBy:(input.count - 1 - index))
            if input[head] != input[tail] {
                return false
            }
        }
        return true
    }
}

class Solution
{
    func multiply(_ num1: String, _ num2: String) -> String {
        var isNagtive = false
        var num11 = num1
        var num22 = num2
        var ret = "0"
        if num1.hasPrefix("-") {
            isNagtive = true
            num11 = String(num1.suffix(num1.count - 1))
            if num2.hasPrefix("-") {
                isNagtive = false
                num22 = String(num2.suffix(num2.count-1))
            }
        } else if num2.hasPrefix("-") {
            isNagtive = true
            num22 = String(num2.suffix(num2.count-1))
        }
        let base = "0".unicodeScalars.first!.value
        for i in num11 {
            let rangeValue = i.unicodeScalars.first!.value - base
            for _ in 0..<rangeValue {
                ret = add(ret, num22)
            }
            ret.append("0")
        }
        print(ret)
        ret.remove(at: ret.index(before: ret.endIndex))
        if isNagtive == true {
            ret.insert("-", at: ret.startIndex)
        }
        
        return ret
    }
    
    //    func numFromString(_ input:String) ->(String, String) {
    //        let num1range = input.range(of :"num1 = ")
    //        let num2
    //    }
    
    func add(_ a:String, _ b:String) -> String {
        let base = "0".unicodeScalars.first?.value
        let minCount = a.count < b.count ? a.count : b.count
        var ret:String = ""
        var carry:UInt32 = 0
        for i in 0..<minCount
        {
            let va = a[a.index(a.startIndex, offsetBy:a.count-i-1)].unicodeScalars.first!.value - base!
            let vb = b[b.index(b.startIndex, offsetBy: (b.count-i-1))].unicodeScalars.first!.value - base!
            //            print("va = (va) vb = (vb) carry = (carry)")
            let (thisRound, thisCarry) = modAndCarry(va+vb+carry)
            //            print("thisround = (thisRound), thisCarry = (thisCarry)")
            ret.append(thisRound)
            carry = thisCarry
        }
        var maxString:String
        if a.count > b.count {
            maxString = a
        } else {
            maxString = b
        }
        for i in minCount..<maxString.count {
            let vc = maxString[maxString.index(maxString.startIndex, offsetBy: maxString.count - i - 1)].unicodeScalars.first!.value - base!
            let (thisRound, thisCarry) = modAndCarry(vc+carry)
            //            print("thisround = (thisRound), thisCarry = (thisCarry)")
            ret.append(thisRound)
            carry = thisCarry
        }
        if carry != 0 {
            ret.append(String(carry))
        }
        return String(ret.reversed())
    }
    func modAndCarry(_ input:UInt32) -> (String, UInt32) {
        let last = input % 10
        let carry = (input - last) / 10
        return (String(last), carry)
    }
    func string2num(_ input:String) -> Int64 {
        var ret:Int64 =  0
        for item in input.unicodeScalars {
            ret = ret * 10 + Int64(item.value - 97)
        }
        return ret
    }
}

class Solution {
    var solution:[[Int]] = [[Int]]()
    func combinationSum2(_ candidates: [Int], _ target: Int) -> [[Int]] {
         var sortedMenu = candidates
        sortedMenu.sort()
        search(sortedMenu, sortedMenu.count, target, 0, [Int](),0)
        return solution
    }
    func search(_ menu:[Int],_ count:Int, _ target:Int, _ current:Int, _ list:[Int], _ currentIndex:Int) {
        if current == target {
            solution.append(list)
            return
        }
        var currentList = list
        for i in currentIndex..<count {
            if i > currentIndex && menu[i-1] == menu[i] {
                continue
            }
            if current + menu[i] <= target {
                currentList.append(menu[i])
                search(menu, count, target, current+menu[i], currentList, i+1)
                currentList.removeLast()
            }
        }
    }
}

class Solution {
    func fullJustify(_ words: [String], _ maxWidth: Int) -> [String] {
        var list = [String]()
        var ret = [String]()
        var count = 0
        for word in words {
            count += word.count
            if count <= maxWidth {
                list.append(word)
                count += 1
            } else {
                ret.append(makeMiddleLine(list, maxWidth))
                list.removeAll()
                count = word.count + 1
                list.append(word)
            }
        }
        ret.append(makeLastLine(list, maxWidth))
        return ret
    }
    
    func makeMiddleLine(_ words: [String], _ maxWidth: Int) -> String {
        var ret = ""
        let wordCount = words.map({$0.count}).reduce(0, +)
        var space = maxWidth - wordCount
        if words.count == 1 {
            ret.append(words.first!)
            let spaceString = String.init(repeating:" ", count: space)
            ret.append(spaceString)
        } else {
            let commonMargin = Int(space / (words.count-1))
            var extraMarginCount = space % (words.count-1)
            let commonSpace = String.init(repeating:" ", count: commonMargin)
            let extraSpace = String.init(repeating:" ", count:commonMargin+1)
            var count = 0
            for word in words {
                ret.append(word)
                if count == words.count - 1 {
                    continue
                } 
                if count < extraMarginCount {
                    ret.append(extraSpace)
                } else {
                    ret.append(commonSpace)
                }
                count += 1
            }
        }
        
        return ret
    }
    func makeLastLine(_ words: [String], _ maxWidth: Int) -> String {
        var ret = ""
        for word in words {
            ret.append(word)
            if ret.count < maxWidth {
                ret.append(" ")
            }
        }
        
        let lastString = String.init(repeating:" ", count:maxWidth-ret.count)
        ret.append(lastString)
        return ret
    }
}

class Solution {
    func run(_ heights:[Int], _ Value:Int, _ K:Int) -> [Int] {
        var ret = [Int](repeating: 0, count: heights.count)
        var temp = heights
        var sortedIndex = sortByValue(heights)
        for v in 0..<Value {
            if temp[K] == sortedIndex[0].0 {
                temp[K] += 1
                ret[K] += 1
            } else {
                let index = sortedIndex[0].1
                temp[index] += 1
                ret[index] += 1
            }
            sortedIndex = sortByValue(temp)
        }
        descirptionWalle(heights, ret)
        
        return ret
    }
    func sortByValue(_ heights:[Int]) -> [(Int, Int)] {
        var ret = [(Int, Int)]()
        var index = 0
        for value in heights {
            ret.append((value, index))
            index += 1
        }
        ret.sort { (a, b) -> Bool in
            return a.0 < b.0
        }
        return ret
        
    }
    func descirptionWalle(_ heights:[Int], _ waters:[Int]) {
        let height = heights.enumerated().map { (index, element) -> Int in
            return element+waters[index]
        }.max()!
        for h in (0..<height).reversed() {
            var count = 0
            for i in heights {
                if i + waters[count] >= h + 1 && i <= h{
                    print("W", terminator:"")
                } else if i >= h + 1 {
                    print("#", terminator:"")
                } else {
                    print(" ", terminator:"")
                }
                count += 1
            }
            print("")
        }
    }
}

let s = Solution.init().run([2,1,1,2,1,2,2], 4, 3)

func forceSearch(_ puzzle:[[Int]]) {
    if isFound(puzzle) {
        minResult = 0
        return
    }
    queue.append(puzzle)
    markedMap[sequenceArray(puzzle)!] = 0
    while queue.count > 0 {
        let temp = queue[0]
        queue.remove(at: 0)
        for round in 0..<4 {
            let (movedPuzzle, success) = move(temp, round)
            if markedMap[sequenceArray(movedPuzzle)!] != nil {
                continue
            }
            if (success) {
                if isFound(movedPuzzle) {
                    minResult = markedMap[sequenceArray(temp)!]! + 1;
                    return
                }
                queue.append(movedPuzzle)
                markedMap[sequenceArray(movedPuzzle)!] = markedMap[sequenceArray(temp)!]! + 1;
            }
        }
    }
}

func move(_ puzzle:[[Int]], _ direction:Int) -> ([[Int]],Bool) {
    //left:0, right:1, top:2, bottom:3
    let zeroIndex = foundZero(puzzle)
    let zeroX = zeroIndex[0]
    let zeroY = zeroIndex[1]
    var targetX = 0
    var targetY = 0
    var puzzleCopy = puzzle
    if direction == 0 {
        if zeroY == 0 {
            return (puzzle, false)
        }
        targetX = zeroX
        targetY = zeroY - 1
        
    } else if direction == 1 {
        if zeroY == puzzle.first!.count - 1 {
            return (puzzle, false)
        }
        targetX = zeroX
        targetY = zeroY + 1
        
    } else if direction == 2 {
        if zeroX == 0 {
            return (puzzle, false)
        }
        targetX = zeroX - 1
        targetY = zeroY
        
    } else {
        if zeroX == puzzle.count - 1 {
            return (puzzle, false)
        }
        targetX = zeroX + 1
        targetY = zeroY
    }
    puzzleCopy[zeroX][zeroY] = puzzleCopy[targetX][targetY]
    puzzleCopy[targetX][targetY] = 0
    return (puzzleCopy, true)
    
}
func foundZero(_ puzzle:[[Int]]) -> [Int] {
    var ret = [Int]()
    var i = 0
    var j = 0
    var recordI = 0
    var recordJ = 0
    for row in puzzle {
        j = 0
        for item in row {
            if item == 0
            {
                recordI = i
                recordJ = j
            }
            j += 1
        }
        i += 1
    }
    ret.append(recordI)
    ret.append(recordJ)
    return ret
}

func sequenceArray(_ puzzle:[[Int]]) -> Int? {
    var retStr = ""
    for row in puzzle {
        for item in row {
            retStr.append(String(item))
        }
    }
    return Int(retStr)
}
func isFound(_ puzzle:[[Int]]) -> Bool {
    if finalPuzzle.count == 0
    {
        var index = 1
        var rowNum = 1
        for row in puzzle {
            if rowNum == puzzle.count {
                var tempArray = Array(index...index+row.count-2)
                tempArray.append(0)
                finalPuzzle.append(tempArray)
            } else {
                finalPuzzle.append(Array(index...index+row.count-1))
            }
            
            index += row.count
            rowNum += 1
        }
    }
    return puzzle.elementsEqual(finalPuzzle)
}