算法汇总

1、字符串反转

• 写一个方法，要求：输入一个字符串ABCDEFG，要求倒序输出GFEDCBA：

    // 方法1 - 使用for循环倒序遍历字符输出
    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方法实现反转
    public String formatStr2(String str) {
        StringBuilder sb = new StringBuilder(str);
        return sb.reverse().toString();
    }
  

• reverse()方法的实现原理：通过查看StringBuilder和StringBuffer的源代码，我们发现reverse()方法由它们的公共父类AbstractStringBuilder实现，具体如下：

    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;
    }
  

• 如果你看不懂上面这段代码，那就看看下面这个方法，你就能明白它的实现原理了：

    // 方法3 - 折半交换字符
    public String formatStr3(String str) {
        char[] ch = str.toCharArray(); // 字符串转为char数组
        int n = ch.length - 1;
        int middle = n >> 1; // 取中间数
        // 以中间字符为界限，左右两边字符交换 相比较方法1减少近一半循环
        // 如字符串长度为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);
    }
  

小结：

• 我们介绍了字符串反转的三种方法：
  1、倒序循环遍历字符串中每个字符，然后输出；
  2、使用StringBuilder或StringButter提供的reverse方法；
  3、手动使用折半交换字符的方法，减少了近一半循环次数。

---

2、求两个字符串的交集

版本1：查找下面两个字符串中的相同元素并输出

String stra = "庄周,甄姬,刘禅,姜子牙,孙膑,鲁班七号,廉颇";
String strb = "庄周,刘禅,廉颇,程咬金,芈月,钟无艳";

• 解决方法
  分割字符串为字符数组，依次比对两个字符数组中的元素，相同的输出。

• 实现代码

    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、因为我们查找子字符串时遵循的先长后短的原则，所以当我们找到第二个字符串中也存在此子字符串时，那就说明这个子字符串就是答案。

• 实现代码

    public String[] findSameStr(String strs, String strl) {
        if (strs.length() > strl.length()) { // 保证第一个参数是短字符串
            return findSameStr(strl, strs);
        }
  
        int length = strs.length();
        boolean isSearched = false; // 是否已找到
        ArrayList<String> mList = new ArrayList<>(); // 存储查找到的字符串
  
        for (int i = length; i >= 0; i--) { // 外层循环控制查找子字符串的长度i
            for (int j = 0; j <= length - i; j++) { // 内层循环控制开始查找的位置j，查找长度i，所以分割字符串时第二个参数即为i + j
                String temp = strs.substring(j, i + j); // 分割字符串 参数举例：(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、手动实现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位置开始剩下的字符数 < 源字符串数
                break;
            }
            index = i;
            for (int n = i + 1, j = 1; j < lenS && n < lenD; j++, n++) {
                if (des.charAt(n) != src.charAt(j)) { // 出现差异，break，重新查找
                    index = -1;
                    break;
                }
            }
        }
        if (index > -1) {
            break;
        }
    }
    return index;
}

4、用两个栈实现一个队列

假设这两个栈分别为s1，s2

• 分析思路
  1、栈的特性为：先进后出；队列的特性为：先进先出；
  2、如一个数组 data[0] ~ data[n - 1] ，我们将它压入s1栈中，那么 data[0]在栈底，data[n - 1]在栈顶；
  3、如果我们对s1栈中的元素执行出栈操作，并将出栈元素压入s2栈中，那么在s2栈中data[n - 1]在栈底，data[0]在栈顶；
  4、此时s2栈中的元素再次出栈的话，顺序即是：按照 data[0] ~ data[n - 1] 的顺序进行出栈，这就和队列先进先出的顺序相吻合。
• 实现思路1
  1、把s1作为存储空间，s2作为临时空间；
  2、入栈时：把元素压入s1；
  3、出栈时：把s1中除栈底元素外的所有元素都倒入s2，弹出s1的栈底元素，然后把s2中所有元素倒回s1。
• 实现思路2
  1、把s1作为存储空间，s2作为临时空间；
  2、入栈时，判断s1是否为空：
  如不为空，说明所有元素都在s1，直接将入栈元素压入s1；
  如为空，将s2中的所有元素倒回s1，再将入栈元素压入s1；
  3、出栈时，判断s2是否为空：
  如不为空，直接弹出s2的顶元素并出栈；
  如为空，把s1中除栈底元素外的所有元素都倒入s2，然后弹出s1的栈底元素。
• 实现思路3 - 最佳方案
  1、把s1作为存储空间，s2作为临时空间；
  2、入栈时，将元素压入s1；
  3、出栈时，判断s2是否为空：
  如不为空，则直接弹出顶元素；
  如为空，把s1中除栈底元素外的所有元素都倒入s2，然后弹出s1的栈底元素。

小结：

优先选择思路3：只会在s2为空时将s1中的元素倒入s2，避免了反复“倒”栈，仅在需要时才“倒”一次。

5、用两个队列实现一个栈

假设这两个队列分别为q1，q2

• 分析思路
  1、队列的特性为：先进先出；栈的特性为：先进后出；
  2、如一个数组 data[0] ~ data[n - 1] ，我们将它加入q1队列中，那么 data[0] 在队列头， data[n - 1] 在队列尾；
  3、如果我们对q1队列中的元素执行出队操作，将出队元素加入q2队列中，并将q1队列尾元素弹出，这就和栈先进后出的顺序相吻合。
• 实现思路1
  1、把q1作为存储空间，q2作为临时空间；
  2、入队列时：把元素插入q1的队尾；
  3、出队列时：把q1队列中除队尾元素外的所有元素都依次出队加入到q2中，弹出q1队列尾元素，然后把q1和q2队列互换。
• 实现思路2
  1、把q1作为入队临时空间，q2作为出队存储空间；
  2、入队列时：把元素插入q1的队尾，如果q2不为空，将q2队列中的元素依次出队并加入q1队尾，然后把q1和q2队列互换；
  3、出队列时：对q2队列执行出队列操作。

小结：

• 思路1在进队列时直接入队，而在每次出队列时都要轮询一遍队列；
• 思路2在每次进队列时都要轮询一遍队列，而在出队列时直接出队。

6、用两个线程交替打印数字1～100

假设这两个线程分别为：
thread1 打印 1 3 5 7 9...
thread2打印 2 4 6 8 10...
最终打印结果为1 2 3 4 5 6 7 8 9 10...

• 分析思路
  题目要求轮流交替打印数字，那就说明两个线程同一时间只有一个可以执行打印数字操作。我们就考虑使用锁机制，保证一个线程先获得锁，执行完操作后，释放锁并唤醒另外一个线程来获得锁，重复此操作直到打印结束

• 实现思路
  1、定义一个全局变量int index = 1; 定义锁对象byte[] object = new byte[0];
  2、thread1线程获得object锁并打印index，执行index++，唤醒object锁上的其它线程(thread2线程)，而后thread1进入wait等待唤醒；
  3、thread2线程的执行过程和步骤二类似。

• 实现代码

  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()必须在同步方法/代码块中调用

100、经典案例

问题描述

• 一个房间有100盏灯（全是关着的），由编号1-100的开关（只有两种状态，开或者关）控制，门外有100个学生，学生按次序一次进入房间，第一个进入的学生切换是1的倍数的开关，第二个学生切换是2的倍数的开关，以此类推，问，第100学生进入切换后，还有多少盏灯是亮着的？

分析思路

• 一开始灯是关着的，那么灯被按下奇数次就还是关着的，按偶数下就是开着的；
• 根据规则，每个灯被按下多少次取决于这个灯的数字的约数有多少个：比如第4个灯会被第 1、2、4 个人按下；再比如第5个灯会被第 1、5 个人按下；
• 所以问题就演变成 1 - 100 这100个数字中哪些数的约数个数为奇数。

实现方案

public void findValidNum() {
    int N = 100; // 100个数字
    for (int i = 1; i <= N; i++) { // 遍历这些数字
        int num = 1; // 至少有一个约数：它本身
        for (int j = 1; j <= i >> 1; j++) { // 除了本身之外最大约数不应该超过 这个数字的一半
            if (i >= j && i % j == 0) { // 如果i对j取余等于0说明j是i的约数
                num++;
            }
        }
        if (num % 2 != 0) { // 余数个数为基数则输出
            System.out.print(i + ",");
        }
    }
}

未完待续...