Halo

领域建模 - 对象状态

课程网页

https://sysu-swsad.github.io/swad-guide/09-domain-modeling

介绍

  之前介绍过快速排序，相比起快排，归并排序是stable的。所谓的stable，是指算法的实现保持了相同的元素之间的顺序（the implementation preserves the input order of equal elements in the sorted order）。它采用了分治的思路。从时间复杂度来看，快排平均复杂度是$O(nlogn)$，最坏情况下是$O(n^2)$；归并排序的时间复杂度总是$O(nlogn)$，这是他的优势所在。

题目描述

  这是一道经典的字符串题目，要求翻转字符串的每一个部分，每一个部分由.分隔开，但部分内部保持原来的顺序，并且只能够在原字符串上操作，不能使用额外的内存空间（允许用一个char的空间），也不能够使用<string>的reverse()函数。

介绍

  说到排序算法，许多小白脱口而出的都是冒泡排序、插入排序等。但是如果考虑到时间复杂度，上面这几种算法效率就不是这么高了，对于大量的数据排序，我们需要更加快速的排序方法。在这篇博客我们就来看看快速排序。

题目

  字节跳动的经典笔试题：为了不断优化推荐效果，今日头条每天要存储和处理海量数据。假设有这样一种场景：我们对用户按照它们的注册时间先后来标号，对于一类文章，每个用户都有不同的喜好值，我们会想知道某一段时间内注册的用户（标号相连的一批用户）中，有多少用户对这类文章喜好值为k。因为一些特殊的原因，不会出现一个查询的用户区间完全覆盖另一个查询的用户区间。

题目内容

题目OJ地址：http://acm.hit.edu.cn/problemset/1062

在黑板上写N个正整数组成的一个数列，进行如下操作：每次擦去其中的两个数$a$和$b$，然后在数列中加入$a \times b + 1$，如此下去直至黑板上剩下一个数字，在所有按这种操作方式最后得到的数中，最大的为max，最小的为min，则该数列的极差定义为M = max - min。请编程计算出给定数列的极差。

题目

  一道经典的字符串题目，但是最近看到有一种新的思路，所以拿出来分享。

  题目描述：给定一个仅包含0或1的字符串，现在可以对其进行一种操作，当有两个相邻的字符其中一个是0另外一个是1的时候，可以消除这两个字符。这样的操作一直进行下去，直到找不到相邻的0和1为止，问这个字符串经历了操作以后的最短长度。

Assignment8

1. 构造NextDate问题的弱一般的等价类测试用例。
   • NextDate问题：NextDate()是整型变量month，day和year的函数，输入1812-2012年期间的某一日期的month，day和year的值，输出这一天的下一天的日期的month，day和year值。