剑指offer笔记Java（2）

发表于 | 分类于 ，

二进制中1的个数

本题知识点：位运算

题目描述

输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。

1
2
3
4
5
6
7
8
9
10
public class Solution {
    public int NumberOf1(int n) {
       int sum = 0;  
       while(n != 0){  
           sum++;  
           n = n & (n - 1);  
       }  
       return sum;  
    }
}

注意事项

一个数减一并且和自己位与，得到的结果是原来的数字将最右边的1变为0后的结果。

但是负数是否为这样我不确定，这里存疑：一个用补码表示的负数减一再与运算，得到的是补码形式的最右边1变0还是原码形式的最右边1变0。

位运算的算法背下来就好，Java位运算的知识粘在下面：

Java提供的位运算符有：左移( << )、右移( >> ) 、无符号右移( >>> ) 、位与( & ) 、位或( | )、位非( ~ )、位异或( ^ )，除了位非( ~ )是一元操作符外，其它的都是二元操作符。

Java 位运算(移位、位与、或、异或、非）

数值的整数次方

本题知识点： 代码完整性

题目描述

给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Solution {
    public double Power(double base, int exponent) {
        if (exponent == 0) {
            return 1;
        }
        if (exponent == 1) {
            return base;
        }
        if (exponent < 0) {
            return 1 / Power(base,- exponent);
        }
        double result = Power(base,exponent >> 1);
        result *= result;
        if ((exponent & 0x1) == 1) {//判断是否为奇数
            result *= base;
        }
        return result;
  }
}

注意事项

java里面比较浮点数与0是否相等，本题使用的是 ==应该有其他的function可以满足不同精度的要求，因为浮点数比较相等方法是判断二者的差是否在一定范围内。

本题要依次判断指数是否为0，指数是否为负数，以及指数是否为正奇数。

使用位运算的右移代替除以2 的运算，使用与0x1位与来判断是否为奇数（与0x1位与是判断最后一位是否为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
42
43
44
public class Solution {
    public void reOrderArray(int [] array) {
        int len = array.length;
        int odd = 0;
        int even = 0;
        int index1 = 0;
        int index2 = -1;
        int temp;
        int i;
        for (i = 0; i < len; i++) { // 找到第一个偶数
            if ((array[i] & 0x1) != 1) {
                even = i;
                break;
            }
        }
        index1 = even; // 序号1为第一个偶数的坐标
        for (i = even + 1; i < len; i++) {
            if ((array[i] & 0x1) == 1) {
                index2 = i; // 序号2为第一个偶数后面第一个奇数的坐标 这样坐标2前就是已经排序好的数组
                break;
            }
            if (i == len - 1) {
                index2 = -1; // 如果找不到第一个偶数后面的奇数，就说明排序好了
            }
        }
        while (index2 != -1) {
            temp = array[index2];
            for (i = index2; i > index1; i--) { // 将偶数序列整体后移一位，将序号2的奇数放到偶数序列前
                array[i] = array[i - 1];
            }
            array[index1] = temp;
            index1 ++; // 更新第一个偶数的序号1
            for (i = index2; i < len; i++) {
                if ((array[i] & 0x1) == 1) {
                    index2 = i; // 更新第一个偶数后面第一个奇数的坐标为序号2
                    break;
                }
                if (i == len -1) {
                    index2 = -1; //如果找不到，就说明排序结束
                }
            }
        }
    }
}

注意事项

函数最开始应该放在while(array.length > 0)的循环内，代码忘记加了；

直接使用增加空间复杂度的方法很好写，但是好的解法不应该都是稍微复杂一点么；

本方法的时间复杂度很高，但是要保证相对顺序不变，传统前后两个指针哨兵的方法不可行；

冒泡排序也可以通过，代码也非常简洁。

链表中倒数第k个结点

本题知识点：链表 快慢指针

题目描述

输入一个链表，输出该链表中倒数第k个结点。 

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

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {
        if (head == null) { // 链表空，返回null
            return null;
        }
        if (k == 0) { // 倒数第0个值也是null
            return null;
        }
        int i = 1;
        ListNode right = new ListNode(1);
        ListNode left = new ListNode(1);
        right = head;
        left = head;
        while (right.next != null) {
            right = right.next;
            i++;
            if (i > k) { // right 是第k个的时候，left应该在第1个
                left = left.next;
            }
        }
        if (i < k) {
            return null;
        }
        return left;
    }
}

注意事项

保证代码完整性，链表要考虑空，k要考虑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
31
/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode ReverseList(ListNode head) {
        if (head == null) {
            return null;
        }
        if (head.next == null) {
            return head;
        }
        ListNode index1 = new ListNode(1);
        ListNode index2 = new ListNode(1);
        ListNode temp = new ListNode(1);
        index1 = null; // 序号1是翻转后数组的头结点
        index2 = head; // 序号2是待翻转的节点，也是新的头结点
        while (index2 != null) { //边界条件，序号2为空，无待翻转节点
            temp = index2.next;
            index2.next = index1;
            index1 = index2;
            index2 = temp;
        }
        return index1;
    }
}

注意事项

完整性：head为空，链表长度为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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
/*
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 && list2 == null) {
            return null;
        }
        if (list1 == null) {
            return list2;
        }
        if (list2 == null) {
            return list1;
        }
        ListNode index = new ListNode(0); // 排序好的链表的最后一个节点
        ListNode temp1 = new ListNode(0); // list1的待排序的第一个节点
        ListNode temp2 = new ListNode(0); // list2的待排序的第一个节点
        ListNode head = new ListNode(0); // 排序好的头结点
        if (list1.val <= list2.val) {
            head = list1;
            temp1 = list1.next;
            temp2 = list2;
        }
        else {
            head = list2;
            temp2 = list2.next;
            temp1 = list1;
        }
        index = head;  // 以上是对定义的节点进行赋值
        while (temp1 != null && temp2 != null) { // 排序过程
            if (temp1.val <= temp2.val) {
                index.next = temp1;
                index = index.next;
                temp1 = temp1.next;
            }
            else if (temp2.val < temp1.val) {
                index.next = temp2;
                index = index.next;
                temp2 = temp2.next;
            }
        }
        if (temp1 == null) { // 如果有一个链表排序结束，则不需要再排序了
            index.next = temp2;
        }
        if (temp2 == null) {
            index.next = temp1;
        }
        return head;
    }
}

注意事项

链表依旧是完整性判断：链表为空，只有一个节点等等；

至今不知道怎么new一个空的ListNode对象，每次都要用初始化函数传入一个val值，不然报错。

树的子结构

本题知识点：树 （递归 or循环）

题目描述

输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

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 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) {
        boolean result = false;
        if (root2 == null) {
            return false;
        }
        if (root1 == null) {
            return false;
        }
        if (root1 != null && root2 != null) {
            if (root1.val == root2.val) {
                result = IsEqual(root1,root2);
            }
            if (!result) {
                result = HasSubtree(root1.left,root2);
            }
            if (!result) {
                result = HasSubtree(root1.right,root2);
            }
        }
        return result;
    }
    public boolean IsEqual(TreeNode root1,TreeNode root2) {
        if (root2 == null) {
            return true;
        }
        else if (root1 == null) {
            return false;
        }
        if (root1.val != root2.val) {
            return false;
        }
        else {
            return IsEqual(root1.left,root2.left) && IsEqual(root1.right,root2.right);
        }
    }
}

注意事项

题意中的子结构不是子树，所以就算只要A中的子树的上面部分和B一样就满足题意。而不是子树和B一模一样。如图

示例

其中左边树A是包含右边树B的。

因此在第二个函数递归到最后一级的时候比较到树B的节点为空即可，不需要同时A的节点也是空。这样IsEqual的命名也有些问题，就不改了。

树设计递归操作，一定要写完整，节点为空的情况一定要写清楚，不要造成无限循环。

二叉树的镜像

本题知识点：树

题目描述

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

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
/**
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;
        }
        Mirror(root.left);
        Mirror(root.right);
        TreeNode temp = new TreeNode(0);
        temp = root.left;
        root.left = root.right;
        root.right = temp;
    }
}

注意事项

递归操作要把函数写完整，空的时候要写清楚。

先分别镜像左右子树，再将左右子树交换。

顺时针打印矩阵

本题知识点：数组

题目描述

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下矩阵： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.

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
import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printMatrix(int [][] matrix) {
        if (matrix == null || matrix.length == 0 || (matrix.length == 1 && matrix[0].length == 0)) {
            return null;
        }
        int rows = matrix.length;
        int columns = matrix[0].length;
        ArrayList<Integer> list = new ArrayList<Integer>();
        int start = 0;
        while (columns > start * 2 && rows > start * 2) {
            printCircle(matrix,columns,rows,start,list);
            start++;
        }
        return list;
    }
    public void printCircle(int [][] matrix, int columns, int rows, int start, ArrayList<Integer> list) {
        int endX = columns - 1 - start;
        int endY = rows - 1 - start;
        for (int i = start; i <= endX; i++) {
            int number = matrix[start][i];
            list.add(number);
        }
        if (start < endY) {
            for (int i = start + 1; i <= endY; i++) {
                int number = matrix[i][endX];
                list.add(number);
            }
        }
        if (start < endX && start < endY) {
            for (int i = endX - 1; i >= start; i--) {
                int number = matrix[endY][i];
                list.add(number);
            }
        }
        if (start < endX && start < endY - 1) {
            for (int i = endY - 1; i >= start + 1; i--) {
                int number = matrix[i][start];
                list.add(number);
            }
        }
    }
}

注意事项

二维数组不为空的条件，上篇笔记中写过；

数组千万别越界，边界条件一定写清楚了；

行数rows和列数columns与行的坐标列的坐标正好是相反对应的，一行坐标范围是0到列数减1，一列的坐标范围是0到行数减1。

包含min函数的栈

本题知识点：栈

题目描述

定义栈的数据结构，请在该类型中实现一个能够得到栈最小元素的min函数。

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
import java.util.Stack;

public class Solution {

    public Stack<Integer> data = new Stack<Integer>();
    public Stack<Integer> min = new Stack<Integer>();
    public void push(int node) {
        data.push(node);
        if (min.isEmpty() || node <= min.peek()) {
            min.push(node);
        }
        else {
            min.push(min.peek());
        }
    }
    
    public void pop() {
        if (!data.isEmpty()) {
            data.pop();
            min.pop();
        }
    }
    
    public int top() {
        if (!data.isEmpty()) {
            return data.peek();
        }
        return 0;
    }
    
    public int min() {
        if (!min.isEmpty()) {
            return min.peek();
        }
        return 0;
    }
}

注意事项

栈的操作判断是否为空栈和数组防止越界，链表判断是否空一样重要。

data栈和min栈要同步，push和pop操作时对两个栈要同步更新，这样的好处可以无脑读取min栈顶的值作为最小值，不用担心进栈出栈操作的干扰。

如果栈为空就随便返回一个值。（0或者1我都试过了）