2017-09-04

WordBreak

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words. You may assume the dictionary does not contain duplicate words.

For example, given
s = "leetcode",
dict = ["leet", "code"].

Return true because "leetcode" can be segmented as "leet code".

这道题的思路是这样的，首先设置一个比字符串长一的数组，这个数组里面多的那个一就是存放空格的位置
假设我们空格在某个位置，然后这个数组的空格前一个位置表示空格之前的数组是字典里面的内容，然后
空格后面的字串被包含在字典里那么就说明在这个字串就是字典里面的内容

这道题说白了也是一个动态规划的问题，这类问题的思想就是存储上一步骤的东西，然后根据上一步骤的东西推算出下一步骤的结论
这里的存储的上一步骤的东西就是那个布尔数组，然后根据递推公式也就是 if 判断里面的东西得出本步骤的结论

import java.util.List;

public class WordBreak {
    public boolean wordBreak(String s, List<String> wordDict) {
        if (s.length() == 0) {
            return true;
        }
        boolean[] res = new boolean[s.length() + 1];
        res[0] = true;
        for (int i = 0; i < s.length(); i++) {
            StringBuilder stringBuilder = new StringBuilder(s.substring(0, i + 1));
            for (int j = 0; j <= i; j++) {
                if (res[j] && wordDict.contains(stringBuilder.toString())) {
                    res[i + 1] = true;
                    break;
                }
                stringBuilder.deleteCharAt(0);
            }
        }
        return res[s.length()];
    }
}

2017-09-03

-LeetCode

BinaryTreeLevelOrderTraversal树的层序遍历

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).

For example:
Given binary tree [3,9,20,null,null,15,7],
    3
   / \
  9  20
    /  \
   15   7
return its level order traversal as:
[
  [3],
  [9,20],
  [15,7]
]

基本思想就是每一次遍历的时候看当前的层数是不是大于已有的 list 集合数，不大于则需要拓展
否则就把获取当前层的 list 集合，然后王进放元素即可。这里需要注意的就是在这个种递归问题中
我们最重要的是考虑当前的问题，而不要考虑到下一层，否则会越来越乱。

import org.junit.jupiter.api.Test;

import java.util.ArrayList;
import java.util.List;

public class BinaryTreeLevelOrderTraversal {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result=new ArrayList<>();

        levelOrder(root,result,0);

        return result;
    }

    private void levelOrder(TreeNode root, List<List<Integer>> result, int level){
        if (root==null){
            return;
        }
        if (level>result.size()-1){
            result.add(new ArrayList<>());
        }
        List<Integer> list=result.get(level);
        if (root!=null){
            list.add(root.val);
        }
        levelOrder(root.left,result,level+1);
        levelOrder(root.right,result,level+1);
    }

}

2017-09-03

-LeetCode

SymmetricTree

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

1
/ \
2   2
/ \ / \
3  4 4  3
But the following [1,2,2,null,3,null,3] is not:
1
/ \
2   2
\   \
3    3

错误的解法，就是遇到多个 null 值的时候就会出问题，也就是在有的时候虽然他不对称，
但是终须遍历的结果表明他就是对称的

import org.junit.jupiter.api.Test;

import java.util.ArrayList;
import java.util.List;

public class SymmetricTree {
    public boolean isSymmetric(TreeNode root) {
        List<TreeNode> list = new ArrayList<>();
        inOrderTraversal(root, list);
        int center = list.size() / 2;
        return compare(list, center);
    }

    public boolean compare(List<TreeNode> list, int center) {
        for (int i = 0, j = list.size() - 1; i < center; i++, j--) {
            if (list.get(i).val != list.get(j).val) {
                return false;
            }
        }
        return true;
    }

    public void inOrderTraversal(TreeNode root, List<TreeNode> list) {
        if (root == null) {
            return;
        }
        inOrderTraversal(root.left, list);
        list.add(root);
        inOrderTraversal(root.right, list);
    }

    @Test
    void test() {

    }
}

好的解法就是使用递归，所谓对称简单来说就是 root 的左孩子和右孩子要一样才行

2017-09-02

ValidateBinarySearchTree

import org.junit.jupiter.api.Test;
import org.omg.CORBA.INTERNAL;

   Given a binary tree, determine if it is a valid binary search tree (BST).

     Assume a BST is defined as follows:

     The left subtree of a node contains only nodes with keys less than the node's key.
     The right subtree of a node contains only nodes with keys greater than the node's key.
     Both the left and right subtrees must also be binary search trees.
     Example 1:
     2
     / \
     1   3
     Binary tree [2,1,3], return true.
     Example 2:
     1
     / \
     2   3
     Binary tree [1,2,3], return false.

错误解法，只判断了每一个小的子树是搜索二叉树，而忽略了整个 root 的情况

public class ValidateBinarySearchTree {

    public boolean isValidBST(TreeNode root) {
        if (root==null){
            return true;
        }
        if (root.left==null&&root.right==null){
            return true;
        }
        int leftValue=(root.left==null)?Integer.MIN_VALUE:root.left.val;
        int rightValue=(root.right==null)? Integer.MAX_VALUE:root.right.val;
        if(leftValue<root.val&&rightValue>root.val){
            return isValidBST(root.left)&&isValidBST(root.right);
        }
        return false;
    }

    @Test
    void test(){
        TreeNode root=new TreeNode(0);
        TreeNode left=new TreeNode(-1);
        TreeNode right=new TreeNode(3);
        root.left=left;
        // root.right=right;
        System.out.println(isValidBST(root));
    }
}

通过的代码就是使用的搜索二叉树的中序遍历，他的终须遍历的话刚好出来结果就是
左边的树必须小于右边的数，这样就能很轻松的判断出来是否合法

public class ValidateBinarySearchTree {

    public boolean isValidBST(TreeNode root) {
        if (root==null){
            return true;
        }
        if (root.left==null&&root.right==null){
            return true;
        }
        List<TreeNode> list=new ArrayList<>();
        inOrderTraversal(root,list);
        for (int i = 1; i < list.size(); i++) {
            if (list.get(i).val <= list.get(i - 1).val){
                return false;
            }
        }
        return true;
    }

    public void inOrderTraversal(TreeNode root,List<TreeNode> list){
        if (root==null){
            return ;
        }
        inOrderTraversal(root.left,list);
        list.add(root);
        inOrderTraversal(root.right,list);
    }

    @Test
    void test(){
        TreeNode root=new TreeNode(0);
        TreeNode left=new TreeNode(-1);
        TreeNode right=new TreeNode(3);
        root.left=left;
        // root.right=right;
        System.out.println(isValidBST(root));
    }
}

以及终须遍历衍生出来的新方法，也就是不使用一个 list 集合来存储前后之间的关系

class ValidateBinarySearchTree2 {

    TreeNode pre=null;
    public boolean isValidBST(TreeNode root) {
        //这是一个中序遍历。然后我们在每次遍历的时候都存储了前一个元素，避免了使用一个 list 集合
        if (root!=null){
            //首先遍历左子树，左子树出问题直接 false
            if (!isValidBST(root.left)){
                return false;
            }
            //核心判断条件，是不是前面的数大于后面的数
            if (pre!=null&&pre.val>=root.val){
                return false;
            }
            //最后就是右子树，右子树由于是最后一道所以可以直接返回他的结果
            return isValidBST(root.right);
        }
        return true;
    }


    @Test
    void test(){
        TreeNode root=new TreeNode(0);
        TreeNode left=new TreeNode(-1);
        TreeNode right=new TreeNode(3);
        root.left=left;
        // root.right=right;
        System.out.println(isValidBST(root));
    }
}

2017-09-02

-LeetCode

UniqueBinarySearchTreesII

import org.junit.jupiter.api.Test;

题目的描述如下

 * Given n, how many structurally unique BST's (binary search trees) that store values 1...n?

     For example,
     Given n = 3, there are a total of 5 unique BST's.

     1         3     3      2      1
     \       /     /      / \      \
     3     2     1      1   3      2
     /     /       \                 \
     2     1         2                 3

也就是让生成搜索二叉树的所有可能情况，用一种遍历方式放在 list 集合中展示出来

这个地方的基本思路就是把这个问题分解成子问题，也就是先找出一个 root 节点，然后分别对左右的子树进行同样的查找操作，
这里的代码比较巧妙的一点就是他一开始存放的并不是已经遍历过的树，而是只存放了这个根结点，根结点的左右子树都放在了根结点的
内部了，所以最后才会有一个双重循环说白了就是循环的是当选这个 root 节点的时候左右子树的所有情况

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

public class UniqueBinarySearchTreesII {
    public List<TreeNode> generateTrees(int n) {
        if (n < 1) {
            return new ArrayList<TreeNode>();
        }
        return generate(1, n);
    }

    public List<TreeNode> generate(int start, int end) {
        List<TreeNode> lists = new ArrayList<>();
        if (start > end) {
            lists.add(null);
            return lists;
        }
        for (int i = start; i <= end; i++) {
            List<TreeNode> leftTree = generate(start, i - 1); //里面的存储结构其实就是只存了一个子树的 root 节点然后，root 节点里面带的有左右子节点的关系
            List<TreeNode> rightTree = generate(i+1, end);
            for (TreeNode leftNode : leftTree) {
                for (TreeNode rightNode : rightTree) {
                    TreeNode root = new TreeNode(i);
                    root.left = leftNode;
                    root.right = rightNode;
                    lists.add(root);
                }
            }
        }
        return lists;
    }

    @Test
    void fun() {
        // generateTrees(3);
        System.out.println(Arrays.toString(generateTrees(3).toArray()));
    }
}

2017-09-01

-LeetCode

卡塔兰数列[UniqueBinarySearchTrees]

Given n, how many structurally unique BST’s (binary search trees) that store values 1…n?

For example,
Given n = 3, there are a total of 5 unique BST’s.


   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

这道题实际上是 Catalan Number卡塔兰数的一个例子，我们先来看当 n = 1的情况，只能形成唯一的一棵二叉搜索树，n分别为1,2,3的情况如下所示：

                    1                        n = 1

                2        1                   n = 2
               /          \
              1            2

   1         3     3      2      1           n = 3
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

就跟斐波那契数列一样，我们把n = 0 时赋为1，因为空树也算一种二叉搜索树，那么n = 1时的情况可以看做是其左子树个数乘以右子树的个数，左右字数都是空树，所以1乘1还是1。那么n = 2时，由于1和2都可以为跟，分别算出来，再把它们加起来即可。n = 2的情况可由下面式子算出：

dp[2] = dp[0] * dp[1]　　　(1为根的情况)

　　　　+ dp[1] * dp[0]　　 (2为根的情况)

同理可写出 n = 3 的计算方法：

dp[3] = dp[0] * dp[2]　　　(1为根的情况)

　　　　+ dp[1] * dp[1]　　 (2为根的情况)

　　　 + dp[2] * dp[0]　　 (3为根的情况)

由此可以得出卡塔兰数列的递推式为：

c[0]=1 ; c[n+1] = sum(c[i]*c[n-i])

最后代码实现为：

public class UniqueBinarySearchTrees {
    public int numTrees(int n) {
        int[] dp=new int[n+1];
        dp[0]=dp[1]=1;
        for (int i = 2; i <=n; i++) {
            for (int j = 0; j < i; j++) {
                dp[i]+=dp[j]*dp[i-j-1];
            }
        }
        return dp[n];
    }

    @Test
    void fun(){
        System.out.println(numTrees(3));
    }
}

2017-09-01

-Linux

命令行常用参数

1.命令行中

1.上一条命令的最后一个参数： !$

2.上一条命令的第 n 个参数： !:n

3.上一条命令的名称： !#

4.上一条命令的内容： !!

5.上n条命令的内容： n!!

2.shell 脚本中

1.上一条命令的名称： $0

2.上一条命令的第 n 个参数：$n

3.上一条命令的执行情况： 0 正常退出非0不正常

2017-08-23

-JAVA

三大框架整合

1.整合思想

web 层 -> struts2
service 层 -> Spring
dao 层 -> Hibernate
整合就是两两整合，struts 和 spring 整合，然后 spring 和 hibernate 整合。
struts 和 spring 整合就是 action 需要的 service 直接通过 spring 实例化并且注入到 action 中
spring 和 hibernate 整合就是把 sessionFactory 放在 spring 中管理，然后把 dao 注入到 service 中
Read More

2017-08-23

-JAVA

Spring笔记(三)

1.使用注解实现 aop

配置 xml

<?xml version="1.0" encoding="UTF-8"?>
<beans xmlns="http://www.springframework.org/schema/beans"
       xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
       xmlns:aop="http://www.springframework.org/schema/aop"
       xsi:schemaLocation="http://www.springframework.org/schema/beans http://www.springframework.org/schema/beans/spring-beans.xsd
                            http://www.springframework.org/schema/aop http://www.springframework.org/schema/aop/spring-aop.xsd ">
        <!--开启 aop 操作-->
        <aop:aspectj-autoproxy/>
        <bean id="user" class="aop1.User"/>
        <bean id="improve" class="aop1.Improve"/>

</beans>
```<!--more-->
* 在增强类中注解
```java
package aop1;

import org.springframework.aop.aspectj.MethodInvocationProceedingJoinPoint;
import org.springframework.context.annotation.EnableAspectJAutoProxy;

@Aspect
public class Improve {
    @Before(value="execution(* aop1.User.say(..))")
    public void before_say(){
        System.out.println("before");
    }

    public void after_say(){
        System.out.println("after");
    }

    public void around_say(MethodInvocationProceedingJoinPoint joinPoint) throws Throwable {
        System.out.println("before");
        joinPoint.proceed();
        System.out.println("after");
    }
}

2.JdbcTemplate

1.增

//配置 dataSource
        DriverManagerDataSource dataSource=new DriverManagerDataSource();
        dataSource.setDriverClassName("com.mysql.jdbc.Driver");
        dataSource.setUrl("jdbc:mysql:///JAVA");
        dataSource.setUsername("root");
        dataSource.setPassword("12345678");
        //设置模板
        JdbcTemplate jdbcTemplate=new JdbcTemplate(dataSource);
        //操作
        String sql="insert into user values(?,?)";
        jdbcTemplate.update(sql,1,"lwen");

2.删

还是 update 操作只是 sql 不一样

3.改

同增加

4.查

类似于 QueryRunner 也是使用接口的实例，不过这里没有准备好的实现类，实现类需要我们自己书写。

1.查询单值

@Test
    void fun2(){
        //配置 dataSource
        DriverManagerDataSource dataSource=new DriverManagerDataSource();
        dataSource.setDriverClassName("com.mysql.jdbc.Driver");
        dataSource.setUrl("jdbc:mysql:///JAVA");
        dataSource.setUsername("root");
        dataSource.setPassword("12345678");
        //设置模板
        JdbcTemplate jdbcTemplate=new JdbcTemplate(dataSource);
        //操作
        String sql="select count(*) from user";
        Object object=jdbcTemplate.queryForObject(sql,Integer.class);
        System.out.println(object);
    }


    class MyRowMapper implements RowMapper{

        public Object mapRow(ResultSet resultSet, int i) throws SQLException {
            User user=new User();
            user.setId(resultSet.getInt("id"));
            user.setName(resultSet.getString("name"));
            return user;
        }
    }

    @Test
    void fun3(){
        //配置 dataSource
        DriverManagerDataSource dataSource=new DriverManagerDataSource();
        dataSource.setDriverClassName("com.mysql.jdbc.Driver");
        dataSource.setUrl("jdbc:mysql:///JAVA");
        dataSource.setUsername("root");
        dataSource.setPassword("12345678");
        //设置模板
        JdbcTemplate jdbcTemplate=new JdbcTemplate(dataSource);
        //操作
        String sql="select * from user where name=?";
        Object object=jdbcTemplate.queryForObject(sql, new MyRowMapper(),"lwen");
        System.out.println(object);
    }

2.多值查询

class MyRowMapper1 implements RowMapper{

        public Object mapRow(ResultSet resultSet, int i) throws SQLException {
            User user=new User();
            user.setId(resultSet.getInt("id"));
            user.setName(resultSet.getString("name"));
            return user;
        }
    }
    @Test
    void fun4(){
        //配置 dataSource
        DriverManagerDataSource dataSource=new DriverManagerDataSource();
        dataSource.setDriverClassName("com.mysql.jdbc.Driver");
        dataSource.setUrl("jdbc:mysql:///JAVA");
        dataSource.setUsername("root");
        dataSource.setPassword("12345678");
        //设置模板
        JdbcTemplate jdbcTemplate=new JdbcTemplate(dataSource);
        //操作
        String sql="select * from user";
        List<User> users=jdbcTemplate.query(sql,new MyRowMapper1());
        System.out.println(users);
    }

2.事务管理

1.xml方式配置

<?xml version="1.0" encoding="UTF-8"?>
<beans xmlns="http://www.springframework.org/schema/beans"
       xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
       xmlns:tx="http://www.springframework.org/schema/tx"
       xmlns:aop="http://www.springframework.org/schema/aop"
       xsi:schemaLocation="http://www.springframework.org/schema/beans http://www.springframework.org/schema/beans/spring-beans.xsd
                            http://www.springframework.org/schema/tx http://www.springframework.org/schema/tx/spring-tx.xsd
                            http://www.springframework.org/schema/aop http://www.springframework.org/schema/aop/spring-aop.xsd ">
    <!--jdbcTemplate-->
    <bean id="jdbc" class="org.springframework.jdbc.core.JdbcTemplate">
        <property name="dataSource" ref="dataSource"/>
    </bean>
    <!--配置事务管理器-->
    <bean id="txManager" class="org.springframework.jdbc.datasource.DataSourceTransactionManager">
        <!--注入 dataSource-->
        <property name="dataSource" ref="dataSource"/>
    </bean>
    <!--配置事务的增强-->
    <tx:advice id="txAdvice" transaction-manager="txManager">
        <tx:attributes>
            <tx:method name="add"/>
        </tx:attributes>
    </tx:advice>
    <!--配置切面-->
    <aop:config>
        <!--切入点-->
        <aop:pointcut id="point1" expression="execution(* com.lwen.Service.add(..))"/>
        <!--切面-->
        <aop:advisor advice-ref="txAdvice" pointcut-ref="point1"/>
    </aop:config>
</beans>

2.注解方式

开启注解

1 2	<!-- 开启注解 --> <tx:annotation-driven transaction-manager="transactionManager"/>

在事务类上面写注解
@Transactional

2017-08-23

-JAVA

Spring笔记(二)

1.注解ioc

1.开启注解扫描

<?xml version="1.0" encoding="UTF-8"?>
<beans xmlns="http://www.springframework.org/schema/beans"
       xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
       xmlns:context="http://www.springframework.org/schema/context"
       xsi:schemaLocation="http://www.springframework.org/schema/beans http://www.springframework.org/schema/beans/spring-beans.xsd
        http://www.springframework.org/schema/context http://www.springframework.org/schema/context/spring-context.xsd">
    <!--开启注解扫描-->
    <context:component-scan base-package="domain1"/>
</beans>

1.命令行中

1.上一条命令的最后一个参数 ： !$

2.上一条命令的第 n 个参数 ： !:n

3.上一条命令的名称 ： !#

4.上一条命令的内容 ： !!

5.上n条命令的内容 ： n!!

2.shell 脚本中

1.上一条命令的名称 ： $0

2.上一条命令的第 n 个参数 ：$n

3.上一条命令的执行情况 ： 0 正常退出 非0不正常

1.整合思想

1.使用注解实现 aop

2.JdbcTemplate

1.增

2.删

3.改

4.查

1.查询单值

2.多值查询

2.事务管理

1.xml方式配置

2.注解方式

1.注解ioc

1.开启注解扫描

1.上一条命令的最后一个参数： !$

2.上一条命令的第 n 个参数： !:n

3.上一条命令的名称： !#

4.上一条命令的内容： !!

5.上n条命令的内容： n!!

1.上一条命令的名称： $0

2.上一条命令的第 n 个参数：$n

3.上一条命令的执行情况： 0 正常退出非0不正常