Skip to main content

动态规划

单词拆分​

给定字符串 s 和单词字典 dict，确定 s 是否可以分成一个或多个以空格分隔的子串，并且这些子串都在字典中存在。

public boolean wordBreak(String s, Set<String> dict) {
    // write your code here
    int maxLength = getMaxLength(dict);
    
    // 长度为n的单词 有n + 1个切割点 比如: _l_i_n_t_
    boolean[] canBreak = new boolean[s.length() + 1];
    // 当s长度为0时
    canBreak[0] = true;
    
    for(int i = 1; i < canBreak.length; i++){
        for(int j = 1; j <= maxLength && j <= i; j++){
            //i - j 表示从 i 点开始往前j个点的位置
            String str = s.substring(i - j,i);
            //如果此str在词典中 并且 str之前的 字符串可以拆分     
            if(dict.contains(str) && canBreak[i - j]){
                canBreak[i] = true;
                break;
            }
        }
    }
    
    return canBreak[canBreak.length - 1];
}

private int getMaxLength(Set<String> dict){
    int max = 0;
    for(String s : dict){
        max = Math.max(max,s.length());
    }
    return max;
}

爬楼梯​

假设你正在爬楼梯，需要n步你才能到达顶部。但每次你只能爬一步或者两步，你能有多少种不同的方法爬到楼顶部？

public int climbStairs(int n) {
    if (n == 0) return 0;
    int[] array = new int[n + 1];
    array[0] = 1;
    if (array.length > 1) {
        array[1] = 1;
    }
    
    for(int i = 2; i < array.length; i++) {
        array[i] = array[i - 1] + array[i - 2];
    }
    return array[n];
}

打劫房屋​

假设你是一个专业的窃贼，准备沿着一条街打劫房屋。每个房子都存放着特定金额的钱。你面临的唯一约束条件是：相邻的房子装着相互联系的防盗系统，且 当相邻的两个房子同一天被打劫时，该系统会自动报警。给定一个非负整数列表，表示每个房子中存放的钱， 算一算，如果今晚去打劫，在不触动报警装置的情况下, 你最多可以得到多少钱 。

public long houseRobber(int[] A) {
    if (A.length == 0) return 0;
    long[] res = new long[A.length + 1];
    res[0] = 0;
    res[1] = A[0];
    for (int i = 2; i < res.length; i++) {
        res[i] = Math.max(res[i - 2] + A[i - 1], res[i - 1]);
    }
    return res[A.length];
}

编辑距离​

给出两个单词word1和word2，计算出将word1 转换为word2的最少操作次数。你总共三种操作方法：插入一个字符、删除一个字符、替换一个字符。

public int minDistance(String word1, String word2) {
    // write your code here
    int n = word1.length();
    int m = word2.length();
    int[][] dp = new int[n + 1][m + 1];
    for (int i = 0; i < n + 1; i++){
        dp[i][0] = i;
    }
    for (int j = 0; j < m + 1; j++){
        dp[0][j] = j;
    }
    for (int i = 1; i< n + 1; i++){
        for (int j = 1; j < m + 1; j++){
            if (word1.charAt(i - 1) == word2.charAt(j - 1)){
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = 1 + Math.min(dp[i - 1][j - 1], Math.min(dp[i][j - 1], dp[i - 1][j]));
            }
        }
    }
    return  dp[n][m];
}

乘积最大子序列​

public int maxProduct(List<Integer> nums) {
    // 分别记录正数最大值和负数最小值
    int[] max = new int[nums.size()];
    int[] min = new int[nums.size()];
    
    min[0] = max[0] = nums.get(0);
    int result = nums.get(0);
    for (int i = 1; i < nums.size(); i++) {
        min[i] = max[i] = nums.get(i);
        if (nums.get(i) > 0) {
            max[i] = Math.max(max[i], max[i - 1] * nums.get(i));
            min[i] = Math.min(min[i], min[i - 1] * nums.get(i));
        } else if (nums.get(i) < 0) {
            max[i] = Math.max(max[i], min[i - 1] * nums.get(i));
            min[i] = Math.min(min[i], max[i - 1] * nums.get(i));
        }
        
        result = Math.max(result, max[i]);
    }
    
    return result;
}

矩阵

螺旋矩阵​

给定一个包含 m x n 个要素的矩阵，（m 行, n 列），按照螺旋顺序，返回该矩阵中的所有要素。

public List<Integer> spiralOrder(int[][] matrix) {
    ArrayList<Integer> rst = new ArrayList<Integer>();
    if(matrix == null || matrix.length == 0) {
        return rst;
    }
    
    int rows = matrix.length;
    int cols = matrix[0].length;
    int count = 0;
    while(count * 2 < rows && count * 2 < cols){
        for (int i = count; i < cols - count; i++) {
            rst.add(matrix[count][i]);
        }
        
        for (int i = count + 1; i < rows - count; i++) {
            rst.add(matrix[i][cols - count - 1]);
        }
        
        if (rows - 2 * count == 1 || cols - 2 * count == 1) { // 如果只剩1行或1列
            break;
        }
            
        for (int i = cols - count - 2; i >= count; i--) {
            rst.add(matrix[rows - count - 1][i]);
        }
            
        for (int i = rows - count - 2; i >= count + 1; i--) {
            rst.add(matrix[i][count]);
        }
        
        count++;
    }
    return rst;
}

判断数独是否合法​

请判定一个数独是否有效。该数独可能只填充了部分数字，其中缺少的数字用 . 表示。

维护一个HashSet用来记同一行、同一列、同一九宫格是否存在相同数字

public boolean isValidSudoku(char[][] board) {
    Set seen = new HashSet();
    for (int i=0; i<9; ++i) {
        for (int j=0; j<9; ++j) {
            char number = board[i][j];
            if (number != '.')
                if (!seen.add(number + " in row " + i) ||
                    !seen.add(number + " in column " + j) ||
                    !seen.add(number + " in block " + i / 3 + "-" + j / 3))
                    return false;
        }
    }
    return true;
}

旋转图像​

给定一个N×N的二维矩阵表示图像，90度顺时针旋转图像。

public void rotate(int[][] matrix) {
    if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
        return;
    }

    int length = matrix.length;

    for (int i = 0; i < length / 2; i++) {
        for (int j = 0; j < (length + 1) / 2; j++){
            int tmp = matrix[i][j];
            matrix[i][j] = matrix[length - j - 1][i];
            matrix[length -j - 1][i] = matrix[length - i - 1][length - j - 1];
            matrix[length - i - 1][length - j - 1] = matrix[j][length - i - 1];
            matrix[j][length - i - 1] = tmp;
        }
    }   
}

二进制 / 位运算

落单的数​

给出 2 * n + 1个数字，除其中一个数字之外其他每个数字均出现两次，找到这个数字。

异或运算具有很好的性质，相同数字异或运算后为0，并且具有交换律和结合律，故将所有数字异或运算后即可得到只出现一次的数字。

public int singleNumber(int[] A) {
    if(A == null || A.length == 0) {
        return -1;
    }
    int rst = 0;
    for (int i = 0; i < A.length; i++) {
        rst ^= A[i];
    }
    return rst;
}

格雷编码​

格雷编码是一个二进制数字系统，在该系统中，两个连续的数值仅有一个二进制的差异。给定一个非负整数 n ，表示该代码中所有二进制的总数，请找出其格雷编码顺序。一个格雷编码顺序必须以 0 开始，并覆盖所有的 2n 个整数。例子——输入：2；输出：[0, 1, 3, 2]；解释: 0 - 00，1 - 01，3 - 11，2 - 10

格雷码生成公式：G(i) = i ^ (i >> 2)

public ArrayList<Integer> grayCode(int n) {
    ArrayList<Integer> result = new ArrayList<Integer>();
    for (int i = 0; i < (1 << n); i++) {
        result.add(i ^ (i >> 1));
    }
    return result;
}

其他

反转整数​

将一个整数中的数字进行颠倒，当颠倒后的整数溢出时，返回 0 (标记为 32 位整数)。

public int reverseInteger(int n) {
    int reversed_n = 0;
    
    while (n != 0) {
        int temp = reversed_n * 10 + n % 10;
        n = n / 10;
        if (temp / 10 != reversed_n) {
            reversed_n = 0;
            break;
        }
        reversed_n = temp;
    }
    return reversed_n;
}

LRU缓存策略​

为最近最少使用（LRU）缓存策略设计一个数据结构，它应该支持以下操作：获取数据（get）和写入数据（set）。获取数据get(key)：如果缓存中存在key，则获取其数据值（通常是正数），否则返回-1。 写入数据set(key, value)：如果key还没有在缓存中，则写入其数据值。当缓存达到上限，它应该在写入新数据之前删除最近最少使用的数据用来腾出空闲位置。

public class LRUCache {
    private class Node{
        Node prev;
        Node next;
        int key;
        int value;

        public Node(int key, int value) {
            this.key = key;
            this.value = value;
            this.prev = null;
            this.next = null;
        }
    }

    private int capacity;
    private HashMap<Integer, Node> hs = new HashMap<Integer, Node>();
    private Node head = new Node(-1, -1);
    private Node tail = new Node(-1, -1);

    public LRUCache(int capacity) {
        this.capacity = capacity;
        tail.prev = head;
        head.next = tail;
    }

    public int get(int key) {
        if( !hs.containsKey(key)) {    		//key找不到
            return -1;
        }

        // remove current
        Node current = hs.get(key);
        current.prev.next = current.next;
        current.next.prev = current.prev;

        // move current to tail
        move_to_tail(current);			//每次get，使用次数+1，最近使用，放于尾部

        return hs.get(key).value;
    }

    public void set(int key, int value) {			//数据放入缓存
        // get 这个方法会把key挪到最末端，因此，不需要再调用 move_to_tail
        if (get(key) != -1) {
            hs.get(key).value = value;
            return;
        }

        if (hs.size() == capacity) {		//超出缓存上限
            hs.remove(head.next.key);		//删除头部数据
            head.next = head.next.next;
            head.next.prev = head;
        }

        Node insert = new Node(key, value);		//新建节点
        hs.put(key, insert);
        move_to_tail(insert);					//放于尾部
    }

    private void move_to_tail(Node current) {    //移动数据至尾部
        current.prev = tail.prev;
        tail.prev = current;
        current.prev.next = current;
        current.next = tail;
    }
}