1.数值的整数次方

题目描述
给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。
注意点：
1.exponent可以是负数，可以是0，可以是正数。
result等于exponent次的base乘积；如果是负数，result等于exponent次的base乘积的倒数；如果是0，除了base==0时，全都返回1（0的0次方无意义）
2.如果exponent是负数，base=0的时候，是没有意义的，这时应该报错
3.判断double类型是否相等时，不能直接==，而要使用精度判断（一般差值小于1e-即认为相等）

思路：
一个优化的表达。如果exponent是偶数，base^exponent = base^{(exponent/2)*base}(exponent/2)；如果是奇数，base^exponent = base^{(exponent/2)*base}(exponent/2)*base

public class Solution {
    public double Power(double base, int exponent) {
        if(isEqual(base,0.0)&&exponent<=0){
            System.out.println("No meaningful input");
            return 0;
        }
        double result;
        if(exponent<0){
            result = getAbsPower(base,Math.abs(exponent));
            result = 1.0/result;
        }else{
            result = getAbsPower(base,exponent);
        }
        return result;
    }
    public double getAbsPower(double base,int absExponent){
        if(absExponent==0){
            return 1;
        }
        if(absExponent==1){
            return base;
        }
        double result=1;
        double halfResult = getAbsPower(base,absExponent>>1);
        result = halfResult*halfResult;
        if((absExponent&1)!=0){
            result*=base;
        }
        return result;
    }
    public boolean isEqual(double a,double b){
        return Math.abs(a-b)<0.0000001d;
    }
}

2.调整数组顺序使奇数位于偶数前面

题目描述
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
思路：
1.类似插入排序。O(n^2)时间复杂度，O(1)空间复杂度。
将奇数前插，然后其余元素后移即可。直到最后遍历完整个数组
2.借助辅助数组。O(n)时间复杂度，O(n)空间复杂度。
先遍历一遍整个数组，找到奇数个数n。拷贝数组，然后对拷贝数组进行遍历，奇数依次从头赋值到原数组；偶数从下标n开始插入。
注意
1.数组拷贝的方式：
int[] dst = Arrays.copyOf(int[] src,int length)
int[] dst = Arrays.copyOfRange(int[] src,int from,int to)
System.arraycopy(int[] src,int srcStart,int[] dst,int dstStart,int copyLength);
2.考虑可扩展性，抽出判断部分单独成函数

import java.util.Arrays;
public class Solution {
    public void reOrderArray(int [] array) {
        int oddCount=0;
        for(int i=0;i<array.length;i++){
            if(isOdd(array[i]))oddCount++;
        }
        if(oddCount==0||oddCount==array.length)return;
        int[] temp = Arrays.copyOf(array,array.length);
        int oddPointer =0;
        int evenPointer = oddCount;
        for(int i=0;i<temp.length;i++){
           if(isOdd(temp[i])){
               array[oddPointer++] = temp[i];
           }else{
               array[evenPointer++] = temp[i];
           }
        }
    }
    public boolean isOdd(int i){
        return (i&1)==1;
    }
}

3.链表中倒数第k个节点

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

思路：
如果不想遍历两遍，可以使用两个指针pre和after，pre先走k步，after再走。这样，当pre到达链表结尾的时候，after指向的节点就是倒数第k个节点

注意点
1.k==0时，直接return null
2.链表的长度可能小于k，此时也返回null

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

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {
        int pre=0;
        if(k==0){
            return null;
        }
        ListNode kthNode=null;
        ListNode node = head;
        while(node!=null){
            pre++;
            if(pre==k){
                kthNode = head;
            }else if(pre>k){
                kthNode = kthNode.next;
            }
            node = node.next;
        }
        return kthNode;
    }
}

4.反转链表

题目描述
输入一个链表，反转链表后，输出新链表的表头。
注意：
1.结束条件 current.next==null，reverseHead = current
2.链表反转后，尾节点后跟null(head节点也要注意反转啊)
3.保存current.next防止断裂

/*
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)return head;
        ListNode pre = null;
        ListNode mid = head;
        ListNode reverseHead = null;
        while(mid!=null){
            ListNode after = mid.next;
            mid.next = pre;
            if(after==null){
                reverseHead = mid;
                break;
            }
            pre = mid;
            mid = after;
        }
        return reverseHead;
    }
}

5.合并两个排序链表

题目描述
输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
/*
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&&list2==null)return null;
        if(list1==null)return list2;
        if(list2==null)return list1;
        ListNode newList; 
        if(list1.val<=list2.val){
            newList = new ListNode(list1.val);
            newList.next = Merge(list1.next,list2);
        }else{
            newList = new ListNode(list2.val);
            newList.next = Merge(list1,list2.next);
        }
        return newList;
    }
}

6.数的子结构

题目描述
输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

这题注意点在于，子结构不等于子树，A中包含一部分B即可

/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

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

    }

}
*/
public class Solution {
    public boolean HasSubtree(TreeNode root1,TreeNode root2) {
        if(root2==null||root1==null){
            return false;
        }else if(root1.val==root2.val&&isContainTree(root1,root2)){
            return true;
        }else{
            return HasSubtree(root1.left,root2)||HasSubtree(root1.right,root2);
        }
    }
    public boolean isContainTree(TreeNode root1,TreeNode root2){
        if(root2==null&&root1==null){
            return true;
        }else if(root1==null){
            return false;
        }else if(root2==null){
            return true;
        }else if(root1.val!=root2.val){
            return false;
        }else{
            return isContainTree(root1.left,root2.left)&&isContainTree(root1.right,root2.right);
        }
    }
}

如果是子树：把root2==null这个判断里的return true改成return false