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

交作业

Homework2 好好学习 天天向上！

各种小问题太多了

It is the true time to draw some conclusions fot the hw2. I think conclusion is more important than the solution to question itself.
Following is my three steps to finish them.
1.completing the date.java
        --use 2 hours finish
        --the begining way to solve
             --isLeapYear : the logic is vital. The impressive thing is to use a good && ||.
             --isBefore and isAfter  the connnection but also focus on the equal situation.
             --dayinmonth, dayinyear : connection
             --difference: use the dayinyear method
             --Date(String s)   use the String.split  (search the API)
2.find out other people's solutions to compare with yourself and then modify your codes
        --use 1 hour
        --modify two things
             --modify the (if else and && ||) such as the logic in isBefore() method (the goal is touse less if else but more || and &&) **
             --modify the daysInYear() dont forget to use the dayInMonth() *****
3.conculusion
         -- view the date.java in a broad way.
              --in Date CLass:  prviate field, two constructors, three static method(isLeapYear dayInMonth isValidDate, think why???) toString().
              --the connection among some methods.

弄了好久才做出来

打卡交作业~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
  }