nber1994



leetcode-数组

August 9, 2019

leetcode-数组

package main

import (
	"fmt"
	"sort"
)

func main() {
	fmt.Println(twoSum1([]int{2, 11, 7, 15}, 9))
	fmt.Println(twoSum2([]int{2, 11, 7, 15}, 9))
}

//两数之和
//给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。
//
//你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。
//
//示例:
//
//给定 nums = [2, 7, 11, 15], target = 9
//
//因为 nums[0] + nums[1] = 2 + 7 = 9
//所以返回 [0, 1]
//两个指针向中间逼近
func twoSum1(nums []int, target int) []int {
	lens := len(nums)
	oldNums := make([]int, lens)
	copy(oldNums[:], nums)
	left := 0
	right := lens - 1
	sortedNums := sort.IntSlice(nums)
	sort.Stable(sortedNums)
	res := []int{}
	for left < right {
		//右边的指针要移动到已经不能移动位置
		for sortedNums[left]+sortedNums[right] > target {
			right--
		}
		if sortedNums[left]+sortedNums[right] == target {
			break
		}
		//左边的指针移动到不能移动位置
		for sortedNums[left]+sortedNums[right] < target {
			left++
		}
		if sortedNums[left]+sortedNums[right] == target {
			break
		}
	}
	for k, v := range oldNums {
		if v == sortedNums[left] || v == sortedNums[right] {
			res = append(res, k)
		}
	}
	return res
}

//空间换时间
//以 差值-> 键值 作为map
func twoSum2(nums []int, target int) []int {
	myMap := map[int]int{}
	for k, v := range nums {
		if i, exist := myMap[v]; exist {
			return []int{i, k}
		}
		myMap[target-v] = k
	}
	return []int{}
}

//搜索插入位置
//给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。
//
//你可以假设数组中无重复元素。
//
//示例 1:
//
//输入: [1,3,5,6], 5
//输出: 2
//示例 2:
//
//输入: [1,3,5,6], 2
//输出: 1
//示例 3:
//
//输入: [1,3,5,6], 7
//输出: 4
//示例 4:
//
//输入: [1,3,5,6], 0
//输出: 0
func searchInsert(nums []int, target int) int {
	res := 0
	for _, v := range nums {
		if v == target || v > target {
			break
		}
		res++
	}
	return res
}

//在排序数组中查找元素的第一个和最后一个位置
//给定一个按照升序排列的整数数组 nums,和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
//
//你的算法时间复杂度必须是 O(log n) 级别。
//
//如果数组中不存在目标值,返回 [-1, -1]。
//
//示例 1:
//
//输入: nums = [5,7,7,8,8,10], target = 8
//输出: [3,4]
//示例 2:
//
//输入: nums = [5,7,7,8,8,10], target = 6
//输出: [-1,-1]
func searchRange(nums []int, target int) []int {
	res := []int{-1, -1}
	for k, v := range nums {
		if v == target {
			if res[0] == -1 {
				res[0] = k
				res[1] = k
			} else {
				res[1] = k
			}
		} else {
			if res[0] == -1 {
			} else {
				break
			}
		}
	}
	return res
}


//旋转图像
//给定一个 n × n 的二维矩阵表示一个图像。
//
//将图像顺时针旋转 90 度。
//
//说明:
//
//你必须在原地旋转图像,这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。
//
//示例 1:
//
//给定 matrix =
//[
//  [1,2,3],
//  [4,5,6],
//  [7,8,9]
//],
//
//原地旋转输入矩阵,使其变为:
//[
//  [7,4,1],
//  [8,5,2],
//  [9,6,3]
//]
//示例 2:
//
//给定 matrix =
//[
//  [ 5, 1, 9,11],
//  [ 2, 4, 8,10],
//  [13, 3, 6, 7],
//  [15,14,12,16]
//],
//
//原地旋转输入矩阵,使其变为:
//[
//  [15,13, 2, 5],
//  [14, 3, 4, 1],
//  [12, 6, 8, 9],
//  [16, 7,10,11]
//]

func rotate(matrix [][]int) {
        //首先根据中轴线进行翻转
        lens := len(matrix)
        for i := 0; i < lens; i++ {
                for j := 0; j+i < lens; j++ {
                        matrix[i+j][i], matrix[i][i+j] = matrix[i][i+j], matrix[i+j][i]
                }
        }
        //再进行左右互换
        for i := 0; i < lens; i++ {
                for j := 0; j < lens/2; j++ {
                        matrix[i][j], matrix[i][lens-j-1] = matrix[i][lens-j-1], matrix[i][j]
                }
        }
}

//搜索旋转排序数组
//假设按照升序排序的数组在预先未知的某个点上进行了旋转。
//
//( 例如,数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
//
//搜索一个给定的目标值,如果数组中存在这个目标值,则返回它的索引,否则返回 -1 。
//
//你可以假设数组中不存在重复的元素。
//
//你的算法时间复杂度必须是 O(log n) 级别。
//
//示例 1:
//
//输入: nums = [4,5,6,7,0,1,2], target = 0
//输出: 4
//示例 2:
//
//输入: nums = [4,5,6,7,0,1,2], target = 3
//输出: -1
func search(nums []int, target int) int {
        lens := len(nums)
        left, right := 0, lens-1
        for left <= right {
                mid := (left + right) / 2
                if nums[mid] == target {
                        return mid
                } else if nums[left] <= nums[mid] {
                        if nums[left] <= target && target < nums[mid] {
                                right = mid
                        } else {
                                left = mid + 1
                        }
                } else {
                        if nums[mid] < target && target <= nums[right] {
                                left = mid
                        } else {
                                right = mid - 1
                        }
                }
        }
        return -1
}

//搜索旋转排序数组II
//假设按照升序排序的数组在预先未知的某个点上进行了旋转。
//
//( 例如,数组 [0,0,1,2,2,5,6] 可能变为 [2,5,6,0,0,1,2] )。
//
//编写一个函数来判断给定的目标值是否存在于数组中。若存在返回 true,否则返回 false。
//
//示例 1:
//
//输入: nums = [2,5,6,0,0,1,2], target = 0
//输出: true
//示例 2:
//
//输入: nums = [2,5,6,0,0,1,2], target = 3
//输出: false
//进阶:
//
//这是 搜索旋转排序数组 的延伸题目,本题中的 nums  可能包含重复元素。
//这会影响到程序的时间复杂度吗?会有怎样的影响,为什么?
func searchII(nums []int, target int) bool {
        lens := len(nums)
        left, right := 0, lens-1
        for left <= right {
                mid := (left + right) / 2
                if nums[mid] == target {
                        return true
                } else if nums[left] < nums[mid] {
                        if nums[left] <= target && target < nums[mid] {
                                right = mid
                        } else {
                                left = mid + 1
                        }
                } else if nums[left] > nums[mid] {
                        if nums[mid] < target && target <= nums[right] {
                                left = mid
                        } else {
                                right = mid - 1
                        }
                } else {
                        left++
                }
        }
        return false
}

//无重复字符的最长子串
//给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。
//
//示例 1:
//
//输入: "abcabcbb"
//输出: 3
//解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。
//示例 2:
//
//输入: "bbbbb"
//输出: 1
//解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。
//示例 3:
//
//输入: "pwwkew"
//输出: 3
//解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
//     请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。
//
func lengthOfLongestSubstring1(s string) int {
        sa := []byte(s)
        byteMap := map[byte]int{}
        res, count := 0, 0
        for i := 0; i < len(sa); {
                if k, exist := byteMap[sa[i]]; exist {
                        if count > res {
                                res = count
                        }
                        count = 0
                        i = k + 1
                        byteMap = map[byte]int{}
                } else {
                        byteMap[sa[i]] = i
                        count++
                        i++
                }
        }
        if count > res {
                res = count
        }
        return res
}

func lengthOfLongestSubstring2(s string) int {
        sa := []byte(s)
        byteMap := map[byte]int{}
        left, right, maxLen := 0, 0, 0
        for i, v := range sa {
                if k, exist := byteMap[v]; !exist {
                        byteMap[v] = i
                } else {
                        if byteMap[v] >= left {
                                left = k + 1
                        }
                        byteMap[v] = i
                }
                if (right-left)+1 > maxLen {
                        maxLen = right - left + 1
                }
                right++
        }
        return maxLen
}

//搜索二维矩阵
//编写一个高效的算法来判断 m x n 矩阵中,是否存在一个目标值。该矩阵具有如下特性:
//
//每行中的整数从左到右按升序排列。
//每行的第一个整数大于前一行的最后一个整数。
//示例 1:
//
//输入:
//matrix = [
//  [1,   3,  5,  7],
//  [10, 11, 16, 20],
//  [23, 30, 34, 50]
//]
//target = 3
//输出: true
//示例 2:
//
//输入:
//matrix = [
//  [1,   3,  5,  7],
//  [10, 11, 16, 20],
//  [23, 30, 34, 50]
//]
//target = 13
//输出: false
func searchMatrix1(matrix [][]int, target int) bool {
        if len(matrix) == 0 || len(matrix[0]) == 0 {
                return false
        }
        n := len(matrix[0])
        m := len(matrix)
        i, j := 0, 0
        for {
                if i == m-1 || matrix[i][0] == target || matrix[i+1][0] > target {
                        break
                }
                i++
        }
        for {
                if j == n {
                        break
                }
                if matrix[i][j] == target {
                        return true
                }
                j++
        }
        return false
}

//搜索二维矩阵II
//编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性:
//
//每行的元素从左到右升序排列。
//每列的元素从上到下升序排列。
//示例:
//
//现有矩阵 matrix 如下:
//
//[
//  [1,   4,  7, 11, 15],
//  [2,   5,  8, 12, 19],
//  [3,   6,  9, 16, 22],
//  [10, 13, 14, 17, 24],
//  [18, 21, 23, 26, 30]
//]
//给定 target = 5,返回 true。
//
//给定 target = 20,返回 false。
func searchMatrix(matrix [][]int, target int) bool {
        if len(matrix) == 0 || len(matrix[0]) == 0 {
                return false
        }
        m, n := len(matrix), len(matrix[0])
        i, j := m-1, 0
        for i >= 0 || j <= n-1 {
                if matrix[i][j] == target {
                        return true
                } else if matrix[i][j] < target {
                        if j < n-1 {
                                j++
                                continue
                        } else {
                                return false
                        }
                } else {
                        if i > 0 {
                                i--
                                continue
                        } else {
                                return false
                        }
                }
        }
        return false
}

//复原IP地址
//给定一个只包含数字的字符串,复原它并返回所有可能的 IP 地址格式。
//
//示例:
//
//输入: "25525511135"
//输出: ["255.255.11.135", "255.255.111.35"]
func restoreIpAddresses1(s string) []string {
        //递归调用
        res := []string{}
        recursiveFunc(s, "", 0, &res)
        return res
}

func recursiveFunc(s, pre string, n int, res *[]string) {
        //此时已经到达最后
        if n == 3 {
                i, _ := strconv.Atoi(s)
                if i >= 0 && i <= 255 && strconv.Itoa(i) == s {
                        *res = append(*res, pre+"."+s)
                }
                return
        }
        for index := 1; index < 4 && index < len(s); index++ {
                j, _ := strconv.Atoi(s[:index])
                if j >= 0 && j <= 255 && strconv.Itoa(j) == s[:index] {
                        if pre == "" {
                                recursiveFunc(s[index:], s[:index], n+1, res)
                        } else {
                                recursiveFunc(s[index:], pre+"."+s[:index], n+1, res)
                        }
                }
        }
}

func restoreIpAddresses(s string) []string {
        res := []string{}
        for a := 1; a < 4 && len(s) >= a; a++ {
                i, _ := strconv.Atoi(s[:a])
                if i < 0 || i > 255 || strconv.Itoa(i) != s[:a] {
                        continue
                }
                for b := a + 1; b < a+4 && len(s) >= b; b++ {
                        j, _ := strconv.Atoi(s[a:b])
                        if j < 0 || j > 255 || strconv.Itoa(j) != s[a:b] {
                                continue
                        }
                        for c := b + 1; c < b+4 && len(s) >= c; c++ {
                                k, _ := strconv.Atoi(s[b:c])
                                if k < 0 || k > 255 || strconv.Itoa(k) != s[b:c] {
                                        continue
                                }
                                l, _ := strconv.Atoi(s[c:])
                                if l < 0 || l > 255 || strconv.Itoa(l) != s[c:] {
                                        continue
                                }
                                res = append(res, s[:a]+"."+s[a:b]+"."+s[b:c]+"."+s[c:])
                        }
                }
        }
        return res
}

//电话号码的字母组合
//给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。
//
//给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。
//1
//2 abc
//3 def
//4 ghi
//5 jkl
//6 mno
//7 pqrs
//8 tuv
//9 wxyz
//0
//
//示例:
//
//输入:"23"
//输出:["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
//说明:
//尽管上面的答案是按字典序排列的,但是你可以任意选择答案输出的顺序
func letterCombinations1(s string) []string {
        if s == "" {
                return []string{}
        }
        keyMap := map[byte][]string{}
        keyMap['0'] = []string{""}
        keyMap['1'] = []string{""}
        keyMap['2'] = []string{"a", "b", "c"}
        keyMap['3'] = []string{"d", "e", "f"}
        keyMap['4'] = []string{"g", "h", "i"}
        keyMap['5'] = []string{"j", "k", "l"}
        keyMap['6'] = []string{"m", "n", "o"}
        keyMap['7'] = []string{"p", "q", "r", "s"}
        keyMap['8'] = []string{"t", "u", "v"}
        keyMap['9'] = []string{"w", "x", "y", "z"}
        if len(s) == 1 {
                return keyMap[s[0]]
        }
        nextRes := letterCombinations(string(s[1:]))
        res := []string{}
        for _, v := range keyMap[s[0]] {
                for _, val := range nextRes {
                        res = append(res, v+val)
                }
        }
        return res
}

func letterCombinations(digit string) []string {
        if digit == "" {
                return []string{}
        }
        keyMap := map[byte][]string{}
        keyMap['0'] = []string{""}
        keyMap['1'] = []string{""}
        keyMap['2'] = []string{"a", "b", "c"}
        keyMap['3'] = []string{"d", "e", "f"}
        keyMap['4'] = []string{"g", "h", "i"}
        keyMap['5'] = []string{"j", "k", "l"}
        keyMap['6'] = []string{"m", "n", "o"}
        keyMap['7'] = []string{"p", "q", "r", "s"}
        keyMap['8'] = []string{"t", "u", "v"}
        keyMap['9'] = []string{"w", "x", "y", "z"}
        res := []string{""}
        for _, v := range []byte(digit) {
                tmp := []string{}
                for _, val := range keyMap[v] {
                        for _, value := range res {
                                tmp = append(tmp, value+val)
                        }
                }
                res = tmp
        }
        return res
}

//括号生成
//给出 n 代表生成括号的对数,请你写出一个函数,使其能够生成所有可能的并且有效的括号组合。
//
//例如,给出 n = 3,生成结果为:
//
//[
//  "((()))",
//  "(()())",
//  "(())()",
//  "()(())",
//  "()()()"
//]
func generateParenthesis(n int) []string {
        res := []string{}
        dfs(n, n, "", &res)
        return res
}

func dfs(left, right int, s string, res *[]string) {
        if left < 0 || right < 0 || left > right {
                return
        }
        if left == 0 && right == 0 {
                *res = append(*res, s)
        }
        dfs(left-1, right, s+"(", res)
        dfs(left, right-1, s+")", res)
}

//二进制求和
//给定两个二进制字符串,返回他们的和(用二进制表示)。
//
//输入为非空字符串且只包含数字 1 和 0。
//
//示例 1:
//
//输入: a = "11", b = "1"
//输出: "100"
//示例 2:
//
//输入: a = "1010", b = "1011"
//输出: "10101"
func addBinary(a string, b string) string {
        arra, arrb := []byte(a), []byte(b)
        lensa, lensb := len(arra), len(arrb)
        res := []byte{}
        add := 0
        for i, j := lensa-1, lensb-1; i >= 0 || j >= 0 || add != 0; i, j = i-1, j-1 {
                sum := 0
                if i >= 0 && j >= 0 {
                        sum = int(arra[i]-'0') + int(arrb[j]-'0') + add
                } else if i >= 0 {
                        sum = int(arra[i]-'0') + add
                } else if j >= 0 {
                        sum = int(arrb[j]-'0') + add
                } else {
                        sum = add
                }
                add = sum / 2
                if sum%2 == 0 {
                        res = append([]byte{'0'}, res...)
                } else {
                        res = append([]byte{'1'}, res...)
                }
        }
        return string(res[:])
}

//最长公共前缀
//编写一个函数来查找字符串数组中的最长公共前缀。
//
//如果不存在公共前缀,返回空字符串 ""。
//
//示例 1:
//
//输入: ["flower","flow","flight"]
//输出: "fl"
//示例 2:
//
//输入: ["dog","racecar","car"]
//输出: ""
//解释: 输入不存在公共前缀。
//说明:
//
//所有输入只包含小写字母 a-z 。
//func longestCommonPrefix(strs []string) string {
//
//}

//合并有序数组
//给定两个有序整数数组 nums1 和 nums2,将 nums2 合并到 nums1 中,使得 num1 成为一个有序数组。
//
//说明:
//
//初始化 nums1 和 nums2 的元素数量分别为 m 和 n。
//你可以假设 nums1 有足够的空间(空间大小大于或等于 m + n)来保存 nums2 中的元素。
//示例:
//
//输入:
//nums1 = [1,2,3,0,0,0], m = 3
//nums2 = [2,5,6],       n = 3
//
//输出: [1,2,2,3,5,6]
func merge(nums1 []int, m int, nums2 []int, n int) {
        if m == 0 {
                copy(nums1, nums2)
        }
        if n == 0 {
                return
        }
        for k, v := range nums2 {
                nums1[m+k] = v
        }
        for i := m; i < m+n; i++ {
                for j := 0; j < i; j++ {
                        if nums1[j] > nums1[i] {
                                nums1[i], nums1[j] = nums1[j], nums1[i]
                        }
                }
        }
}

//杨辉三角
//给定一个非负整数 numRows,生成杨辉三角的前 numRows 行。
//
//在杨辉三角中,每个数是它左上方和右上方的数的和。
//
//示例:
//
//输入: 5
//输出:
//[
//     [1],
//    [1,1],
//   [1,2,1],
//  [1,3,3,1],
// [1,4,6,4,1]
//]
func generate(numRows int) [][]int {
        if numRows == 0 {
                return nil
        }
        res := [][]int{}
        res = append(res, []int{1})
        for i := 1; i < numRows; i++ {
                tmp := []int{1}
                for j := 0; j < len(res[i-1])-1; j++ {
                        tmp = append(tmp, res[i-1][j]+res[i-1][j+1])
                }
                tmp = append(tmp, 1)
                res = append(res, tmp)
        }
        return res
}

//杨辉三角II
//给定一个非负索引 k,其中 k ≤ 33,返回杨辉三角的第 k 行。
//
//在杨辉三角中,每个数是它左上方和右上方的数的和。
//
//示例:
//
//输入: 3
//输出: [1,3,3,1]
//进阶:
//
//你可以优化你的算法到 O(k) 空间复杂度吗?
func getRow(rowIndex int) []int {
        if rowIndex == 0 {
                return []int{}
        }
        rowIndex++
        res := make([]int, rowIndex)
        res[0] = 1
        //次数rowIndex-1次
        for i := 1; i < rowIndex; i++ {
                preNext := 1
                for j := 1; j < i; j++ {
                        tmp := res[j]
                        res[j] = preNext + res[j]
                        preNext = tmp
                }
                res[i] = 1
        }
        return res
}