剑指offer三五题-3

题目描述

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

保证base和exponent不同时为0

题解

取次数绝对值,对底数累乘,然后根据次数正负返回结果或其倒数。

public class Solution {
    public double Power(double base, int exponent) {
        if(base == 0.0){
            return 0.0;
        }

        double result = 1.0d;
        int e = exponent>0?exponent:-exponent;
        for(int i=1; i<=e; i++){
            result *= base;
        }
        return exponent>0?result:1/result;
  }
}

题目描述

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

题解

从左到右遍历数组,遇到偶数不操作,遇到奇数,则将其移到偶数前。

public class Solution {
    public void reOrderArray(int [] array) {
        int length = array.length;
        int odd = 0;
        int even = 0;                           //even用于遍历数组使用,odd用于定位
        while (even < length){
            if (array[even]%2 != 0){
                int temp = array[even];
                for (int i = even; i>odd; i--){
                    array[i] = array[i-1];
                }
                array[odd] = temp;
                odd++;
                even++;
            }else {
                even++;
            }
        }
    }
}

题目描述

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

题解

设两个间隔为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){
            return null;
        }
        ListNode p = head;
        ListNode q = head;

        for(int i=0; i<k; i++){
            if(q == null){
                return null;
            }
            q = q.next;
        }
        while(p!=null&&q!=null){
            p = p.next;
            q = q.next;
        }
        return p;
    }
}

题目描述

输入一个链表,反转链表后,输出新链表的表头。

题解

为了保证链表在反转的过程中不断,需要定义两个节点pre和next来存储正在操作的节点的前节点和后节点,然后再将节点的指向反转,如此遍历,直到next为空时,返回pre。

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode ReverseList(ListNode head) {
        ListNode pre = null;
        ListNode next = head;

        while(next != null){
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }
}

题目描述

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

题解

递归解法

/*
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(list2.next, list1);
            return list2;
        }
    }
}

   转载规则


《剑指offer三五题-3》 帅张 采用 知识共享署名 4.0 国际许可协议 进行许可。
  目录