字符串&排序 2016-08-11

[SnackMen]

49. Group Anagrams 75. Sort Colors

[dayang]

/**
 * [AC] LeetCode 49 Group Anagrams
 * @param {string[]} strs
 * @return {string[][]}
 */
var groupAnagrams = function(strs) {
    var hash = {};
    var i, sorted;
    for(i = 0; i < strs.length; i++){
        sorted = strs[i].split('').sort().join('');
        if(!hash[sorted]){
            hash[sorted] = [];
        }
        hash[sorted].push(strs[i]);
    }
    var res = [],key;
    for(key in hash){
        res.push(hash[key]);
    }
    return res;
};

[dayang]

/**
 * [AC] LeetCode 75  Sort Colors
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var sortColors = function(nums) {
    var redIndex = 0, blueIndex = nums.length - 1,temp,i;
    for(i = 0; i < nums.length && redIndex < blueIndex; i++){
        while(nums[redIndex] === 0) redIndex++;
        while(nums[blueIndex] === 2) blueIndex--;
        if(nums[i] === 0 && i > redIndex){
            temp = nums[i];
            nums[i] =  nums[redIndex];
            nums[redIndex] = temp;
            i--;
        }else if(nums[i] === 2 && i < blueIndex){
            temp = nums[i];
            nums[i] =  nums[blueIndex];
            nums[blueIndex] = temp;
            i--;
        }
    }
};

[wolfogre]

// [AC] LeetCode 49 Group Anagrams
public class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> result = new ArrayList<List<String>>();
        HashMap<Integer, Integer> hashMap = new HashMap<Integer, Integer>();
        for(String str : strs){
            char[] arr = str.toCharArray();
            Arrays.sort(arr);
            int code = new String(arr).hashCode();
            Integer index;
            if((index = hashMap.get(code)) != null)
                result.get(index).add(str);
            else{
                result.add(new ArrayList());
                result.get(result.size() - 1).add(str);
                hashMap.put(code, result.size() - 1);
            }
        }
        return result;
    }
}

[wolfogre]

桶排序

[AC] LeetCode 75  Sort Colors
public class Solution {
    public void sortColors(int[] nums) {
        int [] colorCount = new int[3];
        for(int n : nums){
            ++colorCount[n];
        }
        int index = 0;
        for(int i = 0; i < 3; ++i){
            while(colorCount[i]-- > 0)
                nums[index++] = i;
        }
    }
}

[zhaokuohaha]

49 - C# - 素数是个好东西

public class Solution
{
    public IList<IList<string>> GroupAnagrams(string[] strs)
    {
        Dictionary<int, List<string>> res = new Dictionary<int, List<string>>();
        int[] index = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103 };
        foreach(string str in strs)
        {
            int val = 1;
            foreach(char c in str)
            {
                val *= index[c - 'a'];
            }
            if(res.ContainsKey(val))
            {
                res[val].Add(str);
            }
            else
            {
                res.Add(val, new List<string>() { str });
            }
        }
        List<IList<string>> ret = new List<IList<string>>();
        foreach(var item in res)
        {
            ret.Add(item.Value);
        }
        return ret;
    }
}

附大神原码: 更加出神入化 Java:

public static List<List<String>> groupAnagrams(String[] strs) { 
   int[] prime = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103};//最多10609个z

            List<List<String>> res = new ArrayList<>();
            HashMap<Integer, Integer> map = new HashMap<>();
            for (String s : strs) {
                int key = 1;
                for (char c : s.toCharArray()) {
                    key *= prime[c - 'a'];
                }
                List<String> t;
                if (map.containsKey(key)) {
                    t = res.get(map.get(key));
                } else {
                    t = new ArrayList<>();
                    res.add(t);
                    map.put(key, res.size() - 1);
                }
                t.add(s);
            }
            return res;
    }

[wolfogre]

换新的求code的方法

// [AC] LeetCode 49 Group Anagrams
public class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> result = new ArrayList<List<String>>();
        HashMap<Integer, Integer> hashMap = new HashMap<Integer, Integer>();
        for(String str : strs){
            int code = getUniqueCode(str);
            Integer index;
            if((index = hashMap.get(code)) != null)
                result.get(index).add(str);
            else{
                result.add(new ArrayList());
                result.get(result.size() - 1).add(str);
                hashMap.put(code, result.size() - 1);
            }
        }
        return result;
    }

    private int getUniqueCode(String str){
        int[] primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103};
        int result = 1;
        for(char ch : str.toCharArray()){
            result *= primes[ch - 'a'];
        }
        return result;
    }
}

[zhaokuohaha]

75 - C# - O(n^2)?

public class Solution
{
    public void SortColors(int[] nums)
    {
        int head = 0;
        int tail = nums.Length - 1;
        for(int i=0; i<nums.Length; i++)
        {
            if(nums[i] == 0)
            {
                while (head < i && nums[head] == 0) head++;
                swap(nums, i, head);
                if(nums[i] == 2 ) i--;//换完之后如果是2, 再换一次
            }
            if(nums[i] == 2)
            {
                while (tail> i && nums[tail] == 2) tail--;
                swap(nums, i, tail);
                if(nums[i]==0) i--; //换完之后如果是0, 再换一次
            }
        }
    }
    private void swap(int[] nums, int i, int j)
    {
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }
}

[SnackMen]

/*
*[AC] LeetCode 49 Group Anagrams
*/
public class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        if(strs==null || strs.length==0)
            return new ArrayList<<List<String>>();
        Map<String,List<String>> map = new HashMap<String,List<String>>();

        for(String string : strs){
            char []chars = string.toCharArray();
            Arrays.sort(chars);
            String charToString = new String(chars);
            if(!map.containsKey(charToString))
                map.put(charToString,new ArrayList<String>());
            map.get(charToString).add(string);
        }
        return new ArrayList<List<String>>(map.values());
    }
}

[SnackMen]

/*
*[AC] LeetCode 75  Sort Colors
*遍历两次 
*/
public class Solution {
    public void sortColors(int[] nums) {
        int r=0,w=0,b=0;
        for(int num:nums){
            if(num==0)
                r++;
            else if(num==1)
                w++;
            else
                b++;
        }

        for(int i=0;i<nums.length;i++){
            if(i<r)
                nums[i]=0;
            else if(i<r+w)
                nums[i]=1;
            else
                nums[i]=2;
        }
    }
}