小编Lea*_*ner的帖子

例如字符串"abaccddccefe"中的"ccddcc"

我想到了一个解决方案,但它在O(n ^ 2)时间运行

Algo 1:

步骤:它是一种强力方法

1. 对于j = i + 1到j小于array.length,
   对于i = 1到i小于array.length -1
   , 有2个for循环
2. 这样,您可以从数组中获取每个可能组合的子字符串
3. 有一个回文功能,检查字符串是否是回文
4. 所以对于每个子串(i,j)调用这个函数,如果它是一个回文存储它在一个字符串变量中
5. 如果您找到下一个回文子串并且如果它大于当前回归,则将其替换为当前的回归.
6. 最后你的字符串变量将有答案

问题:1.这个算法在O(n ^ 2)时间运行.

算法2:

1. 反转字符串并将其存储在不同的数组中
2. 现在找到两个数组之间最大的匹配子字符串
3. 但这也是在O(n ^ 2)时间内运行的

你们能想到一个在更好的时间里运行的算法吗？如果可能的话O(n)时间

您将获得一个整数介于1和1,000,000之间的数组.一个整数在数组中两次.你怎么决定哪一个？你能想到一种方法来使用额外的内存来做到这一点.

ALGO:

• 解决方案1:
  1. 有一个哈希表
  2. 迭代数组并将其元素存储在哈希表中
  3. 一旦找到已经在哈希表中的元素,它就是dup元素
  优点:
  • 它在O(n)时间运行,只有1次通过
  缺点:
  • 它使用O(n)额外的内存
• 溶液2:
  1. 使用合并排序(O(nlogn)时间)对数组进行排序
  2. 再次解析,如果你看到一个元素两次,你得到了dup.
  优点:
  • 它不使用额外的内存
  缺点:
  • 运行时间大于O(n)

你们能想到更好的解决方案吗？

我能想到的是:

ALGO:

1. 有一个哈希表,用于存储数字及其相关计数
2. 解析数组并增加数字的计数.
3. 现在解析哈希表以获得计数为1的数字.

你能想到比这更好的解决方案吗？使用O(n)运行时并且不使用额外的空间

这是一个面试问题

我想到了一个解决方案.它使用队列.

public Void BFS()    
{   
   Queue q = new Queue();    
   q.Enqueue(root);    
   Console.WriteLine(root.Value);  

   while (q.count > 0)  
   {  
      Node n = q.DeQueue();  
      if (n.left !=null)  
       {  
          Console.Writeln(n.left);  
          q.EnQueue(n.left);  
        }   
       if (n.right !=null)  
       {  
          Console.Writeln(n.right);  
          q.EnQueue(n.right);  
        }   
    }
}    

有什么想法比这更好的解决方案,它不使用Queue？

我能想到的一种方法是反转列表然后阅读它.但这涉及改变不好的清单.
或者我可以复制列表然后将其反转,但这会使用额外的O(n)内存.有没有更好的方法不使用额外的内存,不修改列表并在O(n)时间运行

反向链表代码在c#中是这样的

Void Reverse (Node head)
{
    Node prev= null;
    Node current = head;
    Node nextNode = null;

        while (current!=null)
        {
            nextNode = current.Next;
            current.Next = prev;
            prev=current;
            current = nextNode; 

        }
        head = prev;

}   

递归解决方案是

void ReadBackWard (Node n)
{
    if (n==null)
        return;
    else
        ReadBackward(n.Next);

    Console.WriteLine(n.Data);

}

给出一个链接的数字列表.交换每2个相邻的链接.例如,如果给您的链接列表是:

a->b->c->d->e->f 

预期产量:

b->a->d->c->f->e

必须交换每2个备用链接.

我在这里写了一个解决方案.你能给我一些其他解决方案吗？你能评论一下我的解决方案并帮助我更好地写出来吗？

void SwapAdjacentNodes (Node head)
{
    if (head == null) return; 

    if (head.next == null) return; 
    Node curr = head;
    Node next = curr.Next;
    Node temp = next.Next;

    while (true)
    {
        temp = next.Next;
        next.Next = curr;
        curr.Next = temp;

        if  (curr.Next != null)
            curr = curr.Next;
        else
            break;
        if (curr.Next.Next!=null)
            next = curr.Next.Next;
        else
            break;
    }   
}

我在考虑解决这个问题.

我的输入:
1.有一个指向最后一个节点的尾指针.
2.一旦知道了最后一个指针,就可以轻松地在它旁边添加一个新节点.

Void Insert(Node N)
{  
    if (head == null) // linked list is empty
    {
       head = N; tail = N; tail.Next = head;
    } 
    else
    {        
      Node temp = tail.Next; // since this is circular tail will point to head
      Tail.Next = N;
      N.Next = temp; // correct 
      tail = N;       
    }
}

没有使用尾指针,任何人都能想到更好的解决方案吗？还如问题所述没有遍历？这是一个面试问题,只需要一些输入来找到最佳解决方案.

我写了一个创建链表副本的方法.
你们能想到比这更好的方法吗？

public static Node Duplicate(Node n)
        {
            Stack<Node> s = new Stack<Node>();

            while (n != null)
            {
                Node n2 = new Node();
                n2.Data = n.Data;
                s.Push(n2);
                n = n.Next;
            }

            Node temp = null;

            while (s.Count > 0)
            {
                Node n3 = s.Pop();
                n3.Next = temp;
                temp = n3;
            }

            return temp;

        }

实现一个算法,该算法将两个字符串作为输入,并返回两者的交集,每个字母最多表示一次.

Algo :(考虑使用的语言将是c#)

1. 将两个字符串转换为char数组
2. 获取较小的数组并为其生成哈希表,其中键为字符,值为0
3. 现在循环遍历另一个数组并在散列表中增加计数(如果该字符存在于其中).
4. 现在取出值为> 0的哈希表的所有char.
5. 这些是交叉值.

这是一个O(n)解决方案但是使用了额外的空间,2个char数组和一个哈希表

你能想到比这更好的解决方案吗？

这是递归代码.
你们能否就如何使用迭代方法实现这一点给出意见？

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

namespace PermAndComb
{
    class Program
    {
        static void Main(string[] args)
        {
            string s = "abcd";
            Permutation(s);
            Console.ReadKey();

        }

        public static void Permutation(string s)
        {
            int len = s.Length;
            char [] inStr  = s.ToCharArray();
            StringBuilder outStr = new StringBuilder();
            bool[] used = new bool[len];

            doPermute(inStr, outStr,used, len, 0);

        }

        public static void doPermute(char[] instr, StringBuilder outStr,bool [] used, int len, int level)
        {
            if (level == len)
            {
                Console.WriteLine(outStr.ToString());
                return;
            } …