Leetcode 每日一题 数组相关

[hankviv]

[hankviv]

map实现，存储到一个map里，遍历时，如果新的map存在当前数就删除，否则就存储。最终新的map就是single num，时间复杂度 o(n),空间复杂度 o(n)

func singleNumber(nums []int) int {
    single := 0
    maps := make(map[int]int)
    for _,num := range nums {
        if _,ok := maps[num];ok{
            delete(maps,num)
        }else{
            maps[num] = 1
        }
    }
    for _,value := range maps{
         single = value
    }
    return  single
}

[hankviv]

方法二：异或方法 因为异或满足： 1、0和任何数异或都等于任何数字本身。 2、两个相同的数字异或等于0， 3、异或满足交换律和结合律。 时间复杂度 o(n) 空间复杂度o(1)

func getSingle(nums []int) int {
    single := 0

    for _,num := range nums{
        single ^= num
    }
    return single
}

[hankviv]

[hankviv]

方法1，使用map，然后在遍历map的key

func missingNumber(nums []int) int {
    numMap := make(map[int]int)
    miss := 0
    for _,num := range nums{
        numMap[num] = 1
    }
    len := len(numMap)
    for i := 0; i< len; i ++ {
        if _,ok:= numMap[i];!ok{
            miss = i
        }
    }
    return miss
}

[hankviv]

给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。 示例 1:

输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
示例 2:

输入: [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。

[hankviv]

暴力法：复杂度O(n方) 遍历两边，保存最大数

func maxProduct(num []int) int {
   lens := len(num)
    max := num[0]
    for i := 0; i < lens; i++ {
        res := num[i]
        for j := i + 1; j < lens; j++ {
            res *= num[j]
            if res > max {
                max = res
            }
            if num[j] > max {
                max = num[j]
            }
        }
    }
    return max
}

[hankviv]

每日一题：

[hankviv]

暴力干：算法复杂度 O(n方) 1、暴力法 遍历一遍 发现零后，遍历后面的数组，和后面不为零的数字交换

func moveZeroes(nums []int) []int {
    lens := len(nums)
    for i := 0; i < lens; i++ {
        if nums[i] == 0 {
            for j := i + 1; j < lens; j++ {
                if nums[j] != 0 {
                    nums[i], nums[j] = nums[j], nums[i]
                    break;
                }
            }
        }
    }
    return nums
}

[hankviv]

2、优解 设置两个指针。一个用来指向数组中能保证之前都是非零的指针。一个指针用来遍历当前数组, 如果为零的时，不做操作，继续遍历，如果不为零时，把当前数和非零的最后一个数交换，并且非零指针+1

func moveZeroes(nums []int) []int {
    lens := len(nums)
    lastnonzeroIndex := 0
    for i := 0; i < lens; i++ {
        if nums[i] != 0 {
            nums[lastnonzeroIndex], nums[i] = nums[i], nums[lastnonzeroIndex]
            lastnonzeroIndex++
        }
    }
    return nums
}

[hankviv]

每日一题：

[hankviv]

依然暴力： 两层遍历 O(n方)

func maxArea(nums []int) int {
    maxArea := 0;
    for i := 0; i < len(nums); i++ {
        for j := i + 1; j < len(nums); j++ {
            minNum := getMin(&nums[i], &nums[j]);
            currentArea := minNum * (j - i)
            if currentArea > maxArea {
                maxArea = currentArea
            }
        }
    }
    return maxArea
}

func getMin(a,b *int) (min int) {
    if *a > *b {
        min = *b
    } else {
        min = *a
    }
    return
}

[hankviv]

方法2: 两端指针法

双指针代表的是 可以作为容器边界的所有位置的范围。在一开始，双指针指向数组的左右边界，表示 数组中所有的位置都可以作为容器的边界，因为我们还没有进行过任何尝试。在这之后，我们每次将 对应的数字较小的那个指针 往 另一个指针 的方向移动一个位置，就表示我们认为 这个指针不可能再作为容器的边界了。

论证逻辑： 由于边界取得是 min(x,y) 假设我们挪动长板的话，当前板变长 面积不变；当前板变短 如果短到小于以前的短板的话，面积不变， 如果大于以前短板的话，虽然最短板不变，但是距离变短，所以也变小； 但是我们挪动短板的话，当前板变长 面积变大，当前板变小，面积不变。

func maxArea(nums []int) int {
    maxArea := 0;
    rightIndex := len(nums) - 1
    leftIndex := 0
    for {
        currentArea := getMin(&nums[rightIndex], &nums[leftIndex]) * (rightIndex - leftIndex)
        if currentArea > maxArea {
            maxArea = currentArea
        }
        if nums[rightIndex] > nums[leftIndex] {
            leftIndex++
        } else {
            rightIndex--
        }
        if leftIndex == rightIndex {
            return maxArea
        }
    }
}

func getMin(a, b *int) (min int) {
    if *a > *b {
        min = *b
    } else {
        min = *a
    }
    return
}

[hankviv]

每日一题

[hankviv]

依然暴力： 直接套公式，两遍循环，每个数只用一次

func twoSum(nums []int, target int) []int {
    length := len(nums)
    for i := 0; i < length; i++ {
        for j := i + 1; j < length; j++ {
            //fmt.Println(nums[i],nums[j])
            if nums[i]+nums[j] == target {
                return []int{i, j}
            }
        }

    }
    return []int{}
}

[hankviv]

2、优解 两遍hash法

func twoSum(nums []int, target int) []int {

    numsMap := make(map[int]int)

    for key,value := range nums{
        numsMap[value] = key
    }

    for key,value := range nums{
        needNum := target - value

        if currentKey,ok := numsMap[needNum]; ok{
            if currentKey != key{
                return []int{key,currentKey}
            }           
        }
    }
    return []int{}
}

[hankviv]

每日一题

[hankviv]

暴力法： 去重花了个把小时，最终还是超时。。。

func threeSum(nums []int, target int) (res [][]int) {

    length := len(nums)
    hashMap := make(map[int]map[int]int)

    for i := 0; i < length; i++ {

        for j := i + 1; j < length; j++ {
            for k := j + 1; k < length; k++ {
                if nums[i]+nums[j]+nums[k] == target {
                    sm := []int{nums[i], nums[j], nums[k]}
                    sort.Ints(sm)
                    first, me, last := sm[0], sm[1], sm[2]
                    if value, ok := hashMap[first][me]; ok {
                        if value == last {
                            break
                        }
                    }
                    if hashMap[first] == nil {
                        hashMap[first] = make(map[int]int)
                    }
                    hashMap[first][me] = last
                    res = append(res, []int{nums[i], nums[j], nums[k]})

                }
            }

        }
    }
    return res
}

[hankviv]

二分查找

func binarySearch(n []int, target int) int {
    length  := len(n)
    low := 0
    high := length -1

    for low <= high  {
        mid := (low + high) / 2
        if n[mid] > target{
            high = mid -1
        }else if n[mid] < target{
            low  = mid +1
        }else {
            return mid
        }
    }
    return 0
}