可乐的博客
0%

发表于 更新于
本文字数： 868 阅读时长 ≈ 1 分钟

6. ZigZag Conversion

把字符转换成一定高度的Z字型，z字形转换，主要是找规律

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

找规律吧，骚年

首先第一列的数字(1,2,3,4,5)是递增的，我们直接遍历就可以了。很容易计算出一个循环是一个竖行加一个斜行，数字的个数是2n-2。列与列之间相隔的数字是2n-2（n代表行数),上面隔8。对于其余的数字我们找其他的规律，看3和7吧 201862-2018-06-02-19-59-09
3和7和下面的组成一个三角形，我利用这个三角形找规律:
总的行数为n，我遍历的时候，当前行号为i,那么三角形的高就是n-i,三角形的两条边就差一，所以我们很容易计算7=3+(5-3)2 ===> secondj=j+(numrows-i)2

阅读全文 »

发表于 更新于
本文字数： 1.2k 阅读时长 ≈ 1 分钟

给出一个数组，给定一个数字，查找需要插入的位置，数组已排好序，瞬间想到二分搜索，然后判断位置就可以了，判断位置判断的有点失败.....

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:
    int searchInsert(vector<int>& nums, int target) {
        int left=0,right=nums.size(),middle=0;
        int flag=0;
        while(left<=right)
        {
            middle=(left+right)/2;
            if(nums[middle]==target)
                {flag=1;break;}
            if(nums[middle]>target) right=middle-1;
            else left=middle+1;
        }
        //return middle;
        if(flag==1) return middle;
        else
        {
            if(nums[middle]<target) return middle+1>nums.size()?nums.size():middle+1;
            else if(nums[middle]>target) return middle;
        }
    }
};

修改版 

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:
    int searchInsert(vector<int>& nums, int target) {
        int left=0,right=nums.size()-1,middle=0;
        int flag=0;
        while(left<right)
        {
            middle=(left+right)/2;
            if(nums[middle]==target)
                return middle;
            if(nums[middle]>target) right=middle-1;
            else left=middle+1;
        }
        //return middle;
        /*
        if(flag==1) return middle;
        else
        {
            if(nums[middle]<target) return middle+1>nums.size()?nums.size():middle+1;
            else if(nums[middle]>target) return middle;
        }*/
        if(nums[left]==target||nums[left]>target) return left;
        else
            return left+1;
    }
};
运行时间多了2ms,但玄学的问题无法解决的....

发表于 更新于
本文字数： 1.1k 阅读时长 ≈ 1 分钟

给jekyll 添加 mathjax

准备刷leetcode，算法题目自然少不了复杂度，\(N^{2}\)之类数学公式的数字，因此需要添加mathjax来显示数学公式，试了不少的坑，记录一下下:

首先是一个dollar符不显示公式，这是因为mathjax考虑到 $ 比较常用，因为外国人的货币都是用 $ 来表示的嘛，所以默认关闭了使用$..$表示公式的方法，而是采用 $$....$$,但是可以手动修改:

1
2
3
4
5
6
7
8
    <!-- mathjax-->
    <script type="text/x-mathjax-config">
        MathJax.Hub.Config({tex2jax: {inlineMath: [ ['$','$'] ],
        displayMath: [ ['$$','$$'] ],
        processEscapes: true,}});
    </script> -->
<script src="http://or4d8nhvk.bkt.clouddn.com/MathJax.js?config=TeX-AMS-MML_HTMLorMML" type="text/javascript"></script>

手动配置displaymath和inlinemath,然后把processescapes转义打开

阅读全文 »

发表于 更新于
本文字数： 2.3k 阅读时长 ≈ 2 分钟

leetcode 9 Palindrome Number

方法一

判断一个数字是否是回文数字，我先转换成字符串，然后从中心向两头比较，好久没写了，有点蛋疼。。。。。 

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
class Solution {
public:
    bool isPalindrome(int x) {
        string number=to_string(x);
        int length=number.length();
        int center=length/2;
        if(length%2)
        {
            for(int i=1;i<=center;i++)
            {
                if(number[center-i]!=number[center+i])
                    return false;
            }
        }
        else
        {
            for(int i=1;i<=center;i++)
            {
                if(number[center-i]!=number[center+i-1])
                    return false;
            }
        }
        return true;
    }
};
```  


看到另一种做法先判断特殊情况，例如x小于0,那么x一定不是回文数字，假如x不等于0，并且x%10==0,那么x的结尾一定有0，开头不能有0,因此x也不是回文数字。对于一般情况，我们把x的后半部分数字提取出来，判断时候相等就可以了，但有时候数字的长度是奇数，所以我们有时候需要判断一下

class Solution { public: bool isPalindrome(int x) { if(x<0||(x!=0&&x%10==0)) return false; int sum=0; while(x>sum) { sum+=sum*10+x%10; x/=10; } return (x==sum)||(x==sum/10); } }; 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19


上面的运行时间在290ms，研究了下提交中运行时间最短的代码
。。。。。。
// 这种全局执行函数，纯粹是为了刷排名
static const auto _______ = []() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    return nullptr;
}();

发现这个东东，主要是关闭cin的缓冲，解除cin和stdio的绑定，提高运行时间的，其实运行的算法没有啥区别，不做研究了2333


## 方法二:manacher算法
方法二主要是在方法一的基础上进行了相关的改进:    
1. 在每个字符的前面和后面都插入`#`字符，在字符串的开头和结尾分别添加一个`^`和`$`表示开头和结尾  
2. 记录下回文串的长度，感觉像是动态规划的算法

class Solution { public: string preprocess(string a) { int n=a.length();//string的赋值一定要用双引号，不然出现一些奇怪的问题，稍后总结 if(n==0) return "^\("; string ret="^"; for(int i=0;i<n;i++) { ret+="#"+a.substr(i,1);//直接取下标不成功，只能使用substr } ret+="#\)"; return ret; }

string longestPalindrome(string s) {
    string T=preprocess(s);
    int n=T.length();
    int *p=new int [n];//用于记录当前点出回文串的长度
    if(n==0) return "";
    int c=0,r=0;//c用来记录当前最长子回文串的长度，r记录当前最长子回文串的右端点
    int i_mirror;
    for(int i=1;i<n-1;i++)
    {
        i_mirror=2*c-i;//找到i关于当前最长子回文串中心c的对称点
        p[i]=r>i?min(p[i_mirror],r-i):0;//如果当前要计算的点在最长子回文串内，那么我们看他的对称点出的子回文串长度，要计算点出的回文串至少是min(p[i_mirro],r-i)，要防止超过最长子回文串的右端点;否则就是在最长子回文串外，需要赋值为0,一位一位的扩展(从中心向两头扩展)
        
        
        while(T[i+1+p[i]]==T[i-1-p[i]])//从中心向两端扩展
            p[i]++;
        
        if(i+p[i]>r)//更新最大子回文串的中心和长度
        {
            c=i;
            r=i+p[i];
        }
    }
    int maxlen=0,center=0;//遍历整个数组，找出最大的子回文串,其实下面的循环可以放到上面里去
    for(int i=1;i<n-1;i++)
    {
        if(p[i]>maxlen)
        {
            center=i;
            maxlen=p[i];
        }
    }
    return s.substr((center-maxlen-1)/2,maxlen);//因为添加了许多'#'，所以位置需要做一些改变
}

}; ```

阅读全文 »

发表于 更新于
本文字数： 4.2k 阅读时长 ≈ 4 分钟

mit operating system Lab 1

https://www.cnblogs.com/orlion/p/5765339.html ## part I：PC Bootstrap 第一部分主要是简单的了解实验环境、汇编语言、内存的的固定位置等基本知识，同时运行试验环境，需要注意的是mit的实验只能在32位系统上运行，尽管qemu-i368模拟的是32位机，但是你就是要用32位系统进行运行，否则就会卡住。。。
重要的话说三遍(mit lab 1 卡住):
** 必须用32位系统运行 **
** 必须用32位系统运行 ** ** 必须用32位系统运行 **

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

+------------------+  <- 0xFFFFFFFF (4GB)
|      32-bit      |
|  memory mapped   |
|     devices      |
|                  |
/\/\/\/\/\/\/\/\/\/\

/\/\/\/\/\/\/\/\/\/\
|                  |
|      Unused      |
|                  |
+------------------+  <- depends on amount of RAM
|                  |
|                  |
| Extended Memory  |
|                  |
|                  |
+------------------+  <- 0x00100000 (1MB)
|     BIOS ROM     |
+------------------+  <- 0x000F0000 (960KB)
|  16-bit devices, |
|  expansion ROMs  |
+------------------+  <- 0x000C0000 (768KB)
|   VGA Display    |
+------------------+  <- 0x000A0000 (640KB)
|                  |
|    Low Memory    |
|                  |
+------------------+  <- 0x00000000

Exercise 2: 单步运行

1
2
3
The target architecture is assumed to be i8086
[f000:fff0]    0xffff0:	ljmp   $0xf000,$0xe05b 
0x0000fff0 in ?? ()
阅读全文 »

发表于 更新于
本文字数： 326 阅读时长 ≈ 1 分钟

leetcode 5 Longest Palindromic Substring

求最大的子回文字符串
参考资料:
https://articles.leetcode.com/longest-palindromic-substring-part-i/
http://www.leetcode.com/2011/11/longest-palindromic-substring-part-ii.html

一种 \(N^{2}\) 复杂度的算法是，枚举每个字符，然后从这个字符向两边扩展，直到两边不相等为止，这样就找到了一个子回文串了，因此寻找子回文串的最坏情况是 $ O(n)\(,我们的外循环中需要遍历一遍中心，复杂度又是\)O(n)\(,所以总的复杂度是\)O(n^{2})$

发表于 更新于
本文字数： 9.1k 阅读时长 ≈ 8 分钟

solveme writeup

题目地址:http://solveme.peng.kr/

Warm up

http://warmup.solveme.peng.kr/

1
2
3
4
5
6
7
    error_reporting(0);
    require __DIR__.'/lib.php';

    echo base64_encode(hex2bin(strrev(bin2hex($flag)))), '<hr>';

    highlight_file(__FILE__);
1wMDEyY2U2YTY0M2NgMTEyZDQyMjAzNWczYjZgMWI4NTt3YWxmY=
阅读全文 »

发表于 更新于
本文字数： 938 阅读时长 ≈ 1 分钟

XSS Challenges solution

题目地址:http://xss-quiz.int21h.jp

challenge 1

输出在搜索结果里面，有引号包围，所以先闭合双引号，然后为所欲为就可以了
payload: "<svg onload=alert(document.domain)>

challenge 2

阅读全文 »

发表于 更新于
本文字数： 3.6k 阅读时长 ≈ 3 分钟

easyctf 总结学习

比赛题目全关闭了。。。。只能根据印象来了
大佬的总结+题目介绍

Discord

网站上有个在线聊天工具，加入进去，里面有个类似于qq的群公告，就是FLAG

intro:Hello,world!

阅读全文 »

发表于 更新于
本文字数： 3.3k 阅读时长 ≈ 3 分钟

使用数组方法进行xss 攻击

原文地址

1
2
3
4
5
6
7
8
JS Execution 
Array Methods

[1].map(alert)
[1].find(alert)
[1].every(alert)
[1].filter(alert)
[1].findIndex(alert)

主要是不适用alert(),感觉有点蛋疼，因为一般waf都是过滤alert，所以我还是试了一下

作者给了一个简单的测试页面 http://brutelogic.com.br/xss.php

阅读全文 »