leetcode_二进制合集

December 25, 2019 5 minutes read

面试 • 算法 • 数据结构

371. 两整数之和

题目

不使用运算符 + 和 - ，计算两整数 a 、b 之和。

示例 1:
输入: a = 1, b = 2
输出: 3
示例 2:
输入: a = -2, b = 3
输出: 1
来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/sum-of-two-integers 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解答

两个整数a, b; a ^ b是无进位的相加； a&b得到每一位的进位；让无进位相加的结果与进位不断的异或，直到进位为0；

思路写在代码中

func getSum(a int, b int) int {
    var sum, carry int 		// 结果 和 进位
    
    sum = a ^ b 			// 不进位加法 0101 ^ 0011 = 0110
    carry = (a&b) << 1 		// 获取进位(全一则一，左移表示进位) 0101&0011 = 0001
    // 还有进位没加进去，递归做加法
    if carry != 0 {
        return getSum(sum, carry)
    }
    return sum
}


// 简写
func getSum(a int, b int) int {
    if b == 0 {
        return a
    }
    
    return getSum(a^b, (a&b)<<1)
}

136. 只出现一次的数字 I

题目

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明：

你的算法应该具有线性时间复杂度。你可以不使用额外空间来实现吗？
示例 1:
输入: [2,2,1]
输出: 1

示例 2:
输入: [4,1,2,1,2]
输出: 4
来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/single-number

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解答一：map统计再遍历

func singleNumber(nums []int) int {
    if len (nums) == 1 {
        return nums[0]
    }

    m := make(map[int]int, len(nums))
    for _, v := range nums {
        m[v]+=1
    }

    for k, v := range m {
        if v == 1 {
            return k
        }
    }
    return 0
}

// 执行用时 :12 ms, 在所有 Go 提交中击败了80.86%的用户
// 内存消耗 :5.9 MB, 在所有 Go 提交中击败了7.72%的用户

解答二：二进制

思路：

数字和自己异或^，结果为0
数字和0异或^，还是为这个数字

func singleNumber(nums []int) int {
    if len(nums) == 1 {
        return nums[0]
    }

    var ret int
    for _, v := range nums {
        ret^=v
    }
    return ret
}
// 执行用时 :8 ms, 在所有 Go 提交中击败了98.44%的用户
// 内存消耗 :4.7 MB, 在所有 Go 提交中击败了100.00%的用户

二进制特性

数字和自己本身异或为 0
- （^ 相同为 0，不同为 1，不进位）
- （& 相同为 1 不同为 0，不进位）
0 和任何数字异或为这个数字

137. 只出现一次的数字 II

题目

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。

说明：你的算法应该具有线性时间复杂度。你可以不使用额外空间来实现吗？

示例 1:
输入: [2,2,3,2]
输出: 3
示例 2:
输入: [0,1,0,1,0,1,99]
输出: 99
来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/single-number-ii 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解答

解法一

使用map，时间和空间复杂度都为O(n)

func singleNumber(nums []int) int {
    sub := make(map[int]int, len(nums))
    
    for _, v := range nums {
        sub[v]++
    }
    
    for k, v := range sub {
        if v == 1 {
            return k
        }
    }
    return -1
}
// 执行用时 :8 ms, 在所有 Go 提交中击败了51.79%的用户
// 内存消耗 :4.3 MB, 在所有 Go 提交中击败了42.86%的用户

解法二

数学运算 3×(a+b+c)−(a+a+a+b+b+b+c)=2c

					 sum
1 1 1 2 3 3 3		 14
1 1 1 2 2 2 3 3 3	 18	
2 2   4/2=2			 18-14=4

解答

func singleNumber(nums []int) int {
    // golang 没有无重复集合set，这里用map代替
    sub := make(map[int]int, len(nums))
    var sum, dep int
    for _, v := range nums {
        // 只加一次
        if sub[v] == 2 {
            dep += v
        } else {
            sub[v]++
        }
        sum += v
    }
   	return sum - dep*3
}
// 执行用时 :8 ms, 在所有 Go 提交中击败了51.79%的用户
// 内存消耗 :4.3 MB, 在所有 Go 提交中击败了42.86%的用户

解法三

评论大神的解法暂时没怎么理解，后面再补充

解答

func SingleNumber2(nums []int) int {
    a,b := 0,0
    for _,v := range nums {
        a = (a^v) & ^b
        b = (b^v) & ^a
    }
    return a
}

解法四

依然是二进制

参考上一题：a ^ a ^ b = b 。

我们假想一种运算 ∆ 可以使得 a ^ a ^ a = 0，且 b ^ 0 = b

1 0 0	a
1 0 0	a
1 0 1	b
1 0 0	a
------
1 0 1	res

从每一位开始分析，需要进行运算之后，把多余的 1 返还给结果

这里就是用到每一位逐次 & （相同为1），然后对 3 取模

比如 1 + 1 + 1 = 3
再对多出来的 3+1 = 4
4 % 3 = 1 ，归还给结果

大部分编程语言默认int的长度为 4字节，即 4 x 8bit = 32位

逐次右移动，计算每一位，然后归还给res，直到32位结束

func SingleNumber2(nums []int) int {
    if len(nums) == 1 {
        return nums[0]
    }
   	var res int
    // 逐次右移
    for i := 0; i < 32; i++ {
        var sum int
        for _, v := range nums {
            // 101 101 110 101 -> 001 001 001 001 -> 
            sum += (v >> i) & 1
            sum %= 3
        }
        // 返还
        res = res | sum(res << 1)
    }
}

260. 只出现一次的数字 III

题目

给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。找出只出现一次的那两个元素。
示例 :

输入: [1,2,1,3,2,5]
输出: [3,5]
注意：

结果输出的顺序并不重要，对于上面的例子， [5, 3] 也是正确答案。你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现？

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/single-number-iii 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

用map统计的方法就不再重复了，比较无脑，空间不可能是常数

还是利用二进制特性：

数字和自己异或^，结果为0
数字和0异或^，还是为这个数字

所以

先将所有数字异或可以得到：这两个数字异或的结果
再从低往高找差异位，再进行分组

组内进行异或，可以找到两个数

1,  1,  2,  2,  3,  4,  5,  5
001,001,010,010,011,100,101,101
逐次异或：
001,001,010,000,011,111,010,111
  
末位为1的分组：
001,001,101,101,011 -> 3(011)
末位为0的分组：
010,010,100         -> 4(100)

全部异或得到：111，最低位为第 1（即两个数从此出现差异）。
3 和 4 分别最低位为 1 和 0，正好分到了 xx1 和 xx0 两个组
分组，组内分别再异或即可得到 3 和 4。

解答

func singleNumber(nums []int) []int {
    // 得到两个数异或后的结果
    var bt int
    for _, v := range nums {
        bt ^= v
    }
    var (
        ret1, ret2 int // 两个结果
        index = findFirst1(bt)  // 两个结果的最低差异位
    )
    for _, v := range nums {
        // 按照差异位分组，组内异或便能得到对应结果
        if (v>>index)&1 == 1 {
            ret1 ^= v
        } else {
            ret2 ^= v
        }
    }
    return []int{ret1, ret2}
}

// 为1的最低位（两个数字异或，不同的位为1）
func findFirst1(n int) int {
    var index int
    // 在int32范围内 && 最低位不为1
    for index < 32 && (n&1) == 0 {
        n>>=1
        index++
    }
    return index
}


// 执行用时 :8 ms, 在所有 Go 提交中击败了76.67%的用户
// 内存消耗 :4.2 MB, 在所有 Go 提交中击败了65.22%的用户

Golang实现SET

package main

import (
	"fmt"
	"sort"
	"sync"
)

type Set struct {
	m map[int]bool
	sync.RWMutex
}

func New() *Set {
	return &Set{
		m: map[int]bool{},
	}
}

func (s *Set) Add(item int) {
	s.Lock()
	defer s.Unlock()
	s.m[item] = true
}

func (s *Set) Remove(item int) {
	s.Lock()
	defer s.Unlock()
	delete(s.m, item)
}

func (s *Set) Has(item int) bool {
	s.RLock()
	defer s.RUnlock()
	_, ok := s.m[item]
	return ok
}

func (s *Set) Len() int {
	return len(s.List())
}

func (s *Set) Clear() {
	s.Lock()
	defer s.Unlock()
	s.m = map[int]bool{}
}

func (s *Set) IsEmpty() bool {
	if s.Len() == 0 {
		return true
	}
	return false
}

func (s *Set) List() []int {
	s.RLock()
	defer s.RUnlock()
	list := []int{}
	for item := range s.m {
		list = append(list, item)
	}
	return list
}

func (s *Set) SortList() []int {
	s.RLock()
	defer s.RUnlock()
	list := []int{}
	for item := range s.m {
		list = append(list, item)
	}
	sort.Ints(list)
	return list
}

func main() {
	//初始化
	s := New()

	s.Add(1)
	s.Add(1)
	s.Add(0)
	s.Add(2)
	s.Add(4)
	s.Add(3)

	s.Clear()
	if s.IsEmpty() {
		fmt.Println("0 item")
	}

	s.Add(1)
	s.Add(2)
	s.Add(3)

	if s.Has(2) {
		fmt.Println("2 does exist")
	}

	s.Remove(2)
	s.Remove(3)
	fmt.Println("无序的切片", s.List())
	fmt.Println("有序的切片", s.SortList())

}