剑指Offer-合并两个排序的链表

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

非递归实现

public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        ListNode head = new ListNode(0);
        ListNode p = head;
        boolean isFirst = true;
        while(list1 != null && list2 != null){
            if(list1.val < list2.val){
                p.next = list1;
                list1 = list1.next;
            }else{
                p.next = list2;
                list2 = list2.next;
            }
            p = p.next;
        }
        if(list1 != null){
            p.next = list1;
        }
        if(list2 != null){
            p.next = list2;
        }
        return head.next;
    }
    
}

递归实现

public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        if(list1 == null){
            return list2;
        }
        if(list2 == null){
            return list1;
        }
        
        ListNode head = null;
        
        if(list1.val < list2.val){
            head = list1;
            head.next = Merge(list1.next, list2);
        }else{
            head = list2;
            head.next = Merge(list1, list2.next);
        }
        return head;
    }
    
}
2017/3/13 posted in  算法-数据结构
 

剑指Offer-二进制中1的个数

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

思路

  • 方案一:

    将(n&1)可以知道n的最后一位是不是1,然后依次将n不断向右移1位,直到n为0。

public class Solution {
    public int NumberOf1(int n) {
        int count = 0;
        while(n != 0){
            if( (n & 1) == 1){
                count++;
            }
            /*
            *注意,这里是>>>
            *>>为最高位填补符号位,负数会发生错误
            *>>>为最高位填写0
            */
            n = n >>> 1;
        }
        return count;
    }
}
  • 方案二:

    将一个整数减一,都是把最右边的1变成0,如果它的右边还有0的话,所有的0都变成1,而它的左边的所有位都保持不变。若我们将n和n-1做与运算,相当于把它最右边的1变成0。那么,一个整数的二进制表示中有多少个1,就可以进行多少次这样的操作。

public class Solution {
    public int NumberOf1(int n) {
        int count = 0;
        while(n != 0){
            count++;
            n = n & (n-1);
        }
        return count;
    }
}
2017/3/12 posted in  算法-数据结构
 

剑指Offer-递归和循环

求斐波那契额

这个题目非常简单,2分钟就可以解决。直接上代码!

public class Solution {
    public int Fibonacci(int n) {
        if(n <= 0){
            return 0;
        }
        if(n == 1){
            return 1;
        }
        return Fibonacci(n-1)+Fibonacci(n-2);
    }
}

但是,这个解法有很多的问题。当n的值比较大的时候,就会出现栈调用溢出。所以,我们一般在条件允许的情况下,使用循环来替代递归的实现。

public class Solution {
    public int Fibonacci(int n) {
        if(n <= 1){
            return n;
        }
        int number1 = 0;
        int number2 = 1;
        int ans = 0;
        for(int i = 2;i<=n;i++){
            ans = number1 + number2;
            number1 = number2;
            number2 = ans;
        } 
        return ans;
    }
}

跳台阶

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

思路

首先我们考虑最简单的情况。如果只有1级台阶,那显然只有一种跳法。如果有2级台阶,那就有两种跳的方法了:一种是分2次跳,每次跳1级;另外一种就是一次跳2级。
接着我们再来讨论一般情况,我们把n级台阶时的跳法看成是n的函数,记为f(n)。当n>2时,第一次跳的时候就有两种不同的选择:一是一次跳1级,此时跳法数目等于后面剩下的n-1级台阶的跳法数目,即为f(n-1);另一种跳法是一次跳2级,这是跳法数目就是后面剩下n-2级台阶的跳法数目,即f(n-2)。因此n级台阶的跳法数目f(n) = f(n-1) + f(n - 2);

代码

public class Solution {
    public int JumpFloor(int target) {
        if(target <= 2){
            return target;
        }
        int number1 = 1;
        int number2 = 2;
        int ans = 0;
        for(int i = 3;i<=target;i++){
            ans = number1 + number2;
            number1 = number2;
            number2 = ans;
        }
        return ans;
    }
}

变态跳台阶

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

思路

借鉴上面的思路,我们把n级台阶时的跳法看成是n的函数,记为f(n)。此时f(n) = f(n-1) + f(n-2) + ...+ f(1) + 1;经过数学推导可得:f(n) = 2n-1;

代码

public class Solution {
    public int JumpFloorII(int target) {
        return 1 << target-1;
    }
}

矩形覆盖

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

思路

既然放在这个章节,自然是递推解决。当我们使用一个1*2的矩形去覆盖大矩形(2*n)的左侧时,我们有两个选择,横着放或者竖着放。当竖着放时,右边剩下的区域长度就为n-1;当横着放时,左边剩下的区域长度就为n-2。所以可以发现f(n) = f(n-1) + f(n-2)

代码

public class Solution {
    public int RectCover(int target) {
        if(target <=2){
            return target;
        }
        int number1 = 1;
        int number2 = 2;
        int ans = 0;
        for(int i = 3;i <= target;i++){
            ans = number1 + number2;
            number1 = number2;
            number2 = ans;
        }
        return ans;
    }
}
2017/3/11 posted in  算法-数据结构
 

剑指offer-旋转数组的最小数字

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

解题思路

O(n)算法

数组遍历,如果a[i]<a[i-1],这该位置为旋转位置,即最小元素。

O(logn)算法

我们可以通过二分的思路,对上述问题进行优化。
我们发现,旋转之后的数组实际上可以划分为两个排序的子数组,而且后面的子数组的元素都小于等于前面的子数组的元素。而我们要找的这个最小元素,恰好是这两个数组的分界线。
和二分查找一样,我们分别用两个指针指向数组的第一个(start)和最后一个元素(end),在求一个中间指针指向数组的中间(mid = (start+end)/2):

  • 如果array[mid] >= array[end],说明分界值应该在数组的后半段,此时将start赋值为mid;
  • 如果array[mid] <= array[start],说明分界值应该在数组的前半段,此时将end赋值为mid;
  • 如果end-start == 1,说明array[end]为我们要找的分界值。
  • PS.如果 array[mid] == array[start] == array[end],此时只能通过遍历来实现。

代码示例

O(n)

public class Solution {
    public int minNumberInRotateArray(int [] array) {
        if(array.length == 0){
            return 0;
        }
        for(int i=1;i<array.length;i++){
            if(array[i]<array[i-1]){
                return array[i];
            }
        }
        return array[0];
    }
}

O(logn)

public class Solution {
    public int minNumberInRotateArray(int [] array) {
        if (array.length == 0) {
            return 0;
        }
        int start = 0;
        int end = array.length - 1;
        while (end - start > 1) {
            int mid = (start + end) / 2;
            
            if(array[start] == array [mid] && array[mid] == array[end]){
                return order(array, start, end);
            }
            
            if( array[mid] >= array[end]){
                start = mid;
                continue;
            }
            if(array[mid] <= array[start]){
                end = mid;
                continue;
            }
        }
        return array[end];
    }
        
    public int order(int[] array,int start,int end){
        for(int i = start+1;i<=end;i++){
            if(array[i]<array[i-1]){
                return  array[i];
            }
        }
        return array[start];
    }
}
2017/3/10 posted in  算法-数据结构
 

剑指Offer-用两个栈实现队列

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

解决思路

栈是后进先出,而队列是先进先出,在pop的过程上是相反的。所以我们要解决的核心问题就是这样。
Stack1用来push数据,这样,最先进入的元素就成为了Stack1的栈底元素。当我们需要出队时,需要找到第一个进入stack1的元素,于是,我们分别将stack1的元素出栈,压入stack2,这时,stack2中的栈顶元素,就是最开始我们插入栈中的元素,也就是我们要pop的元素。
所以,就有了如下的规则:

  • push操作:压入stack1中;
  • pop操作:如果stack2中有元素,则返回stack2的栈顶元素;若stack2为空,则依次将stack1中的元素出栈,压入stack2中,返回stack2的栈顶元素。

代码如下:

import java.util.Stack;

public class Solution {
    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();
    
    public void push(int node) {
        stack1.push(node);
    }
    
    public int pop() {
        if(stack2.size() > 0 ){
            return stack2.pop();
        }
        
        while(stack1.size() > 0 ){
            stack2.push(stack1.pop());
        }
        return stack2.pop();
    }
}
2017/3/10 posted in  算法-数据结构