清风徐来

外观

C#.NET 算法题 中级篇 ​

N 的阶乘尾部 0 的个数 ​

给定一个正整数 n ，求其阶乘的尾部的 0 的个数。

查看代码
c#
/// <summary>
/// 获取0的个数
/// </summary>
/// <param name="n">数字N</param>
/// <param name="type">算法类型(默认0)：0为递归，1为循环，其他无效</param>
/// <returns>0的个数</returns>
public static int GetZeroCounts(int n, int type = 0)
{
    if (type == 0)
    {
        return GetZeroCounts1(n);
    }
    else if (type == 1)
    {
        return GetZeroCounts2(n);
    }
    else
    {

        return 0;
    }
}

 /// <summary>
/// 算法1：递归
/// </summary>
/// <param name="n">数字N<param>
/// <returns>0的个数</returns>
private static int GetZeroCounts1(int n)
{
    if (n / 5 == 0)
        return 0;

    return n / 5 + GetZeroCounts1(n / 5);
}

/// <summary>
/// 算法2：循环
/// </summary>
/// <param name="n">数字N</param>
/// <returns>0的个数</returns>
private static int GetZeroCounts2(int n)
{
    int counts = 0;

    while (n != 0)
    {
        n = n / 5;
        counts += n;
    }

    return counts;
}

排列与组合 ​

给定一个集合，求出集合每个元素的全排列、全组合。

查看代码
c#
/// <summary>
/// 排列与组合
/// </summary>
/// <typeparam name="T"></typeparam>
public class PermutationAndC<T>
{
    /// <summary>
    /// 求从起始标号到结束标号的排列，其余元素不变
    /// </summary>
    /// <param name="t">所求数组</param>
    /// <param name="startIndex">起始标号</param>
    /// <param name="endIndex">结束标号</param>
    /// <returns>从起始标号到结束标号排列的范型</returns>
    public static List<T[]> GetPermutation(T[] t, int startIndex, int endIndex)
    {
        if (startIndex < 0 || endIndex > t.Length - 1)
        {
            return null;
        }
        List<T[]> list = new List<T[]>();
        GetPermutation(ref list, t, startIndex, endIndex);
        return list;
    }

    /// <summary>
    /// 返回数组所有元素的全排列
    /// </summary>
    /// <param name="t">所求数组</param>
    /// <returns>全排列的范型</returns>
    public static List<T[]> GetPermutation(T[] t)
    {
        return GetPermutation(t, 0, t.Length - 1);
    }

    /// <summary>
    /// 求数组中n个元素的排列
    /// </summary>
    /// <param name="t">所求数组</param>
    /// <param name="n">元素个数</param>
    /// <returns>数组中n个元素的排列</returns>
    public static List<T[]> GetPermutation(T[] t, int n)
    {
        if (n > t.Length)
        {
            return null;
        }
        List<T[]> list = new List<T[]>();
        List<T[]> c = GetCombination(t, n);
        for (int i = 0; i < c.Count; i++)
        {
            List<T[]> l = new List<T[]>();
            GetPermutation(ref l, c[i], 0, n - 1);
            list.AddRange(l);
        }
        return list;
    }

    /// <summary>
    /// 求数组中n个元素的组合
    /// </summary>
    /// <param name="t">所求数组</param>
    /// <param name="n">元素个数</param>
    /// <returns>数组中n个元素的组合的范型</returns>
    public static List<T[]> GetCombination(T[] t, int n)
    {
        if (t.Length < n)
        {
            return null;
        }
        int[] temp = new int[n];
        List<T[]> list = new List<T[]>();
        GetCombination(ref list, t, t.Length, n, temp, n);
        return list;
    }

    /// <summary>
    /// 交换两个变量
    /// </summary>
    /// <param name="a">变量1</param>
    /// <param name="b">变量2</param>
    private static void Swap(ref T a, ref T b)
    {
        T temp = a;
        a = b;
        b = temp;
    }

    /// <summary>
    /// 递归算法求数组的组合(私有成员)
    /// </summary>
    /// <param name="list">返回的范型</param>
    /// <param name="t">所求数组</param>
    /// <param name="n">辅助变量</param>
    /// <param name="m">辅助变量</param>
    /// <param name="b">辅助数组</param>
    /// <param name="M">辅助变量M</param>
    private static void GetCombination(ref List<T[]> list, T[] t, int n, int m, int[] b, int M)
    {
        for (int i = n; i >= m; i--)
        {
            b[m - 1] = i - 1;
            if (m > 1)
            {
                GetCombination(ref list, t, i - 1, m - 1, b, M);
            }
            else
            {
                if (list == null)
                {
                    list = new List<T[]>();
                }
                T[] temp = new T[M];
                for (int j = 0; j < b.Length; j++)
                {
                    temp[j] = t[b[j]];
                }
                list.Add(temp);
            }
        }
    }

    /// <summary>
    /// 递归算法求排列(私有成员)
    /// </summary>
    /// <param name="list">返回的列表</param>
    /// <param name="t">所求数组</param>
    /// <param name="startIndex">起始标号</param>
    /// <param name="endIndex">结束标号</param>
    private static void GetPermutation(ref List<T[]> list, T[] t, int startIndex, int endIndex)
    {
        if (startIndex == endIndex)
        {
            if (list == null)
            {
                list = new List<T[]>();
            }
            T[] temp = new T[t.Length];
            t.CopyTo(temp, 0);
            list.Add(temp);
        }
        else
        {
            for (int i = startIndex; i <= endIndex; i++)
            {
                Swap(ref t[startIndex], ref t[i]);
                GetPermutation(ref list, t, startIndex + 1, endIndex);
                Swap(ref t[startIndex], ref t[i]);
            }
        }
    }
}

农历算法 ​

给定一个日期，获取对应日期的农历算法。

查看代码
c#
/// <summary>
/// 获取对应日期的农历算法
/// </summary>
public class LunDay
{
    public LunDay()
    {
        //
        // TODO: 在此处添加构造函数逻辑
        //
    }
    //天干
    private static string[] TianGan = { "甲", "乙", "丙", "丁", "戊", "己", "庚", "辛", "壬", "癸" };

    //地支
    private static string[] DiZhi = { "子", "丑", "寅", "卯", "辰", "巳", "午", "未", "申", "酉", "戌", "亥" };

    //十二生肖
    private static string[] ShengXiao = { "鼠", "牛", "虎", "兔", "龙", "蛇", "马", "羊", "猴", "鸡", "狗", "猪" };

    //农历日期
    private static string[] DayName =   {"*","初一","初二","初三","初四","初五",
          "初六","初七","初八","初九","初十",
          "十一","十二","十三","十四","十五",
          "十六","十七","十八","十九","二十",
          "廿一","廿二","廿三","廿四","廿五",
          "廿六","廿七","廿八","廿九","三十"};

    //农历月份
    private static string[] MonthName = { "*", "正", "二", "三", "四", "五", "六", "七", "八", "九", "十", "十一", "腊" };

    //公历月计数天
    private static int[] MonthAdd = { 0, 31, 59, 90, 120, 151, 181, 212, 243, 273, 304, 334 };

    //农历数据
    private static int[] LunarData = {2635,333387,1701,1748,267701,694,2391,133423,1175,396438
        ,3402,3749,331177,1453,694,201326,2350,465197,3221,3402
        ,400202,2901,1386,267611,605,2349,137515,2709,464533,1738
        ,2901,330421,1242,2651,199255,1323,529706,3733,1706,398762
        ,2741,1206,267438,2647,1318,204070,3477,461653,1386,2413
        ,330077,1197,2637,268877,3365,531109,2900,2922,398042,2395
        ,1179,267415,2635,661067,1701,1748,398772,2742,2391,330031
        ,1175,1611,200010,3749,527717,1452,2742,332397,2350,3222
        ,268949,3402,3493,133973,1386,464219,605,2349,334123,2709
        ,2890,267946,2773,592565,1210,2651,395863,1323,2707,265877};

    /// <summary>
    /// 获取对应日期的农历
    /// </summary>
    /// <param name="dtDay">公历日期</param>
    /// <returns></returns>
    public string GetLunarCalendar(DateTime dtDay)
    {
        string sYear = dtDay.Year.ToString();
        string sMonth = dtDay.Month.ToString();
        string sDay = dtDay.Day.ToString();
        int year;
        int month;
        int day;
        try
        {
            year = int.Parse(sYear);
            month = int.Parse(sMonth);
            day = int.Parse(sDay);
        }
        catch
        {
            year = DateTime.Now.Year;
            month = DateTime.Now.Month;
            day = DateTime.Now.Day;
        }

        int nTheDate;
        int nIsEnd;
        int k, m, n, nBit, i;
        string calendar = string.Empty;
        //计算到初始时间1921年2月8日的天数：1921-2-8(正月初一)
        nTheDate = (year - 1921) * 365 + (year - 1921) / 4 + day + MonthAdd[month - 1] - 38;
        if ((year % 4 == 0) && (month > 2))
            nTheDate += 1;
        //计算天干，地支，月，日
        nIsEnd = 0;
        m = 0;
        k = 0;
        n = 0;
        while (nIsEnd != 1)
        {
            if (LunarData[m] < 4095)
                k = 11;
            else
                k = 12;
            n = k;
            while (n >= 0)
            {
                //获取LunarData[m]的第n个二进制位的值
                nBit = LunarData[m];
                for (i = 1; i < n + 1; i++)
                    nBit = nBit / 2;
                nBit = nBit % 2;
                if (nTheDate <= (29 + nBit))
                {
                    nIsEnd = 1;
                    break;
                }
                nTheDate = nTheDate - 29 - nBit;
                n = n - 1;
            }
            if (nIsEnd == 1)
                break;
            m = m + 1;
        }
        year = 1921 + m;
        month = k - n + 1;
        day = nTheDate;
        //return year+"-"+month+"-"+day;

        #region 格式化日期显示为三月廿四
        if (k == 12)
        {
            if (month == LunarData[m] / 65536 + 1)
                month = 1 - month;
            else if (month > LunarData[m] / 65536 + 1)
                month = month - 1;
        }

        //生肖
        calendar = ShengXiao[(year - 4) % 60 % 12].ToString() + "年 ";
        //天干
        calendar += TianGan[(year - 4) % 60 % 10].ToString();
        //地支
        calendar += DiZhi[(year - 4) % 60 % 12].ToString() + " ";

        //农历月
        if (month < 1)
            calendar += "闰" + MonthName[-1 * month].ToString() + "月";
        else
            calendar += MonthName[month].ToString() + "月";

        //农历日
        calendar += DayName[day].ToString() + "日";

        return calendar;

        #endregion
    }
}

字符串相乘 ​

给定两个以字符串形式表示的非负整数  num1  和  num2，返回  num1  和  num2  的乘积，它们的乘积也表示为字符串形式。

注意：不能使用任何内置的 BigInteger 库或直接将输入转换为整数。

查看代码
c#
public static string Multiply(string num1, string num2)
{
    if (num1 == "0" || num2 == "0") return "0";
    int m = num1.Length, n = num2.Length;
    int[] res = new int[m + n];
    for (int i = m - 1; i >= 0; i--)
    {
        int x = num1[i] - '0';
        for (int j = n - 1; j >= 0; j--)
        {
            int y = num2[j] - '0';
            res[i + j + 1] += x * y;
        }
    }
    for (int i = m + n - 1; i > 0; i--)
    {
        res[i - 1] += res[i] / 10;
        res[i] %= 10;
    }
    int index = res[0] == 0 ? 1 : 0;
    var sb = new StringBuilder();
    while (index < m + n)
    {
        sb.Append(res[index]);
        index++;
    }
    return sb.ToString();
}
你觉得这篇文章怎么样？
  • 0
  • 0
  • 0
  • 0
  • 0
  • 0
0  字
评论
  • 按正序
  • 按倒序
  • 按热度
Copyright © 2023-present 清风徐来