TalkGo 算法之美第一期来啦!!!

TalkGo 算法之美第一期来啦!

活动简介

  1. 主要是以面试题为主,帮助大家了解面试题目
  2. 每次一个主题,周期一般是 1-2 周
  3. 小组内深度讨论,通过题解结识朋友

更详细的活动说明:https://github.com/talkgo/newspaper/blob/master/code_interview.md

活动形式

  1. 向负责人缴纳 50 元保证金即成功报名
  2. 一次未按时打卡,扣 30 元,二次将被全部扣掉
  3. 扣除的保证金作为奖励金分给组长和全勤同学

启动和打卡期

  1. 组长负责启动会(活动讲解、题目简述)
  2. 组员各自打卡,组长跟进小伙伴们的进度
  3. 每次打卡截止时间将会进行一次线上题解讨论会议(讲解解题思路,并对所有题解进行投票)
  4. 当期主题结束后组长要组织大家复盘,并输出一份总结

奖惩机制

惩罚:

  1. 一次未完成打卡,扣除保证金30元
  2. 两次未完成打卡,保证金全部扣除

奖励:

  1. 全勤打卡退还保证金
  2. 组长获得总奖金的 50%
  3. 全勤组员获得被剩余奖金

参与方式

添加微信: mai_yang 缴纳 50 元保证金即可参与,请备注:TalkGo 算法之美

报名截止时间

2020-09-06 00:00:00 UTC+8

本期组长

小林

个人介绍 :暨南大学计算研究生,研二在读, 研究生研究方向知识图谱,推荐算法,个人兴趣后台开发,个人技术博客林小默

本期题目

听说宇宙条的算法题很变态,那我们就来领略一下吧。

题目一

输入一个递增排序的数组和一个数字 S,在数组中查找两个数,使得他们的和正好是 S,如果有多对数字的和等于 S,输出两个数的乘积最小的。

题目二

一个有序数组,从随即一位截断,把前段放在后边,如 4 5 6 7 1 2 3 求中位数

注:希望成员能能够先独立完成题目

TalkGo 算法之美第一期题解

题目 - 和为 S 的两个数字

题目描述

输入一个递增排序的数组和一个数字S,在数组中查找两个数,使得他们的和正好是S,如果有多对数字的和等于S,输出两个数的乘积最小的。

可以用数学证明一个最小的数和最大的数的乘积是最小的

样例

案例 1:

输入: nums = {1, 2, 4, 7, 11, 15}, s = 15 
输出: {4, 11}

案例 2:

输入: nums = {1, 2, 4, 7, 11, 16}, s = 17 
输出: {1, 16}

案例 3:

输入: nums = {1, 2, 4, 7, 11, 16}, s = 10 
输出: {}

案例 4:

输入: nums = {1, 2, 4, 7, 8, 11, 15}, s = 10 
输出: {4, 11}
有4+11=15和7+8=15两组解,因为 4*11=44 < 7*8=56, 所以就题解是 {4, 11}

题解1:穷举

思路:2次循环穷举所有case

复杂度

  • 时间复杂度:O(N^2)
  • 可能复杂度:O(1)

Code

func Solution(nums []int, s int) []int {
	ans := []int{}
	for i := 0; i < len(nums); i++ {
		for j := len(nums) - 1; j > 0; j-- {
			if nums[i]+nums[j] == s {
				ans = append(ans, []int{nums[i], nums[j]}...)
				goto End
			}
		}
	}
End:
	return ans
}

题解2:hash map

思路:建立一个 key =nums[i], val = idx 的 map, 第二次2次循环匹配

复杂度

  • 时间复杂度:O(N)
  • 可能复杂度:O(N)

Code

func Solution(nums []int, s int) []int {
	m, ans := make(map[int]int), []int{}
	for i, num := range nums {
		m[num] = i
	}
	for _, num := range nums {
		if _, ok := m[s-num]; ok {
			ans = append(ans, []int{num, s - num}...)
			break
		}
	}
	return ans
}

题解3:双指针

思路:左右2个指针分别向中间收缩

复杂度

  • 时间复杂度:O(N^2)
  • 可能复杂度:O(1)

Code

func Solution(nums []int, s int) []int {
	left, right, ans := 0, len(nums)-1, []int{}
	for left < right {
		if nums[left]+nums[right] > s {
			right -= 1
		} else if nums[left]+nums[right] < s {
			left += 1
		} else {
			ans = append(ans, []int{nums[left], nums[right]}...)
			break
		}
	}
	return ans
}

题目 - 求中位数

题目描述

一个有序数组,从随机一位截断,把前段放在后边,如 4 5 6 7 1 2 3 求中位数

样例

案例 1:
输入 nums = {1, 2, 3, 7, 11, 15}
输出 5
{1, 2, 3, 4, 5, 6, 7} 从 4 开始折断 

案例 2:
输入 nums = {7, 11, 15, 1, 2, 3}
输出 5

案例 2:
输入 nums = {7, 11, 15, 1, 2, 3, 4}
输出 4


题解1:排序

思路:排序后直接计算

复杂度

  • 时间复杂度:时间复杂度:O (LogN)
  • 可能复杂度:O(N^2)

Code

func Solution(nums []int) int {
	sort.Ints(nums)
	n := len(nums)
	//	偶数
	if n%2 == 0 {
		return (nums[n/2] + nums[n/2-1]) / 2
	//	奇数
	} else {
		return nums[n/2]
	}
}

第一题,kylesliu 第三种方法是我能想到最优的方法了,代码就不贴了
第二题
充分利用有序数组经过一次折叠,也就是只有一个拐点,只要我们找到拐点的位置,中位数的位置就是可以计算的,那么问题就转化为,求拐点,计算中位数的位置
1、求拐点

// 计算拐点在哪,实现的还是比较啰嗦,主要还是考虑到有可能能存在相等的数
func InflectionPoint(nums []int) int {
    if len(nums) < 3 {
        return 0
    }

    prev, prevFlag := nums[0], -1
    for i, n := range nums {
        if i == 0 {
            continue
        }

        currentFlag := -1
        if n < prev {
            currentFlag = 1
        }else if n > prevFlag {
            currentFlag = 0
        }

        if prevFlag >= 0 && currentFlag >= 0 && currentFlag != prevFlag {
            return len(nums) - i
        }

        prev = n
        if currentFlag >= 0 {
            prevFlag = currentFlag
        }
        
    }

    return 0
}

2、计算中位数的位置

// 递增序的序号转化为带有拐点序列的位置:比如{6, 7, 1, 2, 3, 4, 5} 中位数 n = 7/2 = 3, i 拐点 为5 ,返回4, 为中位数的位置
// @n 有序序列的位置
// @i 拐点位置
// @l 数组长度
// 返回在具有拐点的数组中的位置
func RealPosition(n int, i int, l int) int {
    if n < i {
        return l - i + n
    }else {
        return n - i
    }
}

3、最终的求中位数的函数

func MiddleNumber(nums []int) int {
    // 对于长度小于等于2的数组直接返回结果
    if len(nums) == 0 {
        return 0
    } else if len(nums) == 1 {
        return nums[0]
    }else if len(nums) == 2 {
        return (nums[0] + nums[1]) / 2
    }

    // 计算拐点在哪
    inflectionPoint := InflectionPoint(nums)
    nlen := len(nums)
    if nlen % 2 == 0 {
        m0 := RealPosition(nlen/2, inflectionPoint, nlen)
        m1 := RealPosition(nlen/2 - 1, inflectionPoint, nlen)
        return (nums[m0] + nums[m1]) / 2
    }else {
        m := RealPosition(nlen/2, inflectionPoint, nlen)
        return nums[m]
    }
}

其实,从算法的可读性来说,先排序再找最简单,但是如果数组比较大,这种方式虽然啰嗦,但是效率相对较高,可读性不是很高
实际生产环境很难有这么写代码吧

题解:

代码地址:https://github.com/yangwenmai/talkgo-algorithms

题解一

通过 map 来检索加数,降低复杂度。

s001.go

package s001

// 输入一个递增排序的数组和一个数字 S,在数组中查找两个数,使得他们的和正好是 S,
// 如果有多对数字的和等于 S,输出两个数的乘积最小的。
func FindTwoSum(arr []int, s int) (int, int) {
        ret := map[int]int{}
        for i := 0; i < len(arr); i++ {
                ret[arr[i]] = i
        }
        mini, minj := len(arr)-1, len(arr)-1
        for i := 0; i < len(arr); i++ {
                interVal := s - arr[i]
                if j, ok := ret[interVal]; ok {
                        if arr[i]*arr[j] < arr[mini]*arr[minj] {
                                mini = i
                                minj = j
                        }
                }
        }
        return mini, minj
}

s001_test.go

package s001

import (
        "testing"

        "github.com/stretchr/testify/require"
)

func TestFindTwoSum(t *testing.T) {
        x1, x2 := FindTwoSum([]int{1, 3, 5, 7, 8, 10, 13}, 15)
        require.EqualValues(t, 2, x1)
        require.EqualValues(t, 5, x2)
        x1, x2 = FindTwoSum([]int{1, 2, 3, 7, 8, 10, 12}, 13)
        require.EqualValues(t, 0, x1)
        require.EqualValues(t, 6, x2)
        x1, x2 = FindTwoSum([]int{0, 2, 3, 10, 11, 44, 55, 66, 77}, 55)
        require.EqualValues(t, 0, x1)
        require.EqualValues(t, 6, x2)
}

题解二

原本已经有序,只需要找到随机截断的位置,即可拼接成一个有序数组,然后求中位数。

s002.go

package s002

import (
        "fmt"
)

// 一个有序数组,从随即一位截断,把前段放在后边,如 4 5 6 7 1 2 3 求中位数
func FindMiddleNumber(arr []int) int {
        newArr := sort(arr)
        if len(newArr)%2 == 0 {
                // 偶数
                return (newArr[len(newArr)/2-1] + newArr[len(newArr)/2]) / 2
        } else {
                return newArr[len(newArr)/2]
        }
}

func sort(arr []int) []int {
        newArr := []int{}
        for i := 0; i < len(arr); i++ {
                if arr[i] > arr[i+1] {
                        newArr = append(newArr, arr[i+1:]...)
                        newArr = append(newArr, arr[:i+1]...)
                        break
                }
        }
        return newArr
}

s002_test.go

package s002

import (
        "testing"

        "github.com/stretchr/testify/require"
)

func TestFindMiddle(t *testing.T) {
        arr := []int{7, 11, 15, 1, 2, 3}
        ret := FindMiddleNumber(arr)
        require.EqualValues(t, 5, ret)

        arr = []int{7, 11, 15, 1, 2, 3, 6}
        ret = FindMiddleNumber(arr)
        require.EqualValues(t, 6, ret)
}

过来看下题目 你们贴的答案怎么没有隐藏 :sweat_smile:

我看了一下好像不能隐藏帖子,我抽空看看有没有插件支持

ok, 如果可以隐藏那最好不过了

//x+y=s;xy=x(s-x)=xs-xx)=-(x-s/2)(x-s/2)+(s/2)*(s/2) 最小-->x-s/2最大
Q1:推荐指针解法!!!
时间/空间 O(n)

func Find(arr []int,s int )(int,int,error){
	var x,y int
	flag  :=false
	arrmap :=make(map[int]int)
	for i,v:=range arr{
		arrmap[v]=i
	}
	for _,v:=range arr{
		if _,ok:=arrmap[s-v];ok{
			flag=true
			x=v
			y=s-v
			break
		}
	}
	if !flag{
		return x,y,errors.New("not find")
	}
	return x,y,nil
}

Q2:
思路:本题理解为切割+平移,计算原中位数在平移后的位置
   缺点:加班写的,可能临界点与某些特殊场景没考虑全
时间O(n),空间O(1)
        func Median(arr []int)int{
        	arrlen:=len(arr)
        	if arrlen<1{
        		return 0
        	}
        	if arrlen==1{
        		return arr[0]
        	}
        	median:=0
        	arr0:=0 //找到a[0]现在的位置
        	for i:=0;i<arrlen-1;i++{
        		if arr[i]>arr[i+1]{
        			arr0=i+1
        			break
        		}
        	}
        	if arrlen%2==0{
        		middle1:=arr[MiddleIndex(arrlen,arrlen/2-1,arr0)]
        		middle2:=arr[MiddleIndex(arrlen,arrlen/2,arr0)]
        		median=(middle1+middle2)/2
        	}else {
        		middle:=arr[MiddleIndex(arrlen,arrlen/2,arr0)]
        		median= middle
        	}
        	return median
        }
func MiddleIndex(l,positon,arr0 int)int{
	index:=0 //中位数平移后的位置
	if positon>(l-1-arr0){
		index=positon-arr0
	}else {
		index=arr0+positon
	}
	return  index
}

// 输入一个递增排序的数组和一个数字S,在数组中查找两个数,使得他们的和正好是S,
// 如果有多对数字的和等于S,输出两个数的乘积最小的。

func sum(nums []int, s int) []int {
	m1 := make(map[int]int)
	res := []int{}
	for i, v := range nums {
		if _, ok := m1[s-v]; ok {
			res = append(res, []int{s - v, v}...) // 将满足条件的值写入数组中
		}
		m1[v] = i
	}
	return res[len(res)-2:] // 由于是有序数组, 最后面的2个数的乘积必定最小
}

func Test_sum(t *testing.T) {
	nums := []int{1, 2, 4, 7, 8, 11, 15}
	s := 15
	res := sum(nums, s)
	require.EqualValues(t, 4, res[0])
	require.EqualValues(t, 11, res[1])

	nums = []int{1, 2, 4, 7, 8, 11, 15}
	s = 12
	res = sum(nums, s)
	require.EqualValues(t, 1, res[0])
	require.EqualValues(t, 11, res[1])
}
// 4 5 6 7 1 2 3 求中位数
func resever(nums []int, s int) int {
	newnum := []int{}
	le := len(nums)
	if s > le {
		return 0
	}
	newnum = nums[s:]
	newnum = append(newnum, nums[:s]...)
	if len(newnum)%2 != 0 {
		return newnum[len(newnum)/2]
	} else {
		return (newnum[len(newnum)/2] + newnum[len(newnum)/2-1])/2
	}
}

func Test_resever(t *testing.T) {
	nums := []int{1, 2, 4, 7, 8, 11, 15}
	res := resever(nums, 3)
	require.EqualValues(t, 15, res)

	res = resever(nums, 4)
	require.EqualValues(t, 1, res)
}

TalkGo算法之美第一期题解

完整题解地址

题目1:和为 S 的两个数字

输入一个递增排序的数组和一个数字S,在数组中查找两个数,使得他们的和正好是S,如果有多对数字的和等于S,输出两个数的乘积最小的。

思路1:

由于给的数组是排好序的,而且求的是两个数的和,直接使用双指针即可。

func twoSum1(nums []int, s int) []int {
	max := math.MaxInt64
	var answer []int
	for head, tail := 0, len(nums)-1; head<tail; {
		if nums[head]+nums[tail] == s {
			if nums[head]*nums[tail] < max {
				max = nums[head]*nums[tail]
				answer = []int{nums[head], nums[tail]}
			}
			tail--
			head++
		} else if nums[head]+nums[tail] > s {
			tail--
		} else {
			head++
		}
	}
	return answer
}

思路2

根据测试思路1的题解答案可以大胆猜想找到的第一个解就是最优。当然也可以去证明,证明过程直接设几个未知数,然后求导即可,证明过程需要的话可以私聊。

func twoSum2(nums []int, s int) (answer []int) {
	for head, tail := 0, len(nums)-1; head<tail; {
		if nums[head]+nums[tail] == s {
			return []int{nums[head], nums[tail]}
		} else if nums[head]+nums[tail] > s {
			tail--
		} else {
			head++
		}
	}
	return
}

上述两个算法的时间复杂度均为O(N),空间复杂度为O(1)


题目2:旋转数组找中位数

一个有序数组,从随即一位截断,把前段放在后边,如 4 5 6 7 1 2 3 求中位数

思路

核心找到数组中最小数的位置,然后根据最小数的位置去寻找中位数。先判断数组是否被旋转,如果没有旋转,那么最小数就在下标为0处。如果数组被旋转了,那么就使用二叉查找的方法去寻找最小数下标。

题解

func findMedian(nums []int) float32 {
	n := len(nums)
	var minIndex int
	if nums[0] < nums[n-1] {
		minIndex = 0
	} else {
		minIndex = biSearch(nums)
	}
	if n % 2 == 1 {
		return float32(nums[(minIndex+n/2)%n])
	}
	x1 := float32(nums[(minIndex+n/2-1)%n])
	x2 := float32(nums[(minIndex+n/2)%n])
	return (x1 + x2) / 2
}

func biSearch(nums []int) (mid int) {
	low, mid, high := 0, len(nums)/2, len(nums)-1
	for nums[mid-1] < nums[mid] {
		if nums[mid] > nums[low] {
			low = mid
		} else {
			high = mid
		}
		mid = (high + low) / 2
	}
	return
}

时间复杂度为O(logN),空间复杂度为O(1)

题目1具体解法见: https://github.com/lixianliang/hello-go/blob/master/talkgo/algo01/minsum.go
题目2具体解法见: https://github.com/lixianliang/hello-go/blob/master/talkgo/algo01/mid.go

题目1:
方法1: 由于是有序数组,可以使用二分查找对应的组合,时间复杂度为:O(N*logN),空间复杂度为O(N)
方法2: 将有序数组值和索引组合成kv对存储到map中,利用map的快速查找对应的组合,时间复杂度为O(1), 空间复杂度大于O(N)

func FindMinSum2(arr []int, s int) (int, int, error) {
    if len(arr) < 2 {
        return 0, 0, fmt.Errorf("arr must > 2")
    }

    isFind := false
    a, b := 0, 0
    // 将数组value和index当作key value放入map中
    //arrMap := map[int]int{}
    arrMap := make(map[int]int, len(arr))
    for i, val := range arr {
        arrMap[val] = i
    }

    for _, val := range arr {
        x := s - val
        if _, ok := arrMap[x]; ok {
            if isFind {
                if val*x < a*b {
                    a = val
                    b = x
                }
            } else {
                isFind = true
                a = val
                b = x
            }
        }
    }

    if !isFind {
        return a, b, fmt.Errorf("arr not find")
    }

    return a, b, nil
}

题目2:
方法1: 将数组进行排序,然后计算中位数,时间复杂度为O(N*logN),空间复杂度为O(N)
方法2: 此数组被分割成连个有序数组,找到对应的分割点位置,按找方法1的思路找中位数,时间复杂度为O(N)

func FindMidNumber2(arr []int) int {
    // arr数组被分割成两段有序的数组,可以找到对应的临界点
    split := 0 // 分割索引默认为0
    for i := 0; i < len(arr)-1; i++ {
        if arr[i] > arr[i+1] {
            split = i + 1
            break
        }
    }

    n := len(arr)
    if n%2 == 1 {
        // 基数个数
        index := (n/2 + split) % n
        return arr[index]
    } else {
        // 偶数个数
        index1 := (n/2 - 1 + split) % n
        index2 := (n/2 + split) % n
        n1 := arr[index1]
        n2 := arr[index2]
        return (n1 + n2) / 2
    }
}