发表于

这是我参与11月更文挑战的第26天，活动详情查看：2021最后一次更文挑战

概述

状态模式（State Pattern）是当一个对象的内部状态改变时，允许其行为的改变，这个对象的类看起来像被修改了。因此又称为状态对象(Objects for States)模式，是一种对象行为型模式。

状态模式主要用来解决系统中的两种问题，其一是复杂对象状态的转换，另一种是对象在不同状态下的行为的封装。当系统中的某个对象存在多种状态，并且这些状态之间可以进行转换，而对象在不同的状态下行为不同，此时就可以使用状态模式。

状态模式将一个对象的状态从该对象中抽离出来，将其封装到专门的状态类中，使对象的状态可以灵活的变化。对于客户端而言，无须关心对象状态的转换以及对象当前所处的状态，无论对于何种状态的对象，客户端都可以一致处理。

结构

状态模式UML.png

  • Context（环境类）：又称为上下文类，它是拥有多种状态的对象。
  • State（抽象状态类）：一般为接口或抽象类，定义了环境类的一个特定状态的行为。
  • ConcreteState（具体状态类）：每一个具体状态类实现环境类的一个特定状态的行为。

优点

  1. 将对象的行为与状态解耦，降低了系统的复杂度，提高了系统的可维护性，符合单一职责原则。
  2. 增加对象的行为不必修改客户端的代码，符合开闭原则。
  3. 可以让多个环境对象共享一个状态对象，从而减少系统中对象的个数。
  4. 对象状态的变换放到了内部，客户端不必知道类的内部是如何实现状态和行为的切换的，符合迪米特法则。

缺点

  1. 状态过多，会造成类膨胀，不利于维护。
  2. 会增加系统中类和对象的个数，导致系统运行开销增大。
  3. 状态模式的结构与实现都较为复杂，如果使用不当将导致程序结构和代码的混乱。
  4. 增加新的状态类时，需要修改负责状态转换的源代码，不符合开闭原则。

应用场景

  1. 行为会随着状态的改变而改变。
  2. 当程序中需要使用大量的条件、分支判断语句时，可以考虑使用状态模式。

JDK 中的应用

在 JDK 中 java.util.Iterator 就使用了状态模式。

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

这是我参与11月更文挑战的第23天，活动详情查看：2021最后一次更文挑战」

easyExcel

导入依赖（easyexcel依赖中已经有poi的依赖）

1
2
3
4
5
xml复制代码<dependency>
            <groupId>com.alibaba</groupId>
            <artifactId>easyexcel</artifactId>
            <version>2.1.6</version>
        </dependency>

字段实体类

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
typescript复制代码public class excel {
    @ExcelProperty("字符串标题")
    private String string;
    @ExcelProperty("日期标题")
    private Date date;
    @ExcelProperty("数字标题")
    private int aDouble;
​
    public excel() {
    }
​
    public excel(String string, Date date, int aDouble) {
        this.string = string;
        this.date = date;
        this.aDouble = aDouble;
    }
​
    public String getString() {
        return string;
    }
​
    public void setString(String string) {
        this.string = string;
    }
​
    public Date getDate() {
        return date;
    }
​
    public void setDate(Date date) {
        this.date = date;
    }
​
    public int getaDouble() {
        return aDouble;
    }
​
    public void setaDouble(int aDouble) {
        this.aDouble = aDouble;
    }
}
​

指定列的前后顺序

1
2
3
4
5
6
ini复制代码@ExcelProperty(value = "姓名",index = 1)
    private String string;
    @ExcelProperty(value = "日期",index = 2)
    private Date date;
    @ExcelProperty(value = "学号",index = 0)
    private int aDouble;

如果指定列写入，那么忽略的列就会空出来

复杂头

1
2
3
4
5
6
kotlin复制代码@ExcelProperty({"主标题", "字符串标题"})
    private String string;
    @ExcelProperty({"主标题", "日期标题"})
    private Date date;
    @ExcelProperty({"主标题", "数字标题"})
    private int aDouble;

image.png

写入

将数据写入list

1
2
3
4
5
6
7
8
9
10
11
12
ini复制代码   //写入list
    private List<excel> data(){
        List< excel > excels = new ArrayList<>();
        for(int i = 0;i < 10; i++){
            excel e = new excel();
            e.setaDouble(i);
            e.setString("yzy");
            e.setDate(new Date());
            excels.add(e);
        }
        return excels;
    }

简单的写入方法

list写入excel

1
2
3
4
5
6
7
csharp复制代码 //将list写入excel
    @Test
    public void write(){
        //   第一个参数为路径，第二个参数为标题的实体类
//          然后写入木板，再将执行list方法
        EasyExcel.write(PATH+"easy.xlsx",excel.class).sheet("模板").doWrite(data());
    }

image.png

指定列写入

set用来存储需要忽略的列名,add指定忽略的列,列明为字段名

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
vbnet复制代码public void daochuzhidinglie(){
        /*忽略到导出的列*/
​
        Set<String> set = new HashSet<>();
        set.add("aDouble");
        //过滤写入
        EasyExcel.write(PATH+"导出指定列1.xlsx",excel.class).excludeColumnFiledNames(set).sheet("1").doWrite(data());
​
        /*指定要导出的列*/
        /*//set用来存储需要忽略的列名
        Set<String> set1 = new HashSet<>();
        set1.add("date");
        set1.add("string");
        //过滤写入
        EasyExcel.write(PATH+"导出指定列1.xlsx",excel.class).includeColumnFiledNames(set1).sheet("指定学号名称").doWrite(data());
   */ }

忽略学号

image.png

注意点，如果指定了列的顺序，那么指定列写入就会使其他的列空着

image.png

写入图片

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
ini复制代码public void pic() throws Exception {
        //InputStream inputStream = null;
        ArrayList< excel > excels = new ArrayList<>();
        excel excel = new excel();
        //图片路径
        String picPath = PATH+"1.jpg";
     /*五种类型的图片*/
        excel.setBytes(FileUtils.readFileToByteArray(new File(picPath)));
        //excel.setFile(new File(picPath));
        //excel.setPic(picPath);
        //inputStream = FileUtils.openInputStream(new File(picPath));
        //excel.setUrl(new URL(""));
​
        excels.add(excel);
        EasyExcel.write(PATH+"pic.xlsx",excel.class).sheet().doWrite(excels);
        //inputStream.close();
    }

image.png

读取

监听器

读取exccel数据，需要一个监听器用于判断
每次读取100条数据就进行保存操作,由于每次读都是新new UserInfoDataListener的，所以这个list不会存在线程安全问题.
读取到的数据会变成JSON字符串打印出来,放入list中,判断list存的数据是否超过限度,超过就存入数据库并将list清空

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
csharp复制代码public class UserInfoDataListener extends AnalysisEventListener<excel> {
    
    private static final int BATCH_COUNT = 100;
    List<excel> list = new ArrayList<>();
​
    @Override
    //excel 类型
    //AnalysisContext 分析上下文
    public void invoke(excel data, AnalysisContext analysisContext) {
        System.out.println("解析到一条数据:{}"+ JSON.toJSONString(data));
        list.add(data);
        if (list.size() >= BATCH_COUNT) {
            saveData();
            // 存储完成清理 list
            list.clear();
        }
    }
​
    @Override
    public void doAfterAllAnalysed(AnalysisContext analysisContext) {
        // 这里也要保存数据，确保最后遗留的数据也存储到数据库
        saveData();
        System.out.println("所有数据解析完成！");
    }
​
    //写入数据库的业务
    private void saveData() {
        System.out.println("{}条数据，开始存储数据库！" +list.size());
        //userService.save(list);
        System.out.println("存储数据库成功！");
    }
}

读取方法: read的第三个参数是监听器用于判断list中的数据是否存入数据库

1
2
3
4
5
csharp复制代码@Test
    public void read(){
        
        EasyExcel.read(PATH+"easy.xlsx",excel.class,new UserInfoDataListener()).sheet().doRead();
    }

image.png

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

「这是我参与11月更文挑战的第9天，活动详情查看：2021最后一次更文挑战」。

对称二叉树是我们数据结构中常用的一类数据结构，今天我们使用算法来对其进行校验什么样的树称得上对称二叉树。

题目描述

给定一个二叉树，检查它的对称左右子树是否镜像对称的。

题目示例

题目解法

解法一：递归实现（推荐）

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
kotlin复制代码/**
 * Definition for a binary tree node.
 * public 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;
 *     }
 * }
 */
 /**
  * 递归实现
  */
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root == null){
            return true;
        }
        return validateNode(root.left, root.right);
    }

    public boolean validateNode(TreeNode left, TreeNode right){
        if(left == null && right == null){
            return true;
        }
        if(left == null || right == null){
            return false;
        }
        if(left.val != right.val){
            return false;
        }
        // 递归实现
        return validateNode(left.left, right.right) && validateNode(left.right, right.left);
    }
}

解法二：迭代实现

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
csharp复制代码/**
  * 迭代实现
  */
class Solution {
    
    public boolean isSymmetric(TreeNode root) {
        return validate(root.left, root.right);
    }

    public boolean validate(TreeNode left, TreeNode right){
        if (left == null && right == null){
            return true;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(left);
        queue.add(right);
        // 迭代判空
        while (!queue.isEmpty()){
            TreeNode q = queue.poll();
            TreeNode p = queue.poll();
            if (q == null && p == null){
                continue;
            }
            if (q == null || p == null){
                return false;
            }
            if (q.val != p.val){
                 return false;
            }
            queue.add(q.left);
            queue.add(p.right);

            queue.add(q.right);
            queue.add(p.left);
        }
        return true;
    }
}

LeetCode原题链接：leetcode-cn.com/problems/sy…

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

这是我参与11月更文挑战的第23天，活动详情查看：2021最后一次更文挑战.

DFS序

DFS序的定义

将树节点按dfs过程中的访问顺序排序，称为dfs序。

性质

一个节点和它的子树在一个连续的区间中。

时间戳

在dfs过程中，设访问一个新节点需要花费1s的时间，我们可以记录下每个节点的进入时间与退出时间，称为时间戳。显然进入时间是dfs序的反函数，即dfs序中的第i个点的进入时间是i。

1
2
3
4
5
6
7
8
9
cpp复制代码int st[M], ed[M];
void dfs(int now, int fa = 0)
{
	static int cnt = 0;
	st[now] = ++cnt;
	for(int i = fst[now]; i; i = nxt[i])
		if(pnt[i] != fa) dfs(pnt[i],now);
	ed[now] = cnt;
}

应用

1.判断节点的从属关系

如果st[x]<st[y]并且ed[x]>=ed[y]，那么x是y的祖先。

2.POJ 3321 Apple Tree

一棵树，操作一改变一个点的权值，操作二求以某个点为根的子树的权值和。

如果求出了这棵树的dfs序，就可以将问题从树转化为数字序列上的问题。
操作1：单点修改
操作2：区间求和，范围是st[x],ed[x]
使用树状数组维护即可。

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
cpp复制代码#include <cstdio>
const int M = 100016;
int n;
/*链式前向星-开始*/
int fst[M*2], pnt[M*2], nxt[M*2];
void add(int x, int y)
{
	static int tot = 0;
	pnt[++tot] = y;
	nxt[tot] = fst[x];
	fst[x] = tot;
}
/*链式前向星-结束*/

/*dfs序-开始*/
int st[M], ed[M];
void dfs(int now, int fa = 0)
{
	static int cnt = 0;
	st[now] = ++cnt;
	for(int i = fst[now]; i; i = nxt[i])
		if(pnt[i] != fa) dfs(pnt[i],now);
	ed[now] = cnt;
}
/*dfs序-结束*/

/*树状数组-开始*/
int bit[M];
inline void modify(int p, int x)
{
	for(;p<=n;p+=p&-p) bit[p]+=x;
}
inline int sum(int p)
{
	int res = 0;
	for(;p;p-=p&-p) res += bit[p];
	return res;
}
inline int sum(int l, int r)
{
	return sum(r) - sum(l-1);
}
/*树状数组-结束*/
int main(void)
{
	scanf("%d",&n);
	for(int i=1,a,b;i<n;i++)
	{
		scanf("%d%d",&a,&b);
		add(a,b), add(b,a);
	}
	dfs(1);
	for(int i=1;i<=n;i++)
		modify(i,1);
	int q,node;
	char op[3];
	scanf("%d",&q);
	while(q--)
	{
		scanf("%s %d",op,&node);
		if(op[0]=='Q')
			printf("%d\n",sum(st[node],ed[node]) );
		else
			modify(st[node],sum(st[node],st[node])?-1:1);
	}

	return 0;
}

欧拉序

欧拉序的定义

树在dfs过程中的节点访问顺序称为欧拉序.

欧拉序有很多种，只要整体满足dfs顺序即算欧拉序，应当按实际需要选择适合的欧拉序。
欧拉序与dfs序不同地方在于，欧拉序中每个节点可以出现多次，比如进入一次退出一次，又比如每次回溯时记录一次。

1.每次访问一个节点时记录一次

应用：LCA归约为RMQ

这也是最经典的应用。

LCA（Lowest Common Ancestors），即最近公共祖先，是指在有根树中，找出某两个结点u和v最近的公共祖先。
RMQ（Range Minimum/Maximum Query），即区间最值查询，是指在数列中求一段区间的最大或最小值。
ST表（Sprase Table），Tarjan发明，可以预处理复杂度O(nlogn)，查询复杂度O(1)地解决RMQ问题，不支持修改.
参见：RMQ问题与Sparse Table算法

假设现在需要求x和y的LCA，跑一遍欧拉序并记录时间戳st和ed后，st[x],st[y],ed[x],ed[y]的大小关系只有两种情况（交换后）：

  1. st[x]<st[y]<=ed[y]<=ed[x]，表示x是y的祖先。
    此时x与y的LCA就是x。
  2. st[x]<=ed[x]<st[y]<=ed[y]，表示x与y没有祖先-后裔关系。
    在ed[x]与st[y]之间的节点中深度最小的节点，就是x与y的LCA（不妨纸上画一画）

在实现时，先对欧拉序建立st表，比较规则是选择深度小的，查询只要查询min(deep[x],deep[y]),max(deep[x],deep[y])之间深度最小的节点即可。
实际上，可以不用额外统计深度，而把比较规则改为选择st[x]小的。（想一想，为什么）

代码

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
cpp复制代码int st[M], ed[M];
int euler[M*2],cnt;
void dfs(int now,int fa=0)
{
    euler[++cnt] = now;
    st[now] = cnt;
    for(auto nxt:edge[now]) if(nxt!=fa)
    {
        dfs(nxt,now);
        euler[++cnt] = now;
    }
    ed[now] = cnt;
}

SpraseTable stable;
void lca_init()
{
    dfs(root);
    stable = SpraseTable(euler,cnt,[](int a,int b){return st[a]<st[b]?a:b;});
}
int lca_query(int a, int b)
{
    int a = st[read()], b=st[read()];
    printf("%d\n",stable.query(min(a,b),max(a,b)));
}
Luogu P3379【模板】最近公共祖先（LCA）

模板题

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
cpp复制代码#include <bits/stdc++.h>
using namespace std;
inline int read();
const int M = 1000016;
int n,m,s;
vector<int> edge[M];

/*欧拉序-开始*/
int st[M], ed[M],deep[M];
int euler[M*2],cnt;
void dfs(int now,int fa=0)
{
	euler[++cnt] = now;
	st[now] = cnt;
	deep[now] = deep[fa]+1;
	for(auto nxt:edge[now]) if(nxt!=fa)
	{
		dfs(nxt,now);
		euler[++cnt] = now;
	}
	ed[now] = cnt;
}
/*欧拉序-结束*/

/*ST表-开始*/
class SpraseTable
{
    static int lg[M];
    int n;
    function<int(int,int)> cmp;
    vector<vector<int>> table; //table[i][j]表示长度为2^i的以j开头的数组最值
public:
    SpraseTable(int *arr, int _n, 
        function<int(int,int)> _cmp = [](int a,int b){return a<b?a:b;}
    ) : n(_n), cmp(_cmp)
    {
        if(!lg[0]) {lg[0]=-1;for(int i=1;i<M;i++)lg[i]=lg[i/2]+1;}
        table = vector<vector<int>>(lg[n] + 1, vector<int>(n + 1));
        for(int i = 1; i <= n; i++)
            table[0][i] = arr[i];
        for(int i = 1; i <= lg[n]; i++)
            for(int j = 1; j <= n; j++)
                if(j + (1 << i) - 1 <= n)
                    table[i][j] = cmp(table[i-1][j], table[i-1][j+(1<<(i-1))]);
    }
    inline int query(int x, int y)
    {
        int t = lg[y - x + 1];
        return cmp(table[t][x], table[t][y - (1 << t) + 1]);
    }
};int SpraseTable::lg[M];

/*ST表-结束*/

int main(void)
{
	//freopen("in.txt","r",stdin);
	n=read(),m=read(),s=read();
	for(int i=1,a,b;i<n;i++)
	{
		a=read(),b=read();
		edge[a].push_back(b);
		edge[b].push_back(a);
	}
	dfs(s);
	SpraseTable stable(euler,cnt,[](int a,int b){return st[a]<st[b]?a:b;});

	while(m--)
	{
		int a = st[read()], b=st[read()];
		if(a>b) swap(a,b);
		printf("%d\n",stable.query(a,b));
	}

	return 0;
}
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
HDU - 2586 How far away ？

给一棵带边权的无根树，若干次询问，每次询问两个节点的最短距离。

以任意一点为根建立欧拉序，同时dfs出所有节点到根节点的距离，询问a,b的答案就是dis[a]+dis[b]-2*dis[lca(a,b)]

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
cpp复制代码/* LittleFall : Hello! */
#include <bits/stdc++.h>
using namespace std; typedef long long ll;
inline int read(); inline void write(int x);
const int M = 100016, MOD = 1000000007;

int n,q;
ll dis[M]; //距原点的距离
/*ChainForwardStar*/
int pnt[M], nxt[M], fst[M], pri[M], tot;
void add(int a, int b, int p)
{
	pnt[++tot] = b;
	pri[tot] = p;
	nxt[tot] = fst[a];
	fst[a] = tot;
}
/**/

/*欧拉序*/
int st[M],ed[M],euler[M],cnt;
void dfs(int now, int fa = 0)
{
	euler[++cnt] = now;
	st[now] = cnt;
	for(int e=fst[now],son=pnt[e];e;e=nxt[e],son=pnt[e]) if(son!=fa)
	{
		dis[son] = dis[now] + pri[e];
		dfs(son,now);
		euler[++cnt] = now;
	}
	ed[now] = cnt;
}
/**/
class SpraseTable
{
    static int lg[M];
    int n;
    function<int(int,int)> cmp;
    vector<vector<int>> table; //table[i][j]表示长度为2^i的以j开头的数组最值
public:
    SpraseTable(int *arr, int _n, 
        function<int(int,int)> _cmp = [](int a,int b){return a<b?a:b;}
    ) : n(_n), cmp(_cmp)
    {
        if(!lg[0]) {lg[0]=-1;for(int i=1;i<M;i++)lg[i]=lg[i/2]+1;}
        table = vector<vector<int>>(lg[n] + 1, vector<int>(n + 1));
        for(int i = 1; i <= n; i++)
            table[0][i] = arr[i];
        for(int i = 1; i <= lg[n]; i++)
            for(int j = 1; j <= n; j++)
                if(j + (1 << i) - 1 <= n)
                    table[i][j] = cmp(table[i-1][j], table[i-1][j+(1<<(i-1))]);
    }
    inline int query(int x, int y)
    {
        int t = lg[y - x + 1];
        return cmp(table[t][x], table[t][y - (1 << t) + 1]);
    }
};int SpraseTable::lg[M];

int main(void)
{
	#ifdef _LITTLEFALL_
	freopen("in.txt","r",stdin);
    #endif

	int T = read();
	while(T--)
	{
		memset(dis,0,sizeof(dis));
		memset(pnt,0,sizeof(pnt));
		memset(nxt,0,sizeof(nxt));
		memset(fst,0,sizeof(fst));
		memset(pri,0,sizeof(pri));
		memset(st,0,sizeof(st));
		memset(ed,0,sizeof(ed));
		memset(euler,0,sizeof(euler));
		tot = cnt = 0;
		n=read(), q=read();
		for(int i=1,a,b,p;i<n;i++)
		{
			a=read(),b=read(),p=read();
			add(a,b,p);
			add(b,a,p);
		}
		dfs(1);
		SpraseTable stable(euler,cnt,[](int a,int b){return st[a]<st[b]?a:b;});
		while(q--)
		{
			int a = read(), b=read();
			int lca = stable.query(min(st[a],st[b]),max(st[a],st[b]));
			printf("%I64d\n",dis[a]+dis[b]-dis[lca]-dis[lca] );
		}
	}

    return 0;
}


inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
inline void write(int x)
{
     if(x<0) putchar('-'),x=-x;
     if(x>9) write(x/10);
     putchar(x%10+'0');
}

终于学到这里了，可以回去补那个该死的cf1051F了QAQ

2. 欧拉序：进入记录一次，退出记录一次

dfs序与欧拉序的花式用法：DFS序详解-比特飞流
这边的方法好像和树链剖分有很大关系，以后学树剖的时候再看看。

BZOJ4034 树上操作

有一棵点数为 N 的树，以点 1 为根，且树点有边权。然后有 M 个
操作，分为三种：
操作 1 ：把某个节点 x 的点权增加 a 。
操作 2 ：把某个节点 x 为根的子树中所有点的点权都增加 a 。
操作 3 ：询问某个节点 x 到根的路径中所有点的点权和。

这道题，普通做法是树链剖分+数据结构，文艺做法是欧拉序+线段树，玄学做法是欧拉序+树状数组。
好了，因为我不会树链剖分与线段树，使用了玄学做法，参考自(blog.csdn.net/youhavepeop…).

首先求欧拉序，进入记录一次正点权，退出记录一次负点权。
三个操作转化为：

  1. 两个单点修改
  2. 区间修改，正的加，负的减
  3. 区间求和

一个正常的树状数组是做不到第二个操作的，于是用三个树状数组c0,c1,c2维护这个东西。
c0维护原始序列，当有操作1时，c0[st[x]]+=a,c0[ed[x]]−=ac0[st[x]]+=a,c0[ed[x]]-=ac0[st[x]]+=a,c0[ed[x]]−=a
c1记录区间修改，当有操作2时，c1[st[x]]+=a,c1[st[x]]−=ac1[st[x]]+=a,c1[st[x]]-=ac1[st[x]]+=a,c1[st[x]]−=a
c2记录区间修改乘以高度，当有操作2时，c2[st[x]]+=a∗deep[x],c2[ed[x]]−=a∗deep[x]c2[st[x]]+=a*deep[x],c2[ed[x]]-=a*deep[x]c2[st[x]]+=a∗deep[x],c2[ed[x]]−=a∗deep[x]

操作3：ans=sum0(st[x])+sum1(st[x])∗(deep[x]+1)−sum2(st[x])ans = sum_0(st[x])+sum_1(st[x])*(deep[x]+1)-sum_2(st[x])ans=sum0​(st[x])+sum1​(st[x])∗(deep[x]+1)−sum2​(st[x])

多个树状数组的组合，真的很玄学。

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
cpp复制代码#include <bits/stdc++.h>
const int M = 1000016;
typedef long long ll;
inline int read();
int n,m;
int prior[M];
/*链式前向星*/
int fst[M],nxt[M],pnt[M];
void addEdge(int x, int y)
{
	static int tot = 0;
	pnt[++tot] = y;
	nxt[tot] = fst[x];
	fst[x] = tot;
}
/*欧拉序*/
int st[M], ed[M], deep[M], cnt;
void dfs(int now, int fa = 0)
{
	st[now] = ++cnt;
	for(int e = fst[now]; e; e = nxt[e]) if(pnt[e] != fa)
	{
		deep[pnt[e]] = deep[now] + 1;
	    dfs(pnt[e], now);
	}
	ed[now] = ++cnt;
}

/*树状数组*/
ll bit[3][M];
inline void modify(int id, int p, ll x)
{
	for(;p<=cnt;p+=p&-p) bit[id][p]+=x;
}
inline ll sum(int id, int p)
{
	ll res = 0;
	for(;p;p-=p&-p) res += bit[id][p];
	return res;
}


int main(void)
{
	//freopen("in.txt","r",stdin);
	n=read(), m=read();
	for(int i=1;i<=n;i++)
		prior[i] = read();
	for(int i=1,a,b;i<n;i++)
	{
		a = read(), b = read();
		addEdge(a,b);
		addEdge(b,a);
	}
	dfs(1);
	for(int i=1;i<=n;i++)
	{
		modify(0,st[i],prior[i]);
		modify(0,ed[i],-prior[i]);
	}
	while(m--)
	{
		ll op=read(),pos=read(),val;
		if(op==1)
		{
			val=read();
			modify(0, st[pos], val);
			modify(0, ed[pos], -val);
		}
		else if(op==2)
		{
			val=read();
			modify(1, st[pos], val);
			modify(1, ed[pos], -val);
			modify(2, st[pos], val*deep[pos]);
			modify(2, ed[pos], -val*deep[pos]);
		}
		else
		{
			ll ans = sum(0,st[pos])
			 	   + sum(1,st[pos]) * (deep[pos]+1) 
			 	   - sum(2,st[pos]);
			printf("%lld\n",ans );
		}

	}
	return 0;
}
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

前言

我们在前面安装&部署Elasticsearch 7.x，这篇文章了解Elasticsearch中的可视工具Kibana，对存储的文档数据进行可视化。

环境配置

  • CentOS 7+
  • Elasticsearch 7.7.0，需要提前启动；
  • Kibana 7.7.0

操作步骤

Kibana相关配置和操作使用普通用户权限；

  1. 下载Kibana 7.7.0，要与Elasticsearch版本保持一致；
  2. 下载文件名为kibana-7.7.0-linux-x86_64.tar.gz压缩包文件，上传至服务器目录；
  3. 解压到kibana部署目录：
1
bash复制代码tar -zxf kibana-7.7.0-linux-x86_64.tar.gz
  1. 解压完成，目录名称为 kibana-7.7.0-linux-x86_64，如有需要，也可更名为kibana:
1
bash复制代码mv kibana-7.7.0-linux-x86_64 kibana
  1. 进入kibana目录，按需配置；
  2. 开启Kibana服务；
  3. 打开浏览器输入地址，进行访问。

Kibana配置文件

Kibana配置文件路径：

​ config/kibana.yml；

配置内容及说明

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
yml复制代码# Kibana is served by a back end server. This setting specifies the port to use.
# Kibana对外开放端口，默认是5601
server.port: 5601

# Specifies the address to which the Kibana server will bind. IP addresses and host names are both valid values.
# The default is 'localhost', which usually means remote machines will not be able to connect.
# To allow connections from remote users, set this parameter to a non-loopback address.
# Kibana绑定host，默认是localhost，远程及其不能连接；也可以配置本机局域网IP；0.0.0.0，表示所有远程机器可以连接
server.host: "0.0.0.0"
#server.host: "localhost"

# Enables you to specify a path to mount Kibana at if you are running behind a proxy.
# Use the `server.rewriteBasePath` setting to tell Kibana if it should remove the basePath
# from requests it receives, and to prevent a deprecation warning at startup.
# This setting cannot end in a slash.
#server.basePath: ""

# Specifies whether Kibana should rewrite requests that are prefixed with
# `server.basePath` or require that they are rewritten by your reverse proxy.
# This setting was effectively always `false` before Kibana 6.3 and will
# default to `true` starting in Kibana 7.0.
#server.rewriteBasePath: false

# The maximum payload size in bytes for incoming server requests.
#server.maxPayloadBytes: 1048576

# The Kibana server's name.  This is used for display purposes.
#server.name: "your-hostname"

# The URLs of the Elasticsearch instances to use for all your queries.
# Kibana监听elasticsearch实例地址，数组，可配置多个（集群）
elasticsearch.hosts: ["http://localhost:9201"]

# When this setting's value is true Kibana uses the hostname specified in the server.host
# setting. When the value of this setting is false, Kibana uses the hostname of the host
# that connects to this Kibana instance.
#elasticsearch.preserveHost: true

# Kibana uses an index in Elasticsearch to store saved searches, visualizations and
# dashboards. Kibana creates a new index if the index doesn't already exist.
# 配置Kibana在Elasticsearch中的索引
#kibana.index: ".kibana"

# The default application to load.
#kibana.defaultAppId: "home"

# If your Elasticsearch is protected with basic authentication, these settings provide
# the username and password that the Kibana server uses to perform maintenance on the Kibana
# index at startup. Your Kibana users still need to authenticate with Elasticsearch, which
# is proxied through the Kibana server.
# 配置访问elasticsearch实例的用户名和密码
#elasticsearch.username: "kibana"
#elasticsearch.password: "pass"

# Enables SSL and paths to the PEM-format SSL certificate and SSL key files, respectively.
# These settings enable SSL for outgoing requests from the Kibana server to the browser.
# SSL配置
#server.ssl.enabled: false
#server.ssl.certificate: /path/to/your/server.crt
#server.ssl.key: /path/to/your/server.key

# Optional settings that provide the paths to the PEM-format SSL certificate and key files.
# These files are used to verify the identity of Kibana to Elasticsearch and are required when
# xpack.security.http.ssl.client_authentication in Elasticsearch is set to required.
#elasticsearch.ssl.certificate: /path/to/your/client.crt
#elasticsearch.ssl.key: /path/to/your/client.key

# Optional setting that enables you to specify a path to the PEM file for the certificate
# authority for your Elasticsearch instance.
#elasticsearch.ssl.certificateAuthorities: [ "/path/to/your/CA.pem" ]

# To disregard the validity of SSL certificates, change this setting's value to 'none'.
#elasticsearch.ssl.verificationMode: full

# Time in milliseconds to wait for Elasticsearch to respond to pings. Defaults to the value of
# the elasticsearch.requestTimeout setting.
#elasticsearch.pingTimeout: 1500

# Time in milliseconds to wait for responses from the back end or Elasticsearch. This value
# must be a positive integer.
#elasticsearch.requestTimeout: 30000

# List of Kibana client-side headers to send to Elasticsearch. To send *no* client-side
# headers, set this value to [] (an empty list).
#elasticsearch.requestHeadersWhitelist: [ authorization ]

# Header names and values that are sent to Elasticsearch. Any custom headers cannot be overwritten
# by client-side headers, regardless of the elasticsearch.requestHeadersWhitelist configuration.
#elasticsearch.customHeaders: {}

# Time in milliseconds for Elasticsearch to wait for responses from shards. Set to 0 to disable.
#elasticsearch.shardTimeout: 30000

# Time in milliseconds to wait for Elasticsearch at Kibana startup before retrying.
#elasticsearch.startupTimeout: 5000

# Logs queries sent to Elasticsearch. Requires logging.verbose set to true.
#elasticsearch.logQueries: false

# Specifies the path where Kibana creates the process ID file.
# Kibana进程的pid输出路径
#pid.file: /var/run/kibana.pid

# Enables you specify a file where Kibana stores log output.
#logging.dest: stdout

# Set the value of this setting to true to suppress all logging output.
#logging.silent: false

# Set the value of this setting to true to suppress all logging output other than error messages.
#logging.quiet: false

# Set the value of this setting to true to log all events, including system usage information
# and all requests.
#logging.verbose: false

# Set the interval in milliseconds to sample system and process performance
# metrics. Minimum is 100ms. Defaults to 5000.
#ops.interval: 5000

# Specifies locale to be used for all localizable strings, dates and number formats.
# Supported languages are the following: English - en , by default , Chinese - zh-CN .
# Kibana可视化的国际化配置
#i18n.locale: "en"

关键配置说明

  • 特殊端口配置，默认是5601：
1
yaml复制代码server.port: 5601
  • 主机地址配置，默认是localhost，远程不能连接；也可以配置本机局域网IP；配置0.0.0.0，表示所有远程机器可以连接：
1
2
yaml复制代码#server.host: "localhost"
server.host: "0.0.0.0"
  • Kibana配置Elasticsearch实例，该地址和端口必须与Elasticsearch实例中配置的network.host和http.port保持一致：
1
yaml复制代码elasticsearch.hosts: ["http://localhost:9201"]
  • 配置Elasticsearch访问的用户名和密码：
1
2
yaml复制代码elasticsearch.username: "elastic"
elasticsearch.password: "123456"
  • Kibana国际化配置，默认en；汉化配置为zh-CN:
1
yaml复制代码i18n.locale: "en"

Kibana启动

  • 窗口启动：
1
bash复制代码./bin/kibana
  • 后台启动（使用nohup）：
1
bash复制代码nohup ./bin/kibana &

Kibana对外访问

  1. 配置server.host，配置局域网IP或者0.0.0.0：
1
yaml复制代码server.host: "0.0.0.0"
  1. 关闭防火墙（使用root用户操作），也可以通过nginx进行代理：
1
2
3
4
bash复制代码# 关闭防火墙
systemctl stop firewalld
# 查看防火墙状态
systemctl status firewalld
  1. 打开浏览器，输入http://192.168.234.129:5601；
  2. 如设置了密码，访问地址之后，输入用户名密码。

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

这是我参与11月更文挑战的第5天，活动详情查看：2021最后一次更文挑战

引言

最近在学习群里看到群友们在讨论一个问题：并发的向ArrayList里添加10000个元素元素，最后打印出ArrayList的size()，打印结果小于10000，便在群里问这事怎么回事？

首先我们针对三个小伙伴的代码挨个来点评下：

代码检视

第一位

971637857636_.pic.jpg
首先，这个小伙伴饭了一个非常恐怖的错误， for循环里面创建了一万个线程，这对程序来说无疑是一个灾难。虽然这里是一个单机的Demo程序，对于资深的程序员来说，有些东西是要刻在DNA里面的。虽然Java程序员不能像C++程序员对每一块内存都如数家珍，但也不能这么暴殄天物。

其次，这位同学不知道在哪里学到的这个等待线程全部执行完成的方法，while(Thread.activeCount() > 2)很神奇，他还解释说，如果是IDEA这里写2，如果用Eclipse这里写1。说实话还有点可爱。（说明：此方法仅能在运行单机Demo时测试用，在生产环境实不可取的。）好的地方是他考虑到了主线程会早于new出来的线程结束，所以让CPU空转来等待其他线程完成。

说完了编码上的硬伤，我们来看一下这位同学对并发安全的理解：没有理解。他完全没有做任何线程安全的措施，所以输出的结果 9990 是不符合预期的，好吧，我们来看下一位。

第二位

image.png

image.png

在得到其他童鞋的指点后，第二位同学马上做出了调整

第二位的第二次尝试

image.png

image.png

第二位同学放弃了。

ArrayList的线程安全性

大家都知道ArrayList不是线程安全的，那他究竟是怎么不安全了。如何让他变得安全，今天我们就来看看。

啪，很快啊，我就写出了一串代码

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
java复制代码import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.*;

/**
 * ArrayList线程安全实践
 */
public class ArrayListSecturyTest {

    public static void main(String[] args) throws InterruptedException {
        final List<Integer> list = new ArrayList();
        int num = 10000;

        ExecutorService e = new ThreadPoolExecutor(10, 10, 5L, TimeUnit.SECONDS, new ArrayBlockingQueue<Runnable>(num));

        final CountDownLatch countSign = new CountDownLatch(num);
        for (int i = 0; i < num; i++) {
            final int finalI = i;
            e.execute(new Runnable() {
                public void run() {
                    synchronized (list) {
                        list.add(finalI);
                        countSign.countDown();
                    }
                }
            });
        }
        countSign.await();
        e.shutdown();
        System.out.println(list.size());
    }

}

简单说下思路：

// todo

创建一个线程池，然后使用

完整代码：
gitee.com/StephenRead…

执行结果：

不安全的版本
用时：4370 ms
result: 9984520

安全的版本 - 使用synchronize
用时：3410 ms
result: 10000000

安全的版本 - 使用ReentrantLock
用时：6688 ms
result: 10000000

安全的版本 - 使用Collections.synchronizedList(new ArrayList<>())
用时：3033 ms
result: 10000000

Process finished with exit code 0

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

这是我参与11月更文挑战的第24天，活动详情查看：2021最后一次更文挑战

一、准备工作

节点划分如下：
2020-09-0200:48.png

（1）编译

已经得到编译过的包，这步可以越过。

选用 azkaban3.51.0 这个版本自己进行重新编译，编译完成之后得到需要的安装包进行安装。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
bash复制代码cd /opt/lagou/software/

wget https://github.com/azkaban/azkaban/archive/3.51.0.tar.gz

tar -zxvf 3.51.0.tar.gz -C ../servers/

cd /opt/lagou/servers/azkaban-3.51.0/

yum -y install git
yum -y install gcc-c++


# -x test 跳过测试
./gradlew build installDist -x test

（2）上传编译后的安装文件

1
2
3
bash复制代码# 在 linux122 节点创建目录

mkdir /opt/lagou/servers/azkaban

（3）安装需要软件

  1. Azkaban Web 服务安装包

azkaban-web-server-0.1.0-SNAPSHOT.tar.gz

  1. Azkaban 执行服务安装包

azkaban-exec-server-0.1.0-SNAPSHOT.tar.gz

  1. sql 脚本

azkaban-db-0.1.0-SNAPSHOT.tar.gz

（4）数据库准备

在 linux123 节点，运行如下命令

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
bash复制代码# 解压数据库脚本
tar -zxvf azkaban-db-0.1.0-SNAPSHOT.tar.gz -C /opt/lagou/servers/azkaban

# 进入客户端， 密码：12345678
mysql -uroot -p


# 执行以下命令:

SET GLOBAL validate_password_length=5;
SET GLOBAL validate_password_policy=0;

CREATE USER 'azkaban'@'%' IDENTIFIED BY 'azkaban';
CREATE DATABASE azkaban;

GRANT ALL ON azkaban.* to 'azkaban'@'%' IDENTIFIED BY 'azkaban';
FLUSH PRIVILEGES;

use azkaban;

# 在数据库中运行，加载初始化sql创建表
source /opt/lagou/servers/azkaban/azkaban-db-0.1.0-SNAPSHOT/create-all-sql-0.1.0-SNAPSHOT.sql;

验证一下：

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
bash复制代码mysql> show tables;
+--------------------------+
| Tables_in_azkaban        |
+--------------------------+
| QRTZ_BLOB_TRIGGERS       |
| QRTZ_CALENDARS           |
| QRTZ_CRON_TRIGGERS       |
| QRTZ_FIRED_TRIGGERS      |
| QRTZ_JOB_DETAILS         |
| QRTZ_LOCKS               |
| QRTZ_PAUSED_TRIGGER_GRPS |
| QRTZ_SCHEDULER_STATE     |
| QRTZ_SIMPLE_TRIGGERS     |
| QRTZ_SIMPROP_TRIGGERS    |
| QRTZ_TRIGGERS            |
| active_executing_flows   |
| active_sla               |
| execution_dependencies   |
| execution_flows          |
| execution_jobs           |
| execution_logs           |
| executor_events          |
| executors                |
| project_events           |
| project_files            |
| project_flow_files       |
| project_flows            |
| project_permissions      |
| project_properties       |
| project_versions         |
| projects                 |
| properties               |
| triggers                 |
+--------------------------+
29 rows in set (0.00 sec)

二、配置 Azkaban-web-server

在 linux122 节点下

  1. 解压 azkaban-web-server
1
2
3
4
bash复制代码mkdir /opt/lagou/servers/azkaban

cd /opt/lagou/software/azkaban
tar -zxvf azkaban-web-server-0.1.0-SNAPSHOT.tar.gz -C /opt/lagou/servers/azkaban/
  1. 生成 ssl 证书
1
2
3
4
5
6
7
8
9
10
11
12
13
14
bash复制代码cd /opt/lagou/servers/azkaban/azkaban-web-server-0.1.0-SNAPSHOT

# 生成ssl证书:
keytool -keystore keystore -alias jetty -genkey -keyalg RSA


# 会生成 `keystore`
[root@linux122 azkaban-web-server-0.1.0-SNAPSHOT]# ll
total 8
drwxr-xr-x 3 root root   65 May 29  2019 bin
drwxr-xr-x 2 root root  106 May 29  2019 conf
-rw-r--r-- 1 root root 2242 Sep  2 01:10 keystore
drwxr-xr-x 2 root root 4096 May 29  2019 lib
drwxr-xr-x 6 root root   73 May 29  2019 web

如下图所示：

大红框，输入密码均为 ： azkaban
小红框，输入： y
其他信息，直接回车即可。
2020-09-0201:11.png

  1. 修改 azkaban-web-server 的配置文件
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
bash复制代码cd /opt/lagou/servers/azkaban/azkaban-web-server-0.1.0-SNAPSHOT/conf

vim azkaban.properties

# 修改
default.timezone.id=Asia/Shanghai
jetty.use.ssl=true
jetty.port=8443

# 增加，在 mail.host= 下增加即可
jetty.keystore=keystore
jetty.password=azkaban
jetty.keypassword=azkaban
jetty.truststore=keystore
jetty.trustpassword=azkaban

# 修改
mysql.port=3306
mysql.host=linux123
mysql.database=azkaban
mysql.user=azkaban
mysql.password=azkaban

# 注释如下
#azkaban.executorselector.filters=StaticRemainingFlowSize,MinimumFreeMemory,CpuStatus
  1. 添加属性
1
2
3
4
5
6
7
8
9
10
11
12
13
bash复制代码cd /opt/lagou/servers/azkaban/azkaban-web-server-0.1.0-SNAPSHOT
# 目录下没有，所以需要创建
mkdir -p plugins/jobtypes
cd plugins/jobtypes/


vim commonprivate.properties

# 添加如下

azkaban.native.lib=false
execute.as.user=false
memCheck.enabled=false

三、配置 Azkaban-exec-server

在 linux123 节点上操作

  1. 上传 azkaban-exec-server-0.1.0-SNAPSHOT.tar.gz 包到 linux123 节点上
1
2
3
4
bash复制代码

# 解压缩
tar -zxvf azkaban-exec-server-0.1.0-SNAPSHOT.tar.gz -C /opt/lagou/servers/azkaban/
  1. 修改 azkaban-exec-server 的配置文件
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
bash复制代码cd /opt/lagou/servers/azkaban/azkaban-exec-server-0.1.0-SNAPSHOT/conf

vi azkaban.properties

# 修改
default.timezone.id=Asia/Shanghai
azkaban.webserver.url=https://linux123:8443

mysql.port=3306
mysql.host=linux123
mysql.database=azkaban
mysql.user=azkaban
mysql.password=azkaban


# 增加配置，在 executor.flow.threads=30 下行
executor.port=12321
  1. 分发 exec-server 到 linux121 节点
1
2
3
bash复制代码[root@linux123 servers]# pwd
/opt/lagou/servers
[root@linux123 servers]# scp -r azkaban linux121:$PWD

四、启动服务

  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
bash复制代码# 在 linux121 启动 exec-server
bin/start-exec.sh

# 在 linux123 启动 exec-server
bin/start-exec.sh

# 在 linux122 启动web-server
bin/start-web.sh

# 查看进程是否在，使用 jps
jps


[root@linux121 azkaban-exec-server-0.1.0-SNAPSHOT]# jps
16499 Jps
5044 QuorumPeerMain
4342 NameNode
4442 DataNode
4750 NodeManager
16479 AzkabanExecutorServer

[root@linux123 azkaban-exec-server-0.1.0-SNAPSHOT]# jps
3298 ResourceManager
3798 QuorumPeerMain
6038 Jps
3080 DataNode
3160 SecondaryNameNode
3528 NodeManager
6025 AzkabanExecutorServer
  1. 激活 exec-server

在 linux122 上 运行bin/start-web.sh，用 jps 查看没有对应进程。
查看日志

1
2
3
4
5
6
7
8
9
10
11
12
13
bash复制代码[root@linux122 logs]# pwd
/opt/lagou/servers/azkaban/azkaban-web-server-0.1.0-SNAPSHOT/logs
[root@linux122 logs]# ll
total 8
-rw-r--r-- 1 root root 7301 Sep  2 01:49 azkaban-webserver.log


 at azkaban.webapp.AzkabanWebServer.class(AzkabanWebServer.java:122)
  while locating azkaban.webapp.AzkabanWebServer
Caused by: azkaban.executor.ExecutorManagerException: No active executor found
	at azkaban.executor.ExecutorManager.setupExecutors(ExecutorManager.java:253)
	at azkaban.executor.ExecutorManager.<init>(ExecutorManager.java:131)
	at azkaban.executor.ExecutorManager$$FastClassByGuice$$e1c1dfed.newInstance(<generated>)

需要手动激活 executor

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
bash复制代码# linux121 和 linux123 均要执行

cd /opt/lagou/servers/azkaban/azkaban-exec-server-0.1.0-SNAPSHOT

# 在 linux123 上执行
curl -G "linux123:$(<./executor.port)/executor?action=activate" && echo

# 在 linux121 上执行
curl -G "linux121:$(<./executor.port)/executor?action=activate" && echo



[root@linux123 azkaban-exec-server-0.1.0-SNAPSHOT]# curl -G "linux123:$(<./executor.port)/executor?action=activate" && echo
{"status":"success"}

[root@linux121 azkaban-exec-server-0.1.0-SNAPSHOT]# curl -G "linux121:$(<./executor.port)/executor?action=activate" && echo
{"status":"success"}

访问 ：https://linux122:8443

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

这是我参与11月更文挑战的第24天，活动详情查看：2021最后一次更文挑战

  1. 哪种连续子字符串更长

给你一个二进制字符串 s 。如果字符串中由 1 组成的 最长 连续子字符串 严格长于 由 0 组成的 最长 连续子字符串，返回 true ；否则，返回 false 。

例如，s = “110100010” 中，由 1 组成的最长连续子字符串的长度是 2 ，由 0 组成的最长连续子字符串的长度是 3 。
注意，如果字符串中不存在 0 ，此时认为由 0 组成的最长连续子字符串的长度是 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
arduino复制代码示例 1：

输入：s = "1101"
输出：true
解释：
由 1 组成的最长连续子字符串的长度是 2："1101"
由 0 组成的最长连续子字符串的长度是 1："1101"
由 1 组成的子字符串更长，故返回 true 。

示例 2：

输入：s = "111000"
输出：false
解释：
由 1 组成的最长连续子字符串的长度是 3："111000"
由 0 组成的最长连续子字符串的长度是 3："111000"
由 1 组成的子字符串不比由 0 组成的子字符串长，故返回 false 。

示例 3：

输入：s = "110100010"
输出：false
解释：
由 1 组成的最长连续子字符串的长度是 2："110100010"
由 0 组成的最长连续子字符串的长度是 3："110100010"
由 1 组成的子字符串不比由 0 组成的子字符串长，故返回 false 。

提示：

1 <= s.length <= 100
s[i] 不是 ‘0’ 就是 ‘1’

解题思路

计算每个连续0串和连续1串的长度，找出二者的最长串，判断最长的连续1串是否大于最长的连续0串

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
cpp复制代码class Solution {
public:
    bool checkZeroOnes(string s) {
        int max1(0),max0(0);
        for (int i = 0; i < s.size(); ++i) {
            int st=i;
            while (i<s.size()&&s[i]=='0')
            {
                i++;
            }
            max0=max(max0,i-st);
            st=i;
            while (i<s.size()&&s[i]=='1')
            {
                i++;
            }
            max1=max(max1,i-st);
            i--;
        }
        return max1>max0;
    }
};

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

这是我参与11月更文挑战的第23天，活动详情查看：2021最后一次更文挑战

join如何选择驱动表和被驱动表，大小表怎么选？？

其实平时两张表做join时，我并不会考虑那么多，表和表之间做关联，取对应的字段join一下就好了，但今天在学习了李玥老师的专栏后，其实这后面关系到效率的问题，要是没有处理好，对性能将会造成很大的影响，接下来我们一起来探究，如果有两个大小不同的表做join到底是怎么执行的呢？

1
2
3
4
5
6
7
sql复制代码create Table `t1` (
    `id` int(11) NOT NULL,
    `a` int(11) DEFAULT NULL,
    `b` int(11) DEFAULT NULL,
    PRIMARY KEY (`id`),
    KEY `a` (`a`)
)ENGINE=InnoDB;
1
2
3
4
5
6
7
sql复制代码create Table `t2` (
    `id` int(11) NOT NULL,
    `a` int(11) DEFAULT NULL,
    `b` int(11) DEFAULT NULL,
    PRIMARY KEY (`id`),
    KEY `a` (`a`)
)ENGINE=InnoDB;

t1和t2表，a字段上有索引，b字段上没有索引，我们往t1表插入100条数据，t2表插入1000行数据。

我们看如下的sql：

1
csharp复制代码select * from t1 stright_join t2 on (t1.a = t2.a);

如果我们直接用join，MySQL优化器可能会帮我们选择t1或者t2作为驱动表，但为了我们能够更直观地研究，我们用straight_join让MySQL使用固定的连接方式来执行语句，也就是说，前面的t1表是驱动表，t2表是被驱动表。

我们看下explain的结果可以看出，join的过程中，我们使用了t2表的索引a。

截屏2021-11-25 下午11.57.56.png

执行过程如下所示：

  1. 从t1读入一行数据 R
  2. 从R中取出字段a到t2去查找
  3. 取出t2表中满足条件的行，和 R组成一行，加入结果集
  4. 重复步骤1和3，直到检索到t1的最后一行为止

在这个过程中，我们先遍历t1，然后然后根据t1表中取出的数据，去t2表中查找满足条件的记录，因为用到了t2表的索引，所以我们称之为“index Nested-Loop Join”,NLJ

“index Nested-Loop Join”

我们再来回顾下这个流程：

  1. 对驱动表t1做全表扫描，也就是扫描了100行
  2. 对于每一行的R，根据字段a去t2中扫描，因为a在t2中有索引，我们知道，索引的结构其实就是树结构，所以走的是树搜索过程，因此每次的搜索过程只需要扫描一行，所以对于t2表来说，总共扫描100行
  3. 所以t1的100行加上t2的100行，我们总共扫描了200行数据。

如果我们把上面的流程转换成用伪代码来实现是什么样的呢？

1
2
3
4
5
6
csharp复制代码List<object> a_list = SQL(select * from t1)
for(a_list.size) {
    objectB = select * from t2 where a = a_list.a
    把返回的objectB和a_list[i]组成结果集的一行
}
// 其实这个写法很像salesForce里的SOQL，大家能看懂啥意思就行。

我们可以看到，在这个查询的过程中，我们扫描了200行（t1扫描了100行，t2扫描了100行），但是总共执行了101条语句，对t1只执行了一条sql查询出了所有数据，然后执行100次对t2的查询。对比可见，如果我们用join的话，我们只需要执行一次sql，而用程序来做查询的话，我们需要多执行100次sql。

那我们回归正题，我们应该怎么选择驱动表呢，接着来分析最开始的这条sql。

1
csharp复制代码select * from t1 stright_join t2 on (t1.a = t2.a);

这条语句中，驱动表是走全表扫描，而被驱动表走的是树的索引。假设被驱动表的行数是M，每次在被驱动表查一行数据，我们要先搜索索引a,因为a是辅助索引，所以我们需要回表到主键索引上再次搜索，我们知道，检索一棵树的复杂度是以2为底的M的对数log2M,因为我们要查找两棵树，所以时间乘2，为2log2M。

假设驱动表的行数是N，因为要全表扫描，所以要扫描驱动表N行，每一行数据，又要到被驱动表上匹配一次，所以复杂度为 N + N*2log2M (驱动表的扫描次数 + 驱动表的每一行都要在被驱动表的两棵数上做对比查询也就是N*（上面我们得出的查询两棵树的复杂度2log2M）)

根据N + N*2log2M我们可以知道，N越大，复杂度越高，假设N扩大1000倍，那么扫描行数就会扩大1000倍，但是M扩大1000倍，扫描的行数只会扩大10倍，所以应该让小表来做驱动表。 但是该结论的前提是：“可以使用到被驱动表上的索引”

那如果被驱动表上的索引我们用不到，会发生什么情况呢？

我们改下sql

1
csharp复制代码 select * from t1 straight_join t2 on (t1.a = t2.b);

因为t2表的字段b没有索引，所以我们在去t2表做匹配的时候，需要做一次全表扫描。所以扫描t1表100行，扫描出来的每一行，又要去t2表做全表扫描，总共是100*1000=100000行。这个算法叫 “simple Nested- Loop Join”，但我们很容易发现，这种算法太笨了。

MySQL使用了另一种算法，叫做 “Block Nested-Loop Join”

“Block Nested-Loop Join”

这时候，被驱动表上没有可用的索引，算法的流程变成这样：

  1. 把select * from t1的数据读如线程内存 join_buffer内,相当于把整个t1表放入了内存。
  2. 扫描t2，把t2中的每一行都拿出来和t1进行对比，满足的加入结果集。

C01AED95-A9BD-4FF8-9D3D-9031757A1F92.png

我们可以从explain中看到，两张表都没有用到索引，所以需要做全表扫描，扫描的行数是t1的100行加上t2的1000行，1100行。但是每次从t2中扫描出来的一行，都需要和内存中t1的数据做对比，也就是1000*100=100000次判断。结果和上面我们说的笨笨的 “simple Nested- Loop Join” 是一样的，但是 “Block Nested-Loop Join” 因为是在内存中进行比对，所以速度上会快很多。

那我们在没用到被驱动表上的索引时，应该怎么选驱动表呢？

我们假设小表的行数是N，大表是M，那么

  1. 两个表都做一次全表扫描，所以总的扫描的行数是M+N
  2. 内存的判断次数是M*N

所以此时，不管选谁做大表小表驱动表，结果都是一样的，因为我们在 “Block Nested-Loop Join” 中运用到了join_buffer，我们会想到，那如果join_buffer放不下数据怎么办。

join_buffer大小可以由join_buffer_size来控制，默认值是256k，要是放不下的话，就分段来放，我们如果把join_buffer_size的值改为1200，再执行

1
csharp复制代码select * from t1 stright_join t2 on (t1.a = t2.a);

执行的过程就会变成：

  1. 扫描t1，按顺序读取数据放入join_buffer中，假如说放到88行join_buffer放满了
  2. 扫描t2，把t2中的每一行都取出来，跟join_buffer中的数据做对比，满足的放入结果集
  3. 清空join_buffer
  4. 继续扫描t1，顺序读取最后的12行数据放入join_buffer，然后继续执行步骤2

这也就是 “Block Nested-Loop Join” 中 Block 的含义 分段

虽然我们把t1的数据分成两次放入join_buffer，但是我们总的判断次数还是没变，依旧是（88+12）*1000=100000次。

那我们在这种分段的情况下，应该如何选择驱动表呢？

假设驱动表的行数是N，需要分成K次放入join_buffer，被驱动表的行数是M。因为我们的join_buffer是固定不变的大小，所以我们可以把 K 表示为 λ*N ，因为驱动表的行数是N，我们就算每次分段的大小是1，也不会超过N，所以
λ的大小就在(0,1)。

所以，在执行的过程中：

  1. 扫描的行数就是N+λNM（驱动表所有行都扫描存入join_buffer中 + 分成的断数*被驱动表的行数）
  2. 内存判断次数 N*M

所以，内存的判断次数和驱动表和被驱动表的大小都没关系，但是扫描的行数和N有关。并且在N的大小固定时，其实就是和λ的大小有关，那我们应该尽量让λ的大小越小越好，那就是让join_buffer_size的值越大，一次可以放更多的行，那分段的次数自然就下去了。

所以结论是，应该让小表来做驱动表，并且改大join_buffer_size的大小。

最后，我们来探讨一个问题，什么是“小表”

难道行数越小的表就是小表吗？不见得如此，如果我们在sql中再加上对驱动表的限制，例如：

1
2
csharp复制代码select * from t1 straight_join t2 on (t1.b=t2.b) where t2.id<=50; 
select * from t2 straight_join t1 on (t1.b=t2.b) where t2.id<=50;

上面这两条sql都没有用上索引，但是第二行中，位于驱动表位置的t2限制了只有前50行，所以我们只需要将这50行数据放入join_buffer中，显然这么做更好，所以这里的t2的前50行，就是 “小表”。

再看下面这两条sql

1
csharp复制代码select t1.b,t2.* from t1 straight_join t2 on (t1.b=t2.b) where t2.id<=100; 2 select t1.b,t2.* from t2 straight_join t1 on (t1.b=t2.b) where t2.id<=100;

这个例子里，表 t1 和 t2 都是只有 100 行参加 join。但是，这两条语句每次查询放入 join_buffer 中的数据是不一样的:

  • 表 t1 只查字段 b，因此如果把 t1 放到 join_buffer 中，则 join_buffer 中只需要放入 b 的值;
  • 表 t2 需要查所有的字段，因此如果把表 t2 放到 join_buffer 中的话，就需要放入三个字 段 id、a 和 b。

这里，我们应该选择表 t1 作为驱动表。也就是说在这个例子里，“只需要一列参与 join 的 表 t1”是那个相对小的表。

在决定哪个表做驱动表的时候，应该是两个表按照各自的条件过滤，过滤完成之后，计算参与 join 的各个字段的总数据量，数据量小的那个表，就是“小表”， 应该作为驱动表。

小结

  1. “index Nested-Loop Join” ，也就是有用到被驱动表的索引，让小表来做驱动表
  2. “Block Nested-Loop Join” ，在没用到被驱动表上的索引时，应该让小表来做驱动表，并且改大join_buffer_size的大小

反正就是在使用 join 的时候，应该让小表做驱动表。

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

这是我参与11月更文挑战的第24天，活动详情查看：2021最后一次更文挑战

  1. 计算力扣银行的钱

Hercy 想要为购买第一辆车存钱。他 每天 都往力扣银行里存钱。

最开始，他在周一的时候存入 1 块钱。从周二到周日，他每天都比前一天多存入 1 块钱。在接下来每一个周一，他都会比 前一个周一 多存入 1 块钱。

给你 n ，请你返回在第 n 天结束的时候他在力扣银行总共存了多少块钱。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
ini复制代码示例 1：

输入：n = 4
输出：10
解释：第 4 天后，总额为 1 + 2 + 3 + 4 = 10 。

示例 2：

输入：n = 10
输出：37
解释：第 10 天后，总额为 (1 + 2 + 3 + 4 + 5 + 6 + 7) + (2 + 3 + 4) = 37 。注意到第二个星期一，Hercy 存入 2 块钱。

示例 3：

输入：n = 20
输出：96
解释：第 20 天后，总额为 (1 + 2 + 3 + 4 + 5 + 6 + 7) + (2 + 3 + 4 + 5 + 6 + 7 + 8) + (3 + 4 + 5 + 6 + 7 + 8) = 96 。

提示：

1 <= n <= 1000

解题思路

直接模拟存钱的过程

  1. 在周一的时候存入 1 块钱。从周二到周日，每天都比前一天多存入 1 块钱。
  2. 下一周的周一需要比上一周的周一存入更多的钱，从周二到周日，还是保持每天都比前一天多存入 1 块钱的规律
  3. 直到第n天，返回存入的总和

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
cpp复制代码class Solution {
public:
    int totalMoney(int n) {
        int pre=0,sum=0,cur=0;
        for (int i = 0; i < n; ++i) {
            if (i%7==0)
            {
              pre++;
              cur=pre;
            }else cur++;
            sum+=cur;
        }
        return sum;
    }
};

优化思路

  1. 对于每一周，一定会存下28元，因为：1+2+3+4+5+6+7=28，所以当有r个完整的一周时，会存下 28 * n 元；
  2. 从第二周开始，每一周都会比前面一周多7元；
  3. 第r周，会多存下 7*(1+2+3+..+r-1)元。根据等差数列的求和公式，可推导出：7r(r - 1)/2 元；
  4. 而最后不能构成完整一周的那几天也是利用相同的思想，可以拆分为 1+2+…mod 和 r * mod。
1
2
3
4
5
6
7
cpp复制代码class Solution {
public:
    int totalMoney(int n) {
        int r=n/7,mod=n%7;
        return (28 * r)+ (7 * r * (r - 1) / 2)+ (r * mod)+ (mod * (mod + 1) / 2);
    }
};

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%