leetcode hot 100(刷题篇11)(231/235/237/238/292/557/240/36)offer/3/4/5

目录

1.leetcode2312 的幂

2.leetcode235二叉搜索树的最近公共祖先

3.leetcode237删除链表中的节点

4.leetcode238除自身以外数组的乘积

5.leetcode292Nim 游戏

6.leetcode557反转字符串中的单词 III

7.offer3数组中重复的数字

8.offer4二维数组中的查找

leetcode240. 搜索二维矩阵 II

9.offer5替换空格

10.leetcode36有效的数独

---

1.leetcode2312 的幂

/**
    O(1)
    O(1)
 */
class Solution {
    public boolean isPowerOfTwo(int n) {
        return n > 0 && (n & (n - 1)) == 0;
    }
}

2.leetcode235二叉搜索树的最近公共祖先

/**
    O(N)
    O(1)
 */
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        TreeNode ancestor = root;
        while (true) {
            if (p.val < ancestor.val && q.val < ancestor.val) {
                ancestor = ancestor.left;
            } else if (p.val > ancestor.val && q.val > ancestor.val) {
                ancestor = ancestor.right;
            } else {
                break;
            }
        }
        return ancestor;
    }
}

3.leetcode237删除链表中的节点

/**
    O(1)
    O(1)
 */
class Solution {
    public void deleteNode(ListNode node) {
        node.val = node.next.val;
        node.next = node.next.next;
    }
}

4.leetcode238除自身以外数组的乘积

/**
    O(N)
    O(1)
    左边乘积
    右边乘积
    二者乘积  就是最终结果
 */
class Solution {
    public int[] productExceptSelf(int[] nums) {
        int length = nums.length;
        int[] answer = new int[length];

        // answer[i] 表示索引 i 左侧所有元素的乘积
        // 因为索引为 '0' 的元素左侧没有元素， 所以 answer[0] = 1
        answer[0] = 1;
        for (int i = 1; i < length; i++) {
            answer[i] = nums[i - 1] * answer[i - 1];
        }

        // R 为右侧所有元素的乘积
        // 刚开始右边没有元素，所以 R = 1
        int R = 1;
        for (int i = length - 1; i >= 0; i--) {
            // 对于索引 i，左边的乘积为 answer[i]，右边的乘积为 R
            answer[i] = answer[i] * R;
            // R 需要包含右边所有的乘积，所以计算下一个结果时需要将当前值乘到 R 上
            R *= nums[i];
        }
        return answer;
    }
}

5.leetcode292Nim 游戏

/**
    O(1)
    O(1)
    显而易见的是，如果石头堆中只有一块、两块、或是三块石头，那么在你的回合，你就可以把全部石子拿走，
    从而在游戏中取胜；如果堆中恰好有四块石头，你就会失败。
    因为在这种情况下不管你取走多少石头，总会为你的对手留下几块，
    他可以将剩余的石头全部取完，从而他可以在游戏中打败你。
    因此，要想获胜，在你的回合中，
    必须避免石头堆中的石子数为 4 的情况。
 */
class Solution {
    public boolean canWinNim(int n) {
        return n % 4 != 0;
    }
}

6.leetcode557反转字符串中的单词 III

/**
    开辟一个新字符串。然后从头到尾遍历原字符串，直到找到空格为止，
    此时找到了一个单词，并能得到单词的起止位置。
    随后，根据单词的起止位置，可以将该单词逆序放到新字符串当中。
    如此循环多次，直到遍历完原字符串，就能得到翻转后的结果。
    O(N)
    O(N)
 */

class Solution {
    public String reverseWords(String s) {
        StringBuffer ret = new StringBuffer();
        int length = s.length();
        int i = 0;
        while (i < length) {
            int start = i;
            while (i < length && s.charAt(i) != ' ') {
                i++;
            }
            for (int p = start; p < i; p++) {
                ret.append(s.charAt(start + i - 1 - p));
            }
            while (i < length && s.charAt(i) == ' ') {
                i++;
                ret.append(' ');
            }
        }
        return ret.toString();
    }
}

7.offer3数组中重复的数字

/**
    O(N)
    O(N)

 */
class Solution {
    public int findRepeatNumber(int[] nums) {
        Set<Integer> set = new HashSet<Integer>();
        int repeat = -1;
        for (int num : nums) {
            if (!set.add(num)) {
                repeat = num;
                break;
            }
        }
        return repeat;
    }
}

8.offer4二维数组中的查找

leetcode240. 搜索二维矩阵 II

/**
    从右上角开始查找。
    cur = target  true
    cur > target   左侧移动
       cur < target 下面移动
    cur < target   下面移动
    O(M + N)
    O(1)
 */
class Solution {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }
        int rows = matrix.length, columns = matrix[0].length;
        int row = 0, column = columns - 1;
        while (row < rows && column >= 0) {
            int num = matrix[row][column];
            if (num == target) {
                return true;
            } else if (num > target) {
                column--;
            } else {
                row++;
            }
        }
        return false;
    }
}

9.offer5替换空格

/**
    最差情况 扩大三倍
    O(N)
    O(N)
 */
class Solution {
    public String replaceSpace(String s) {
        int length = s.length();
        char[] array = new char[length * 3];
        int size = 0;
        for (int i = 0; i < length; i++) {
            char c = s.charAt(i);
            if (c == ' ') {
                array[size++] = '%';
                array[size++] = '2';
                array[size++] = '0';
            } else {
                array[size++] = c;
            }
        }
        String newStr = new String(array, 0, size);
        return newStr;
    }
}

10.leetcode36有效的数独

/**
    O(1)
    O(1)
 */
class Solution {
    public boolean isValidSudoku(char[][] board) {
        int[][] rows = new int[9][10];
        int[][] columns = new int[9][10];
        int[][][] subboxes = new int[3][3][10];
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                char c = board[i][j];
                if (c != '.') {
                    int index = c - '0';
                    rows[i][index]++;
                    columns[j][index]++;
                    subboxes[i / 3][j / 3][index]++;
                    if (rows[i][index] > 1 || columns[j][index] > 1 || subboxes[i / 3][j / 3][index] > 1) {
                        return false;
                    }
                }
            }
        }
        return true;
    }
}