Java 多线程学习中遇到的一个有趣的问题

今天随便写了一个线程之间相互调度的程序,代码如下:

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
class First extends Thread
{
public First()
{
start();
}

synchronized public void run()
{
try
{
wait();
}
catch(InterruptedException e)
{
e.printStackTrace();
}
try
{
sleep(2000);
}
catch(InterruptedException e)
{
e.printStackTrace();
}
System.out.println("hello world~");
}
}

class Second extends Thread
{
First first;
public Second(First first)
{
this.first = first;
start();
}

synchronized public void run()
{
try
{
wait();
}
catch (InterruptedException e1)
{
e1.printStackTrace();
}
synchronized( first )
{
try
{
sleep(2000);
System.out.println("I'm faster than first~");
}
catch(InterruptedException e)
{
e.printStackTrace();
}
first.notifyAll();
}
}
}

public class Main
{
public static void main(String[] args) throws InterruptedException
{
First first = new First();
Second second = new Second(first);
synchronized( second )
{
System.out.println("I'm faster than second~");
second.notifyAll();
}
}
}

本以为输出会很顺畅,但是出现的问题是,只输出了一行:I’m faster than second~

程序就一直处于无响应状态,纠结了好久终于想明白是这么一回事:在main函数中,对second.notifyAll()的调用早于second中的wait()调用(因为是多线程并行,故函数响应时间与代码先后顺序无关),这样先唤醒了second,紧接着second才开始wait,因此就处于无响应状态。

改进方法:只要在second.notifyAll()调用之前空出一点时间先让second的wait调用开始即可,事实上,这段时间如此之短以至于在我电脑上只需要在之前加一行输出语句即可。为了保险起见,还是多加了个sleep,改进后代码如下:

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
class First extends Thread
{
public First()
{
start();
}

synchronized public void run()
{
try
{
wait();
}
catch(InterruptedException e)
{
e.printStackTrace();
}
try
{
sleep(2000);
}
catch(InterruptedException e)
{
e.printStackTrace();
}
System.out.println("hello world~");
}
}

class Second extends Thread
{
First first;
public Second(First first)
{
this.first = first;
start();
}

synchronized public void run()
{
try
{
wait();
}
catch (InterruptedException e1)
{
e1.printStackTrace();
}
synchronized( first )
{
try
{
sleep(2000);
System.out.println("I'm faster than first~");
}
catch(InterruptedException e)
{
e.printStackTrace();
}
first.notifyAll();
}
}
}

public class Main
{
public static void main(String[] args) throws InterruptedException
{
First first = new First();
Second second = new Second(first);
System.out.println("wating for all threads prepared~");
Thread.sleep(2000);
synchronized( second )
{
System.out.println("I'm faster than second~");
second.notifyAll();
}
}
}

输出结果:

1
2
3
4
wating for all threads prepared~
I’m faster than second~
I’m faster than first~
hello world~

文件夹遍历 Java 版

Java下的File类(文件类,其实感觉文件类有点误导性,用“文件路径”会好一点)有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
33
34
35
import java.io.File;
import java.io.FileWriter;
import java.io.IOException;

public class test_for_team_study_2
{
public static void traverse(String name, FileWriter wt) throws IOException
{
wt.write(name + "\r\n");
File path = new File(name);
String[] list = path.list();
if( null == list )
return ;
for(int i = 0; i < list.length; i ++)
if( -1 == list[i].indexOf(".") )
traverse(name + "/" + list[i], wt);
}

public static void main(String[] args) throws IOException
{
FileWriter wt = new FileWriter("C:/Users/Administrator/Desktop/file in D.out");
String name = "D:/";
File path = new File(name);
String[] list = path.list();
for(int i = 0; i < list.length; i ++)
{
wt.write("now is the file#:" + i + "\r\n==========================\r\n");
traverse(name + "/" + list[i], wt);
wt.write("\r\n\r\n\r\n");
}
wt.flush();
wt.close();
System.out.println("finished!");
}
}

JAVA 设置 JTable 表格的可编辑性

有时候,我们需要设置JTable表格某些行某些列不可编辑以保证数据准确,用DefaultTableModel初始化的话,需要重写它的public boolean isCellEditable(int, int)方法,写法简单呈现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
DefaultTableModel myModel = new DefaultTableModel(dataOfOrder, headOfOrder)	//实例化表格模式
{
/**
*
*/
private static final long serialVersionUID = 1L;

public boolean isCellEditable(int rowIndex, int columnIndex) //重写方法改编可编辑性
{
if( columnIndex == getColumnCount() - 1 )
return true;
return false;
}
};

上述写法是设置只有表格的最后一列可编辑,其他列不可编辑。有了rowIndex和columnIndex这两个参数,可以随意的设置可编辑范围。

注意要达到目的,定义另一个类继承DefaultTableModel,之后在类中重写方法是不可行的!

Java 窗体中按钮布局问题

在Java窗体中,有时需要对按钮的设置进行布局,这时使用GridLayout(x, y)会很方便,意思是把窗口划分为x行y列的小格子,在add的时候就是一行一行的填充,这样可以是按钮得到标准化布局

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
import java.awt.BorderLayout;
import java.awt.Dimension;
import java.awt.GridLayout;
import java.awt.Toolkit;

import javax.swing.JButton;
import javax.swing.JFrame;
import javax.swing.JPanel;

public class test_for_blog extends JFrame
{
/**
*
*/
private static final long serialVersionUID = 5136083409273453255L;

private static int JFwidth = 450;
private static int JFheight = 350;

JPanel panel = null;

JButton btnAdd = null;
JButton btnDelete = null;

public test_for_blog()
{
super("按钮添加测试");

panel = new JPanel();

btnAdd = new JButton("Add");
btnDelete = new JButton("Delete");

panel.setLayout( new GridLayout(1, 2) );
panel.add(btnAdd);
panel.add(btnDelete);
this.getContentPane().add(panel, BorderLayout.SOUTH);
}

public static void main(String[] args)
{
test_for_blog test = new test_for_blog();
Dimension screenSize = Toolkit.getDefaultToolkit().getScreenSize(); //获取显示屏尺寸
test.setBounds((screenSize.width - JFwidth) / 2, (screenSize.height - JFheight) / 2, JFwidth, JFheight); //使程序窗口居中
test.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE); //窗口设为可关闭
test.setResizable(false); //窗口设为不可调节大小
test.setVisible(true); //窗口设为可见
}
}

POJ 3255 Roadblocks (次短路问题)

解法有很多奇葩的地方,比如可以到达终点再跳回去再跳回来(比如有两个点)。。。。反正就是不能有最短路,不过没关系,算法都能给出正确结果

思想:和求最短路上的点套路一样,spfa先正着求一次,再反着求一次最短路,然后枚举每条边<i,j>找dist_zheng[i] + len<i,j> + dist_fan[j]的第二小值即可!注意不能用邻接矩阵,那样会MLE,应该用邻接表

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
/*
poj 3255
3808K 266MS
*/

#include<cstdio>
#include<cstring>
#include<queue>
#include<iostream>

#define MAXN 200005
#define MAX_INT 2147483647

using namespace std;

int last[5005], dist_1[5005], dist_2[5005], n, m, gra[5005][5005];
bool mark[MAXN];

struct node
{
int u;
int v;
int w;
int next;
node()
{
u = v = w = next = 0;
}
}edge[MAXN];

void spfa( int dist[5005], int s )
{
queue<int>myQueue;
dist[s] = 0;
memset(mark, false, sizeof(mark));
mark[s] = true;
myQueue.push(s);
while( !myQueue.empty() )
{
int x = myQueue.front();
myQueue.pop();
mark[x] = false;
int t = last[x];
while( t )
{
if( dist[ edge[t].v ] > dist[x] + edge[t].w )
{
dist[ edge[t].v ] = dist[x] + edge[t].w;
if( !mark[ edge[t].v ] )
myQueue.push( edge[t].v );
}
t = edge[t].next;
}
}
}

int main()
{
cin >> n >> m;
for(int i = 1;i <= m;i ++)
{
int a, b, c;
scanf("%d %d %d", &a, &b, &c);
edge[i].u = edge[i + m].v = a;
edge[i].v = edge[i + m].u = b;
edge[i].w = edge[i + m].w = c;
edge[i].next = last[a];
last[a] = i;
edge[i + m].next = last[b];
last[b] = i + m;
}
memset( dist_1, 1, sizeof(dist_1) );
spfa( dist_1, 1 );
memset( dist_2, 1, sizeof(dist_2) );
spfa( dist_2, n );
int ans = MAX_INT, tmp = MAX_INT;
for(int i = 1;i <= n;i ++)
{
int t = last[i];
while( t )
{
if( dist_1[i] + dist_2[ edge[t].v ] + edge[t].w < tmp )
{
ans = tmp;
tmp = dist_1[i] + dist_2[ edge[t].v ] + edge[t].w;
}
else if( dist_1[i] + dist_2[ edge[t].v ] + edge[t].w < ans
&& dist_1[i] + dist_2[ edge[t].v ] + edge[t].w != tmp )
ans = dist_1[i] + dist_2[ edge[t].v ] + edge[t].w;
t = edge[t].next;
}
}
cout << ans << endl;
return 0;
}

POJ 3093 Margaritas on the River Walk(0-1背包变形)

这题目的思路很巧妙,什么情况下剩下的所有物品都放不下呢?就是当前剩余物品中最小的那个也放不下。所以,先把物品按照容量从小到大排序,依次枚举当前背包为放不下的最小物品的情况。

对于当前物品i,必有1到i-1的所有物品都放进去,这时候比i大的物品谁放谁不放是不确定的。转换成0-1背包问题:把前i-1个物品都放进去以后,得到空间为tsum – sum[i-1](前缀和)的包,只要从第i+1到第n个物品中拿出一个方案填充这个包使得剩余体积小于第i个物品的体积就可以了,把总方案数累加就是结果!

注意特殊情况:当排序后最小的物品也无法放入时,直接返回0,因为dp[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
/*
poj 3093
232K 0MS
*/
#include<cstdio>
#include<algorithm>
#include<iostream>

#define MAXN 1005

using namespace std;

int n, m, wei[35], dp[MAXN], sum[MAXN];

__int64 Bag()
{
memset(sum, 0, sizeof(sum));
sort( wei + 1, wei + n + 1 );
if(wei[1] > m) //因为很可能有最小的也放不下这种情况,而dp【0】是初始化为1的,会输出1
return 0;
for(int i = 1;i <= n;i ++)
sum[i] = sum[i-1] + wei[i];
__int64 ans = 0;
for(int i = 1;i <= n;i ++)
{
if(sum[i - 1] > m)
break;
memset(dp, 0, sizeof(dp));
dp[sum[i-1]] = 1;
for(int j = i + 1;j <= n;j ++)
for(int k = m; k >= sum[i - 1] + wei[j]; k --)
dp[k] += dp[k - wei[j]];

for(int j = m - wei[i] + 1;j <= m;j ++)
ans += dp[j];
}
return ans;
}

int main()
{
int Cases;
cin>>Cases;
for(int cnt = 1; cnt <= Cases; cnt ++)
{
cin >> n >> m;
for(int i = 1;i <= n;i ++)
cin>> wei[i];
cout << cnt << " " << Bag() <<endl;
}
return 0;
}

要开始编程了

6月准备期末考试,除了考试没有再编过程。今天院内ACM培训选拔赛,虽然手生,还是顺利通过了。这两周不用去听水课了,通过这两周找找感觉,巩固一下算法把,不要放下c++和Java的学习。一月不编程感觉水平有点下滑,很简单的题目竟然选择了很复杂的算法,还是错的,其实暴搜就可以,哎,好好练习吧

POJ 2676 Sudoku(数独)

经典搜索问题,主要是时间上的优化,我用了三个辅助数组记录信息 row[i][k] = 1表示第i行数字k已经被使用,col[j][k] = 1表第j列数字k已经被使用,blo[i][k]表示第i个小九宫格中数字k已经被使用

还有很重要的一个优化(没有优化的话可能会超时,或者非常慢,像POJ讨论区里有很多说正着搜超时,倒着搜0ms,这的确是一个可以用的方法,但是有一定的随机性),每次填数字时,先扫描一遍整个矩阵,找出可选数字情况最少的那个0所在的地方,优先填这里,这样会使得搜索树尽可能的“瘦“一些,效果会非常明显

代码

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
/*
poj 2676
236K 0MS
*/

#include<cstdio>
#include<iostream>

#define MAXN 10
#define MAX_INT 2147483647

using namespace std;

bool flag = false;
int matrix[MAXN][MAXN], row[MAXN][MAXN], col[MAXN][MAXN], blo[MAXN][MAXN];
//用int判断比bool判断要快!
int area[MAXN][MAXN] = {
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 1, 1, 1, 2, 2, 2, 3, 3, 3},
{0, 1, 1, 1, 2, 2, 2, 3, 3, 3},
{0, 1, 1, 1, 2, 2, 2, 3, 3, 3},
{0, 4, 4, 4, 5, 5, 5, 6, 6, 6},
{0, 4, 4, 4, 5, 5, 5, 6, 6, 6},
{0, 4, 4, 4, 5, 5, 5, 6, 6, 6},
{0, 7, 7, 7, 8, 8, 8, 9, 9, 9},
{0, 7, 7, 7, 8, 8, 8, 9, 9, 9},
{0, 7, 7 ,7, 8, 8, 8, 9, 9, 9}
};

void solve(int cnt)
{
if(flag)
return ;
if( !cnt )
{
flag = true;
for(int i = 1;i <= 9;i ++)
{
for(int j = 1;j <= 9;j ++)
cout<<matrix[i][j];
cout<<endl;
}
return ;
}
int tx, ty, Min = MAX_INT;
for(int i = 1;i <= 9;i ++) //扫描矩阵,找到可选数字情况最少的那个0
{
for(int j = 1;j <= 9;j ++)
{
if( !matrix[i][j] )
{
int times = 0;
for(int k = 1;k <= 9;k ++)
if( !row[i][k] && !col[j][k] && !blo[area[i][j]][k] )
times ++;
if(times < Min)
{
Min = times ;
tx = i;
ty = j;
}
}
}
}
for(int k = 1;k <= 9;k ++)
{
if( !row[tx][k] && !col[ty][k] && !blo[area[tx][ty]][k] )
{
row[tx][k] = col[ty][k] = blo[area[tx][ty]][k] = 1;
matrix[tx][ty] = k;
solve(cnt - 1);
matrix[tx][ty] = 0;
row[tx][k] = col[ty][k] = blo[area[tx][ty]][k] = 0;
}
}
}

int main()
{
int cases = 0, cnt = 0;
cin>>cases;
while(cases --)
{
memset(row, 0, sizeof(row));
memset(col, 0, sizeof(col));
memset(blo, 0, sizeof(blo));
memset(matrix, 0, sizeof(matrix));
flag = false;
cnt = 0;
for(int i = 1;i <= 9;i ++)
{
for(int j = 1;j <= 9;j ++)
{
char ch;
cin>>ch;
matrix[i][j] = ch - '0';
row[i][matrix[i][j]] = 1;
col[j][matrix[i][j]] = 1;
blo[area[i][j]][matrix[i][j]] = 1;
if( !matrix[i][j] )
cnt ++;
}
}
solve(cnt);
}
return 0;
}

Windows 编程之文件夹遍历

利用windows的API,FindFirstFile和FileNextFile,采用递归遍历指定文件夹中的所有文件及文件夹,第一次windows编程,代码写的很臃肿难看,请大家多多包涵!

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
#include<cstdio>
#include<cstring>
#include<iostream>
#include<windows.h>

#define MAXN 100005

using namespace std;

void surf(WIN32_FIND_DATA myData)
{
cout<<myData.ftCreationTime.dwLowDateTime<<endl;
cout<<myData.ftLastAccessTime.dwLowDateTime<<endl;
cout<<myData.ftLastWriteTime.dwLowDateTime<<endl;
SYSTEMTIME ctime , atime , wtime;
FileTimeToSystemTime(&myData.ftCreationTime , &ctime);
FileTimeToSystemTime(&myData.ftLastAccessTime , &atime);
FileTimeToSystemTime(&myData.ftLastWriteTime , &wtime);
printf("%d年%d月%d日%d时%d分%d秒\n"
, ctime.wYear , ctime.wMonth , ctime.wDay , ctime.wHour , ctime.wMinute , ctime.wSecond);
printf("%d年%d月%d日%d时%d分%d秒\n"
, atime.wYear , atime.wMonth , atime.wDay , atime.wHour , atime.wMinute , atime.wSecond);
printf("%d年%d月%d日%d时%d分%d秒\n"
, wtime.wYear , wtime.wMonth , wtime.wDay , wtime.wHour , wtime.wMinute , wtime.wSecond);
cout<<endl<<endl;
}

void traverse(char *Str)
{
WIN32_FIND_DATA myData;
HANDLE hFind = INVALID_HANDLE_VALUE;
char str[MAX_PATH] = {0};
strcpy(str , Str);
strcat(str , "/*"); //使用通配符进行匹配
hFind = FindFirstFile(str , &myData);
if(INVALID_HANDLE_VALUE == hFind)
return ;
while(FindNextFile(hFind , &myData))
{
if(myData.cFileName[0] != '.') //非返回目录时进行下一步
{
cout<<"========="<<myData.cFileName<<"=========="<<endl;
surf(myData);
if(myData.dwFileAttributes == FILE_ATTRIBUTE_DIRECTORY) //判断是否为文件夹
{
char dir[MAX_PATH] = {0};
snprintf(dir , MAX_PATH, "%s/%s" , Str , myData.cFileName); //构造路径
traverse(dir);
}
}
}
FindClose(hFind); //关闭句柄
}

int main()
{
char *str = "./test";
traverse(str);
}

我的当前目录下的test文件夹有“haha”文件夹以及test.1 , test , 2 , test , 3三个文件,”haha”文件夹里又含有“ai”文件夹以及haha.1 , haha.2 , haha.3三个文件,“ai”文件夹里又含有“wo”文件夹以及ai.1 , ai.2 , ai.3三个文件,”wo”文件夹里有wo.1 , wo.2 , wo.3三个文件。。。

程序输出结果:

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
=========haha==========
1556376338
2156419021
2156419021
2014年5月31日10时16分18秒
2014年5月31日10时24分27秒
2014年5月31日10时24分27秒


=========ai==========
2147248496
772195107
772195107
2014年5月31日10时24分27秒
2014年5月31日11时26分34秒
2014年5月31日11时26分34秒


=========ai.1==========
2197291359
2197291359
2197291359
2014年5月31日10时24分32秒
2014年5月31日10时24分32秒
2014年5月31日10时24分32秒


=========ai.2==========
2197291359
2328198846
2328198846
2014年5月31日10时24分32秒
2014年5月31日10时24分45秒
2014年5月31日10时24分45秒


=========ai.3==========
2197291359
2387262224
2387262224
2014年5月31日10时24分32秒
2014年5月31日10时24分51秒
2014年5月31日10时24分51秒


=========wo==========
752914004
2835575798
2835575798
2014年5月31日11时26分33秒
2014年5月31日15时40分33秒
2014年5月31日15时40分33秒


=========wo.1==========
806557072
806557072
806557072
2014年5月31日11时26分38秒
2014年5月31日11时26分38秒
2014年5月31日11时26分38秒


=========wo.2==========
870010701
870010701
870010701
2014年5月31日11时26分44秒
2014年5月31日11时26分44秒
2014年5月31日11时26分44秒


=========wo.3==========
870010701
923383754
923383754
2014年5月31日11时26分44秒
2014年5月31日11时26分50秒
2014年5月31日11时26分50秒


=========haha.1==========
1601118898
1601118898
1601118898
2014年5月31日10时16分22秒
2014年5月31日10时16分22秒
2014年5月31日10时16分22秒


=========haha.2==========
1601118898
1678113301
1678113301
2014年5月31日10时16分22秒
2014年5月31日10时16分30秒
2014年5月31日10时16分30秒


=========haha.3==========
1601118898
1742136963
1742136963
2014年5月31日10时16分22秒
2014年5月31日10时16分36秒
2014年5月31日10时16分36秒


=========test.1==========
1835930690
1835930690
1601118898
2014年5月31日10时23分55秒
2014年5月31日10时23分55秒
2014年5月31日10时16分22秒


=========test.2==========
1924505756
1924505756
1678113301
2014年5月31日10时24分4秒
2014年5月31日10时24分4秒
2014年5月31日10时16分30秒


=========test.3==========
1924535758
1924535758
1742136963
2014年5月31日10时24分4秒
2014年5月31日10时24分4秒
2014年5月31日10时16分36秒