Android算法学习之路（updating）

1、字符串压缩

字符串压缩

遍历字符串的每一个字符，记录count，最后append，本菜忽略了最后一位字符。

private String test(String str) {
        if (str.length() < 1) {
            return "";
        }
        if (str.length() == 1) {
            return str;
        }
        StringBuilder sb = new StringBuilder();
        int count = 1;
        char c = str.charAt(0);
        for (int i = 1; i < str.length(); i++) {
            if (c == str.charAt(i)) {
                count++;
            } else {
                sb.append(c);
                sb.append(count == 1 ? "" : count);
                c = str.charAt(i);
                count = 1;
            }
        }
        //这里记录最后一个字符
        sb.append(c);
        sb.append(count == 1 ? "" : count);
        return sb.toString();
    }

2、火车运煤

火车运煤

首先，要把3000吨煤全部运出来，至少需要3次
每次走全程，最多只能运1000吨，回不来
每次走500，来来回回白忙活
只有在小于500的某个点存煤，才有可能将煤运到终点，如走400，存200，回去，再走400，存200，回去，第三次走到这剩600，再装上这400，到终点，剩400。
当然，这不是最优的

假设第一个存煤点为X，运三次，需要经过X点5次，第五次经过X点后，X点运完才是最优的，需要消耗煤5X，如果此时X的煤是大于2000的，要运往下一个点Y，还需要运三次，消耗5Y，如果小于等于2000，则只需要消耗3Y，所以要确保最少消耗，要保证5X>=1000，到Y点的时候，最多只能有1000，因为多了运不了，所以5X+3Y>=2000，因为Y点最多1000，所有Y点，离终点越近最后剩下的就越多，所以问题就变成了这样：

5X>=1000
5X+3Y>=2000
求X+Y最大值？

最后得出X=200,Y=333.3333333时X+Y得出最大值533.33333333。
也就是1000-(1000-(200+333.3333333))=533.33333333。

3、单词反转

单词反转

public static String getReverseStr(String str) {
        int start = 0;
        int end = str.length() - 1;
        char[] reverse = reverse(str.toCharArray(), start, end);
        if (reverse[0]=='.') {
            start++;
        }
        for (int i = 0; i < str.length() - 1; i++) {
            if (reverse[i] == ' ') {
                end = i - 1;
                reverse(reverse, start, end);
                start = i + 1;
            }
        }
        return String.valueOf(reverse);
    }
    
    public static char[] reverse(char[] array, int start, int end) {
        while (start < end) {
            char temp = array[start];
            array[start++] = array[end];
            array[end--] = temp;
        }
        return array;
    }

4、Reverse Integer

Reverse Integer

这里有一个坑，当输入的值较大，且反转过后已经超过了int的取值范围，就返回0，所以这里用long类型进行运算。

public static int reverseInt(int num) {
        long result = 0;
        while (num != 0) {
            int temp = num % 10;
            if (temp != 0 || result != 0) {
                result = result * 10 + temp;
            }
            num = num / 10;
        }
        return result > Integer.MAX_VALUE || result < Integer.MIN_VALUE ? 0 : (int) result;
    }

5、扑克牌顺子

从扑克牌中随机抽5张牌，判断是不是一个顺子， 即这5张牌是不是连续的。2～10为数字本身， A为1。 J为11、Q为12、 为13。大小王可以看成任意数字。

首先将5张牌装进数据并进行排序，这里将大小王定义成0，记录大小王的数量为kingNum，并从第一个非0数开始，分别于下一个数进行比较，如果两数之差为1表示是连续的，不为1则记录中间的间隔数数量intervalNum，最后将大小王数kingNum与间隔数intervalNum进行比较，如果kingNum大于等于intervalNum，则表示可以组成顺子。

private boolean isSerial(int[] num) {
        Arrays.sort(num);
        //大小王数
        int kingNum = 0;
        //间隔数
        int intervalNum = 0;
        for (int i = 0; i < num.length - 1; i++) {
            if (num[i] == 0) {
                //记录大小王数量
                kingNum++;
            } else {
                //如果出现相同的数，对子，则不可能组成顺子
                if (num[i] == num[i + 1]) {
                    return false;
                } else {
                    //记录间隔数数量
                    intervalNum += num[i + 1] - num[i] - 1;
                }
            }
        }
        return kingNum >= intervalNum;
    }

6、折半查找

fun main(args: Array<String>) {
    val nums = arrayOf(1, 5, 9, 12, 65, 78, 99, 158, 198, 222, 555, 666)
    println(binarySearch(nums, 1))
}

private fun binarySearch(nums: Array<Int>, key: Int): Int {
    var left = 0
    var right = nums.size - 1
    var index: Int
    while (left <= right) {
        index = (left + right) / 2
        if (nums[index] > key) {
            right = index - 1
        } else if (nums[index] < key) {
            left = index + 1
        } else {
            return index
        }
    }
    return -1
}