Protected: 2014

This content is password protected. To view it please enter your password below:

blogs

技术:

  1. http://www.qyjohn.net/
  2. http://www.valleytalk.org/
  3. http://www.cloud-sec.org/

 安全:

病毒&逆向技术:

  1. http://www.securelist.com/en/analysis
  2. http://www.cyberesi.com/category/malware/
  3. http://www.accessroot.com/arteam/site/download.php?list.10
  4. http://www.utdallas.edu/~zhiqiang.lin/spring2012.html
  5. https://code.google.com/p/volatility/downloads/list
  6. http://sourcecodebrowser.com./

安全技术:

  1. http://www.secdocs.org/
  2. http://www.vupen.com/blog/
  3. http://cybersword.net/attack/exploit/558.html

一道逻辑题

题目如下:有一堆小球,8个,外观完全一样,其中有一个重量跟其他的不同,重量略轻。给一天平。问:最少几次可以把不同的球称出来。

答案是两次。

题目可以进一步引申,假设时n个球,n>2。问最少一次。又或假设,只知道其中一个球跟其他不同,却不知道起是轻是重,需要几次?4cd6a8bdff913eb194f212b55d93ac7d

求最长不含相同字符的连续子串

原题来源于陈利人老师的微信待字闺中:由26 个小写字母组成的字符串str,在str 中查找最长不含相同字符的连续子串。如 abcacfrar,为acfr。

解题思路:查找最长不重复,原题并没有说找到第一个最长结果后怎么做(最长结果是26)。所以并不一定要遍历字符串。亦可找到最长字符串(最长不含相同字符的连续子串,在不引起歧义的情况下后面都用最长字符串表示)即结束查找。我们暂且不去考虑这种情况。现在开始,我们从第一个字符开始读,则这个字符会变成当前最长字符串。则当前我们有如下变量:

  1. 当前最长字符串。
  2. 当前读到的位置。
  3. 当前最长字符串开始的位置。

继续往下读,假设读到第n个字符,开始出现重复字符。我们分析下应该如何处理:首先,当前最长字符串是第一个字符到当前都到的字符前面的字符。这个很容易看出来,问题是接下来怎么做,这个很关键。如何设置当前最长字符串的开始问题将直接决定算法的正确性。基于条件,我们知道,最长字符串中任意一个字符只能有一个,而上一次出现的该字符起所在的最长字符串已经得出,所以,很容易知道,正确的做法是从当前字符上一次出现的位置的下一个位置起继续算最长字符串。到现在位置,问题已经清晰了,理论上讲应该能求出这个最长字符串了。接下来要考虑的就是效率了。最快的方法肯定是辅助hash,用该hash记载当前字符上一次出现的位置。到此,问题解决。回头上代码。

#include <iostream>
#include <string>
#include <map>

using namespace std;

int main(){
    map<char, int> hash;
    for(int i=(int)'a';i<=(int)'z'; i++){
        char a = (char)i;
        hash[a] = -1;
    }
    string str = "sdfsfvdsfsadfsadfasjfqazwsxedcrfvtgbyhnujmikolpkasdfjkasldfjktgbyhnujmikolpoiuytrewqasdfghjlmnb";
    int current_start = 0;
    int current_longest = 0;
    int longest = 0;
    int longest_start = 0;
    int current_location = 0;
    for(;current_location<str.size();current_location++){
        char c = str.at(current_location);
        if(current_location>hash[c]){
            current_longest = current_location - current_start;
            if(current_longest>longest){
                longest = current_longest;
                longest_start = current_start;
            }
            if(hash[c]>current_start){
                current_start=hash[c]+1;
            }
            hash[c]=current_location;
        }
    }
    cout << longest_start<<endl;
    cout << longest<<endl;
    cout << "Longest string:" <<str.substr(longest_start, longest)<<endl;
}