盛水最多的容器/接雨水-java动态规划

盛水最多的容器

题目描述

感觉对动态规划还是理解不够清楚,一开始想了半天还是全部遍历的方法,最好的方法其实是一次移动一个指针,height小的内移。

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

class Solution {
public int maxArea(int[] height) {
//值大的不动,值小的向内移动
if(height.length < 2)return 0;
int first = 0;
int last = height.length-1;
int cap = Math.min(height[first],height[last])*(last-first);
int tmp;
while(first != last){
if(height[first] > height[last]){
last -= 1;
tmp = Math.min(height[first],height[last])*(last-first);
if(tmp > cap)cap = tmp;
}
else{
first += 1;
tmp = Math.min(height[first],height[last])*(last-first);
if(tmp > cap)cap = tmp;
}
}
return cap;
}
}

接雨水

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
def trap(self, height: List[int]) -> int:
# 边界条件
if not height: return 0
n = len(height)
maxleft = [0] * n
maxright = [0] * n
ans = 0
# 初始化
maxleft[0] = height[0]
maxright[n-1] = height[n-1]
# 设置备忘录,分别存储左边和右边最高的柱子高度
for i in range(1,n):
maxleft[i] = max(height[i],maxleft[i-1])
for j in range(n-2,-1,-1):
maxright[j] = max(height[j],maxright[j+1])
# 一趟遍历,比较每个位置可以存储多少水
for i in range(n):
if min(maxleft[i],maxright[i]) > height[i]:
ans += min(maxleft[i],maxright[i]) - height[i]
return ans

太妙了,就只计算我头顶有多少水,最后加起来就行了,简洁明了。

基金分析,定时邮件提示

寒假搞基金,写了一个定时提醒的脚本,开学后就不用每天都关注行情了。策略很简单,在定投的基础上,多退少补。涨幅过高赎回,每周四逢低加倍。


执行的效果如图

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
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
import requests
import pandas as pd
import re
import sys
import math
import json
import smtplib
from email.mime.text import MIMEText
import time
import datetime
import numpy as np

def timeStamp_to_time_13(timeNum):
timeStamp = float(timeNum/1000)
timeArray = time.localtime(timeStamp)
otherStyleTime = time.strftime("%Y-%m-%d %H:%M:%S", timeArray)
print(otherStyleTime)

def is_trade_day(date):
server_url = "http://www.easybots.cn/api/holiday.php?d="
# 假如今天是周日
date1 = "".join(date.split('-'))
while(1):
req = requests.get(server_url + date1)
vop_data = json.loads(req.text)
if int(vop_data[date1]) == 2:#节假日
return False
elif int(vop_data[date1]) == 1:#周末
return False
else:
return True
time.sleep(3)
# #now = (datetime.datetime.utcnow() + datetime.timedelta(hours=8))
# sunday = date1.weekday()
# #print(sunday)
# # 如果今天是周日,则返回True
# if sunday == 6 or sunday == 5:
# return False
# else:
# return False
def get_month_year_firstday(error_month = 0):
#获得第一个不是周末的月初和年初日子

for i in range(1,10):

if(error_month == 1):
m_tmp = datetime.datetime.now().strftime('%m')
m_tmp = str(int(m_tmp)-1).rjust(2,"0")
month = datetime.datetime.now().strftime('%Y')+"-"+m_tmp+"-"+str(i).rjust(2,"0")
else:
month = datetime.datetime.now().strftime('%Y-%m')+"-"+str(i).rjust(2,"0")
if is_trade_day(month):
break
for i in range(1,10):
year = datetime.datetime.now().strftime('%Y')+"-01-"+str(i).rjust(2,"0")
if is_trade_day(year):
break

print(month,year)
return month,year
def get_daily_prise(date,fund_code):
"""
:param url: 网页URL
:parma date: 时间日期2020-01-16
:return: 累计净值和日增长率
"""
headers = {"Referer":"http://fundf10.eastmoney.com/jjjz_001811.html","Host":"api.fund.eastmoney.com"}
url = "http://api.fund.eastmoney.com/f10/lsjz?callback=jQuery18305100678071626792_1580736628860&fundCode="+fund_code+"&pageIndex=1&pageSize=20&startDate="+date+"&endDate="+date+"&_=1580736651052"
response = requests.request("GET", url, headers=headers)
tmp = json.loads(response.text[41:-1])['Data']
try:
print("success")
print(tmp['LSJZList'][0]['LJJZ'],tmp['LSJZList'][0]['JZZZL'])
return(tmp['LSJZList'][0]['LJJZ'],tmp['LSJZList'][0]['JZZZL'])
except IndexError:
print("IndexError")
return ("error","error")


def my_mail(message,conf):

msg_from=conf['sender'] #发送方邮箱
passwd=conf['password'] #填入发送方邮箱的授权码
msg_to_list=conf['receiver'] #收件人邮箱

subject="基金邮箱提示"
#print(message)
msg = MIMEText(message,"html")
msg['Subject'] = subject
msg['From'] = msg_from

for i in range(len(msg_to_list)):
msg_to = msg_to_list[i]
msg['To'] = msg_to
try:
s = smtplib.SMTP_SSL("smtp.qq.com",465)
s.login(msg_from, passwd) #登录SMTP服务器
s.sendmail(msg_from, msg_to, msg.as_string())#发邮件 as_string()把MIMEText对象变成str
print ("发送成功")
except s.SMTPException:
print ("发送失败")
finally:
s.quit()

def get_resonse(url):
"""
:param url: 网页URL
:return: 爬取的文本信息
"""
try:
r = requests.get(url)
r.raise_for_status()
r.encoding = 'utf-8'
return r.text
except:
print('Failed to get response to url!')
return ''
def get_realtime_anayls(code):
url = "http://fundgz.1234567.com.cn/js/"+code+".js"
r = get_resonse(url)
text_json = json.loads(r[8:-2])
return text_json

def get_fund_info(code):
failed_list = []
data_list = {}
url = 'http://fund.eastmoney.com/pingzhongdata/'+code+'.js'
response = get_resonse(url)
# 爬取失败等待再次爬取
if response is '':
return ''
else:
strs = re.findall(r'var(.*?);',response)
for i in range(0,len(strs)):
tmp = strs[i].split('=')
var_name = tmp[0].strip()
data_list[var_name] = [tmp[1]]
return data_list

def getYesterday(today=datetime.date.today()):

for i in range(1,100):
oneday=datetime.timedelta(days=i)
yesterday=today-oneday
print(yesterday)
if(is_trade_day(yesterday.strftime('%Y-%m-%d'))):
return yesterday

def make_csv():
fund_list = read_fund_list()
#print(fund_list)
yesterday_time = getYesterday()
print(yesterday_time)
now_date = yesterday_time.strftime('%Y-%m-%d')
final = []
final.append(['基金名称','今日累计净值','今日净增长'+now_date,'年初增长率','月初增长率','28号加倍','周四加倍','是否赎回'])
for i in range(1,len(fund_list)):
stock_json_str = get_fund_info(fund_list[i])
#stock_json = json.loads(stock_json_str)
tmp = []
tmp.append(stock_json_str['fS_name'][0].split('"')[1])
a,b = get_daily_prise(now_date,fund_list[i])
tmp.append(a)
tmp.append(b+'%')

print("年初和月初")
month,year = get_month_year_firstday()
#print( month,year)
month_price,rub = get_daily_prise(month,fund_list[i])
if month_price == "error":
month,year = get_month_year_firstday(error_month = 1)
month_price,rub = get_daily_prise(month,fund_list[i])
year_price,rub = get_daily_prise(year,fund_list[i])
print(year_price,month_price)
tmp.append(str((float(a)/float(year_price) - 1) * 100).ljust(5,"0")+"%")
tmp.append(str((float(a)/float(month_price) - 1) * 100).ljust(5,"0")+"%")
if((float(a)/float(year_price) - 1)<-0.05):
tmp.append("定投加三倍")
elif((float(a)/float(year_price) - 1)<-0.03):
tmp.append("定投加两倍")
elif((float(a)/float(year_price) - 1)<0.1):
tmp.append("不变")
else:
tmp.append("停止投入")


if((float(a)/float(month_price) - 1)<-0.05):
tmp.append("定投加三倍")
elif((float(a)/float(month_price) - 1)<-0.03):
tmp.append("定投加两倍")
elif((float(a)/float(month_price) - 1)<0.1):
tmp.append("不变")
else:
tmp.append("停止投入")


if((float(a)/float(month_price) - 1)>0.2):
tmp.append("赎回"+str((float(a)/float(month_price) - 1)-0.1))
elif((float(a)/float(month_price) - 1)>0.5):
tmp.append("赎回"+str((float(a)/float(month_price) - 1)-0.1))
else:
tmp.append("不必")
final.append(tmp)
df = pd.DataFrame(final,index=fund_list, columns=['基金名称','今日累计净值','今日净增长'+now_date,'年初增长率','月初增长率','28号加倍','周四加倍','是否赎回'])#生成6行4列位置
outputpath='fund.csv'
df.to_csv(outputpath,sep=',',index=False,header=False,encoding='utf_8_sig')
return(df)

def read_fund_list():
#read txt method one
f = open("fund_list.txt")
ans = []
ans.append("/")
line = f.readline()
ans.append(line.replace("\n",""))
while line:
line = f.readline()
ans.append(line.replace("\n",""))
f.close()
return list(filter(None, ans))

if __name__ == '__main__':
stock_json_str = get_fund_info("001811")
#stock_json = json.loads(stock_json_str)
# for i in stock_json_str.keys():
# print(i+":")
# print(stock_json_str[i])
# print("---------------------------------------------------------------------\n")

# text = get_realtime_anayls("001811")
#
# print(text_json)
# w782 comm lsjz


# timeStamp_to_time_13(1580728885284)
# is_week_lastday("2020-01-08")
df = make_csv()
conf = {'sender': 'qqnumber@qq.com', 'sender_name':'guo',
'receiver':['qqnumber@qq.com','qqnumber@qq.com'], 'password':'*********',
'server':'smtp.qq.com','port':465, 'receiver_name':['me','guest']}
df=pd.read_csv("fund.csv")
df.sort_values('月初增长率',inplace = False)
my_mail(df.to_html(),conf)
#print(get_realtime_anayls("001811"))

python socket调试

昨日写的websocket的调试测速脚本,未完善,精确到毫秒级别了,脚本自身的速度也会影响很大,感觉这个方法可信度不高。

长连接就是一次建立socket后不断开请求,短链接就是每次都重新建立socket请求,http即路由调试请求

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
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
import websocket
import json
import datetime
import numpy as np
import requests
import time

url_ws = "ws://127.0.0.1:8090/ws/1111"#"ws://yandongxunjing.club:8090/ws/1111" # 接口地址
url_http = "http://127.0.0.1:8090/gggg"#"http://yandongxunjing.club:8090/gggg"


content = [{"request_index":0,"time_stamp":111111111111111111,"source_id":13,"chapter_id":4,"event_id":4},{"request_index":1,"time_stamp":111111111111111111,"source_id":13,"chapter_id":4,"event_id":4}]
#0是菜单,1是内容
socket_time_list = []
http_time_list = []
time_list_socket_s = []
time_list_socket_l = []



send_list = []
def test_http(i):
#global
data={'message':str(content[i]),'sessionid':1111}
print(data)
r = requests.get(url_http,params=data)
print(r.text)

def on_message(ws, message):
endtime = datetime.datetime.now()
starttime = send_list.pop(0)
time_list_socket_l.append((starttime - endtime).microseconds)

# global times
# global endtime
# global starttime
# endtime = datetime.datetime.now()
# time_list_socket_l.append((starttime - endtime).microseconds)

# times -= 1
# if(times>0):
# starttime = datetime.datetime.now()
# ws.send(json.dumps(content[1]))
# #print(message)
# else:
# print("---------------------------------")
# print("短链接时间:")
# print(time_list_socket_s)
# print(np.mean(time_list_socket_s))
# print("---------------------------------")
# print("长连接时间:")
# print(time_list_socket_l)
# print(np.mean(time_list_socket_l))
# print("---------------------------------")
# print("http时间:")
# print(time_list_http)
# print(np.mean(time_list_http))
# print("times up")


def on_error(ws, error):
print(error)
def on_close(ws):
print("close connection")

def on_open(ws):
for i in range(20):
starttime = datetime.datetime.now()
ws1.send(json.dumps(content[1]))
send_list.append(starttime)
time.sleep(3)
#time_list_socket_l.append((starttime - endtime).microseconds)
#ws.send(json.dumps(content[1]))
print("on open")

if __name__ == "__main__":
time_list_http = []
# for i in range(20):
# starttime = datetime.datetime.now()
# test_http(1)
# endtime = datetime.datetime.now()
# time.sleep(3)
# time_list_http.append((endtime - starttime).microseconds)




# websocket.enableTrace(True)




for i in range(20):#短链接测试
starttime = datetime.datetime.now()
ws = websocket.create_connection(url_ws)

ws.send(json.dumps(content[1]))
result = ws.recv()
print(result)
endtime = datetime.datetime.now()
time_list_socket_s.append((endtime - starttime).microseconds)
time.sleep(3)
# ws1 = websocket.WebSocketApp(url_ws,
# on_message = on_message,
# on_error = on_error,
# on_close = on_close)
# times = 20
# ws1.on_open = on_open
# starttime = datetime.datetime.now()
# ws1.run_forever()



print("---------------------------------")
print("短链接时间:")
print(time_list_socket_s)
print(np.mean(time_list_socket_s))
print("---------------------------------")
print("长连接时间:")
print(time_list_socket_l)
print(np.mean(time_list_socket_l))
print("---------------------------------")
print("http时间:")
print(time_list_http)
print(np.mean(time_list_http))
print("times up")
# print(time_list_socket_l)
# print(time_list_socket_s)


#预计统计的时间,socket建立时间+请求(onOpen),socket通信中请求(send & respond),
# http请求时间
#

回溯算法练习

写的力扣的算法题目,一口气把所有组合总和的题做了,有一道还击败了99%的人,也可能是运气好吧。

39.组合总和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
Arrays.sort(candidates);
List<List<Integer>> results = new ArrayList<>();
List<Integer> tmp_res = new ArrayList<>();
back_track(candidates,target,results,tmp_res,0);
return results;
}
public void back_track(int[] candidates, int target, List<List<Integer>> results, List<Integer> tmp_res,int num){//num是索引
if(target < 0)return;
if(target == 0){
//results.add(tmp_res);//浅拷贝
results.add(new ArrayList(tmp_res));
return;
}
for(int i = num;i < candidates.length; i++){
tmp_res.add(candidates[i]);
back_track(candidates,target-candidates[i],results,tmp_res,i);
tmp_res.remove(tmp_res.size() - 1);//清零
}
}
}

40.组合总和II

这道题的重点在于如何去重。 一种方案是Set,但是由于Set是红黑树底层,其效率过低。 一种巧妙的方案是:
自愧不如,我去重的方法是。。。。。

return ans.stream().distinct().collect(Collectors.toList());

哭辽。按照大佬的思路,back_track里面正在循环的元素与上一个元素相等的时候,直接continue。效率和内存都大大提升。

哦,还有一个存留问题,

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
class Solution {
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
//int[] candidates = {2,5,2,1,2};
//target = 5;
List<List<Integer>> ans = new ArrayList<>();
List<Integer> tmp_ans = new ArrayList<>();
Arrays.sort(candidates);
System.out.println(candidates.length);
back_track(candidates,target,ans,tmp_ans,0);
return ans;//.stream().distinct().collect(Collectors.toList());
}
public void back_track(int[] candidates, int target, List<List<Integer>> ans, List<Integer> tmp_ans, int num){
if(target<0)return;
if(target == 0){
ans.add(new ArrayList(tmp_ans));
return;
}
for(int i=num;i < candidates.length; i++){
if(i>num&&candidates[i] == candidates[i-1])continue;
if(target<0)break;//根据都是正整数的条件加速
tmp_ans.add(candidates[i]);
back_track(candidates,target - candidates[i],ans,tmp_ans,i+1);
tmp_ans.remove(tmp_ans.size() - 1);
}
}
}

216 组合总数III

image.png

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public List<List<Integer>> combinationSum3(int k, int target) {
List<List<Integer>> ans = new ArrayList<>();
List<Integer> tmp_ans = new ArrayList<>();
int[] candidates = {1,2,3,4,5,6,7,8,9};
System.out.println(candidates.length);
back_track(candidates,target,ans,tmp_ans,k,0);
return ans;//.stream().distinct().collect(Collectors.toList());
}
public void back_track(int[] candidates, int target, List<List<Integer>> ans, List<Integer> tmp_ans, int flag,int num){
if(target<0)return;
if(target == 0 && flag ==0){
ans.add(new ArrayList(tmp_ans));
return;
}
for(int i=num;i < candidates.length; i++){
if(i>num&&candidates[i] == candidates[i-1])continue;
if(target<0||flag<0)break;//根据都是正整数的条件加速
tmp_ans.add(candidates[i]);
back_track(candidates,target - candidates[i],ans,tmp_ans,flag - 1,i+1);
tmp_ans.remove(tmp_ans.size() - 1);
}
}
}

作者:guo-guo-tm
链接:https://leetcode-cn.com/problems/combination-sum-iii/solution/zai-zu-he-zong-he-ii-de-ji-chu-shang-jia-liao-yi-g/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

  • Copyrights © 2015-2023 galaxy
  • Visitors: | Views:

请我喝杯咖啡吧~

支付宝
微信