Please enable Javascript to view the contents

GO 算法学习

 ·  ☕  3 分钟

✨:希望坚持每周 2-3 道吧(😭 < “这道题我不会做,不会做,太难了!”)。

链表

Base

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
package main

import "fmt"

type Node struct {
	Data int
	Next *Node
}

// 创建链表
func createLinkedList() *Node {
	var head, sentry *Node
	data := []int{11, 12, 13, 14, 15, 16}
	for i, d := range data {
		if i == 0 {
			head = &Node{Data: d, Next: nil}
			sentry = head
		} else {
			sentry.Next = &Node{Data: d, Next: nil}
			sentry = sentry.Next
		}
	}
	return head
}

// 打印链表
func printLinkedList(head *Node) {
	var sentry *Node
	sentry = head
	for {
		if sentry == nil {
			break
		}
		fmt.Printf("%d -> ", sentry.Data)
		if sentry.Next == nil {
			fmt.Print("nil")
			break
		} else {
			sentry = sentry.Next
		}
	}
	fmt.Println()
}

// 获取链表的长度
func getLinkListlength(head *Node) int {
	var length int
	sentry := head
	for {
		if sentry == nil {
			break
		}
		length++
		sentry = sentry.Next
	}
	return length
}

func main(){
	...
}

题目一:递归反转链表

递归反转链表
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
func reverse(head *Node) *Node {
	if head == nil || head.Next == nil {
		return head
	}
	newList := reverse(head.Next)
	sentry := head.Next
	sentry.Next = head
	head.Next = nil
	return newList
}

面试题:从链表尾部分组逆序

给定一个单链表的头节点 head,实现一个调整单链表的函数,使得每 K 个节点之间为一组进行逆序,并且从链表的尾部开始组起,头部剩余节点数量不够一组的不需要逆序,(不能使用队列或者栈作为辅助)。
例如:
    链表: `1->2->3->4->5->6->7->8->null`, K = 3。那么 `6->7->8`,`3->4->5`,`1->2`各位一组。

    调整后:`1->2->5->4->3->8->7->6->null`。其中 `1->2` 不调整,因为不够一组。

解题思路:
获取链表的长度,忽略 length%k 对其他的 node 进行分组反转(写的有点拙劣)。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
func reverseKGroup(head *Node, length int) *Node {
	if head == nil || head.Next == nil {
		return head
	}
	length := getLinkListlength(head)
	ignoreLen := length % k

	var j int
	var flag bool
	var endSentry, nextGsentry, ghead, gend *Node
	endSentry = head
	if ignoreLen == 0 {
		length++
	}
	for i := 1; i < length; i++ {
		// 忽略的节点
		if i < ignoreLen {
			endSentry = endSentry.Next
			continue
		}
		if j == 0 {
			j++
			if nextGsentry == nil {
				if ignoreLen == 0 {
					ghead = endSentry
				} else {
					ghead = endSentry.Next
				}
			} else {
				ghead = nextGsentry
			}
			gend = ghead
		} else if j < k {
			j++
			gend = gend.Next
		}
		if j == k {
			nextGsentry = gend.Next
			gend.Next = nil
			if ignoreLen == 0 {
				tmp := reverse(ghead)
				if flag == false {
					head = tmp
					endSentry = head
					flag = true
				} else {
					endSentry.Next = tmp
				}

			} else {
				endSentry.Next = reverse(ghead)
			}
			for {
				if endSentry.Next == nil {
					break
				}
				endSentry = endSentry.Next
			}
			j = 0
		}
	}
	return head
}

矩阵

翻转矩阵后的得分

leetcode 861.翻转矩阵后的得分

有一个二维矩阵 A 其中每个元素的值为 0 或 1 。

移动是指选择任一行或列,并转换该行或列中的每一个值:将所有 0 都更改为 1,将所有 1 都更改为 0。

在做出任意次数的移动后,将该矩阵的每一行都按照二进制数来解释,矩阵的得分就是这些数字的总和。

返回尽可能高的分数。

得最高分思路:左边第一例必须都为 1 其余同位 1 越多就越大;

而我实际编写的代码很冗余,这次参考别人的答案:

无需修改原矩阵,而是可以计算每一列对总分数的「贡献」,从而直接计算出最高的分数。假设矩阵共有 m 行 n 列,计算方法如下:
- 对于最左边的列而言,由于最优情况下,它们的取值都为 1,因此每个元素对分数的贡献都为 2^n−1,总贡献为 m*(2^n-1)。

- 对于第 j 列(j>0,此处规定最左边的列是第 0 列)而言,我们统计这一列 0,1 的数量,令其中的最大值为 k,则 k 是列翻转后的 1 的数量,该列的总贡献为 k * (2^n-1-j),在统计 0,1 的数量的时候,**要考虑最初进行的行反转**。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
func matrixScore(A [][]int) int {
	var (
		m, n int // 行,列
		ans  int // 总贡献值
	)
	m, n = len(A), len(A[0])
	// 第一列的总贡献值
	ans = 1 << (n - 1) * m
	// 遍历余下列
	for j := 1; j < n; j++ {
		ones := 0
		for _, row := range A {
			// 与第一个值不同话则不可能同时为相同的值
			if row[j] == row[0] {
				ones++
			}
		}
		// 取最大值
		if ones < m-ones {
			ones = m - ones
		}
		// 计算每一列的值
		ans += 1 << (n - 1 - j) * ones
	}
	return ans
}

我好菜鸭~ 写的也太优美了8

目录