Berkeley CS 61B Data Structures(in Java) Homework2 加分+讨论帖

打卡交作业~hw就慢慢有难度了。。算法真是无止境-。-

交作业，交作业。一道一道跟下来，更加感到这个课不仅是讲的清楚，课后作业的设置尤其好。总是能骚到痛处。也多谢前面各位的总结和讨论获益良多。大家共勉。


补充内容 (2017-4-3 00:54):
哇哈哈，看到楼下，又回头看了自己的，也是“居然有错”。。。isbefore()少了 this.day=d.day，立马改正，图就不再传了 ：）

半个月前做的 下午认真一看 居然有错 留在迟点有空再找
警示

终于做完了。卡在constructor，this 和 tostring很久。需要学习基础知识和简化code。

这里介绍一种常数时间复杂度的difference函数实现：
由于除了闰年都是1年365天，因此这里的关键是在于判断两个年份之间闰年的个数：
闰年个数 ＝ 2年份间所有4的倍数 － 2个年份间经过的所有100的倍数 ＋ 2年份间经过的所有400的倍数。

所以关键的问题又转化为了如何判断两个数a和b之间的c的倍数的个数，注意到对任意的a和c：

在a到a+c-1之间(含边界)有且只有1个c的倍数；
在a+c到a+2c-1之间(含边界)有且只有1个c的倍数；
...
在a+kc到a+(k+1)c-1之间(含边界)有且只有1个c的倍数；

于是可以知道：在a到a+kc-1之间(含边界)一定有且只有k个c的倍数；

然后注意到另一个事实：一定存在1个整数n，使得a+nc-1<b<=a+(n+1)c-1成立。
根据上面的结论，可以知道，只要找到这个n，那么a和b之间c的倍数个数(含边界)就等于：n 加上 (a+nc)和b之间c的倍数个数。而要求 (a+nc)和b之间c的倍数个数，只需要遍历 (a+nc)到b，逐个检查是否能够被c整除，最多也只要循环c次就能求得结果。

因此只要能求得上述的n的值，就能以O(c)的复杂度计算出两个数a和b之间的c的倍数的个数。
而n实际上非常好求，注意到有：n ＝ [(b+1-a)/c]，于是我们得到了一个以O(c)的时间复杂度计算两个数a和b之间的c的倍数的个数的算法。

而在闰年个数的计算中，c分别等于4，100以及400，皆是常数，于是我们得到了一个常数时间复杂度O(1)，计算两个给定的年份之间所经历的闰年个数的算法，进而可以常数时间复杂度来计算difference的值。

下面贴上我的代码：

  public static int countDivideBy(int startNumber, int endNumber, int divideNumber) {
    if(startNumber > endNumber) {
      return 0;
    }
    int kNumber = (endNumber + 1 - startNumber) / divideNumber;
    for(int i = startNumber + kNumber * divideNumber - 1;i <= endNumber;i++) {
      if(i % divideNumber == 0) kNumber ++;
    }
    return kNumber;
  }
  public static int countLeapYear(int startYear, int endYear) {
    return countDivideBy(startYear,endYear,4) - countDivideBy(startYear,endYear,100) + countDivideBy(startYear,endYear,400);
  }

  public int difference(Date d) {

    if(!isValidDate(d.month,d.day,d.year)){
      System.out.println("Invalid date value!");
      System.exit(0);
    }

    int dayNumberOfYearD = 365;
    int dayNumberOfYearThis = 365;
    if(isLeapYear(d.year)) dayNumberOfYearD++;
    if(isLeapYear(this.year)) dayNumberOfYearThis++;

    if(this.year == d.year) return this.dayInYear() - d.dayInYear();
    if(this.year > d.year) {
      return this.dayInYear() + (dayNumberOfYearD - d.dayInYear()) + 365*(this.year - d.year - 1) + countLeapYear(d.year+1,this.year-1);      
    } else {
      return -(dayNumberOfYearThis - this.dayInYear()) - d.dayInYear() - 365*(d.year - this.year - 1) - countLeapYear(this.year+1,d.year-1);
    }                          // replace this line with your solution
  }

来交作业了，新学了一个String [] d = s.split("/");

1 需要学习的是如何把overall task 转化为subtasks。
2 public boolean isAfter(Date b) {
        return compareTo(b) > 0;
3 the method of class String: split

打卡   difference那里弄了好久

Testing constructors.
Date should be 1/1/1: 1/1/1
Date should be 2/4/2: 2/4/2
Date should be 2/29/2000: 2/29/2000
Date should be 2/29/1904: 2/29/1904
Date should be 12/31/1975: 12/31/1975
Date should be 1/1/1976: 1/1/1976
Date should be 1/2/1976: 1/2/1976

Testing LeapYear:
12/31/1975is a leap year: (should be false)false
1/1/1976is a leap year: (should be true)true

Testing daysInMonth:
12/31/1975 has 31 days in month

Testing dayinyear:
12/31/1975is the 365th day.
1/1/1976is the 1th day.

Testing before and after.
1/1/1976 after 12/31/1975 should be true: true
1/2/1976 after 1/1/1976 should be true: true
12/31/1975 after 12/31/1975 should be false: false
12/31/1975 after 1/1/1976 should be false: false
1/1/1976 after 1/2/1976 should be false: false
12/31/1975 before 1/1/1976 should be true: true
1/1/1976 before 1/2/1976 should be true: true
12/31/1975 before 12/31/1975 should be false: false
1/1/1976 before 12/31/1975 should be false: false
1/2/1976 before 1/1/1976 should be false: false

Testing difference.
12/31/1975 - 12/31/1975 should be 0: 0
1/1/1976 - 12/31/1975 should be 1: 1
1/2/1976 - 12/31/1975 should be 2: 2
1/2/1976 - 2/27/1977 should be -422: -422
8/31/2110 - 2/27/1977 should be 48762: 48762

Process finished with exit code 0

交作业！！！