算法雖然不是特別簡單，但沒有你想象中的那么難。

Sort Array By Parity easy

AC-17ms.
按照《算法導(dǎo)論》排序一章的一些概念，第二種可以稱為是原址的（in-place)。
First Try:
用了另一個數(shù)組來保存結(jié)果拯刁，如果是奇數(shù)進(jìn)行swap操作，同時在else中還要維護(hù)偶數(shù)的位置正確性逝段。

class Solution {
    public int[] sortArrayByParity(int[] A) {
        int[] result = new int[A.length];
        for (int i = 0,tmp = 0; i < A.length; i++) {
            if (A[i] % 2 == 1) {
                result[A.length - tmp - 1] = A[i];
                tmp ++;
            } else {
                result[i - tmp] = A[i];
            }
        }
        return result;
    }
}

提交后瞄了眼垛玻，發(fā)現(xiàn)可以只操作原數(shù)組割捅，改了一下，這次只需要將even數(shù)據(jù)移到前面即可帚桩。

        for (int i = 0,evenIndex = 0; i < A.length; i++) {
            if (A[i] % 2 == 0) {
                int tmp = A[i];
                A[i] = A[evenIndex];
                A[evenIndex] = tmp;
                evenIndex ++;
            }
        }
        System.err.println(System.nanoTime() - start + "ms.");
        return A;

To Lower Case easy

作了個弊亿驾，逃
str.toLowerCase();
論思路的話，拿到str的char數(shù)組账嚎，判斷是否位于大寫字母的ASCII碼范圍內(nèi)莫瞬，如果是，原有ASCII碼+32存入郭蕉，否則原樣存入疼邀，利用String(char[])構(gòu)造方法返回小寫。大概類似這位老哥的解法戳一下
A的ASCII碼是65恳不，a是97

劍指Offer

二維數(shù)組中的查找

思路： 從右上角（或左上角）開始進(jìn)行判斷檩小。
其他：每一行進(jìn)行二分查找开呐，雖然也可以實現(xiàn)烟勋，但是復(fù)雜度為O(NlgN)，不推薦

public boolean Find(int target, int[][] array) {
        if (array == null || array.length == 0 || array[0].length == 0 ) {
            return false;
        }
        int rows = array.length;//代表行數(shù)
        int cols = array[0].length ;//代表列數(shù)
        if (rows > 0 && cols > 0) {
            int row = 0;
            int column = cols - 1;
            while (row < rows && column >= 0) {
                if (array[row][column] == target) {
                    return true;
                } else if (array[row][column] > target) {
                    column--;
                } else {
                    ++row;
                }
            }
        }
        return false;
    }

替換空格

這里有個有意思的知識點筐付，空格ASCII碼是32,16進(jìn)制表示為0x20卵惦，因此替換時表示為%20；#ASCII碼是35,16進(jìn)制0x23瓦戚，因此替換時表現(xiàn)為%23沮尿；
如果可以新開辟字符串來完成替換，那就比較簡單了较解，現(xiàn)在考慮的是在原有字符串上進(jìn)行替換

思路：空格替換為‘%20’畜疾，原來一個字符，現(xiàn)在就多了2個.注意：setLength的過程其實是找了另一個數(shù)組印衔，將原有數(shù)據(jù)拷貝上去了啡捶，數(shù)據(jù)組成是原有數(shù)據(jù)+新擴(kuò)容的。然后才是移動奸焙。這樣而跟創(chuàng)建一個新數(shù)組瞎暑，然后直接賦值相比，反而有多次一舉之嫌疑与帆。這一點了赌，等什么時候再學(xué)習(xí)一下C/C++時再來對比。用Java里的append和replace有作弊的嫌疑玄糟，因此這里仍舊按照書上思想來實現(xiàn)勿她。不過略有改動，while改成了for循環(huán)阵翎，更簡潔也更容易理解一些逢并。

public String replaceSpace(StringBuffer str) {
        int oldLength = str.length();
        if (oldLength == 0) {
            return str.toString();
        }
        int spaceNum = 0;
        for (int i = 0; i < oldLength; i++) {
            if (str.charAt(i) == ' ') spaceNum++;
        }
        // 計算出替換后的字符串長度
        int newLength = oldLength + spaceNum * 2;
        str.setLength(newLength);
        for (int i = oldLength - 1; i >= 0; i--) {
            if (str.charAt(i) != ' ') {
                str.setCharAt(--newLength, str.charAt(i));
            } else {
                str.setCharAt(--newLength, '0');
                str.setCharAt(--newLength, '2');
                str.setCharAt(--newLength, '%');
            }
        }
        return str.toString();
    }

從尾到頭打印鏈表

注意這里是單鏈表播揪，只有next指針。又學(xué)到一點筒狠，因為是單鏈表猪狈，所以只能從頭到尾遍歷，但是打印又是要從尾到頭打印辩恼，因此就是后進(jìn)入的先出來雇庙，符合LIFO棧的數(shù)據(jù)結(jié)構(gòu)定義，因此可以使用Stack來實現(xiàn)灶伊。（慚愧疆前，Stack還是第一次用呢。另外再說一點聘萨，linkedlist也可以當(dāng)成棧來使用的）

public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        Stack<Integer> stack = new Stack<>();
        while (listNode != null) {
            stack.push(listNode.val);
            listNode = listNode.next;
        }
        ArrayList result = new ArrayList();
        while (!stack.isEmpty()) {
            result.add(stack.pop());
        }
        return result;
    }
// 順便把從頭到尾打印也給寫了一下
public ArrayList<Integer> printListFromHeadToTail(ListNode listNode) {
        ArrayList<Integer> result = new ArrayList<>();
        while (listNode != null) {
            result.add(listNode.val);
            listNode = listNode.next;
        }
        return result;
    }

這里順便還知道了竹椒，遞歸在本質(zhì)上就是一個棧結(jié)構(gòu)。因此還有遞歸寫法如下：

    ArrayList result  = new ArrayList();
    public ArrayList<Integer> printListFromTailToHeadRecursive(ListNode listNode) {

        if (listNode != null) {
            if (listNode.next != null) {
                printListFromTailToHeadRecursive(listNode.next);
            }
            result.add(listNode.val);
        }
        return result;
    }

順便把簡單的鏈表結(jié)構(gòu)也貼上米辐；當(dāng)有了對應(yīng)結(jié)構(gòu)的時候胸完，此時就可以把對應(yīng)的《算導(dǎo)》里面的事項轉(zhuǎn)換成具體的代碼實現(xiàn)了。

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

        ListNode(int val) {
            this.val = val;
        }

    }

重建二叉樹

這里又有個知識點翘贮，寬度優(yōu)先遍歷赊窥，就是一層一層的來，從左到右遍歷輸出狸页。
此問題有一定難度锨能，對應(yīng)回答里有一個高票答案，看起來比較簡潔芍耘，但是易讀性較差址遇。不過，經(jīng)過對比斋竞，遞歸調(diào)用時的參數(shù)是一致的倔约。
這里稍作解釋，constructCore里的參數(shù)窃页，pre和in數(shù)組是不變的跺株，不講；startPreorder是指左孩子前序序列下標(biāo)起點脖卖，endPreorder是左孩子前序序列結(jié)束下標(biāo)乒省；另兩個是中序序列的對應(yīng)參數(shù)。
另外畦木，構(gòu)建右子樹時袖扛，if條件表達(dá)式，有些不是很清楚為何，留作思考蛆封；再者唇礁，對于另一個最優(yōu)解答，找到rootIndex之后惨篱，并不判斷是否需要構(gòu)建左子樹而是直接構(gòu)建盏筐，猜測應(yīng)該是沒進(jìn)for循環(huán)，構(gòu)造了一個null吧砸讳。這兩個問題暫且留作思考琢融。

public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
        if (pre == null || in == null) {
            return null;
        }
        return constructCore(pre, 0, pre.length - 1, in, 0, in.length - 1);
    }

    private TreeNode constructCore(int[] pre, int startPreorder, int endPreOrder, int[] in, int startInorder, int endInorder) {
        if (startPreorder > endPreOrder || startInorder > endInorder)
            return null;
        // 前序遍歷的第一個是root值
        int rootValue = pre[startPreorder];
        TreeNode root = new TreeNode(rootValue);
        int rootInorder = startInorder;

        // 找出內(nèi)部節(jié)點在中序序列中的位置
        for (int i = startInorder; i <= endInorder; i++) {
            if (in[i] == rootValue) {
                rootInorder = i;
                break;
            }
        }
        // 左子樹的長度
        int leftLength = rootInorder - startInorder;
        // 前序序列截止下標(biāo)
        int leftPreorderEnd = startPreorder + leftLength;
        if (leftLength > 0) {
            // 構(gòu)建左子樹
            root.left = constructCore(pre, startPreorder + 1, leftPreorderEnd,
                    in, startInorder, rootInorder - 1);
        }
        if (leftLength < endPreOrder - startPreorder) {
            // 構(gòu)建右子樹
            root.right = constructCore(pre, leftPreorderEnd + 1, endPreOrder,
                    in, rootInorder + 1, endInorder);

        }

        return root;
    }

位運(yùn)算

五種：與、或簿寂、異或漾抬、左移、右移常遂。
異或：同0異1
左移：左移n位纳令，右邊補(bǔ)n個0
右移：數(shù)字是無符號數(shù)值，用0填充克胳；有符號數(shù)值平绩，用符號位填充。（提到有符號數(shù)毯欣，這里會涉及到反碼馒过、補(bǔ)碼臭脓，《計算機(jī)科學(xué)導(dǎo)論》里面有講酗钞，只有哪天再復(fù)習(xí)一下了，只看不記實在是太容易忘記了来累，哈哈砚作，不過再提一下，個人覺得這本書翻譯的有挺多地方都有問題嘹锁，還是要辯證看待葫录。比如：P33 二進(jìn)制補(bǔ)碼表示法范圍分為兩半：0000-0110以及0111-1111，應(yīng)該是0000-0111领猾，1000-1111）
有符號數(shù)：0表示正整數(shù)米同，1表示負(fù)整數(shù)
反碼：無論正負(fù)，簡單反轉(zhuǎn)各個位即可摔竿。參照維基百科反碼解釋面粮，還有一些條件：正數(shù)反碼等于原碼，負(fù)數(shù)反碼等于符號位不變继低，反轉(zhuǎn)其余位熬苍。反碼里有兩個0，+0:0000，-0:1111

反碼實例

補(bǔ)碼實例

補(bǔ)碼

1. 左移：
   1000喘垂，是負(fù)數(shù)，以補(bǔ)碼形式存在绍撞，如何計算其十進(jìn)制是多少呢正勒？
   補(bǔ)碼取反误债，0111扶关，表示的十進(jìn)制數(shù)7，+1得到8闺魏，加上負(fù)號-8.
   而-1 <<2, -1是int非洲，4字節(jié)32位鸭限，二進(jìn)制表示為32個1，左移2位之后變?yōu)?0個1两踏，2個0败京；取反變成30個0,2個1，十進(jìn)制就是3缆瓣，+1得到4喧枷，加負(fù)號為-4.
2. 右移
   正數(shù)補(bǔ)0，負(fù)數(shù)補(bǔ)1
   -1 >> 1 = -1
   3.無符號右移
   無論該數(shù)是正負(fù)，均補(bǔ)0
   -1 >>> 1 = 2147483647 即2^31 - 1,Integer.MAX_VALUE.
   解釋一下隧甚，32個1無符號右移之后變成0跟31個1.即2^0 + 2^1 + 2^2 + ...+2^30 = 2 ^31 - 1;(等比數(shù)列求和)
   再來一個位運(yùn)算交換位置：
   
   image.png
   
   貼一下博主地址
   另外關(guān)于位運(yùn)算再貼一篇文章詳解Java里的位運(yùn)算

二進(jìn)制中的1的個數(shù)

思路：用1和n做與運(yùn)算车荔，如果不是0，則說明n對應(yīng)位置是1
這里if條件用!=0還要更好一些

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

然而這種解法的話至少要循環(huán)32次（int 4字節(jié)32位）戚扳，如果有幾個1就循環(huán)幾次就好了

一個整數(shù)n做運(yùn)算n & (n - 1)可以把n最右側(cè)的1變成0

    public int NumberOf1(int n) {
        int count = 0;
        while (n != 0) {
            count++;
            n &= (n - 1);
        }
        return count;
    }

用兩個棧實現(xiàn)隊列

第一次就AC忧便，哇哇哇。

思路：用stack1來存放push進(jìn)來的值帽借，每次出棧的時候珠增，只要Stack2非空，則先出棧Stack2的數(shù)砍艾；一旦stack2空了蒂教，就立馬取stack1里面已經(jīng)存在的數(shù)，壓入stack2中脆荷，再出棧凝垛。這里沒處理為空時pop（）的邊界問題，因為沒有時蜓谋，pop()也該報錯梦皮，EmptyStackException，Stack類也是這么處理的桃焕。順便再說下pop()和peek(）了剑肯，pop()彈出并返回棧頂?shù)闹担琾eek（）返回棧頂?shù)闹怠?/p>

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.isEmpty()) return stack2.pop();
        while (!stack1.isEmpty()) {
            stack2.push(stack1.pop());
        }
        return stack2.pop();
    }

順便再看看兩個隊列實現(xiàn)一個棧怎么實現(xiàn)：

思路：push時兩個隊列哪個有數(shù)據(jù)观堂，就往哪個push让网；都沒有數(shù)據(jù)，隨便一個push型将。
pop時寂祥，隊列1有n條數(shù)據(jù)，就把前n-1條數(shù)據(jù)放入隊列2七兜，隊列2有數(shù)據(jù)就放到隊列1中去。

    ArrayDeque<Integer> queue1 = new ArrayDeque<>();
    ArrayDeque<Integer> queue2 = new ArrayDeque<>();

    public void stackPush(int node) {
        if (queue1.isEmpty() & queue2.isEmpty()) {
            queue1.add(node);
            return;
        }
        if (queue1.isEmpty()) {
            queue2.add(node);
        } else {
            queue1.add(node);
        }
    }

    public int stackPop() {
        if (queue1.isEmpty() && queue2.isEmpty()) {
            return -1;
        }
        if (queue1.isEmpty()) { // 如果隊列2非空,
            
            while (queue2.size() > 1) {
                queue1.add(queue2.poll());
            }
            return queue2.poll();
        } else { // 隊列1非空
            
            while (queue1.size() > 1) {
                queue2.add(queue1.poll());
            }
            return queue1.poll();
        }

    }

員工年齡排序

參見這篇文章

下標(biāo)對應(yīng)年齡福扬，值對應(yīng)該年齡出現(xiàn)了幾次腕铸；最后一個二重循環(huán)將年齡重新放入ages數(shù)組☆醣看似O(n^2)狠裹，實際上，這個二重循環(huán)只執(zhí)行了ages.length次汽烦。

public void sortAge(int[] ages){
        int oldAge = 70;
        int youngAge = 17;
        int[] timeOfAge = new int[oldAge+1];

        for(int i = youngAge; i <= oldAge; i++){
            timeOfAge[i] = 0;
        }

        for(int j = 0; j < ages.length; j++){
            int a = ages[j];
            timeOfAge[a]++;
        }

        int index = 0;
        for(int i = youngAge; i <= oldAge; i++){
            for(int j = 0; j < timeOfAge[i]; j++){
                ages[index] = i;
                index++;
            }
        }
    }

旋轉(zhuǎn)數(shù)組中的最小數(shù)

這道題就有點奇怪了涛菠，按照書上思路，自己測試一些，也是可以正常輸出的俗冻，但是不知為何礁叔，無法通過OJ

public int minNumberInRotateArray(int[] array) {
        if (array.length < 0) return -1;
        int low = 0, high = array.length - 1;
        int mid = low;// 解決原本就是已排序數(shù)組的問題
        while (array[low] >= array[high]) {
            if (array[low] == array[high] && array[mid] == array[high]) {
                return minInOrder(array, low, high);
            }
            if (low - high == 1) {
                mid = high;
                break;
            }
            mid = (low + high) / 2;
            if (array[mid] >= array[low]) {
                low = mid;
            } else {
                high = mid;
            }
        }
        return array[mid];
    }



    private int minInOrder(int[] array, int low, int high) {
        int result = array[low];
        for (int i = low + 1; i < high; i++) {
            if (result > array[i]) {
                result = array[i];
            }
        }
        return result;
    }

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

這道題簡直太有趣了，將指數(shù)分為奇偶迄薄，基數(shù)就是1半平方再乘base琅关；偶數(shù)不用乘base。注意：0^0在數(shù)學(xué)上是沒意義的讥蔽，這里簡單的處理為1.指數(shù)為負(fù)即為求正數(shù)的倒數(shù)涣易。

public double Power(double base, int exponent) {
       if (exponent == 0) return 1;
       if (exponent == 1) return base;
       if (exponent < 0) return 1/Power(base, -exponent);
       double result = Power(base, exponent >> 1);
       result *= result ;
       if ((exponent & 1) == 1) {
           result *= base;
       }
       return result;
   }

在O(1)時間刪除鏈表節(jié)點
思路：1.遍歷找到待刪除節(jié)點i的前驅(qū)，修改前驅(qū)next指向

2. 不需要遍歷冶伞，將i的后繼值放入i中新症，將i指向i的next的next。不過注意一些邊界情況：（1）刪除的節(jié)點不是tail節(jié)點（2）刪除的鏈表只有一個節(jié)點（3）鏈表有多個節(jié)點响禽，刪除最后一個節(jié)點（4）刪除的節(jié)點是否在鏈表中

將奇數(shù)移到前面偶數(shù)移到后面

先給出不保證順序的版本（即只要奇數(shù)在前就行）账劲，這一點同LeetCode那題基本類似。

public void reOrderArray(int [] array) {
        if (array == null || array.length == 0) return;
        int begin = 0;
        int end = array.length - 1;
        while (begin < end) {
            // 找到偶數(shù)
            while (begin < end && (array[begin] & 1) != 0) {
                begin++;
            }

            // 找到奇數(shù)
            while (begin < end && (array[end] & 1) == 0) {
                end--;
            }

            if (begin < end) {
                int tmp = array[begin];
                array[begin] = array[end];
                array[end] = tmp;
            }
        }
        
    }

再給出有保證順序版本（這個就需要順次移動了）：

if (array == null || array.length == 0) return;
        int begin = 0;
        int end ;
        while (begin < array.length) {
            // 找到偶數(shù)
            while (begin < array.length && (array[begin] & 1) != 0) {
                begin++;
            }

            end = begin + 1;

            // 找到奇數(shù)
            while (end < array.length && (array[end] & 1) == 0) {
                end++;
            }

            if (end < array.length) {
                int tmp = array[end];
                // 這里只能采取從后往前的方式
                for (int i = end - 1; i >= begin; i--) {
                    array[i+1] = array[i];
                }
                array[begin++] = tmp;
                System.err.println(Arrays.toString(array));
            } else {
                break;
            }
        }

話說魯棒性金抡，這個光從漢語意義上講實在是讓人費(fèi)解的很啊╮(╯▽╰)╭

鏈表中倒數(shù)第k個結(jié)點

思路: 兩個指針瀑焦，一個先跑k-1次，另一個再開始跑

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

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {
        // 代表走到第幾個節(jié)點
        int count = 0;
        ListNode first = head, second = head ;
        while (first != null) {
            first = first.next;
            count ++;
            // 當(dāng)?shù)谝粋€鏈表走到k- 1時梗肝，第二個鏈表也跑起來
            if (count > k ) {
                second = second.next;
            }
        }
        // 如果鏈表的數(shù)量還不足k個
        if (count < k) return null;
        return second;
    }
}