瀏覽標籤:

LinQ

[C#][LeetCode] 804. Unique Morse Code Words

這題要將英文轉換成摩斯密碼,並計算出重複字串的數量,我用 Linq 輕鬆解決。

public class Solution {
    
    public int UniqueMorseRepresentations(string[] words) {
        
        string[] morseCode = new string[] {".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."};
        
        List<char> listAToZ = Enumerable.Range('a', 26)
                                        .Select(x => (char)x)
                                        .ToList();
        
        var morseCodeAns = words.Select(x => 
        {
            var temp = x.Select(y => morseCode[listAToZ.IndexOf(y)]);            
            return string.Join(string.Empty, temp);
        });
        
        return morseCodeAns.Distinct().Count();
    }
}

 

       

[C#][LeetCode][Easy] 561. Array Partition I

問題:

Given an array of 2n integers, your task is to group these integers into n pairs of integer, say (a1, b1), (a2, b2), …, (an, bn) which makes sum of min(ai, bi) for all i from 1 to n as large as possible.

心得:
看到這題我第一個反應就是去找linq有沒有辦法分割陣列,然後再加總= =
不過LINQ效能沒有很好,看到最佳解答有提供一個不錯的方法。

我的答案:

public class Solution {
    public int ArrayPairSum(int[] nums) {
        return nums.OrderBy(x => x)
                   .Select((x, index) => new { index, x })
                   .GroupBy(x => x.index / 2)
                   .Sum(x => x.Select(y => y.x).Min());
    }
}

最佳解答:

public class Solution {
    public int ArrayPairSum(int[] nums) {
        Array.Sort(nums);
        int result = 0;
        for (int i = 0; i < nums.Length; i += 2)
        {
            result += nums[i];
        }
        return result;
    }
}
       

[C#][Linq][Expression] 將陣列分割成固定長度的小陣列

來源:[Snippet]在C#中将List分割成多个定长的小List

可以將一個很長很長很長的List分割成固定大小的List方便批次運算。

程式碼:

public static IEnumerable<IEnumerable<T>> ChunkBy<T>(this IEnumerable<T> source, int chunkSize)
{
    return source.Select((x, i) => new { Index = i, Value = x }).GroupBy(x => x.Index / chunkSize).Select(x => x.Select(v => v.Value));
}
       

[C#][LeetCode][Easy] 258. Add Digits

心得:

題目要求將每一位數相加,直到剩下個位數。

問題:

Given a non-negative integer num, repeatedly add all its digits until the result has only one digit.

For example:

Given num = 38, the process is like: 3 + 8 = 11, 1 + 1 = 2. Since 2 has only one digit, return it.

答案:

  1. For + 遞迴
    public class Solution {
        public int AddDigits(int num) {
            string str = num.ToString();
            if (str.Length < 2)
            {
                return int.Parse(str);
            }
            else
            {
                int tmp = 0;
                for (int i = 0; i < str.Length; i++)
                {
                    tmp += int.Parse(str[i].ToString());
                }
        
                return AddDigits(tmp);
            }
        }
    }
  2. LinQ + 遞迴
    public class Solution {
        public int AddDigits(int num) {
            string str = num.ToString();
            if (str.Length < 2)
            {
                return int.Parse(str);
            }
            else
            {
                return AddDigits(str.Sum(x => int.Parse(x.ToString())));
            }
        }
    }
  3. Normal
    public class Solution {
        public int AddDigits(int num) {
            string str = num.ToString();
            while (str.Length > 1)
            {
                int tmp = 0;
                for (int i = 0; i < str.Length; i++)
                {
                    tmp += int.Parse(str[i].ToString());
                }
    
                str = tmp.ToString();
            }
    
            return int.Parse(str);
        }
    }
       

[C#][LeetCode][Easy] 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.

答案:

  • LinQ – OrderBy
    public class Solution {
        public bool IsAnagram(string s, string t) {
            return new string(s.OrderBy(x => x).ToArray()) == new string(t.OrderBy(x => x).ToArray());
        }
    }
  • LinQ – Sort
    public class Solution {
        public bool IsAnagram(string s, string t) {
            var arr_1 = s.ToList();
            var arr_2 = t.ToList();
            arr_1.Sort();
            arr_2.Sort();
            return new string(arr_1.ToArray()) == new string(arr_2.ToArray());
        }
    }
  • Normal – Array.Sort
    public class Solution {
        public bool IsAnagram(string s, string t) {
            var arr_1 = s.ToArray();
            var arr_2 = t.ToArray();
            Array.Sort(arr_1);
            Array.Sort(arr_2);
            return new string(arr_1) == new string(arr_2);
        }
    }
  • Normal – 硬幹 (會 Time Limit Exceeded)
    public class Solution {
        public bool IsAnagram(string s, string t) {
            return Sort(s) == Sort(t);
        }
        
        private string Sort(string str){
            string result = "";
             for(int i = 0; i < 25; i++){
                char c = Convert.ToChar(Convert.ToInt16('a') + i);
                for(int j = 0; j < str.Length; j++){
                    if(c == str[j]){
                        result += c;
                    }
                }
            }
            
            return result;
        }
    }

參考:

  1. (C#)用迴圈印出字母A到Z
       

[C#][LeetCode][Easy] 448. Find All Numbers Disappeared in an Array

心得:

題目大意是有一陣列1~N且亂序,必須找出N並找出未出現哪些數字,剛開始我用硬幹的方式,結果顯示Time Out如下:

public class Solution {
    public IList<int> FindDisappearedNumbers(int[] nums) {
        List<int> ans = new List<int>();
        
        if(nums.Length > 1){
            //Sort
            for(int i = 0; i < nums.Length; i++){
                for(int j = i; j < nums.Length; j++){
                    if(nums[j] < nums[i]){
                        int tmp = nums[j];
                        nums[j] = nums[i];
                        nums[i] = tmp;
                    }
                }
            }
            
            int n = nums.Length;
            for(int i = 0; i < n; i++){
                bool b = false;
                for(int j = 0; j < nums.Length; j++){
                    if(i+1 == nums[j]){
                        b = true;
                        break;
                    }
                }
                
                if(!b){
                    ans.Add(i+1);
                }
            }
        }else if(nums.Length == 1){
            if(nums[0] != 1){
                ans.Add(1);
            }
        }
        
        return ans;
    }
}

後來改用稍為聰明一點的LinQ來找出N,結果還是Time Out如下:

public class Solution {
    public IList<int> FindDisappearedNumbers(int[] nums) {
        List<int> ans = new List<int>();
        if(nums.Length > 0){
            int max = nums.Max();
            if(max < nums.Length){
                max = nums.Length;
            }
            for(int i = 1; i <= max; i++){
                if(nums.Any(x=> x == i) == false){
                    ans.Add(i);
                }
            }
        }
        
        return ans;
    }
}

最後生氣了,直接全部都用LinQ,交給RangeExcept直接省略兩個迴圈並且順利解決!

問題:

Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.

Find all the elements of [1, n] inclusive that do not appear in this array.

Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.

答案:

public class Solution {
    public IList<int> FindDisappearedNumbers(int[] nums) {
        List<int> ans = new List<int>();
        
        if(nums.Length > 0){
            ans.AddRange(Enumerable
            .Range(1, nums.Length > nums.Max() ? nums.Length : nums.Max())
            .Except(nums));
        }
        
        return ans;
    }
}

參考:

  1. [C#] 對List&lt;T&gt;取交集、聯集及差集