LeetCode算法题第二章

LeetCode算法题第二章

3的幂

/// <summary>
///  3的幂
/// </summary>
/// <param name="n"></param>
/// <returns></returns>
public static bool IsPowerOfThree(int n)
{
    if (n == 1)
    {
        return true;
    }
    if (n % 3 != 0 || n <= 0)
    {
        return false;
    }
    return IsPowerOfThree(n / 3);
}

4的幂

/// <summary>
///  4的幂
/// </summary>
/// <param name="n"></param>
/// <returns></returns>
public static bool IsPowerOfFour(int n)
{
    if (n == 1)
    {
        return true;
    }
    if (n % 4 != 0 || n < 0)
    {
        return false;
    }
    return IsPowerOfFour(n / 4);
}

第三大的数

/// <summary>
/// 第三大的数
/// </summary>
/// <param name="n"></param>
/// <returns></returns>
public static int ThirdMax(int[] nums)
{
    Array.Sort(nums);
    Array.Reverse(nums);
    nums = nums.Distinct().ToArray();
    if (nums.Length >= 3)
    {
        return nums[2];
    }
    return nums[0];
}

斐波那契数

/// <summary>
/// 斐波那契数
/// </summary>
/// <param name="n"></param>
/// <returns></returns>
public static int Fib(int n)
{
    if(n == 0)
    {
        return 0;
    }
    if (n == 1)
    {
        return 1;
    }
    return Fib(n - 1) + Fib(n - 2);
}

三个数的最大乘积

/// <summary>
/// 三个数的最大乘积
/// </summary>
/// <param name="nums"></param>
/// <returns></returns>
public static int MaximumProduct(int[] nums)
{
    Array.Sort(nums);
    return nums[0] * nums[1] * nums[nums.Length - 1] > nums[nums.Length - 1] * nums[nums.Length - 2] * nums[nums.Length - 3] ? nums[0] * nums[1] * nums[nums.Length - 1] : nums[nums.Length - 1] * nums[nums.Length - 2] * nums[nums.Length - 3];
}

X的平方根（emmm没想通直接用Math了）

/// <summary>
///  X的平方根
/// </summary>
/// <param name="x"></param>
/// <returns></returns>
public static int MySqrt(int x)
{
    return (int)Math.Sqrt(x);
}

二分查找（用了最简单的方法但也通过了，但是要求是二分查找所以重写了）

/// <summary>
/// 二分查找
/// </summary>
/// <param name="nums"></param>
/// <param name="target"></param>
/// <returns></returns>
public static int Search(int[] nums, int target)
{
    //Array.Sort(nums);
    //for (int i = 0; i < nums.Length; i++)
    //{
    //    if (nums[i] == target)
    //    {
    //        return i;
    //    }
    //}
    //return -1;
    //二分查找
    Array.Sort(nums);
    int start = 0;
    int end = nums.Length - 1;
    while (start < end)
    {
        int mid = (start + end) / 2;
        if (nums[mid] == target)
        {
            return mid;
        }
        if (nums[mid] > target)
        {
            end = mid - 1;
        }
        if (nums[mid] < target)
        {
            start = mid + 1;
        }
    }
    return -1;
}

整数反转（自己写的不符合要求）

/// <summary>
/// 整数反转
/// </summary>
/// <param name="x"></param>
/// <returns></returns>
public static int Reverse(int x)
{
    string num = string.Empty;
    if (x < 0)
    {
        num = (x * -1).ToString();//变正数
    }
    else
    {
        num = (x * -1).ToString();
    }
    string nums = string.Empty;
    for (int i = num.Length-1; i >= 0; i--)
    {
        //最后一位是0的话就跳出
        if (num[num.Length - 1] == 0)
        {
            continue;
        }
        nums += num[i].ToString();
    }
    if (x < 0)
    {
        return Convert.ToInt32(nums) * -1;//还原符号
    }
    return Convert.ToInt32(nums);
}

整数反转（借鉴了别人Java的解题思路）

/// <summary>
/// 整数反转
/// </summary>
/// <param name="x"></param>
/// <returns></returns>
public static int Reverse(int x)
{
    long n = 0;
    while (x != 0)
    {
        n = n * 10 + x % 10;
        x = x / 10;
    }
    return (int)n == n ? (int)n : 0;
}

检查两个字符串数组是否相等

/// <summary>
/// 检查两个字符串数组是否相等
/// </summary>
/// <param name="word1"></param>
/// <param name="word2"></param>
/// <returns></returns>
public static bool ArrayStringsAreEqual(string[] word1, string[] word2)
{
    string txt1 = string.Empty;
    string txt2 = string.Empty;
    for (int i = 0; i < word1.Length; i++)
    {
       txt1 += word1[i].ToString();
    }
    for (int i = 0; i < word2.Length; i++)
    {
       txt2 += word2[i].ToString();
    }
    return txt1 == txt2;
    //别人的一句代码解决（性能好过一丢丢）
    //return string.Join("", word1).Equals(string.Join("", word2));
}

合并两个有序数组（性能杠杠滴就是写完就看不懂了）

/// <summary>
/// 合并两个有序数组
/// </summary>
/// <param name="nums1"></param>
/// <param name="m"></param>
/// <param name="nums2"></param>
/// <param name="n"></param>
public static void Merge(int[] nums1, int m, int[] nums2, int n)
{
    if (m == 0)
    {
        nums1 = new int[n];
        for (int i = 0; i < nums2.Length; i++)
        {
            if (i == n)
            {
                break;
            }
            if (nums2[i] != 0)
            {
                nums1[i] = nums2[i];
            }
        }
    }
    if (n == 0)
    {
        int[] num3 = nums1;
        for (int i = 0; i < num3.Length; i++)
        {
            if (i == m)
            {
                break;
            }
            if (num3[i] != 0)
            {
                nums1[i] = num3[i];
            }
        }
    }
    else
    {
        Array.Sort(nums1);
        Array.Sort(nums2);
        Array.Reverse(nums2);
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < nums1.Length; j++)
            {
                if (nums1[j] == 0)
                {
                    nums1[j] = nums2[i];
                    break;
                }
            }
        }
        Array.Sort(nums1);
    }
}

有序数组中出现次数超过25%的元素

/// <summary>
/// 有序数组中出现次数超过25%的元素
/// </summary>
/// <param name="arr"></param>
/// <returns></returns>
public static int FindSpecialInteger(int[] arr)
{
    int count = arr.Length / 4;
    List<int>list=arr.ToList();
    for (int i = 0; i < list.Count; i++)
    {
        if (list.Where(s => s == list[i]).ToList().Count > count)
        {
            return list[i];
        }
    }
    return 0;
}

字符串压缩

/// <summary>
/// 字符串压缩
/// </summary>
/// <param name="S"></param>
/// <returns></returns>
public static string CompressString(string S)
{
    S += "?";
    string key = string.Empty;
    string text = string.Empty;
    int count = 0;
    for (int i = 0; i < S.Length; i++)
    {
        if (i == 0)
        {
            key = S[i].ToString();
        }
        if (key == S[i].ToString())
        {
            count++;
        }
        else
        {
            text += S[i - 1].ToString() + count.ToString();
            key = S[i].ToString();
            count = 1;
        }
    }
    return text.Length <= S.Length - 1 ? text: S.Replace("?", "") ;
}

将字符串拆分为若干长度为 k 的组（头发掉光写法）

/// <summary>
///  将字符串拆分为若干长度为 k 的组（头发掉光写法）
/// </summary>
/// <param name="s"></param>
/// <param name="k"></param>
/// <param name="fill"></param>
/// <returns></returns>
public static string[] DivideString(string s, int k, char fill)
{
    int mold = s.Length % k;//余数
    int remainder = (s.Length - mold) / k;//获取需要几个item
    int count = 0;//item数量
 
    if (remainder > 0)
    {
        count += remainder;
    }
    if (mold > 0)
    {
        count++;
    }
    if (count > 0)
    {
        List<string> list = new List<string>();
        int sum = 0;
        for (int i = 0; i < count; i++)
        {
            string text = string.Empty;
            int kcount = 0;//获取数量
            for (int j = 0; j < s.Length; j++)
            {
                if (i == count - 1 && mold > 0)
                {
                    text += s[sum].ToString();
                    kcount++;
                    //最后一次遍历
                    if (sum == s.Length - 1)
                    {
                        int x = k - kcount;
                        for (int w = 0; w < x; w++)
                        {
                            text += fill.ToString();
                        }
                        list.Add(text);
                        return list.ToArray();
                    }
                    sum++;
                    continue;
                }
                text += s[sum].ToString();
                kcount++;
                sum++;
                if (kcount == k)
                {
                    list.Add(text);
                    break;
                }
            }
        }
        return list.ToArray();
    }
    return null;
}

将字符串拆分为若干长度为 k 的组（先补齐后分割）

/// <summary>
///  将字符串拆分为若干长度为 k 的组（先补齐后分割）
/// </summary>
/// <param name="s"></param>
/// <param name="k"></param>
/// <param name="fill"></param>
/// <returns></returns>
public static string[] DivideString(string s, int k, char fill)
{
    //不如原来的性能好
    int mold = s.Length % k;//余数
    int remainder = (s.Length - mold) / k;//获取需要几个item
    int count = 0;//item数量
 
    if (remainder > 0)
    {
       count += remainder;
    }
    if (mold > 0)
    {
       count++;
    }
    if (count > 0)
    {
       int kcount = count * k - s.Length;//补齐数
       for (int i = 0; i < kcount; i++)
       {
           s += fill.ToString();
       }
       List<string> list = new List<string>();
       int sum = 0;
       for (int i = 0; i < count; i++)
       {
           string text = string.Empty;
           kcount = 0;//获取数量
           for (int j = 0; j < s.Length; j++)
           {
               text += s[sum].ToString();
               kcount++;
               sum++;
               if (kcount == k)
               {
                   list.Add(text);
                   break;
               }
           }
       }
       return list.ToArray();
    }
    return null;
}