排序算法之快排以及各排序算法效率比较

1468848854

最后一篇排序算法,快速排序,该算法基本思想是这样

1.先从数列中取出一个数作为基准数。

2.分区过程,将比这个数大的数全放到它的右边,小于或等于它的数全放到它的左边。
3.再对左右区间重复第二步,直到各区间只有一个数。

如图

Java核心代码实现

static void qsort(int[] array, int left, int right) {
if (left < right) {
// 每次一最左变的为基数t
int t = array[left], i = left, j = right;
// 从当前段右边开始找比t大的数
while (i < j && array[j] >= t)
j–;
// 找到比t大的数
if (i < j)
array[i++] = array[j];
// 从当前段左边开始找比t小的数
while (i < j && array[i] < t)
i++;
// 找到比t小的数
if (i < j)
array[j–] = array[i];
// 已经找到了t的位置
array[i] = t;
// 从右边开始找
qsort(array, left, right - 1);
// 从左边开始找
qsort(array, left + 1, right);
}

下面是几个排序算法的效率进行比较

单位ms(毫秒),每次生成的是0-1000的随机数,所以取的是运行10次的平均值,可以看出效率最高是的归并排序,什么冒泡插入就不列举了,还有就是快排在100个数据的时候感觉就要挂了,竟然运行了2000000+ms

排序数目 归并排序 希尔排序 堆排 Java的Arrays类自带排序
100 0ms 0ms 0ms 0ms
1000 2ms
10ms 16ms 1ms
10000 13ms 107ms 100ms 11ms
50000 16ms 3300ms 900ms 28ms
100000 21ms 9720ms 1887ms 41ms

自己写的Oauth协议第三方登陆授权系统(单账户多站点登陆)

1468926217

相信大家都用过第三方登陆,第三方登陆的好处是不用注册,而且只需记住一个账号密码即可,可以那么问题来了。
什么是Oauth协议

OAuth(开放授权)是一个开放标准。

允许第三方网站在用户授权的前提下访问在用户在服务商那里存储的各种信息。

而这种授权无需将用户提供用户名和密码提供给该第三方网站。

OAuth允许用户提供一个令牌给第三方网站,一个令牌对应一个特定的第三方网站,同时该令牌只能在特定的时间内访问特定的资源。
OAuth认证和授权的过程

1、用户访问第三方网站网站,想对用户存放在服务商的某些资源进行操作。

2、第三方网站向服务商请求一个临时令牌。

3、服务商验证第三方网站的身份后,授予一个临时令牌。

4、第三方网站获得临时令牌后,将用户导向至服务商的授权页面请求用户授权,然后这个过程中将临时令牌和第三方网站的返回地址发送给服务商。

5、用户在服务商的授权页面上输入自己的用户名和密码,授权第三方网站访问所相应的资源。

6、授权成功后,服务商将用户导向第三方网站的返回地址。

7、第三方网站根据临时令牌从服务商那里获取访问令牌。

8、服务商根据令牌和用户的授权情况授予第三方网站访问令牌。

9、第三方网站使用获取到的访问令牌访问存放在服务商的对应的用户资源。

老规矩的来张图简单粗暴的了解Oauth

我就是贪在他只需记住一个账号密码即可登陆其他的,比如我要登陆几个系统的后台,密码账号什么的一大堆,但是使用第三方登陆授权可以轻松解决这个问题,而且可以设置用户权限,于是我选择了使用第三方登陆授权解决多账号多站点登陆,实现一个账号登陆多个系统。
DEMO

账号1:Ape 密码:Ape

账号2:test 密码:test

三个demo:https://api.xiaocp.com/oauthdemo/

SDK开发工具包下载Ape_SDK1.0
SDK介绍

下载sdk解压后有4个php文件

config.php

<?php
/**

config是配置文件,分别给网站配上APPID,APPKEY,CALLBACK三个属性,三者都是一一对应的

接下来是Oauth.php核心类

<?php
/**

  • Created by PhpStorm.
  • User: Ape
  • Date: 2016-7-17
  • Time: 16:04
  • /
    require_once(‘config.php’);
    require_once(‘URL.class.php’);

class Oauth{

const VERSION = "1.0";
const GO_LOGIN_URL = "https://api.xiaocp.com/oauth/index/login";
const GET_OPENID_URL = "https://api.xiaocp.com/oauth/index/get_token";
const GET_USER_INFO_URL = "https://api.xiaocp.com/oauth/index/get_user_info";

public $urlUtils;
protected $error;

private static $data;

public function __construct(){
    session_start();
    $this->urlUtils = new URL();
    $this->error = new ErrorCase();
}

public function login(){
    $appid = APE_OAUTH_SDK_APPID;
    $appkey = APE_OAUTH_SDK_APPKRY;
    $callback = APE_OAUTH_SDK_CALLBACK;

    //-------生成唯一随机串防CSRF攻击
    $state = md5(uniqid(rand(), true));
    $_SESSION['state'] = $state;

    //-------构造请求参数列表
    $keysArr = array(
        "client_id" => $appid,
        "client_key" => $appkey,
        "redirect_uri" => $callback,
        "state" => $state,
    );

    $login_url =  $this->urlUtils->combineURL(self::GO_LOGIN_URL, $keysArr);
    header("Location:$login_url");
}

public function callback(){
    //--------验证state防止CSRF攻击
    $state = $_SESSION['state'];
    if($_GET['state'] != $state){
        $this->error->showError("30001");
    }

    //-------请求参数列表
    $keysArr = array(
        "client_id" => APE_OAUTH_SDK_APPID,
        "redirect_uri" => APE_OAUTH_SDK_CALLBACK,
        "client_key" => APE_OAUTH_SDK_APPKRY,
        "code" => $_GET['code']
    );

    //------构造请求access_token的url
    $token_url = $this->urlUtils->combineURL(self::GET_OPENID_URL, $keysArr);
    $response = $this->urlUtils->get_contents($token_url);
    $msg = json_decode($response, true);
    return $msg['data'];
}

public function get_user_info($access_token = '', $open_id = ''){
    //-------请求参数列表
    $keysArr = array(
        "access_token" => $access_token,
        "open_id" => $open_id,
    );

    //------构造请求access_token的url
    $token_url = $this->urlUtils->combineURL(self::GET_USER_INFO_URL, $keysArr);
    $response = $this->urlUtils->get_contents($token_url);
    $msg = json_decode($response, true);

    return $msg['data'];
}

}

前面几个声明的常量是请求服务端地址,先是要调用login()函数进行请求转发,会弹出这么的个页面

这就是第三方请求登陆的页面,然后登陆成功会到code跟state参数回传到毁掉地址,state用于检验数据的一致性,code参数的值我在服务端设定了60秒失效,那么就要在这时间内调用callback()函数获取access_token与open_id,同一个用户的不同web应用的openid是不一样的,然后再调用get_user_info函数就可以拿到用户的资料什么的啦哈哈。

谈谈你的最后一个暑假

1472745743

前言:大学临毕业前的最后一个暑假,可以说是工作之前最轻松的了。工作后,我们要面对的问题有很多,会很忙碌,休息的时间少了,假期少了,不会再有暑假那么长的假期了。所以,对于这个假期,我们要珍惜,不要浪费。这个暑假至关重要,一定要好好的利用。

思考,沉思,思考未来以及现在。过完这个暑假,没有多长时间就要迈入社会了,要实习工作了。所以,这个暑假里,好好的思考一下自己的未来,想想自己的未来应该是怎么样的,自己适合做什么样的工作,这些都至关重要。这个关系到你的第一份工作的选择,这个想清楚了,那么你的人生的第一步就开始了,就要展开未来的蓝图了。

最后一个暑假,我选择留在学校做事情,每天我们六个人一起吃饭一起去六号楼一起回宿舍,这段时光过得充实又难忘。还是那句话计划赶不上变化,中途家里出了点事情回去了一段时间,但是都捱过来了都会好起来的。

深入浅析Java之Static Class

1488901775

摘要今天刚刚从凡科面试Java回来,4个小时的来回车程敌不过一张试卷一杯热茶还有那问不到10句话的面试官,坐等复试通知,祝我好运。

问题描述试卷是5道Java题,前面4题都是一些关于Java的小逻辑小算法题目, 最后一题有点尴尬了。。。那就是 static class

之前接触过 静态实例变量静态方法静态块 ,mmp竟然还有个static class

当时的题目的代码是这样的

public static class XXX{

}
当时我就觉得怪怪的,其实问题就出在这,只有内部静态类!这样是错的。

下面是静态内部类与非静态内部类的区别
(1)内部静态类不需要有指向外部类的引用。但非静态内部类需要持有对外部类的引用。

(2)非静态内部类能够访问外部类的静态和非静态成员。静态类不能访问外部类的非静态成员。他只能访问外部类的静态成员。

(3)一个非静态内部类不能脱离外部类实体被创建,一个非静态内部类可以访问外部类的数据和方法,因为他就在外部类里面。

还有就是创建静态内部类与非静态内部类实例的区别
静态内部类实例 = new 外部类.静态内部类();
// 创建静态内部类的实例
OuterClass.StaticInnerClass simple = new OuterClass.StaticInnerClass();
非静态内部类实例 =new 外部类.new 非静态内部类();

// 创建非静态内部类的实例
OuterClass.InnerClass obj = new OuterClass().new InnerClass();

DWR网页推送技术之聊天系统

1489066101

之前,是上学期的事情了,去的一家老师介绍的公司面试Java,是个中型公司,很有发展性,可惜我们六个人都没过面试,虽说过程不如意,但是整个面试下来收获也不少,就比如这一门之前没听过的技术 DWR 。

至于DWR是什么?

它包含两个主要的部分:允许JavaScript从WEB服务器上一个遵循了AJAX原则的Servlet中获取数据.另外一方面一个JavaScript库可以帮助网站开发人员轻松地利用获取的数据来动态改变网页的内容.

DWR采取了一个类似AJAX的新方法来动态生成基于JAVA类的JavaScript代码。这样WEB开发人员就可以在JavaScript里使用Java代码,就像它们是浏览器的本地代码(客户端代码)一样;但是Java代码运行在WEB服务器端而且可以自由访问WEB 服务器的资源。出于安全的理由,WEB开发者必须适当地配置哪些Java类可以安全的被外部使用

基于DWR聊天系统DEMO http://www.xiaocp.com:8080/springmvc/chat

矩阵快速幂

1490111648

矩阵快速幂是用来高效地计算矩阵的高次方的。将次方计算的o(n)的时间复杂度,降到log(n)。

矩阵快速幂原理:
把n个数进行两两分组,比如:XXXXXX 可以转换成 (X*X)(XX)(X*X)

左边是的以X为基础进行的6次运算,右边的是以(X*X)为基础进行了3次计算

所以矩阵快速幂的的好处在于减少重复计算的次数
再来看看矩阵快速幂的具体实现是怎么样的

也是很容易理解

例如
X^21 可以拆分成 (X^16) * (X^4) * (X^1)

X^320 可以拆分成 (X^256) * (X^64)

没错,细心的朋友们肯定是发现了

21 的二级制为 10101,即 2^4 + 2^2 + 2^0 的值 16,4,1

320 的二级制为 101000000,即 2^8 + 2^6 的值 256,64

与二进制快速求幂核心代码一致

long pow(int x, int n){
long p = 1;
while (n != 0){
if (n & 1 == 1) p = x;
x = x;
n >>= 1;
}
return p;
}
完整代码
/

  • 矩阵 快速幂

  • @author Ape

  • /
    public class JuZhen {

    public static int[][] multiply(int[][] a, int[][] b) {

    int[][] array = new int[a.length][b[0].length];
    for (int i = 0; i < a.length; i++) {
        for (int j = 0; j < b[0].length; j++) {
            for (int k = 0; k < a[0].length; k++) {
                array[i][j] += a[i][k] * b[k][j];
            }
        }
    }
    return array;

    }

    public static int[][] pow(int[][] a, int n) {

    int[][] res = new int[a.length][a[0].length];
    for (int i = 0; i < res.length; i++) {
        for (int j = 0; j < res[0].length; j++) {
            if (i == j)
                res[i][j] = 1;
            else
                res[i][j] = 0;
        }
    }
    
    while (n != 0) {
        if ((n & 1) == 1) // 判断最后边一位是否为1
            res = multiply(res, a);
        n >>= 1; // 往右移一位
        a = multiply(a, a);
    }
    return res;

    }

    public static void main(String[] args) {

    int[][] array = { { 1, 1, 1 }, { 1, 1, 1 }, { 1, 1, 1 } };
    int[][] resArray = pow(array, 4);
    for (int i = 0; i < resArray.length; i++) {
        for (int j = 0; j < resArray[0].length; j++) {
            System.out.print(resArray[i][j] + "  ");
        }
        System.out.println();
    }
    System.out.println(2 << 1);

    }

}

巧用位运算

1490152102

程序中的所有数在计算机内存中都是以二进制的形式储存的。位运算说穿了,就是直接对整数在内存中的二进制位进行操作,位运算速度最快。

很久之前我也知道也了解也用过位运算,但并没有那么的熟悉,今天来总结一下吧。

Java也有C也有,都提供了6种位运算

&
按位与
相同位的两个数字都为1,则为1;若有一个不为1,则为0。

| 按位或
相同位只要一个为1即为1。

^ 按位异或
相同位不同则为1,相同则为0。

~ 按位取反
内存中的0和1全部取反

<< 左移
转为二进制后左移n位,相当于 * 2

右移
转为二进制后右移n位

1.交换两个数不需要第三个变量
x ^= y;
y ^= x;
x ^= y;
2.二进制快速幂
long pow(int x, int n){
long p = 1;
while (n != 0){
if ((n & 1) == 1) p *= x;
x *= x;
n >>= 1;
}
return p;
}
3.判断奇数偶数
n&1 结果为1,则n为奇数,否则偶数

n%2 = n&1

n%4 = n&3

n%8 = n&7

4.代替if else
if (x == a)
x= b;
else
x= a;
等价于
x= a ^ b ^ x;
以后有遇到的再补充

动态规划 VS 深度优先搜索

1490449085

如题描述
1 2 3
4 5 6
7 8 9
计算表格从左上角到右下角的最大和,每次只能向左或者向右走。

接到题目脑海里第一个想法就是dfs,现在感觉dfs有点low了,不过dfs是解决办法的一种,但是还是那句话,具体问题具体分析,对于这个问题还是dp效率比较高

动规解题的一般思路

  1. 将原问题分解为子问题

    把原问题分解为若干个子问题,子问题和原问题形式相同或类似,只不过规模变小了。子问题都解决,原问题即解决(数字三角形例)。

    子问题的解一旦求出就会被保存,所以每个子问题只需求 解一次。

  2. 确定状态

    在用动态规划解题时,我们往往将和子问题相关的各个变量的一组取值,称之为一个“状 态”。一个“状态”对应于一个或多个子问题, 所谓某个“状态”下的“值”,就是这个“状 态”所对应的子问题的解。

    所有“状态”的集合,构成问题的“状态空间”。“状态空间”的大小,与用动态规划解决问题的时间复杂度直接相关。 在数字三角形的例子里,一共有N×(N+1)/2个数字,所以这个问题的状态空间里一共就有N×(N+1)/2个状态。

    整个问题的时间复杂度是状态数目乘以计算每个状态所需时间。在数字三角形里每个“状态”只需要经过一次,且在每个状态上作计算所花的时间都是和N无关的常数。

  3. 确定一些初始状态(边界状态)的值

    以“数字三角形”为例,初始状态就是底边数字,值就是底边数字值。

  4. 确定状态转移方程

    定义出什么是“状态”,以及在该“状态”下的“值”后,就要找出不同的状态之间如何迁移――即如何从一个或多个“值”已知的 “状态”,求出另一个“状态”的“值”(递推型)。状态的迁移可以用递推公式表示,此递推公式也可被称作“状态转移方程”。

能用动规解决的问题的特点

1) 问题具有最优子结构性质。如果问题的最优解所包含的 子问题的解也是最优的,我们就称该问题具有最优子结 构性质。

2) 无后效性。当前的若干个状态值一旦确定,则此后过程的演变就只和这若干个状态的值有关,和之前是采取哪种手段或经过哪条路径演变到当前的这若干个状态,没有关系。

DP And DFS 实现
import java.util.Scanner;

public class Dp {

static int[][] map = new int[101][101];
static int[][] dp = new int[101][101];
static int max = 0, n, m;

public static void main(String[] args) {

    Scanner scanner = new Scanner(System.in);

    n = scanner.nextInt();
    m = scanner.nextInt();

    // input
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            dp[i][j] = map[i][j] = scanner.nextInt();

    // dp
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + map[i][j];

    // print result
    System.out.println(dp[n][m]);
    dfs(1, 1, 0);
    System.out.println(max);

    scanner.close();

}

static void dfs(int x, int y, int value) {
    if (x > n || y > m)
        return;

    value += map[x][y];
    if (x == n && y == m) {
        if (max < value)
            max = value;
    }

    dfs(x + 1, y, value);
    dfs(x, y + 1, value);
}

}

再探 地宫取宝

1490535525

题目描述
标题:地宫取宝

X 国王有一个地宫宝库。是 n x m 个格子的矩阵。每个格子放一件宝贝。每个宝贝贴着价值标签。
地宫的入口在左上角,出口在右下角。
小明被带到地宫的入口,国王要求他只能向右或向下行走。
走过某个格子时,如果那个格子中的宝贝价值比小明手中任意宝贝价值都大,小明就可以拿起它(当然,也可以不拿)。
当小明走到出口时,如果他手中的宝贝恰好是k件,则这些宝贝就可以送给小明。
请你帮小明算一算,在给定的局面下,他有多少种不同的行动方案能获得这k件宝贝。

数据格式
输入一行3个整数,用空格分开:n m k (1<=n,m<=50, 1<=k<=12)
接下来有 n 行数据,每行有 m 个整数 Ci (0<=Ci<=12)代表这个格子上的宝物的价值
要求输出一个整数,表示正好取k个宝贝的行动方案数。该数字可能很大,输出它对 1000000007 取模的结果。

例如,输入

2 2 2
1 2
2 1
输出
2
输入
2 3 2
1 2 3
2 1 5
输出
14
峰值内存消耗(含虚拟机) < 256M
CPU消耗 < 2000ms

以前的题解 DFS记忆化搜索 http://www.xiaocp.com/single/36

当然,当时的通过率只有40%左右吧

来看看DP解法,100分通过,思路是这样的,我采用一个四维数组进行运算,即数组dp[x][y][k][max],数组的意思是 走到坐标 x y已取到k件宝贝,宝贝最大值是max,数组的值是方法数,这么一来清晰明了多了,那么他当前的方法数 += x坐标减1 + y坐标减1 (因为是往下或者往右边走)

代码实现
public class Main{
static final int N = 55;
static final int M = 15;
static final int MOD = 1000000007;

static int dp[][][][] = new int[N][N][M][M];
static int map[][] = new int[N][N];

public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);

    int n = scanner.nextInt();
    int m = scanner.nextInt();
    int k = scanner.nextInt();

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            map[i][j] = scanner.nextInt();
            map[i][j]++; // 区分本身为0
        }

    dp[1][1][1][map[1][1]] = 1;
    dp[1][1][0][0] = 1;

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            if (i == 1 && j == 1)
                continue;
            for (int c = 0; c <= k; c++)
                for (int max = 0; max < 13; max++) {
                    if (max < map[i][j])
                        dp[i][j][c + 1][map[i][j]] = ((dp[i][j][c + 1][map[i][j]]
                                % MOD + dp[i - 1][j][c][max] % MOD)
                                % MOD + dp[i][j - 1][c][max] % MOD)
                                % MOD;
                    dp[i][j][c][max] = ((dp[i][j][c][max] % MOD + dp[i - 1][j][c][max]
                            % MOD)
                            % MOD + dp[i][j - 1][c][max] % MOD)
                            % MOD;
                }
        }
    int ans = 0;
    // 结果是  最大宝贝价值  0 - 12 的总和
    for (int i = 0; i < 13; i++)
        ans = (ans + dp[n][m][k][i]) % MOD;

    System.out.println(ans);

    scanner.close();
}

}