数据结构,你还记得吗(下)_玖富娱乐主管发布


玖富娱乐是一家为代理招商,直属主管信息发布为主的资讯网站,同时也兼顾玖富娱乐代理注册登录地址。 有了前面两篇博文做沉淀,这篇博文该干啥呢,该玩一玩Code了。下面将以《数据构造,你还记得吗(上)》内里所触及的口试题为泉源,若是问到你,你该怎样做呢?

跟上一篇《数据构造,你还记得吗(中)》目次举行一一对应,以此来提拔明白。

数组

数组反转

            int[] arr = { 1, 2, 3, 5, 6 };
            int length = arr.Length / 2;
            for(int i=0;i<length; i  )
            {
                int temp = arr[i];
                arr[i] = arr[arr.Length - i-1];
                arr[arr.Length - i-1] = temp;
            }

List和ArrayList自带反转函数 Reverse();

寻觅数组中第二小的元素

  • 处置惩罚方案有按递增递次对数组举行排序,堆排、快排、兼并排序等等都能够到达目标。时候复杂度是O(nlogn)。
  • 其次是扫描数组两次。在第一次遍历中找到最小元素。在第二次遍历中,找到大于它的最小元素,时候复杂度是O(n)。
    下面引见一次遍历处置惩罚,时候复杂度是O(n)。
            Stopwatch stopwatch = new Stopwatch();
            stopwatch.Start();
            int min =int.MaxValue;
            int secondMin = int.MaxValue;
            int[] arr = { 1, 3, 5, 6, 8, 9, 10, 66 , 66 ,55,88,66,22,55,58};
            for (int i = 0; i < arr.Length; i  )
            {
                int num = arr[i];
                if (num < min)
                {
                    secondMin = min;
                    min = num;
                }
                else
                    secondMin = num < secondMin ? num : secondMin;
            };
            stopwatch.Stop();
            Console.WriteLine(secondMin "消费时候{0}",stopwatch.Elapsed.ToString());

找出数组中第一个不反复的元素

  • 笨要领
           Stopwatch stopwatch = new Stopwatch();
            stopwatch.Start();
            int[] arr = { 1, 3, 5, 6, 8, 9, 10, 66 , 66 ,55,88,66,22,55,581,1,3,5,6};
            Dictionary<int, List<int>> dic = new Dictionary<int, List<int>>();
            int index = 0;
            for (int i = 0; i < arr.Length; i  )
            {
                index  ;
                if (!dic.ContainsKey(arr[i]))
                {
                    
                    dic.Add(arr[i], new List<int> { index });
                }
               else
                {
                   dic[arr[i]].Add(index);
                }
            };
            int minIndex = int.MaxValue;
            int temp=0 ;
            foreach(var k in dic.Keys)
            {
                if(dic[k].Count==1)
                {
                    foreach(var v in dic[k])
                    {
                        if (minIndex > v)
                        {
                            minIndex = v;
                            temp = k;
                        }
                    }
                }
            }
            stopwatch.Stop();
            Console.WriteLine(temp   "消费时候{0}",stopwatch.Elapsed.ToString());
  • 快要领
            Stopwatch stopwatch = new Stopwatch();
            stopwatch.Start();
            int[] arr = { 1, 3, 5, 6, 8, 9, 10, 66, 66, 55, 88, 66, 22, 55, 581, 1};
            foreach (var a in arr)
            {
                int firstIndex = Array.IndexOf(arr, a);
                int lastIndex = Array.LastIndexOf(arr, a);
                if (firstIndex == lastIndex)
                {
                    stopwatch.Stop();
                    Console.WriteLine(a   "消费时候{0}", stopwatch.Elapsed.ToString());
                    break;
                }
            }

兼并两个有序数组

  • 快要领
            int[] arr1 = { 1, 3, 5, 6, 8, 9, 10, 66, 66, 55, 88, 66, 22, 55, 581, 1};
            int[] arr2 = { 1,4, 5,7, 8, 55, 10, 66, 66,};
            List<int> list = new List<int>();
            list.AddRange(arr1);
            list.AddRange(arr2);
            list.Sort();
            foreach(var l in list)
            {
                Console.WriteLine(l);
            }

运用栈盘算后缀表达式

后缀表达式简介

  1. 中缀表达式:
    一般,算术表达式写作中缀表达式,,甚么是中缀表达式呢?中缀表达式就是:操纵符位于操纵数之间。以下情势: 比方表达式:1 2*3, 盘算时,我们依据表达式的优先划定规矩来盘算。其结果是7而不是9。

  2. 后缀表达式:
    后缀表达式就是:操纵符位于两个操纵数以后,后缀表达式的情势以下: 。以下所示: 1 2 - 等价于1-2
  • 长处
    运用后缀表达式的长处:后缀表达式比中缀表达式更轻易盘算,由于它不消斟酌优先划定规矩和括弧,表达式中的操纵数和操纵符的递次就足以完成盘算。因而程序设想语言编辑器和运行时情况在其内部中每每运用后缀表达式。栈是用于盘算后缀表达式的抱负数据构造。
  代码有点长,已经由测试,放上跟栈有关的中心代码段,以下:
  public int evaluate(String expr)
        {
            int op1, op2, result = 0;
            String token;
            //将字符串剖析,/s 婚配任何空缺字符,包孕空格、制表符、换页符等。   
            String[] tokenizer = expr.Split(" ");
            for (int x = 0; x < tokenizer.Length; x  )
            {
                Console.WriteLine(tokenizer[x]   " ");//输出  
                token = tokenizer[x];
                if (isOperator(token))
                {//推断是操纵符,则出栈两个操纵数  
                    op2 = stack.Pop();
                    op1 = stack.Pop();
                    result = evalSingleOp(token[0], op1, op2);//盘算结果  
                    stack.Push(result);//把盘算结果压入栈中  
                }
                else
                {
                    stack.Push( int.Parse(token));//压入操纵数  
                }
            }
            return result;
        }

     private bool isOperator(String token)
        {

            return (token.Equals(" ") || token.Equals("-") ||
                   token.Equals("*") || token.Equals("/"));
        }

对栈的元素举行排序

  Stack<int> arr1 = new Stack<int>();
            arr1.Push(9);
            arr1.Push(3);
            arr1.Push(4);
            arr1.Push(7);
            arr1.Push(2);

  public Stack<int> StackSort(Stack<int> arr)
        {
            if (arr.Count==0)
            {
                return new Stack<int>();
            }
            Stack<int> newStack = new Stack<int>();
            int top = arr.Pop();
            newStack.Push(top);
            while (arr.Count>0)
            {
                int first = arr.Pop(); //拿出第一个
                while (newStack.Count > 0 && first > newStack.Peek())
                {
                    int temp = newStack.Pop();
                    arr.Push(temp);
                }
                newStack.Push(first);
            }
            while(newStack.Count>0)
            {
                int temp = newStack.Pop();
                arr.Push(temp);
            }
            return arr;
        }

推断表达式是不是括号均衡

设想一个算法,推断用户输入的表达式中括号是不是婚配,表达式中能够含有圆括号、中括号和大括号。

  bool CheckBlancedParentheses(string ch)
        {
            char[] arr = ch.ToCharArray();
            if (0 == arr.Length)
                return false;
            Stack<char> stack=new Stack<char>();
         
           for(int i=0;i<arr.Length;i  )
            { 
                if ('(' == arr[i] || '[' == arr[i] || '{' == arr[i])
                    stack.Push(arr[i]);

                else if (')' == arr[i])
                {
                    if (stack.Count == 0)
                        return false;
                    else if ('(' != stack.Peek())
                        return false;
                    else stack.Pop();
                }
                else if (']' == arr[i])
                {
                    if (stack.Count == 0)
                        return false;
                    else if ('[' != stack.Peek())
                        return false;
                    else stack.Pop();
                }
                else if ('}' == arr[i])
                {
                    if (stack.Count== 0)
                        return false;
                    else if ('{' != stack.Peek())
                        return false;
                    else stack.Pop();
                }
            }
            if (stack.Count>0)
                return true;
            return false;
        }

运用栈完成行列

        Stack stack1 = new Stack();
        Stack stack2 = new Stack();
        public void Push(Object o)
        {
            stack1.Push(o);
        }
        public Object Pop()
        {
            Object o = null;

            if (stack2.Count == 0)
            {
                //把stack1的数据放入stack2,留下末了一个数据
                while (stack1.Count > 1)
                {
                    stack2.Push(stack1.Pop());
                }
                if (stack1.Count == 1)
                {
                    //把stack1的留下的谁人数据返回进来
                    o = stack1.Pop();
                }
            }
            else
            {
                o = stack2.Pop();
            }

            return o;
        }

行列

运用行列透露表现栈

        Queue<int> queue1 = new Queue<int>();
        Queue<int> queue2 = new Queue<int>();

        public void Push(int o)
        {
            queue1.Enqueue(o);
        }
        public int Pop()
        {
            int num = 0;
            while (queue1.Count > 1)
            {
                queue2.Enqueue(queue1.Dequeue());
            }
            if (queue1.Count == 1)
            {
                //把queue1的留下的谁人数据返回进来
                num = queue1.Dequeue();
                while (queue2.Count > 0)
                {
                    queue1.Enqueue(queue2.Dequeue());
                }
            }
            return num;
        }

对行列的前k个元素倒序

 public Queue<int> ReversalQueue(Queue<int> queue ,int k)
        {
            Queue<int> queue2 = new Queue<int>();
            if (queue.Count == 0) return queue2;

            Stack<int> stack = new Stack<int>();

            for(int i=0;i<k;i  )
            {
                stack.Push(queue.Dequeue());
            }
            while(stack.Count>0)
            {
                queue2.Enqueue(stack.Pop());
            }
            while(queue.Count>0)
            {
                queue2.Enqueue(queue.Dequeue());
            }
            return queue2; 

        }

链表

反转链表

  放上中心代码,感兴趣的能够在博客园内里搜一下,许多博友有引见
   public LinkNode<T> Reverse(LinkNode<T> node1, LinkNode<T> node2)
        {
            bool head= false;
            if (node1 == this.Head) head = true;
            LinkNode<T> tmp = node2.Next;
            node2.Next = node1;
            if (head) node1.Next = null;
            if (tmp == null) {
                return node2; }
            else
            {
               return Reverse(node2, tmp);
            }
        }

链表是不是有轮回

触及到指针

-玖富娱乐是一家为代理招商,直属主管信息发布为主的资讯网站,同时也兼顾玖富娱乐代理注册登录地址。-
  • 单链表推断是不是存在轮回,即推断是不是有两个指针指向统一地位,即推断海量指针中是不是有雷同数据。然后对一切指针挑选插入排序或许疾速排序。
  • 将一切的遍历过的节点用哈希表存储起来,用节点的内存地址作为哈希表的值存储起来。每遍历一个节点,都在这个构造中查找是不是遍历过。若是找到有反复,则申明该链表存在轮回。若是直到遍历完毕,则申明链表不存在轮回。哈希表中存储的值为节点的内存地址,如许查找的操纵所需时候为O(1),遍历操纵须要O(n),hash表的存储空间须要分外的O(n)。以是全部算法的时候复杂度为O(n),空间复杂度为O(n)。

找到运用处所再转头来补,或许看上一篇文章,链接中是其他博友的引见并附有代码

找到运用处所再转头来补,或许看上一篇文章,链接中是其他博友的引见并附有代码

字典树

找到运用处所再转头来补,或许看上一篇文章,链接中是其他博友的引见并附有代码

哈希表

Dictionary的内部完成机制,Dictionary怎样完成疾速查找

先看源码

       // buckets是哈希表,用来寄存Key的Hash值
        // entries用来寄存元素列表
        // count是元素数目
        private void Insert(TKey key, TValue value, bool add)
        {
            if (key == null)
            {
                throw new ArgumentNullException(key.ToString());
            }
            // 起首分派buckets和entries的空间
            if (buckets == null) Initialize(0);
            int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF; // 盘算key值对应的哈希值(HashCode)
            int targetBucket = hashCode % buckets.Length; // 对哈希值求余,取得须要对哈希表举行赋值的地位

#if FEATURE_RANDOMIZED_STRING_HASHING
            int collisionCount = 0;
#endif
            // 处置惩罚争执的处置惩罚逻辑
            for (int i = buckets[targetBucket]; i >= 0; i = entries[i].next)
            {
                if (entries[i].hashCode == hashCode && comparer.Equals(entries[i].key, key))
                {
                    if (add)
                    {
                        throw new ArgumentNullException();
                    }
                    entries[i].value = value;
                    version  ;
                    return;
                }

#if FEATURE_RANDOMIZED_STRING_HASHING
                collisionCount  ;
#endif
            }

            int index; // index记录了元素在元素列表中的地位
            if (freeCount > 0)
            {
                index = freeList;
                freeList = entries[index].next;
                freeCount--;
            }
            else
            {
                // 若是哈希表寄存哈希值已满,则从新从primers数组中掏出值来作为哈希表新的巨细
                if (count == entries.Length)
                {
                    Resize();
                    targetBucket = hashCode % buckets.Length;
                }
                // 巨细若是没满的逻辑
                index = count;
                count  ;
            }

            // 对元素列表举行赋值
            entries[index].hashCode = hashCode;
            entries[index].next = buckets[targetBucket];
            entries[index].key = key;
            entries[index].value = value;
            // 对哈希表举行赋值
            buckets[targetBucket] = index;
            version  ;

#if FEATURE_RANDOMIZED_STRING_HASHING
            if(collisionCount > HashHelpers.HashCollisionThreshold && HashHelpers.IsWellKnownEqualityComparer(comparer)) 
            {
                comparer = (IEqualityComparer<TKey>) HashHelpers.GetRandomizedEqualityComparer(comparer);
                Resize(entries.Length, true);
            }
#endif
        }

疾速缘由 :运用哈希表来存储元素对应的地位,然后我们能够经由历程哈希值疾速地从哈希表中定位元素地点的地位索引,从而疾速获取到key对应的Value值(能够依据上一篇引见明白)

总结

写文章很少有圆满的说法,上一篇文章在宣布以后,我又新增修改了许多器械,有点"缝缝补补又三年"的觉得。这篇(下)也须要再举行遗漏查缺,哪天来设法主意了(比方哈希,二叉树,B树),又来举行完美。 写博文的重要目标是完美稳固本身的学问系统,翻阅大批文章来进修的一个历程,目标其实不是为了赞扬,不信你看看赞扬,是不是看到了信奉。 该系列上中下基本终究完毕,关于大神来讲,数据构造就是小菜一碟(数据构造也不止我写的这么点),但对许多来人,之前关于数据构造的3W都没怎样花心思去想,若是有人问到了,是不是是很忸捏。接下来,我会继承稳固基本(这个小我觉的非常重要)和研讨框架和微效劳,继承勤奋!

-玖富娱乐是一家为代理招商,直属主管信息发布为主的资讯网站,同时也兼顾玖富娱乐代理注册登录地址。