剑指offer笔记Java（4）

发表于 | 分类于 ，

从1到n整数中1出现的次数

题目描述

输入一个整数n，求从1到n这n个整数的十进制表示中1出现的次数。例如输入12，从1到12这些整数中包含1的数字有1,10,11和12，1一共出现了5次。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Solution {
    public int NumberOf1Between1AndN_Solution(int n) {
        int number = 0;
        for (int i = 1; i <= n; i++) {
            number += NumberOf1(i);
        }
        return number;
    }
    public int NumberOf1(int i) {
        int number = 0;
        while(i>0) {
            if (i%10 == 1)
                number++;
            i = i / 10;
        }
        return number;
    }
}

把数组排成最小的数

题目描述

输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。

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
import java.util.ArrayList;
//import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
public class Solution {
    public String PrintMinNumber(int [] numbers) {
        if(numbers == null || numbers.length < 1) {
            return "";
        }
        ArrayList<String> list = new ArrayList<String>();
        int length = numbers.length;
        for(int i=0; i<length; i++) {
            list.add(String.valueOf(numbers[i]));
        }
        Collections.sort(list, new Comparator<String>() {
 
            @Override
            public int compare(String o1, String o2) {
                String result1 = o1 + o2;
                String result2 = o2 + o1;
                return result1.compareTo(result2);
            }
        });
        StringBuffer buf = new StringBuffer();
        for(int i=0; i<length; i++) {
            buf.append(list.get(i));
        }
        return buf.toString();
    }
}

注意事项

重写使用的是Collection.sort，它和Arrays.sort的区别是什么。

丑数

题目描述

把只包含因子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
public class Solution {
    public int GetUglyNumber_Solution(int index) {
        if (index == 1) return 1;
        if (index == 0) return 0;
        int [] ugly = new int [index];
        int a = 0,b = 0,c = 0;
        ugly[0] = 1;
        for (int i = 1; i < index; i++) {
            while(ugly[a]*2 <= ugly[i-1]) {a++;}//去除重复的候选人，比如6,6,10的情况，更新6之后还要在更新一次6
            while(ugly[b]*3 <= ugly[i-1]) {b++;}
            while(ugly[c]*5 <= ugly[i-1]) {c++;}
            if(minnum(ugly[a]*2,ugly[b]*3,ugly[c]*5)==1){
                ugly[i] = ugly[a]*2;
                a++;
                continue;
            }
            if(minnum(ugly[a]*2,ugly[b]*3,ugly[c]*5)==2){
                ugly[i] = ugly[b]*3;
                b++;
                continue;
            }
            if(minnum(ugly[a]*2,ugly[b]*3,ugly[c]*5)==3){
                ugly[i] = ugly[c]*5;
                c++;
                continue;
            }
        }
        return ugly[index-1];
    }
    public int minnum (int a,int b,int c) {
        int result = a < b ? a : b;
        result = result < c ? result : c;
        if (result == a)
        return 1;
        if (result == b)
        return 2;
        else
        return 3;
    }
}

注意事项

第一个只出现一次的字符

题目描述

在一个字符串(1<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置

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
import java.util.LinkedHashMap;
import java.util.Map;
public class Solution {
    public int FirstNotRepeatingChar(String str) {
        Map<Character,Integer> map = new LinkedHashMap<>();
        for(int i=0;i<str.length();i++){  //从头开始扫描检查字符是否在哈希表中
            if(map.containsKey(str.charAt(i))){//如果在表中有找到字符，获取该字符的value,同time表示
                int time = map.get(str.charAt(i));
                map.put(str.charAt(i), ++time);//将键值对放进表中，更新出现的次数，即time++，
            }
            else {
                map.put(str.charAt(i), 1);  //若不在哈希表中，就添加表中
            }
        }
        int pos = -1;  
        int i=0;
        for(;i<str.length();i++){ //再次从头开始扫描哈希表，取出来第一个value是1的字符。若不存在就返回-1.
            char c = str.charAt(i);
            if (map.get(c) == 1) {
                return i;
            }
        }
        return pos;
    }
}

注意事项

代码是抄别人的；

注意以下function：

map.containsKey(key);

map.put(key,value);

map.get(key);

数组中的逆序对

题目描述

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007

两个链表的第一个公共结点

题目描述

输入两个链表，找出它们的第一个公共结点。

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
/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        if (pHead1 == null || pHead2 == null) {
            return null;
        }
        int length1 = getLength(pHead1);
        int length2 = getLength(pHead2);
        int dif = length2 > length1 ? length2 - length1 : length1 - length2;
        ListNode longlist = pHead1;
        ListNode shortlist = pHead2;
        if (length1 < length2) {
            longlist = pHead2;
            shortlist = pHead1;
        }
        int i = 0;
        for (; i < dif; i++) {
            longlist = longlist.next;
        }
        while (longlist != null && longlist != shortlist) {
                longlist = longlist.next;
                shortlist = shortlist.next;
        }
        ListNode result = longlist;
        return result;
    }
    private int getLength(ListNode pHead) {
        int count = 0;
        while(pHead != null) {
            count ++;
            pHead = pHead.next;
        }
        return count;
    }
}

注意事项

数字在排序数组中出现的次数

题目描述

统计一个数字在排序数组中出现的次数。

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
public class Solution {
    public int GetNumberOfK(int [] array , int k) {
        if (array == null && array.length == 0) {
            return 0;
        }
        int n = array.length;
        int left = 0,right = n-1;
        int mid,temp;
        int firstk = -1,lastk = -1;
        for(;left <= right;) {
            mid = (left + right) / 2;
            temp = array[mid];
            if (k == array[mid] && (mid == 0 || array[mid - 1] != k)) {
                firstk = mid;
                break;
            }
            else if (k <= temp) {
                right = mid - 1;
            }
            else {
                left = mid + 1;
            }
        }
        left = 0;
        right = n -1;
        for(;left <= right;) {
            mid = (left + right) / 2;
            temp = array[mid];
            if (k == array[mid] && ( mid == n-1 || array[mid + 1] != k) ) {
                lastk = mid;
                break;
            }
            else if (k >= temp) {
                left = mid + 1;
            }
            else {
                right = mid - 1;
            }
        }
        int result = 0;
        if (firstk > -1 && lastk > -1) {
            result = lastk - firstk + 1;
        }
        return result;
    }
}

注意事项

二分，用递归写和用循环写都可以

二叉树的深度

题目描述

输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。

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
/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

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

    }

}
*/
public class Solution {
    public int TreeDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (root.left == null) {
            return TreeDepth (root.right) + 1;
        }
        if (root.right == null) {
            return TreeDepth (root.left) + 1;
        }
        int l = TreeDepth(root.left);
        int r = TreeDepth (root.right);
        return l > r ? (l + 1) : (r + 1);
    }
}

注意事项

二叉树优先考虑递归

平衡二叉树

题目描述

输入一棵二叉树，判断该二叉树是否是平衡二叉树。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Solution {
    private boolean Isbalanced = true;
    public boolean IsBalanced_Solution(TreeNode root) {
        getDepth(root);
        return Isbalanced;
    }
    private int getDepth (TreeNode root) {
        if (!Isbalanced || root == null) return 0;
        int l = getDepth(root.left);
        int r = getDepth(root.right);
        if ((l - r) > 1 || (r - l) > 1) {
            Isbalanced = false;
        }
        return l > r ? (l+1) : (r+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
//num1,num2分别为长度为1的数组。传出参数
//将num1[0],num2[0]设置为返回结果
import java.util.ArrayList;
public class Solution {
    public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
        int temp = FindNum(array);
        int bit = 0;
        while((temp & 1) == 0) {
            temp = temp >> 1;
            bit++;
        }
        ArrayList list1 = new ArrayList();
        ArrayList list2 = new ArrayList();
        for (int i = 0; i < array.length; i++) {
            if(Isbit(array[i],bit)) list1.add(array[i]);
            else list2.add(array[i]);
        }
        num1[0] = FindList(list1);
        num2[0] = FindList(list2);
    }
    private int FindNum (int [] array) {
        int n = array.length;
        int result = 0;
        for(int i = 0; i < n; i++) {
            result ^=  array[i];
        }
        return result;
    }
    private int FindList (ArrayList<Integer> array) {
        int n = array.size();
        int result = 0;
        for(int i = 0; i < n; i++) {
            result ^=  array.get(i);
        }
        return result;
    }
    private boolean Isbit(int num,int n) {
        num = num >> n;
        return ((num & 1) == 0);
    } 
}