剑指Offer_15

发表于 2017-12-01 | 分类于剑指Offer

题目

输入一个链表，反转链表后，输出链表的所有元素。

解题思路

三个指针来记录位置，反转链表。

/*
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 || head.next == null){
            return head;
        }
        
        ListNode pre = null;
        ListNode cur = head;
        ListNode post = head.next;
        
        while(post != null){
            cur.next = pre;
            pre = cur;
            cur = post;
            post = post.next;
        }
        //循环退出条件post == null
        //最后一个节点还未指向它的前一节点
        cur.next = pre;
        return cur;
    }
}

剑指Offer_14

发表于 2017-12-01 | 分类于剑指Offer

题目

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

解题思路

解法一：

两趟遍历，第一趟记录链表的总长度n，第二趟跑n-k长度。

/*
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 || k <= 0){
            return null;
        }
        
        int cntNode = 0;
        ListNode p = head;
        while(p != null){
            p = p.next;
            ++cntNode;
        }
        if(cntNode < k){
            return null;
        }
        int i = cntNode - k;
        while(i-- != 0){
            head = head.next;
        }
        return head;
    }
}

解法二：

利用快慢双指针，当快指针到达k位置时，慢指针开始启动，一旦快指针到达终点(指向null)时，慢指针到达倒数k位置。

/*
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 || k <= 0){
            return null;
        }
        
        ListNode fast = head;
        ListNode slow = head;
        
        for(int i = 1; i < k; ++i){
        	//如果指针还没到达k的位置就指向了null
        	//那么k的长度超过链表的长度返回null
            if(fast.next != null){
                fast = fast.next;
            }
            else{
                return null;
            }
        }
        //fast一直跑直到链表尾部的下一节点 null
        while(fast.next != null){
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
}

剑指Offer_13

发表于 2017-12-01 | 分类于剑指Offer

题目

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

解题思路

解法一：
时间复杂度高O(n^2)，但是不占额外的内存空间

public class Solution {
    private void exchange(int []array, int i, int j){
        int temp = array[i]; 
        array[i] = array[j];
        array[j] = temp;
    }
    
    private boolean isOdd(int x){
        return x % 2 == 1;
    }
    
    private boolean isEven(int x){
        return x % 2 == 0;
    }
    
    public void reOrderArray(int [] array) {
        if(array == null || array.length == 0){
            return;
        }
        //冒泡算法，将后置位的奇数和它的前值位的偶数进行顺序交换
        for(int i = 1; i < array.length; ++i){
            for(int j = i; j > 0 && isEven(array[j-1]) && isOdd(array[j]); --j){
                exchange(array, j-1, j);
            }
        }
    }
    
    
}

解法二：
时间复杂度和空间复杂度都为O(n)
两个数组分别储存奇数和偶数

public class Solution {
    public void reOrderArray2(int [] array) {
        if(array == null || array.length == 0){
            return;
        }
        List<Integer> oddList = new ArrayList<>();
        List<Integer> evenList = new ArrayList<>();
        for(int i = 0; i < array.length; ++i){
            if(isOdd(array[i])){
                oddList.add(array[i]);
            }
            else{
                evenList.add(array[i]);
            }
        }
        for(int i = 0; i < oddList.size(); ++i){
            array[i] = oddList.get(i);
        }
        //array[i]的位置记得加上odd.size()
        for(int i = 0; i < evenList.size(); ++i){
            array[oddList.size() + i] = evenList.get(i);
        }
    }
}

剑指Offer_12

发表于 2017-12-01 | 分类于剑指Offer

题目

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

解题思路

举个例子：3的11次方
直接将3累乘11次肯定不是一个优解方案。
3的11次方可以写成3 ^(1101)
等价于 (3的1次方) (3的0次方) (3的4次方) (3 的8次方);
ret = (3) (1) (3 3 3 3) (3 3 3 3 3 3 3 3 )

public class Solution {
    public double Power(double base, int exponent) {
        if(exponent == 0){
            return 1.0;
        }
        if(base == 0){
            return 0.0;
        }
        int p = Math.abs(exponent);
        double ret = 1.0;
        
        while(p != 0){
            if((p & 1) == 1){
                ret *= base;
            }
            p >>= 1;
            base *= base;
        }
        return exponent > 0 ? ret : 1 / ret;
  }
}

剑指Offer_11

发表于 2017-11-30 | 分类于剑指Offer

题目

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

解题思路

解法一：
对于输入的n不做改变，使用flag = 1对n的每一位进行检查是否等于1

public class Solution {
    public int NumberOf1(int n) {
		int cnt = 0;
        int flag = 1;
        while(flag != 0){
            if((flag & n) != 0){
                ++cnt;
            }
            flag <<= 1;
        }
        
        return cnt;
    }
}

解法二：
每次循环检查n的末位，是否等于1
利用java的 >>>
逻辑右移或叫无符号右移运算符“>>>“只对位进行操作，没有算术含义，它用0填充左侧的空位。

public class Solution {
    public int NumberOf1(int n) {
    	int cnt = 0;
    
        while(n != 0){
            if((n & 1) == 1){
				++cnt;
            }
            n >>>= 1;
        }
        
        return cnt;
    }
}

剑指Offer_10

发表于 2017-11-30 | 分类于剑指Offer

题目

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

解题思路

找规律（斐波那契数列）

a. 当target <= 2时，直接返回target
b. 当target == n时，分两种情况，如下图

点我进行加载

public class Solution {
    public int RectCover(int target) {
    	if(target <= 2){
            return target;
        }
        else{
            return RectCover(target - 1) + RectCover(target -2);
        }
    }
}

剑指Offer_9

发表于 2017-11-30 | 分类于剑指Offer

题目

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

解题思路

对于每个台阶来说，青蛙都可以选择踩不踩

public class Solution {
    public int JumpFloorII(int target) {
        if(target <= 1){
            return target;
        }
        return (int)Math.pow(2, target-1);
    }
}

不用Math的函数

1	return 1 << --target;

剑指Offer_8

发表于 2017-11-30 | 分类于剑指Offer

题目

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

解题思路

找规律（斐波那契数列的应用）

a. 假设第一次跳1阶，那么剩下的跳法为f(n-1)
b. 假设第一次跳2阶，那么剩下的跳法为f(n-2)
c. 结合a,b考虑来看，总跳法为f(n) = f(n-1) + f(n-2)
d. 并且当n <= 2时, 跳法为n

public class Solution {
    public int JumpFloor(int target) {
		if(target <= 2){
            return target;
        }
        else{
            return JumpFloor(target - 1) + JumpFloor(target - 2);
        }
    }
}

剑指Offer_7

发表于 2017-11-30 | 分类于剑指Offer

题目

大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项。
n<=39

解题思路

斐波那契数列
[1, 1, 2, 3, 5, 8, 13, 21 , …]

public class Solution {
    public int Fibonacci(int n) {
		if(n == 0){
            return 0;
        }
        else if( n == 1 || n == 2){
            return 1;
        }
        int f1 = 1;
        int f2 = 1;
        for(int i = 3; i < n; ++i){
            int temp = f2;
            f2 = f1 + f2;
            f1 = temp;
        }
        return f1 + f2;
    }
}

剑指Offer_6

发表于 2017-11-30 | 分类于剑指Offer

题目

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

解题思路

相当于求数组中最小的元素

输入的数组：非递减数组的旋转。

例如在数组[3, 4, 5, 1, 2]中，我们要找的元素是1，需要从两边往中间逼近，并且当hi-lo <= 1，lo就是最小值的位置（也是查找结束的条件），那么二分查找即可。

import java.util.ArrayList;
public class Solution {
    public int minNumberInRotateArray(int [] array) {
        if(array.length == 0){
            return 0;
        }
        int lo = 0;
        int hi = array.length - 1;
        int mid = -1;
        for( ; ; ){
            if(hi - lo <= 1){
                mid = hi;
                break;
             }
            
            mid = (lo + hi) / 2;
            
            //当array[lo] <= array[mid]， mid左边的元素都小于mid， 向中间逼近
            if(array[lo] <= array[mid]){
                lo = mid;
            }
            //当array[lo] > array[mid]时，比如[3, 4, 5, 1, 2]中的4[lo]和1[mid]
            //此时由右往中间逼近 
            else{
                hi = mid;
            }
        }
        return array[mid];
    }
}