杂项

我的日程安排表 I

实现MyCalendar类来存储活动。如果新添加的活动没有重复，则可以添加。类将有方法book(int start，int end)。这代表左闭右开的间隔[start，end)有了预定，范围内的实数x，都满足start <= x < end，返回true。 否则，返回false，并且事件不会添加到日历中。

TreeMap 是一个有序的key-value集合，它通过 红黑树 实现，继承于AbstractMap，所以它是一个Map，即一个key-value集合。TreeMap可以查询小于等于某个值的最大的key，也可查询大于等于某个值的最小的key。 元素的顺序可以改变，并且对新的数组不会有影响。

class MyCalendar {
    TreeMap<Integer, Integer> calendar;

    MyCalendar() {
        calendar = new TreeMap();
    }

    public boolean book(int start, int end) {
        Integer previous = calendar.floorKey(start), next = calendar.ceilingKey(start);
        if ((previous == null || calendar.get(previous) <= start) && (next == null || end <= next)) {
            calendar.put(start, end);
            return true;
        }
        return false;
    }
}

合并排序数组

合并两个排序的整数数组A和B变成一个新的数组。可以假设A具有足够的空间去添加B中的元素。

public void mergeSortedArray(int[] A, int m, int[] B, int n) {
    int i = m - 1, j = n - 1, index = m + n - 1;
    while (i >= 0 && j >= 0) {
        if (A[i] > B[j]) {
            A[index--] = A[i--];
        } else {
            A[index--] = B[j--];
        }
    }
    while (i >= 0) {
        A[index--] = A[i--];
    }
    while (j >= 0) {
        A[index--] = B[j--];
    }
}

贪心

买卖股票的最佳时机

假设有一个数组，它的第i个元素是一支给定的股票在第i天的价格。如果你最多只允许完成一次交易(例如，一次买卖股票)，设计一个算法来找出最大利润。

public int maxProfit(int[] prices) {
    if (prices == null || prices.length == 0) {
        return 0;
    }

    int min = Integer.MAX_VALUE;  //记录最低的价格
    int profit = 0;
    for (int price : prices) {
        min = Math.min(price, min);
        profit = Math.max(price - min, profit);
    }

    return profit;
}

买卖股票的最佳时机 II

给定一个数组 prices 表示一支股票每天的价格。可以完成任意次数的交易, 不过不能同时参与多个交易，设计一个算法求出最大的利润。

贪心：只要相邻的两天股票的价格是上升的, 我们就进行一次交易, 获得一定利润。

public int maxProfit(int[] prices) {
    int profit = 0;
    for (int i = 0; i < prices.length - 1; i++) {
        int diff = prices[i + 1] - prices[i];
        if (diff > 0) {
            profit += diff;
        }
    }
    return profit;
}

最大子数组

给定一个整数数组，找到一个具有最大和的子数组，返回其最大和。

public int maxSubArray(int[] A) {
    if (A == null || A.length == 0){
        return 0;
    }
    //max记录全局最大值，sum记录区间和，如果当前sum>0，那么可以继续和后面的数求和，否则就从0开始
    int max = Integer.MIN_VALUE, sum = 0;
    for (int i = 0; i < A.length; i++) {
        sum += A[i];
        max = Math.max(max, sum);
        sum = Math.max(sum, 0);
    }

    return max;
}

主元素

给定一个整型数组，找出主元素，它在数组中的出现次数严格大于数组元素个数的二分之一(可以假设数组非空，且数组中总是存在主元素)。

public int majorityNumber(List<Integer> nums) {
    int currentMajor = 0;
    int count = 0;

    for(Integer num : nums) {
        if(count == 0) {
            currentMajor = num;
        }
        
        if(num == currentMajor) {
            count++;
        } else {
            count--;
        }
    }
    return currentMajor;
}

字符串处理

生成括号

给定 n，表示有 n 对括号, 请写一个函数以将其生成所有的括号组合，并返回组合结果。

public List<String> generateParenthesis(int n) {
    List<String> res = new ArrayList<>();
    helper(n, n, "", res);
    return res;
}

// DFS
private void helper(int nL, int nR, String parenthesis, List<String> res) {
    // nL 和 nR 分别代表左右括号剩余的数量
    if (nL < 0 || nR < 0) {
        return;
    }
    
    if (nL == 0 && nR == 0) {
        res.add(parenthesis);
        return;
    }
    helper(nL - 1, nR, parenthesis + "(", res);
    if (nL >= nR) {
        return;
    }
    helper(nL, nR - 1, parenthesis + ")", res);
}

Excel表列标题

给定一个正整数，返回相应的列标题，如Excel表中所示。如1 -> A，2 -> B...26 -> Z，27 -> AA

public String convertToTitle (int n) {
    StringBuilder str = new StringBuilder();

    while (n > 0) {
        n--;
        str.append ( (char) ( (n % 26) + 'A'));
        n /= 26;
    }
    return str.reverse().toString();
}

翻转游戏

翻转游戏：给定一个只包含两种字符的字符串：+和-，你和你的小伙伴轮流翻转"++"变成"--"。当一个人无法采取行动时游戏结束，另一个人将是赢家。编写一个函数，计算字符串在一次有效移动后的所有可能状态。

public List<String> generatePossibleNextMoves (String s) {
    List list = new ArrayList();
    for (int i = -1; (i = s.indexOf ("++", i + 1)) >= 0;) {
        list.add (s.substring (0, i) + "--" + s.substring (i + 2));
    }
    return list;
}

翻转字符串中的单词

给定一个字符串，逐个翻转字符串中的每个单词。

public String reverseWords(String s) {
    if(s.length() == 0 || s == null){
        return " ";
    }
    //按照空格将s切分
    String[] array = s.split(" ");
    StringBuilder sb = new StringBuilder();
    //从后往前遍历array，在sb中插入单词
    for(int i = array.length - 1; i >= 0; i--){
        if(!array[i].equals("")) {
            if (sb.length() > 0) {
                sb.append(" ");
            }
            
            sb.append(array[i]);
        }
    }
    return sb.toString();
}

转换字符串到整数

实现atoi这个函数，将一个字符串转换为整数。如果没有合法的整数，返回0。如果整数超出了32位整数的范围，返回INT_MAX(2147483647)如果是正整数，或者INT_MIN(-2147483648)如果是负整数。

public int myAtoi(String str) {
    if(str == null) {
        return 0;
    }
    str = str.trim();
    if (str.length() == 0) {
        return 0;
    }
        
    int sign = 1;
    int index = 0;

    if (str.charAt(index) == '+') {
        index++;
    } else if (str.charAt(index) == '-') {
        sign = -1;
        index++;
    }
    long num = 0;
    for (; index < str.length(); index++) {
        if (str.charAt(index) < '0' || str.charAt(index) > '9') {
            break;
        }
        num = num * 10 + (str.charAt(index) - '0');
        if (num > Integer.MAX_VALUE ) {
            break;
        }
    }   
    if (num * sign >= Integer.MAX_VALUE) {
        return Integer.MAX_VALUE;
    }
    if (num * sign <= Integer.MIN_VALUE) {
        return Integer.MIN_VALUE;
    }
    return (int)num * sign;
}

最长公共前缀

public String longestCommonPrefix(String[] strs) {
    if (strs == null || strs.length == 0) {
        return "";
    }
    String prefix = strs[0];
    for(int i = 1; i < strs.length; i++) {
        int j = 0;
        while (j < strs[i].length() && j < prefix.length() && strs[i].charAt(j) == prefix.charAt(j)) {
            j++;
        }
        if( j == 0) {
            return "";
        }
        prefix = prefix.substring(0, j);
    }
    return prefix;
}

回文数

判断一个正整数是不是回文数。回文数的定义是，将这个数反转之后，得到的数仍然是同一个数。

public boolean palindromeNumber(int num) {
    // Write your code here
    if(num < 0){
        return false;
    }
    int div = 1;
    while(num / div >= 10){
        div *= 10;
    }
    while(num > 0){
        if(num / div != num % 10){
            return false;
        }
        num = (num % div) / 10;
        div /= 100;
    }
    return true;
}