testtesttesttest

算法

位

1. 一个整形数组中除了两个数字之外，其他都出现了两次，请找出两个只出现一次的数字

树

1.树的后序排列
2.判断数组是否是 树的后序遍历结果

链表

数组

1.把数组排成最小的数
2.找出数组中重复的超过一般的数字

其他问题

mysql

1：MySQL 的逻辑架构了解吗？

2：谈一谈 MySQL 的读写锁

3：MySQL 的锁策略有什么？

4：数据库死锁如何解决？

5：事务是什么?

6：事务有什么特性？

7：MySQL 的隔离级别有哪些？

8：MVCC 是什么？

9：谈一谈 InnoDB

10：谈一谈 MyISAM

11：谈一谈 Memory

12：查询执行流程是什么？

13：VARCHAR 和 CHAR 的区别？

14：DATETIME 和 TIMESTAMP 的区别？

15：数据类型有哪些优化策略？

16：索引有什么作用？

17：谈一谈 MySQL 的 B-Tree 索引

18：了解 Hash 索引吗？

19：什么是自适应哈希索引？

20 ：什么是空间索引？

21：什么是全文索引？

22：什么是聚簇索引？

23：什么是覆盖索引？

24：你知道哪些索引使用原则？

25：索引失效的情况有哪些？

26：如何定位低效 SQL？

27：SHOW PROFILE 的作用？

28：trace 是干什么的？

29：EXPLAIN 的字段有哪些，具有什么含义？

30：有哪些优化 SQL 的策略？

31：MySQL 主从复制的作用？

32：MySQL 主从复制的步骤？

作者：程序员吴师兄
链接：https://www.zhihu.com/question/452184164/answer/1923347183
来源：知乎
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

解答

树的后序排列

package xuelongjiang.question;

/**
 *
 * 树的后序排列
 * @author xuelongjiang
 */
public class AfterOrderTree {

    public void traverse(BinaryTreeNode node) {
        if (node == null) {
            return ;
        }

        if (node.left != null) {
            traverse(node.left);
            traverse(node.right);
        }
        System.out.print( node.vlaue+ ",");

    }

    public static void main(String[] args) {
        AfterOrderTree afterOrderTree = new AfterOrderTree();

        afterOrderTree.test1();
        afterOrderTree.test2();
        afterOrderTree.test3();
        afterOrderTree.test4();
    }


    /**
     * 完整的二叉树
     *         10
     *     6       14
     *  4    8   12   16
     *
     * 期望输出： 4 8 6 12 16 14 10
     */
    public void test1() {

        BinaryTreeNode node3 = new BinaryTreeNode(4, null, null);
        BinaryTreeNode node5 = new BinaryTreeNode(8, null, null);
        BinaryTreeNode node1 = new BinaryTreeNode(6, node3, node5);

        BinaryTreeNode node4 = new BinaryTreeNode(12, null, null);
        BinaryTreeNode node6 = new BinaryTreeNode(16, null, null);
        BinaryTreeNode node2 = new BinaryTreeNode(14, node4, node6);

        BinaryTreeNode node = new BinaryTreeNode(10, node1, node2);

        System.out.println("test1:");
        traverse(node);
        // 前序输出树
        System.out.println("-------------------");


    }

    // 半完整的二叉树
    // 10,14, 12, 6, 4
    /**
     * 半完整的二叉树
     *         10
     *     6       14
     *  4       12
     *
     * 期望输出： 4 6  12 14 10
     */
    public void test2() {
        BinaryTreeNode node3 = new BinaryTreeNode(4, null, null);
        BinaryTreeNode node4 = new BinaryTreeNode(12, null, null);

        BinaryTreeNode node1 = new BinaryTreeNode(6, node3, null);
        BinaryTreeNode node2 = new BinaryTreeNode(14, node4, null);



        BinaryTreeNode node = new BinaryTreeNode(10, node1, node2);
        System.out.println("test2:");
        traverse(node);
        System.out.println("-------------------");
    }

    //只有根节点
    // 10
    public void test3() {
        System.out.println("test3:");
        BinaryTreeNode node = new BinaryTreeNode(10, null, null);
        traverse(node);
        System.out.println("-------------------");
    }

    //空树
    // null
    public void test4() {
        System.out.println("test4:");
        traverse(null);
        System.out.println("-------------------");
    }


}

一个整形数组中除了两个数字之外，其他都出现了两次，请找出两个只出现一次的数字

package xuelongjiang.question;

import javax.swing.*;

/**
 * 一个整形数组中除了两个数字之外，其他都出现了两次，请找出两个只出现一次的数字
 *
 * @author xuelongjiang
 */
public class ArrayFindOneNumber {


    public Integer[] findNumber(int[] arrays) {
        Integer[] findNum = new Integer[2];
        if (arrays == null || arrays.length == 0) {
            return  findNum;
        }

        int resultORX = arrays[0];
        for (int i = 1; i < arrays.length; i++ ) {
            resultORX = resultORX ^ arrays[i];
        }
        int bitIndex = oneBitIndex(resultORX);

        findNum[0] = 0;
        findNum[1] = 0;
        for (int number : arrays) {

            if (isBit(number, bitIndex)) {
                  findNum[0] = number ^ findNum[0];
            } else {
                findNum[1] = number ^ findNum[1];
            }
        }
        return findNum;
    }

    public int oneBitIndex(int number) {
        int index = 0;
        while ((number & 1) == 0 && index < 32) {
            number >>>=1;
            index++;
        }
        return index;
    }

    public boolean isBit(int number, int oneBitIndex) {
        number = number >>> oneBitIndex;
        return (number & 1) == 1;
    }



    /**
     * 个整形数组中除了一个数字之外，其他都出现了两次
     * @param arrays
     * @return
     */
    public Integer findNumber1(int[] arrays) {
        Integer findNum = null;
        if (arrays == null || arrays.length == 0) {
            return findNum;
        }
        findNum = arrays[0];
        for (int i = 1; i < arrays.length; i++) {
            findNum = findNum ^ arrays[i];
        }
        return findNum;
    }


    public static void main(String[] args) {
        ArrayFindOneNumber findOneNumber = new ArrayFindOneNumber();
        findOneNumber.test1();
        findOneNumber.test2();
        findOneNumber.test3();
        findOneNumber.test4();
    }

    public void test1() {
        int[] arrays  = {1,2,3,4,5,1,2,3,4,5,6,7,6};
        Integer number = findNumber1(arrays);
        System.out.println("test1:"  +  (7 == number));
    }

    public void test2() {
        int[] arrays  = {1,2,3,4,5,1,2,3,4,5,6,7,6, 8};
        Integer[] number = findNumber(arrays);
        System.out.println("test2:"  +  (7 == number[0] && 8 == number[1]));
    }

    public void test3() {
        int[] arrays  = {1,2,3,4,5,1,2,3,4,5,7,0};
        Integer[] number = findNumber(arrays);
        System.out.println("test3:"  +  (7 == number[0] && 0 == number[1]));
    }

    public void test4() {
        int[] arrays  = {};
        Integer[] number = findNumber(arrays);
        System.out.println("test4:"  +  (null == number[0] && null == number[1]));
    }
}

判断数组是否是 树的后序遍历结果

package xuelongjiang.question;

/**
 * 24题
 *
 * 判断数组是否是 树的后序遍历结果
 *
 * @author xuelongjiang
 */
public class ArrayIsTreeAfterOrder {


    public boolean verifyAfterOrder(int[] arrays, int start, int end) {
        if (arrays == null || end < 0 ||  start > end) {
            return false;
        }

        if (start == end) {
            return true;
        }

        int root = arrays[end];
        int i = start;

        // 左序列
        for (; i <= end; i++) {
            if (root < arrays[i]) {
                break;
            }
        }
        //右序列
        int j = i;
        for (; j <= end; j++) {
            if (root > arrays[j]) {
                return false;
            }
        }

        boolean left = true;
        if (i > start) {
            left = verifyAfterOrder(arrays, start, i -1 );
        }

        boolean right = true;
        if (i < end ) {

            right = verifyAfterOrder(arrays, i,end - 1);
        }

        return left && right;
    }

    public static void main(String[] args) {
        ArrayIsTreeAfterOrder arrayIsTreeAfterOrder = new ArrayIsTreeAfterOrder();

        arrayIsTreeAfterOrder.test1();
        arrayIsTreeAfterOrder.test2();
        arrayIsTreeAfterOrder.test3();
    }


    //期望true 整棵树
    public void test1 () {
        int [] arrays = {5, 7, 6, 9, 11, 10, 8};
        System.out.println("test1:" +  verifyAfterOrder(arrays, 0, 6));
    }

    //期望true 半棵树
    public void test2 () {
        int [] arrays = {5, 7, 6, 10, 8};
        System.out.println("test2:" +  verifyAfterOrder(arrays, 0, 4));
    }

    //期望false
    public void test3 () {
        int [] arrays = {5, 9, 6, 7, 11, 10, 8};
        System.out.println("test3:" +  verifyAfterOrder(arrays, 0, 6));
    }



}

把数组排成最小的数

package xuelongjiang.question;

import java.util.Arrays;
import java.util.Comparator;

/**
 * 把数组排成最小的数
 * @author xuelongjiang
 */
public class ArrayMinNumber {


    public String printMinNumber(int[] numbers) {
        if (numbers == null || numbers.length == 0) {
            return "";
        }
        String[] strArray = new String[numbers.length];
        for (int i = 0; i < numbers.length; i++) {
            strArray[i] = String.valueOf(numbers[i]);
        }
        Arrays.sort(strArray, new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                return (o1 + o2).compareTo(o2 + o1);
            }
        });

        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < strArray.length; i++) {
            stringBuilder.append(strArray[i]);
        }
        return stringBuilder.toString();
    }


    public static void main(String[] args) {
        ArrayMinNumber arrayMinNumber = new ArrayMinNumber();

        arrayMinNumber.test1();
        arrayMinNumber.test2();
        arrayMinNumber.test3();
        arrayMinNumber.test4();

    }

    public void test1() {
        int [] numbers = {3, 321, 32};
        String result = printMinNumber(numbers);
        System.out.println("test1:" + result + result.equals("321323"));
    }

    public void test2() {
        int [] numbers = {};
        String result = printMinNumber(numbers);
        System.out.println("test2:" + result + result.equals(""));
    }

    public void test3() {
        int [] numbers = {1, 0, 11};
        String result = printMinNumber(numbers);
        System.out.println("test3:" + result + result.equals("0111"));
    }

    public void test4() {
        int [] numbers = {456,36, 32};
        String result = printMinNumber(numbers);
        System.out.println("test4:" + result + result.equals("3236456"));
    }

}

找出数组中重复的超过一般的数字

package xuelongjiang.question;

/**
 * 找出数组中重复的超过一般的数字
 * @author xuelongjiang
 */
public class ArrayMoreThanHalf {

    public int moreThanHalf(int[] array) {
        if (array == null || array.length == 0) {
            return -1;
        }

        int number = array[0];
        int times = 1;
        for (int i = 1; i < array.length; i++) {
            if (array[i] == number) {
                times = times + 1;
            } else if(times > 0){
                times = times - 1;
            } else {
                times = 1;
                number = array[i];
            }
        }
        if (isHalf(array, number)){
            return number;
        }
        return -1;
    }

    public boolean isHalf(int[] array, int number)  {
        int times = 0;
        for (int i = 0; i < array.length; i++) {
            if (array[i] == number) {
                times = times + 1;
            }
        }
        boolean isHalf = true;
        if (times*2 < array.length) {
            isHalf = false;
        }
        return isHalf;
    }


    public static void main(String[] args) {
        ArrayMoreThanHalf thanHalf = new ArrayMoreThanHalf();

        thanHalf.test1();
        thanHalf.test2();
        thanHalf.test3();
        thanHalf.test4();
    }

    public void test1() {
        int[] array = {1, 2, 3, 2, 2, 2, 5, 4, 2 };
        System.out.println("tets1:" + moreThanHalf(array));

    }

    public void test2() {
        int[] array = null;
        System.out.println("tets2:" + moreThanHalf(array));
    }

    public void test3() {
        int[] array = {};
        System.out.println("tets3:" + moreThanHalf(array));
    }

    public void test4() {
        int[] array = {1};
        System.out.println("tets4:" + moreThanHalf(array));
    }


}