月度归档:2017年04月

最小的K个数

题目描述

输入n个整数,找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字,则最小的4个数字是1,2,3,4,。

import java.util.*;
public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        if(input==null)return null;
        ArrayList<Integer> res=new ArrayList<Integer>();
        if(input.length<k||k==0){
            return res;
        }
        for(int i=0;i<k;i++){
            res.add(input[i]);
        }
        Collections.sort(res);
        for(int i=k;i<input.length;i++){
            if(res.get(k-1)>input[i]){
                res.remove(k-1);
                res.add(input[i]);
                Collections.sort(res);
            }
        }
        return res;

    }
}

二叉搜索树与双向链表

题目描述

输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向。

代码

/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
     public TreeNode Convert(TreeNode root) {
        if(root==null)return null;
        if(root.left==null&&root.right==null)return root;
        //把左子树转换成为双链表后,返回第一个节点
        TreeNode left=Convert(root.left);
        TreeNode p=left;
        //定位到最后一个节点
        while(p!=null&&p.right!=null){
            p=p.right;
        }
        //把左子树形成的最后一个节点与跟节点连接起来
        if(left!=null){
            p.right=root;
            root.left=p;
        }

        //把右子树转换成为双链表后,返回第一个节点
        TreeNode right=Convert(root.right);
        //连接右子树形成的双链表的第一个节点和根节点连接起来
        if(right!=null){
            right.left=root;
            root.right=right;
        }


        return left!=null?left:root;
    }
}

mybatis学习笔记-基础

新建工程,引入jar包

新建一个工程,引入以下jar包,mybatis的lib目录里面的库,mybatis-x.x.x.jar,mysql(数据库)驱动jar包

引入配置文件

在src(平行于src目录也可以)目录下新建 log4j.properties文件,填入以下代码


log4j.rootLogger=DEBUG,stdout log4j.appender.stdout=org.apache.log4j.ConsoleAppender log4j.appender.stdout.layout=org.apache.log4j.PatternLayout log4j.appender.stdout.layout.ConversionPattern=%5p[%t] - %m%n

在src(平行于src目录也可以)目录下新建 SqlMapConfig(可变),填入以下代码

 <?xml version="1.0" encoding="UTF-8" ?>  
<!DOCTYPE configuration  
  PUBLIC "-//mybatis.org//DTD Config 3.0//EN"  
  "http://mybatis.org/dtd/mybatis-3-config.dtd">  
<configuration>  
    <!-- 对事务的管理和连接池的配置 -->  
    <environments default="development">  
        <environment id="development">  
            <transactionManager type="JDBC" />  
            <dataSource type="POOLED">  
                <property name="driver" value="com.mysql.jdbc.Driver" />  
                <property name="url" value="jdbc:mysql://localhost:3306/mybatis" />  
                <property name="username" value="root" />  
                <property name="password" value="xxxxxx" />  
            </dataSource>  
        </environment>  
    </environments>  
</configuration>

到这里mybatis就算是搭建好了

### User的CRUD 样例

新建 User.java

 package me.xdzhcs.entity;

import java.util.Date;


/**
 * 用户
 * @author xdzhcs
 * 
 */
public class User {

    private int id;
    private String username;
    private String sex;
    private String address;
    private Date birthday;

    public Date getBirthday() {
        return birthday;
    }
    public void setBirthday(Date birthday) {
        this.birthday = birthday;
    }
    public int getId() {
        return id;
    }
    public void setId(int id) {
        this.id = id;
    }
    public String getUsername() {
        return username;
    }
    public void setUsername(String username) {
        this.username = username;
    }
    public String getSex() {
        return sex;
    }
    public void setSex(String sex) {
        this.sex = sex;
    }
    public String getAddress() {
        return address;
    }
    public void setAddress(String address) {
        this.address = address;
    }
    @Override
    public String toString() {
        return "User [id=" + id + ", username=" + username + ", sex=" + sex
                + ", address=" + address + ", birthday=" + birthday + "]";
    }

}

在数据库建立对应的表

CREATE TABLE `user` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `username` varchar(255) DEFAULT NULL,
  `sex` varchar(255) DEFAULT NULL,
  `address` varchar(255) DEFAULT NULL,
  `birthday` date DEFAULT NULL,
  PRIMARY KEY (`id`)
) ENGINE=InnoDB AUTO_INCREMENT=12 DEFAULT CHARSET=utf8mb4;

建user.xml配置文件

<?xml version="1.0" encoding="UTF-8" ?>
<!DOCTYPE mapper PUBLIC "-//mybatis.org//DTD Mapper 3.0//EN" "http://mybatis.org/dtd/mybatis-3-mapper.dtd">
<mapper namespace="test">

     <!--
         根据id查询得到一个user对象
      -->
     <select id="getUserById" parameterType="int" resultType="me.xdzhcs.entity.User">
         select * from user where id=#{id}
     </select>

     <select id="listUserByName" parameterType="java.lang.String" resultType="me.xdzhcs.entity.User">
         select * from user where username like '%${value}%'
     </select>

     <insert id="insertUser" parameterType="me.xdzhcs.entity.User">
        <selectKey keyProperty="id" order="AFTER" resultType="int">
            SELECT LAST_INSERT_ID()
        </selectKey>
        insert into user(username,birthday,address,sex) values(#{username},#{birthday},#{address},#{sex})
     </insert>

     <delete id="deleteUser" parameterType="int">
        delete from user where id = #{id}
     </delete>

     <update id="updateUser" parameterType="me.xdzhcs.entity.User">
        update user set username=#{username}  ,address=#{address}, sex=#{sex},birthday=#{birthday}
        where id=#{id} 
     </update>

</mapper>

增删改差简单测试

package me.xdzhcs.first;

import java.io.IOException;
import java.io.InputStream;
import java.util.Date;
import java.util.List;

import me.xdzhcs.entity.User;

import org.apache.ibatis.io.Resources;
import org.apache.ibatis.session.SqlSession;
import org.apache.ibatis.session.SqlSessionFactory;
import org.apache.ibatis.session.SqlSessionFactoryBuilder;
import org.junit.Test;


public class MybatisFirst {

    //根据id查询一条用户信息
    @Test
    public void getUserByIdTest() throws IOException{

        //mybatis配置文件
        String resource = "SqlMapConfig.xml";

        //得到配置文件流
        InputStream inputStream = Resources.getResourceAsStream(resource);

        //创建会话工厂
        SqlSessionFactory sqlSessionFactory = new SqlSessionFactoryBuilder().build(inputStream);

        //sqlsession
        SqlSession sqlSession = sqlSessionFactory.openSession();

        User user = sqlSession.selectOne("test.getUserById",1);

        System.out.println(user);
        //释放资源
        sqlSession.close();

    }

    @Test
    public void listUserByNameTest() throws IOException{

        //mybatis配置文件
        String resource = "SqlMapConfig.xml";

        //得到配置文件流
        InputStream inputStream = Resources.getResourceAsStream(resource);

        //创建会话工厂
        SqlSessionFactory sqlSessionFactory = new SqlSessionFactoryBuilder().build(inputStream);

        //sqlsession
        SqlSession sqlSession = sqlSessionFactory.openSession();

        List<User> users = sqlSession.selectList("test.listUserByName","abc");

        System.out.println(users);
        //释放资源
        sqlSession.close();

    }
    @Test
    public void insertUserTest() throws IOException{

        //mybatis配置文件
        String resource = "SqlMapConfig.xml";

        //得到配置文件流
        InputStream inputStream = Resources.getResourceAsStream(resource);

        //创建会话工厂
        SqlSessionFactory sqlSessionFactory = new SqlSessionFactoryBuilder().build(inputStream);

        //sqlsession
        SqlSession sqlSession = sqlSessionFactory.openSession();

        User user = new User();
        user.setAddress("address");
        user.setBirthday(new Date());
        user.setSex("boy");
        user.setUsername("xdzhcs");

        sqlSession.insert("test.insertUser",user);
        sqlSession.commit();

        System.out.println("user.id:"+user.getId());

        //释放资源
        sqlSession.close();

    }

    @Test
    public void deleteUserTest() throws IOException{

        //mybatis配置文件
        String resource = "SqlMapConfig.xml";

        //得到配置文件流
        InputStream inputStream = Resources.getResourceAsStream(resource);

        //创建会话工厂
        SqlSessionFactory sqlSessionFactory = new SqlSessionFactoryBuilder().build(inputStream);

        //sqlsession
        SqlSession sqlSession = sqlSessionFactory.openSession();

        sqlSession.delete("test.deleteUser",1);
        sqlSession.commit();


        //释放资源
        sqlSession.close();

    }
    @Test
    public void updateUserTest() throws IOException{

        //mybatis配置文件
        String resource = "SqlMapConfig.xml";

        //得到配置文件流
        InputStream inputStream = Resources.getResourceAsStream(resource);

        //创建会话工厂
        SqlSessionFactory sqlSessionFactory = new SqlSessionFactoryBuilder().build(inputStream);

        //sqlsession
        SqlSession sqlSession = sqlSessionFactory.openSession();

        User user = new User();
        user.setAddress("aaaaaaaaaaaa");
        user.setSex("aaaaaaaa");
        user.setUsername("aaaaaaaaa");
        user.setId(2);
        sqlSession.update("test.updateUser",user);
        sqlSession.commit();


        //释放资源
        sqlSession.close();

    }

}

dao层开发的两种方式

传统dao接口+dao实现模式

先略

mapper代理开发

开发规范

  • 在mapper.xml中namespace等于mapper接口地址
  • mapper.java接口中的方法名和mapper.xml中statement的id一致
  • mapper.java接口中的方法输入参数类型和mapper.xml中statement的paramenterType指定的类型一致
  • mapper.java接口中的方法返回值类型和mapper.xml中statement的resultType指定的类型一致

代码

UserDao.java

package me.xdzhcs;

import java.util.List;

import me.xdzhcs.entity.User;

public interface UserDAO {
    User getUserById(int id) throws Exception;
    List<User> listUserByName(String name) throws Exception;
    void insertUser(User user)throws Exception;
    void deleteUser(int id)throws Exception;
    void updateUser(User user)throws Exception;
}

User.xml

<?xml version="1.0" encoding="UTF-8" ?>
<!DOCTYPE mapper PUBLIC "-//mybatis.org//DTD Mapper 3.0//EN" "http://mybatis.org/dtd/mybatis-3-mapper.dtd">
<mapper namespace="me.xdzhcs.UserDAO">

     <!--
         根据id查询得到一个user对象
      -->
     <select id="getUserById" parameterType="int" resultType="me.xdzhcs.entity.User">
         select * from user where id=#{id}
     </select>

     <select id="listUserByName" parameterType="java.lang.String" resultType="me.xdzhcs.entity.User">
         select * from user where username like '%${value}%'
     </select>

     <insert id="insertUser" parameterType="me.xdzhcs.entity.User">
        <selectKey keyProperty="id" order="AFTER" resultType="int">
            SELECT LAST_INSERT_ID()
        </selectKey>
        insert into user(username,birthday,address,sex) values(#{username},#{birthday},#{address},#{sex})
     </insert>

     <delete id="deleteUser" parameterType="int">
        delete from user where id = #{id}
     </delete>

     <update id="updateUser" parameterType="me.xdzhcs.entity.User">
        update user set username=#{username}  ,address=#{address}, sex=#{sex},birthday=#{birthday}
        where id=#{id} 
     </update>

</mapper>

使用方法

package me.xdzhcs;

import static org.junit.Assert.*;

import java.io.IOException;
import java.io.InputStream;
import java.util.Date;
import java.util.List;

import me.xdzhcs.entity.User;

import org.apache.ibatis.io.Resources;
import org.apache.ibatis.session.SqlSession;
import org.apache.ibatis.session.SqlSessionFactory;
import org.apache.ibatis.session.SqlSessionFactoryBuilder;
import org.junit.Before;
import org.junit.Test;

public class UserDAOTest {

    private SqlSessionFactory sqlSessionFactory;

    @Before
    public void setUp() throws IOException{
        String resource = "SqlMapConfig.xml";
        InputStream inputStream = Resources.getResourceAsStream(resource);
        sqlSessionFactory=new SqlSessionFactoryBuilder().build(inputStream);

    }

    @Test
    public void testGetUserById() throws Exception {
        SqlSession sqlsession = sqlSessionFactory.openSession();
        //创建 UserMapper对象,mybatis自动生成mapper代理对象
        UserDAO dao=sqlsession.getMapper(UserDAO.class);
        User user =dao.getUserById(2);
        System.out.println(user);
        sqlsession.close();
    }

    @Test
    public void testListUserByName() throws Exception {
        SqlSession sqlsession = sqlSessionFactory.openSession();
        //创建 UserMapper对象,mybatis自动生成mapper代理对象
        UserDAO dao=sqlsession.getMapper(UserDAO.class);
        List<User> users =dao.listUserByName("abc");
        System.out.println(users);
        sqlsession.close();
    }

    @Test
    public void testInsertUser() throws Exception {
        SqlSession sqlsession = sqlSessionFactory.openSession();
        //创建 UserMapper对象,mybatis自动生成mapper代理对象
        UserDAO dao=sqlsession.getMapper(UserDAO.class);
        User user = new User();
        user.setBirthday(new Date());
        user.setAddress("china");
        user.setSex("male");
        user.setUsername("xiaoming");
        dao.insertUser(user);
        sqlsession.commit();
        sqlsession.close();
    }

    @Test
    public void testDeleteUser() throws Exception {
        SqlSession sqlsession = sqlSessionFactory.openSession();
        //创建 UserMapper对象,mybatis自动生成mapper代理对象
        UserDAO dao=sqlsession.getMapper(UserDAO.class);
        dao.deleteUser(12);
        sqlsession.commit();
        sqlsession.close();
    }

    @Test
    public void testUpdateUser() throws Exception {
        SqlSession sqlsession = sqlSessionFactory.openSession();
        //创建 UserMapper对象,mybatis自动生成mapper代理对象
        UserDAO dao=sqlsession.getMapper(UserDAO.class);
        User user = new User();
        user.setBirthday(new Date());
        user.setAddress("china");
        user.setSex("male");
        user.setUsername("xiaoming");
        user.setId(11);
        dao.updateUser(user);
        sqlsession.commit();
        sqlsession.close();
    }

}

顺时针打印矩阵

题目描述

输入一个矩阵,按照从外向里以顺时针的顺序依次打印出每一个数字,例如,如果输入如下矩阵: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.

思路

一圈一圈地打印,特别要注意边界条件

代码

import java.util.*;
public class Solution {
       public ArrayList<Integer> printMatrix(int [][] matrix) {
        if(matrix==null||matrix.length==0||matrix[0].length==0){
            return null;
        }
        ArrayList<Integer> result = new ArrayList<>();
        int row=matrix.length;
        int col=matrix[0].length;
        int loopCount=(Math.min(row,col)+1)/2;
        for(int i=0;i<loopCount;i++){
            //向右 j为列
            for(int j=0+i;j<col-i;j++){
                result.add(matrix[i][j]);
            }
            //向下 j为行
            for(int j=0+i+1;j<row-i-1;j++){
                result.add(matrix[j][col-i-1]);
            }
            //向左 j为列
            for(int j=col-i-1;row-i-1>=(row+1)/2&&j>=i;j--){
                result.add(matrix[row-i-1][j]);
            }
            //向上 j为行
            for(int j=row-i-2;i<(col/2)&&j>=(i+1);j--){
                result.add(matrix[j][i]);
            }
        }
        return result;
    }
}

二叉树中和为某一值的路径

题目描述

输入一颗二叉树和一个整数,打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。

思路

递归输出

代码

import java.util.*;
/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        LinkedList<Integer>path = new LinkedList<>();
        FindPath(root,target,0,path,result);
        return result;
    }
    public void FindPath(TreeNode root,int target,int curSum,LinkedList<Integer>path,ArrayList<ArrayList<Integer>> result){
        if(root==null)return;
        boolean isLeaf=(root.left==null&&root.right==null);
        path.addLast(root.val);
        if(isLeaf&&curSum+root.val==target){
            //得到一条符合的路径
            ArrayList<Integer> onePath=new ArrayList<>();
            for(Integer i:path){
                onePath.add(i);
            }
            result.add(onePath);
        }

        if(root.left!=null){
            FindPath(root.left,target,curSum+root.val,path,result);
        }

        if(root.right!=null){
            FindPath(root.right,target,curSum+root.val,path,result);
        }

        path.removeLast();
    }
}

栈的压入、弹出序列

题目描述

输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序,序列4,5,3,2,1是该压栈序列对应的一个弹出序列,但4,3,5,1,2就不可能是该压栈序列的弹出序列。(注意:这两个序列的长度是相等的)

思路

代码

import java.util.*;

public class Solution {
    public boolean IsPopOrder(int [] pushA,int [] popA) {
        if(pushA==null||popA==null)return false;
        if(pushA.length!=popA.length)return false;
        int pushIndex=0;
        int popIndex=0;
        LinkedList<Integer> s = new LinkedList<>();
        while(pushIndex<pushA.length){
            s.addLast(pushA[pushIndex++]);
            while(popIndex<popA.length&&s.getLast()==popA[popIndex]){
                s.removeLast();
                popIndex++;
            }
        }
        return s.isEmpty();
    }
}

包含min函数的栈

题目描述

定义栈的数据结构,请在该类型中实现一个能够得到栈最小元素的min函数。

思路

使用一个辅助栈来存储当前最小值,即可实现o(1)的查询最小值操作

代码

import java.util.*;

public class Solution {

    private LinkedList<Integer> s1 = new LinkedList<>();
    private LinkedList<Integer> s2 = new LinkedList<>();
    public void push(int node) {
        s1.add(node);
        if(s2.isEmpty()){
            s2.addLast(node);
        }else {
            s2.addLast(s2.getLast()<node?s2.getLast():node);
        }
    }

    public void pop() {
        s1.removeLast();
        s2.removeLast();
    }

    public int top() {
        return s1.getLast();
    }

    public int min() {
        return s2.getLast();
    }
}

二叉树的镜像

题目描述

操作给定的二叉树,将其变换为源二叉树的镜像。
输入描述:
二叉树的镜像定义:源二叉树
8
/ \
6 10
/ \ / \
5 7 9 11
镜像二叉树
8
/ \
10 6
/ \ / \
11 9 7 5

思路

递归交换左右子树

代码

/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    public void Mirror(TreeNode root) {
        if(root==null)return;
        TreeNode t=root.left;
        root.left=root.right;
        root.right=t;
        Mirror(root.left);
        Mirror(root.right);
    }
}

树的子结构

题目描述

输入两棵二叉树A,B,判断B是不是A的子结构。(ps:我们约定空树不是任意一个树的子结构)

思路

递归枚举tree1的接点
再判断tree2是不是tree1的子树(也是递归)

代码

/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    public boolean HasSubtree(TreeNode root1, TreeNode root2) {
        boolean result=false;
        if(root1!=null&&root2!=null){
            result=isTree1HasTree2(root1,root2);
            if(!result){
                result=HasSubtree(root1.left,root2);
            }
            if(!result){
                result=HasSubtree(root1.right,root2);
            }
        }
        return result;
    }
    public boolean isTree1HasTree2(TreeNode root1, TreeNode root2){
        if(root2==null){
            return true;
        }
        if(root1==null){
            return false;
        }
        if(root1.val!=root2.val){
            return false;
        }
        return isTree1HasTree2(root1.left,root2.left)&&isTree1HasTree2(root1.right,root2.right);
    }
}