算法唯手熟尔(PAT剩余清单 or leetcode)

算法笔记的前十章一眨眼就过去了，每天保证至少一题，题源随意，题目思路都会写在代码思路中

水平太菜，所谓的的C，全部使用了STL

2020/3/5

PAT A1119_C

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string>
#include <string.h>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>

using namespace std;

//PAT A1119
//二叉树，已知前序和后序，写出一个中序的可能即可
//前序的开始的第一个应该是后序的最后一个是相等的，这个结点就是根结点
//不确定的状态可以都先当作右孩子
//如果只有一个儿子结点的话，在递归判断的时候无法知道是否是左儿子还是右儿子；
//但是如果有两个或者没有的话，是可以判断的
//如果根节点存在右子树，则post序列中倒数第二个节点(即根节点的右子树的根节点)
//在pre中的index与根节点的index差值一定大于1
struct NODE
{
    int data;
    struct NODE *left;
    struct NODE *right;
};
vector<int> pre,post;
bool flag=true;
NODE *create(int preL,int preR,int postL,int postR)
{
    if(preL>preR) return NULL;
    NODE *node =new NODE;
    node->left=NULL;
    node->right=NULL;
    node->data=pre[preL];
    if(preL==preR) return node;
    int k;
    for(k=preL+1;k<=preR;k++){
        if(pre[k]==post[postR-1])
            break;
    }
    int leftnum=k-preL-1;
    if(k-preL>1){
        node->left=create(preL+1,preL+leftnum,postL,postL+leftnum-1);
        node->right=create(preL+leftnum+1,preR,postL+leftnum,postR-1);
    }
    else{
        flag=false;
        node->right = create(preL+1,preR,postL,postR-1);
    }
    return node;
}

int num=0;

void inOrder(NODE *root)
{
    if(root==NULL) return;
    inOrder(root->left);
    if(num==0)
        printf("%d",root->data);
    else
        printf(" %d",root->data);
    num++;
    inOrder(root->right);
}

int main()
{
    int n;
    scanf("%d",&n);
    pre.resize(n);
    post.resize(n);
    for(int i=0;i<n;i++) scanf("%d",&pre[i]);
    for(int i=0;i<n;i++) scanf("%d",&post[i]);
    NODE *root=create(0,n-1,0,n-1);
    if(flag==true)printf("Yes\n");
	if(flag==false)printf("No\n");
	inOrder(root);
	printf("\n"); //一定要加，不加全错
    return 0;
}

2020/3/6

PAT A1123_C

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string>
#include <string.h>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>

using namespace std;
//PAT A1123
//平衡二叉树（AVL）
//生成平衡二叉树 + 层序遍历 + 判断是否为完全二叉树
//用队列层序输出时，判断第一个无孩子结点之后输出的结点是否有孩子，用来判断是否是完全二叉树
int od[30];
struct NODE
{
    int data;
    int height;
    struct NODE *left;
    struct NODE *right;
};

//生成一个新节点
NODE *newNode(int v)
{
    NODE *node=new NODE;
    node->data=v;
    node->height=1;
    node->left=node->right=NULL;
    return node;
}
//获取节点height
int getHeight(NODE *node)
{
    if(node==NULL) return 0;
    else return node->height;
}
//计算节点平衡因子
int getBalance(NODE *node)
{
    return getHeight(node->left)-getHeight(node->right);
}
//更新节点高度
void updateHeight(NODE *node)
{
    node->height=max(getHeight(node->left),getHeight(node->right))+1;
}
//左旋
void L(NODE* &node)
{
    NODE* temp=node->right;
    node->right=temp->left;
    temp->left=node;
    updateHeight(node);
    updateHeight(temp);
    node=temp;
}
//右旋
void R(NODE* &node)
{
    NODE* temp=node->left;
    node->left=temp->right;
    temp->right=node;
    updateHeight(node);
    updateHeight(temp);
    node=temp;
}

void insert(NODE* &root,int v)
{
    if(root==NULL){
        root=newNode(v);
        return;
    }
    if(v<root->data){
        insert(root->left,v);
        updateHeight(root);
        if(getBalance(root)==2){
            if(getBalance(root->left)==1){
                R(root);
            }
            else if(getBalance(root->left)==-1){
                L(root->left);
                R(root);
            }
        }
    }
    else{
        insert(root->right,v);
        updateHeight(root);
        if(getBalance(root)==-2){
            if(getBalance(root->right)==-1){
                L(root);
            }
            else if(getBalance(root->right)==1){
                R(root->right);
                L(root);
            }
        }
    }
}

NODE* create(int data[],int n)
{
    NODE *root=NULL;
    for(int i=0;i<n;i++){
        insert(root,data[i]);
    }
    return root;
}

int num=0;
bool complete=true;
bool havechild=true;
void levelOrder(NODE *root)
{
    queue<NODE*> q;
    q.push(root);
    while(!q.empty()){
        NODE *node=q.front();
        q.pop();
        if(node->left!=NULL){
            q.push(node->left);
            if(!havechild) complete=false;
        }
        else havechild=false;
        if(node->right!=NULL){
            q.push(node->right);
            if(!havechild) complete=false;
        }
        else havechild=false;
        if(num==0) printf("%d",node->data);
        else printf(" %d",node->data);
        num++;
    }
    printf("\n");
}

int main()
{
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d",&od[i]);
    //生成平衡二叉树
    NODE *root=create(od,n);
    //层序遍历
    levelOrder(root);
    if(complete) printf("YES\n");
    else printf("NO\n");
    return 0;
}

PAT A1115_C

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string>
#include <string.h>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>

using namespace std;

//PAT A1115
//建立一个二叉树
//统计最后两层的节点的数量
struct NODE
{
    int data;
    int layer;
    struct NODE* left;
    struct NODE* right;
};
const int maxn=1010;
int od[maxn];

NODE* newNODE(int v)
{
    NODE* node=new NODE;
    node->data=v;
    node->layer=1;
    node->left=node->right=NULL;
    return node;
}

void insert(NODE* &root,int v)
{
    if(root==NULL){
        root=newNODE(v);
        return;
    }
    if(v<=root->data){
        insert(root->left,v);
    }
    else{
        insert(root->right,v);
    }
}

NODE* create(int data[],int n)
{
    NODE *root=NULL;
    for(int i=0;i<n;i++){
        insert(root,data[i]);
    }
    return root;
}

int level[maxn]={0}; //记录每一行的节点数
int deep=-1;
void levelOrder(NODE* root)
{
    queue<NODE*> q;
    q.push(root);
    while(!q.empty()){
        NODE* node =q.front();
        deep=max(deep,node->layer);
        q.pop();
        if(node->left!=NULL){
            node->left->layer=node->layer+1;
            q.push(node->left);
        }
        if(node->right!=NULL){
            node->right->layer=node->layer+1;
            q.push(node->right);
        }
        level[node->layer]++;
    }
}

int main()
{
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d",&od[i]);
    }
    NODE* root=create(od,n);
    levelOrder(root);
    //printf("%d",level[deep]);
    //printf("%d",level[deep-1]);
    printf("%d + %d = %d\n",level[deep],level[deep-1],level[deep]+level[deep-1]);
    return 0;
}

PAT A1114_C

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
64
65
66
67
68
69
70
71
72
73
74
#include<iostream>
#include<string>
#include<cmath>
#include<algorithm>
#include<vector>
//去TY的并查集，真复杂，直接邻接表
using namespace std;
typedef long long LL;
const int maxn = 10000;
struct Person{ int e,a;}per[maxn]; //存放住宅数，住宅面积
struct Family{
    int id,member;
    double avga,avge;
    Family(int a,int b,double c,double d): id(a), member(b), avge(c), avga(d) {}
};
bool table[maxn],vis[maxn];
vector<int> adj[maxn];
vector<Family> ans;
bool cmp(Family a,Family b){
    return a.avga!=b.avga?a.avga>b.avga:a.id<b.id;
}
void DFS(int u,LL &sumE,LL &sumA,int &member){
    vis[u] = 1;
    member++;
    sumE += per[u].e;
    sumA += per[u].a;
    for(int i=0;i<adj[u].size();i++){
        int v = adj[u][i];
        if(!vis[v])
            DFS(v,sumE,sumA,member);
    }
}
int main(){
    int n,id,fid,mid,k,cid,e,a;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>id>>fid>>mid;
        table[id] = 1;
        if(fid!=-1){
            adj[id].push_back(fid);
            adj[fid].push_back(id);
            table[fid] = 1;
        }
        if(mid!=-1){
            adj[id].push_back(mid);
            adj[mid].push_back(id);
            table[mid] = 1;
        }
        cin>>k;
        while(k--){
            cin>>cid;
            adj[id].push_back(cid);
            adj[cid].push_back(id);
            table[cid] = 1;
        }
        cin>>per[id].e>>per[id].a;
    }
    int cnt = 0;
    for(int u=0;u<maxn;u++){
        if(table[u] && !vis[u]){
            LL sumE = 0,sumA = 0;
            int member = 0;
            DFS(u,sumE,sumA,member);
            cnt++;
            ans.push_back(Family(u,member,1.0*sumE/member,1.0*sumA/member));
        }
    }
    cout<<cnt<<endl;
    sort(ans.begin(),ans.end(),cmp);
    for(int i=0;i<cnt;i++)
        printf("%04d %d %.3lf %.3lf\n",ans[i].id,ans[i].member,ans[i].avge,ans[i].avga);
	return 0;
}

leetcode 206. 反转链表_C

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
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string>
#include <string.h>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>

using namespace std;

struct ListNode
{
    int val;
    struct ListNode* next;
};

ListNode* reverseList(ListNode *head)
{
    //preNode表示当前节点的前一个节点
    ListNode *preNode = head;
    //当前节点curNode
    ListNode *curNode = head->next;
    while (curNode != NULL) {
        //nextNode,表示当前节点的下一个节点
        ListNode* nextNode = curNode->next;
        curNode->next = preNode;
        preNode = curNode;
        curNode = nextNode;
    }
    return preNode;
}

int main()
{
    int n;
    scanf("%d",&n);
    ListNode* root=new ListNode;
    ListNode* head=new ListNode;
    head->next=NULL;
    root=head;
    for(int i=0;i<n;i++){
        scanf("%d->",&head->val);
        ListNode* temp=new ListNode;
        head->next=temp;
        head=temp;
    }
    head->next=NULL;
    ListNode* pre =reverseList(root);
    pre=pre->next;
    //pre=root->next;
    for(int i=0;i<n;i++){
        printf("%d->",pre->val);
        pre=pre->next;
    }
    printf("NULL\n");
    return 0;
}

leetcode 206. 反转链表_Go

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
package main

import "fmt"

// ListNode ,just a struct
type ListNode struct {
	Val  int
	Next *ListNode
}

func reverseList(head *ListNode) *ListNode {
	var preNode *ListNode
	preNode = nil
	curNode := head
	for curNode != nil {
		next := curNode.Next
		curNode.Next = preNode
		preNode = curNode
		curNode = next
	}
	return preNode
}

func main() {
	n := 0
	fmt.Scanf("%d\n", &n)
	var root *ListNode = new(ListNode)
	var head *ListNode = new(ListNode)
	//var temp *ListNode = new(ListNode)
	root = head
	//fmt.Printf("%p\n", root)
	for i := 0; i < n; i++ {
		fmt.Scanf("%d->", &head.Val)
		head.Next = new(ListNode) //先初始化，在next
		if i == 4 {
			break
		}
		head = head.Next
	}
	head = nil
	//fmt.Printf("%p\n", root)
	// for i := 0; i < n; i++ {
	// 	fmt.Printf("%d->", root.Val)
	// 	root = root.Next
	// }
	var pre *ListNode = reverseList(root)
	pre = pre.Next
	for i := 0; i < n; i++ {
		fmt.Printf("%d->", pre.Val)
		pre = pre.Next
	}
	fmt.Printf("NULL\n")
}

2020/3/7

leetcode 225. 用队列实现栈_Go

GO本身不支持stack啥的，那切片实现一下也不错，学到了一些姿势，我自己想的是用两个切边操作一下肯定是可以实现一个栈的

大家也可以画个图，画着画着就出来了

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
type MyStack struct {
    Queue1 []int
    Queue2 []int
    top int //栈顶元素
}


/** Initialize your data structure here. */
func Constructor() MyStack {
    var mystack MyStack
    return mystack
}


/** Push element x onto stack. */
func (this *MyStack) Push(x int)  {
    this.Queue1=append(this.Queue1,x)
    this.top=x
}


/** Removes the element on top of the stack and returns that element. */
func (this *MyStack) Pop() int {
    var length int = len(this.Queue1)
    //除了要出栈的元素全部存到另一个空切片Queue2中去
    for i:=0;i<length-1;i++{
        temp:=this.Queue1[0]
        this.top = temp
        this.Queue1 = this.Queue1[1:]
        this.Queue2 = append(this.Queue2, temp)
    }
    target := this.Queue1[0]
    //交换队列，并让辅助队列变空
    this.Queue1 = this.Queue2
    this.Queue2 = make([]int, 0)
    return target
}


/** Get the top element. */
func (this *MyStack) Top() int {
    return this.top
}


/** Returns whether the stack is empty. */
func (this *MyStack) Empty() bool {
    var result int = len(this.Queue1)
    return result==0
}


/**
 * Your MyStack object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Push(x);
 * param_2 := obj.Pop();
 * param_3 := obj.Top();
 * param_4 := obj.Empty();
 */

2020/3/8

PAT A1007_C

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
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string>
#include <string.h>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>

using namespace std;

//PAT a1007
//求最长子序列
const int maxn=10010;
int dp[maxn],temp[maxn],s[maxn]={0};
bool flag=false;
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d",&temp[i]);
        if(temp[i]>=0) flag=true;
        dp[i]=-1;
    }
    if(!flag){
        printf("0 %d %d\n",temp[0],temp[n-1]);
        return 0;
    }
    dp[0]=temp[0];
    for(int i=1;i<n;i++){
        if(dp[i-1]+temp[i]>temp[i]){
            dp[i]=temp[i]+dp[i-1];
            s[i]=s[i-1];
        }
        else{
            dp[i]=temp[i];
            s[i]=i;
        }
    }
    int k=0;
    for(int i=1;i<n;i++){
        if(dp[i]>dp[k]){
            k=i;
        }
    }
    printf("%d %d %d\n",dp[k],temp[s[k]],temp[k]);
    return 0;
}

PAT A1045_C

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
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string>
#include <string.h>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>

using namespace std;

//PAT A1045
//LIS
//可以在输入数据的时候就直接剔除不喜欢的颜色，从而简化操作
const int maxc=210;
const int maxn=10010;
int HashTable[maxc];
int A[maxn],dp[maxn];
int main()
{
    int n,m,x;
    scanf("%d%d",&n,&m);
    fill(HashTable,HashTable+maxc,-1);
    for(int i=0;i<m;i++){
        scanf("%d",&x);
        HashTable[x]=i;
    }
    int num=0,L;
    scanf("%d",&L);
    for(int i=0;i<L;i++){
        scanf("%d",&x);
        if(HashTable[x]>=0)
            A[num++]=HashTable[x];
    }
    int ans=-1;
    for(int i=0;i<num;i++){
        dp[i]=1;
        for(int j=0;j<i;j++){
            if(A[j]<=A[i]&&dp[j]+1>dp[i]){
                dp[i]=dp[j]+1;
            }
        }
        ans=max(ans,dp[i]);
    }
    printf("%d\n",ans);
    return 0;
}

PAT A1040_C

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
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string>
#include <string.h>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>

using namespace std;

//PAT A1040
//最长回文串
const int maxn=1010;
string s;
int dp[maxn][maxn];
int main()
{
    getline(cin,s);
    //cout<<s<<endl;
    int len=s.length(),ans=1;
    fill(dp[0],dp[0]+maxn*maxn,0);
    //边界
    for(int i=0;i<len;i++){
        dp[i][i]=1;
        if(i<len-1){
            if(s[i]==s[i+1]){
                dp[i][i+1]=1;
                ans=2;
            }
        }
    }
    //状态转移方程
    for(int L=3;L<=len;L++){
        for(int i=0;i+L-1<len;i++){
            int j=i+L-1;
            if(s[i]==s[j]&&dp[i+1][j-1]==1){
                dp[i][j]=1;
                ans=L;
            }
        }
    }
    printf("%d\n",ans);
    return 0;
}

leetcode 994. 腐烂的橘子_Go

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
64
65
66
67
68
69
package main

import "fmt"

func orangesRotting(grid [][]int) int {
	if len(grid) == 0 {
		return 0
	}
	var w, h int = len(grid), len(grid[0]) // 行、列
	var health int = 0
	var queue = [][]int{}
	// 读入图表
	for i := 0; i < w; i++ {
		for j := 0; j < h; j++ {
			if grid[i][j] == 2 {
				queue = append(queue, []int{i, j})
			} else if grid[i][j] == 1 {
				health++
			}
		}
	}
	// BFS 迷宫走法
	var time int = 0
	for len(queue) > 0 && health > 0 {
		time++
		length := len(queue)
		// 去除第一个节点
		for i := 0; i < length; i++ {
			dot := queue[0]
			x, y := dot[0], dot[1]
			queue = queue[1:]
			//上边的健康
			if y-1 >= 0 && grid[x][y-1] == 1 {
				grid[x][y-1] = 2
				health--
				queue = append(queue, []int{x, y - 1})
			}
			//下边的健康
			if y+1 < h && grid[x][y+1] == 1 {
				grid[x][y+1] = 2
				health--
				queue = append(queue, []int{x, y + 1})
			}
			//左边的健康
			if x-1 >= 0 && grid[x-1][y] == 1 {
				grid[x-1][y] = 2
				health--
				queue = append(queue, []int{x - 1, y})
			}
			//右边的健康
			if x+1 < w && grid[x+1][y] == 1 {
				grid[x+1][y] = 2
				health--
				queue = append(queue, []int{x + 1, y})
			}
		}
	}
	if health > 0 {
		return -1
	}
	return time
}

func main() {
	var grid = [][]int{{2, 1, 1}, {1, 1, 0}, {0, 1, 1}}
	result := orangesRotting(grid)
	fmt.Println(result)
}

2020/3/9

今天要忙的事情好多，就做个水题吧，即将毕业的真痛苦

leetcode 1103. 分糖果||_Go

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func distributeCandies(candies int, num_people int) []int {
    ans:=make([]int,num_people)
    add:=1
    idx:=0
    candies-=1
    for candies>0{
        ans[idx]+=add
        add++
        candies-=add
        idx=(idx+1)%num_people
    }
    ans[idx]+=candies+add
    return ans
}

2020/3/10

PAT A1068_C

背包问题冲冲冲

一个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
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
64
65
66
67
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string>
#include <string.h>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>

using namespace std;

//PAT A1068
// 0/1 背包问题
// 特色是不光要求值，还需要把选择的序列写出来
const int maxn=10010;
const int maxc=110;
int dp[maxc]={0};
int c[maxn];
bool flag[maxn];
bool choice[maxn][maxc];
bool cmp(int a,int b){
    return a>b;
}
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&c[i]);
    }
    sort(c+1,c+n+1,cmp); //从小到大排序
    for(int i=1;i<=n;i++){
        for(int v=m;v>=c[i];v--){
            if(dp[v]<=dp[v-c[i]]+c[i]){
                dp[v]=dp[v-c[i]]+c[i];
                choice[i][v]=1;   //容量是v时，放入第i件物品
            }
            else choice[i][v]=0;
        }
    }
    if(dp[m]!=m) printf("No Solution");
    else{
        int k=n,num=0,v=m;
        while(k>=0){
            if(choice[k][v]==true){
                flag[k]=true;
                v-=c[k];
                num++;
            }
            else flag[k]=false;
            k--;
        }
        for(int i=n;i>=1;i--){
            if(flag[i]==true){
                printf("%d",c[i]);
                num--;
                if(num>0) printf(" ");
            }
        }
    }
    return 0;
}

2020/3/13

我太难了，这两天在准备开题，还学了不少web，尽然咕了

leetcode 1071. 字符串的最大公因子_Go

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
package main

import "fmt"

// 辗转相除法
func mod(str1 string, str2 string) string {
	var remain string = str1
	length := len(str2)
	for {
		if len(remain) < length || remain[:length] != str2 {
			break
		}
		remain = remain[length:]
	}
	return remain
}

func gcdOfStrings(str1 string, str2 string) string {
	if len(str1) < len(str2) {
		str1, str2 = str2, str1
	}
	var remain string = mod(str1, str2)
	if remain == "" {
		return str2
	} else if remain == str1 {
		return ""
	}
	return gcdOfStrings(str2, remain)
}

func main() {
	var s1 string = "ABCABC"
	var s2 string = "ABC"
	result := gcdOfStrings(s1, s2)
	fmt.Println(result)
}

2020/3/14

leetcode 121. 买卖股票的最佳时机_Go

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
package main

import (
	"fmt"
)

// 暴力显然可以，但阿弥陀佛，能不暴力还是不暴力了
// 第一步：找到最低价位
// 第二步：找到最大差价，且有日期限制，不可穿越时空
// 之前应该用py写过，用go在加深一遍go语法的印象
func maxProfit(prices []int) int {
	profit := 0
	if len(prices) <= 1 {
		return profit
	}
	min := prices[0]
	for i := 0; i < len(prices); i++ {
		if prices[i] < min {
			min = prices[i]
		} else if profit < prices[i]-min {
			profit = prices[i] - min
		}
	}
	return profit
}

func main() {
	var prices = []int{7, 1, 5, 3, 6, 4}
	result := maxProfit(prices)
	fmt.Println(result)
}

2020/3/17

codeup 21142_C(哈夫曼树)

学一手哈夫曼树，其实不怎么复杂，掌握有优先级的队列就好

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
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string>
#include <string.h>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>

using namespace std;
//Codeup_21142
priority_queue<long long,vector<long long>,greater<long long>> q;
int main()
{
    long long n,x,y,ans=0;
    scanf("%lld",&n);
    long long temp;
    for(int i=0;i<n;i++){
        scanf("%lld",&temp);
        q.push(temp);
    }
    while(q.size()>1){
        x=q.top();
        q.pop();
        y=q.top();
        q.pop();
        q.push(x+y);
        ans+=x+y;
    }
    printf("%lld\n",ans);
    return 0;
}

AVL_tips

以前写过，就理一下思路

1
2
3
4
5
node* newNode(int v); //生成一个结点
int getHeight(node *root); //获取结点高度
int getBalanceFactor(node *root); //获取平衡因子
void updateHeight(node *root); //更新高度
左旋+右旋函数

HeapSort_tips

记录一下重要的函数，其余按照堆排序的逻辑来不会出错的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void downAdjust(int low,int high){
    int i=low;
    int j=i*2;
    while(i<=high){
        if(j+1<=high&&heap[j+1]>heap[j]){
            j=j+1;
        }
        if(heap[i]<heap[j]){
            swap(heap[j],heap[i]);
            i=j;
            j=j*2;
        }else{
            breal;
        }
    }
}

并查集_tips

1
2
3
4
5
6
7
8
9
10
void init(); //初始化isRoot与father数组
int findFather(int v){  //找到祖先，合并路径
    if(v==father[v]) return v;
    else{
        int F=findFather(father[v]);
        father[v]=F;
        return F;
    }
}
void union(int a,int b) //合并父亲结点

Kruskal最小生成树(边贪心)_tips

1
2
3
4
5
6
7
8
9
10
11
12
13
int kruskal(int n,int m){ // n是顶点数，m是边数
    int ans=0,Num_Edge=0; // 最小生成树边权之和，当前边数
    // 将所有边权从小到大排序
    for（从小到大枚举所有边）{
        if(当前测试边两个端点不在一个连通块内){
            // 将该测试边加入最小生成树
    		// ans+=测试边的边权
    		// 最小生成树的当前边数 Num_Edge+1
    		if(Num_Edge<n-1) break;
        }
	}
    return ans;
}

2020/3/19

ECNU_OJ_35. 零元素占比

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
#include <stdio.h>

#define M 100
//int (*p)[M]定义的数组指针，表示定义一个指针变量，
//此指针变量是指向一个含有M个元素的一维数组

double Ratio(int (*p)[M], int n, int m)
/* PreCondition:
 p points to a two-dimensional array with n lines and m integers in each line
    PostCondition: array is sorted satisfying to the specification
*/

{
    double sum = n*m;
    double count=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            //printf("%d\n",*(*(p+i)+j));
            if (*(*(p+i)+j)==0)
                count++;
        }
    }
    return count/sum;
}

int main() {
    int a[100][M], m, n, i, j;
    scanf("%d%d", &n, &m);
    for (i = 0; i < n; i++)
        for (j = 0; j < m; j++)
            scanf("%d", &a[i][j]);
    printf("%.9f\n", Ratio(a, n, m));
    return 0;
}

ECNU_OJ_3441. 唐纳德与子串 (Easy)

不管是不是easy，反正用KMP做，学习一波，我们可以看到hard级难度是只能用kmp实现的

kmp算法

仅仅后移模式串；指针不回溯；找出公共前后缀

公共前后缀的条件为：

1、最长的前后缀

2、长度小于指针前所有字符长度

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
64
65
66
67
#include <iostream>
#include <cstring>
#include <string.h>
#include <string>
using namespace std;
int l,r,p;
int next1[100000];

void getNext(string str,int len)
{
    int j=-1;
    next1[0]=-1;
    for(int i=1;i<len;i++){
        while(j!=-1&&str[i]!=str[j+1]){
            j=next1[j];
        }
        if(str[i]==str[j+1]){
            j++;
        }
        next1[i]=j;
    }
}

int KMP(string text,string pattern)
{
    int n=text.length();
    int m=pattern.length();
    getNext(pattern,m);
    int j=-1,ans=0;
    for(int i=0;i<n;i++){
        while(j!=-1&&text[i]!=pattern[j+1]){
            j=next1[j];
        }
        if(text[i]==pattern[j+1]){
            j++;
        }
        if(j==m-1){
            ans++;
            j=next1[j];
        }
    }
    return ans;
}

int main()
{
    string s,z;
    string temp;
    cin>>s;
    //cout<<s<<endl;
    cin>>p;
    //cout<<p<<endl;

    for(int i=0;i<p;i++)
    {
        cin>>l>>r>>z;
        //cout<<l<<" "<<r<<" "<<z<<endl;
        temp=s;
        temp=s.substr(l,r-l+1);
        //cout<<temp.size()<<endl<<endl;
        memset(next1,0,sizeof(next1));
        int ans=KMP(temp,z);
        cout<<ans<<endl;
    }
    return 0;
}

这代码放到hard里面是通不过的，心酸，不过知道kmp咋做就好了

2020/3/21

leetcode 169. 多数元素_Go

刷个水题热热手，最近一直在看英语和GO

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
package main

import "fmt"

func majorityElement(nums []int) int {
	Hash := make(map[int]int, 0)
	for i := 0; i < len(nums); i++ {
		Hash[nums[i]]++
	}
	for key, value := range Hash {
		if value > len(nums)/2 {
			return key
		}
	}
	return -1
}

func main() {
	var input = [3]int{3, 2, 3}
	ans := majorityElement(input[:])
	fmt.Println(ans)
}

接下来展示一个别人的神仙做法

1
2
3
4
func majorityElement(nums []int) int {
    sort.Ints(nums)
    return nums[len(nums)/2]
}

人与人的差距怎么就这么大呢

2020/3/22

leetcode 409. 最长回文串_Go

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
package main

import (
	"fmt"
	"unicode"
)

// 求能组成的最长回文串
// 我想到的就是配对，然后可以再多带一个单一字符
func longestPalindrome(s string) int {
	var Hash [52]int
	count := 0
	for _, value := range s {
		// 若是大写
		if unicode.IsUpper(value) {
			value -= 'A'
			//fmt.Println(value)
			Hash[value]++
		} else {
			value -= 'a'
			value += 26
			Hash[value]++
		}
	}
	for _, value := range Hash {
		count += value / 2 * 2
	}
	if count == len(s) {
		return count
	}
	return count + 1
}

func main() {
	var str string
	fmt.Scanf("%s", &str)
	//fmt.Println(str)
	ans := longestPalindrome(str)
	fmt.Println(ans)
}

2020/3/26

leetcode 876. 链表的中间结点_Go

典型的two pointer，快慢指针

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
package main

import "fmt"

// ListNode struct
type ListNode struct {
	Val  int
	Next *ListNode
}

var head = &ListNode{
	0,
	nil,
}

var pre = head

func create(input []int) {
	for i := 0; i < len(input); i++ {
		var temp = &ListNode{}
		temp.Next = nil
		temp.Val = input[i]
		head.Next = new(ListNode)
		head.Next = temp
		head = head.Next
	}
}

func middleNode(head *ListNode) *ListNode {
	fast, slow := head, head
	for {
		if fast.Next != nil && fast.Next.Next != nil {
			slow = slow.Next
			fast = fast.Next.Next
		} else if fast.Next != nil {
			return slow.Next
		} else {
			return slow
		}
	}
}

func main() {
	input := []int{1, 2, 3, 4, 5, 6}
	create(input)
	// // check
	// for pre != nil {
	// 	fmt.Println(pre.Val)
	// 	pre = pre.Next
	// }
	ans := middleNode(pre.Next)
	fmt.Println(ans.Val)
}

2020/3/30

leetcode 62. 圆圈中最后剩下的数字_Go

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
package main

import "fmt"

// 约瑟夫环
func f(n int, m int) int {
	if n == 1 {
		return 0
	}
	x := f(n-1, m)
	return (m + x) % n
}

func lastRemaining(n int, m int) int {
	return f(n, m)
}

func main() {
	ans := lastRemaining(5, 3)
	fmt.Println(ans)
}

leetcode 300. 最长上升子序列_Go

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
package main

import (
	"fmt"
	"math"
)

// dp LIS
const m = math.MaxInt16

var dp = [m]int{}

// Max 返回较大值
func Max(x, y int) int {
	if x < y {
		return y
	}
	return x
}

func lengthOfLIS(nums []int) int {
	ans := 0
	for i := 0; i < len(nums); i++ {
		dp[i] = 1
		for j := 0; j < i; j++ {
			if nums[i] > nums[j] && dp[j]+1 > dp[i] {
				dp[i] = dp[j] + 1
			}
		}
		ans = Max(ans, dp[i])
	}
	return ans
}

func main() {
	a := []int{10, 9, 2, 5, 3, 7, 101, 18}
	ans := lengthOfLIS(a)
	fmt.Println(ans)
}

leetcode 1160. 拼写单词_Go

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
package main

import "fmt"

func countCharacters(words []string, chars string) int {
	// hashTable
	var hashTable = [26]int{}
	count := 0
	for i := 0; i < len(chars); i++ {
		hashTable[chars[i]-'a']++
	}
	for i := 0; i < len(words); i++ {
		tempTable := hashTable
		temp := words[i]
		//fmt.Println(temp)
		flag := true
		for j := 0; j < len(temp); j++ {
			if tempTable[temp[j]-'a'] > 0 {
				tempTable[temp[j]-'a']--
			} else {
				flag = false
				break
			}
		}
		if flag == true {
			count += len(temp)
		}
	}
	return count
}

func main() {
	words := []string{"hello", "world", "leetcode"}
	chars := "welldonehoneyr"
	ans := countCharacters(words, chars)
	fmt.Println(ans)
}

leetcode 543. 二叉树的直径_Go

今天的前几题其实一上来都有思路，但这题让我有点迷茫，不清楚该怎么操作，让我知道昨晚这题可以休息了……

后来觉得其实就是要求左子树的深度+右子树的深度，这么想就简单很多了

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
package main

import "fmt"

// TreeNode Definition for a binary tree node.
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

// 求深度
func depth(root *TreeNode, m *int) int {
	if root == nil {
		return 0
	}
	l := depth(root.Left, m)
	r := depth(root.Right, m)
	*m = max(l+r, *m)
	return int(max(l, r)) + 1

}

func diameterOfBinaryTree(root *TreeNode) int {
	if root == nil {
		return 0
	}
	m := 0
	depth(root, &m)
	return m
}

func main() {
	temp := new(TreeNode)
	temp.Val = 1
	temp.Left = new(TreeNode)
	temp.Right = new(TreeNode)
	temp.Left.Val = 2
	temp.Right.Val = 3
	temp.Left.Left = new(TreeNode)
	temp.Left.Right = new(TreeNode)
	temp.Left.Left.Val = 4
	temp.Left.Right.Val = 5
	ans := diameterOfBinaryTree(temp)
	fmt.Println(ans)
}

2020/4/1

leetcode 914. 卡牌分组_Go

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
package main

import (
	"fmt"
)

func gcd(a, b int) int {
	if b == 0 {
		return a
	}
	return gcd(b, a%b)
}

func hasGroupsSizeX(deck []int) bool {
	m := make(map[int]int)
	for i := 0; i < len(deck); i++ {
		m[deck[i]]++
	}
	for _, value := range m {
		for _, k := range m {
			if gcd(value, k) < 2 {
				return false
			}
		}
	}
	return true
}

// 感觉就是一个Hash，再加上gcd
func main() {
	deck := []int{1, 1, 1, 1, 2, 2, 2, 2, 2, 2}
	fmt.Println(hasGroupsSizeX(deck))
}

leetcode 1111. 有效括号的嵌套深度_Go

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
package main

import "fmt"

func maxDepthAfterSplit(seq string) []int {
	stack := make([]int, 0, len(seq))
	var deep = -1
	for _, v := range seq {
		if string(v) == "(" {
			deep++
			stack = append(stack, deep%2)
		}
		if string(v) == ")" {
			stack = append(stack, deep%2)
			deep--
		}
	}
	return stack
}

// 说实话，这题目我都看了半天
// depth("(" + A + ")") = 1 + depth(A) 关键是这句话理解就好了
// 分析到最后就是把左括号竟可能的分成两个序列即可
func main() {
	seq := "(()())"
	ans := maxDepthAfterSplit(seq)
	fmt.Println(ans)
}

2020/4/2

leetcode 289. 生命游戏_Go

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
package main

import (
	"fmt"
)

func abs(a int) int {
	if a < 0 {
		return -a
	}
	return a
}

func gameOfLife(board [][]int) {
	way := [3]int{0, 1, -1}
	row := len(board)
	col := len(board[0])
	// select every node
	for i := 0; i < row; i++ {
		for j := 0; j < col; j++ {
			aliveNum := 0
			// select each direction
			// 和迷宫走法一样
			for x := 0; x < 3; x++ {
				for y := 0; y < 3; y++ {
					if way[x] != 0 || way[y] != 0 {
						r := way[x] + i
						c := way[y] + j
						// check border
						if (r >= 0 && r < row) && (c >= 0 && c < col) {
							if abs(board[r][c]) == 1 {
								aliveNum++
								fmt.Println(aliveNum, i, j)
							}
						}
					}
				}
			}
			// check status
			// alive ->dead
			if (board[i][j] == 1) && (aliveNum < 2 || aliveNum > 3) {
				board[i][j] = -1
			}
			// dead ->alive
			if (board[i][j] == 0) && (aliveNum == 3) {
				board[i][j] = 2
			}
		}
	}
	for i := 0; i < row; i++ {
		for j := 0; j < col; j++ {
			if board[i][j] > 0 {
				board[i][j] = 1
			} else {
				board[i][j] = 0
			}
		}
	}
}

// 生命游戏，第一眼觉得是个图题，后来才知道主要是为了练符合状态
// 需要变化的是结点本身的状态，改变依据是周围结点的状态
// 硬做的话提前备份一个二维数组就好，尝试一下原地算法
// 原地算法不依赖额外的资源或者依赖少数的额外资源，仅依靠输出来覆盖输入的一种算法操作。
// 需要对改变后的数组状态做一些新的标记，来避免与0/1状态混淆
/*
alive->dead :-1
alive->alive :1
dead->alive :2
*/
func main() {
	var board = make([][]int, 0)
	temp := []int{0, 1, 0}
	board = append(board, temp)
	temp = []int{0, 0, 1}
	board = append(board, temp)
	temp = []int{1, 1, 1}
	board = append(board, temp)
	temp = []int{0, 0, 0}
	board = append(board, temp)
	fmt.Println(board)
	gameOfLife(board)
	fmt.Println(board)
}

2020/4/3

leetcode 8. 字符串转换整数_Go

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
package main

import (
	"fmt"
	"math"
	"strings"
	"unicode"
)

// 自动机什么的是学不会的，但各种情况的逻辑判断需要好好锻炼
func myAtoi(str string) int {
	flag := 1
	// 按找空白符分割字符串成一个切片
	strSlice := strings.FieldsFunc(str, unicode.IsSpace)
	//fmt.Println(strSlice, reflect.TypeOf(strSlice))
	// 分割后只需要判断切片内第一个元素即可
	var temp string
	// 防止输入""
	if len(strSlice) == 0 {
		return 0
	}
	if !unicode.IsDigit(rune(strSlice[0][0])) {
		if strSlice[0][0] == '+' {
			flag = 1
			strSlice[0] = strSlice[0][1:]
			//fmt.Println(strSlice[0])
		} else if strSlice[0][0] == '-' {
			flag = -1
			strSlice[0] = strSlice[0][1:]
		} else {
			return 0
		}
	}
	first := strSlice[0]
	for i := 0; i < len(first); i++ {
		if !unicode.IsDigit(rune(first[i])) {
			break
		} else {
			temp += string(first[i])
		}
	}
	// strToNum
	ans := 0
	for i := 0; i < len(temp); i++ {
		ans = int(temp[i]-'0') + ans*10
		if ans*flag > math.MaxInt32 {
			return math.MaxInt32
		}
		if ans*flag < math.MinInt32 {
			return math.MinInt32
		}
	}
	return flag * ans
}

func main() {
	//str := "-996 9k3 and 987"
	//str2 := "words and 987"
	str3 := "-91283472332"
	fmt.Println(myAtoi(str3))
}

2020/4/4

leetcode 42. 接雨水_Go

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
package main

import "fmt"

// 暴力思维：两边最大高度的较小值减去当前高度的值
// 但暴力不可取，还是不暴力了……
// 题解里那个栈的应用是真的没想到，tcl
// 用two pointers来解决
func trap(height []int) int {
	left := 0
	right := len(height) - 1
	ans := 0
	leftMax, rightMax := 0, 0
	for left < right {
		if height[left] < height[right] {
			if height[left] >= leftMax {
				leftMax = height[left]
			} else {
				ans += leftMax - height[left]
			}
			left++
		} else {
			if height[right] >= rightMax {
				rightMax = height[right]
			} else {
				ans += rightMax - height[right]
			}
			right--
		}
	}
	return ans
}

func main() {
	height := []int{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1}
	fmt.Println(trap(height))
}

2020/4/5

leetcode 460. LFU缓存_Go

真难……

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
package main

import "fmt"

// Node struct
type Node struct {
	key, value int
	num        int   // 调用次数
	prev, next *Node // 前序，后继指针，为双重链表做准备
}

// DoubleList prepare for freeList
type DoubleList struct {
	head, tail *Node
}

// ConstructorDB init
func ConstructorDB() *DoubleList {
	head, tail := &Node{}, &Node{}
	head.next, tail.prev = tail, head
	return &DoubleList{
		head: head,
		tail: tail,
	}
}

// LFUCache struct
type LFUCache struct {
	capacity int
	rest     int // 剩余容量
	minFreq  int // 当前最少num
	cache    map[int]*Node
	freqList map[int]*DoubleList // key是调用的num，每个建对应的值是一个链表,越靠近头结点调用的越近
}

// Constructor init
func Constructor(capacity int) LFUCache {
	return LFUCache{
		capacity: capacity,
		rest:     capacity,
		cache:    make(map[int]*Node),
		freqList: make(map[int]*DoubleList),
		minFreq:  0,
	}
}

// Remove node from DoubleList
func (p *DoubleList) Remove(node *Node) {
	node.prev.next = node.next
	node.next.prev = node.prev
	node.next = nil
	node.prev = nil
}

// IsEmpty -> Judge if DoubleList is empty
func (p *DoubleList) IsEmpty() bool {
	return p.head.next == p.tail
}

// AddNode -> add node to doubleList
func (p *DoubleList) AddNode(node *Node) {
	node.next = p.head.next
	node.prev = p.head
	p.head.next.prev = node
	p.head.next = node
}

// UpdateFre freeList
func (p *LFUCache) UpdateFre(node *Node) {
	freq := node.num
	p.freqList[freq].Remove(node)
	// Judge if its num is min
	if p.minFreq == freq && p.freqList[freq].IsEmpty() {
		p.minFreq++
		delete(p.freqList, freq)
	}
	node.num++
	if p.freqList[node.num] == nil {
		p.freqList[node.num] = ConstructorDB()
	}
	p.freqList[node.num].AddNode(node)
}

// Get output
func (p *LFUCache) Get(key int) int {
	node, ok := p.cache[key]
	if ok {
		p.UpdateFre(node)
		return node.value
	}
	return -1
}

// RemoveLast -> remove last node
func (p *DoubleList) RemoveLast() *Node {
	if p.IsEmpty() {
		return nil
	}
	last := p.tail.prev
	p.Remove(last)
	return last
}

// Put input
func (p *LFUCache) Put(key int, value int) {
	if p.capacity == 0 {
		return
	}
	node, ok := p.cache[key]
	if ok {
		node.value = value
		p.UpdateFre(node)
	} else {
		if p.rest == 0 {
			node := p.freqList[p.minFreq].RemoveLast()
			delete(p.cache, node.key)
			p.rest++
		}
		temp := &Node{key: key, value: value, num: 1}
		p.cache[key] = temp
		if p.freqList[1] == nil {
			p.freqList[1] = ConstructorDB()
		}
		p.freqList[1].AddNode(temp)
		p.minFreq = 1
		p.rest--
	}
}

func main() {
	cache := Constructor(2)
	cache.Put(1, 1)
	cache.Put(2, 2)
	fmt.Println(cache.Get(1)) // 返回 1
	cache.Put(3, 3)           // 去除 key 2
	fmt.Println(cache.Get(2)) // 返回 -1 (未找到key 2)
	fmt.Println(cache.Get(3)) // 返回 3
	cache.Put(4, 4)           // 去除 key 1
	fmt.Println(cache.Get(1)) // 返回 -1 (未找到 key 1)
	fmt.Println(cache.Get(3)) // 返回 3
	fmt.Println(cache.Get(4)) // 返回 4
}

2020/4/6

今天的每日一题我直接放弃了，做之前简单的吧……

leetcode 1013. 将数组分成相等的三个部分_Go

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
package main

import "fmt"

func canThreePartsEqualSum(A []int) bool {
	sum := 0
	for i := 0; i < len(A); i++ {
		sum += A[i]
	}
	if sum%3 != 0 {
		return false
	}
	target := sum / 3
	idx, sumTemp := 0, 0
	for idx < len(A) {
		sumTemp += A[idx]
		if sumTemp == target {
			break
		}
		idx++
	}
	if sumTemp != target {
		return false
	}
	idx++
	for idx+1 < len(A) { // 满足最后一部分非空
		sumTemp += A[idx]
		if sumTemp == 2*target {
			return true
		}
		idx++
	}
	return false
}

func main() {
	A := []int{0, 2, 1, -6, 6, -7, 9, 1, 2, 0, 1}
	fmt.Println(canThreePartsEqualSum(A))
}

2020/4/7

leetcode 面试题 01.07. 旋转矩阵_Go

我自己本身没有去纠结原地算法，我觉得这一题让我进一步了解copy这个机制已经有收获了

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
package main

import "fmt"

func rotate(matrix [][]int) {
	length := len(matrix)
	ans := make([][]int, length)
	for i := 0; i < length; i++ {
		ans[i] = make([]int, length)
	}
	for i := 0; i < length; i++ {
		for j := 0; j < length; j++ {
			ans[j][length-i-1] = matrix[i][j]
		}
	}
	copy(matrix, ans)
}

func main() {
	matrix := [][]int{
		{1, 2, 3},
		{4, 5, 6},
		{7, 8, 9},
	}
	rotate(matrix)
	fmt.Println(matrix)
}

2020/4/8

leetcode 面试题13. 机器人的运动范围_Go

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
64
65
66
67
68
package main

import "fmt"

func addNum(a int) int {
	ans := 0
	for a > 0 {
		ans += a % 10
		a /= 10
	}
	return ans
}

func judge(row, col, m, n, k int, visit [][]int) bool {
	if row < 0 || row >= m {
		return false
	}
	if col < 0 || col >= n {
		return false
	}
	if visit[row][col] == 1 {
		return false
	}
	visit[row][col] = 1
	ans := addNum(row) + addNum(col)
	return ans <= k
}

func movingCount(m int, n int, k int) int {
	visit := make([][]int, m)
	for i := 0; i < m; i++ {
		visit[i] = make([]int, n)
	}
	num := 0
	// init queue
	queue := [][]int{}
	temp := []int{0, 0}
	queue = append(queue, temp)
	visit[0][0] = 1
	// BFS
	for len(queue) != 0 {
		top := queue[0]
		queue = queue[1:]
		num++
		if judge(top[0]-1, top[1], m, n, k, visit) {
			temp = []int{top[0] - 1, top[1]}
			queue = append(queue, temp)
		}
		if judge(top[0]+1, top[1], m, n, k, visit) {
			temp = []int{top[0] + 1, top[1]}
			queue = append(queue, temp)
		}
		if judge(top[0], top[1]-1, m, n, k, visit) {
			temp = []int{top[0], top[1] - 1}
			queue = append(queue, temp)
		}
		if judge(top[0], top[1]+1, m, n, k, visit) {
			temp = []int{top[0], top[1] + 1}
			queue = append(queue, temp)
		}
	}
	return num
}

func main() {
	fmt.Println(movingCount(2, 3, 1))
}

2020/4/9

leetcode 22. 括号生成_Go

这题我是用暴力做的

但引出了切片作为函数参数这个大坑，资料:https://www.jianshu.com/p/7439e7ae3c4c

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
package main

import "fmt"

// 先用暴力算法写
// 要是这题的思路弄清楚，我觉得递归就入门了，学习一下

func generateParenthesis(n int) []string {
	var current string
	var result = []string{}
	generateAll(&current, n*2, &result)
	//fmt.Println(result)
	return result
}

func generateAll(current *string, n int, result *[]string) {
	if n == len(*current) {
		if valid(*current) {
			*result = append(*result, *current)
			//fmt.Println(result)
		}
		return
	}
	*current += "("
	generateAll(current, n, result)
	*current = (*current)[:len(*current)-1]
	*current += ")"
	generateAll(current, n, result)
	*current = (*current)[:len(*current)-1]
}

func valid(str string) bool {
	balance := 0
	for i := 0; i < len(str); i++ {
		if string(str[i]) == "(" {
			balance++
		} else {
			balance--
			if balance < 0 {
				return false
			}
		}
	}
	return balance == 0
}

func main() {
	ans := generateParenthesis(3)
	fmt.Println(ans)
}

本文作者： xiaoyuyu
本文链接： http://woaixiaoyuyu.github.io/2020/03/05/%E7%AE%97%E6%B3%95every-day/
版权声明： 本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。转载请注明出处！
赏

谢谢你请我吃糖果

扫一扫，分享到微信

微信分享二维码
本站总访问量次 本站访客数人

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

记录成长的点滴<br><br>涉猎颇广的信息技术爱好者<br>希望未来的xiaoyuyu<br>可以成为优秀的工程师