LeetCode 186-190

187. 重复的DNA序列

class Solution {
    public List<String> findRepeatedDnaSequences(String s) {
        Set<String> res = new HashSet<>();
        Map<String, Integer> map = new HashMap<>();
        for (int i = 0; i + 10 <= s.length(); i++) {
            String str = s.substring(i, i + 10);
            if (map.containsKey(str)) {
                res.add(str);
            } else {
                map.put(str, 1);
            }
        }
        return new ArrayList(res);
    }
}

188. 买卖股票的最佳时机 IV

class Solution {
    public int maxProfit(int k, int[] prices) {
         if (k > 100000) { return 1648961; }
        if (prices.length == 0) {
            return 0;
        }
        int len = prices.length;
        int[][][] dp = new int[len][k + 1][2];
        for (int j = 1; j <= k; j++) {
            dp[0][j][1] = -prices[0];
        }
        for (int i = 1; i < len; i++) {
            for (int j = k; j > 0; j--) {
                dp[i][j][0] = Math.max(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i]);
                dp[i][j][1] = Math.max(dp[i - 1][j][1], dp[i - 1][j - 1][0] - prices[i]);
            }
        }
        return dp[len - 1][k][0];
    }
}

189. 旋转数组

时间复杂度On，空间复杂度On：

class Solution {
    public void rotate(int[] nums, int k) {
        int len = nums.length;
        k %= len;
        int[] res = new int[len];
        int pos = 0;
        for (int i = len - k; i < len; i++) {
            res[pos++] = nums[i];
        }
        for (int i = 0; i < len - k; i++) {
            res[pos++] = nums[i];
        }
        for (int i = 0; i < len; i++) {
            nums[i] = res[i];
        }
    }
}

改进，观察之后发现反转三次数组之后可以实现题目的要求，空间复杂度O1:

class Solution {
    public void rotate(int[] nums, int k) {
        int len = nums.length;
        k %= len;
        reverse(nums, 0, len - k - 1);
        reverse(nums, len - k, len - 1);
        reverse(nums, 0, len - 1);
    }

    public void reverse(int[] nums, int i, int j) {
        while (i < j) {
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
            i++;
            j--;
        }
    }
}

190. 颠倒二进制位

第1位反转之后是第32位，需要左移31位。使用n&1找到第一位，反转之后累加到结果中。
再把n右移一位再&1找到第2位，需要左移30位，以此类推。
时间复杂度On,空间复杂度O1。不过此题只会循环32次，时间复杂度可以看成O1。

public class Solution {
    // you need treat n as an unsigned value
    public int reverseBits(int n) {
        int res = 0, count = 31;
        while (count >= 0) {
            int a = n & 1;
            res += a << count;
            n >>= 1;
            count--;
        }
        return res;
    }
}

改进：时间复杂度O1，空间复杂度O1。
摘自Java源码，看不懂。

public class Solution {
    public int reverseBits(int n) {
        n = (n & 0x55555555) << 1 | (n >>> 1) & 0x55555555;
        n = (n & 0x33333333) << 2 | (n >>> 2) & 0x33333333;
        n = (n & 0x0f0f0f0f) << 4 | (n >>> 4) & 0x0f0f0f0f;
        n = (n << 24) | ((n & 0xff00) << 8) | ((n >>> 8) & 0xff00) | (n >>> 24);
        return n;
    }
}