剑指offer笔记Java（3）

发表于 | 分类于 ，

栈的压入、弹出序列

本题知识点：栈

题目描述

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4，5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）

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
mport java.util.ArrayList;

public class Solution {
    public boolean IsPopOrder(int [] pushA,int [] popA) {
        int i = 0;
        int j = 0;
        int len = pushA.length;
        ArrayList<Integer> list = new ArrayList<Integer>();
        while (true) {
            if (list.size() == 0 || popA[j] != list.get(list.size() - 1)) {
                if (i == len) {
                    return false;
                }
                list.add(pushA[i]);
                i++;
            }
            else if (popA[j] == list.get(list.size() - 1)) {
                j++;
                list.remove(list.size() - 1);
            }
            if (j == len) {
                break;
            }
        }
        return true;
    }
}

注意事项

本题的边界条件和成功判定特别容易出错，至少在我的代码里面改了很多次才成功：

  • 使用Arraylist模拟栈，使用list.get(list.size() - 1)) list.add(pushA[i]) list.remove(list.size() - 1)模拟栈的操作。

  • 核心思想是用一个栈模拟进栈的操作，然后不断寻找栈顶元素是否为待出栈元素，只要能在栈顶找到所有的待出栈元素即为成功。

  • 栈顶元素不等于pop[j]或者空栈，操作是一样的，均需要向栈内压入新的元素。

  • 代码的判定false的条件一定是还存在pop[j]，但是在一次与栈顶元素比较失败之后没有新的元素压入栈内。所以可以return false可以写在不等于的判断内。

  • 代码的判定true的条件是最后一个pop[j]判断成功。return true 可以写在等于的判断内。

  • 由于false的情况可以更多的节约计算时间，即不用遍历完所有的数据，因此代码使用的是先判断return false。

  • 跳出循环条件其实也是return true 的情况，修改了很多次，因此用break写在了循环最后一部分。

总结一下，本题思想是模拟进栈过程，按照出栈顺序不断寻找栈顶元素。但是要注意栈空和往后继续寻找是一样的操作，以及最后成功失败的判定条件。

这题做了好久好久，免不得啰嗦几句。。。

从上往下打印二叉树

本题知识点：树

题目描述

从上往下打印出二叉树的每个节点，同层节点从左至右打印。(层次遍历)

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

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

    }

}
*/
public class Solution {
    public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
        ArrayList<TreeNode> list = new ArrayList<TreeNode>();
        ArrayList<Integer> result = new ArrayList<Integer>();
        if (root == null) {
            return result;
        }
        list.add(root);
        while (list.size() > 0) {
            result.add(list.get(0).val);
            if (list.get(0).left != null) {
                list.add(list.get(0).left);
            }
            if (list.get(0).right != null) {
                list.add(list.get(0).right);
            }
            list.remove(0);
        }
        return result;
    }
}

注意事项

树的循环或者遍历要注意代码完整性（节点为空的情况）；

层次遍历使用队列。

二叉搜索树的后序遍历序列

本题知识点：树

题目描述

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

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
public class Solution {
    public boolean VerifySquenceOfBST(int [] sequence) {
        
        int len = sequence.length;
        if (len == 0) {
            return false;
        }
        return _VerifySquenceOfBST(sequence, 0, len - 1);
    }
    public boolean _VerifySquenceOfBST(int [] s, int start, int end) {
        if (end - start <= 1) {
            return true;
        }
        int root = s[end];
        int flag1 = -1;
        for (int i = start; i < end - 1; i++) {
            if(s[i] == root || s[i+1] == root || s[i] == s[i+1]) {
                return false;
            }
            else if (s[i] >= root && s[i+1] <= root) {
                return false;
            }
            if (s[i] < root) {
                flag1 = i + 1;
            }
        }
        if (flag1 == root || flag1 == -1) {
            return _VerifySquenceOfBST(s, start, end - 1);
        }
        else {
            return _VerifySquenceOfBST(s, start, flag1 - 1) && _VerifySquenceOfBST(s, flag1, end - 1);
        }
    }
}

注意事项

为了递归使用函数，新定义一个 _VerifySquenceOfBST，增加判断数组的首尾坐标；

新函数中递归使用自己的时候特意做了长度的区分，即递归判断的时候发现子树长度为0就默认是true，只需要判断另一部分子树，体现在第28行代码以及第11行代码。分别对应只含有左子树、右子树或者本身的长度就为0,1,2（此时均是符合题意的）；

当然最开始要判断空树，因为新函数是无法传入空树的，首尾坐标存在则表示树的长度至少为1；

对于新函数，当树的长度大于等于3的时候，要判断一下几点：

  1. 根节点root和任意一个节点的值不能相等且任意两个节点值不相等；
  2. 根据题意只允许出现“小”“大”“中”的序列，其中“中”是根节点；
  3. 优选判断false，因此一旦出现s[i]>=root>=s[i+1]的情况就是false；
  4. 如果到最后都没有出现上述情况，就代表是符合题意的，进而需要找到左右子树的分界点；
  5. 这里采用flag1定位“小”序列的结尾的下一个位坐标；
  6. 如果flag1==root，证明全部为“小”序列，即全部为左子树；
  7. 如果flag1==-1，证明不存在“小”序列，全部是右子树；
  8. 其余情况flag1就是“大”序列也就是右子树的第一个坐标，就可以区分出左右子树，且每个子树的长度大于等于1；

其实代码的描述有些地方是重复的，因此还可以继续优化，不过时间复杂度新函数每次都是O(n)，总的时间复杂度取决于递归调用了几次，为O(nlogn)。

二叉树中和为某一值的路径

本题知识点：树

题目描述

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

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
import java.util.ArrayList;
/**
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) {
        int sum = 0;
        ArrayList<TreeNode> list = new ArrayList<TreeNode>();
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        if (root == null) {
            return result;
        }
        _FindPath(root, target, result, list, sum);
        return result;
    }
    public void _FindPath(TreeNode node,int target,ArrayList<ArrayList<Integer>> result, ArrayList<TreeNode> list,int sum) {
        sum += node.val;
        list.add(node);
        if (sum == target && node.left == null && node.right == null) {
            ArrayList<Integer> temp = new ArrayList<Integer>();
            for (int i = 0; i < list.size(); i++) {
                temp.add(list.get(i).val);
            }
            result.add(temp);
            //temp.clear();
        }
        if (node.left != null) {
            _FindPath(node.left, target, result, list, sum);
        }
        if (node.right != null) {
            _FindPath(node.right, target, result, list, sum);
        }
        sum -= node.val;
        list.remove(list.size()-1);
    }
}

注意事项

！！！树的题一定要用递归，有些题循环写起来太麻烦了。

这道题就是，虽然递归优化不是很好，但是写着方便，而且出错概率小。

思路完全是按照书上面写的。

复杂链表的复制

本题知识点：链表

题目描述

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）

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
57
58
59
60
61
/*
public class RandomListNode {
    int label;
    RandomListNode next = null;
    RandomListNode random = null;

    RandomListNode(int label) {
        this.label = label;
    }
}
*/
public class Solution {
    public RandomListNode Clone(RandomListNode pHead)
    {
        if (pHead == null) {
            return null;
        }
        if (pHead.next == null) {
            return new RandomListNode(pHead.label);
        }
        copyNode(pHead);
        copyLink(pHead);
        return separate(pHead);
    }
    public void copyNode(RandomListNode pHead) {
        RandomListNode index = new RandomListNode(0);
        index = pHead;
        while (index != null) {
            RandomListNode temp = new RandomListNode(index.label);
            temp.next = index.next;
            index.next = temp;
            index = temp.next;
        }
    }
    public void copyLink(RandomListNode pHead) {
        RandomListNode index = new RandomListNode(0);
        index = pHead;
        while (index != null) {
            if (index.random != null) {
                index.next.random = index.random.next;
            }
            index = index.next.next;
        }
    }
    public RandomListNode separate(RandomListNode pHead) {
        RandomListNode index1 = new RandomListNode(0);
        RandomListNode head = new RandomListNode(0);
        RandomListNode index2 = new RandomListNode(0);
        index1 = pHead;
        head = index1.next;
        index2 = head;
        while (index2.next != null) {
            index1.next = index2.next;
            index1 = index2.next;
            index2.next = index1.next;
            index2 = index1.next;
        }
        index1.next = null;
        return head;
    }
}

注意事项

链表不要出现为空的异常。

二叉搜索树与双向链表

本题知识点：树

题目描述

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

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 {
    TreeNode last = null;
    public TreeNode Convert(TreeNode pRootOfTree) {
        _convert(pRootOfTree);
        while (last != null && last.left != null) {
            last = last.left;
        }
        return last;
    }
    public void _convert(TreeNode root) {
        if (root == null) {
            return;
        }
        _convert(root.left);
        root.left = last;
        if (last != null) {
            last.right = root;
        }
        last = root;
        _convert(root.right);
    }
}

注意事项

用全局变量，不然递归的时候传参总是不成功。

字符串的排列

本题知识点：字符串的排序

题目描述

输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。

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.List;
public class Solution {
    private StringBuffer buffer;
    private List<String> list = new ArrayList<>();
    public ArrayList<String> Permutation(String str) {
        if (str == null || str.length() == 0) {
           return (ArrayList<String>) list;
        }
        buffer = new StringBuffer(str);
        PermutationCore(0);
        return (ArrayList<String>) list;
    }
    public void PermutationCore(int begin) {
        if (begin == buffer.length() - 1) {
            list.add(buffer.toString());
        }
        for(int i = begin; i < buffer.length(); i++) {
            swap(begin,i);
            PermutationCore(begin + 1);
            swap(begin,i);
        }
    }
    public swap (int i,int j) {
        char a = buffer.charAt(i);
        char b = buffer.charAt(j);
        buffer.setCharAt(i, b);
        buffer.setCharAt(j, 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
import java.util.ArrayList;
import java.util.List;
import java.util.Set;
import java.util.TreeSet;
import java.util.Iterator;
public class Solution {
    private StringBuffer buffer;
    private List<String> list = new ArrayList<>();
    private Set<String> set = new TreeSet<>();
    
    public ArrayList<String> Permutation(String str) {
        if (str == null || str.length() == 0) {
           return (ArrayList<String>) list;
        }
        buffer = new StringBuffer(str);
        PermutationCore(0);
        Iterator<String> iterator = set.iterator();
        while(iterator.hasNext()) {
            list.add(iterator.next());
        }
        return (ArrayList<String>) list;
    }
    public void PermutationCore(int begin) {
        if (begin == buffer.length() - 1) {
            set.add(buffer.toString());
        }
        for(int i = begin; i < buffer.length(); i++) {
            swap(begin,i);
            PermutationCore(begin + 1);
            swap(begin,i);
        }
    }
    public void swap (int i,int j) {
        char a = buffer.charAt(i);
        char b = buffer.charAt(j);
        buffer.setCharAt(i,b);
        buffer.setCharAt(j,a);
    }
}

注意事项

待补充

数组中出现次数超过一半的数字

本题知识点：

题目描述

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        if (array == null || array.length == 0) {
            return 0;
        }
        int N = array.length;
        int middle = N / 2;
        int index = partition(array,0,N-1);
        int start = 0;
        int end = N - 1;
        while (index != middle) {
            if (index > middle) {
                end = index - 1;
                index = partition(array,start,end);
            }
            else {
                start = index + 1;
                index = partition(array,start,end);
            }
        }
        if (checkArray(array,array[index])) {
            return array[index];
        }
        else {
            return 0;
        }
    }
    private int partition (int[] array,int left,int right) {
        if (left > right) {
            return -1;
        }
        int root = array[left];
        while (left < right) {
            while(left < right && array[right] >= root) right--;
            array[left] = array[right];
            while(left < right && array[left] <= root) left++;
            array[right] = array[left];
        }
        array[left] = root;
        return left;
    }
    private boolean checkArray(int[] array, int value) {
        int N = array.length;
        int count = 0;
        for (int i = 0; i < N; i++) {
            if (array[i] == value) {
                count ++;
            }
        }
        return count*2 > N ? true : false;
    }
}

最小的K个数

题目描述

输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import java.util.TreeSet;
import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        
        if(input == null)
            return null;
        ArrayList<Integer> list = new ArrayList<Integer>(k);
        if(k > input.length)
            return list;
        TreeSet<Integer> tree = new TreeSet<Integer>();
        for(int i = 0 ; i < input.length; i++){
            tree.add(input[i]);
        }
        int i = 0;
        for(Integer elem : tree){
            if(i >= k)
                break;
            list.add(elem);
            i++;
        }
        return list;
    }
}

注意事项

TreeSet的使用直接完成对容器寻找最大值，插入和删除的操作。代码通过了，但是存疑。

连续子数组的最大和

题目描述

输入一个整形数组，数组里面有正数也有负数。数组中一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        if (array == null || array.length == 0) {
            return 0;
        }
        int max = 0;
        int result = array[0];
        for (int i = 0; i < array.length; i++) {
            if (max <= 0)
                max = array[i];
            else 
                max += array[i];
            result = result < max ? max : result;
        }
        return result;
    }
}

注意事项