Valid Sudoku leetcode

Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules.

The Sudoku board could be partially filled, where empty cells are filled with the character '.'.

A partially filled sudoku which is valid.

Note:
A valid Sudoku board (partially filled) is not necessarily solvable. Only the filled cells need to be validated.

首先按照每行chek 然后每列check 最后每个block 分别check

check的方法是维护一个hashset 如果是'.'就跳过 如果是char就看set中是否包含 如果包含就return false 不包含就把当前char放入set中

对于block的i j取法比较trick 

k/ 3 * 3  ~ k / 3 * 3 + 2 是代表行数 k % 3 * 3 ~ k % 3 *3 + 2 是列数 这样对于每个k都可以表示一个block
时间复杂度 O(3*n^2)

public class Solution {
    public boolean isValidSudoku(char[][] board) {
        HashSet<Character> set = new HashSet<Character>();
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == '.') {
                    continue;
                }
                if (set.contains(board[i][j])) {
                    return false;
                }
                set.add(board[i][j]);
            }
            set.clear();
        }
        for (int j = 0; j < 9; j++) {
            for (int i = 0; i < 9; i++) {
               if (board[i][j] == '.') {
                    continue;
                }
                if (set.contains(board[i][j])) {
                    return false;
                }
                set.add(board[i][j]);
            }
            set.clear(); 
        }
        for (int k = 0; k < 9; k++) {
            for (int i = k / 3 * 3; i < k / 3 * 3 + 3; i ++) {
                for (int j = (k % 3) * 3; j < (k % 3) * 3 + 3; j++) {
                    if (board[i][j] == '.') {
                    continue;
                }
                if (set.contains(board[i][j])) {
                    return false;
                }
                set.add(board[i][j]);
                }
            }
            set.clear(); 
        }
        return true;
    }
}

Longest Substring Without Repeating Characters leetcode

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.

基本思路是维护一个窗口，每次关注窗口中的字符串，在每次判断中，左窗口和右窗口选择其一向前移动。同样是维护一个HashSet, 正常情况下移动右窗口，如果没有出现重复则继续移动右窗口，如果发现重复字符，则说明当前窗口中的串已经不满足要求，继续移动有窗口不可能得到更好的结果，此时移动左窗口，直到不再有重复字符为止，中间跳过的这些串中不会有更好的结果，因为他们不是重复就是更短。因为左窗口和右窗口都只向前，所以两个窗口都对每个元素访问不超过一遍，因此时间复杂度为O(2*n)=O(n),是线性算法。空间复杂度为HashSet的size,也是O(n).

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        int walker = 0;
        int runner = 0;
        int max = 0;
        HashSet<Character> set = new HashSet<Character>();
        while (runner < s.length()) {
            if (set.contains(s.charAt(runner))) {
                max = Math.max(max, runner - walker);
                while (s.charAt(walker) != s.charAt(runner)) {
                    set.remove(s.charAt(walker));
                    walker++;
                }
                set.remove(s.charAt(walker));
                walker++;
            } else {
                set.add(s.charAt(runner));
                runner++;
            }
        }
        return Math.max(max, runner - walker);
    }
}

Longest Consecutive Sequence leetcode

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.

Your algorithm should run in O(n) complexity.

最简单的方法是先排序再一次遍历 时间复杂度O(nlogn) + O(n) = O(nlogn)
用hashset存储所有的数 这样查找时间为O(1),
对于数组中每个数我们要找大于和小于他的数 例如当前数组是2 我们就要查找有没有1 和3, 如果有了3了, 那么继续找4.
所以我们对于数组中的每个数都在hashset中找他的上下边界 找到后就在set中删除然后继续查找, 维护一个max 最后返回最长的连续
我们对于数组中每个数都进行一次查找, 查找的时间复杂度是O(1) 所以最后复杂度是O(n)

public class Solution {
    public int longestConsecutive(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        HashSet<Integer> set = new HashSet<Integer>();
        for (int i = 0; i < nums.length; i++) {
            set.add(nums[i]);
        }
        int max = 0;
        for (int i = 0; i < nums.length; i++) {
            if (set.contains(nums[i])) {
                int count = 1;
                set.remove(nums[i]);
                int low = nums[i] - 1;
                int high = nums[i] + 1;
                while (set.contains(low)) {//找下边界
                    set.remove(low);
                    count++;
                    low--;
                }
                while (set.contains(high)) {//找上边界
                    set.remove(high);
                    count++;
                    high++;
                }
                max = Math.max(max, count);
            }
        }
        return max;
    }
}