赞
踩
剑指offer(专项突破版)-go语言实现,适合Java转go程序员参考
func twoSum(numbers []int, target int) []int {
left := 0
right := len(numbers)-1
for left < right && numbers[left] + numbers[right] != target {
if numbers[left] + numbers[right] < target{
left++
}else {
right--
}
}
return []int{left, right}
}
注意:数组的长度是数组类型的一部分,所以[3]int和[4]int是两种不同的数组类型。所以本题中[]int{left, right}中[]里不能加数字,否则会报错,例如[2]int 无法匹配[]int,所以该如何初始化一个int数组呢?如下所示。
//全局:
var arr0 [5]int = [5]int{1, 2, 3}
var arr1 = [5]int{1, 2, 3, 4, 5}
var arr2 = [...]int{1, 2, 3, 4, 5, 6}
var str = [5]string{3: "hello world", 4: "tom"}
//局部:
a := [3]int{1, 2} // 未初始化元素值为 0。
b := [...]int{1, 2, 3, 4} // 通过初始化值确定数组长度。
c := [5]int{2: 100, 4: 200} // 使用索引号初始化元素。
d := [...]struct {
name string
age uint8
}{
{"user1", 10}, // 可省略元素类型。
{"user2", 20}, // 别忘了最后一行的逗号。
}
func threeSum(nums []int) [][]int {
res := [][]int{}
if len(nums) >= 3 {
sort.Ints(nums)
i := 0
for i < len(nums) - 2{
res = twoSum(nums, i, res)
temp := nums[i]
for i < len(nums) && nums[i] == temp{
i++
}
}
}
return res
}
func twoSum(nums []int, i int, res [][]int) [][]int {
j := i+1
k := len(nums)-1
for j < k{
if nums[i] + nums[j] + nums[k] == 0{
res = append(res, []int{nums[i], nums[j], nums[k]})
temp := nums[j]
for nums[j] == temp && j < k {
j++
}
}else if nums[i] + nums[j] + nums[k] < 0{
j++
}else{
k--
}
}
return res
}
这个题目用到了排序,对于goLang排序是sort.Ints(nums),Java是Arrays.sort(nums)
而且不同于Java,twoSum必须要把res返回,这与Java的传引用不同,go是传值的。但是如果不想返回,可以使用指针。
所以这样也行
func threeSum(nums []int) [][]int {
res := [][]int{}
if len(nums) >= 3 {
sort.Ints(nums)
i := 0
for i < len(nums) - 2{
twoSum(nums, i, &res)
temp := nums[i]
for i < len(nums) && nums[i] == temp{
i++
}
}
}
return res
}
func twoSum(nums []int, i int, res *[][]int) {
j := i+1
k := len(nums)-1
for j < k{
if nums[i] + nums[j] + nums[k] == 0{
*res = append(*res, []int{nums[i], nums[j], nums[k]})
temp := nums[j]
for nums[j] == temp && j < k {
j++
}
}else if nums[i] + nums[j] + nums[k] < 0{
j++
}else{
k--
}
}
}
func minSubArrayLen(target int, nums []int) int {
left := 0
sum := 0
minlen := math.MaxFloat64
for right := 0 ; right < len(nums) ; right++{
sum = sum + nums[right]
for left <= right && sum >= target {
minlen = math.Min(minlen, float64(right-left+1))
sum = sum - nums[left]
left++
}
}
if minlen == math.MaxFloat64 {
return 0
}
return int(minlen)
}
这里要注意minlen = math.Min(minlen, float64(right-left+1)) 的输入输出都是float64,所以minlen := math.MaxFloat64 取的是float64,最终返回值是int,所以要强转。
这个不难,由于给定的是正整数,所以只要从左到右乘进去,然后再从左到右除,一个O(n)的时间复杂度就可以搞定。
一个很基础的双指针问题。
func numSubarrayProductLessThanK(nums []int, k int) int {
product := 1
left := 0
count := 0
for right := 0 ; right < len(nums) ; right++{
product *= nums[right]
for left <= right && product >= k{
product /= nums[left]
left++// 注意left是跟随向右走的
}
if right >= left{
count += right-left+1
}else{
count += 0
}
}
return count
}
这个有个问题,求连续数组的和,那不能排序;整数数组,可能有负数,所以不能用双指针,因为可能越加越少;
所以要用哈希表,存sumToCount,
func subarraySum(nums []int, k int) int {
sumToCount := make(map[int]int, len(nums))
sumToCount[0] = 1
sum := 0
count := 0
for _, num := range nums{
sum += num
v, ok := sumToCount[sum-k]
if ok{
count += v // 存在一个sum-k,就加一个,这里是为了统计结果
}
// v, ok = sumToCount[sum]
// if !ok{
// v = 0
// }
// 用这一行,代替上边一段,因为如果获取结果失败,刚好把v设为默认值0
v, _ = sumToCount[sum]
sumToCount[sum] = v+1 //这里才是统计sum
}
return count
}
func findMaxLength(nums []int) int {
sumToIndex := make(map[int]int, len(nums))
sumToIndex[0] = -1
sum := 0
maxLength := 0
for i := 0 ; i < len(nums) ; i++{
if nums[i] == 0{
sum += -1
}else{
sum += 1
}
if index, ok := sumToIndex[sum]; ok{
temp := i - index
if maxLength < temp {
maxLength = temp
}
}else{
sumToIndex[sum] = i
}
}
return maxLength
}
关键点,累加到当前位置得到一个sum,判断是否之前已经有过这样一个累加值。如果有,那么到到上一个下标之间这段就是最长子数组。
goLang的一个语法糖,if 可以用;分割,分号之后做判断条件。
func pivotIndex(nums []int) int {
total := 0
for _, num := range nums {
total += num
}
sum := 0
for i, length := 0, len(nums); i < length; i++ {
sum += nums[i]
if( sum-nums[i] == total - sum){
return i
}
}
return -1
}
注意Java中求数组和可以用流,例如:
int total = Arrays.stream(nums).sum();
这个题没有调试出来!!!
后来应该是用chatGPT改出来的,但是不知道为什么csdn没有保存上一次的修改记录
type NumMatrix struct {
sums [][]int
}
func Constructor(matrix [][]int) NumMatrix {
rows, cols := len(matrix), len(matrix[0])
sums := make([][]int, rows+1)
for i := range sums {
sums[i] = make([]int, cols+1)
}
for i := 1; i <= rows; i++ {
for j := 1; j <= cols; j++ {
sums[i][j] = matrix[i-1][j-1] + sums[i-1][j] + sums[i][j-1] - sums[i-1][j-1]
}
}
return NumMatrix{sums: sums}
}
func (this *NumMatrix) SumRegion(row1 int, col1 int, row2 int, col2 int) int {
return this.sums[row2+1][col2+1] - this.sums[row1][col2+1] - this.sums[row2+1][col1] + this.sums[row1][col1]
}
/**
* Your NumMatrix object will be instantiated and called as such:
* obj := Constructor(matrix);
* param_1 := obj.SumRegion(row1,col1,row2,col2);
*/
func isPalindrome(s string) bool {
left := 0
right := len(s)-1
for left < right {
ch1 := s[left]
ch2 := s[right]
if !isLetterOrDigit(ch1) {
left++
} else if !isLetterOrDigit(ch2) {
right--
}else {
ch1 = toLowerCase(ch1)
ch2 = toLowerCase(ch2)
if ch1 != ch2{
return false
}
left++
right--
}
}
return true
}
func isLetterOrDigit(ch byte) bool{
if (byte('A') <= ch && ch <= byte('Z')) || (byte('a') <= ch && ch <= byte('z')) || (byte('0') <= ch && ch <= byte('9')) {
return true
}
return false
}
func toLowerCase(ch byte) byte{
if byte('A') <= ch && ch <= byte('Z'){
return ch - byte('A') + byte('a')
}
return ch
}
字符处理:
判断是字母或数字
Java
Character.isLetterOrDigit(ch);
goLang
需要自己判断
主要goLang的字符是byte
字符串中取某个值
Java
str.charAt(index);
goLang
ch1 := s[left]
func validPalindrome(s string) bool {
left := 0
right := len(s)-1
for left < right {
ch1 := s[left]
ch2 := s[right]
if ch1 != ch2 {
s1 := s[left: right]
s2 := s[left+1: right+1]
fmt.Println(s1)
fmt.Println(s2)
return (isPalindrome(s1) || isPalindrome(s2))
}
left++
right--
}
return true
}
func isPalindrome(s string) bool {
left := 0
right := len(s)-1
for left < right {
ch1 := s[left]
ch2 := s[right]
if !isLetterOrDigit(ch1) {
left++
} else if !isLetterOrDigit(ch2) {
right--
}else {
ch1 = toLowerCase(ch1)
ch2 = toLowerCase(ch2)
if ch1 != ch2{
return false
}
left++
right--
}
}
return true
}
func isLetterOrDigit(ch byte) bool{
if (byte('A') <= ch && ch <= byte('Z')) || (byte('a') <= ch && ch <= byte('z')) || (byte('0') <= ch && ch <= byte('9')) {
return true
}
return false
}
func toLowerCase(ch byte) byte{
if byte('A') <= ch && ch <= byte('Z'){
return ch - byte('A') + byte('a')
}
return ch
}
func countSubstrings(s string) int {
if s == "" || len(s) == 0 {
return 0
}
count := 0
for i := 0 ; i < len(s) ; i++{
count += countPalindrome(s, i, i)
count += countPalindrome(s, i, i+1)
}
return count
}
func countPalindrome(s string, start int, end int) int {
count := 0
for start >= 0 && end < len(s) && s[start] == s[end] {
count++
start--
end++
}
return count
}
书中Java代码第一个边界判断是判断s==null
,如果go写s==nil
就有问题,因为string不匹配nil,string是有默认值的,如果需要判空,那么就写s==""
。
这个题还可以用动态规划来实现,如下。
func countSubstrings(s string) int {
n := len(s)
dp := make([][]bool, n)
for i := 0; i < n; i++ {
dp[i] = make([]bool, n)
}
count := 0
for j := 0; j < n; j++ {
for i := 0; i <= j; i++ {
if s[i] == s[j] && (j-i < 2 || dp[i+1][j-1]) {
dp[i][j] = true
count++
}
}
}
return count
}
可以用一个二维数组dp,其中dp[i][j]表示以i开头、以j结尾的子串是否为回文子串。对于一个子串s,如果s[i]==s[j]并且s[i+1:j-1]也是回文串,那么s[i:j]就是一个回文子串。
因此,我们可以得到状态转移方程:
dp[i][j] = true, if s[i]==s[j] and (j-i<2 or dp[i+1][j-1]==true)
其中(j-i<2)表示长度为1或者2的子串,因为长度为1或者2的子串只需要判断首尾两个字符是否相同即可。另外,我们需要用一个变量count来记录回文子串的数量。
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func removeNthFromEnd(head *ListNode, n int) *ListNode {
dummy := &ListNode{
0,
nil,
}
dummy.Next = head
front := head
back := dummy
for i := 0 ; i < n ; i++ {
front = front.Next // 为什么可以一直next,因为条件是 n <= sz
}
for front != nil {
front = front.Next
back = back.Next
}
back.Next = back.Next.Next
return dummy.Next
}
最初对dummy初始化的时候写成了
dummy := ListNode{
0,
nil,
}
这导致了dummy是个ListNode,但是他的Next是指针,在执行back = back.Next
的时候失败,利用chatGPT找到了问题。
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func detectCycle(head *ListNode) *ListNode {
inLoop := getNodeInLoop(head)
if inLoop == nil {
return nil
}
node := head
for node != inLoop {
node = node.Next
inLoop = inLoop.Next
}
return node
}
func getNodeInLoop(head *ListNode) *ListNode {
if head == nil || head.Next == nil {
return nil
}
slow := head.Next
fast := slow.Next
for slow != nil && fast != nil {
if slow == fast {
return slow
}
slow = slow.Next
fast = fast.Next
if fast != nil {
fast = fast.Next
}
}
return nil
}
快慢指针判断是否成环,然后一个从头,一个从交汇地往前走,再次交汇就是入口
这个是第一次涉及到结构体,第一次出错特别多,直接在程序中注释
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func getIntersectionNode(headA, headB *ListNode) *ListNode {
count1 := countList(headA)
count2 := countList(headB)
delta := math.Abs(count1-count2) // math.Abs()的入参和返回值都是float64
var longer *ListNode // 为了要将headA赋给longer,longer也应该是一个指针
var shorter *ListNode
if count1 > count2 { longer = headA } else { longer = headB} // goLang没有三元表达式,必须强制使用if
if count1 > count2 { shorter = headB } else { shorter = headA}
node1 := longer
for i := 0.0 ; i < delta; i++{
node1 = node1.Next
}
node2 := shorter
for node1 != node2 {
node1 = node1.Next
node2 = node2.Next
}
return node1
}
func countList(head *ListNode) float64{
count := 0.0
for head != nil {
count++
head = head.Next
}
return count
}
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func reverseList(head *ListNode) *ListNode {
var prev *ListNode // prev := nil不可以
cur := head
for cur != nil {
next := cur.Next
cur.Next = prev
prev = cur
cur = next
}
return prev
}
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
l1 = reverseList(l1)
l2 = reverseList(l2)
reversedHead := addReversed(l1, l2)
return reverseList(reversedHead)
}
func reverseList(head *ListNode) *ListNode {
var prev *ListNode // prev := nil不可以
cur := head
for cur != nil {
next := cur.Next
cur.Next = prev
prev = cur
cur = next
}
return prev
}
func addReversed(head1 *ListNode, head2 *ListNode) *ListNode {
dummy := &ListNode{
0,
nil,
}
sumNode := dummy
carry := 0
for head1 != nil || head2 != nil {
sum := 0
if head1 != nil {
sum += head1.Val
}
if head2 != nil {
sum += head2.Val
}
sum += carry
if sum >= 10 {
carry = 1
}else {
carry = 0
}
if sum >= 10 {
sum = sum - 10
}
newNode := &ListNode{
sum,
nil,
}
sumNode.Next = newNode
sumNode = sumNode.Next
if head1 != nil {
head1 = head1.Next
}
if head2 != nil {
head2 = head2.Next
}
}
if carry > 0 {
sumNode.Next = &ListNode{
carry,
nil,
}
}
return dummy.Next
}
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func reorderList(head *ListNode) {
dummy := &ListNode{
0,
head,
}
fast, slow := dummy, dummy
for fast != nil && fast.Next != nil {
slow = slow.Next
fast = fast.Next
if fast.Next != nil {
fast = fast.Next
}
}
temp := slow.Next
slow.Next = nil
link(head, reverseList(temp), dummy)
}
func link(node1, node2, head *ListNode) {
prev := head
for node1 != nil && node2 != nil {
temp := node1.Next
prev.Next = node1
node1.Next = node2
prev = node2
node1 = temp
node2 = node2.Next
}
if node1 != nil {
prev.Next = node1
}
}
func reverseList(head *ListNode) *ListNode {
var prev *ListNode // prev := nil不可以
cur := head
for cur != nil {
next := cur.Next
cur.Next = prev
prev = cur
cur = next
}
return prev
}
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func isPalindrome(head *ListNode) bool {
if head == nil || head.Next == nil {
return true
}
slow := head
fast := head.Next
for fast.Next != nil && fast.Next.Next != nil {
fast = fast.Next.Next
slow = slow.Next
}
secondHalf := slow.Next
if fast.Next != nil{
secondHalf = slow.Next.Next // 当有奇数个节点,舍弃掉第一条链的最后一个
}
slow.Next = nil // 断开第一条和第二条的连接
return equals(secondHalf, reverseList(head))
}
func reverseList(head *ListNode) *ListNode {
var prev *ListNode
cur := head;
for cur != nil {
next := cur.Next
cur.Next = prev
prev = cur
cur = next
}
return prev
}
func equals(head1, head2 *ListNode) bool{
for head1 != nil && head2 != nil {
if head1.Val != head2.Val{
return false
}
head1 = head1.Next
head2 = head2.Next
}
return head1 == nil && head2 == nil
}
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public boolean isPalindrome(ListNode head) {
if (head == null || head.next == null){
return true;
}
ListNode slow = head;
ListNode fast = head.next;
while (fast.next != null && fast.next.next != null){
fast = fast.next.next;
slow = slow.next;
}
ListNode secondHalf = slow.next;
if (fast.next != null){
secondHalf = slow.next.next; // 当有奇数个节点,舍弃掉第一条链的最后一个
}
slow.next = null; // 断开第一条和第二条的连接
return equals(secondHalf, reverseList(head));
}
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode cur = head;
while (cur != null){
ListNode next = cur.next;
cur.next = prev;
prev = cur;
cur = next;
}
return prev;
}
private boolean equals(ListNode head1, ListNode head2){
while (head1 != null && head2 != null){
if (head1.val != head2.val){
return false;
}
head1 = head1.next;
head2 = head2.next;
}
return head1 == null && head2 == null;
}
// class ListNode {
// int val;
// ListNode next;
//
// ListNode(int x) {
// val = x;
// next = null;
// }
// }
}
思考:为什么这里要判断边界,24题不需要,仅仅是因为返回值不同吗?这里返回boolean,24返回链表
这个题用了快慢指针,快慢指针通常用于解决链表成环的问题,例如22题。
/**
* Definition for a Node.
* type Node struct {
* Val int
* Prev *Node
* Next *Node
* Child *Node
* }
*/
func flatten(root *Node) *Node {
flattenGetTail(root)
return root
}
func flattenGetTail(head *Node) *Node {
node := head
tail := &Node{
0, nil, nil, nil,
}
for node != nil {
next := node.Next
if node.Child != nil {
child := node.Child
childTail := flattenGetTail(node.Child)
node.Child = nil
node.Next = child
child.Prev = node
childTail.Next = next
if next != nil {
next.Prev = childTail
}
tail = childTail
}else {
tail = node
}
node = next
}
return tail
}
/**
* Definition for a Node.
* type Node struct {
* Val int
* Next *Node
* }
*/
func insert(head *Node, x int) *Node {
node := &Node{
x, nil,
}
if head == nil {
head = node
head.Next = head
}else if head.Next == head {
head.Next = node
node.Next = head
}else {
insertCore(head, node)
}
return head
}
func insertCore(head, node *Node) {
cur, next, biggest := head, head.Next, head
for !(cur.Val <= node.Val && next.Val >= node.Val) && next != head {
cur = next
next = next.Next
if cur.Val >= biggest.Val {
biggest = cur
}
}
if cur.Val <= node.Val && next.Val >= node.Val {
cur.Next = node
node.Next = next
}else {
node.Next = biggest.Next
biggest.Next = node
}
}
先贴chatGPT给的正确答案
这里要特别注意随机数生成的写法,否则很容易报
panic: invalid argument to Intn
math/rand.(*Rand).Intn(0x8?, 0x4b4560?)
rand.go, line 168
math/rand.Intn(...)
rand.go, line 337
main.(*RandomizedSet).GetRandom(0xc00005cd80)
solution.go, line 45
main.(*DriverSolution).Helper_Select_Method(0x4b76e0?, {0xc000014080?, 0x0?}, {0x5ac9f8?, 0x7?, 0x8?}, 0xc00005cd80?)
solution.go, line 74
main.(*DriverSolution).Helper(0xc0000560c0?, {0xc000076120, 0x8, 0x4b3ee0?}, {0xc000084000, 0x8, 0xc000014038?})
solution.go, line 126
main.main()
solution.go, line 171
这个错误和导包没关系,leetcode会自动导包。
type RandomizedSet struct {
numToLocation map[int]int
nums []int
}
/** Initialize your data structure here. */
func Constructor() RandomizedSet {
numToLocation := make(map[int]int)
nums := make([]int, 0)
rand.Seed(time.Now().UnixNano())
return RandomizedSet{numToLocation, nums}
}
/** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
func (this *RandomizedSet) Insert(val int) bool {
_, ok := this.numToLocation[val]
if ok {
return false
}
this.numToLocation[val] = len(this.nums)
this.nums = append(this.nums, val)
return true
}
/** Removes a value from the set. Returns true if the set contained the specified element. */
func (this *RandomizedSet) Remove(val int) bool {
loc, ok := this.numToLocation[val]
if !ok {
return false
}
this.numToLocation[this.nums[len(this.nums)-1]] = loc
delete(this.numToLocation, val)
this.nums[loc] = this.nums[len(this.nums)-1]
this.nums = this.nums[:len(this.nums)-1]
return true
}
/** Get a random element from the set. */
func (this *RandomizedSet) GetRandom() int {
loc := rand.Intn(len(this.nums))
return this.nums[loc]
}
type LRUCache struct {
head *LRUListNode
tail *LRUListNode
lruMap map[int]*LRUListNode
capacity int
}
type LRUListNode struct {
Key int
Val int
Next *LRUListNode
Prev *LRUListNode
}
func Constructor(capacity int) LRUCache {
head := &LRUListNode{-1, -1, nil, nil}
tail := &LRUListNode{-1, -1, nil, head}
head.Next = tail
lruMap := make(map[int]*LRUListNode)
return LRUCache{head, tail, lruMap, capacity}
}
func (this *LRUCache) Get(key int) int {
node, ok := this.lruMap[key]
if !ok {
return -1
}
this.moveToTail(node, node.Val)
return node.Val
}
func (this *LRUCache) moveToTail(node *LRUListNode, newVal int) {
this.deleteNode(node)
node.Val = newVal
this.insertToTail(node)
}
func (this *LRUCache) deleteNode(node *LRUListNode) {
node.Prev.Next = node.Next
node.Next.Prev = node.Prev
}
func (this *LRUCache) insertToTail(node *LRUListNode) {
this.tail.Prev.Next = node
node.Prev = this.tail.Prev
node.Next = this.tail
this.tail.Prev = node
}
func (this *LRUCache) Put(key int, value int) {
if _, ok := this.lruMap[key]; ok {
this.moveToTail(this.lruMap[key], value)
} else {
if len(this.lruMap) == this.capacity {
toBeDeleted := this.head.Next
this.deleteNode(toBeDeleted)
delete(this.lruMap, toBeDeleted.Key)
}
node := &LRUListNode{key, value, nil, nil}
this.insertToTail(node)
this.lruMap[key] = node
}
}
/**
* Your LRUCache object will be instantiated and called as such:
* obj := Constructor(capacity);
* param_1 := obj.Get(key);
* obj.Put(key,value);
*/
func isAnagram(s string, t string) bool {
if len(s) != len(t) || s == t{
return false
}
counts := [26]int{} // 初始化一个数组
for _, ch := range s { // 遍历一个字符串
counts[ch-'a']++
}
for _, ch := range t {
if counts[ch-'a'] == 0{
return false
}
counts[ch-'a']--
}
return true
}
import "sort"
func groupAnagrams(strs []string) [][]string {
groups := make(map[string][]string)
for _, str := range strs {
sorted := []byte(str)
sort.Slice(sorted, func(i, j int) bool {
return sorted[i] < sorted[j]
})
stringArr, ok := groups[string(sorted)]
if !ok {
stringArr = make([]string, 0)
}
stringArr = append(stringArr, str)
groups[string(sorted)] = stringArr
}
res := [][]string{}
for _, v := range groups {
res = append(res, v)
}
return res
}
这里需要参照 剑指 Offer II 007. 数组中和为 0 的三个数
,这里也用到了排序包sort,但是这个包里没有 sort.Bytes 这个函数。很奇葩的一个事情,chatGPT第一次回答的时候跟我说有这个函数,后边他又自我修正了。实际应该使用sort.Slice()。
func isAlienSorted(words []string, order string) bool {
orderArray := [26]int{}
for i := 0 ; i < len(order) ; i++{
orderArray[order[i]-'a'] = i
}
for i := 0 ; i < len(words)-1 ; i++{ // 注意边界
if !isSorted(words[i], words[i+1], orderArray){
return false
}
}
return true
}
func isSorted(word1,word2 string, order [26]int) bool{
i := 0
for ; i < len(word1) && i < len(word2) ; i++{
ch1 := word1[i];
ch2 := word2[i];
if order[ch1-'a'] < order[ch2-'a']{
return true
}
if order[ch1-'a'] > order[ch2-'a']{
return false
}
}
return i == len(word1) // 前缀相同,长度不同。如果等于第一个的长度,那说明第一个遍历结束,第一个比第二个短,也就是第一个在前
}
func findMinDifference(timePoints []string) int {
if len(timePoints) > 1440 {
return 0
}
minuteFlags := [1440]bool{}
for _, time := range timePoints {
hhmm := strings.Split(time, ":")
hh, _ := strconv.Atoi(hhmm[0])
mm, _ := strconv.Atoi(hhmm[1])
min := hh*60 + mm
if minuteFlags[min] {
return 0
}
minuteFlags[min] = true
}
return findMinDifferenceCore(minuteFlags)
}
func findMinDifferenceCore(minuteFlags [1440]bool) int {
minDiff := 1440
prev := -1
first := 1440
last := -1
for i := 0 ; i < 1440 ; i++ {
if minuteFlags[i] {
if prev >= 0 && i-prev < minDiff{
minDiff = i-prev
}
prev = i
if i < first {
first = i
}
if i > last {
last = i
}
}
}
if first + 1440 - last < minDiff {
minDiff = first + 1440 - last
}
return minDiff
}
先贴正确答案,下边就是错的了
func findMinDifference(timePoints []string) int {
if len(timePoints) > 1440 {
return 0
}
minuteFlags := [1440]bool{}
for _, time := range timePoints {
hhmm := strings.Split(time, ":")
hh, _ := strconv.Atoi(hhmm[0])
mm, _ := strconv.Atoi(hhmm[1])
min := hh*60 + mm
_, ok := minuteFlags[min] // 这里是个数组,被我当成map了
if ok { // 就算是map也不能用ok,这里要判断是否重复,如果重复表示两个值之间的差为0
return 0
}
minuteFlags[min] = true
}
return findMinDifferenceCore(minuteFlags)
}
func findMinDifferenceCore(minuteFlags [1440]bool) int {
minDiff := 1439
prev := -1
first := 1439
last := -1
for i := 0 ; i < 1440 ; i++ {
flag, _ := minuteFlags[i]
if flag {
if prev >= 0 && i-prev < minDiff{
minDiff = i-prev
}
prev = i
if i < first {
first = i
}
if i > last {
last = i
}
}
}
if first + 1440 - last < minDiff {
minDiff = first + 1440 - last
}
return minDiff
}
Java的Stack
函数 | 函数功能 |
---|---|
push(e) | 入栈 |
pop | 弹栈 |
peek | 返回栈顶,但不弹栈 |
但是goLang怎么办呢,可以用切片
func evalRPN(tokens []string) int {
stack := make([]int, 0, 4)
for _, token := range tokens {
switch token {
case "+" , "-" , "*" , "/" : // 第一个错误的点,这里和Java不一样,Java是顺着case xx
num1 := stack[len(stack)-2]
num2 := stack[len(stack)-1] // 第二个错误的点,这两个值不能反
stack = stack[:len(stack)-2]
stack = append(stack, calculate(num1, num2, token))
default :
tokenInt, _ := strconv.Atoi(token)
stack = append(stack, tokenInt)
}
}
return stack[len(stack)-1]
}
func calculate(num1 int, num2 int, oper string) int {
switch oper {
case "+" :
return num1 + num2
case "-" :
return num1 - num2
case "*" :
return num1 * num2
case "/" :
return num1 / num2
default :
return 0
}
}
func asteroidCollision(asteroids []int) []int {
stack := make([]int, 0, 4)
for _, asteroid := range asteroids {
for len(stack) > 0 && stack[len(stack)-1] > 0 && stack[len(stack)-1] < -asteroid {
stack = stack[:len(stack)-1]
}
if len(stack) > 0 && asteroid < 0 && stack[len(stack)-1] == -asteroid {
stack = stack[:len(stack)-1]
} else if asteroid > 0 || len(stack) == 0 || stack[len(stack)-1] < 0 {
stack = append(stack, asteroid)
}
}
return stack
}
func dailyTemperatures(temperatures []int) []int {
res := make([]int, len(temperatures), len(temperatures))
stack := make([]int, 0, len(temperatures))
for i := 0 ; i < len(temperatures) ; i++ {
for len(stack) > 0 && temperatures[i] > temperatures[stack[len(stack)-1]] {
prev := stack[len(stack)-1]
res[prev] = i - prev
stack = stack[:len(stack)-1]
}
stack = append(stack, i)
}
return res
}
Queue的方法
操作 | 抛异常 | 不抛异常 |
---|---|---|
插入元素 | add(e) | offer(e) |
删除元素 | remove | poll |
返回最前面的元素 | element | peek |
可以看出Java处理队列问题真简单,但是goLang没有队列。。。
goLang处理队列问题通常是切片或者链表,大概相当与ArrayList和LinkedList
参考文章golang的两种队列实现方式
class MovingAverage {
private Queue<Integer> nums;
private int capacity;
private int sum;
/** Initialize your data structure here. */
public MovingAverage(int size) {
nums = new LinkedList<>();
capacity = size;
}
public double next(int val) {
nums.offer(val);
sum += val;
if (nums.size() > capacity){
sum -= nums.poll();
}
return (double) sum / nums.size();
}
}
/**
* Your MovingAverage object will be instantiated and called as such:
* MovingAverage obj = new MovingAverage(size);
* double param_1 = obj.next(val);
*/
type MovingAverage struct {
queue []int
cap int
sum int
}
/** Initialize your data structure here. */
func Constructor(size int) MovingAverage {
var ins = MovingAverage{
make([]int, 0, size+2),
size,
0,
}
return ins
}
func (this *MovingAverage) Next(val int) float64 {
this.queue = append(this.queue, val)
this.sum += val
if len(this.queue) > this.cap {
this.sum -= this.queue[0]
this.queue = this.queue[1:this.cap+1]
}
return float64(this.sum)/float64(len(this.queue))
}
/**
* Your MovingAverage object will be instantiated and called as such:
* obj := Constructor(size);
* param_1 := obj.Next(val);
*/
这真的是一种奇怪的写法,通过切片的截取实现了和队列一样的先进先出效果,我朋友跟我讲切片就是队列,那就先这样吧。
这里要注意几个点:
初始化结构体的时候,最后一个元素后边还要加",",我不知道只是goLand的特性还是就该如此。
切片的截取则是前包后不包,所以cap要+1
import java.util.LinkedList;
import java.util.Queue;
//leetcode submit region begin(Prohibit modification and deletion)
class RecentCounter {
private Queue<Integer> times;
private int windowSize;
public RecentCounter() {
times = new LinkedList<>();
windowSize = 3000;
}
public int ping(int t) {
times.offer(t);
while (times.peek() + windowSize < t){
times.poll();
}
return times.size();
}
}
/**
* Your RecentCounter object will be instantiated and called as such:
* RecentCounter obj = new RecentCounter();
* int param_1 = obj.ping(t);
*/
//leetcode submit region end(Prohibit modification and deletion)
type RecentCounter struct {
times []int
windowSize int
}
func Constructor() RecentCounter {
var ins = RecentCounter{
make([]int, 0, 10000),
3000,
}
return ins
}
func (this *RecentCounter) Ping(t int) int {
this.times = append(this.times, t)
for this.times[0] + this.windowSize < t {
this.times = this.times[1:]
}
return len(this.times)
}
/**
* Your RecentCounter object will be instantiated and called as such:
* obj := Constructor();
* param_1 := obj.Ping(t);
*/
搞明白了41题,42题就很容易做了,就是个用切片代替Java-Queue的做法。
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
type CBTInserter struct {
Queue []*TreeNode
Root *TreeNode
}
func Constructor(root *TreeNode) CBTInserter {
queue := make([]*TreeNode, 0, 2)
queue = append(queue, root)
for queue[0].Left != nil && queue[0].Right != nil {
node := queue[0]
queue = append(append(queue[1:], node.Left), node.Right)
}
return CBTInserter{
queue,root,
}
}
func (this *CBTInserter) Insert(v int) int {
parent := this.Queue[0]
node := &TreeNode{
v, nil, nil,
}
if parent.Left == nil {
parent.Left = node
}else {
parent.Right = node
this.Queue = append(append(this.Queue[1:], parent.Left), parent.Right)
}
return parent.Val
}
func (this *CBTInserter) Get_root() *TreeNode {
return this.Root
}
/**
* Your CBTInserter object will be instantiated and called as such:
* obj := Constructor(root);
* param_1 := obj.Insert(v);
* param_2 := obj.Get_root();
*/
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func largestValues(root *TreeNode) []int {
queue1 := make([]*TreeNode, 0, 10)
queue2 := make([]*TreeNode, 0, 10)
res := make([]int, 0, 10)
if root == nil {
return res
}
queue1 = append(queue1, root)
max := queue1[0].Val
for len(queue1) > 0 {
node := queue1[0]
queue1 = queue1[1:]
if node.Val > max {
max = node.Val
}
if node.Left != nil {
queue2 = append(queue2, node.Left)
}
if node.Right != nil {
queue2 = append(queue2, node.Right)
}
if len(queue1) == 0 {
res = append(res, max)
queue1 = queue2
if len(queue1) > 0 {
max = queue1[0].Val
}
queue2 = make([]*TreeNode, 0, 10)
}
}
return res
}
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func findBottomLeftValue(root *TreeNode) int {
queue1 := make([]*TreeNode, 0, 10)
queue2 := make([]*TreeNode, 0, 10)
queue1 = append(queue1, root)
bottomLeft := queue1[0]
for len(queue1) > 0 {
node := queue1[0]
queue1 = queue1[1:]
if node.Left != nil {
queue2 = append(queue2, node.Left)
}
if node.Right != nil {
queue2 = append(queue2, node.Right)
}
if len(queue1) == 0 {
queue1 = queue2
queue2 = make([]*TreeNode, 0, 10)
if len(queue1) > 0 {
bottomLeft = queue1[0]
}
}
}
return bottomLeft.Val
}
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func rightSideView(root *TreeNode) []int {
queue1 := make([]*TreeNode, 0, 10)
queue2 := make([]*TreeNode, 0, 10)
res := make([]int, 0, 10)
if root == nil {
return res
}
queue1 = append(queue1, root)
node := queue1[0]
for len(queue1) > 0 {
node = queue1[0]
queue1 = queue1[1:]
if node.Left != nil {
queue2 = append(queue2, node.Left)
}
if node.Right != nil {
queue2 = append(queue2, node.Right)
}
if len(queue1) == 0 {
queue1 = queue2
queue2 = make([]*TreeNode, 0, 10)
res = append(res, node.Val)
}
}
return res
}
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func pruneTree(root *TreeNode) *TreeNode {
if root == nil {
return root
}
root.Left = pruneTree(root.Left)
root.Right = pruneTree(root.Right)
if root.Left == nil && root.Right == nil && root.Val == 0 {
return nil
}
return root
}
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func sumNumbers(root *TreeNode) int {
return sumNumbersCore(root, 0)
}
func sumNumbersCore(root *TreeNode, path int) int {
if root == nil {
return 0
}
path = path * 10 + root.Val
if root.Left == nil && root.Right == nil {
return path
}
return sumNumbersCore(root.Left, path) + sumNumbersCore(root.Right, path)
}
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func pathSum(root *TreeNode, targetSum int) int {
sum2cntMap := &map[int]int{
0: 1,
}
return dfs(root, targetSum, sum2cntMap, 0)
}
func dfs(root *TreeNode, sum int, sum2cntMap *map[int]int, path int) int {
if root == nil {
return 0
}
path += root.Val
count, ok := (*sum2cntMap)[path - sum]
if !ok {
count = 0
}
pathCnt, ok := (*sum2cntMap)[path]
if ok {
(*sum2cntMap)[path] = pathCnt+1
}else {
(*sum2cntMap)[path] = 1
}
count += dfs(root.Left, sum, sum2cntMap, path)
count += dfs(root.Right, sum, sum2cntMap, path)
pathCnt, _ = (*sum2cntMap)[path]
(*sum2cntMap)[path] = pathCnt - 1
return count
}
class Solution {
public TreeNode increasingBST(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
TreeNode prev = null;
TreeNode first = null;
while (cur != null || !stack.isEmpty()) {
// 已示例1为例,从栈底到栈顶依次是5321
while (cur != null) {
stack.push(cur);
cur = cur.left;
}
cur = stack.pop();
if (prev != null) {
// 只有初始化的时候prev才是null,之后总是有值的
prev.right = cur;
} else {
// 这里只会进来一次,然后指向最左子节点
first = cur;
}
prev = cur;
cur.left = null;
cur = cur.right;
}
return first;
}
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {
}
TreeNode(int val) {
this.val = val;
}
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
}
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func increasingBST(root *TreeNode) *TreeNode {
stack := make([]*TreeNode, 0, 0)
cur := root
var prev *TreeNode
var first *TreeNode
for cur != nil || len(stack) != 0{
for cur != nil{
stack = append(stack, cur)
cur = cur.Left
}
cur = stack[len(stack)-1]
stack = stack[:len(stack)-1]
if prev != nil{
prev.Right = cur
}else{
first = cur
}
prev = cur
cur.Left = nil
cur = cur.Right
}
return first
}
这是第一次用切片来模拟栈,也是第一次使用指针。
用切片当栈用倒不复杂,出栈的时候len-1把最后一个舍弃掉就可以了。
指针初始化要记住形式 var first * TreeNode。
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func inorderSuccessor(root *TreeNode, p *TreeNode) *TreeNode {
cur := root
var res *TreeNode
for cur != nil {
if cur.Val > p.Val {
res = cur
cur = cur.Left
} else {
cur = cur.Right
}
}
return res
}
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func convertBST(root *TreeNode) *TreeNode {
stack := make([]*TreeNode, 0, 10)
cur := root
sum := 0
for cur != nil || len(stack) > 0 {
for cur != nil {
stack = append(stack, cur)
cur = cur.Right
}
cur = stack[len(stack)-1]
stack = stack[:len(stack)-1]
sum += cur.Val
cur.Val = sum
cur = cur.Left
}
return root
}
type MyCalendar struct {
root *node
}
type node struct {
start, end int
left, right *node
}
func Constructor() MyCalendar {
return MyCalendar{
root: nil,
}
}
func (this *MyCalendar) Book(start int, end int) bool {
if this.root == nil { // 空树直接插入
this.root = &node{start: start, end: end}
return true
}
cur := this.root
var pre *node
for cur != nil {
if cur.start >= end { // 待插入日程在当前日程之前 cur{3,6} {1,2}
pre = cur
cur = cur.left
} else if cur.end <= start { // 待插入日程在当前日程之后 cur{3,6} {7,8}
pre = cur
cur = cur.right
} else { // 重叠 cur{3,6} {4,7} {1,4}
return false
}
}
node := &node{start: start, end: end}
if pre.start >= end {
pre.left = node
} else {
pre.right = node
}
return true
}
/**
* Your MyCalendar object will be instantiated and called as such:
* obj := Constructor();
* param_1 := obj.Book(start,end);
*/
type Trie struct {
children [26]*Trie
end bool
}
/** Initialize your data structure here. */
func Constructor() Trie {
return Trie{}
}
/** Inserts a word into the trie. */
func (this *Trie) Insert(word string) {
cur := this
for i := range word {
if cur.children[word[i]-'a'] == nil {
cur.children[word[i]-'a'] = &Trie{}
}
cur = cur.children[word[i]-'a']
}
cur.end = true
}
/** Returns if the word is in the trie. */
func (this *Trie) Search(word string) bool {
cur := this
for i := range word {
if cur.children[word[i]-'a'] == nil {
return false
}
cur = cur.children[word[i]-'a']
}
return cur.end
}
/** Returns if there is any word in the trie that starts with the given prefix. */
func (this *Trie) StartsWith(prefix string) bool {
cur := this
for i := range prefix {
if cur.children[prefix[i]-'a'] == nil {
return false
}
cur = cur.children[prefix[i]-'a']
}
return true
}
/**
* Your Trie object will be instantiated and called as such:
* obj := Constructor();
* obj.Insert(word);
* param_2 := obj.Search(word);
* param_3 := obj.StartsWith(prefix);
*/
type MapSum struct {
children [26]*MapSum
value int
}
/** Initialize your data structure here. */
func Constructor() MapSum {
return MapSum{}
}
func (this *MapSum) Insert(key string, val int) {
node := this
for i := 0 ; i < len(key) ; i++ {
index := key[i]-'a'
if node.children[index] == nil {
node.children[index] = &MapSum{}
}
node = node.children[index]
}
node.value = val
}
func (this *MapSum) Sum(prefix string) int {
node := this
for i := 0 ; i < len(prefix) ; i++ {
index := prefix[i]-'a'
if node.children[index] == nil {
return 0
}
node = node.children[index]
}
return getSum(node)
}
func getSum(node *MapSum) int {
if node == nil {
return 0
}
res := node.value
for _, child := range node.children {
res += getSum(child)
}
return res
}
/**
* Your MapSum object will be instantiated and called as such:
* obj := Constructor();
* obj.Insert(key,val);
* param_2 := obj.Sum(prefix);
*/
func searchInsert(nums []int, target int) int {
left := 0
right := len(nums)-1
for left <= right{
mid := (left+right)/2
if nums[mid] >= target && (mid == 0 || nums[mid-1] < target){
return mid
}
if nums[mid] >= target {
right = mid - 1
}else{
left = mid + 1
}
}
return len(nums)
}
很基础的二分查找
func peakIndexInMountainArray(arr []int) int {
left := 1
right := len(arr) - 2
for left <= right{
mid := (left + right)/2
if arr[mid] > arr[mid+1] && arr[mid] > arr[mid-1]{
return mid
}
if arr[mid] > arr[mid-1]{
left = mid+1
} else {
right = mid-1
}
}
return -1
}
很基础的二分查找
func mySqrt(x int) int {
left := 1
right := x
for left <= right {
mid := (left + right)/2
if mid <= x / mid && (mid+1) > x / (mid+1) { // 注意:mid*mid <= x 数学上等价,但是会溢出
return mid
}
if mid <= x / mid{
left = mid + 1
}else{
right = mid - 1
}
}
return 0
}
}
func relativeSortArray(arr1 []int, arr2 []int) []int {
var counts [1001]int
for _, num := range arr1 {
counts[num]++
}
i := 0
for _, num := range arr2{
for counts[num] > 0{
arr1[i] = num
i++
counts[num]--
}
}
for num := 0 ; num < len(counts) ; num++{
for counts[num] > 0 {
arr1[i] = num
i++
counts[num]--
}
}
return arr1
}
注意range的写法, 是:= range
并且,arr1[i++]的写法也是错误的
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func sortList(head *ListNode) *ListNode {
if head == nil || head.Next == nil {
return head
}
head2 := split(head)
head = sortList(head)
head2 = sortList(head2)
return merge(head, head2)
}
func split(head *ListNode) *ListNode {
fast := head.Next // fast 初始化为 head.Next 的情况下,如果链表只有一个节点,那么 fast 会指向 nil,循环就会立即停止,而不会出现无限循环的情况。之前我指向head导致了oom
slow := head
for fast != nil && fast.Next != nil {
fast = fast.Next.Next
slow = slow.Next
}
head2 := slow.Next
slow.Next = nil
return head2
}
func merge(head1, head2 *ListNode) *ListNode {
dummy := &ListNode{
0, nil,
}
cur := dummy
for head1 != nil && head2 != nil {
if head1.Val < head2.Val {
cur.Next = head1
head1 = head1.Next
} else {
cur.Next = head2
head2 = head2.Next
}
cur = cur.Next
}
if head1 == nil {
cur.Next = head2
} else {
cur.Next = head1
}
return dummy.Next
}
func combinationSum2(candidates []int, target int) [][]int {
sort.Ints(candidates)
res := [][]int{}
candidation := []int{}
helper(candidates, target, 0, candidation, &res)
return res
}
func helper(candidates []int, target int, i int, candidation []int, res *[][]int) {
if target == 0 {
// 拷贝 candidation 切片的值
tmp := make([]int, len(candidation))
copy(tmp, candidation)
*res = append(*res, tmp)
} else if target > 0 && i < len(candidates) {
// 不选择当前元素
helper(candidates, target, getNext(candidates, i), candidation, res)
// 选择当前元素
newCandidation := append([]int{}, candidation...)
newCandidation = append(newCandidation, candidates[i])
helper(candidates, target-candidates[i], i+1, newCandidation, res)
}
}
func getNext(candidates []int, i int) int {
next := i
for next < len(candidates) && candidates[next] == candidates[i] {
next++
}
return next
}
func minPathSum(grid [][]int) int {
n := len(grid)
m := len(grid[0])
dp := make([][]int, n)
for i := range dp {
dp[i] = make([]int, m)
}
dp[0][0] = grid[0][0]
for j := 1 ; j < m ; j++ {
dp[0][j] = dp[0][j-1] + grid[0][j]
}
for i := 1 ; i < n ; i++ {
dp[i][0] = dp[i-1][0] + grid[i][0]
}
for i := 1 ; i < n ; i++ {
for j := 1 ; j < m ; j++ {
if dp[i-1][j] < dp[i][j-1] {
dp[i][j] = dp[i-1][j] + grid[i][j]
} else {
dp[i][j] = dp[i][j-1] + grid[i][j]
}
}
}
return dp[n-1][m-1]
}
func findOrder(numCourses int, prerequisites [][]int) []int {
graph := make(map[int][]int, 16)
for i := 0 ; i < numCourses ; i++ {
graph[i] = make([]int, 0, 10)
}
inDegrees := make([]int, numCourses)
for _, prerequisite := range prerequisites {
graph[prerequisite[1]] = append(graph[prerequisite[1]], prerequisite[0])
inDegrees[prerequisite[0]]++
}
queue := make([]int, 0, 10)
for i := 0 ; i < numCourses ; i++ {
if inDegrees[i] == 0 {
queue = append(queue, i)
}
}
order := make([]int, 0, 10)
for len(queue) != 0 {
course := queue[0]
queue = queue[1:]
order = append(order, course)
for _, next := range graph[course] {
inDegrees[next]--
if inDegrees[next] == 0 {
queue = append(queue, next)
}
}
}
if len(order) == numCourses {
return order
} else {
return []int{}
}
}
func longestConsecutive(nums []int) int {
fathers := make(map[int]int, len(nums))
counts := make(map[int]int, len(nums))
all := make(map[int]bool, len(nums))
for _, num := range nums {
fathers[num] = num
counts[num] = 1
all[num] = true
}
for _, num := range nums {
if _, ok := all[num+1] ; ok {
union(&fathers, &counts, num, num+1)
}
if _, ok := all[num-1] ; ok {
union(&fathers, &counts, num, num-1)
}
}
longest := 0
for _, length := range counts {
if length > longest {
longest = length
}
}
return longest
}
func union(fathers, counts *map[int]int, i, j int) {
fatherOfI := findFather(fathers, i)
fatherOfJ := findFather(fathers, j)
if fatherOfI != fatherOfJ {
(*fathers)[fatherOfI] = fatherOfJ
countOfI, _ := (*counts)[fatherOfI]
countOfJ, _ := (*counts)[fatherOfJ]
(*counts)[fatherOfJ] = countOfI + countOfJ
}
}
func findFather(fathers *map[int]int, i int) int{
if (*fathers)[i] != i {
(*fathers)[i] = findFather(fathers, (*fathers)[i])
}
return (*fathers)[i]
}
提示:这里对文章进行总结:
例如:以上就是今天要讲的内容,本文仅仅简单介绍了pandas的使用,而pandas提供了大量能使我们快速便捷地处理数据的函数和方法。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。