摘要：程序員面試金典題目字符串確定兩個(gè)字符串同構(gòu)的字符重新排列后，能否變成詳細(xì)第一步先判斷兩個(gè)字符串的長(zhǎng)度是否相等字符串的長(zhǎng)度為有括號(hào)數(shù)組清除二維數(shù)組行列將數(shù)組中所有為的元素所在的行列都置為讀數(shù)據(jù)和寫(xiě)數(shù)據(jù)必須分開(kāi)。

StringA的字符重新排列后，能否變成StringB 詳細(xì)

import java.util.*;

public class Same {
    public boolean checkSam(String stringA, String stringB) {
        // write code here
        if(stringA.length()!=stringB.length())
            return false;
        int[] recoder = new int[256];
        for(int i=0;i
tips:

第一步先判斷兩個(gè)字符串的長(zhǎng)度是否相等

字符串的長(zhǎng)度為.length()有括號(hào)



1.7 數(shù)組 清除二維數(shù)組行列
將數(shù)組中所有為0的元素所在的行列都置為0
import java.util.*;

public class Clearer {
    public int[][] clearZero(int[][] mat, int n) {
        // write code here
        boolean[] row = new boolean[n];
        boolean[] col = new boolean[n];
        for(int i=0;i
tips
讀數(shù)據(jù)和寫(xiě)數(shù)據(jù)必須分開(kāi)。



1.8字符串    翻轉(zhuǎn)子串
檢查string2是否為sting1旋轉(zhuǎn)而成
public boolean checkReverseEqual(String s1, String s2) {
        // write code here
        if (s1 == null || s2 == null || s1.length() != s2.length())
            return false;
        return (s1+s1).contains(s2);
    }
tips
旋轉(zhuǎn)問(wèn)題：先將string1 收尾拼接，再檢查新的字符串是否含有s2.



2.2鏈表    鏈表中倒數(shù)第k個(gè)結(jié)點(diǎn)
輸入一個(gè)鏈表，輸出該鏈表中倒數(shù)第k個(gè)結(jié)點(diǎn)
public ListNode FindKthToTail(ListNode head,int k) {
        //需不需要new？？？
        //ListNode headp = new ListNode(-1);
        if(head == null||k<1) return null;
        ListNode tailp = head;
        ListNode headp = head;
        for(int i=1;i
tips

new一個(gè)obj1對(duì)象，然后obj1 = obj2 ,錯(cuò)錯(cuò)錯(cuò)

核心思想：兩個(gè)指針，相差k-1，tail指到尾，則前指針正好找到想要的位置。

另外一種思路是采用遞歸，head==null時(shí)，將count置零，之后count++。




2.3鏈表    訪問(wèn)單個(gè)節(jié)點(diǎn)的刪除
刪除單向鏈表中間的某個(gè)結(jié)點(diǎn)，并且只能訪問(wèn)該結(jié)點(diǎn)
public boolean removeNode(ListNode pNode) {
        // write code here
        if(pNode == null || pNode.next == null)
            return false;
        pNode.val = pNode.next.val;
        pNode.next = pNode.next.next;
        return true;
    }
tips
只能訪問(wèn)該節(jié)點(diǎn)，則不能刪除該節(jié)點(diǎn)，因?yàn)閯h除之后則鏈表與前面斷開(kāi)鏈接，所有只能修改該節(jié)點(diǎn)的值為下一節(jié)點(diǎn)的值，再指向下下節(jié)點(diǎn)。



2.5鏈表    鏈?zhǔn)紸+B
鏈表頭為個(gè)位，A{1,2,3},B{3,2,1},則返回{4,4,4}
public ListNode plusAB(ListNode a, ListNode b) {
        // write code here
        int flag = 0;
        ListNode result = new ListNode(-1);
        ListNode phead = result;
        while(a!=null || b!=null || flag!=0){
            int sum = flag;
            if(a!=null){
                sum+=a.val;
                a = a.next;
            }
            if(b!=null){
                sum+=b.val;
                b = b.next;
            }
            int val = sum%10;
            flag = sum/10;
            result.next = new ListNode(val);
            result = result.next;
        }
        return phead.next;
    }
tips

之前有一個(gè)想法就是先相加公共部分，然后處理多出來(lái)的部分，這樣處理起來(lái)非常麻煩。

如果鏈表頭為高位，則采用棧方法處理。先對(duì)兩個(gè)鏈表分別壓棧，最后弾棧，直至兩個(gè)都為空并且進(jìn)位等于0。




2.7鏈表    回文鏈表
檢查鏈表是否為回文,{1,2,3,2,1},返回true
 public boolean isPalindrome(ListNode pHead) {
        // 快慢指針
        ListNode fast = pHead;
        ListNode slow = pHead;
        Stack stack = new Stack<>();
        while(fast != null && fast.next != null){
            stack.push(slow.val);
            slow = slow.next;
            fast = fast.next.next;     
        }
        if(fast != null)
              slow = slow.next;
        while(slow != null){
            if(slow.val != stack.pop())
                return false;
            slow = slow.next;
        }
        return true;      
    }
    
    public boolean isPalindrome(ListNode pHead) {
        //雙棧
        if(pHead == null || pHead.next == null)
            return true;
        Stack stack1 = new Stack();        
        Stack stack2 = new Stack();

        while(pHead!=null){
            stack1.push(pHead.val);
            pHead = pHead.next;    
        }
        while(stack1.size()>stack2.size()){
            stack2.push(stack1.pop());
        }
        if(stack2.size()>stack1.size()){
            stack2.pop();
        }
        while(!stack1.empty() && !stack2.empty()){
            if(stack1.pop() != stack2.pop())
                return false;
        }
        return true;
            
    }

tips

方案1：用快慢指針，當(dāng)快指針指向鏈表尾部時(shí)，慢指針正好指向中部，并且將慢指針壓棧，這里要注意奇偶數(shù)的區(qū)別。

方案2：先將所有鏈表數(shù)據(jù)壓到棧1，然后彈出一半到棧2，兩者再進(jìn)行比較。不過(guò)該方法顯然沒(méi)有方法一效率高。




3.5棧和隊(duì)列    用兩個(gè)棧實(shí)現(xiàn)隊(duì)列
public class Solution {
    Stack stack1 = new Stack();
    Stack stack2 = new Stack();
     
    public void push(int node) {
        stack1.push(node);
    }
     
    public int pop() {
        if(stack1.isEmpty() && stack2.isEmpty()){
            throw new RuntimeException("the queue is empty!");
        }
        if(stack2.isEmpty()){
          while(!stack1.isEmpty()){
              stack2.push(stack1.pop());
          }
        }
        return stack2.pop();
         
    }
}
tips
throw new RuntimeException("the queue is empty!");下次可以用



3.6棧和隊(duì)列    雙棧排序
要求只有一個(gè)緩存棧，并且排好序的棧最大元素在棧頂。
 public ArrayList twoStacksSort(int[] numbers) {
        // write code here
        ArrayList arrayList = new ArrayList();
        Stack stack1 = new Stack();
        Stack stack2 = new Stack();
         
        for(int i=0;itemp){
                stack1.push(stack2.pop());
            }
            stack2.push(temp);
        }
         
        while(!stack2.isEmpty()){
            arrayList.add(stack2.pop());
        }
        return arrayList;
    }

tips
while(!stack2.isEmpty() && stack2.peek()>temp){
        stack1.push(stack2.pop());
     }
stack2.push(temp);

代碼的簡(jiǎn)潔性!思維不要太僵硬，可以多層條件一起考慮，不必非要一層一層考慮分析。

不要先考慮stack2是否為空，再嵌套考慮棧頂是否大于temp。。。



4.1 樹(shù) 檢查二叉樹(shù)是否平衡
樹(shù)的平衡指左右高度相差不能大于1
public boolean isBalance(TreeNode root) {
        // 遍歷整個(gè)樹(shù)的所有節(jié)點(diǎn)
        if(root == null)return true;
        int left = getHeight(root.left);
        int right = getHeight(root.right);
        int cha = Math.abs(left-right);
        if(cha>1)return false;
        else return true;
    }
    public int getHeight(TreeNode root){
        if(root == null) return 0;
        int left = getHeight(root.left);
        int right = getHeight(root.right);
        return Math.max(left,right)+1;
    }
另一種解法：一邊檢查高度一邊檢查是否平衡

public boolean isBalance(TreeNode root) {
        // write code here
        if(root == null)return true;
        if(getHeight(root) == -1)return false;
        return true;
    }
    public int getHeight(TreeNode root){
        if(root == null) return 0;
        int left = getHeight(root.left);
        if(left == -1) return -1;
        int right = getHeight(root.right);
        if(right == -1) return -1;
        if(Math.abs(left-right)>1) return -1;
        else return Math.max(left,right)+1;
    }
tips
這樣的改進(jìn)的好處在于不用遍歷所有的樹(shù)節(jié)點(diǎn)


4.3最小二叉查找樹(shù)
給定一個(gè)元素各不相同的升序數(shù)組，生成一個(gè)最小二叉查找樹(shù)
public TreeNode creatBST(int[] arr,int start,int end){
    if(start>end)return null;
    int mid = (start+end)>>1;
    TreeNode n = new TreeNode(arr[mid]);
    n.left = creatBST(arr,start,mid-1);
    n.right = creatBST(arr,mid+1;end);
    return n;
}
tips
二叉查找樹(shù)：數(shù)組的中間值為根，根的左子樹(shù)元素值全部小于根節(jié)點(diǎn)值，根的右子樹(shù)大于根節(jié)點(diǎn)。



4.4 樹(shù) 輸出單層節(jié)點(diǎn)
給定一顆二叉樹(shù)，創(chuàng)建含有某一深度上所有結(jié)點(diǎn)的鏈表。
 private ListNode result= new ListNode(-1);
    public ListNode getTreeLevel(TreeNode root, int dep) {
        // write code here
        ListNode list = result;
        getTree(root,dep,1);
        return list.next;
        
    }
    public void getTree(TreeNode root,int dep,int i){
        if(root == null) return;
        if(i == dep){
            result.next = new ListNode(root.val);
            result = result.next;
        }else{
            getTree(root.left,dep,i+1);
            getTree(root.right,dep,i+1);
        }
            
    }


4.5 樹(shù) 檢查是否為BST(二叉查找樹(shù))
int former = Integer.MIN_VALUE;
    public boolean checkBST(TreeNode root){
        if(root == null) return true;
        if(!checkBST(root.left)) return false;
        if(root.val <= former) return false;
        former = root.val;
        if(!checkBST(root.right)) return false;
        return true;
    }
tips

先序遍歷：左中右順序，這樣保證每一個(gè)元素值比上一個(gè)元素值大即可。

對(duì)上一層返回?cái)?shù)據(jù)的處理：if語(yǔ)句

Integer.MIN_VALUE即min-value是Integer類里面的變量值。