1.數(shù)值的整數(shù)次方

題目描述
給定一個(gè)double類型的浮點(diǎn)數(shù)base和int類型的整數(shù)exponent。求base的exponent次方。
注意點(diǎn)：
1.exponent可以是負(fù)數(shù)，可以是0，可以是正數(shù)。
result等于exponent次的base乘積；如果是負(fù)數(shù)，result等于exponent次的base乘積的倒數(shù)；如果是0，除了base==0時(shí)，全都返回1（0的0次方無意義）
2.如果exponent是負(fù)數(shù)，base=0的時(shí)候，是沒有意義的，這時(shí)應(yīng)該報(bào)錯(cuò)
3.判斷double類型是否相等時(shí)，不能直接==，而要使用精度判斷（一般差值小于1e-即認(rèn)為相等）

思路：
一個(gè)優(yōu)化的表達(dá)。如果exponent是偶數(shù)，base^exponent = base^{(exponent/2)*base}(exponent/2)；如果是奇數(shù)，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.調(diào)整數(shù)組順序使奇數(shù)位于偶數(shù)前面

題目描述
輸入一個(gè)整數(shù)數(shù)組，實(shí)現(xiàn)一個(gè)函數(shù)來調(diào)整該數(shù)組中數(shù)字的順序，使得所有的奇數(shù)位于數(shù)組的前半部分，所有的偶數(shù)位于數(shù)組的后半部分，并保證奇數(shù)和奇數(shù)，偶數(shù)和偶數(shù)之間的相對(duì)位置不變。
思路：
1.類似插入排序。O(n^2)時(shí)間復(fù)雜度，O(1)空間復(fù)雜度。
將奇數(shù)前插，然后其余元素后移即可。直到最后遍歷完整個(gè)數(shù)組
2.借助輔助數(shù)組。O(n)時(shí)間復(fù)雜度，O(n)空間復(fù)雜度。
先遍歷一遍整個(gè)數(shù)組，找到奇數(shù)個(gè)數(shù)n?？截悢?shù)組，然后對(duì)拷貝數(shù)組進(jìn)行遍歷，奇數(shù)依次從頭賦值到原數(shù)組；偶數(shù)從下標(biāo)n開始插入。
注意
1.數(shù)組拷貝的方式：
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.考慮可擴(kuò)展性，抽出判斷部分單獨(dú)成函數(shù)

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.鏈表中倒數(shù)第k個(gè)節(jié)點(diǎn)

題目描述
輸入一個(gè)鏈表，輸出該鏈表中倒數(shù)第k個(gè)結(jié)點(diǎn)。

思路：
如果不想遍歷兩遍，可以使用兩個(gè)指針pre和after，pre先走k步，after再走。這樣，當(dāng)pre到達(dá)鏈表結(jié)尾的時(shí)候，after指向的節(jié)點(diǎn)就是倒數(shù)第k個(gè)節(jié)點(diǎn)

注意點(diǎn)
1.k==0時(shí)，直接return null
2.鏈表的長(zhǎng)度可能小于k，此時(shí)也返回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.反轉(zhuǎn)鏈表

題目描述
輸入一個(gè)鏈表，反轉(zhuǎn)鏈表后，輸出新鏈表的表頭。
注意：
1.結(jié)束條件 current.next==null，reverseHead = current
2.鏈表反轉(zhuǎn)后，尾節(jié)點(diǎn)后跟null(head節(jié)點(diǎn)也要注意反轉(zhuǎn)啊)
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.合并兩個(gè)排序鏈表

題目描述
輸入兩個(gè)單調(diào)遞增的鏈表，輸出兩個(gè)鏈表合成后的鏈表，當(dāng)然我們需要合成后的鏈表滿足單調(diào)不減規(guī)則。
/*
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.數(shù)的子結(jié)構(gòu)

題目描述
輸入兩棵二叉樹A，B，判斷B是不是A的子結(jié)構(gòu)。（ps：我們約定空樹不是任意一個(gè)樹的子結(jié)構(gòu)）

這題注意點(diǎn)在于，子結(jié)構(gòu)不等于子樹，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這個(gè)判斷里的return true改成return false