环形链表II
给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
说明：不允许修改给定的链表。
进阶：
你是否可以不用额外空间解决此题？
思路：
如下图所示：
- 初始化slow指针指向head节点，fast指向head->next节点，假设slow与fast在c点相遇。由于slow走过的路程为x+y，fast走过的路程为x+y+z+y，且fast走过的距离是slow的两倍，所以：
2(x+y)=x+y+z+y
- 化简得：x=z，此时把slow指针放到c处，fast指针放到a处，俩指针以相同速度向前走，则相遇节点为b，且b为相遇节点。
//两数之和
//借助一个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
}