发表于 | 分类于 ，

简述

请用rand1To5实现等概率随机产生1~7的随机函数rand1To7

1
2
3
4
5
6
7
8
9
public class rand1to5 { 
    /* 
     * 给定一个等概率随机产生1~5的随机函数rand1To5如下 public int rand1To5() { return (int) 
     * (Math.random() * 5) + 1; } 除此之外不能使用任何额外的随机机制， 
     * 请用rand1To5实现等概率随机产生1~7的随机函数rand1To7。 
     */ 
    public int rand1To5() { 
        return (int) (Math.random() * 5) + 1; 
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
public int rand1To7() {
    int num = 0;
    do {
        num = 5 * (rand1To5() - 1) + rand1To5() - 1;// 0-24
    } while (num > 20); // 把21 22 23 24 的概率平摊到0-20上
    return num % 7 + 1;
}
// 拓展： 1-m 等概率 转化成 等1-n概率 问题
// 实质就是看 把 m 看成m进制 n<m 则 m进制能装下n
// m>n 扩充成m^2 也就是增加一位 看能不能放下n 以此类推

// 给定一个以p概率产生0，以1-p概率产生1的随机函数rand01p如下：
// 除此之外不能使用任何额外的随机机制，请用rand01p实现等概率随机
// 产生1~6的随机函数rand1To6。
public int rand01p() {
    // you can change p as you like
    double p = 0.83;
    return Math.random() < p ? 0 : 1;
}

public int rand01() {
    int num = 0;
    do {
        num = rand01p();
    } while (num == rand01()); // 01 和 10 产生的概率是相同的 把1看做01 0看做10
    return num == 1 ? 1 : 0;
}

public int rand0To3() {
    return rand01() * 2 + rand01();
}

public int rand1To6() {
    int num = 0;
    do {
        num = rand0To3() * 4 + rand0To3();
    } while (num > 11);
    return num % 6 + 1;

}
// 其实就是一个扩大 补位 然后筛选的过程

发表于 | 分类于 ，

题目描述

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
例如输入前序遍历序列{1,2,4,7,3,5,6,8}和
中序遍历序列{4,7,2,1,5,3,8,6}，
则重建二叉树并返回。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/*
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        TreeNode root = reConstructBinaryTree(pre, 0, pre.length - 1, in ,0, in.length - 1);
        return root;
    }
    
    private TreeNode reConstructBinaryTree(int [] pre,int startPre,int endPre,int [] in,int startIn,int endIn) {
         
        if(startPre > endPre || startIn > endIn)
            return null;
        TreeNode root = new TreeNode(pre[startPre]);
         
        for(int i = startIn; i <= endIn; i++)
            if(in[i] == pre[startPre]) {
                root.left = reConstructBinaryTree(pre, startPre + 1, startPre + i - startIn, in, startIn, i - 1);
                root.right = reConstructBinaryTree(pre, i - startIn+startPre + 1, endPre, in, i + 1, endIn);
            } 
        return root;
    }
}

发表于 | 分类于 ，

题目描述

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public class ListNode {
    int val;
    ListNode next = null;
    ListNode(int val) {
        this.val = val;
    }
}

public class Solution {
    public ListNode merge(ListNode list1,ListNode list2) {
        if(list1 == null){
            return list2;
        }
        if(list2 == null){
            return list1;
        }
        ListNode res = null;
        if(list1.val > list2.val){
           res = list2;
           res.next = merge(list1,list2.next);
        }else{
            res = list1;
            res.next = merge(list1.next,list2);
        }
        return res;
    }
}

发表于 | 分类于 ，

题目描述

输入两颗二叉树A，B，判断B是不是A的子结构。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
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) {
         if(root2 == null){
            return false;
        }
         if(root1 == null ) {
            return false;
        }
        boolean flag = false;
        flag = IsSubtree(root1,root2);
     
        if(!flag){
            flag = HasSubtree(root1.left, root2);
            if(!flag){
                flag = HasSubtree(root1.right, root2);
            }
        }
        return flag;
    }
    private boolean IsSubtree(TreeNode root1,TreeNode root2){
        if(root2 == null){
            return true;
        }
        if(root1 == null ) {
            return false;
        }
        if(root1.val == root2.val){
            return IsSubtree(root1.left, root2.left) &&
                IsSubtree(root1.right, root2.right);
        }
        return false;
    }
}

发表于 | 分类于 ，

题目描述

操作给定的二叉树，将其变换为源二叉树的镜像。

输入描述:

二叉树的镜像定义：源二叉树 

    8
   /  \
  6   10
 / \  / \
5  7 9 11
镜像二叉树
    8
   /  \
  10   6
 / \  / \
11 9 7  5

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

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 temp = root.left;
        root.left = root.right;
        root.right = temp;
        mirror(root.left);
        mirror(root.right);
    }
}

发表于 | 分类于 ，

题目描述

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
import java.util.ArrayList;
import java.util.Stack;


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>> pathList = new ArrayList<ArrayList<Integer>>();
        if(root == null){
            return pathList;
        }
        Stack<Integer> stack = new Stack<Integer>();
        findPath(root, target, stack, pathList);
        return pathList;
    }
    
    private void findPath(TreeNode root, int target, Stack<Integer> path, ArrayList<ArrayList<Integer>> pathList) {
        if(root == null)
            return;
            
        if(root.left == null && root.right == null){
            if(root.val == target){
                ArrayList<Integer> ValList = new ArrayList<Integer>();
                for(int i : path){
                    ValList.add(i);
                }
                ValList.add(root.val);
                pathList.add(ValList);
            }
        } else {
            path.push(new Integer(root.val));
            findPath(root.left, target-root.val, path, pathList);
            findPath(root.right, target-root.val, path,  pathList);
            path.pop();
        }
    }
}

发表于 | 分类于 ，

题目描述

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
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 pRootOfTree) {
       if(pRootOfTree == null){
            return null;
        }
        TreeNode left = Convert(pRootOfTree.left);
        TreeNode p = left;
        while(p != null && p.right != null){
            p = p.right;
        }
        if(left != null){
            p.right = pRootOfTree;
            pRootOfTree.left = p;
        }
        TreeNode right = Convert(pRootOfTree.right);
        p = right;
        while(p != null && p.left != null){
            p = p.left;
        }
        if(right != null){
            right.left = pRootOfTree;
            pRootOfTree.right = right;
        }
        return left != null ? left : pRootOfTree;       
    }
}

发表于 | 分类于 ，

题目描述

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
       // int res = 0;
        if(array == null || array.length == 0){
            return 0;
        }
        int count = 1;
        int temp = array[0];
        for(int i=1; i < array.length; i++){
            if(array[i] == temp){
                count++;
            }else{
                count--;
                if(count < 1){
                    temp = array[i];
                    count = 1;
                }
              //  count--;
            }
        }
        int num=0;
        for(int i = 0 ;i < array.length; i++){
            if(array[i] == temp){
                num++;
            }
        }
        int len = array.length / 2;
        return num > len ? temp : 0;
    }
}

发表于 | 分类于 ，

题目描述

HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。你会不会被他忽悠住？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Solution {

    public int FindGreatestSumOfSubArray(int[] array) {
        if(array == null || array.length == 0){
            return 0;
        }
        int max = Integer.MIN_VALUE;
        int temp = 0;
        for(int i=0; i < array.length; i++){
            temp += array[i];
            max = Math.max(max, temp);
            temp = temp < 0 ? 0 : temp;
        }
        return max;
    }
}

发表于 | 分类于 ，

题目描述

把只包含因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
public class Solution {

    public int GetUglyNumber_Solution(int index) {
        if(index <= 0) {
            return 0;
        }
        if(index <= 5) {
            return index;
        }
        int[] array = new int[index];
        array[0] = 1;
        array[1] = 2;
        array[2] = 3;
        array[3] = 4;
        array[4] = 5;
         
        for(int i = 5;i < index; i++) {
            int min = 0;
            int min2 = 0, min3 = 0, min5 = 0;
            int temp = 0;
            //找到已知的丑数的2倍的数，且该数比已知最大丑数大。
            for(int j = 0; j < i; j++) {
                temp = array[j] * 2;
                if(temp > array[i-1]) {
                    min2 = temp;
                    break;
                }
            }
            //同上，3倍
            for(int j = 0;j < i; j++) {
                temp = array[j] * 3;
                if(temp > array[i-1]) {
                     min3 = temp;	
                     break;
                }
            }
            //同上，5倍
            for(int j = 0; j < i; j++) {
                temp = array[j] * 5;
                if(temp > array[i-1]){ 
                    min5 = temp;
                    break;
                }
            }
            min = Math.min(Math.min(min2, min3), min5);
            array[i] = min;           
        }
        return array[index-1];
    }
}