leeyupeng

leeyupeng@126.com

0%

发表于 更新于 分类于 阅读次数： Valine：

反射机制

分析

1.通过类名创建类实例
2.通过类成员名字操作类实例成员的值
3.通过类方法名字操作类实例方法的调用
4.读取配置文件创建类实例，赋值成员，调用成员方法
5.将类实例生成配置文件
6.创建编辑器对类实例进行赋值修改，保存类实例，加载类实例

java的反射机制

java的反射机制是通过Class实现的
1.获取Class

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Student stu1 = new Student();//这一new 产生一个Student对象，一个Class对象。
Class stuClass = stu1.getClass();//获取Class对象
System.out.println(stuClass.getName());

//第二种方式获取Class对象
Class stuClass2 = Student.class;
System.out.println(stuClass == stuClass2);//判断第一种方式获取的Class对象和第二种方式获取的是否是同一个

//第三种方式获取Class对象
try {
  Class stuClass3 = Class.forName("fanshe.Student");//注意此字符串必须是真实路径，就是带包名的类路径，包名.类名
  System.out.println(stuClass3 == stuClass2);//判断三种方式是否获取的是同一个Class对象
} catch (ClassNotFoundException e) {
  e.printStackTrace();

阅读全文 »

发表于 更新于 分类于 阅读次数： Valine：

Welcome to CPlusPlus

1
2
3
4
5
//hello world
void main()
{
  printf("hello world");
}

聯係方式

  • QQ:418846793
  • email:leeyupeng@126.com
阅读全文 »

发表于 更新于 分类于 ， 阅读次数： Valine：

通配符匹配

给定一个字符串 (s) 和一个字符模式 (p) ，实现一个支持 ‘?’ 和 ‘*’ 的通配符匹配。

‘?’ 可以匹配任何单个字符。
‘*’ 可以匹配任意字符串（包括空字符串）。
两个字符串完全匹配才算匹配成功。

回溯法

思路分析

双指针 i，j

  • 1.若s[i]==p[j] 则i++,j++;
  • 2.若p[j]==’?’ 则i++,j++;
  • 3.若p[j]==’*’ 则j++，并更新star的位置和回溯时的起点
  • 4.若s[i]!=p[j] 则
    • 1.如果star位置的-1，匹配失败；
    • 2.回溯，起点加1，j回到起点 star+1;
阅读全文 »

发表于 更新于 分类于 ， 阅读次数： Valine：

最大矩形

题目

2559.Largest Rectangle in a Histogram

描述

单调栈

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
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <algorithm>
#include <ctime>
using namespace std;

long long LargetRectangle(int n, vector<int>& v)
{
	long long ans=0;
	vector<long long> ansvector(n);
	for (int i = 0; i < n; i++)
	{
		ansvector[i] = v[i];
	}
	stack<int> s;
	for (int i = 0; i < n; i++)
	{
		while (!s.empty())
		{
			if (v[s.top()] > v[i])
			{
				ansvector[s.top()] += (long long)v[s.top()] * (i - s.top() - 1);
				s.pop();
			}
			else
			{
				break;
			}
		}
		s.push(i);
	}

	while (!s.empty())
	{
		ansvector[s.top()] += (long long)v[s.top()] * (n - s.top() - 1);
		s.pop();
	}

	for (int i = n -1; i >= 0; i--)
	{
		while (!s.empty())
		{
			if (v[s.top()] > v[i])
			{
				ansvector[s.top()] += (long long)v[s.top()] * (s.top() - i - 1);
				s.pop();
			}
			else
			{
				break;
			}
		}
		s.push(i);
	}

	while (!s.empty())
	{
		ansvector[s.top()] += (long long)v[s.top()] * (s.top());
		s.pop();
	}

	for (int i = 0; i < n; i++)
	{
		ans = ans > ansvector[i] ? ans : ansvector[i];
	}
	return ans;
}
int main()
{
	int n;
	while (cin >> n)
	{
		if (n == 0)
		{
			break;
		}
		vector<int> v(n);
		for (int i = 0; i < n; i++)
		{
			cin >> v[i];
		}

		cout<<LargetRectangle(n,v)<<endl;
	}

	return 0;
}
阅读全文 »

发表于 更新于 分类于 ， 阅读次数： Valine：

0/1背包问题

题目

- 3624.Charm Bracelet

描述

有N个物品，每个物品的价值di和重量wi，背包容量为M，每个物品最多可以装入背包一个，求背包可以装的物品的总价值

分支限界法

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
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

struct Charm
{
	int weight;
	int desirability;
};
struct Node
{
	int index;
	int weight;
	int desirability;
	int evaluation;

	int index2;
	int weight2;
	int evaluation2;

	bool operator<(const Node a)const
	{
		return evaluation < a.evaluation;
	}
};
vector<Charm>* v = NULL;

int Down(int n, int m)
{
	int down = 0;
	for (int i = n - 1; i >= 0; i--)
	{
		if (m >= (*v)[i].weight)
		{
			m -= (*v)[i].weight;
			down += (*v)[i].desirability;
		}
		else
		{
			//down += m * (*v)[i].desirability / (*v)[i].weight;
		}

		if (m == 0)
		{
			break;
		}
	}
	return down;
}
int Up(int n, int m)
{
	int up = 0;
	for (int i = n - 1; i >= 0; i--)
	{
		if (m >= (*v)[i].weight)
		{
			m -= (*v)[i].weight;
			up += (*v)[i].desirability;
		}
		else
		{
			up += m * (*v)[i].desirability / (*v)[i].weight;
			break;
		}
	}
	return up;
}
void Evaluation(Node& node)
{
	int evaluation = node.evaluation2;
	int weight = node.weight2;
	int index = node.index2;
	for (int i = index; i >= 0; i--)
	{
		if (weight >= (*v)[i].weight)
		{
			weight -= (*v)[i].weight;
			evaluation += (*v)[i].desirability;
		}
		else
		{
			node.index2 = i;
			node.weight2 = weight;
			node.evaluation2 = evaluation;

			evaluation += weight * (*v)[i].desirability / (*v)[i].weight;
			break;
		}

		if (i == 0)
		{
			node.index2 = i - 1;
			node.weight2 = weight;
			node.evaluation2 = evaluation;
			break;
		}
	}
	node.evaluation = evaluation;
}
int BranchAndBound(int n, int m)
{
	int down = Down(n, m);
	//向上取整
	int up = Up(n, m);

	if (down == up)
	{
		return down;
	}

	priority_queue<Node> q;
	Node root;
	root.index = n - 1;
	root.weight = m;
	root.desirability = 0;
	root.evaluation = 0;
	root.index2 = n - 1;
	root.weight2 = m;
	root.evaluation2 = 0;
	Evaluation(root);
	q.push(root);
	Node c1;
	Node c2;
	while (!q.empty())
	{
		Node top = q.top();
		q.pop();

		if (top.evaluation <= down)
		{
			break;
		}
		if (top.index < 0)
		{
			down = down > top.desirability ? down : top.desirability;
			continue;
		}

		if (top.weight == 0)
		{
			down = down > top.desirability ? down : top.desirability;
			continue;
		}

		if (top.desirability == top.evaluation)
		{
			down = down > top.desirability ? down : top.desirability;
			continue;
		}

		if (top.weight >= (*v)[top.index].weight)
		{
			c1.index = top.index - 1;
			c1.weight = top.weight - (*v)[top.index].weight;
			c1.desirability = top.desirability + (*v)[top.index].desirability;
			c1.evaluation = top.evaluation;
			c1.index2 = top.index2;
			c1.weight2 = top.weight2;
			c1.evaluation2 = top.evaluation2;
			q.push(c1);


			c2.index = top.index - 1;
			c2.weight = top.weight;
			c2.desirability = top.desirability;
			c2.evaluation = top.evaluation;
			c2.index2 = top.index2 <= c2.index ? top.index2 : c2.index;
			if (top.index2 < top.index)
			{
				c2.index2 = top.index2;
				c2.weight2 = top.weight2 + (*v)[top.index].weight;
				c2.evaluation2 = top.evaluation2 - (*v)[top.index].desirability;
			}
			else
			{
				c2.index2 = top.index - 1;
				c2.weight2 = top.weight2;
				c2.evaluation2 = top.evaluation2;
			}
			Evaluation(c2);
			if (c2.evaluation > down)
			{
				q.push(c2);
			}
		}
		else
		{
			top.index = top.index - 1;
			q.push(top);
		}
	}

	return down;

}
bool cmp(Charm c1, Charm c2)
{
	if (c1.desirability * c2.weight == c2.desirability * c1.weight)
	{
		return c1.weight < c2.weight;
	}
	else
	{
		return 1.0f * c1.desirability / c1.weight < 1.0f * c2.desirability / c2.weight;
	}
}
int CharmBracelet(vector<Charm>* v, int n, int m)
{
	sort(v->begin(), v->end(), cmp);

	int ans = BranchAndBound(n, m);
	return ans;
}
int main()
{
	int n, m;
	cin >> n >> m;
	v = new vector<Charm>(n);
	for (int i = 0; i < n; i++)
	{
		cin >> (*v)[i].weight;
		cin >> (*v)[i].desirability;
	}
	int result = CharmBracelet(v, n, m);
	delete v;
	v = NULL;
	cout << result << endl;
	return 0;
}
阅读全文 »

发表于 更新于 分类于 ， 阅读次数： Valine：

0/1背包问题

题目

- 3624.Charm Bracelet

描述

有N个物品，每个物品的价值di和重量wi，背包容量为M，每个物品最多可以装入背包一个，求背包可以装的物品的总价值

分支限界法

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
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

struct Charm
{
	int weight;
	int desirability;
};
struct Node
{
	int index;
	int weight;
	int desirability;
	int evaluation;

	bool operator<(const Node a)const
	{
		return evaluation < a.evaluation;
	}
};
vector<Charm>* v = NULL;

int Down(int n, int m)
{
	int down = 0;
	for (int i = n - 1; i >= 0; i--)
	{
		if (m >= (*v)[i].weight)
		{
			m -= (*v)[i].weight;
			down += (*v)[i].desirability;
		}
		else
		{
			//down += m * (*v)[i].desirability / (*v)[i].weight;
		}

		if (m == 0)
		{
			break;
		}
	}
	return down;
}
int Up(int n, int m)
{
	int up = 0;
	for (int i = n - 1; i >= 0; i--)
	{
		if (m >= (*v)[i].weight)
		{
			m -= (*v)[i].weight;
			up += (*v)[i].desirability;
		}
		else
		{
			up += m * (*v)[i].desirability / (*v)[i].weight;
			break;
		}
	}
	return up;
}
void Evaluation(Node& node)
{
	int evaluation = node.desirability;
	int weight = node.weight;
	for (int i = node.index; i >= 0; i--)
	{
		if (weight >= (*v)[i].weight)
		{
			weight -= (*v)[i].weight;
			evaluation += (*v)[i].desirability;
		}
		else
		{
			evaluation += weight * (*v)[i].desirability / (*v)[i].weight;
			break;
		}
	}
	node.evaluation = evaluation;
}
int BranchAndBound(int n,int m)
{
	int down = Down(n,m);
	//向上取整
	int up = Up(n,m);

	if (down == up)
	{
		return down;
	}

	priority_queue<Node> q;
	Node root;
	root.index = n - 1;
	root.weight = m;
	root.desirability = 0;
	Evaluation(root);
	q.push(root);
	Node c1;
	Node c2;
	while (!q.empty())
	{
		Node top = q.top();
		q.pop();

		if (top.index < 0)
		{
			down = down > top.desirability ? down : top.desirability;
			break;
		}

		if (top.weight >= (*v)[top.index].weight)
		{
			c1.index = top.index - 1;
			c1.weight = top.weight - (*v)[top.index].weight;
			c1.desirability = top.desirability + (*v)[top.index].desirability;
			Evaluation(c1);
			if (c1.evaluation > down)
			{
				q.push(c1);
			}
		}

		c2.index = top.index - 1;
		c2.weight = top.weight;
		c2.desirability = top.desirability;
		Evaluation(c2);
		if (c2.evaluation > down)
		{
			q.push(c2);
		}
	}

	return down;

}
bool cmp(Charm c1, Charm c2)
{
	if (c1.desirability * c2.weight == c2.desirability * c1.weight)
	{
		return c1.weight < c2.weight;
	}
	else
	{
		return 1.0f * c1.desirability / c1.weight < 1.0f * c2.desirability / c2.weight;
	}
}
int CharmBracelet(vector<Charm>* v, int n, int m)
{
	sort(v->begin(), v->end(), cmp);

	int ans = BranchAndBound(n, m);
	return ans;
}
int main()
{
	int n, m;
	cin >> n >> m;
	v = new vector<Charm>(n);
	for (int i = 0; i < n; i++)
	{
		cin >> (*v)[i].weight;
		cin >> (*v)[i].desirability;
	}
	int result = CharmBracelet(v, n, m);
	delete v;
	v = NULL;
	cout << result << endl;
	return 0;
}
阅读全文 »