《剑指offer》牛客网21-40

发表于 | 阅读数
字数统计: 4.4k | 阅读时长 ≈ 21

21.栈的压入、弹出序列

题目描述

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列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
import java.util.ArrayList;
import java.util.Stack;
public class Solution {
    public boolean IsPopOrder(int [] pushA,int [] popA) {
        int len = pushA.length;
        Stack<Integer> s = new Stack<Integer>();

        for(int i=0, j=0;  i < len; i++){
            s.push(pushA[i]);
            while(j < len && s.peek() == popA[j]){
                s.pop();
                j = j+1;
            }
        }
        return s.empty();
    }

}

22.从上往下打印二叉树

题目描述
从上往下打印出二叉树的每个节点，同层节点从左至右打印。

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
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
/**
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<Integer> list = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.remove();
            if (node == null) {
                continue;
            }
            list.add(node.val);
            queue.add(node.left);
            queue.add(node.right);
        }
        return list;
    }
}

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

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

例如输入数组{5， 7， 6， 9， 11， 10， 8}，则返回true
发现对于每一棵子树，它的根结点总是对应该子树的后序序列的最后一个数
那么，只需要不断地确定出左子树区间和右子树区间，并且判断：左子树区间的所有结点值 < 根结点值 < 右子树区间所有结点值，这个条件是否满足即可

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
import java.util.Arrays;
/*  copyOfRange方法有以下几个重载的方法，使用方法基本一样，只是参数数组类型不一样
    original：第一个参数为要拷贝的数组对象
    from：第二个参数为拷贝的开始位置（包含）
    to：第三个参数为拷贝的结束位置（不包含）
*/
public class Solution {
    public boolean VerifySquenceOfBST(int [] sequence) {
        int len = sequence.length;
        if(len==0)
            return false;
        int root = sequence[len-1];
        //左子点的值小于根节点的值
        int i=0;
        for(;i<len-1;i++){
            if(sequence[i]>root) break;
        }
        //在二叉搜索树中右子树节点的值大于根节点
        int j=i;
        for(;j<len-1;j++){
            if(sequence[j]<root) return false;
        }
        

        boolean left=true,right=true;
        
        if(i>0) 
            left=VerifySquenceOfBST(Arrays.copyOfRange(sequence,0,i));
        if(i<len-1)  
            right=VerifySquenceOfBST(Arrays.copyOfRange(sequence,i,len-1));
        return left && right;
    }

}

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

题目描述
输入一颗二叉树的跟节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前)

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

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

}
*/
public class Solution {
    private ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
    private ArrayList<Integer> list = new ArrayList<>();
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
        if(root == null)
            return result;
        list.add(root.val);
        target -= root.val;
        if(target == 0 && root.left == null && root.right == null)
            result.add(new ArrayList<Integer>(list));
        ArrayList<ArrayList<Integer>> result1 = FindPath(root.left, target);
        ArrayList<ArrayList<Integer>> result2 = FindPath(root.right, target);
        list.remove(list.size()-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
30
31
32
public class PathInTree {
		public class TreeNode {
				int val = 0;
				TreeNode left = null;
				TreeNode right = null;
				public TreeNode(int val) {
					this.val = val;
				}
		}
	
		public void findPath(TreeNode root,int target) {
				if(root==null)
					return;
				ArrayList<Integer> list= new ArrayList<>();
				printPath(root, target,list);
		}
	
		private void printPath(TreeNode node,int target,ArrayList<Integer> list) {
				if(node==null)
					return;
				list.add(node.val);
				target-=node.val;? //每个结点的target不会受到方法的影响而改变
				if(target==0 && node.left==null && node.right==null) {? //叶子结点
						for (Integer integer : list)
								System.out.print(integer+" ");
								System.out.println();
				}else {	//中间结点
					printPath(node.left, target, list);
					printPath(node.right, target, list);
				}
				list.remove(list.size()-1);
		}

25.复杂链表的复制

题目描述
输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的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
/*
public class RandomListNode {
    int label;
    RandomListNode next = null;
    RandomListNode random = null;

    RandomListNode(int label) {
        this.label = label;
    }

}
*/
import java.util.*;
public class Solution {
    public RandomListNode Clone(RandomListNode pHead)
    {
        if(pHead == null)return null;
        RandomListNode newHead = null;
        RandomListNode p = pHead;
        RandomListNode q = null;
        Map<RandomListNode, RandomListNode> map = new HashMap<>();
        while(p != null){
            if(newHead == null){
                newHead = new RandomListNode(pHead.label);
                q = newHead;
                map.put(pHead, newHead);
            }else{
                if(p.next!= null && map.containsKey(p.next))
                    q.next = map.get(p.next);
                else{
                    if(p.next!= null){
                        RandomListNode temp = new RandomListNode(p.next.label);
                        map.put(p.next, temp);
                        q.next = temp;
                    }
                }
                if(p.random != null && map.containsKey(p.random))
                    q.random = map.get(p.random);
                else{
                    if(p.random != null){
                        RandomListNode temp = new RandomListNode(p.random.label);
                        map.put(p.random, temp);
                        q.random = temp;   
                    }
                }
                p = p.next;
                q = q.next;
            }
        }
        return newHead;
    }
}

26.二叉搜索树与双向链表

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

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

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

}
*/
import java.util.*;
public class Solution {

    private ArrayList<TreeNode> list = new ArrayList<>();
    public TreeNode Convert(TreeNode pRootOfTree) {
        mid(pRootOfTree);
        if(list.size()==1 || list.size()==0){
            return pRootOfTree;
        }
        TreeNode root = null;
        TreeNode pre = null;
        TreeNode after = null;
        for(int i=0;i<list.size()-1;i++){
            if(i==0){
                root=list.get(i);
                root.left = pre;
                pre = root;
                after= list.get(i+1);
                root.right=after;
            }else{
                after.left=pre;
                pre = after;
                after = list.get(i+1);
                pre.right = after;
            }
        }
        after.left = pre;
        after.right = null;
        return root;
    }
    private void mid(TreeNode pRootOfTree) {
        if(pRootOfTree==null){
            return ;
        }
        if(pRootOfTree.left!=null){
            mid(pRootOfTree.left);
        }
        list.add(pRootOfTree);
        if(pRootOfTree.right!=null){
            mid(pRootOfTree.right);
        }
    }

}

27.字符串的排列

题目描述
输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
输入描述:
输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。

TreeSet这个数据结构本身采用红黑树实现，能够自动将字符串按照字典序排序，同时因为其实现了Set接口，所以又能同时保证所有的结果是一个集合。而学过离散数学的朋友都知道，集合中的元素是不会重复的，所以如果我们采用TreeSet对排列的结果进行存储，那么就能轻易的达到上述要求。下面是本人实现的代码：

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.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.Set;
import java.util.TreeSet;
public class Solution {
   private List<String> list = new ArrayList<>();
    private Set<String> set = new TreeSet<>();
    private StringBuffer buffer;
    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++){
            //if(buffer.charAt(i)==buffer.charAt(begin) && begin!=i) continue;
            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);    
    }
}

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

题目描述
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为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
public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        if(array == null || array.length == 0)return 0;
        int preValue = array[0];
        int count = 1;
        for(int i = 1; i < array.length; i++){
            if(array[i] == preValue)
                count++;
            else{
                count--;
                if(count == 0){
                    preValue = array[i];
                    count = 1;
                }
            }
        }
        int num = 0;
        for(int i=0; i < array.length; i++)
            if(array[i] == preValue)
                num++;
        return (num > array.length/2)?preValue:0;

    }

}

29.最小的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
1.
import java.util.Arrays;
import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> list=new ArrayList<Integer>();
        if(input==null||input.length<=0)
            return list;
        if(k>input.length)
            return list;
        

        Arrays.sort(input);
        for(int i=0;i<k;i++)
            list.add(input[i]);
        return list;
        
    }

}

30.连续子数组的最大和

题目描述

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import java.util.*;
public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        if(array==null||array.length<=0)
            return 0;
        int sum=0;
        int max=Integer.MIN_VALUE;
        for(int val:array){
            sum=sum<=0?val:val+sum;
            max=Math.max(max,sum);
            

        }
        return max;
    }

}

31.整数中1出现的次数（从1到n整数中1出现的次数）

题目描述
求出113的整数中1出现的次数,并算出1001300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数（从1 到 n 中1出现的次数）。

1
2
3
4
5
6
7
8
9
10
11
12
public class Solution {
    public int NumberOf1Between1AndN_Solution(int n) {
        int count=0;
        for(int i=n;i>0;i--){
            for(int j=i;j>0;j/=10){
                if(j%10==1) 
                    count++;
            }
        }
        return count;
    }
}

32.把数组排成最小的数

题目描述
输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{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
import java.util.ArrayList;
public class Solution {

    public String PrintMinNumber(int [] numbers) {
        if(numbers == null || numbers.length == 0)return "";
        for(int i=0; i < numbers.length; i++){
            for(int j = i+1; j < numbers.length; j++){
                int sum1 = Integer.valueOf(numbers[i]+""+numbers[j]);
                int sum2 = Integer.valueOf(numbers[j]+""+numbers[i]);
                if(sum1 > sum2){
                    int temp = numbers[j];
                    numbers[j] = numbers[i];
                    numbers[i] = temp;
                }
            }
        }
        String str = new String("");
        for(int i=0; i < numbers.length; i++)
            str = str + numbers[i];
        return str;
     
    }

}

33.丑数

题目描述
把只包含质因子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
public class Solution {
    public int GetUglyNumber_Solution(int index) {
        if(index <= 0)return 0;
        int p2=0,p3=0,p5=0;//初始化三个指向三个潜在成为最小丑数的位置
        int[] result = new int[index];
        result[0] = 1;//
        for(int i=1; i < index; i++){
            result[i] = Math.min(result[p2]*2, Math.min(result[p3]*3, result[p5]*5));
            if(result[i] == result[p2]*2)
                p2++;//为了防止重复需要三个if都能够走到
            if(result[i] == result[p3]*3)
                p3++;//为了防止重复需要三个if都能够走到
            if(result[i] == result[p5]*5)
                p5++;//为了防止重复需要三个if都能够走到
        }
        return result[index-1];
    }
}

34.第一个只出现一次的字符位置

题目描述
在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1（需要区分大小写）.

1
2
3
4
5
6
7
8
9
10
11
12
13
public class Solution {
    public int FirstNotRepeatingChar(String str) {
        int cnts[]=new int [256];
        for(int i=0;i<str.length();i++){
            cnts[str.charAt(i)]++;
        }
        for(int i=0;i<str.length();i++){
            if(cnts[str.charAt(i)]==1)
                return i;
        }
        return -1;
    }
}

35.数组中的逆序对

题目描述
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007
输入描述:
题目保证输入的数组中没有的相同的数字
数据范围：
对于%50的数据,size<=10^4
对于%75的数据,size<=10^5
对于%100的数据,size<=2*10^5
示例1
输入
1,2,3,4,5,6,7,0
输出
7

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
public class Main {

	private int reversePair = 0; // 统计数组中的逆序对

	public int inversePairs(int[] array) {
		if (array == null) { //数组为null返回0
			return 0;
		}
		int len = array.length;

		if (len == 0) { //数组长度为0返回0
			return 0;
		}
		sort(array, 0, len - 1); //进行排序
		return reversePair;
	}

	private void sort(int[] arr, int start, int end) {
		if (start < end) { //利用归并排序的思想
			int mid = (start + end) / 2;
			sort(arr, start, mid);
			sort(arr, mid + 1, end);
			merger(arr, start, mid, mid + 1, end);
		}
	}
    
	private void merger(int[] arr, int start1, int end1, int start2, int end2) { //归并排序
		int len = end2 - start1 + 1;
		int [] nums = new int[len];
		int k = end2 - start1 + 1;
		int i = end1;
		int j = end2;
		
		while(i >= start1 && j >= start2){
			if(arr[i] > arr[j]){
				nums[--k] = arr[i--];
				reversePair = reversePair + (j - start2 + 1);
			}else{
				nums[--k] = arr[j--];
			}
		}
		for( ; i >= start1; i--){
			nums[--k] = arr[i];
		}
		for( ; j >= start2; j--){
			nums[--k] = arr[j];
		}
		for(int m =0; m < len; m++){
			arr[start1++] = nums[m];
		}
	}

	public static void main(String[] args) {
		Main main = new Main();
		int nums[] = new int[]{7, 5, 6, 4};
		int total = main.inversePairs(nums);
		System.out.println(total);
	}
}

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }

}*/
public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        ListNode l1=pHead1;
        ListNode l2=pHead2;
        while(l1!=l2){
            l1=(l1==null)?pHead2:l1.next;
            l2=(l2==null)?pHead1:l2.next;
        }
         return l1;
    }
}

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import java.util.Arrays;
public class Solution {

    public int GetNumberOfK(int [] array , int k) {
        int index = Arrays.binarySearch(array, k);
        if(index<0)
            return 0;
        int cnt = 1;
        for(int i=index+1; i < array.length && array[i]==k;i++)
            cnt++;
        for(int i=index-1; i >= 0 && array[i]==k;i--)
            cnt++;
        return cnt;
     
    }

}

38.二叉树的深度

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
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) {
        return root==null? 0:1+Math.max(TreeDepth(root.left),TreeDepth(root.right));
    }
}

39.平衡二叉树

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class Solution {
    public int depth(TreeNode root){
        if(root == null)
            return 0;
        int left = depth(root.left);
        if(left == -1)
            return -1; //如果发现子树不平衡之后就没有必要进行下面的高度的求解了
        int right = depth(root.right);
        if(right == -1)
            return -1;//如果发现子树不平衡之后就没有必要进行下面的高度的求解了
        if(left - right <(-1) || left - right > 1)
            return -1;
        else
            return 1+(left > right?left:right);
    }

    public boolean IsBalanced_Solution(TreeNode root) {
        return depth(root) != -1;
    }

}

40.数组中只出现一次的数字

题目描述
一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

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
//num1,num2分别为长度为1的数组。传出参数
//将num1[0],num2[0]设置为返回结果
import java.util.HashMap;
public class Solution {
    public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
        //哈希算法
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        for(int i=0; i < array.length; i++){
            if(map.containsKey(array[i]))
                map.put(array[i],2);
            else
                map.put(array[i],1);
        }
        int count = 0;
        for(int i=0; i < array.length; i++){
            if(map.get(array[i]) == 1){
                if(count == 0){
                    num1[0] =  array[i];
                    count++;
                }else
                    num2[0] =  array[i];
            }
        }

    }

}
-------------本文结束感谢您的阅读-------------
0%