目錄
1. 問題描述
2. 解題分析
2.1 每個月的日歷的矩陣表示
2.2 假日和調休公休日的處理
2.3 求最大矩形
2.3.1 暴力搜索
2.3.2 滑動窗搜索
3. 代碼及測驗
4. 后記
1. 問題描述
2. 解題分析
2.1 每個月的日歷的矩陣表示
在python中可以用calendar模塊的monthcalendar()來實作，參見另一篇博客Python calendar模塊的常用有趣用法https://blog.csdn.net/chenxy_bwave/article/details/121251954
https://blog.csdn.net/chenxy_bwave/article/details/121251954，以下分別為兩種方式列印的日歷，第一條陳述句是將星期日設定為一周的第一天，
import calendar
calendar.setfirstweekday(calendar.SUNDAY)
calendar.prmonth(2014,4)
print(np.array(calendar.monthcalendar(2014,4)))列印效果如下：
2.2 假日和調休公休日的處理
首先考慮假日的資料， 假日的資料在檔案中是以以下形式存盤的：
可以按行以字串的形式讀入，然后利用python datetime中模塊將它們變換成datetime.datetime object并從中提取出年、月、日資訊，然后再基于這個年月日資訊將上一節得到的矩陣的對應元素置為0（表示非作業日）， 接下來考慮因調休變為作業日的公休日的資料，存盤格式同上，以同樣方式處理即可，只不過這次是將對應元素置為非0值（比如說置為1即可） 在以下代碼中用readfile()函式來從以上兩個檔案中讀取資料，并提取日期資訊，恢復出其中的年、月、日，然后存盤在一個dict型別變數中，以(year, month)為key，value則是包含對應年月中的日期的串列，其中，設計到了利用datetime模塊進行處理，關于datetime模塊使用方法的簡要介紹，參見博客：Python中日期時間處理：datetime包的實用示例https://blog.csdn.net/chenxy_bwave/article/details/120977111https://blog.csdn.net/chenxy_bwave/article/details/120977111
2.3 求最大矩形
2.3.1 暴力搜索
首先，求最大矩形問題當然可以用暴力搜索的方法來求解，
比如說，一個2*2的矩陣，其中以矩陣最左上角格子(0,0)為最左上角的矩形有多少個呢？恰好是4個，對于一般的情況n*m的矩陣，其中以矩陣最左上角格子(0,0)為最左上角的矩形總共有n*m個，掃描這n*m個矩形排除掉中間含有0元素的矩形（或者將其面積置0更簡單），求剩下矩形的最大面積即得“以矩陣最左上角格子(0,0)為最左上角的矩形”的最大面積，接下來，同理可以求得以格子(0,1)、(0,2)、，，，、(1,0)、(1,1)、為最左上角的矩形的最大面積，再求這些最大值中的最大值即得當前矩陣中不含0元素的最大矩形面積，
這樣暴力搜索的復雜度是多少呢？為簡便起見，考慮原矩陣為正方形，大小為n*n
首先，對矩形最左上角的格子的掃描，n*n
其次，針對每個矩形最左上角格子候選，其對應的可能的矩形數取決于它的坐標，假定它的坐標為(i,j)，則可能的矩形數為(n-i)*(n-j)
這樣，總的需要評估其面積的矩形個數為：
這種方案只能想一想作為基準參考，不能去實作，
2.3.2 滑動窗搜索
暴力搜索是以格子（考慮某個格子為所求矩形的左上角格子）為基點進行搜索，也可以從另一個角度考慮滑動窗方案，考慮以不同大小和形狀的矩形框在日歷矩形上滑動，因為是要求最大的矩形面積，所以掃描用的滑動矩形窗面積按從大到小的順序安排，這樣找到了第一個不包含0的滑動位置就找到了原題要求的最大矩形面積，
由于有可能多種形狀的矩形框具有相同的面積，比如說4*2和2*4的矩形框的面積都為8，所以先構建一個字典，以面積為key，對應的可能的形狀的串列作為value，代碼如下：
# 2. Construct the dictionary for rectangulars area-shape pair
area_shape = dict()
for i in range(1,6):
for j in range(1,8):
if i*j not in area_shape:
area_shape[i*j] = []
area_shape[i*j].append((i,j))有了以上準備作業后，針對某個月的處理流程如下所示：
注1：將holidays和extra-workdays對應元素的值重置時需要根據日期資訊去確定它在矩陣中的對應位置，首先需要確定當月的第一天對應的weekday(星期幾)，這樣就能確定當月1日在矩陣中的位置，進而可以推得指定日期在矩陣中的位置，這個處理對應于以下代碼（extra-workday的處理與此相同）：
# Set holidays to 0
if (y,m) in h:
holidays = h[(y,m)]
for hday in holidays:
# Find the position of the current holiday in month calendar matrix
i = (hday + fst_wkday - 1)//7
j = (hday + fst_wkday - 1)%7
c[i,j] = 03. 代碼及測驗
# -*- coding: utf-8 -*-
"""
Created on Thu Nov 11 09:35:28 2021
@author: chenxy
"""
import sys
import time
from datetime import datetime
import math
# import random
from typing import List
from collections import deque
import itertools as it
import numpy as np
import calendar
# Set SUNDAY to the first weekday
calendar.setfirstweekday(calendar.SUNDAY)
calendar.prmonth(2014,4)
print(np.array(calendar.monthcalendar(2014,4)))
def readfile(filename:str)->dict:
'''
Read holiday file and extra-workday file
Parameters
----------
filename : string
Returns
-------
A dictionary to store the data
'''
print('Read {0} line by line, and store the holidays into a dictionary...'.format(filename))
dat = dict()
f=open(filename,'r')
if f.mode == 'r':
f_lines = f.readlines()
for line in f_lines:
# print(line,end='')
date_object = datetime.strptime(line[:10], "%Y/%m/%d") # Strip the last '\n' in line
# print("date_object ={}-{}-{}".format(date_object.year,date_object.month,date_object.day))
y,m,d = date_object.year,date_object.month,date_object.day
if (y,m) not in dat:
dat[(y,m)] = []
dat[(y,m)].append(d)
f.close()
return dat
# 1. Read the data file
h = readfile('q62-holiday.txt')
e = readfile('q62-extra-workday.txt')
# 2. Construct the dictionary for rectangulars area-shape pair
area_shape = dict()
for i in range(1,6):
for j in range(1,8):
if i*j not in area_shape:
area_shape[i*j] = []
area_shape[i*j].append((i,j))
# 3. loop over year/month to find the maximum rectangular of each month
max_area = dict()
for y in range(2014,2015):
for m in range(4,7):
# calendar.prmonth(y,m)
c = np.array(calendar.monthcalendar(y,m))
# Set the first and the last column to 0
c[:,0] = 0
c[:,6] = 0
# print('The original month calendar:\n',c)
# find the first weekday of the current month
fst_wkday, num_days = calendar.monthrange(y, m)
fst_wkday = (fst_wkday + 1)%7 # Because the SUNDAY is set to the first weekday
# Set holidays to 0
if (y,m) in h:
holidays = h[(y,m)]
for hday in holidays:
# Find the position of the current holiday in month calendar matrix
i = (hday + fst_wkday - 1)//7
j = (hday + fst_wkday - 1)%7
c[i,j] = 0
# Set extra-workday to 100--any positive value is OK
if (y,m) in e:
extras = e[(y,m)]
for eday in extras:
# Find the position of the current extra workday in month calendar matrix
i = (eday + fst_wkday - 1)//7
j = (eday + fst_wkday - 1)%7
c[i,j] = 100
# print('The month calendar after holidays and extra workdays setting:\n',c)
# Search for the maximum rectangular only covering workday
found = False
for a in range(35,0,-1):
# print(a)
if a in area_shape:
ij_list = area_shape[a]
for (i,j) in ij_list:
for i0 in range(5-i+1):
for j0 in range(7-j+1):
rect = c[i0:i0+i,j0:j0+j]
# print(a,i,j,i0,j0, rect)
if np.all(rect):
max_area[(y,m)] = a
found = True
break
if found:
break
if found:
break
if found:
break
print(max_area)
運行結果：{(2014, 4): 16, (2014, 5): 20, (2014, 6): 16}
以上代碼沒有完全回答題目所問的問題，原因是原書所附帶資料并不完整，只有到2012/10/07為止的資料，所以我只參考題圖補充了2014年4,5,6月的假日資料（這三個月沒有公休日調休的情況），并測驗了這三個月的最大矩形面積與題目描述中提示的值是否一致，但是，關于2014年6月的題目描述中提示的值其實是錯的，很顯然存在一個4*4的瓦完全作業日的矩形區域，
4. 后記
由于不熟悉日期和日歷的處理，花了一些時間做學習python的calendar和datetime兩個模塊的處理，本應作為這道題的核心演算法的求最大矩形的問題，與日期和日期的處理相比感覺反而相形見絀了，
上一篇：Q61: 不交叉一筆畫下去
下一篇：Q63: 迷宮會合
本系列總目錄參見：程式員的演算法趣題：詳細分析和Python全解
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/356747.html
標籤：其他