QuHai互联科技 算法题部分

11、实现计算第n个斐波那契数

12、给定一个字符串编码规则，如输入字符串”Y3E12S!3”,字母后面的数字表示该字符重复几次，如果字符后没有数字则表示一个字符，最终输出转码后的字符串’YYYEEEEEEEEEEEES!!!’。试写出转码的函数，编程语言不限。

13、简述你所了解的两种或以上排序算法以及其时间复杂度

14、给定一个单向链表（给出头指针），将其翻转后输出（新的头指针）

Csharp 语言

public class ListNode {
    public int val;
    public ListNode next;
    public ListNode(int x) { val = x; }
}

public ListNode ReverseList(ListNode head) {
    ListNode prev = null;
    while (head != null) {
        ListNode next = head.next; // 记录下一个节点
        head.next = prev; // 当前节点指向前一个节点
        prev = head; // 将当前节点设为下一次的前一个节点
        head = next; // 移动到下一个节点
    }
    return prev;
}

15、使用至少2种方法判断一个字符串是否是回文。写出代码实现，编程语言不限

Csharp 语言

1、双指针法

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

namespace 判断是否回文
{
    class Program
    {
        public static bool IsHuiWen(string s)
        {

            for (int i = 0, j = s.Length-1; i < j; i++, j--)
            { if (s[i] != s[j])
                { return false; }
            }
            return true;
        }

        public static void Main(string[] args)
        {
            string s = Console.ReadLine();
            if (IsHuiWen(s))
            {
                Console.WriteLine(("Yes"));
            }
            else Console.WriteLine("No");

            Console.ReadKey();
        }

    }
}

2、反转函数

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

namespace 判断是否回文
{
    class Program
    {
        public static bool IsPalindrome(string s)
        {
            string reverseS = new string(s.Reverse().ToArray());
            return s == reverseS;
            //首先使用 .Reverse() 方法得到一个逆序枚举器，再使用 .ToArray() 将其转换为字符数组，
            //最后调用 string 类型的构造方法生成一个新的字符串，即为原字符串的翻转。
        }

        public   static void Main(string[] args)
        {
            string s = Console.ReadLine();
            if (IsPalindrome(s))
                Console.WriteLine("Yes");
            else Console.WriteLine("No");


            Console.ReadKey();
        }
    }
}

输入：
aannccddfddccnnaa Yes