剑指offer题库以及详解

发表于 分类于 阅读次数：
本文字数： 21k 阅读时长 ≈ 19 分钟

剑指offer

第一题

题目:在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

思路:因为这个二维数组是有序的, 可以先定位到左下角, 判断要找的数, 如果target > 左下角 就往右找, 然后target < 左下角 就往上找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Solution {
    public boolean Find(int target, int [][] array) {
		//得到二维数组的行和列
		int rows = array.length;
		int cols = array[0].length;
		//定位到左下角
		int i = rows - 1;
		int j = 0;
		//循环查找, 不知道循环次数, 用while
		while(i >= 0 && j < cols){
			if(target > array[i][j])
				j++;
			else if(target < array[i][j])
				i--;
			else
				return true;
		}
		return false;
	}
}

第二题

题目: 请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

思路:首先不能使用String提供的replace()方法

①从前往后替换, 每替换一次后面的字符就要移动一次, 效率低下

②从后往前替换, 每个字符只需要移动一次, 所以选择这个思路

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 Solution {
	public String replaceSpace(StringBuffer str) {
		//计算空格数
		int spacenum = 0;
		for(int i = 0; i < str.length(); i++){
			if(str.charAt(i) == ' ')
				spacenum++;
		}
		//扩容
		int indexOld = str.length() - 1;
		int newLength = str.length() + spacenum * 2;
		int indexNew = newLength - 1;
		str.setLength(indexNew);
		//替换
		for(;indexOld >= 0 && newLength > indexOld; --indexOld){
			if(str.charAt(indexOld) == ' '){
				str.setCharAt(indexNew--, '0');
				str.setCharAt(indexNew--, '2');
				str.setCharAt(indexNew--, '%');
			} else {
				str.setCharAt(indexNew--, str.charAt(indexOld));
			}
		}
		return str.toString();
	}
}

第三题

题目: 输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。

1
2
3
4
5
6
7
8
public class ListNode {
       int val;
       ListNode next = null;

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

代码实现:

解法一: 递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import java.util.ArrayList;
public class Solution {
	//先创建一个 ArrayList 集合
	ArrayList<Integer> arrayList = new ArrayList<>();
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
		//判断传入的链表是否不为空
		if(listNode != null){
			//递归调用 printListFromTailToHead()方法, 传入链表的元素
			this.printListFromTailToHead(listNode.next);
			//将遍历出来的链表的元素的值添加入 arrayList 中
			arrayList.add(listNode.val);
		}
		return arrayList;
    }
}

解法二: 利用栈(先进后出)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import java.util.ArrayList;
import java.util.Stack;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        Stack<Integer> temp = new Stack<>();
        ArrayList<Integer> newList = new ArrayList<>();
        ListNode t = listNode;
        while( t != null ){
			temp.push(t.val);
			t = t.next;
		}
		while( !temp.empty() ){
			newList.add(temp.pop());
		}
		return newList;
    }
}

第四题

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

1
2
3
4
5
6
7
Definition for binary tree
	public class TreeNode {
       int val;
       TreeNode left;
       TreeNode right;
       TreeNode(int x) { val = x;}
   }

代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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;
    }
    //前序遍历{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}
    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);
                break;
            }
                 
        return root;
    }
}

第五题

题目: 用两个栈来实现一个队列,完成队列的Push和Pop操作, 队列中的元素为 int 类型

思路: 首先栈是先进后出, 队列是先进先出

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.Stack;
 
public class Solution {
    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();
    
	//队列的 push 操作和 栈的 push 是相同的
    public void push(int node) {
        stack1.push(node);
    }
     
    public int pop() {
		//判断 stack1 和 stack2 是否为空
        if(stack1.empty()&&stack2.empty()){
            throw new RuntimeException("Queue is empty!");
        }

        if(stack2.empty()){
            while(!stack1.empty()){
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }
}

第六题

题目:把一个数组最开始的若干元素搬到数组的末尾, 我们称之为数组的旋转. 输入一个非减排序的数组的一个旋转, 输出旋转数组的最小元素.例如数组{3,4,5,1,2} 为 {1,2,3,4,5}, 该数组的最小值为1, NOTE: 给出的所有元素都大于0, 若数组大小为0 ,请返回0

思路:(1)array[mid] > array[high]:
出现这种情况的array类似[3,4,5,6,0,1,2]，此时最小数字一定在mid的右边。
low = mid + 1
(2)array[mid] == array[high]:
出现这种情况的array类似 [1,0,1,1,1] 或者[1,1,1,0,1]，此时最小数字不好判断在mid左边
还是右边,这时只好一个一个试 ，
high = high - 1
(3)array[mid] < array[high]:
出现这种情况的array类似[2,2,3,4,5,6,6],此时最小数字一定就是array[mid]或者在mid的左
边。因为右边必然都是递增的。
high = mid

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import java.util.ArrayList;
public class Solution {
    public int minNumberInRotateArray(int [] array) {
		int low = 0;
		int hight = array.length - 1;
		while(low < hight){
			//中间的位置
			int mid = low + (hight - low)/2;
			//若中间的数 > 最后一个数, 最小的数就是中间数的下一个
			if(array[mid] > array[hight]){
				low = mid + 1;
			//若中间的数 = 最后一个数, 最小的数左右都有可能, 所有要缩小,继续找
			}else if(array[mid] == array[hight]){
				hight -= 1;
			//若中间的数 < 最后一个数, 最小的数只能是中间的数,或,中间数的左边的数中的某一个
			}else{
				hight = mid;
			}
		}
		return array[low];
	}
}

第七题

题目: 输入一个整数n, 请你输出斐波那契列的第n项(从0开始,第0项为0)

思路一: 采用递归, 这种解法效率低, 每次都要调自己

1
2
3
4
5
6
7
8
9
public class Solution {
    public int Fibonacci(int n) {
        if(n < 2){
            return n;
        }else{
            return Fibonacci(n - 1) + Fibonacci(n - 2);
        }
    }
}

思路二:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Solution {
    public int Fibonacci(int n) {
        if(n < 0) throw new IllegalArgumentException("输入的数不能小于0");
        if(n == 0 || n == 1) return n;
        
        int a = 1, b = 0, sum = 0;
        for(int i = 2;i <= n;i++){
            sum = a + b;
            b = a;
            a = sum;
        }
        return sum;
    }
}

第八题

题目: 一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

思路: 这还是一个斐波那契列, 唯一不同的是从1开始

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Solution {
    public int JumpFloor(int target) {
        if(target < 1) throw new IllegalArgumentException("台阶数不能小于1");;
        if(target < 3) return target;
        
        int a = 1, b = 2, sum = 0;
        for(int i = 3;i <= target;i++){
            sum = a + b;
            a = b;
            b = sum;
        }
        return sum;
    }
}

第九题

题目: 一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。
求该青蛙跳上一个n级的台阶总共有多少种跳法。
分析: f(1) = 1
f(2) = f(2-1) + f(2-2) //f(2-2) 表示2阶一次跳2阶的次数。
f(3) = f(3-1) + f(3-2) + f(3-3)
…
f(n) = f(n-1) + f(n-2) + f(n-3) + … + f(n-(n-1)) + f(n-n) 

说明： 
    1）这里的f(n) 代表的是n个台阶有一次1,2,...n阶的 跳法数。
    2）n = 1时，只有1种跳法，f(1) = 1
    3) n = 2时，会有两个跳得方式，一次1阶或者2阶，这回归到了问题（1） ，f(2) = f(2-1) + f(2-2) 
    4) n = 3时，会有三种跳得方式，1阶、2阶、3阶，那么就是第一次跳出1阶后面剩下：f(3-1);第一次跳出2阶，剩下f(3-2)；第一次3阶，那么剩下f(3-3)
因此结论是f(3) = f(3-1)+f(3-2)+f(3-3)
    5) n = n时，会有n中跳的方式，1阶、2阶...n阶，得出结论：
f(n) = f(n-1)+f(n-2)+...+f(n-(n-1)) + f(n-n) => f(0) + f(1) + f(2) + f(3) + ... + f(n-1)
    6) 由以上已经是一种结论，但是为了简单，我们可以继续简化：
f(n-1) = f(0) + f(1)+f(2)+f(3) + ... + f((n-1)-1) = f(0) + f(1) + f(2) + f(3) + ... + f(n-2)
f(n) = f(0) + f(1) + f(2) + f(3) + ... + f(n-2) + f(n-1) = f(n-1) + f(n-1)
可以得出：f(n) = 2*f(n-1)
    7) 得出最终结论,在n阶台阶，一次有1、2、...n阶的跳的方式时，总得跳法为：

               | 1       ,(n=0 ) 

    f(n) =     | 1       ,(n=1 )

               | 2*f(n-1),(n>=2)

代码实现:

1
2
3
4
5
6
7
8
9
10
public class Solution {
    public int JumpFloorII(int target) {
        if(target < 0) throw new IllegalArgumentException("台阶数不能小于0");
        if(target == 1){
            return 1;
        }else{
            return 2 * JumpFloorII(target - 1);
        }
    }
}

第十题

题目: 我们可以用2×1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2×n的大矩形，总共有多少种方法？

分析: 还是一个斐波那契

采用递归:

1
2
3
4
5
6
7
8
9
10
public class Solution {
    public int RectCover(int target) {
        if(target < 0) throw new IllegalArgumentException("输入的n不能小于0的整数");
        if(target == 0 || target == 1 || target == 2){
            return target;
        } else{
            return RectCover(target - 1) + RectCover(target - 2);
        }
    }
}

不用递归, 效率比较高的解法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Solution {
    public int RectCover(int target) {
        if(target < 0) throw new IllegalArgumentException("输入的数不能小于0");
        if(target == 0 || target == 1) return target;
        
        int a = 1, b = 1, sum = 0;
        for(int i = 2;i <= target;i++){
            sum = a + b;
            b = a;
            a = sum;
        }
        return sum;
    }
}

第十一题

题目: 输入一个整数, 输出该数二进制表示中1的个数, 其中负数用补码表示

思路:如果一个整数不为0，那么这个整数至少有一位是1。如果我们把这个整数减1，那么原来处在整数最右边的1就会变为0，原来在1后面的所有的0都会变成1(如果最右边的1后面还有0的话)。其余所有位将不会受到影响。

举个例子：一个二进制数1100，从右边数起第三位是处于最右边的一个1。减去1后，第三位变成0，它后面的两位0变成了1，而前面的1保持不变，因此得到的结果是1011.我们发现减1的结果是把最右边的一个1开始的所有位都取反了。这个时候如果我们再把原来的整数和减去1之后的结果做与运算，从原来整数最右边一个1那一位开始所有位都会变成0。如1100&1011=1000.也就是说，把一个整数减去1，再和原整数做与运算，会把该整数最右边一个1变成0.那么一个整数的二进制有多少个1，就可以进行多少次这样的操作。

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

第十二题

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

解法一: 常规解法, 时间复杂度为O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
public class Solution {
    public double Power(double base, int exponent) {
        double result = 1;
        //abs() : 返回这个数的绝对值
        for(int i = 0;i < Math.abs(exponent);i++){
            result *= base;
        }
        if(exponent < 0){
            result = 1/result;
        }
        return result;
    }
}

解法二: 递归:

​ n为偶数时, a^n = a^(n/2) * a^(n/2)

​ n为奇数时, a^n=（a^（n-1）/2）×（a^（n-1/2））×a

时间复杂度为 O(logn)

1
2
3
4
5
6
7
8
9
10
11
12
13
public class Solution(){
    public double Power(double base, int exponent){
        int n = Math.abs(exponent);
        if(n == 0) return 1;
        if(n == 1) return base;
        
        double result = Power(base, n>>1);
        result *= result;
        if((n&1) == 1) result *= base;
        if(exponent < 0) result = 1/result;
        return result;
    }
}

第十三题

题目: 输入一个整数数组,实现一个函数来调整该数组中的数字的顺序,使得所有的奇数位于数组的前半部分,所有的偶数位于数组的后半部分,并保证奇数和奇数,偶数和偶数之间的相对位置不变.

思路: 

1
2
3
首先统计奇数的个数
然后新建一个等长数组，设置两个指针，奇数指针从0开始，偶数指针从奇数个数的末尾开始 遍历，填数
此方法的时间复杂度为O(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
public class Solution{
    public void reOrderArray(int [] array){
        if(array.length == 0 ||array.length == 1) return;
        int oddCount = 0,oddBegin = 0;
        //创建一个和原数组等长的新数组
        int[] newArray = new int[array.length];
        //遍历数组
        for(int i = 0;i < array.length;i++){
            //判断数组元素为奇数时,将oddCount向后移一位,
            //最终oddCount的位置就是第一个偶数的位置
            if((array[i]&1) == 1) oddCount++;
        }
        for(int i = 0;i < array.length;i++){
            //判断元素为奇数就从新数组的开头位置开始放
            if((array[i]&1) == 1){
                newArray[oddBegin++] = array[i];
            } else{
                //如果元素为偶数就从新数组的偶数第一个位置开始放
                newArray[oddCount++] = array[i];
            }
        }
        //最后用新数组排好序的元素替换原数组的元素
        for(int i = 0;i < array.length;i++){
            array[i] = newArray[i];
        }
    }
}

第十四题

题目: 输入一个链表,输出该链表中倒数第K个节点

1
2
3
4
5
6
7
8
9
/*
public class ListNode {
    int val;
    ListNode next = null;

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

思路: 定义两个指针, 先让着两个指针都指向链表的头结点, 然后让其中一个指针往后移(k - 1)位, 再让另一个指针开始跑(此时两个指针在相对静止的跑), 当先跑的那个指针到达链表末尾时, 后跑的那个指针到达的位置就是倒数第k的位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Solution{
    public ListNode FindKthToTail(ListNode head,int k){
        //定义两个指针都指向头结点
        ListNode p, q;
        p = q = head;
        //记录k值
        int a = k;
        //记录节点个数
        int count = 0;
        while(p != null){
            p = p.next;
            count++;
            if(k < 1) q = q.next;
            k--;
        }
        if(count < a) return null;
        return q;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
精简写法
public class Solution{
    public ListNode FindKthToTail(ListNode head,int k){
    	ListNode p, q;
    	p = q = head;
    	int i = 0;
    	for( ; p != null; i++){
    		if(i >= k) q = q.next;
    		p = p.next;
    	}
    	return i < k ? null : q;
    }
}

第十五题

题目: 输入一个人链表, 反转链表后, 输出新链表的表头.

1
2
3
4
5
6
7
8
9
/*
public class ListNode {
    int val;
    ListNode next = null;

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

题解

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 Solution {
    public ListNode ReverseList(ListNode head) {
       
        if(head==null)
            return null;
        //head为当前节点，如果当前节点为空的话，那就什么也不做，直接返回null；
        ListNode pre = null;
        ListNode next = null;
        //当前节点是head，pre为当前节点的前一节点，next为当前节点的下一节点
        //需要pre和next的目的是让当前节点从pre->head->next1->next2变成pre<-head next1->next2
        //即pre让节点可以反转所指方向，但反转之后如果不用next节点保存next1节点的话，此单链表就此断开了
        //所以需要用到pre和next两个节点
        //1->2->3->4->5
        //1<-2<-3 4->5
        while(head!=null){
            //做循环，如果当前节点不为空的话，始终执行此循环，此循环的目的就是让当前节点从指向next到指向pre
            //如此就可以做到反转链表的效果
            //先用next保存head的下一个节点的信息，保证单链表不会因为失去head节点的原next节点而就此断裂
            next = head.next;
            //保存完next，就可以让head从指向next变成指向pre了，代码如下
            head.next = pre;
            //head指向pre后，就继续依次反转下一个节点
            //让pre，head，next依次向后移动一个节点，继续下一次的指针反转
            pre = head;
            head = next;
        }
        //如果head为null的时候，pre就为最后一个节点了，但是链表已经反转完毕，pre就是反转后链表的第一个节点
        //直接输出pre就是我们想要得到的反转后的链表
        return pre;
    }
}

第十六题

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

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 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;
        
        if(list1.val <= list2.val){
            list1.next = Merge(list1.next, list2);
            return list1;
        } else{
            list2.next = Merge(list1, list2.next);
            return list2;
        }
    }
}
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
//非递归版
public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        //新建一个头节点，用来存合并的链表。
        ListNode head=new ListNode(-1);
        head.next=null;
        ListNode root=head;
        while(list1!=null&&list2!=null){
            if(list1.val<list2.val){
                head.next=list1;
                head=list1;
                list1=list1.next;
            }else{
                head.next=list2;
                head=list2;
                list2=list2.next;
            }
        }
        //把未结束的链表连接到合并后的链表尾部
        if(list1!=null){
            head.next=list1;
        }
        if(list2!=null){
            head.next=list2;
        }
        return root.next;
    }
}

第十七题

题目：输入两棵二叉树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
51
52
53
54
/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

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

    }

}
*/
public class Solution {
    public static boolean HasSubtree(TreeNode root1, TreeNode root2) {
        boolean result = false;
        //当Tree1和Tree2都不为零的时候，才进行比较。否则直接返回false
        if (root2 != null && root1 != null) {
            //如果找到了对应Tree2的根节点的点
            if(root1.val == root2.val){
                //以这个根节点为为起点判断是否包含Tree2
                result = doesTree1HaveTree2(root1,root2);
            }
            //如果找不到，那么就再去root的左儿子当作起点，去判断时候包含Tree2
            if (!result) {
                result = HasSubtree(root1.left,root2);
            }
             
            //如果还找不到，那么就再去root的右儿子当作起点，去判断时候包含Tree2
            if (!result) {
                result = HasSubtree(root1.right,root2);
               }
            }
            //返回结果
        return result;
    }
 
    public static boolean doesTree1HaveTree2(TreeNode node1, TreeNode node2) {
        //如果Tree2已经遍历完了都能对应的上，返回true
        if (node2 == null) {
            return true;
        }
        //如果Tree2还没有遍历完，Tree1却遍历完了。返回false
        if (node1 == null) {
            return false;
        }
        //如果其中有一个点没有对应上，返回false
        if (node1.val != node2.val) {  
                return false;
        }
         
        //如果根节点对应的上，那么就分别去子节点里面匹配
        return doesTree1HaveTree2(node1.left,node2.left) && doesTree1HaveTree2(node1.right,node2.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
/**
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;
        if(root.left == null && root.right == null) return;
        
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        
        if(root.left != null) Mirror(root.left);
        if(root.right != null) 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
/*
public class ListNode {
    int val;
    ListNode next = null;

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

//定义两个起始位置为头结点的指针,p1指在较短链表上,p2指在较长链表上
//让这p1,p2同时next,当p1到达链表尾部时,让p1指向较长链表的头部
//当p2到达链表尾部时,让p2指向较短链表头部
//当它们指向同一个节点时,该节点就是两个链表的第一个公共节点
public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
 		ListNode p1 = pHead1;
        ListNode p2 = pHead2;
        
        while(p1 != p2){
            if(p1 != null) p1 = p1.next;
            if(p2 != null) p2 = p2.next;
            
            if(p1 != p2){
                if(p1 == null) p1 = pHead2;
                if(p2 == null) p2 = pHead1;
            }
        }
        return p1;
    }
}

第二十题

题目：给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。

思路：快慢指针法

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

    ListNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
 
    ListNode EntryNodeOfLoop(ListNode pHead){
		//判断是否为链表,不是直接返回null
        if(pHead == null || pHead.next == null) return null;
        //定意两个快慢指针
        ListNode m = pHead.next;
        ListNode k = pHead.next.next;
        //进行指针前进
        while(m != k){
            if(k != null && k.next != null){
           		  m = m.next;
           		  k = k.next.next;
     		} else{
                return null;
            }
       	}
        
        //当快慢指针指向同一个节点时,跳出while循环
        k = pHead;
        while(m != k){
            m = m.next;
            k = k.next;
        }
        return m;
    }
}

第二十一题

题目: 输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下4 X 4矩阵： 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
44
45
46
47
48
49
50
51
52
53
54
55
package com.holicCode;

import java.util.ArrayList;

public class Solution {
    public static ArrayList<Integer> printMatrix(int [][] matrix) {
        ArrayList<Integer> list = new ArrayList<>();
        if (matrix == null || matrix.length == 0) {
            return list;
        }
        int up = 0;
        int down = matrix.length - 1;
        int left = 0;
        int right = matrix[0].length - 1;
        while (true) {
            // 向右
            for (int i = left; i <= right; i++) {
                list.add(matrix[up][i]);
            }
            if (++up > down) {
                break;
            }
            // 向下
            for (int i = up; i <= down; i++) {
                list.add(matrix[i][right]);
            }
            if (--right < left) {
                break;
            }
            // 向左
            for (int i = right; i >= left; i--) {
                list.add(matrix[down][i]);
            }
            if (--down < up) {
                break;
            }
            // 向上
            for (int i = down; i >= up; i--) {
                list.add(matrix[i][left]);
            }
            if (++left > right) {
                break;
            }
        }
        return list;
    }

    
    //测试
    public static void main(String[] args) {
		int[][] matrix = {{1},{2},{3},{4},{5}};
		System.out.println(printMatrix(matrix));
		
	}
}

未完,待续……….

Thanks
0%