杂题

nber1994

All
Posts
Categories
Tags
About

杂题

    ❐leetcode


环形链表II

给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。
说明:不允许修改给定的链表。
进阶:
你是否可以不用额外空间解决此题?
思路:
如下图所示:

2(x+y)=x+y+z+y

//两数之和
//借助一个hash表来进行数据的存储
//O(N)
func twoSum(nums []int, target int) []int {
	hashMap := make(map[int]int, len(nums))
	for k, v := range nums {
		if index, exist := hashMap[target-v]; exist {
			return []int{k, index}
		} else {
			hashMap[v] = k
		}
	}
	return nil
}

//先将数组排序,然后两个指针分别寻找
//O(logN)
func twoSum1(nums []int, target int) []int {
	lens := len(nums)
	oldNums := make([]int, lens)
	copy(oldNums[:], nums)
	sortedNums := sort.IntSlice(nums)
	sort.Stable(sortedNums)
	left, right := 0, lens-1
	for left < right {
		for {
			if sortedNums[left]+sortedNums[right] <= target {
				break
			}
			right--
		}
		if sortedNums[left]+sortedNums[right] == target {
			break
		}
		for {
			if sortedNums[left]+sortedNums[right] >= target {
				break
			}
			left--
		}
		if sortedNums[left]+sortedNums[right] == target {
			break
		}
	}
	res := []int{}
	for k, v := range oldNums {
		if v == left || v == right {
			res = append(res, k)
		}
	}
	return res
}

//三数之和
//遍历最外面的一个,里面的就转化为2sum
func threeSum(nums []int) [][]int {
	lens := len(nums)
	res := [][]int{}
	sort.Ints(nums)
	for left := 0; left < lens-2; left++ {
		//防止重复产生
		if left > 0 && nums[left] == nums[left-1] {
			continue
		}
		mid, right := left+1, lens-1
		for mid < right {
			//防止重复产生
			if mid > left+1 && nums[mid] == nums[mid-1] {
				continue
			}
			if nums[left]+nums[mid]+nums[right] == 0 {
				res = append(res, []int{left, mid, right})
				mid++
				right--
			}
			if nums[left]+nums[mid]+nums[right] > 0 {
				right--
			}
			if nums[left]+nums[mid]+nums[right] < 0 {
				left++
			}
		}
	}
	return res
}

最大回文子串

//最大回文子串
func longestPalindrome(s string) string {
	//动态规划, p(i, j) si 到 sj之间是否是回文字符串
	//p(i, j) = p(i-1, j+1) && si == sj
	//p(i, i) = true
	//p(i, i+1) = (si == si+1)
	sArr := []byte(s)
	lens := len(sArr)
	p := [][]int{}
	for i := 0; i < lens; i++ {
		tmp := make([]int, lens)
		p = append(p, tmp)
	}
	maxLen := 0
	start := 0
	for j := 0; j < lens-1; j++ {
		for i := 0; i <= j; i++ {
			if j-i < 2 {
				if sArr[i] == sArr[j] {
					p[i][j] = 1
				}
			} else {
				if p[i+1][j-1] == 1 && sArr[i] == sArr[j] {
					p[i][j] = 1
				}
			}
			if p[i][j] == 1 && j-i+1 > maxLen {
				maxLen = j - i + 1
				start = i
			}
		}
	}
	return string(sArr[start : start+maxLen])
}

//最大回文子序列
//用pij表示在i,j之间最大的子序列
//如果si==sj,则pij=pi+1j-1 + 2
//如果si!=sj,则pij=max(pi+1j,pij-1)
func longestPalindromeSubseq(s string) int {
	sArr := []byte(s)
	lens := len(sArr)
	p := [][]int{}
	for i := 0; i < lens; i++ {
		tmp := make([]int, lens)
		p = append(p, tmp)
	}
	for i := 0; i < lens; i++ {
		for j := 0; i+j < lens; j++ {
			if j == i+j {
				p[j][i+j] = 1
			} else if sArr[j] == sArr[i+j] {
				p[j][i+j] = p[j+1][i+j-1] + 2
			} else if sArr[j] != sArr[i+j] {
				if p[j+1][i+j] > p[j][i+j-1] {
					p[j][i+j] = p[j+1][i+j]
				} else {
					p[j][i+j] = p[j][i+j-1]
				}
			}
		}
	}
	return p[0][lens-1]
}

//最大回文子序列
//用pij表示在i,j之间最大的子序列
//如果si==sj,则pij=pi+1j-1 + 2
//如果si!=sj,则pij=max(pi+1j,pij-1)
//输出, 保证在当前值之前,i+1,j-1  i+1,j, i,j-1都已初始化完毕
//0 0
//1 1
//2 2
//3 3
//0 1
//1 2
//2 3
//0 2
//1 3
//0 3
func longestPalindromeSubseq1(s string) int {
	sArr := []byte(s)
	lens := len(sArr)
	p := [][]int{}
	for i := 0; i < lens; i++ {
		tmp := make([]int, lens)
		p = append(p, tmp)
	}
	for i := 0; i < lens; i++ {
		for j := 0; i+j < lens; j++ {
			fmt.Println(j, i+j)
			if j == i+j {
				p[j][i+j] = 1
			} else if sArr[j] == sArr[i+j] {
				p[j][i+j] = p[j+1][i+j-1] + 2
			} else if sArr[j] != sArr[i+j] {
				if p[j+1][i+j] > p[j][i+j-1] {
					p[j][i+j] = p[j+1][i+j]
				} else {
					p[j][i+j] = p[j][i+j-1]
				}
			}
		}
	}
	return p[0][lens-1]
}

//最长公共子串
//dp[i,j]表示str1在i位置,str2在j位置,最长的公共子串
//则sai==saj则dp[i,j] = dp[i-1,j-1] + 1
//否则dp[i,j] = 0, 因为要求是要连续
func lcs(s1, s2 string) string {
	sa1 := []byte(s1)
	sa2 := []byte(s2)
	lens1 := len(sa1)
	lens2 := len(sa2)
	dp := [][]int{}
	for i := 0; i < lens1; i++ {
		tmp := make([]int, lens2)
		dp = append(dp, tmp)
	}
	max, start := 0, 0
	for i := 0; i < lens1; i++ {
		for j := 0; j < lens2; j++ {
			if i == 0 || j == 0 {
				if sa1[i] == sa2[j] {
					dp[i][j] = 1
				}
			} else if sa1[i] == sa2[j] {
				dp[i][j] = dp[i-1][j-1] + 1
			}
			if dp[i][j] > max {
				max = dp[i][j]
				start = i + 1 - max
			}
		}
	}
	return string(sa1[start : start+max])
}

//最长公共子序列
func lcseq(str1, str2 string) int {
	sa1 := []byte(str1)
	sa2 := []byte(str2)
	lens1 := len(sa1)
	lens2 := len(sa2)
	dp := [][]int{}
	for i := 0; i < lens1; i++ {
		tmp := make([]int, lens2)
		dp = append(dp, tmp)
	}
	for i := 0; i < lens1; i++ {
		for j := 0; j < lens2; j++ {
			if i == 0 || j == 0 {
				if sa1[i] == sa2[j] {
					dp[i][j] = 1
				}
			} else if sa1[i] == sa2[j] {
				dp[i][j] = dp[i-1][j-1] + 1
			} else if sa1[i] != sa2[j] {
				if dp[i-1][j] > dp[i][j-1] {
					dp[i][j] = dp[i-1][j]
				} else {
					dp[i][j] = dp[i][j-1]
				}
			}
		}
	}
	return dp[lens1-1][lens2-1]
}

//全排列
//将首个元素随机和后面的元素进行交换
func permute(nums []int) [][]int {
	lens := len(nums)
	res := [][]int{}
	recur(nums, 0, lens-1, &res)
	return res
}

func recur(nums []int, left, right int, res *[][]int) {
	if left == right {
		tmp := make([]int, len(nums))
		copy(tmp, nums)
		*res = append(*res, tmp)
	} else {
		for i := left; i <= right; i++ {
			nums[left], nums[i] = nums[i], nums[left]
			recur(nums, left+1, right, res)
			nums[left], nums[i] = nums[i], nums[left]
		}
	}
}

//给出1-n的m位数的全排列
func permuteNm(n, m int) []string {
	nums := []byte{}
	for i := 1; i <= n; i++ {
		nums = append(nums, byte(i)+'0')
	}
	res := []string{}
	recurNm(nums, []byte{}, m, &res)
	return res
}

func recurNm(nums, pre []byte, m int, res *[]string) {
	if m == 0 {
		tmp := make([]byte, len(pre))
		copy(tmp, pre)
		*res = append(*res, string(tmp))
	} else {
		for k, v := range nums {
			tNums := make([]byte, len(nums))
			tPre := make([]byte, len(pre))
			copy(tNums, nums)
			copy(tPre, pre)
			tPre = append(tPre, v)
			tNums = append(tNums[:k], tNums[k+1:]...)
			recurNm(tNums, tPre, m-1, res)
		}
	}
}

func allCount(n int) int {
	myMap := map[string]string{"13": "2", "46": "5", "79": "8", "17": "4", "28": "5", "39": "6", "19": "5", "37": "5", "31": "2", "64": "5", "97": "8", "71": "4", "82": "5", "93": "6", "91": "5", "73": "5"}
	count := 0
	for i := n; i <= 9; i++ {
		allList := permuteNm(9, n)
		fmt.Println(len(allList))

		for key, val := range myMap {
			for _, v := range allList {
				if strings.Contains(v, key) && !strings.Contains(string([]byte(v)[:strings.Index(v, key)]), val) {
					break
				}
			}
			count++
		}
	}
	return count
}

//全排列 存在重复元素
func permuteII(nums []int) [][]int {
	lens := len(nums)
	res := [][]int{}
	recurII(nums, 0, lens-1, &res)
	return res
}

func recurII(nums []int, left, right int, res *[][]int) {
	if left == right {
		tmp := make([]int, len(nums))
		copy(tmp, nums)
		*res = append(*res, tmp)
	} else {
		for i := left; i <= right; i++ {
			//若i节点之后还存在相同的元素,则不进行交换,因为如果将相同的元素放在第一位,后面的元素进行全排列,但是全排列的元素都相同所以会重复
			if !canGoOn(nums, i, right) {
				continue
			}
			nums[left], nums[i] = nums[i], nums[left]
			recurII(nums, left+1, right, res)
			nums[left], nums[i] = nums[i], nums[left]
		}
	}
}

func canGoOn(nums []int, i, right int) bool {
	for _, v := range nums[i+1 : right+1] {
		if v == nums[i] {
			return false
		}
	}
	return true
}

//下一个排列
//下一个排列就是指的比当前数字最大的最小的数
//从后向前找到第一个比前一个小的数
//然后在后面的数中找到比该数大的最小的数,进行交换
//然后后面的数进行升序排列
func nextPermutation(nums []int) {
	fmt.Println(nums)
	lens := len(nums)
	index := 0
	for i := lens - 2; i > 0; i-- {
		if nums[i] < nums[i+1] {
			index = i
			break
		}
	}
	index2 := 0
	for i := index + 1; i < lens; i++ {
		if nums[i] < nums[index] {
			index2 = i - 1
			break
		}
	}
	nums[index], nums[index2] = nums[index2], nums[index]
	for left, right := index+1, lens-1; left < right; left, right = left+1, right-1 {
		nums[left], nums[right] = nums[right], nums[left]
	}
	fmt.Println(nums)
}

//第k个排列
func getPermutation(n int, k int) string {
	res := make([]byte, n)
	numSet := make([]byte, n)
	for i := 0; i < n; i++ {
		numSet[i] = byte(i) + '1'
	}
	for i := 1; i <= n; i++ {
		index := k / factorial(n-i)
		rest := k % factorial(n-i)
		if rest != 0 {
			index++
		}
		res[i-1] = numSet[index-1]
		numSet = append(numSet[:index-1], numSet[index:]...)
		k = k - (index-1)*factorial(n-i)
	}
	return string(res)
}

func factorial(n int) int {
	res := 1
	for i := n; i > 0; i-- {
		res *= i
	}
	return res
}

//字符串相加
func addStrings(s1, s2 string) string {
	sa1 := []byte(s1)
	sa2 := []byte(s2)
	lens1 := len(sa1)
	lens2 := len(sa2)
	i, push := 0, byte(0)
	res := []byte{}
	for {
		if lens1-i < 1 && lens2-i < 1 && push == byte(0) {
			break
		}
		num1, num2 := byte('0'), byte('0')
		if lens1-i > 0 {
			num1 = sa1[lens1-i-1]
		}
		if lens2-i > 0 {
			num2 = sa2[lens2-i-1]
		}
		tmp := num1 + num2 + push - '0'
		if tmp > '9' {
			push = byte(1)
			tmp = tmp - 10
		} else {
			push = byte(0)
		}
		res = append([]byte{tmp}, res...)
		i++
	}
	return string(res)
}

//大数相乘
func multiply(num1 string, num2 string) string {
	if num1 == "0" || num2 == "0" {
		return "0"
	}

	// string转换成[]byte,容易取得相应位上的具体值
	bsi := []byte(num1)
	bsj := []byte(num2)

	// temp 的长度只可能为 len(num1)+len(num2) 或 len(num1)+len(num2)-1
	// 先选长的,免得位不够
	temp := make([]int, len(num1)+len(num2))
	for i := 0; i < len(bsi); i++ {
		for j := 0; j < len(bsj); j++ {
			// 每个位上的乘积,可以直接存入 temp 中相应的位置
			temp[i+j+1] += int(bsi[i]-'0') * int(bsj[j]-'0')
		}
	}

	// 统一处理进位
	for i := len(temp) - 1; i > 0; i-- {
		temp[i-1] += temp[i] / 10
		temp[i] = temp[i] % 10
	}

	// num1 和 num2 较小的时候,temp的首位为0
	// 为避免输出结果以0开头,需要去掉temp的0首位
	if temp[0] == 0 {
		temp = temp[1:]
	}

	// 转换结果
	// temp 选用为[]int,而不是[]byte,是因为
	// Go中,byte的基础结构是uint8,最大值为255。
	// 不考虑进位的话,temp会溢出
	res := make([]byte, len(temp))
	for i := 0; i < len(temp); i++ {
		res[i] = '0' + byte(temp[i])
	}

	return string(res)
}

//逆序对的个数 结合归并排序完成
func allReverseCup(nums []int) int {
	count := 0
	mergeSort(nums, &count)
	return count
}

func mergeSort(nums []int, count *int) []int {
	lens := len(nums)
	if lens < 2 {
		return nums
	}
	mid := lens / 2
	return merge(mergeSort(nums[:mid], count), mergeSort(nums[mid:], count), count)
}

func merge(nums1, nums2 []int, count *int) []int {
	res := []int{}
	for len(nums1) > 0 || len(nums2) > 0 {
		if len(nums1) > 0 && len(nums2) > 0 {
			if nums1[0] > nums2[0] {
				res = append(res, nums1[0])
				nums1 = nums1[1:]
				*count = *count + len(nums2)
			} else {
				res = append(res, nums2[0])
				nums2 = nums2[1:]
			}
		} else if len(nums1) > 0 {
			res = append(res, nums1[0])
			nums1 = nums1[1:]
		} else if len(nums2) > 0 {
			res = append(res, nums2[0])
			nums2 = nums2[1:]
			*count = *count + len(nums1)
		}
	}
	return res
}