头条面试题,输出二叉树每一层的第一个元素

package info.weida;

/**
 * @ Author     : viete.
 * @ Date       : Created in 16:06 2018/8/25
 * @ Description: 头条面试题,输出二叉树每一层的第一个元素
 */
class Node {
    char val;
    Node left, right;

    Node(char val) {
        this.left = null;
        this.right = null;
        this.val = val;
    }
}

public class Tree {
    private static char[] a = new char[99];

    private static void fun(Node node) {
        fun(node, 0);
    }

    private static void fun(Node node, int level) {
        if (node == null) return;
        if (a[level] == '\0') {
            a[level] = node.val;
            System.out.println(node.val);
        }
        fun(node.left, level + 1);
        fun(node.right, level + 1);
    }

/*
        A
    B        C
         D      E
       F   G
*/

    public static void main(String[] args) {
        Node A = new Node('A');
        Node B = new Node('B');
        Node C = new Node('C');
        Node D = new Node('D');
        Node E = new Node('E');
        Node F = new Node('F');
        Node G = new Node('G');
        A.left = B;
        A.right = C;
        C.left = D;
        C.right = E;
        D.left = F;
        D.right = G;
        fun(A);
    }

}

mysql之多条件COUNT

SELECT
    platname,
    projetId,
    COUNT(DISTINCT MobileMumber) AS onlyGetNumberCnt,
    COUNT(mobileMumber) AS GetNumberCnt,
    COUNT(
        DISTINCT CASE
        WHEN GetVerifyCodeAt IS NULL THEN
            NULL
        ELSE
            MobileMumber
        END
    ) AS onlyGetVeriCnt,
    COUNT(
        CASE
        WHEN GetVerifyCodeAt IS NULL THEN
            NULL
        ELSE
            MobileMumber
        END
    ) AS GetVerirCnt
FROM
    sms_record
WHERE
    1 = 1
GROUP BY
    platname,
    projetId

6128493130

最长公共子序列

状态转移方程
LCS(x,y) =
(1) LCS(x - 1,y - 1) + 1 如果Ax = By
(2) max(LCS(x – 1, y) , LCS(x, y – 1)) 如果Ax ≠ By
(3) 0 如果x = 0或者y = 0

package info.weida;

/**
 * @ Author     :viete.
 * @ Date       :Created in 11:03 2018/8/15
 * @ Description:
 */
public class DPLCS {
    private int[][] flag;

    public int calcLen(int[] a, int[] b) {
        int[][] dp = new int[a.length + 1][b.length + 1];
        flag = new int[a.length + 1][b.length + 1];

        for (int i = 0; i < a.length; i++)
            dp[i][0] = 0;
        for (int i = 0; i < b.length; i++)
            dp[0][i] = 0;
        for (int i = 1; i <= a.length; i++) {
            for (int j = 1; j <= b.length; j++) {
                if (a[i - 1] == b[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    flag[i][j] = 0;
                } else if (dp[i - 1][j] > dp[i][j - 1]) {
                    dp[i][j] = dp[i - 1][j];
                    flag[i][j] = 1;
                } else {
                    dp[i][j] = dp[i][j - 1];
                    flag[i][j] = -1;
                }
            }
        }
        return dp[a.length][b.length];
    }

    public void print(int[] a, int[] b, int i, int j) {
        if (i == 0 || j == 0) return;
        if (flag[i][j] == 0) {
            print(a, b, i - 1, j - 1);
            System.out.print(a[i - 1] + " ");
        } else if (flag[i][j] == 1) {
            print(a, b, i - 1, j);
        } else {
            print(a, b, i, j - 1);
        }
    }

    public static void main(String[] args) {
        int[] a = {1, 3, 5, 4, 2, 6, 8, 7};
        int[] b = {1, 4, 8, 6, 7, 5};
        DPLCS dplcs = new DPLCS();
        int len = dplcs.calcLen(a, b);
        System.out.println(len);
        dplcs.print(a, b, a.length, b.length);
    }
}

最长公共子串

package info.weida;

/**
 * @ Author     :viete.
 * @ Date       :Created in 11:27 2018/8/15
 * @ Description:
 */
public class DPLCSub {
    public boolean[][] flag;
    public int x, y;

    public int calcLen(char[] a, char[] b) {
        int[][] dp = new int[a.length + 1][b.length + 1];
        flag = new boolean[a.length + 1][b.length + 1];
        for (int i = 0; i < a.length; i++) {
            dp[i][0] = 0;
        }
        for (int i = 0; i < b.length; i++) {
            dp[0][i] = 0;
        }
        int max = -1;
        for (int i = 1; i <= a.length; i++) {
            for (int j = 1; j <= b.length; j++) {
                if (a[i - 1] == b[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    flag[i][j] = true;
                } else {
                    dp[i][j] = 0;
                    flag[i][j] = false;
                }
                if (dp[i][j] > max) {
                    max = dp[i][j];
                    x = i;
                    y = j;
                }
            }
        }
        return max;
/        return dp[a.length][b.length];
    }

    public void print(char[] a, char[] b, int i, int j) {
        if (i == 0 || j == 0) return;
        if (flag[i][j]) {
            print(a, b, i - 1, j - 1);
            System.out.print(a[i - 1]);
        }
    }

    public static void main(String[] args) {
        char a[] = "1234567".toCharArray();
        char b[] = "12345678".toCharArray();

        DPLCSub dplcSub = new DPLCSub();
        int len = dplcSub.calcLen(a, b);
        System.out.println(len);
        dplcSub.print(a, b, dplcSub.x, dplcSub.y);
    }
}

6165501811

使用动态规划特征

  1. 求一个问题的最优解
  2. 大问题可以分解为子问题,子问题还有重叠的更小的子问题
  3. 整体问题最优解取决于子问题的最优解(状态转移方程)
  4. 从上往下分析问题,从下往上解决问题
  5. 讨论底层的边界问题

割绳子

  • 给你一根长度为N的绳子,把绳子剪成M段(m,n都是整数),每段绳子的长度记为k[0],k[1],k[2]…. 请问如何剪绳子使得k[0],k[1],k[2]的乘积最大
  • 例如 绳子长度8 最大乘积18 = 2*3*3
import java.util.Scanner;

/**
 * @ Author     :viete.
 * @ Date       :Created in 21:17 2018/8/14
 * @ Description:
 */
public class DPGeShengZi {
    private static final int MAXN = 50;
    private int[] dp = new int[MAXN];

    private int fun(int n) {
        if (n < 0) return 0;
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 3;
        / 边界
        if (n <= 3) return dp[n];
        for (int m = 4; m <= n; m++) {
            int max = 0;
            for (int i = m / 2 + 1; i > 0; i--) {
                if (dp[i] * dp[m - i] > max)
                    max = dp[i] * dp[m - i];
                / 状态转移方程 f(n) = max{f(i) * f(n - i)} i >= 3
            }
            dp[m] = max;
        }
        return dp[n];
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int rst = new DPGeShengZi().fun(n);
        System.out.println(rst);
    }
}

硬币问题

  • 我们有面值为1元3元5元的硬币若干枚,如何用最少的硬币凑够11元?
package info.weida;

import java.util.Scanner;

/**
 * @ Author     :viete.
 * @ Date       :Created in 21:42 2018/8/14
 * @ Description:
 */
public class DPCoinChange {
    private static final int MAXN = 200;
    int[] dp = new int[MAXN];
    int[] hb = {1, 3, 5};

    private int fun(int n) { /返回n元至少的硬币个数
        dp[0] = 0;
        dp[1] = 1;/1
        dp[2] = 2;/1+1
        dp[3] = 1;/3
        dp[4] = 2;/1+3
        dp[5] = 1;/5
        if(n<0)return 0;
        if(n<=5)return dp[n];
        for (int m = 6; m <= n; m++) {
            / f(n)=min{f(n-vi)}
            int min = Integer.MAX_VALUE;
            for (int i = 0; i < hb.length; i++) {
                if (dp[m - hb[i]] < min) min = dp[m - hb[i]]+1;
            }
            dp[m] = min;
        }
        return dp[n];
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt();
        System.out.println(new DPCoinChange().fun(n));
    }
}

剑指Offer之二叉搜索树的后序遍历序列

输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。

非递归版本 时间复杂度O(n2)

/左子树一定比右子树小,right部分的最后一个数字是右子树的根,他也比左子树所有值大,因此我们可以每次只看有子树是否符合条件即可,即使到达了左子树也可以看出由左右子树组成的树还想右子树那样处理
/对于左子树回到了原问题,对于右子树,左子树的所有值都比右子树的根小可以暂时把他看出右子树的左子树
/只需看看右子树的右子树是否符合要求即可
public class Solution {
    public boolean VerifySquenceOfBST(int [] sequence) {
        if(sequence == null || sequence.length == 0)return false;
        int length = sequence.length - 1;
        while(length > 0){
            int i = 0;
            while(i < length && sequence[i] < sequence[length])i++;
            while(i < length && sequence[i] > sequence[length])i++;
            if(i < length)return false;
            length--;
        }
        return true;
    }
}

递归版本

/分治思想 二叉查找树的特点:左子树<根<=右子树  
public class Solution {
    public boolean VerifySquenceOfBST(int [] sequence) {
        if(sequence.length == 0) return false;
        if(sequence.length == 1) return true;
        return judge(sequence,0,sequence.length-1);
    }
     
    public boolean judge(int[] a,int start,int end){
        if(start >= end){
            return true;
        }
        int i = start;
        while(a[i] < a[end]){
            ++i;
        }
        for(int j=i;j<end;j++){
            if(a[j] < a[end]){
                return false;
            }
        }
        return judge(a,start,i-1) && judge(a,i,end-1);
    }
}