Fancy DSA Fancy DSA
数据结构
算法
LeetCode
  • 关于
  • 导航 (opens new window)
  • 分类
  • 标签
  • 归档
设计模式 (opens new window)
博客 (opens new window)
GitHub (opens new window)

Jonsam NG

想的更多,也要想的更远
数据结构
算法
LeetCode
  • 关于
  • 导航 (opens new window)
  • 分类
  • 标签
  • 归档
设计模式 (opens new window)
博客 (opens new window)
GitHub (opens new window)
  • 开始上手
  • Plan 计划
  • Roadmap 路线
  • 算法简介
  • Sort 排序

  • Search 搜索

  • Recursive 递归

  • Graph 图

  • Tree 树

  • Math 数学

  • Hash 哈希

  • String 字符串

  • BitManipulation 位操纵

  • Backtracking 回溯

  • DynamicProgramming 动态规划

    • ClimbingStairs [爬楼梯]
    • CoinChange [钱币兑换]
    • EditDistance [编辑距离]
    • FibonacciNumber [斐波那契数]
    • FindMonthCalendar [月历]
      • 介绍
      • 实现
      • 扩展
    • KadaneAlgo [最大连续子数组和之Kadane算法]
    • LevenshteinDistance [莱文斯坦距离]
    • LongestCommonSubsequence [最长公共子序列]
    • LongestIncreasingSubsequence [最长递增子序列]
    • LongestPalindromicSubsequence [最长回文子序列]
    • LongestValidParentheses [最长合法括号]
    • MaxNonAdjacentSum [最大非连接子集和]
    • MaxProductOfThree [最大三数积]
    • MinimumCostPath [最小代价路径]
    • NumberOfSubsetEqualToGivenSum [等和子集]
    • RodCutting [棒材切割问题]
    • Shuf [随机样本]
    • SieveOfEratosthenes [埃拉托斯特尼筛法]
    • SlidingWindow [滑窗]
    • SudokuSolver [数独]
    • TrappingRainWater [接住雨水]
    • TribonacciNumber [翠波那契数]
    • ZeroOneKnapsack [零一背包]
  • Cache 缓存

  • Array 数组

  • Ciphers 密码学

  • Conversions 转换

  • ProjectEuler 欧拉计划

  • 其他

  • 算法
  • DynamicProgramming 动态规划
jonsam
2022-09-26
目录

FindMonthCalendar [月历]

# 介绍

给定 mm/yyyy 的月份,打印次月份的月历。

# 实现

# JavaScript

/*
*  This algorithm accepts a month in the format mm/yyyy.
*  And prints out the month's calendar.
*  It uses an epoch of 1/1/1900, Monday.
*/

class Month {
  constructor () {
    this.Days = ['M', 'T', 'W', 'Th', 'F', 'S', 'Su']
    this.BDays = ['M', 'Su', 'S', 'F', 'Th', 'W', 'T']
    this.epoch = { month: 1, year: 1900 }
    this.monthDays = [31, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
    this.monthDaysLeap = [31, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
  }

  printCal (days, startDay, output = value => console.log(value)) {
    output('M   T   W   Th  F   S   Su')
    const dates = []; let i;
    for (i = 1; i <= days; i++) {
      dates.push(i)
    }
    for (i = 0; i < this.Days.indexOf(startDay); i++) {
      dates.unshift(' ')
    }
    while (true) {
      let row = ''
      for (i = 0; (i < 7) && (dates.length !== 0); i++) {
        row += dates.shift()
        while ((row.length % 4) !== 0) {
          row += ' '
        }
      }
      output(row)
      if (dates.length === 0) break
    }
  }

  parseDate (date) {
    const dateAr = []; let block = ''; let i
    for (i = 0; i < date.length; i++) {
      if (date[i] === '/') {
        dateAr.push(parseInt(block))
        block = ''
        continue
      }
      block += date[i]
    }
    dateAr.push(parseInt(block))
    if (dateAr.length !== 2) throw new Error('Improper string encoding')
    const dateOb = { month: dateAr[0], year: dateAr[1] }
    return dateOb
  }

  isLeapYear (year) {
    if (((year % 400) === 0) || (((year % 100) !== 0) && ((year % 4) === 0))) return true
    return false
  }

  isGreater (startDate, endDate) {
    if (startDate.year > endDate.year) {
      return true
    } else if (startDate.year < endDate.year) {
      return false
    } else if (startDate.month > endDate.month) {
      return true
    } else if (startDate.month < endDate.month) {
      return false
    }
    return true
  }

  getDayDiff (startDate, endDate) {
    if (this.isGreater(startDate, endDate) === null) {
      return 0
    } else if ((this.isGreater(startDate, endDate) === true)) {
      const midDate = startDate
      startDate = endDate
      endDate = midDate
    }
    let diff = 0
    while (startDate.year !== endDate.year) {
      diff += (this.isLeapYear(startDate.year)) ? 366 : 365
      startDate.year = startDate.year + 1
    }
    while (startDate.month !== endDate.month) {
      if (startDate.month < endDate.month) {
        if (this.isLeapYear(startDate.year)) diff += this.monthDaysLeap[startDate.month]
        else diff += this.monthDays[startDate.month]
        startDate.month = startDate.month + 1
      } else {
        if (this.isLeapYear(startDate.year)) diff -= this.monthDaysLeap[startDate.month - 1]
        else diff -= this.monthDays[startDate.month - 1]
        startDate.month = startDate.month - 1
      }
    }
    return diff
  }

  generateMonthCal (date) {
    const Month = this.parseDate(date); let day = ''
    let difference = this.getDayDiff(this.epoch, Month)
    difference = difference % 7
    let Month2 = this.parseDate(date)
    day = (this.isGreater(Month2, this.epoch)) ? this.Days[difference] : this.BDays[difference]
    Month2 = this.parseDate(date)
    if (this.isLeapYear(Month2.year)) this.printCal(this.monthDaysLeap[Month2.month], day)
    else this.printCal(this.monthDays[Month2.month], day)
  }
}

// const x = new Month()
// x.generateMonthCal('1/2021')
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112

# 扩展

# 通过年月计算月中天数

const getMonthDays = (monthNumber, year) => {
  const the31DaysMonths = [1, 3, 5, 7, 8, 10, 12]
  const the30DaysMonths = [4, 6, 9, 11]

  if (!the31DaysMonths.includes(monthNumber) && !the30DaysMonths.includes(monthNumber) && (monthNumber !== 2)) {
    throw new TypeError('Invalid Month Number.')
  }

  if (the31DaysMonths.includes(monthNumber)) return 31 
  if (the30DaysMonths.includes(monthNumber)) return 30 

  // Check for Leap year
  // (year % 400) === 0) || (((year % 100) !== 0) && ((year % 4) === 0))
  if (year % 4 === 0) {
    if ((year % 100 !== 0) || (year % 100 === 0 && year % 400 === 0)) {
      return 29
    }
  }

  return 28
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

# 计算两日相差天数

/*
    DateDayDifference Method
    ------------------------
    DateDayDifference method calculates the number of days between two dates.

    Algorithm & Explanation : https://ncalculators.com/time-date/date-difference-calculator.htm
*/

// Internal method for make calculations easier
const isLeap = (year) => {
  if (year % 400 === 0) return true
  else if (year % 100 === 0) return false
  else if (year % 4 === 0) return true
  else return false
}
const DateToDay = (dd, mm, yyyy) => {
  return Math.floor((365 * (yyyy - 1)) + ((yyyy - 1) / 4) - ((yyyy - 1) / 100) + ((yyyy - 1) / 400) + dd + (((367 * mm) - 362) / 12) + (mm <= 2 ? 0 : isLeap(yyyy) ? -1 : -2))
}

const DateDayDifference = (date1, date2) => {
  // firstly, check that both input are string or not.
  if (typeof date1 !== 'string' && typeof date2 !== 'string') {
    return new TypeError('Argument is not a string.')
  }
  // extract the first date
  const [firstDateDay, firstDateMonth, firstDateYear] = date1.split('/').map((ele) => Number(ele))
  // extract the second date
  const [secondDateDay, secondDateMonth, secondDateYear] = date2.split('/').map((ele) => Number(ele))
  // check the both data are valid or not.
  if (firstDateDay < 0 || firstDateDay > 31 ||
        firstDateMonth > 12 || firstDateMonth < 0 ||
        secondDateDay < 0 || secondDateDay > 31 ||
        secondDateMonth > 12 || secondDateMonth < 0) {
    return new TypeError('Date is not valid.')
  }
  return Math.abs(DateToDay(secondDateDay, secondDateMonth, secondDateYear) - DateToDay(firstDateDay, firstDateMonth, firstDateYear))
}

// Example : DateDayDifference('17/08/2002', '10/10/2020') => 6630
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

# 计算某日周几

/*
                    DateToDay Method
                    ----------------
    The DateToDay method takes a date in string format and
    returns the name of a day. The approach behind this method
    is very simple, we first take a string date and check
    whether their date is valid or not, if the date is valid
    then we do this But apply the algorithm shown below. The
    algorithm shown below gives us the number of the day and
    finally converts it to the name of the day.

    Algorithm & Explanation : https://cs.uwaterloo.ca/~alopez-o/math-faq/node73.html
*/

// March is taken as the first month of the year.
const calcMonthList = {
  1: 11,
  2: 12,
  3: 1,
  4: 2,
  5: 3,
  6: 4,
  7: 5,
  8: 6,
  9: 7,
  10: 8,
  11: 9,
  12: 10
}

// show the week day in a number : Sunday - Saturday => 0 - 6
const daysNameList = { // weeks-day
  0: 'Sunday',
  1: 'Monday',
  2: 'Tuesday',
  3: 'Wednesday',
  4: 'Thursday',
  5: 'Friday',
  6: 'Saturday'
}

const DateToDay = (date) => {
  // firstly, check that input is a string or not.
  if (typeof date !== 'string') {
    return new TypeError('Argument is not a string.')
  }
  // extract the date
  const [day, month, year] = date.split('/').map((x) => Number(x))
  // check the data are valid or not.
  if (day < 0 || day > 31 || month > 12 || month < 0) {
    return new TypeError('Date is not valid.')
  }
  // divide year to century and yearDigit value.
  const yearDigit = (year % 100)
  const century = Math.floor(year / 100)
  // Apply the algorithm shown above
  const weekDay = Math.abs((day + Math.floor((2.6 * calcMonthList[month]) - 0.2) - (2 * century) + yearDigit + Math.floor(yearDigit / 4) + Math.floor(century / 4)) % 7)
  // return the weekDay name.
  return daysNameList[weekDay]
}

// Example : DateToDay("18/12/2020") => Friday
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
编辑 (opens new window)
上次更新: 2022/10/28, 17:23:56
FibonacciNumber [斐波那契数]
KadaneAlgo [最大连续子数组和之Kadane算法]

← FibonacciNumber [斐波那契数] KadaneAlgo [最大连续子数组和之Kadane算法]→

最近更新
01
0-20题解
10-31
02
本章导读
10-31
03
算法与转换:Part1
10-28
更多文章>
Theme by Vdoing | Copyright © 2022-2022 Fancy DSA | Made by Jonsam by ❤
  • 跟随系统
  • 浅色模式
  • 深色模式
  • 阅读模式