使用JAVA发送UDP报文实现WOL远程唤醒

WOL简介

远程开机也被称为远程唤醒技术(Wake on Lan: WOL),是指可以通过局域网、互联网或者通讯网实现远程开机,无论目标主机离用户有多远、处于什么位置,只要其与发送命令主机可以通信,就能够被随时启动,该技术被现在的大多数主板与网卡所支持。
使用之前,请确保打开网卡的远程唤醒功能:

实现原理

局域网内的任意一台PC可通过发送魔术包的方式远程唤醒目标主机,魔术包是用16进制表示的数据包,它由固定的前缀数据以及固定重复次数的目标主机MAC地址所组成。所谓固定前缀数据即6对“FF”,所谓固定重复次数即16次,也就是说魔术包是由12个“F”加重复16次的主机MAC地址组成,例如本文所用试验机的MAC地址为“74-86-7A-71-D5-0A”,所以使该机远程开机的魔术包为:

0xFFFFFFFFFFFF74867A71D50A74867A71D50A74867A71D50A74867A71D50A74867A71D50A74867A71D50A74867A71D50A74867A71D50A74867A71D50A74867A71D50A74867A71D50A74867A71D50A74867A71D50A74867A71D50A74867A71D50A74867A71D50A

在Windows系统中,主机的MAC地址可以通过在命令窗口中输入“ipconfig -all”命令查看。

编码与调试

首先下载标准版的 MagicPacket 输入目标主机的MAC地址,观察是否能顺利唤醒关机状态的目标主机。
如果一切正常,下载网络包嗅探工具smsniff,运行后,紧接着再用MagicPacket发送一次报文,这时候可以通过smsniff观察这次报文的结构。

然后我们编写JAVA代码,直至模仿出一样的报文,即可实现在JAVA代码中唤醒目标主机,今后可以移植到Android,树莓派等环境,实现更丰富的功能。代码如下:

package com.newflypig.wol;

import java.io.IOException;
import java.net.DatagramPacket;
import java.net.InetAddress;
import java.net.MulticastSocket;
import java.net.UnknownHostException;

public class WOL {
    /**
     * main方法,发送UDP广播,实现远程开机,目标计算机的MAC地址为:28D2443568A7
     */
    public static void main(String[] args) {
        String ip = "255.255.255.255";//广播IP地址
        String mac= "FCAA14D0C108";
        int port = 2304;//端口号
        //魔术包数据
        String magicPackage = "0xFFFFFFFFFFFF";
        for(int i = 0; i < 16; i++){
            magicPackage += mac;
        }
        //转换为2进制的魔术包数据
        byte[] command = hexToBinary(magicPackage);
        for(Byte b : command){
            System.out.print(b.byteValue());
        }

        //广播魔术包
        try {
            //1.获取ip地址
            InetAddress address = InetAddress.getByName(ip);
            //2.获取广播socket
            MulticastSocket socket = new MulticastSocket(port);
            //3.封装数据包
            /*public DatagramPacket(byte[] buf,int length
             *      ,InetAddress address
             *      ,int port)
             * buf:缓存的命令
             * length:每次发送的数据字节数,该值必须小于等于buf的大小
             * address:广播地址
             * port:广播端口
            */
            DatagramPacket packet = new DatagramPacket(command, command.length-1, address, port);
            //4.发送数据
            socket.send(packet);
            //5.关闭socket
            socket.close();
        } catch (UnknownHostException e) {
            //Ip地址错误时候抛出的异常
            e.printStackTrace();
        } catch (IOException e) {
            //获取socket失败时候抛出的异常
            e.printStackTrace();
        }
    }

    /**
     * 将16进制字符串转换为用byte数组表示的二进制形式
     * @param hexString:16进制字符串
     * @return:用byte数组表示的十六进制数
     */
    private static byte[] hexToBinary(String hexString){
        //1.定义变量:用于存储转换结果的数组
        byte[] result = new byte[hexString.length()/2];

        //2.去除字符串中的16进制标识"0X"并将所有字母转换为大写
        hexString = hexString.toUpperCase().replace("0X", "");

        //3.开始转换
        //3.1.定义两个临时存储数据的变量
        char tmp1 = '0';
        char tmp2 = '0';
        //3.2.开始转换,将每两个十六进制数放进一个byte变量中
        for(int i = 0; i < hexString.length(); i += 2){
            tmp1 = hexString.charAt(i);
            tmp2 = hexString.charAt(i+1);
            result[i/2] = (byte)((hexToDec(tmp1)<<4)|(hexToDec(tmp2)));
        }
        return result;
    }

    /**
     * 用于将16进制的单个字符映射到10进制的方法
     * @param c:16进制数的一个字符
     * @return:对应的十进制数
     */
    private static byte hexToDec(char c){
        int index = "0123456789ABCDEF".indexOf(c);
        return (byte)index;
    }
}

NOIP2015子串问题解题报告

NOIP2015子串问题解题报告

本题来自NOIP2015,我第一次见它是在NUAA1012,这题是一条经典的动态规划(dynamic programming)。

做算法竞赛也有一段时间了,我所理解的动态规划就是用开数组的方式解决递归的时间复杂度。可能是还不熟练的原因,每次遇到动态规划我都要先写出递归函数,然后用循环和开数组的方式改造,记录递推中产生的过程解,这样在新的方程中递推到同样位置时不需要深入计算,直接用已经计算出来解即可,从而降低时间复杂度,但是因为开辟了数组记录过程解,因此是一种典型的「空间换时间」的思想。

这一题对我来说,同样需要先写出递归函数,再去改造。如果是练习的话,可以在OJ平台一步一步提交观察,现在一些流行的OJ平台不光会告诉你AC还是WA,还会告诉你A了几个测试用例,所以如果光写递归的话,能够通过大概40%,用上DP改造,可以通过90%,最后一道测试用例不出意外的话,你的空间会超,要想拿到100%AC,最后一个测试用例需要使用滚动数组降低空间复杂度。实际现场竞赛的话建议考虑周全后,再提交,毕竟会有惩罚机制在里面。

网上这道题的解题报告不胜枚举,但大多数作为算法的初级爱好者,我都看得云里雾里,看了一些报告,加上自己想了一个晚上,我力争用自然人类的语言来把这题讲明白。

题目大意就是给定两个字符串,A和B,其中A称之为主串,B称之为子串,和一个取串数K。

要求在主串A中找到K个连续的字符串,能够组成完整的子串B,求这种方案的个数。

样例分析

6 3 1
aabaab
aab
6 3 2
aabaab
aab
6 3 3
aabaab
aab

样例 1,将A串取一个子集,组成B串:
aab aab
aab aab
(两种方案)

样例 2,将A串取两个子集,组成B串:
a ab aab
a aba ab
a a ba ab
aab a ab
aa b aab
aa baa b
aab aa b
(七种方案)

样例 3:
a a b aab
a a baa b
a ab a a b
a aba a b
a a b a a b
a a ba a b
aab a a b
(七种方案)

我们设主串长度为N,子串长度为M,取子集个数为K,N >= M >= K,这是潜在的天然条件
乍一看,最终解法数与N,M,K之间应该存在着某种关系,这种关系应该还与A串和B串的实际内容相关。虽然这种关系暂时我们还看不出来,但隐约觉得应该可以通过层层往前递推,让N,M,K逐渐变小而得到。于是我们设f(i,j,k)表示在主串的0-i中,取k个子集组成子串的0-j的方法有f(i,j,k)种,我们最终就是要求f(N-1, M-1, K)。

推导f方程

有了方程f,我们就要求递推关系,假设,我们现在知道所有f([0,i), [0,j], [1,k])的任意值,现在试着推导f(i,j,k),A串B串还是用样例中的A=aabaab,B=aab,K=2来推理,那么我们现在知道所有的f([0,4],[0,2],[1,2]),求f(5,2,2)。
PS:k=0时,无视其他所有值,f直接等于0,因为无法将主串取出0个子集出来构成子串。
f(5,2,2) = ?
我们将目光聚焦到A[5]和B[2]上,也就是’b’和’b’。
咦?这两个字母一样诶,那我们是不是有且只有两种选择:
一种是取出来的子集带有A[5]
另一种是取出来的子集不带A[5]
我们先不忙着继续推导,先给这两种情况分别命名,组成结果数带有A串最后一个字母的叫做s(i,j,k),反之,不带有最后一个字母的叫做t(i,j,k),假设s和t函数都我们都能轻松求出来,我们现在试着给A串做一次修改,让他变成aabaabc,现在求f(6,2,2),好了,现在A[6]和B[2]分别是字母’c’和’b’,这两个字母不同,那我们只且只有一种情况,那就是刚刚定义的不取A[6]的t函数,我们再仔细观察一下,不取A[6]的话,那只能在A[0,5]中选择子集,那结果等同于f(5,2,2)啊,也就是f(6,2,2) = t(6,2,2) = f(5,2,2),好了,我们将t函数的定义取消掉,因为它可以直接用f(i-1,j,k)取代,本文中我们再也不会提到t这个函数了。
我们先归纳一下现在的分支:

if(A[i] == B[j]){    //取A[i]和不取A[i]
    f(i,j,k) = s(i,j,k) + f(i-1, j, k);
}else{                //不取A[i]
    f(i,j,k) = f(i-1, j, k);
}

大功告成,开始写递归?慢着,s是个什么鬼,好吧我们硬着头皮继续推导s吧:

推导s方程

s的定义是取A[i]这个字符时,从A[0,i]中取k个子集构成B[0-j]的方法数,也就是潜在的现状就是A[i] == B[j]
我们将A串回归到样例状态aabaab,这时候求s(5,2,2)就是默认要取A[5]了,也就是A串最后一个字符’b’必须参与子集的选择。
我们又遇到一个似曾相识的问题,前方的道路又产生了一个问题:我们的A[4] = B[1]呢,取还是不取A[4]?
No,No,No,取不取A[4]这个问题问得不好,会产生二义性,我们需要问一个更明确的问题:合并A[4,5]使其作为一个整体,还是不合并?
合并A[i-1]和A[i]:s(i,j,k) = s(i-1, j-1, k)
不合并A[i-1]和A[i]:,s(i,j,k) = f(i-1, j-1, k-1)
以上两个公式的推导过程咱就省略吧,对着aabaab和aab两个字符串比划比划就能的出来。
于是我们又有了下面这个分支:

if(A[i-1] == B[j-1]){    //合并+不合并
    s(i,j,k) = s(i-1, j-1, k) + f(i-1, j-1, k-1);
}else{                    //不合并
    s(i,j,k) = f(i-1, j-1, k-1);
}

以下就是整个递推方程的推导脑图:

f,s都有了,下面用递归函数AC这道题吧

咳咳咳,没说完,只能A掉40%哦,递归栈太深,会溢出的。
我贴代码有人愿意看吗?反正我看解题报告从来不看别人的代码,看也看不懂,每个人编码习惯还不同,有强迫症的话简直抓狂。

    //本来想贴代码的,想想只能A40%的代码也没人愿意看啊,还是算了。。。

动态规划改造之

动态规划天生就是用来解决递归的,使用开数组记录的方式空间换时间,递推时我们从f(i,j,k)一步一步向f(0,0,0)推理,DP时我们从f(0,0,0)一步一步向f(i,j,k)逼近,但这一题因为测试用例太极限,单纯动规也只能A掉90%的测试用例,第10组用例会报「空间超限」,128M的内存不够用,我算了一下,一个整型变量4个字节,也就是4Byte,如果第10组数据是1≤n≤1000,1≤m≤200,1≤k≤m这样一个等级的话,需要开两个[1000][200][200]这么大的数组,算下来就是2 * 1000 * 200 * 200 * 4B = 320,000,000B = 312,500KB = 305M,题目限制只有128M,显然不够了。

滚动数组

这时候我们引入滚动数组的概念,首先不要被陌生词汇唬住,先别看这个术语,我们来观察一下之前推导的s函数

if(A[i-1] == B[j-1]){    //合并+不合并
    s(i,j,k) = s(i-1, j-1, k) + f(i-1, j-1, k-1);
}else{                    //不合并
    s(i,j,k) = f(i-1, j-1, k-1);
}

我们发现s函数只会跟自身的s(i-1,j-1,k)发生关系,想象一下s[i][j][k]是一个三维的立方体,也就是每次求s[i][j][k]时,它都只需要知道同一层二维平面的之前推导出来的数据,而下面层那些数据都不需要了。而一旦使用动态规划,我们计算机内存中会保存s[0-i] [0-j][1,k]的所有数据,直到程序进程结束,这些数据才会被释放,辣么,会有很多数据白白的保存在内存中,而我们可以预计他们再也不会被以后的推导过程调用。
于是,我们第一步空间压缩,拿s函数(或者叫s数组)开刀吧,因为它只跟它同一层的s[i-1][j-1]发生关系。所以只需要开辟s[n][m]就行了,将一个三维立方体活生生地压缩成为一个二维平面,哈哈,有没有《三体》中二向箔的感觉。
然而,不幸的事情再次发生,当我们把原本需要开s[N][M][K]的数组换成了s[N][M],之后,还是会报「空间超限」。。。
逼着我们继续拿f函数动刀,继续观察推导出来的f函数,这时候要并入s函数一起观察:

if(A[i] == B[j]){    //取A[i]和不取A[i] f(i,j,k) = s(i,j,k) + f(i-1, j, k);
    if(A[i-1] == B[j-1]){    //合并+不合并
        f(i,j,k) = s(i-1, j-1, k) + f(i-1, j-1, k-1) + f(i-1, j, k);
    }else{            //不合并
        f(i,j,k) = f(i-1, j-1, k-1) + f(i-1, j, k);
    }
}else{                //不取A[i]
    f(i,j,k) = f(i-1, j, k);
}

f[N][M][K]同样看做一个立方体,那么它在层层往上搭建的过程中,不光用到了k层的二维平面,还用到了k-1层的二维平面,好说,只要他不是在立方体里到处乱跑就行,不就是用到下一层吗,那我们同样没必要开辟f[N][M][K],我们只需要开辟f[N][M][2]就行了,然后用一个flag从0到1,从1再到0,轮流交替使用f[i][j][flag]就OK了,滚动数组的技巧完美get。

最终编码

写到这里终于要上100%AC的代码了,不过我相信还是没人愿意看代码,所有ACMer包括我在内都只想看思路,自己实现代码对不对。
不过为了符合国际惯例,还是贴上代码吧:

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

char *A, *B;

int main()
{
    int n,m,K;
    scanf("%d %d %d", &n, &m, &K);
    int f[n][m][2];
    int s[n][m];
    A = (char*)malloc( (n+1) * sizeof(n));
    B = (char*)malloc( (m+1) * sizeof(m));
    scanf("%s", A);
    scanf("%s", B);

    /*
     * ACM比赛中,1s对应的计算量大约是4*10^8
     * 因此O(n*m*K) = 1000 * 200 * 1000是可以接受的
     */
    int k,i,j;
    bool flag = false;
    for(k = 1; k<=K; k++){
        for(i = 0; i<n; i++)
            for(j = k-1; j<=i && j<m; j++){

                if(i < j || j < (k-1)){
                    f[i][j][flag?1:0] = 0;
                    s[i][j] = 0;
                    continue;
                }

                if(j == 0 && k ==1){
                    s[i][j] = A[i] == B[j] ? 1 : 0;
                    f[i][j][flag?1:0] = (long long)((long long)s[i][j] + ((k <= 0 || i<1 || j<0 || i<j || j<(k-1))?0:(long long)f[i-1][j][flag?1:0])) % 1000000007;
                    continue;
                }

                if(A[i] == B[j]){
                    if(i>0 && j>0){
                        if(A[i-1] == B[j-1])
                            s[i][j] = (long long)((j<k?0:s[i-1][j-1]) + ((k<=1)?0:f[i-1][j-1][flag?0:1])) % 1000000007;
                        else
                            s[i][j] = (k<=1)?0:f[i-1][j - 1][flag?0:1];
                    }
                    f[i][j][flag?1:0] = (long long)(s[i][j] + ((k <= 0 || i<1 || j<0 || i<=j || j<(k-1))?0:f[i-1][j][flag?1:0]) ) % 1000000007;
                }else{
                    f[i][j][flag?1:0] = i==0?0:f[i - 1][j][flag?1:0];
                }
            }
        flag = !flag;
    }

    printf("%d\n", f[n - 1][m - 1][flag?0:1]);

    return 0;
}

/**************************************************************
    Problem: 2241
    User: newflydd
    Language: C
    Result: 正确
    Time:396 ms
    Memory:3168 kb
****************************************************************/

丁丁生于 1987.07.01 ,30岁,英文ID:newflydd

  • 现居住地 江苏 ● 泰州 ● 姜堰
  • 创建了 Jblog 开源博客系统
  • 坚持十余年的 独立博客 作者
  • 大学本科毕业后就职于 中国电信江苏泰州分公司,前两年从事Oracle数据库DBA工作,两年后公司精简技术人员,被安排到农村担任支局长(其本质是搞销售),于2016年因志向不合从国企辞职,在小城镇找了一份程序员的工作。
  • Git OSChina 上积极参与开源社区