最新要闻

广告

手机

iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?

iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?

警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案

家电

世界快消息!掌握这几个算法题.NET初级面试算法不发愁

来源:博客园

1、冒泡排序

冒泡排序算法是一种简单的排序算法,它通过重复比较相邻的元素来实现排序。每次对相邻的两个元素进行比较,如果第一个元素比第二个元素大,就交换这两个元素的位置。重复这个过程,直到没有任何两元素需要比较为止。时间复杂度是O(n^2)。以下是冒泡排序的代码实现:


(资料图片)

public void BubbleSort(int[] nums){    for (int i = 0; i < nums.Length - 1; i++)    {        for (int j = 0; j < nums.Length - i - 1; j++)        {            if (nums[j] > nums[j + 1])            {                int temp = nums[j];                nums[j] = nums[j + 1];                nums[j + 1] = temp;            }        }    }}

2、一列数的规则如下: 1、1、2、3、5、8、13、21、34...... 求第40位数是多少, 用C#递归算法实现。

这是有名的斐波拉契数列。在数据规则中,第一个数是1,第二个数也是1。从第三个数开始,每一项都是前面两个数的和。因此我们可以用递归的方式来求解第n个数。时间复杂度为O(n)。实现方法如下:

publicinFb(intn){if(n<=1)returnn;elsereturnFb(n-1)+Fb(n-2);}//调用int result = Fb(40);Console.WriteLine(result);//结果:102334155

3、数组去重

写一个函数,输入一个数组,返回去重后的数组。这道题是常考比较简单的一道题,时间复杂度为O(n)。示例如下:

public int[] RemoveDuplicates(int[] nums){    if (nums == null || nums.Length == 0)returnnums;    Array.Sort(nums);    int i = 0;    for (int j = 1; j < nums.Length; j++)    {        if (nums[j] != nums[i])        {            i++;            nums[i] = nums[j];        }    }    return nums.Take(i + 1).ToArray();}

4、二分查找

给定一个有序数组[1, 2, 3, 4, 5, 6, 7, 8, 9],查找目标值为6,输出其下标为5。此题时间空间复杂度为O(log n)。代码实现示例如下:

public int BinarySearch(int[] nums, int target){    int left = 0, right = nums.Length - 1;    while (left <= right)    {        int mid = left + (right - left) / 2;        if (nums[mid] == target)        {            return mid;        }        else if (nums[mid] < target)        {            left = mid + 1;        }        else        {            right = mid - 1;        }    }    return -1;   // 没有找到目标值}//调用int[] nums = {1, 2, 3, 4, 5, 6, 7, 8, 9};int target = 6;int index = BinarySearch(nums, target);Console.WriteLine(index);

5、字符串匹配

写一个函数,输入一个字符串和一个目标字符串,返回目标字符串在字符串中的位置。时间复杂度为O(n*m)。示例代码如下:

public int StrStr(string haystack, string needle){    if (string.IsNullOrEmpty(needle))    {        return 0;    }    int n = haystack.Length, m = needle.Length;    if (n < m)    {        return -1;    }    for (int i = 0; i <= n - m; i++)    {        int j;        for (j = 0; j < m; j++)        {            if (haystack[i+j] != needle[j])            {                break;            }        }        if (j == m)        {            return i;        }    }    return -1;   // 没有找到目标字符串}//调用    string haystack = "欢迎公众号:DOTNET开发跳槽";string needle = "NET";int index = StrStr(haystack, needle);Console.WriteLine(index);//结果为:9

6、选择排序算法

它的基本思路是每次在未排序的元素中选择最小的元素,并将其放到已排序序列的末尾。具体来说,选择排序是通过不断地找出未排序部分中的最小值,然后将其与未排序部分的第一个元素交换位置来实现排序的。由于它每次只需要比较未排序部分的元素,因此选择排序的比较次数相对其他排序算法来说较少,但是由于频繁地交换元素,因此它的时间复杂度仍然是O(n^2)。示例代码如下:

public void SelectionSort(int[] nums){    int n = nums.Length;    for (int i = 0; i < n - 1; i++)    {        int minIndex = i;        for (int j = i + 1; j < n; j++)        {            if (nums[j] < nums[minIndex])            {                minIndex = j;            }        }        if (minIndex != i)        {            int temp = nums[i];            nums[i] = nums[minIndex];            nums[minIndex] = temp;        }    }}

结语

算法面试题是.NET面试难以越过的鸿沟,尤其是大厂的面试肯定少不了。本文讲述了6种面试题,主要是排序和查找类的算法题,这也是面试中比较常见的一些算法题。在面试中或许会考这些算法题的变种题,大家可以根据具体情况随机应变。希望本文对你的面试有所帮助,同时欢迎把你考到的算法题留言,并欢迎对本文吐槽。

来源公众号:DotNet开发跳槽

关键词: