36. Valid Sudoku

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

250px-sudoku-by-l2g-20050714-svg

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

A partially filled sudoku which is valid.

思路:
数独规则,9行9列的棋盘,每行,每列和每个33的小方格都不能有重复的数字,并且数字只能是0-9
分别判断行,列跟3
3小方格中是否满足了解。 可以用Hashset 或者数组来解决

public class Solution {
    public boolean isValidSudoku(char[][] board) {
        if (board.length != 9 || board[0].length != 9 ) return false;
        HashSet<Integer> set;
        // validate col

        for (int i = 0; i < 9; i++) {
            set = new HashSet<Integer>();
            for (int j = 0; j < 9; j++) {
                char cell = board[i][j];
                if (cell == '.') continue;
                if (cell < '0' || cell > '9') return false;
                int val = cell - '0';
                if (set.contains(val)) {
                    return false;
                }
                set.add(val);
            }
        }
        // validate col

        for(int j = 0; j < 9; j++) {
            set = new HashSet<Integer>();
            for (int i = 0; i < 9; i++) {
                char cell = board[i][j];
                if (cell == '.') continue;
                if (cell < '0' || cell > '9') return false;
                int val = cell - '0';
                if (set.contains(val)) {
                    return false;
                }
                set.add(val);
            }
        }

        // validate subsquare

        for (int i = 0; i < 9; i+=3) {
            for (int j = 0; j < 9; j+=3) {
                set = new HashSet<Integer>();
                for (int k = i; k < i + 3; k++) {
                    for (int l = j; l < j + 3; l++) {
                        char cell = board[k][l];
                        if (cell == '.') continue;
                        if (cell < '0' || cell > '9') return false;
                        int val = cell - '0';
                        if (set.contains(val)) {
                            return false;
                        }
                        set.add(val);
                    }
                }
            }
        }
        return true;
    }
}

Advertisements

242. Valid Anagram

Given two strings s and t, write a function to determine if t is an anagram of s.

For example,
s = “anagram”, t = “nagaram”, return true.
s = “rat”, t = “car”, return false.

Note:
You may assume the string contains only lowercase alphabets.

思路:本题只需毕竟字符在两个字符串中出现次数相同,跟顺序无关系,而且都假设是lowercase下,果断祭出大杀器用char字符数组来做,假设是ASCII码开辟26空间,统计字符出现次数。 如果是Unicode则开辟256空间

public class Solution {
    public boolean isAnagram(String s, String t) {
        if (s == null &amp;&amp; t == null) return true;
        if (s.length() == 0 &amp;&amp; s.length() == 0) return true;
        if (s.length() == 0 || t.length() == 0 || s == null || t == null) return false;
        char[] arr = new char[26];
        for (int i = 0; i &lt; s.length(); i++) {
            int pos = s.charAt(i) - 'a';
            arr[pos]+=1;
        }
        for (int j = 0; j &lt; t.length(); j++) {
            int pos = t.charAt(j) - 'a';
            arr[pos]-=1;
        }
        for (int i = 0; i &lt; arr.length; i++) {
            if (arr[i] != 0) {
                return false;
            }
        }
        return true;
    }
}

290. Word Pattern

Given a pattern and a string str, find if str follows the same pattern.

Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty word in str.

Examples:
pattern = “abba”, str = “dog cat cat dog” should return true.
pattern = “abba”, str = “dog cat cat fish” should return false.
pattern = “aaaa”, str = “dog cat cat dog” should return false.
pattern = “abba”, str = “dog dog dog dog” should return false.
Notes:
You may assume pattern contains only lowercase letters, and str contains lowercase letters separated by a single space.

思路:跟205. Isomorphic Strings 思路完全相同, 唯一注意的是205中是char比较, 本题是String比较.

public class Solution {
    public boolean wordPattern(String pattern, String str) {
        if (str == null || pattern == null) return false;
        String[] arr = str.split(&quot;\\s+&quot;);
        if (pattern.length() != arr.length) return false;
        HashMap&lt;Character, String&gt; map = new HashMap&lt;&gt;();
        HashSet&lt;String&gt; set = new HashSet&lt;&gt;();

        for (int i = 0; i &lt; arr.length; i++) {
            Character c = pattern.charAt(i);
            String s = arr[i];
            if (!map.containsKey(c)) {
                if (set.contains(s)) {
                    return false;
                } else {
                    map.put(c, s);
                    set.add(s);
                }
            } else {
                String value = map.get(c);
                if (!value.equals(arr[i])) {
                    return false;
                }
            }
        }
        return true;
    }
}

205. Isomorphic Strings

Given two strings s and t, determine if they are isomorphic.

Two strings are isomorphic if the characters in s can be replaced to get t.

All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character but a character may map to itself.

For example,
Given “egg”, “add”, return true.

Given “foo”, “bar”, return false.

Given “paper”, “title”, return true.

Note:
You may assume both s and t have the same length.

思路:建立s->t的hashtable, 用hashset检查t中的char不会被映射2次

public class Solution {
    public boolean isIsomorphic(String s, String t) {
        if (s.length() != t.length() ) return false;
        if (s == null || t == null) return false;
        HashMap<Character, Character> map = new HashMap<>(); // build mapping table based on s -> t
        HashSet<Character> set = new HashSet<>(); // keep track of char in t

        for (int i = 0; i < s.length(); i ++) {
            if (!map.containsKey(s.charAt(i))) {
                if(set.contains(t.charAt(i))) {
                    return false;
                } else {
                    map.put(s.charAt(i), t.charAt(i));
                    set.add(t.charAt(i));
                }

            } else {
                Character value = map.get(s.charAt(i));
                if(value != t.charAt(i)) {
                    return false;
                } 
            }

        }
        return true;
    }
}

136. Single Number

Given an array of integers, every element appears twice except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

思路: 非space0(n)解法,用hashTable。 注意Java的hashMap的遍历API。
Space 0(n)的解法, 数字成对出现找落单,用XOR的性质, 0^X=X;X^X=0;初始result=0,去挨个XOR数组里面的数,最后就是单个数的结果。

public class Solution {
    public int singleNumber(int[] nums) {
        int result = nums[0];
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        for(int i = 0; i < nums.length; i++) {
            if (!map.containsKey(nums[i])) {
                map.put(nums[i], 1);
            } else {
                int count = map.get(nums[i]);
                map.put(nums[i], count + 1);
            }
        }

        Set set = map.entrySet();
        Iterator iter = set.iterator();
        while(iter.hasNext()) {
            Map.Entry me = (Map.Entry) iter.next();
            if ((int)me.getValue() == 1) {
                result =(int) me.getKey();
            }
        }
        return result;
    }
}

space: o(1)

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

165. Compare Version Numbers

Compare two version numbers version1 and version2.
If version1 > version2 return 1, if version1 < version2 return -1, otherwise return 0.

You may assume that the version strings are non-empty and contain only digits and the . character.
The . character does not represent a decimal point and is used to separate number sequences.
For instance, 2.5 is not "two and a half" or "half way to version three", it is the fifth second-level revision of the second first-level revision.

Here is an example of version numbers ordering:

0.1 < 1.1 < 1.2 < 13.37

思路:
这个是String转Int来计算,务必想到用char来跟'0'或者'a' 或者'A'进行计算。
由于存在".",我们可以分成"."之前的版本跟"."之后的版本来分开计算, 因为会出现1.0 == 1情况。
这个题目如果用split会使程序跑起来会很慢。

public class Solution {
    public int compareVersion(String version1, String version2) {
        int p1 = 0; // pointer in version1
        int p2 = 0; // pointer in version2

        while(p1 < version1.length() || p2 < version2.length()) {
            int v1 = 0;
            int v2 = 0;

            while(p1 < version1.length() && version1.charAt(p1) != '.') {
                v1 = v1 * 10 + version1.charAt(p1) - '0';
                p1++;
            }
            while(p2 < version2.length() && version2.charAt(p2) != '.') {
                v2 = v2 * 10 + version2.charAt(p2) - '0';
                p2++;
            }
            p1++;
            p2++;
            if (v1 > v2) {
                return 1;
            } else if(v1 < v2) {
                return -1;
            }
        }

        return 0;
    }
}