1、字符串反轉(zhuǎn)

• 寫一個方法，要求：輸入一個字符串ABCDEFG，要求倒序輸出GFEDCBA：

    // 方法1 - 使用for循環(huán)倒序遍歷字符輸出
    public String formatStr1(String str) {
        int length = str.length();
        StringBuilder sb = new StringBuilder();
        for (int index = length - 1; index >= 0; index--) {
            sb.append(str.charAt(index));
        }
        return sb.toString();
    }
  
    // 方法2 - 使用StringBuilder或StringButter提供的reverse方法實現(xiàn)反轉(zhuǎn)
    public String formatStr2(String str) {
        StringBuilder sb = new StringBuilder(str);
        return sb.reverse().toString();
    }
  

• reverse()方法的實現(xiàn)原理：通過查看StringBuilder和StringBuffer的源代碼，我們發(fā)現(xiàn)reverse()方法由它們的公共父類AbstractStringBuilder實現(xiàn)，具體如下：

    public AbstractStringBuilder reverse() {
        boolean hasSurrogates = false;
        int n = count - 1;
        for (int j = (n-1) >> 1; j >= 0; j--) {
            int k = n - j;
            char cj = value[j];
            char ck = value[k];
            value[j] = ck;
            value[k] = cj;
            if (Character.isSurrogate(cj) ||
                Character.isSurrogate(ck)) {
                hasSurrogates = true;
            }
        }
        if (hasSurrogates) {
            reverseAllValidSurrogatePairs();
        }
        return this;
    }
  

• 如果你看不懂上面這段代碼，那就看看下面這個方法，你就能明白它的實現(xiàn)原理了：

    // 方法3 - 折半交換字符
    public String formatStr3(String str) {
        char[] ch = str.toCharArray(); // 字符串轉(zhuǎn)為char數(shù)組
        int n = ch.length - 1;
        int middle = n >> 1; // 取中間數(shù)
        // 以中間字符為界限，左右兩邊字符交換 相比較方法1減少近一半循環(huán)
        // 如字符串長度為7，則 n = 6，middle = 3，將 0 1 2 3 和 6 5 4 3 交換
        // 如字符串長度為6，則 n = 5，middle = 2，將 0 1 2 和 5 4 3 交換
        for (int j = middle; j >= 0; j--) { 
            int k = n - j;
            char cj = ch[j];
            char ck = ch[k];
            ch[j] = ck;
            ch[k] = cj;
        }
        return new String(ch);
    }
  

小結(jié)：

• 我們介紹了字符串反轉(zhuǎn)的三種方法：
  1、倒序循環(huán)遍歷字符串中每個字符，然后輸出；
  2、使用StringBuilder或StringButter提供的reverse方法；
  3、手動使用折半交換字符的方法，減少了近一半循環(huán)次數(shù)。

2、求兩個字符串的交集

版本1：查找下面兩個字符串中的相同元素并輸出

String stra = "莊周,甄姬,劉禪,姜子牙,孫臏,魯班七號,廉頗";
String strb = "莊周,劉禪,廉頗,程咬金,羋月,鐘無艷";

• 解決方法
  分割字符串為字符數(shù)組，依次比對兩個字符數(shù)組中的元素，相同的輸出。

• 實現(xiàn)代碼

    public void findSameStr(String stra , String strb) {
  
        String[] sa = stra.split(",");
        String[] sb = strb.split(",");
  
        int lengtha = sa.length;
        int lengthb = sb.length;
  
        for (int i = 0; i < lengtha; i++) {
            for (int j = 0; j < lengthb; j++) {
                if (sa[i].equals(sb[j])) {
                    System.out.println(sa[i]);
                    break;
                }
            }
        }
    }
  

版本2：從兩個字符串中找出最長的相同字符串序列

String stra = "abchelHelouyouarmabc";
String strb = "You are my Hello abcd, hello";

• 分析思路
  1、從第一個字符串中找出所有的子字符串元素；
  2、從第二個字符串中查找是否存在該字符串；
  3、例如第一個字符串中子字符串的組合有："ab","abc","abch" ... "bc"，從第二個字符串中查找是否還有這些子字符串組合；
  4、題目要求的要找到最長的相同字符序列，所以我們從第一個字符串中找出子字符串時就要遵循先長后短的順序；
  5、比如字符串"abcdefghi"，長度為9，我們查找它的子字符串首先就應該是它本身，然后找8個長度的子字符串為："abcdefghi"和"bcdefghi"，然后找7個長度的字符串："abcdefg"和"bcdefgh"以及"cdefghi"，以此類推；
  6、因為我們查找子字符串時遵循的先長后短的原則，所以當我們找到第二個字符串中也存在此子字符串時，那就說明這個子字符串就是答案。

• 實現(xiàn)代碼

    public String[] findSameStr(String strs, String strl) {
        if (strs.length() > strl.length()) { // 保證第一個參數(shù)是短字符串
            return findSameStr(strl, strs);
        }
  
        int length = strs.length();
        boolean isSearched = false; // 是否已找到
        ArrayList<String> mList = new ArrayList<>(); // 存儲查找到的字符串
  
        for (int i = length; i >= 0; i--) { // 外層循環(huán)控制查找子字符串的長度i
            for (int j = 0; j <= length - i; j++) { // 內(nèi)層循環(huán)控制開始查找的位置j，查找長度i，所以分割字符串時第二個參數(shù)即為i + j
                String temp = strs.substring(j, i + j); // 分割字符串 參數(shù)舉例：(0,9)、(0,8)(1,9)、(0,7)(1,8)(2,9)
                if (strl.contains(temp)) { // 該子字符串存在于另一個字符串中
                    mList.add(temp);
                    isSearched = true;
                }
            }
            if (isSearched) {
                break;
            }
        }
        if (list.size() > 0) {
            return list.toArray(new String[list.size()]);
        }
        return null;
    }
  

3、手動實現(xiàn)String的index方法

public int index(String src, String des) { // 源字符串,目標字符串
    int index = -1;
    int lenS = src.length();
    int lenD = des.length();
    for (int i = 0; i < lenD; i++) {
        if (des.charAt(i) == src.charAt(0)) { // 找到第一個符合的字符
            if (lenD - i < lenS) { // 目標字符串從i位置開始剩下的字符數(shù) < 源字符串數(shù)
                break;
            }
            index = i;
            for (int n = i + 1, j = 1; j < lenS && n < lenD; j++, n++) {
                if (des.charAt(n) != src.charAt(j)) { // 出現(xiàn)差異，break，重新查找
                    index = -1;
                    break;
                }
            }
        }
        if (index > -1) {
            break;
        }
    }
    return index;
}

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

假設(shè)這兩個棧分別為s1，s2

• 分析思路
  1、棧的特性為：先進后出；隊列的特性為：先進先出；
  2、如一個數(shù)組 data[0] ~ data[n - 1] ，我們將它壓入s1棧中，那么 data[0]在棧底，data[n - 1]在棧頂；
  3、如果我們對s1棧中的元素執(zhí)行出棧操作，并將出棧元素壓入s2棧中，那么在s2棧中data[n - 1]在棧底，data[0]在棧頂；
  4、此時s2棧中的元素再次出棧的話，順序即是：按照 data[0] ~ data[n - 1] 的順序進行出棧，這就和隊列先進先出的順序相吻合。
• 實現(xiàn)思路1
  1、把s1作為存儲空間，s2作為臨時空間；
  2、入棧時：把元素壓入s1；
  3、出棧時：把s1中除棧底元素外的所有元素都倒入s2，彈出s1的棧底元素，然后把s2中所有元素倒回s1。
• 實現(xiàn)思路2
  1、把s1作為存儲空間，s2作為臨時空間；
  2、入棧時，判斷s1是否為空：
  如不為空，說明所有元素都在s1，直接將入棧元素壓入s1；
  如為空，將s2中的所有元素倒回s1，再將入棧元素壓入s1；
  3、出棧時，判斷s2是否為空：
  如不為空，直接彈出s2的頂元素并出棧；
  如為空，把s1中除棧底元素外的所有元素都倒入s2，然后彈出s1的棧底元素。
• 實現(xiàn)思路3 - 最佳方案
  1、把s1作為存儲空間，s2作為臨時空間；
  2、入棧時，將元素壓入s1；
  3、出棧時，判斷s2是否為空：
  如不為空，則直接彈出頂元素；
  如為空，把s1中除棧底元素外的所有元素都倒入s2，然后彈出s1的棧底元素。

小結(jié)：

優(yōu)先選擇思路3：只會在s2為空時將s1中的元素倒入s2，避免了反復“倒”棧，僅在需要時才“倒”一次。

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

假設(shè)這兩個隊列分別為q1，q2

• 分析思路
  1、隊列的特性為：先進先出；棧的特性為：先進后出；
  2、如一個數(shù)組 data[0] ~ data[n - 1] ，我們將它加入q1隊列中，那么 data[0] 在隊列頭， data[n - 1] 在隊列尾；
  3、如果我們對q1隊列中的元素執(zhí)行出隊操作，將出隊元素加入q2隊列中，并將q1隊列尾元素彈出，這就和棧先進后出的順序相吻合。
• 實現(xiàn)思路1
  1、把q1作為存儲空間，q2作為臨時空間；
  2、入隊列時：把元素插入q1的隊尾；
  3、出隊列時：把q1隊列中除隊尾元素外的所有元素都依次出隊加入到q2中，彈出q1隊列尾元素，然后把q1和q2隊列互換。
• 實現(xiàn)思路2
  1、把q1作為入隊臨時空間，q2作為出隊存儲空間；
  2、入隊列時：把元素插入q1的隊尾，如果q2不為空，將q2隊列中的元素依次出隊并加入q1隊尾，然后把q1和q2隊列互換；
  3、出隊列時：對q2隊列執(zhí)行出隊列操作。

小結(jié)：

• 思路1在進隊列時直接入隊，而在每次出隊列時都要輪詢一遍隊列；
• 思路2在每次進隊列時都要輪詢一遍隊列，而在出隊列時直接出隊。

6、用兩個線程交替打印數(shù)字1～100

假設(shè)這兩個線程分別為：
thread1 打印 1 3 5 7 9...
thread2打印 2 4 6 8 10...
最終打印結(jié)果為1 2 3 4 5 6 7 8 9 10...

• 分析思路
  題目要求輪流交替打印數(shù)字，那就說明兩個線程同一時間只有一個可以執(zhí)行打印數(shù)字操作。我們就考慮使用鎖機制，保證一個線程先獲得鎖，執(zhí)行完操作后，釋放鎖并喚醒另外一個線程來獲得鎖，重復此操作直到打印結(jié)束

• 實現(xiàn)思路
  1、定義一個全局變量int index = 1; 定義鎖對象byte[] object = new byte[0];
  2、thread1線程獲得object鎖并打印index，執(zhí)行index++，喚醒object鎖上的其它線程(thread2線程)，而后thread1進入wait等待喚醒；
  3、thread2線程的執(zhí)行過程和步驟二類似。

• 實現(xiàn)代碼

  private byte[] object = new byte[0];
  private int index = 1;
  
  private Runnable mRunnable = new Runnable() {
    @Override
    public void run() {
        while (index <= 100) {
            synchronized (object) {
                System.out.print(index);
                index++;
                object.notifyAll();
                try {
                    object.wait();
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }
        }
    }
  };
  
  public void execute() {
    Thread thread1 = new Thread(mRunnable);
    Thread thread2 = new Thread(mRunnable);
    thread1.start();
    thread2.start();
  }
  

• 注意：wait(),notify(),notifyAll()必須在同步方法/代碼塊中調(diào)用

100、經(jīng)典案例

問題描述

• 一個房間有100盞燈（全是關(guān)著的），由編號1-100的開關(guān)（只有兩種狀態(tài)，開或者關(guān)）控制，門外有100個學生，學生按次序一次進入房間，第一個進入的學生切換是1的倍數(shù)的開關(guān)，第二個學生切換是2的倍數(shù)的開關(guān)，以此類推，問，第100學生進入切換后，還有多少盞燈是亮著的？

分析思路

• 一開始燈是關(guān)著的，那么燈被按下奇數(shù)次就還是關(guān)著的，按偶數(shù)下就是開著的；
• 根據(jù)規(guī)則，每個燈被按下多少次取決于這個燈的數(shù)字的約數(shù)有多少個：比如第4個燈會被第 1、2、4 個人按下；再比如第5個燈會被第 1、5 個人按下；
• 所以問題就演變成 1 - 100 這100個數(shù)字中哪些數(shù)的約數(shù)個數(shù)為奇數(shù)。

實現(xiàn)方案

public void findValidNum() {
    int N = 100; // 100個數(shù)字
    for (int i = 1; i <= N; i++) { // 遍歷這些數(shù)字
        int num = 1; // 至少有一個約數(shù)：它本身
        for (int j = 1; j <= i >> 1; j++) { // 除了本身之外最大約數(shù)不應該超過 這個數(shù)字的一半
            if (i >= j && i % j == 0) { // 如果i對j取余等于0說明j是i的約數(shù)
                num++;
            }
        }
        if (num % 2 != 0) { // 余數(shù)個數(shù)為基數(shù)則輸出
            System.out.print(i + ",");
        }
    }
}

未完待續(xù)...