最接近的三数之和

解题思路

首先对数组进行排序，接着遍历数组，用两个指针分别记录nums[i]之后的左右边界，令sum = nums[i]+nums[left]+nums[right]：

若sum<target，说明三数之和过小，left++
若sum>target，说明三数之和过大，right--

解题代码

func threeSumClosest(nums []int, target int) int {
    // 排序
    sort.Ints(nums)
    // 记录最接近的三叔之和
    closestSum := nums[0]+nums[1]+nums[len(nums)-1]  
    // 遍历数组
    for i := 0; i < len(nums); i++ {
        // 左右指针
        left, right := i+1, len(nums)-1
        for left < right {
            sum := nums[i]+nums[left]+nums[right]   // 三数之和
            if sum == target {
                return target
            } else {
                if abs(target-sum) < abs(target-closestSum) {
                    closestSum = sum
                }
                if sum < target {
                    // 左指针向右移动
                    left++
                } else {
                    // 右指针向左移动
                    right--
                }
            }
        }
    }

    return closestSum
}

func abs(n int) int {
    if n > 0 {
        return n
    }
    return -n
}

位1的个数

解题思路

进行32次移位，循环检查给定整数n的二进制位的每一位是否为1
n & (n−1)，其运算结果恰为把n的二进制位中的最低位的1变为0的结果。不断让当前的n与n-1做与运算，直到n变为0即可。因为每次运算会使得n的的最低位的1被翻转，因此运算次数就等于n的二进制1的个数。

解题代码

32次移位

func hammingWeight(num uint32) int {
    count := 0      // 记录1的个数
    for i := 0; i <= 32; i++ {
        if num>>i & 1 == 1 {
            count++
        }
    }

    return count
}

n & (n−1)运算

func hammingWeight(num uint32) int {
    count := 0      // 记录1的个数
    for num != 0 {
        num = num & (num-1)
        count++
    }

    return count
}

打家劫舍 II

解题思路

利用动态规划的思路，定义一维dp数组，dp[i]表示偷i间房子的最大金额。

初始化：没有房子dp[0] = 0
状态转移方程：dp[i] = max(dp[i-1], dp[i-2]+nums[i-1])，dp[i]有两种选择，不偷第i-1间房子（dp[i-1]）或者偷第i-1间房子（dp[i-2]+nums[i-1]）。

遍历两次数组，第一次不偷第一间房屋，第二次不偷最后一间房屋，取两次的最大金额即可。需要注意的是nums长度为1时，需要特殊处理，直接返回nums[0]。

解题代码

func rob(nums []int) int {
    if len(nums) == 1 {
        return nums[0]
    }
    // 记录最大金额
    res := 0
    // 定义dp数组
    dp := make([]int, len(nums)+1)
    dp[0] = 0

    // 第一次遍历，不偷第一个房屋
    dp[1] = 0
    for i := 2; i <= len(nums); i++ {
        dp[i] = max(dp[i-1], dp[i-2]+nums[i-1])
    }
    res = dp[len(nums)]

    // 第二次遍历，不偷最后一个房屋
    dp[1] = nums[0]
    for i := 2; i < len(nums); i++ {
        dp[i] = max(dp[i-1], dp[i-2]+nums[i-1])
    }
    res = max(res, dp[len(nums)-1])

    return res
}

func max(n1, n2 int) int {
    if n1 > n2 {
        return n1
    }
    return n2
}

反转字符串中的单词 III

解题思路

从前向后遍历字符串，记录上一个空格的位置（第一个单词之前的看作-1）、当前空格的位置（最后一个单词之后的看作len(s)），反转上一个空格和当前空格之间的单词。

解题代码

func reverseWords(s string) string {
    pre, cur := -1, 0    // 记录上一个空格、当前空格的位置
    slice := []byte(s)   // 转为字节切片
    for cur <= len(slice) {
        if cur == len(slice) || slice[cur] == ' ' {
            // 遇到空格或者遇到最后一个单词，反转单词
            left, right := pre+1, cur-1
            for left < right {
                slice[left], slice[right] = slice[right], slice[left]
                left++
                right--
            }
            pre = cur
        }
        cur++
    }

    return string(slice)
}

在排序数组中查找数字 I

解题思路

基于二分查找，找到最靠前的target位置。

解题代码

func search(nums []int, target int) int {
    // 二分查找
    left, right := 0, len(nums)-1
    for left < right {
        mid := (left+right)/2
        if nums[mid] < target {
            left = mid+1
        } else {
            right = mid
        }
    }

    count := 0      // 记录出现的次数
    for i := left; i < len(nums) && nums[i] == target; i++ {
        count++
    }

    return count
}

有效的字母异位词

解题思路

若字符串s和t的长度不相同，肯定不是字母异位词。若长度相同，利用哈希表，记录字符串s中各个字符出现的次数；遍历t，令hashMap[t[i]]--，若出现hashMap[t[i]]小于0，则t中存在s没有的字符

解题代码

func isAnagram(s string, t string) bool {
    if len(s) != len(t) {
        // s和t长度不相等，肯定不是
        return false
    }
    hashMap := make(map[byte]int, 26)
    // 遍历s记录每个字符出现的次数
    for i := 0; i < len(s); i++ {
        hashMap[s[i]]++
    }
    // 遍历t，hashMap[t[i]]--;若出现hashMap[t[i]]小于0，则t中存在s没有的字符
    for i := 0; i < len(t); i++ {
        hashMap[t[i]]--
        if hashMap[t[i]] < 0 {
            return false
        }
    }

    return true
}

Dawn's Blogs

算法刷题笔记 (30) 最接近的三数之和位1的个数打家劫舍II 在排序数组中查找数字I 有效的字母异位词

最接近的三数之和

解题思路

解题代码

位1的个数

解题思路

解题代码

打家劫舍 II

解题思路

解题代码

反转字符串中的单词 III

解题思路

解题代码

在排序数组中查找数字 I

解题思路

解题代码

有效的字母异位词

解题思路

解题代码