算法练习

2021 三月份

1. 两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。
示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：
输入：nums = [3,2,4], target = 6
输出：[1,2]

解答

class Solution {
    func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
        for (index1,value1) in nums.enumerated() {
            for (index2,value2) in nums.enumerated() {
                if value1 + value2 == target && index1 != index2{
                    return[index1,index2];
                }
            }
        }
        return [0];
    }
}

2. 搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

你可以假设数组中无重复元素。

示例 1:
输入: [1,3,5,6], 5
输出: 2

示例 2:
输入: [1,3,5,6], 2
输出: 1

解答

class Solution {
    func searchInsert(_ nums: [Int], _ target: Int) -> Int {
        for (index,value) in nums.enumerated() {
            if value >= target {
                return index
            }
        }
        return nums.count
    }
}

3.Nim 游戏

你和你的朋友，两个人一起玩 Nim 游戏：

• 桌子上有一堆石头。
• 你们轮流进行自己的回合，你作为先手。
• 每一回合，轮到的人拿掉 1 - 3 块石头。
• 拿掉最后一块石头的人就是获胜者。

假设你们每一步都是最优解。请编写一个函数，来判断你是否可以在给定石头数量为 n 的情况下赢得游戏。如果可以赢，返回 true；否则，返回 false 。

示例 1：
输入：n = 4
输出：false
解释：如果堆中有 4 块石头，那么你永远不会赢得比赛；
因为无论你拿走 1 块、2 块 还是 3 块石头，最后一块石头总是会被你的朋友拿走。

示例 2：
输入：n = 1
输出：true

解答

//巴什博奕
class Solution {
    func canWinNim(_ n: Int) -> Bool {
            return (n % 4 != 0 ) ? true : false ;
    }
}

4. 存在重复元素 II

给定一个整数数组和一个整数 k，判断数组中是否存在两个不同的索引* i* 和* j*，使得 nums [i] = nums [j]，并且 i 和 j 的差的 绝对值 至多为 k。

示例 1:

输入: nums = [1,2,3,1], k= 3
输出: true

示例 2:
输入: nums = [1,0,1,1], k=1
输出: true

解答

class Solution {
    func containsNearbyDuplicate(_ nums: [Int], _ k: Int) -> Bool {

        var dict: [Int: Int] = [:]
        for (index, item) in nums.enumerated() {
            if dict.keys.contains(item),
               let value = dict[item] {
                if (index - value) <= k {
                    return true
                } else {
                    dict[item] = index
                }
            } else {
                dict[item] = index
            }
        }
        return false
    }
}