Tag: LeetCode - 逸如风的个人博客

- 博客
- 分类
- 标签
- 归档
- 友链
- 关于
- 摄影展

(LeetCode系列)刷题记

2099-06-06 LeetCode

求平方根

方法一：二分

时间复杂度：O(logN)
空间复杂度：O(1)

注意点：

mid*mix > x的时候容易溢出，改成mid > x/mid
mid := (l+r)>>1的时候也容易溢出，改成mid := l + (r-l)>>1

不保留小数

//不保留小数
func Sqrt(x int) int {

	if x <= 0 {
		return 0
	}

	l, r := 1, x-1
	for l <= r {
		mid := l + (r-l)>>1
		if mid > x/mid {
			r = mid - 1
		} else if mid < x/mid {  //Tips:写成x/mid用来确认不会溢出
			l = mid + 1
		} else {
			return mid
		}
	}

	return r
}

2021-11-30 算法

彻底解决解决两个链表相交的问题

前言

两个链表相交涉及到关于链表的一系列问题：其中包含了如下子问题，并且涉及到了大量的算法思想，比如快慢指针

判断链表是否有环
链表有环的情况下找到环的入口节点
判断两个链表是否相交
相交的情况下找到相交时候的第一个节点

对应的7种情况

解决代码

执行测试命令：go test -v intersection_test.go intersection.go -test.run TestIntersection

解决代码

package InterviewCoding

/**
 * @Author: yirufeng
 * @Date: 2021/11/25 8:21 上午
 * @Email: yirufeng@foxmail.com
 * @GitHub: https://www.github.com/sivanWu0222
 * @Desc:
 **/

type LinkedListNode struct {
	Val  int
	Next *LinkedListNode
}

/*
题目：返回两个链表相交的节点
步骤：
1. 明确题目中的意思，两个链表有无环，是否一定相交(如果不一定的话，我们需要判断是否相交，只有在相交的情况下我们才可以返回相交的第一个节点)
2. 分情况进行讨论：
	2.1 有环
		2.1.1 一定相交：
			直接找到相交的节点即可
		2.1.2 不一定相交：
			首先判断是否相交
			相交的时候，找到相交的第一个节点并返回
	2.2 无环
		2.2.1 一定相交：
		2.2.2 不一定相交：
			首先判断是否相交
			相交的时候，找到相交的第一个节点并返回
	2.3 1个有环1个无环，说明一定不会相交，直接返回Nil就可以了
*/

//返回两个链表的相交节点，如果不相交返回Nil，否则返回相交的第一个节点
func Intersection(l1, l2 *LinkedListNode) *LinkedListNode {
	//如果有一个为空，直接说明不相交
	if l1 == nil || l2 == nil {
		return nil
	}

	//判断两个链表是否有环，如果有环就返回环的起始节点
	startOfl1Ring, startOfl2Ring := startNodeOfRing(l1), startNodeOfRing(l2)
	//如果1个有1个没有，说明白不相交，直接返回nil
	if ((startOfl1Ring == nil) && (startOfl2Ring != nil)) || ((startOfl1Ring != nil) && (startOfl2Ring == nil)) {
		return nil
	}

	var ret *LinkedListNode
	if startOfl1Ring != nil { //如果有环
		ret = findIntersectionNodeWhenBothHaveCycle(l1, l2, startOfl1Ring, startOfl2Ring)
	} else { //如果没有环：此时就转换为我们正常的题解了
		ret = findIntersectionNodeWhenBothNoCycle(l1, l2)
	}

	return ret
}

//当两个链表都没有环的时候，找到两个链表的相交节点(可能相交，可能不相交)
//三种解法去找出第一个相交的节点
func findIntersectionNodeWhenBothNoCycle(l1, l2 *LinkedListNode) *LinkedListNode {
	//1. 获得第1个链表第2个链表的长度以及各自链表的最后一个节点
	l1Length, l2Length := 1, 1
	l1LastNode, l2LastNode := l1, l2
	for l1LastNode.Next != nil {
		l1Length, l1LastNode = l1Length+1, l1LastNode.Next
	}
	for l2LastNode.Next != nil {
		l2Length, l2LastNode = l2Length+1, l2LastNode.Next
	}

	//判断各自最后一个节点是否相等，如果不相等，说明不相交，直接返回nil
	if l1LastNode != l2LastNode {
		return nil
	}

	//先走长度差
	l1LastNode, l2LastNode = l1, l2
	if l1Length > l2Length {
		for i := 0; i < l1Length-l2Length; i++ {
			l1LastNode = l1LastNode.Next
		}
	} else {
		for i := 0; i < l2Length-l1Length; i++ {
			l2LastNode = l2LastNode.Next
		}
	}

	//然后一起走，如果中途相等直接返回
	for l1LastNode != l2LastNode {
		l1LastNode, l2LastNode = l1LastNode.Next, l2LastNode.Next
	}

	return l1LastNode
}

//当两个链表都有环的时候，找到两个链表的相交节点(可能相交，可能不相交(各自有一个自己的环))
func findIntersectionNodeWhenBothHaveCycle(l1, l2, startOfl1Ring, startOfl2Ring *LinkedListNode) *LinkedListNode {
	//判断两个链表是否有环的时候我们可以找到链表有环时候环的第一个节点
	//如果两个环的起始节点都相同，此时问题转变为l1的起始节点到自己拥有环的开始节点和l2的起始节点到自己拥有环的开始节点的第一个相交节点
	if startOfl1Ring == startOfl2Ring {
		l1Temp, l2Temp := l1, l2
		//转变为求两个无环单链表的相交节点
		var l1TempLength, l2TempLength int

		for l1Temp != startOfl1Ring {
			l1Temp, l1TempLength = l1Temp.Next, l1TempLength+1
		}

		for l2Temp != startOfl2Ring {
			l2Temp, l2TempLength = l2Temp.Next, l2TempLength+1
		}

		//长的先走
		if l1TempLength > l2TempLength {
			for i := 0; i < l1TempLength-l2TempLength; i++ {
				l1Temp = l1Temp.Next
			}
		} else {
			for i := 0; i < l2TempLength-l1TempLength; i++ {
				l2Temp = l2Temp.Next
			}
		}

		//此时一起走
		for l1Temp != l2Temp {
			l1Temp, l2Temp = l1Temp.Next, l2Temp.Next
		}
		return l1Temp

	} else { //如果两个环的起始节点不同，让其中一个环开始走，走到起始节点为止，如果中途会出现和另外一个环起始节点相同，说明相交，否则各自成环
		l1Temp := startOfl1Ring.Next
		for l1Temp != startOfl1Ring {
			if l1Temp == startOfl2Ring {
				return startOfl2Ring
			}
			l1Temp = l1Temp.Next
		}
	}

	return nil
}

//返回链表是否有环，如果有的话直接返回true，否则返回false
func startNodeOfRing(head *LinkedListNode) *LinkedListNode {
	fast, slow := head, head
	for fast != nil && fast.Next != nil {
		fast, slow = fast.Next.Next, slow.Next
		//说明此时相遇，表明有环
		if fast == slow {
			break
		}
	}

	//这里是第二个注意点，这里不仅仅要判断fast是否为空，还要判断fast.Next是否为空，
	//因为让链表停止上面for循环的有两个条件：1. fast为空 2. fast.Next为空
	//判断一下是因为fast为空或者fast.Next为空还是fast==slow退出的
	if fast == nil || fast.Next == nil {
		return nil
	}

	//走到这里说明有环，此时让fast指向head,然后fast与slow每次都走一步，一起相遇的时候返回即可
	fast = head
	for fast != slow {
		fast, slow = fast.Next, slow.Next
	}
	return fast
}

测试代码

package InterviewCoding

import (
	"testing"
)

/**
 * @Author: yirufeng
 * @Date: 2021/11/25 11:05 上午
 * @Email: yirufeng@foxmail.com
 * @GitHub: https://www.github.com/sivanWu0222
 * @Desc:
 **/

//测试两个链表
func TestIntersection(t *testing.T) {
	//模拟场景
	//1.1 两个不带环且不相交的链表
	l1, l2 := constructTwoLinkedListWithoutCycleAndNotIntersection()
	if Intersection(l1, l2) != nil {
		t.Fatalf("expect no intersection node.")
	}

	//1.2 两个不带环但是相交的链表：LeetCode原题
	//已修复，由于&&写成了||
	l1, l2 = constructTwoLinkedListWithoutCycleButIntersection()
	if Intersection(l1, l2) == nil {
		t.Log(Intersection(l1, l2))
		t.Fatalf("expect to have intersection node.")
	}

	//2. 1个链表有环，1个无环
	l1, l2 = constructTwoLinkedListButOneHasCycle()
	if Intersection(l1, l2) != nil {
		t.Fatalf("expect no intersection node.")
	}
	//3. 两个链表都有环
	//3.1 两个链表都有环，但是两个链表的环都是各自的
	l1, l2 = constructTwoLinkedBothHasOwnCycle()
	if Intersection(l1, l2) != nil {
		t.Fatalf("expect no intersection node.")
	}

	//3.2.1 两个链表都有环，并且两个链表是相交的，且交点在进入环之前
	//todo: 有问题
	l1, l2 = constructTwoLinkedListBothHasCycleAndIntersection()
	if Intersection(l1, l2) == nil {
		t.Fatalf("expect to have intersection node.")
	}
	//3.2.2 两个链表都有环，并且两个链表是相交的，且交点在环上
	l1, l2 = constructTwoLinkedListBothHasCycleAndIntersectionII()
	if Intersection(l1, l2) == nil {
		t.Fatalf("expect to have intersection node.")
	}
}

//两个不带环但是相交的链表
func constructTwoLinkedListWithoutCycleButIntersection() (l1, l2 *LinkedListNode) {
	node := &LinkedListNode{Val: 5}
	l1, l2 = &LinkedListNode{Val: 3}, &LinkedListNode{Val: 4, Next: &LinkedListNode{Val: 6, Next: node}}
	l1.Next, l2.Next = node, node
	return l1, l2
}

//两个不带环且不相交的链表
func constructTwoLinkedListWithoutCycleAndNotIntersection() (l1, l2 *LinkedListNode) {
	l1, l2 = &LinkedListNode{Val: 3, Next: &LinkedListNode{Val: 4}}, &LinkedListNode{Val: 5, Next: &LinkedListNode{Val: 6}}
	return l1, l2
}

//构造两个链表1个有环1个无环
func constructTwoLinkedListButOneHasCycle() (l1, l2 *LinkedListNode) {
	node, node2 := &LinkedListNode{Val: 2}, &LinkedListNode{Val: 3}
	node.Next, node2.Next = node2, node
	l1, l2 = &LinkedListNode{Val: 1, Next: node}, &LinkedListNode{Val: 3}
	return l1, l2
}

//构造两个都有环的链表，但是两个链表的环都是各自的
func constructTwoLinkedBothHasOwnCycle() (l1, l2 *LinkedListNode) {
	node, node2 := &LinkedListNode{Val: 2}, &LinkedListNode{Val: 3}
	node.Next, node2.Next = node2, node
	node3, node4 := &LinkedListNode{Val: 4}, &LinkedListNode{Val: 5}
	node3.Next, node4.Next = node4, node3
	l1, l2 = &LinkedListNode{Val: 1, Next: node}, &LinkedListNode{Val: 3, Next: node3}
	return l1, l2
}

//构造两个都有环的链表，但是两个链表都是相交的且相交的起点位于环的入口之前
func constructTwoLinkedListBothHasCycleAndIntersection() (l1, l2 *LinkedListNode) {
	node, node2 := &LinkedListNode{Val: 4}, &LinkedListNode{Val: 5}
	node.Next, node2.Next = node2, node
	node3 := &LinkedListNode{Val: 6, Next: node}
	l1, l2 = &LinkedListNode{Val: 1, Next: node3}, &LinkedListNode{Val: 3, Next: node3}
	return l1, l2
}

//构造两个都有环的链表，但是两个链表都是相交的且相交的起点位于环上
func constructTwoLinkedListBothHasCycleAndIntersectionII() (l1, l2 *LinkedListNode) {
	node, node2 := &LinkedListNode{Val: 4}, &LinkedListNode{Val: 5}
	node.Next, node2.Next = node2, node
	l1, l2 = &LinkedListNode{Val: 1, Next: node}, &LinkedListNode{Val: 3, Next: &LinkedListNode{Val: 6, Next: node2}}
	return l1, l2
}

2021-11-27 LeetCode

两个全排列的题目

第一道题

2020-11-28 LeetCode算法

golang刷回溯遇到的坑

情况说明

今天在做LeetCode-46题，DFS深搜写完，最后结果愣是不对，中途调试发现每次满足结束递归条件时得到的结果都是对的，但是后面一有满足条件就会造成最终的结果不对。

下面是46题的错误代码，中途调试打印cur可以正确打印，但是打印ret每次都会改变

func permute(nums []int) [][]int {
	if len(nums) == 0 {
		return nil
	}
	used, cur, res := make([]bool, len(nums)), []int{}, [][]int{}

	generatePermutation(&nums, &res, &used, cur)
	return res
}

func generatePermutation(nums *[]int, res *[][]int, used *[]bool, cur []int) {

	if len(*nums) == len(cur) {
		//just for test
		fmt.Printf("添加元素------>")
		for _, val := range cur {
			fmt.Printf("%v\t", val)
		}
		fmt.Println(cur)
		temp := make([]int, len(*nums))
		copy(temp, cur)
		*res = append(*res, temp)
		//fmt.Println(res)
	}

	//添加正确之后的对比
	//if len(*nums) == len(cur) {
	//	ans := make([]int, len(cur))
	//	copy(ans, cur)
	//	*res = append(*res, ans)
	//	return
	//}

	for i := 0; i < len(*nums); i++ {
		//如果当前值没有使用
		if !(*used)[i] {
			(*used)[i] = true
			cur = append(cur, (*nums)[i])
			//进行递归
			generatePermutation(nums, res, used, cur)
			//到这里说明之前的已经遍历完了
			(*used)[i] = false
			cur = cur[:len(cur)-1]
		}
	}

}

2020-09-06 LeetCode回溯

(LeetCode系列)242字母易位词

字母易位词，指的是两个单词只是字母的排列顺序不同，换言之就是字母的种类数以及字母出现的次数都一致我们重点只需要验证字母出现的次数以及字母的种类数是否一致排序 sorted() 不会改变传入可迭代对象的顺序，而是返回一个排好序的可迭代对象 12def isAnagram(self, s: str, t: str) -> bool: return sorted(s) == sor...

2020-06-05 LeetCode

(LeetCode系列)7整数反转

题意仔细审题，两个关键点 32位有符号整数，需要考虑负数如何处理题中给的注意，考虑是否溢出解法一：逆序累加我们将负数乘以-1，与正数统一处理，之后计算反转的结果之后再确认是否需要乘以-1 报错的代码 123456# 第一次提交：报错，错误测试用例，输入的内容经过反转之后超出了32位有符号整数的边界 def reverse(self, x: int) -> int: ...

2020-06-05 LeetCode

(LeetCode系列)刷题记

两数相加思路：分别求出两个链表都有数字时各个数字的和，如果产生进位，将进位记录在计算下一位的时候加上如果没有产生进位，移动到下一位如果有链表为空，那么直接计算剩余链表的数字与进位的和直到最后两个链表都为空，但是还有进位，此时我们还要再给进位分配一个链表的节点求公共链表之后单独求不为空的链表的解法123456789101112131415def addTwoNumber...

2020-06-05 LeetCode

(LeetCode系列)118杨辉三角

解法解法一(自己的解法，蛮力求解，找关系)发现每一行如果大于2个元素两边都用1填充，并且其他位置的元素的关系式如下： ele[i][j] = ele[i-1][j-1] + ele[i-1][j] ele[i][j] = 1 当且仅当j=0或j=i时 12345678910111213141516class Solution: def generate(self, numRow...

2020-05-26 LeetCodedp

(LeetCode系列)191位1的个数

解决方法方法一：一位一位判断我们对输入的数字从最后一位开始，每次和1进行与运算，之后每次左移1位为什么每次不右移1位呢？因为如果对于有符号整数，每次右移我们前面会填充符号位(正数填0负数填1)因此对于后面的计数会有影响，而左移对于有符号整数都只是在右边填充0 区分逻辑右移，逻辑左移与算数右移，算数左移：逻辑左移=算数左移，右边统一添0 逻辑右移，左边统一添0 算数右移，左...

2020-05-26 LeetCode位运算

1 / 2