161. One Edit Distance

今儿做微软的OA遇上了这个原题,赶紧来总结一下.
思路: 找编辑距离为1,也就是给的两个字符串中,只有一个字符不同,或者字符缺失. 分以下几种情况讨论:
1. 给定的两个字符串长度相同, 则先找到字符串不同的位置i,然后验证i+1后的子串是否相同即可。
2. 给定的两个字符串长度相差为1, 则先找到第一个对应位置不一样的那个字符,如果较长字符串在那个字符之后的部分和较短字符串那个字符及之后的部分是一样的,则符合要求.
3. 给定的两个字符串长度大于1, 则肯定不符合要求.
复杂度: Time O(n), Space O(1)

public class Solution {
    public boolean isOneEditDistance(String s, String t) {
        int sLen = s.length();
        int tLen = t.length();
        if (sLen == 0 && tLen == 0) return false;
        if (sLen == tLen) return isOneEdit(s, t);
        if (sLen - tLen == 1) return isOneDeleted(s, t);
        if (tLen - sLen == 1) return isOneDeleted(t, s);
        return false;
    }

    public boolean isOneEdit(String s, String t) {
        boolean isModified = false;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) != t.charAt(i)) {
                if (isModified) return false;
                else isModified = true;
            }
        }
        return isModified;
    }

    public boolean isOneDeleted(String longStr, String shortStr) {
        for (int i = 0; i < shortStr.length(); i++) {
            if (longStr.charAt(i) != shortStr.charAt(i)) {
                return longStr.substring(i+1).equals(shortStr.substring(i));
            }
        }
        return true;
    }
}
Advertisements

54. Spiral Matrix

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

For example,
Given the following matrix:

[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]

You should return [1,2,3,6,9,8,7,4,5].

思路:

public class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> res = new ArrayList<>();
        if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) return res;
        int count = 0;
        int row = matrix.length;
        int col = matrix[0].length;
        while(count * 2 < row && count * 2 < col) {
            for (int i = count; i <= col - 1 - count; i++) { // 左上->右上
                res.add(matrix[count][i]);
            }
            for (int j = count + 1; j <= row - 1 - count; j++) { // 右上 -> 右下
                res.add(matrix[j][col - 1 - count]);
            }
            if (row - 2 * count == 1 || col - 2 * count == 1) break; // 只有1行或者1列情况就停止
            for (int i = col - 2 - count; i >= count; i--) { // 右下 -> 左下
                res.add(matrix[row - 1 - count][i]);
            }
            for (int j = row - 2 - count; j >= count + 1; j--) { // 左下 -> 左上
                res.add(matrix[j][count]);
            }
            count++;
        }
        return res;
    }
}

268. Missing Number

Given an array containing n distinct numbers taken from 0, 1, 2, …, n, find the one that is missing from the array.

For example,
Given nums = [0, 1, 3] return 2.

Note:
Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?

思路1: 用bit XOR来做,由于给定数组的特殊性,每个数字在数组中都有与下标相对应的数
复杂度: Time O(n)

public class Solution {
    public int missingNumber(int[] nums) {
        int num = 0;
        for (int i = 0; i < nums.length; i++) {
            num = num ^ nums[i];
        }
        for (int i = 0; i <= nums.length; i++) {
            num = num ^ i;
        }
        return num;
    }
}

思路2: 先排序,然后用二分法找到第一个和nums[i]不相等的数i就可以了。
复杂度: Time O(nlogn)

  public int missingNumber(int[] nums) {
        Arrays.sort(nums);
        int start = 0;
        int end = nums.length - 1;
        while(start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (nums[mid] > mid) {
                end = mid;
            } else {
                start = mid;
            }
        }
        if (start == nums[start]) {
            return end;
        }
        return start;

    }

思路3: 求和相减.
复杂度: Time O(n)

public class Solution {
    public int missingNumber(int[] nums) {
        int sum = 0;
        int len = nums.length;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
        }
        int idxSum =  len * (1 + len)/ 2;
        return idxSum - sum;
    }
}

114. Flatten Binary Tree to Linked List

Given a binary tree, flatten it to a linked list in-place.

For example,
Given

         1
        / \
       2   5
      / \   \
     3   4   6
//The flattened tree should look like:
   1
    \
     2
      \
       3
        \
         4
          \
           5
            \
             6

思路: 用Stack,如果当前节点有右子树,把右子树入栈,左子树放到右子树,如果找到左子树叶子节点,左子树叶子节点接到stack中pop出来的右子树节点。
复杂度: Time O(n), Space O(n)

public class Solution {
    public void flatten(TreeNode root) {
        if (root == null) return;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while(cur != null || !stack.isEmpty()) {
           if (cur.right != null) { // 右子树放到stack
               stack.push(cur.right);
           }
           if (cur.left != null) { // 如果右左子树,左子树变为右子树
               cur.right = cur.left;
               cur.left = null; // 原来左子树为null
           } else if (!stack.isEmpty()) { // 找到左子树的叶子
               TreeNode temp = stack.pop(); 
               cur.right = temp;
           }
           cur = cur.right;
        }
    }
}

419. Battleships in a Board

Given an 2D board, count how many different battleships are in it. The battleships are represented with ‘X’s, empty slots are represented with ‘.’s. You may assume the following rules:

You receive a valid board, made of only battleships or empty slots.
Battleships can only be placed horizontally or vertically. In other words, they can only be made of the shape 1xN (1 row, N columns) or Nx1 (N rows, 1 column), where N can be of any size.
At least one horizontal or vertical cell separates between two battleships – there are no adjacent battleships.
Example:
X..X
…X
…X
In the above board there are 2 battleships.
Invalid Example:
…X
XXXX
…X
This is an invalid board that you will not receive – as battleships will always have a cell separating between them.

思路: 找多少有多少条battleship,这个题目解法跟island题目完全相同。 用BFS或者DFS来遍历, 题目要求不准改动board的值,可以用个boolean的visited数组来解决;

public class Solution {
    private int[] xDir = new int[]{0, -1, 0, 1};
    private int[] yDir = new int[]{1, 0, -1, 0};

    public int countBattleships(char[][] board) {
        if (board == null || board.length == 0 || board[0] == null || board[0].length == 0) return 0;
        int row = board.length;
        int col = board[0].length;
        int count = 0;
        boolean[][] visited = new boolean[row][col];
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (!visited[i][j] && board[i][j] == 'X') {
                    countBattleships(board, visited, i, j);
                    count++;
                }
            }
        }
        return count;
    }

    public void countBattleships(char[][] board, boolean[][] visited, int x, int y) {
        if (x < 0 || y < 0 || x >= board.length || y >= board[0].length) return;
        if (board[x][y] == '.' || visited[x][y]) return;
        visited[x][y] = true;
        for (int i = 0; i < 4; i++) {
            int newX = x + xDir[i];
            int newY = y + yDir[i];
            countBattleships(board, visited, newX, newY);
        }
    }
}

152. Maximum Product Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest product.

For example, given the array [2,3,-2,4],
the contiguous subarray [2,3] has the largest product = 6.

思路: 乘积的最大值可能来自于两个正数相乘或者两个负数相乘。所以我们要同时来保存每次乘积的最大值跟最小值.
复杂度: time O(n), space: O(n)

public class Solution {
    public int maxProduct(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];
        int[] maxProds = new int[nums.length];
        int[] minProds = new int[nums.length];
        int res = nums[0];
        maxProds[0] = minProds[0] = nums[0];

        for (int i = 1; i < nums.length; i++) {
            if (nums[i] >= 0) {
                maxProds[i] = Math.max(nums[i], maxProds[i-1] * nums[i]);
                minProds[i] = Math.min(nums[i], minProds[i-1] * nums[i]);
            } else {
                maxProds[i] = Math.max(nums[i], minProds[i-1] * nums[i]);
                minProds[i] = Math.min(nums[i], maxProds[i-1] * nums[i]);
            }
            res = Math.max(maxProds[i], res);
        }
        return res;
    }
}

53. Maximum Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [-2,1,-3,4,-1,2,1,-5,4],
the contiguous subarray [4,-1,2,1] has the largest sum = 6.

More practice:
If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

思路: DP的思路,用一个curSum跟maxSum来追踪.
复杂度 time O(n) space O(1)

public class Solution {
    public int maxSubArray(int[] nums) {
        if (nums == null || nums.length == 0) 
            return Integer.MIN_VALUE;
        int curSum = nums[0];
        int maxSum = nums[0];
        for (int i = 1; i &lt; nums.length; i++) {
            curSum = curSum &gt; 0 ? curSum + nums[i]: nums[i];
            maxSum = Math.max(curSum, maxSum);
        }
        return maxSum;
    }
}