using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;
using System.Threading.Tasks;

namespace Leetcode
{
    class Program
    {
        //461. Hamming Distance ~ Easy = Accepted 149/149
        public static int HammingDistance(int x, int y)
        {
            string xBinary = Convert.ToString(x, 2);
            string yBinary = Convert.ToString(y, 2);
            int differences = 0;
            int repeat = Math.Max(xBinary.Length, yBinary.Length);
            for (int i = 0; i < repeat; i++)
            {
                if (xBinary.Length < repeat)
                {
                    xBinary = "0" + xBinary;
                }

                if (yBinary.Length < repeat)
                {
                    yBinary = "0" + yBinary;
                }
            }

            for (int i = 0; i < repeat; i++)
            {
                if (xBinary[i] != yBinary[i])
                {
                    differences++;
                }
            }
            return differences;
        }

        //561. Array Partition I ~ Easy = Accepted 81/81
        public static int ArrayPairSum(int[] nums)
        {
            if (nums.Count() == 2)
            {
                return nums[0];
            }

            List<int> numList = nums.ToList();
            numList.Sort();

            int sum = 0;
            for (int i = 0; i < numList.Count; i += 2)
            {
                sum += numList[i];
            }
            return sum;
        }

        //476. Number Complement ~ Easy  = Accepted 149/149
        public static int FindComplement(int num)
        {
            string numBinary = Convert.ToString(num, 2);
            string compBinary = "";

            for (int i = 0; i < numBinary.Length; i++)
            {
                compBinary += numBinary[i] == '0' ? 1 : 0;
            }
            return Convert.ToInt32(compBinary, 2);
        }

        //566. Reshape the Matrix ~ Easy = Accepted 56/56
        public static int[,] MatrixReshape(int[,] nums, int r, int c)
        {
            if (r * c > nums.GetLength(0) * nums.GetLength(1))
            {
                return nums;
            }

            Queue<int> numQueue = new Queue<int>();
            int[,] newMatrix = new int[r, c];

            for (int i = 0; i < nums.GetLength(0); i++)
            {
                for (int j = 0; j < nums.GetLength(1); j++)
                {
                    numQueue.Enqueue(nums[i, j]);
                }
            }

            for (int i = 0; i < newMatrix.GetLength(0); i++)
            {
                for (int j = 0; j < newMatrix.GetLength(1); j++)
                {
                    newMatrix[i, j] = numQueue.Dequeue();
                }
            }

            return newMatrix;
        }

        //557. Reverse Words in a String III ~ Easy = Accepted ~ 30/30
        public static string ReverseWords(string s)
        {
            string[] splitString = s.Split(null);
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < splitString.Count(); i++)
            {
                char[] currentWord = splitString[i].ToCharArray();
                sb.Append(string.Join("", currentWord.Reverse()));
                sb.Append(" ");
            }
            return sb.ToString().Trim();
        }

        //500. Keyboard Row ~ Easy = Accepted ~ 22/22
        public static string[] FindWords(string[] words)
        {
            List<string> oneLineWords = new List<string>();
            for (int i = 0; i < words.Length; i++)
            {
                if (Regex.Matches(words[i].ToLower(), "[qwertyuiop]").Count == words[i].Length ||
                    Regex.Matches(words[i].ToLower(), "[asdfghjkl]").Count == words[i].Length ||
                    Regex.Matches(words[i].ToLower(), "[zxcvbnm]").Count == words[i].Length)
                {
                    oneLineWords.Add(words[i]);
                }
            }
            return oneLineWords.ToArray();
        }

        //575. Distribute Candies ~ Easy = Accepted ~ 207/207
        public static int DistributeCandies(int[] candies)
        {
            if (candies.Distinct().Count() > candies.Count() / 2)
            {
                return candies.Count() / 2;
            }
            return candies.Distinct().Count();
        }

        //412. Fizz Buzz ~ Easy = Accepted ~ 8/8
        public static List<string> FizzBuzz(int n)
        {
            List<string> fizzBuzz = new List<string>();

            for (int i = 1; i <= n; i++)
            {
                string current = "";
                if (i % 3 == 0)
                {
                    current += "Fizz";
                }
                if (i % 5 == 0)
                {
                    current += "Buzz";
                }
                if (i % 3 != 0 && i % 5 != 0)
                {
                    current += i.ToString();
                }

                fizzBuzz.Add(current);
            }

            return fizzBuzz;
        }

        //344. Reverse String ~ Easy = Accepted ~ 476/476
        public static string ReverseString(string s)
        {
            return string.Join("", s.ToCharArray().Reverse());
        }

        //496. Next Greater Element I ~ Easy = Accepted ~ 17/17
        public static int[] NextGreaterElement(int[] findNums, int[] nums)
        {
            int[] greaterInts = new int[findNums.Length];
            int j = 0, flag = 0;
            for (int i = 0; i < findNums.Length; i++)
            {
                j = Array.IndexOf(nums, findNums[i]) + 1;
                while (j < nums.Length)
                {
                    if (findNums[i] < nums[j])
                    {
                        greaterInts[i] = nums[j];
                        flag = 1;
                        j = nums.Length;
                    }
                    j++;
                }

                if (flag == 0)
                {
                    greaterInts[i] = -1;
                }
                flag = 0;
            }
            return greaterInts;
        }

        //463. Island Perimeter ~ Easy = Accepted ~ 5833/5833
        public static int IslandPerimeter(int[,] grid)
        {
            int perimeter = 0;
            for (int i = 0; i < grid.GetLength(0); i++)
            {
                for (int j = 0; j < grid.GetLength(1); j++)
                {
                    if ((int)grid.GetValue(i, j) == 1)
                    {
                        if (i - 1 < 0 || grid[i - 1, j] == 0)
                        {
                            perimeter++;
                        }
                        if (j - 1 < 0 || grid[i, j - 1] == 0)
                        {
                            perimeter++;
                        }
                        if (j + 1 >= grid.GetLength(1) || grid[i, j + 1] == 0)
                        {
                            perimeter++;
                        }
                        if (i + 1 >= grid.GetLength(0) || grid[i + 1, j] == 0)
                        {
                            perimeter++;
                        }
                    }
                }
            }
            return perimeter;
        }

        //292. Nim Game ~ Easy = Accepted ~ 60/60
        public static bool CanWinNim(int n)
        {
            return !(n % 4 == 0);
        }

        //485. Max Consecutive Ones ~ Easy = Accepted ~ 41/41
        public static int FindMaxConsecutiveOnes(int[] nums)
        {
            if (!nums.Contains(0))
            {
                return nums.Length;
            }
            int count = 0, maxCount = 0;
            for (int i = 0; i < nums.Length; i++)
            {
                if (nums[i] == 1)
                {
                    count++;
                }
                else
                {
                    maxCount = Math.Max(maxCount, count);
                    count = 0;
                }
            }
            return Math.Max(maxCount, count);
        }

        //136. Single Number ~ Easy = Accepted ~ 15/15
        public static int SingleNumber(int[] nums)
        {
            Array.Sort(nums);
            if (nums.Length == 1)
            {
                return nums[0];
            }

            for (int i = 0; i < nums.Length - 1; i += 2)
            {
                if (nums[i] != nums[i + 1])
                {
                    return nums[i];
                }
            }

            if (nums[nums.Length - 1] != nums[nums.Length - 2])
            {
                return nums[nums.Length - 1];
            }
            return -1;
        }

        //521. Longest Uncommon Subsequence I ~ Easy = Accepted ~ 41/41
        public static int FindLUSlength(string a, string b)
        {
            if (a.Equals(b))
            {
                return -1;
            }
            return Math.Max(a.Length, b.Length);
        }

        //520. Detect Capital ~ Easy = Accepted ~ 550/550
        public static bool DetectCapitalUse(string word)
        {
            char[] wordChar = word.ToCharArray();
            if (word.Length == 1)
            {
                return true;
            }
            else if (word.Length == 2)
            {
                if (Char.IsUpper(wordChar[0]))
                {
                    return true;
                }
                else
                {
                    return !Char.IsUpper(wordChar[1]);
                }
            }

            for (int i = 1; i < word.Length; i++)
            {
                if (Char.IsUpper(wordChar[0]))
                {
                    if (Char.IsUpper(wordChar[1]))
                    {
                        if (!Char.IsUpper(wordChar[i]))
                        {
                            return false;
                        }
                    }
                    else
                    {
                        if (Char.IsUpper(wordChar[i]))
                        {
                            return false;
                        }
                    }
                }
                else
                {
                    if (Char.IsUpper(wordChar[i]))
                    {
                        return false;
                    }
                }
            }
            return true;
        }

        //448. Find All Numbers Disappeared in an Array
        public static List<int> FindDisappearedNumbers(int[] nums)
        {
            Array.Sort(nums);
            List<int> missing = new List<int>();
            List<int> numsList = nums.ToList();

            for (int i=0; i< numsList.Count; i++)
            {
                if(!(numsList[i] == numsList[i + 1] || numsList[i] + 1 == numsList[i + 1]))
                {
                    //missing.Add(i+1);
                    numsList.Insert(i, i + 1);
                    i-=2;
                }
            }

            return numsList.ToList();
        }

        static void Main(string[] argsConsole)
        {
            FindDisappearedNumbers(new int[8] { 1,2,2,3,3,4,7,8 }).ForEach(Console.WriteLine);
            //Console.WriteLine(FindDisappearedNumbers(new int[8] { 1,2,2,3,3,4,7,8 }));
            Console.WriteLine("fin");
            Console.ReadKey();
        }
    }
}