Lemuria 发布的文章

随想


最近一段时间浑浑噩噩,不知道在做些什么,从六月中旬去暑期实习到现在,经过了秋招提前批,现在又开始秋招了,虽然offer陆陆续续拿了几个,但猛然一想,从开始工作到现在居然没有怎么深入学习过一门技术,在公司用到的新技术,也只是浅尝辄止。今天看了一些大神的面经,发现很多题目自己都不会,乃至于一些技术甚至没有听说过。

五月份去面试的时候还不会分布式,对分布式服务几乎没有了解,回来后虽然把SpringCloud全家桶和其他一些中间件都学了一遍,但也只是学了一遍,会用而已,实现之类的根本没看,貌似达不到大厂面试的要求。从六月份到现在自我感觉没有丝毫进步,学习上似乎到了一个瓶颈。浪费了两个月时间实在是该死,恐怖的是当时的自己完全没有意识到这件事,看来心态的转变也很重要,自以为天下无敌,殊不知自己原来是井底之蛙。

学习如逆水行舟,不进则退,别人会用的技术自己不会,别人学了新东西自己没学,别人的技术基础比自己扎实,我还有什么理由沾沾自喜呢?现在一想,自己离优秀还差得远呢,不过是运气好了一些,面试官放松了一些罢。倘若再来一遍,结果还未可知呢。技术的大海无边无际,拿到了offer就开始躺平自甘堕落,实在是愚蠢至极,不可救药。记以此文,警醒自己。


AVL树的Java实现


AVL树的Java实现

1. 前言

AVL树是带有平衡条件的二叉查找树,如果我们向一棵树插入排好序的一组数,树会变得很深而且左右两边不平衡。或者删除数据的时候也经常有这种情况,这时候插入和删除操作的复杂度会大幅上升。引入平衡条件后,就解决了这个问题。具体分析参见《数据结构与算法分析》第四版二叉搜索树和AVL树的章节。

2. 代码
package data.structure;

//节点定义
class AvlTreeNode {
    Integer value;
    AvlTreeNode left = null;
    AvlTreeNode right = null;
    Integer height = 0;

    @Override
    public String toString() {
        return "AvlTreeNode{" +
                "value=" + value +
                ", height=" + height +
                '}';
    }

    public AvlTreeNode(Integer value) {
        this.value = value;
    }
    public AvlTreeNode() {
    }
}

public class AvlTree {
    //获取树的高度,定义空节点的高度为-1,叶子节点的高度为0
    int getTreeHeight(AvlTreeNode root){
        return root == null ? -1 : root.height;
    }

    //插入数据和搜索树一样,多了个平衡操作
    AvlTreeNode insert(AvlTreeNode root, int value){
        if(root.value == null){
            root.value = value;
            return root;
        } else {
            if(root.value > value){
                if(root.left != null){
                    root.left = insert(root.left, value);
                } else {
                    root.left = new AvlTreeNode(value);
                }
            } else if(root.value < value) {
                if(root.right != null){
                    root.right = insert(root.right, value);
                } else {
                    root.right = new AvlTreeNode(value);

                }
            }
        }

        //插入完成后执行平衡操作
        root = balance(root);
        //返回平衡完成后的根节点
        return root;
    }

    /*
    * 不平衡的四种情况:
    * 1. 向左子树的左子树插入数据导致不平衡
    * 2. 向左子树的右子树插入数据导致不平衡
    * 3. 向右子树的左子树插入数据导致不平衡
    * 4. 向右子树的右子树插入数据导致不平衡
    * */
    AvlTreeNode balance(AvlTreeNode root){
        if(root == null){
            return null;
        }
        //树的两边不平衡,而且属于第一或第二种情况
        if(getTreeHeight(root.left) - getTreeHeight(root.right) > 1){
            //第一种情况,单旋转
            if(getTreeHeight(root.left.left) >= getTreeHeight(root.left.right)){
                root = rotateWithLeftChild(root);
            } else {
                //第二种情况,双旋转
                root = doubleRotateLeftChild(root);
            }

        } else if(getTreeHeight(root.right) - getTreeHeight(root.left) > 1){
            //第四种情况,单旋转
            if(getTreeHeight(root.right.right) > getTreeHeight(root.right.left)){
                root = rotateWithRightChild(root);
            } else {
                //第三种情况,双旋转
                root = doubleRotateRightChild(root);
            }
        }

        root.height = Integer.max(getTreeHeight(root.right),getTreeHeight(root.left)) + 1;
        return root;
    }

    AvlTreeNode rotateWithLeftChild(AvlTreeNode root){
        AvlTreeNode temp = root.left;
        //root.left的右结点值比root.left大,比root小,所以在root的左边
        root.left = temp.right;
        temp.right = root;
        //修改高度
        root.height = Integer.max(getTreeHeight(root.right),getTreeHeight(root.left)) + 1;
        temp.height = Integer.max(getTreeHeight(temp.left),root.height) + 1;

        //替换掉节点
        root = temp;
        //返回被替换后的根节点
        return root;
    }

    AvlTreeNode rotateWithRightChild(AvlTreeNode root){
        AvlTreeNode temp = root.right;
        root.right = temp.left;
        temp.left = root;
        root.height = Integer.max(getTreeHeight(root.right),getTreeHeight(root.left)) + 1;
        temp.height = Integer.max(getTreeHeight(temp.left),root.height) + 1;

        //替换掉节点
        root = temp;
        //返回被替换后的根节点
        return root;
    }
    //双旋转左子树
    AvlTreeNode doubleRotateLeftChild(AvlTreeNode root){
        //先将左子树的右节点左旋,例如{5,3,4},旋转完成后变成{5,4,3}
        root.left = rotateWithRightChild(root.left);
        //再单旋转一次,变成{4,3,5}
        root = rotateWithLeftChild(root);
        return root;
    }
    //双旋转右子树
    AvlTreeNode doubleRotateRightChild(AvlTreeNode root){
        root.right = rotateWithLeftChild(root.right);
        root = rotateWithRightChild(root);
        return root;
    }
    //先根遍历
    void print(AvlTreeNode root){
        if(root != null){
            System.out.print(root + " ");
            if(root.left != null){
                print(root.left);
            }
            if(root.right != null){
                print(root.right);
            }
        }
        return;
    }
    //寻找值最小的节点
    AvlTreeNode findMin(AvlTreeNode root){
        if(root == null){
            return null;
        }
        if(root.left!=null){
            return findMin(root.left);
        } else{
            return root;
        }
    }
    //删除操作和普通的搜索树一样,只不过多加了一个平衡
    AvlTreeNode delete(AvlTreeNode root, Integer value){
        if(root == null){
            return null;
        }
        if(root.value > value){
            root.left = delete(root.left, value);
        } else if(root.value < value){
            root.right = delete(root.right, value);
        } else if(root.right!=null && root.left!=null) {
            root.value = findMin(root.right).value;
            root.right = delete(root.right, root.value);
        } else{
            root =  root.left != null?root.left:root.right;
        }
        //删除完成后执行平衡操作
        root = balance(root);
        //返回平衡完成后的根节点
        return root;
    }

    void run(){
        int[] nums = {1,2,3,4,5,6,7,16,15,14,13,12,11,10,9,8};
        //int[] nums = {1,2,3};
        //int[] nums = {5,4,3,2,1};
        //int[] nums = {5,3,4};
        AvlTreeNode root = new AvlTreeNode();

        for (int num : nums) {

            root = insert(root, num);
            //插入一次输出一次
            print(root);
            System.out.println();
        }

        delete(root,4);
        print(root);
    }

    public static void main(String[] args) {
        AvlTree avlTree = new AvlTree();
        avlTree.run();

    }

}

面试小记


面试小记

今天去面试Java后端实习生,虽然说面试过了,不过被打击的很惨,进公司先填了一份个人信息,然后就有一个前端的大哥过来面试我,感觉挺随和的,问的东西也是比较简单的排序算法,然后介绍一下自己做过的项目,大学里平时都学些啥。

然后前端大哥就拿着我的简历出去了,又来了一个后端大哥,我还想着他会从哪里开始问起呢,不知道是不是因为我简历上写了学过算法的原因,他给了我一个开幕雷击:“你对红黑树有什么理解吗?”。当时人就傻了,红黑树只在大二下学期的时候看过一点点,而且没有深入,现在都忘了个七七八八,只好说不知道。然后大哥就没说话了,过了一会又问我JDK版本一般用的几,我说8,然后他就问有没有用过8以上的版本,好家伙我也没有,问我jvm的默认垃圾回收器,可惜我面试前只看了垃圾回收的几种方式,垃圾回收器给忘了,又没答出来。然后又是沉默,沉默是今晚的康桥。看见我简历上写了项目,然后问:“只有一个项目吗?”。我记得简历上是有两个的,然后就指了一下,接着就又是沉默。。我感觉不太妙,就说博客系统还在线上,可以访问看看,后端大哥也没咋理我。。。最后问了一个如果给一个项目我写,我能不能完成,我问他能不能详细点,他说springcloud的。我前段时间学了springcloud,不过还没学完,只好说自己还没学完,但在入职之前可以学完。大哥沉默一阵后就出去了。

最后人事过来说我过了,问我感觉咋样,说实话真的很意外,可能是给我一个机会吧。

这次面试让我觉得自己的技术栈还很有欠缺,算法部分因为太久没有使用和学习已经忘了很多,新的技术还没有学完,后端大哥问的东西一个都答不出来,是时候把书架上已经吃灰的数据结构与算法分析拿出来看看了,学习新技术也应该提上日程,不能每天混日子了。时不我待,以此诫勉自己。


debian安装svn服务端


debian安装svn服务端

最近有一个新项目需要几个人一起开发,就搭建一个svn服务器顺便学习一下svn管理代码。

1、安装svn

sudo apt-get install subversion

2、创建一个svn启动目录,哪里都行

mkdir /www/svn

3、创建一个仓库

svnadmin create center

4、配置用户和权限

vi /www/svn/center/conf/svnserve.conf
svnserve.conf 中默认配置都是注释掉的把下列几个配置去掉注释,稍作修改

[general]
anon-access = read      
auth-access = write       // 有权限用户可读写
password-db = passwd // 指定密码配置文件的路径
authz-db = authz   // 指定目录权限配置文件的路径

vi /www/svn/center/conf/passwd
[users]
username1 = password1
username2 = password2

vi /www/svn/center/conf/authz

[groups]
aaa = username1,username2     //多个用户用逗号分隔
[/]
@aaa = rw
* = r

这样一来服务端就配置好了,客户端直接用就行。


SpringBoot整合JWT+shiro


SpringBoot整合JWT+shiro

前段时间写了个前后端分离的项目,被跨域的问题折磨了,前几天学了JWT,和shiro整合后就可以更方便了。

不过自己技术浅薄,在网上找了会后发现一个挺不错的博客,看了一遍后写完了。

放上链接:

https://blog.csdn.net/u010606397/article/details/104110093

1、shiro的工作流程

在整合这两个之前我们需要清楚shiro+jwt的工作流程,如下:

1、AccessControlFilter#onPreHandle()
2、AuthenticationFilter#isAccessAllowed(),此方法仅判断当前的subject(用户)是否已经认证,结果subject.authenticated是未认证。
3、JwtFilter#onAccessDenied(),用户未认证,此方法被调用。
4、JwtFilter#executeLogin(), 使用请求头Authorization生成JwtToken,然后执行subject.login(JwtToken);
5、AuthenticatingRealm#getAuthenticationInfo(),通过JwtToken查询缓存中的AuthenticationInfo
6、缓存中没有AuthenticationInfo,进入 JwtRealm#doGetAuthenticationInfo(),校验token合法性,并生成SimpleAuthenticationInfo。

7、DefaultWebSubjectFactory#createSubject,使用SimpleAuthenticationInfo中的principals生成一个已认证的subject,用户认证就完成了。

授权流程是这样:

1、AccessControlFilter#onPreHandle()
2、PermissionsAuthorizationFilter#isAccessAllowed(),判断subject是否具备接口权限。
3、AuthorizingRealm#getAuthorizationInfo(),获取授权缓存。
4、没有授权缓存,通过JwtRealm#doGetAuthorizationInfo()获取授权信息。

有了这个我们就开始写代码了。

2、JWTUtils

首先需要有一个JWT的工具类,我这个工具类写的很不完善,临时用一下。

public class JWTUtils {
    private static final String SIGN = "!@a$Df^a8b)%";

    public static String getToken(Map<String,String> map){
        Calendar instance = Calendar.getInstance();
        instance.add(Calendar.DATE,7);
        JWTCreator.Builder builder = JWT.create();
        builder.withExpiresAt(instance.getTime());
        for (String s : map.keySet()) {
            builder.withClaim(s,map.get(s));
        }
        String token = builder.sign(Algorithm.HMAC256(SIGN));

        return token;
    }

    public static DecodedJWT verify(String token){
        return JWT.require(Algorithm.HMAC256(SIGN)).build().verify(token);
    }

    /*public static DecodedJWT getTokenInfo(String token){
        return JWT.require(Algorithm.HMAC256(SIGN)).build().verify(token);
    }*/
    public static String getUsername(String token){
        String username = String.valueOf(JWT.require(Algorithm.HMAC256(SIGN)).build().verify(token).getClaim("username"));
        return username;
    }
}

2、JwtToken

创建一个JwtToken用来替代AuthenticationToken,如下:

public class JwtToken implements AuthenticationToken {
    private String token;

    public JwtToken(String token) {
        this.token = token;
    }

    @Override
    public Object getPrincipal() {
        return this.token;
    }
    //因为token里面有信息了,这个直接返回空就行
    @Override
    public Object getCredentials() {
        return "";
    }
}

3、Filter

根据上面的流程,我们需要两个filter,一个BasicHttpAuthenticationFilter,一个PermissionsAuthorizationFilter。

首先创建一个JwtFilter,继承BasicHttpAuthenticationFilter,如下:

//创建一个JwtFilter继承BasicHttpAuthenticationFilter
public class JwtFilter extends BasicHttpAuthenticationFilter {

    /*
    重写createToken,onAccessDenied,executeLogin三个方法
     */
    @Override
    protected AuthenticationToken createToken(ServletRequest request, ServletResponse response) {
        //获取请求头中Authorization的值
        String authorization = getAuthzHeader(request);
        //用获取到的值创建token对象
        return new JwtToken(authorization);
    }

    //身份认证未通过
    @Override
    protected boolean onAccessDenied(ServletRequest request, ServletResponse response) throws Exception {
        boolean r;
        String authorization = getAuthzHeader(request);
        HashMap<String, Object> map = new HashMap<>();
        //判断authorization是否为空
        if (authorization == null||authorization == ""){
            map.put("state",false);
            map.put("massage","没有token");
            //没有token,返回false,登录页面虽然没有token,但是不会被拦截
            r = false;
            response.setCharacterEncoding("UTF-8");
            response.getWriter().println(JSONObject.toJSON(map));
        } else {
            r = executeLogin(request, response);
        }

        return r;
    }

    //执行登录操作
    @Override
    protected boolean executeLogin(ServletRequest request, ServletResponse response) throws Exception {
        AuthenticationToken token = this.createToken(request, response);
        HashMap<String, Object> map = new HashMap<>();
        response.setCharacterEncoding("UTF-8");
        if(token == null){
            map.put("state",false);
            map.put("massage","未登录");
            return false;
        } else{
            try{
                Subject subject = this.getSubject(request, response);
                subject.login(token);
                return this.onLoginSuccess(token,subject,request,response);
            } catch (Exception e){
                map.put("state",false);
                map.put("massage","用户认证异常");
                e.printStackTrace();
                response.getWriter().println(JSONObject.toJSON(map));
                response.getWriter().close();
                return false;
            }

        }
    }
}

用户访问时,被过滤器拦截下来后因为没有认证,调用onAccessDenied方法,如果没有附带token,就返回没有token,访问结束。如果附带了token,则执行executeLogin方法。

然后创建一个CustomPermissionsAuthorizationFilter继承PermissionsAuthorizationFilter,如下:

public class CustomPermissionsAuthorizationFilter extends PermissionsAuthorizationFilter {

    /**
     * 用户无权访问url时,此方法会被调用
     * 默认实现为org.apache.shiro.web.filter.authz.AuthorizationFilter#onAccessDenied()
     * 覆盖父类的方法,返回自定义信息给前端
     *
     * 接口doc上说:
     *    AuthorizationFilter子类(权限授权过滤器)的onAccessDenied()应该永远返回false,那么在onAccessDenied()内就必然要发送response响应给前端,不然前端就收不到任何数据
     *    AuthenticationFilter、AuthenticatingFilter子类(身份认证过滤器)的onAccessDenied()的返回值则没有限制
     */
    @Override
    protected boolean onAccessDenied(ServletRequest request, ServletResponse response){
        HashMap<String, Object> map = new HashMap<>();
        map.put("state",false);
        map.put("massage","权限不足");
        try {
            response.getWriter().println(JSONObject.toJSONString(map));
            response.getWriter().close();
        } catch (IOException e) {
            e.printStackTrace();
        }
        return false;
    }

}

4、Realm

public class JwtRealm extends AuthorizingRealm {

    //因为是熟悉流程,所以授权就没写
    @Override
    protected AuthorizationInfo doGetAuthorizationInfo(PrincipalCollection principals) {
        return null;
    }

    @Override
    protected AuthenticationInfo doGetAuthenticationInfo(AuthenticationToken authenticationToken) throws AuthenticationException {
        String token = (String) authenticationToken.getPrincipal();
        try{
            //检查token是否有效,如果有效就创建一个subject
            JWTUtils.verify(token);
            return new SimpleAuthenticationInfo(token, "",this.getName());
        } catch (Exception e){
            e.printStackTrace();
            return null;
        }

    }
    // subject.login(token)方法中的token是JwtToken时,调用此Realm的doGetAuthenticationInfo
    @Override
    public boolean supports(AuthenticationToken token) {
        return token instanceof JwtToken;
    }
}

5、Config

最后需要一个ShiroConfig来配置好上面的过滤器和Realm

@Configuration
public class ShiroConfig {

    @Bean
    public JwtRealm jwtRealm(){
        return new JwtRealm();
    }

    @Bean("mySecurityManager")
    public DefaultWebSecurityManager securityManager(@Qualifier("jwtRealm") JwtRealm jwtRealm){
        DefaultWebSecurityManager manager = new DefaultWebSecurityManager();
        manager.setRealm(jwtRealm);


        //禁止session持久化存储
        DefaultSubjectDAO subjectDAO = new DefaultSubjectDAO();
        DefaultSessionStorageEvaluator defaultSessionStorageEvaluator = new DefaultSessionStorageEvaluator();
        defaultSessionStorageEvaluator.setSessionStorageEnabled(false);
        subjectDAO.setSessionStorageEvaluator(defaultSessionStorageEvaluator);
        manager.setSubjectDAO(subjectDAO);

        return manager;
    }

    @Bean
    public ShiroFilterFactoryBean shiroFilterFactoryBean(@Qualifier("mySecurityManager") DefaultWebSecurityManager securityManager){
        ShiroFilterFactoryBean factoryBean = new ShiroFilterFactoryBean();

        factoryBean.setSecurityManager(securityManager);

        //添加filter,factoryBean.getFilters()获取到的是引用,可直接添加值
        factoryBean.getFilters().put("jwt", new JwtFilter());
        factoryBean.getFilters().put("customPerms", new CustomPermissionsAuthorizationFilter());

        /**
         * factoryBean.getFilterChainDefinitionMap();默认是size=0的LinkedHashMap
         */
        Map<String, String> definitionMap = factoryBean.getFilterChainDefinitionMap();

        /**
         * definitionMap是一个LinkedHashMap,是一个链表结构
         * put的顺序很重要,当/open/**匹配到请求url后,将不再检查后面的规则
         * 官方将这种原则称为 FIRST MATCH WINS
         * https://waylau.gitbooks.io/apache-shiro-1-2-x-reference/content/III.%20Web%20Applications/10.%20Web.html
         */


        /**
         * 由于禁用了session存储,shiro不会存储用户的认证状态,所以在接口授权之前要先认证用户,不然CustomPermissionsAuthorizationFilter不知道用户是谁
         * 实际项目中可以将这些接口权限规则放到数据库中去
         */
        /*definitionMap.put("/role/permission/edit", "jwt, customPerms["+userService.getRolePermisssionEdit().getName()+"]");*/

        // 前面的规则都没匹配到,最后添加一条规则,所有的接口都要经过com.example.shirojwt.filter.JwtFilter这个过滤器验证
        definitionMap.put("/login", "anon");
        definitionMap.put("/**", "jwt");

        factoryBean.setFilterChainDefinitionMap(definitionMap);

        return factoryBean;

    }
}

这次的学习让我对shiro有了更深刻的理解,不再是像以前一样连用都用不太好。所以说经常看代码还是很有用的。