Dawn's Blogs

分享技术 记录成长

0%

算法刷题笔记 (13) 多数元素 在排序数组中查找元素的第一个和最后一个位置 只出现一次的数字 比较版本号 对称二叉树

发表于 更新于 分类于

多数元素

多数元素

解题思路

  1. 以空间换时间，用哈希表来记录元素出现的次数
  2. 摩尔投票法，因为多数元素是指出现次数大于一半的元素，因此多数元素的个数 - 其他元素的个数 >= 1，相当于每个多数元素和其他元素两两抵消，最后至少剩余一个多数元素

解题代码

  1. 空间换时间
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func majorityElement(nums []int) int {
    hashMap := make(map[int]int)    // 哈希表记录元素出现次数
    n := len(nums)  // 元素个数
    var majElem int    // 多数元素

    for i := 0; i < n; i++ {
        if _, ok := hashMap[nums[i]]; !ok {
            // 第一次出现，记录在哈希表中
            hashMap[nums[i]] = 1
        } else {
            // 不是第一次出现，增加出现次数
            hashMap[nums[i]]++
        }
        if hashMap[nums[i]] > n/2 {
            // 出现次数多于一半
            majElem = nums[i]
            break
        }
    }

    return majElem
}
  1. 摩尔投票法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func majorityElement(nums []int) int {
    var canditate int   // 候选人
    var count int

    for i := 0; i < len(nums); i++ {
        if count == 0 {
            // 确定新的候选人
            canditate = nums[i]
        }
        if canditate == nums[i] {
            count++
        } else {
            count--
        }
    }

    return canditate
}

在排序数组中查找元素的第一个和最后一个位置

在排序数组中查找元素的第一个和最后一个位置

解题思路

利用二分查找，分别找到目标元素的左侧边界和右侧边界

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
func searchRange(nums []int, target int) []int {
    return []int{left(nums, target), right(nums, target)}
}

func left(nums []int, target int) int {     // 找到目标元素的左侧边界
    low, high := 0, len(nums)-1
    var mid int
    for low <= high {
        mid = (low+high)/2
        if target <= nums[mid] {
            high = mid - 1
        } else {
            low = mid + 1
        }
    }

    if low >= len(nums) || nums[low] != target {
        return -1
    }

    return low
}

func right(nums []int, target int) int {    // 找到目标元素的右侧边界
    low, high := 0, len(nums)-1
    var mid int
    for low <= high {
        mid = (low+high)/2
        if target >= nums[mid] {
            low = mid + 1
        } else {
            high = mid - 1
        }
    }
    
    if high < 0 || nums[high] != target {
        return -1
    }

    return high
}

只出现一次的数字

只出现一次的数字

解题思路

  1. 首先想到用哈希表记录元素出现的次数，但是空间复杂度达到O(n)
  2. 暴力破解，每次从数组中取出一个数，从剩下的数中查找，如果找不到，那么这个数字就是只出现一次的数字。时间复杂度达O(n^2)
  3. 先排序，时间复杂度达O(nlogn)
  4. 位运算，假设数组中有2m+1个数字，其中a[1], a[2], a[3], ..., a[m]均出现了2次，a[m+1]只出现了一次。那么数组中的所有元素异或之后可以写成(a[1]⊕a[1])⊕(a[2]⊕a[2])⊕...⊕(a[m]⊕a[m])⊕a[m+1]，即可以得到0⊕0⊕...⊕0⊕a[m+1]=a[m+1]

解题代码

位运算

1
2
3
4
5
6
7
8
9
func singleNumber(nums []int) int {
    var res int // 结果

    for _, num := range nums {
        res = res ^ num
    }

    return res
}

比较版本号

比较版本号

解题思路

双指针法，两个指针i和j分别指向version1和version2的下标，分割修订号并且转化为数字，对两个版本的修订号进行比较

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
func compareVersion(version1 string, version2 string) int {
    len1, len2 := len(version1), len(version2)
    var i, j int    // i为version1的下标，j为version2的下标
    
    for i < len1 || j < len2 {
        num1 := 0   // version1的修订号
        for ; i < len1 && version1[i] != '.'; i++ {    // 将字符串转为数字
            num1 = num1*10 + int(version1[i]-'0')
        }
        i++     // 跳过点号

        num2 := 0   // version2的修订号
        for ; j < len2 && version2[j] != '.'; j++ {    // 将字符串转为数字
            num2 = num2*10 + int(version2[j]-'0')
        }
        j++     // 跳过点号

        if num1 > num2 {
            return 1
        } else if num1 < num2 {
            return -1
        }
    }

    return 0
}

对称二叉树

对称二叉树

解题思路

  1. 递归法，基于二叉树的深度优先遍历。将根节点的左子树记为left，右子树记为right，比较left和right是否相等。若相等则继续进行比较，比较left的左子树和right的右子树、left的右子树和right的左子树是否相等
  2. 迭代法，使用队列。首先从队列中拿出两个节点left和right进行比较。将left的左子树和right的右子树放入队列；将left的右子树和right的左子树放入队列

解题代码

  1. 深度优先遍历，递归法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isSymmetric(root *TreeNode) bool {
    return dfs(root.Left, root.Right)
}

func dfs(left, right *TreeNode) bool {
    if left == nil && right == nil {
        // left和right都为空
        return true
    }
    if left == nil || right == nil {
        // left和right有一个不为空
        return false
    }
    if left.Val != right.Val {
        // 值不相等
        return false
    }
    // left和right相等，继续向下比较
    return dfs(left.Left, right.Right) && dfs(left.Right, right.Left)
}
  1. 迭代法，使用队列
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isSymmetric(root *TreeNode) bool {
    if root == nil {
        return true
    }
    queue := make([]*TreeNode, 0)  // 队列
    queue = append(queue, root.Left)    // 根的左子树入队
    queue = append(queue, root.Right)   // 根的右子树入队

    for len(queue) > 0 {
        // 左右树出队
        left := queue[0]
        right := queue[1]
        queue = queue[2:]
        if left == nil && right == nil {
            continue
        }
        if left == nil || right == nil {
            return false
        }
        if left.Val != right.Val {
            return false
        }
        // 左树的左子树、右树的右子树入队
        queue = append(queue, left.Left)
        queue = append(queue, right.Right)
        // 左树的右子树、右树的左子树入队
        queue = append(queue, left.Right)
        queue = append(queue, right.Left)
    }

    return true
}