Category: 不学无术

Categories
不学无术

操作系统中的虚拟内存

某次面试问到了这个问题，回答的不是很好，这两天仔细查了一下，先写下来。当初的问题很简单，就是“What is virtual memory in OS?”

为什么要有虚拟内存？

早期的操作系统是没有虚拟内存的概念的，在实模式（DOS下有的概念，相反的词叫“保护模式”）底下，完全没有什么分段分页或者虚拟地址的概念。这种情况下，内存的操作看起来很直白，程序中对内存的读写就是直接写实际的内存地址。这种直白的带来了很多问题，比如1）操作系统要想执行多进程就比较困难，进程的切换主要方法应该是把当前的进程写入硬盘，然后换个新的程序出来运行。因为所有程序都是直接操作内存，弄不好就崩了；2）如果程序比实际能分配的内存大，那就坑了，程序都载入不了了~
早期某些没有虚拟内存的实模式系统，内存分配的一种情况是这样
[[设备驱动][用户程序][操作系统]]
为了解决第一个问题，引入了内存抽象技术。即每个进程拥有自己的地址，引入了地址空间，操作系统分配给进程的其实是虚拟地址，这些虚拟地址在操作的时候会被转化为实际的物理地址，而这个过程对程序来说是透明的，如下图（来自《Memory management: What every driver writer needs to know》）。
Windows Virtual Memory Address
为了解决第二个问题，引入了虚拟内存技术。

程序的局部性原理

虚拟内存（Virtual Memory） 是指计算机呈现出要比实际拥有的内存大得多的内存量。因此它允许程序员编制并运行比实际系统拥有的内存大得多的程序。这使得许多大型项目也能够在具有有限内存资源的系统上实现。

虚拟内存的可用，个人认为很大程度上依赖于程序的局部性原理。局部性原理分为时间和空间上的局部性：

  1. 最近被访问的程序段在不久的将来还是很容易被访问到；
  2. 在内存中被访问的地址附近的数据在不久的将来也很容易被访问到；

也就是说，在某个特定的事件范围内，有很大比例的内存访问是集中于一小块内存范围内的，这个范围比程序声明要使用的总范围来的小（得多）。

虚拟内存技术

虚拟内存是现代操作系统普遍使用的一种技术。主要的思想很简单，拆东墙补西墙，即把感觉不怎么需要的内存块先写入磁盘，把内存中没有的但亟需使用的内存块调入内存。由于磁盘的容量比内存大很多（虽然磁盘访问的速度比内存慢很多），所以磁盘就成了放置“装不下”的内存块的大备胎。
对于一个程序来说，操作系统分配给他了可操作的地址，操作系统就像管家一样，负责管理内存、磁盘的具体调配（系统调用）。但是至于这段内存地址，实际在操作系统里是放在了内存还是磁盘还是其他什么地方里头，程序就不得而知了，大致就是下图这么个情况吧(来自维基百科)。
虚拟内存
当然这种虚拟内存是有代价的，毕竟磁盘的随机访问速度跟内存还差好几个数量级。因此系统要利用程序的局部性原理，尽量预测未来可能会频繁用到哪些内存，并把他们放入物理内存中。在Win32操作系统下，内存被按照页来分配，一个页是4KB大小。程序在执行的时候，当需要访问某个虚拟地址但是这个页面目前还在磁盘中存储的时候，系统就会产生缺页中断，缺页中断的结果是系统将自认为最近最没机会被访问的页从物理内存中换出（当然如果有空闲内存则没有这个操作），然后把现在急需的页从磁盘中调入。这里就牵扯到换页算法了，一个好的页面调度算法应当尽量减小页面换入换出的次数。
 
 

Categories
不学无术

LeetCode 331. Verify Preorder Serialization of a Binary Tree

如家网络实在太卡了，不过还好没有人劫@!$#@W…
稍微说一下思路把，这个问题就是判断某一层上的节点它的孩子会不会“溢出”，或者第一层的节点有没有完全闭合。我用一个栈来保存每一层的孩子数目（包括null）：

  • 当碰到数字的时候，压一层计数为0的栈，表示新开了一层并且这一层的孩子数为0
  • 当碰到#号时，说明多了一个空孩子，当前栈顶的计数+1，并且判断当前栈顶的计数是否>=2了，如果是的话，那说明这一层已经满了，那就退栈，然后再继续给新栈顶计数+1，继续判断是否满….如此往复

由于有了#表示空节点所以层级变得明确，举个例子：一个叶节点读入两个#，当前层的计数等于2后就退栈，并且给父亲层的计数器+1（表示下一层已经结束了，父亲多了一个左/右孩子）。
代码（好久没有纯手打一遍AC了）

class Solution {
public:
    bool isValidSerialization(string preorder) {
        int size = preorder.size();
        stack<int> working;
        int i = 0;
        while(i < size){
            int end = preorder.find(',', i);
            if(end == string::npos)
                end = size;
            if(preorder[i] != '#'){
                //number
                working.push(0);
            } else {
                //'#'
                if(i == 0){
                    //The null root?!
                    if(size > 1) return false;
                    else return true;
                }
                working.top() += 1;
                while(working.size()>1 && working.top() >= 2){
                    working.pop();
                    working.top() += 1;
                }
            }
            if(working.size() == 1 && working.top() > 2)
                return false;
            i = end+1;
        }
        return (working.size()==1) && (working.top()==2);
    }
};

BTW,苏州的交通状况和路面比杭州好多了。

Categories
不学无术

LeetCode 139. Word Break

题目

Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.
For example, given
s = "leetcode",
dict = ["leet", "code"].
Return true because "leetcode" can be segmented as "leet code".

思路1

写的第一个版本是超时的，但是思路应当是正确的，反正就是动态规划，但我用的是递归方法。
就是如果找到s[start,end]是单词表中的单词时，有两种处理，一种是算入然后往后走；另一种是忽略这次匹配成功，继续往后寻找。
代码大概这样：

class Solution {
public:
	int findNextWord(const string& s, int start, int curr, unordered_set<string>& wordDict) {
		//Find the end position of next possible word, or return -1
		string word = s.substr(start, curr - start + 1);
		for (int i = curr + 1; i < s.size(); i++) {
			word += s[i];
			if (wordDict.count(word) > 0) {
				return i;
			}
		}
		return -1;
	}
	bool parseSeq(const string& s, unordered_set<string>& wordDict, int start, int end, map<int, bool>& cache) {
		//Judge s[start...end]
		if (end >= s.size())
			return false;
		if (cache.count(start) > 1)
			return cache[start];
		string word = s.substr(start, end - start + 1);
		if (wordDict.count(word) > 0) {
			bool withThisWord = parseSeq(s, wordDict, end + 1, end + 1, cache);
			if (end + 1 == s.size() || withThisWord) {
				cache[start] = true;
				return true;
			}
		}
		int nextPos = findNextWord(s, start, end, wordDict);
		if (-1 != nextPos) {
			bool appendWord = parseSeq(s, wordDict, start, nextPos, cache);
			if (appendWord) {
				cache[start] = true;
				return true;
			}
		}
		cache[start] = false;
		return false;
	}
	bool wordBreak(string s, unordered_set<string>& wordDict) {
		map<int, bool> cache;
		return parseSeq(s, wordDict, 0, 0, cache);
	}
};

但是如果这里出现了超级多的单字，比如字符串是

aaaaaaaaaaaaaaaaaaaaaaa

然后字典是

{a,aa,aaa,aaaa}

这就搞笑了，得匹配死，所以肯定是超时。

思路2

这个是讨论组里看来的，突然发现一般来说DP递归能做的，就可以从后往前用非递归的方法写。对于这个问题来说，从后往前并不像做LCS那样时要完全倒着写。举个例子，有字符串str=thisisawesome 和字典{this, is, a, we, some, awesome} 的时候，可以用一个缓存cache来记录是否在str[i]位置有单词结束，比如str[3]位置就是”this”这个词结束的地方。当顺着继续搜索的时候，往前查找缓存记录，可以知道如果cache[i]=true的话，那才有可能从i这个位置往后到当前位置组成新单词，接着去查找字典看看有没有这个单词，如果没有的话，就得继续往前找到新的可用的开头i。这里加黑的“才有可能”是比较关键的。
代码大概是这样

bool wordBreak(string s, unordered_set<string>& wordDict) {
		if (wordDict.empty())
			return false;
		vector<bool> cache(s.size() + 1, false); //If a word ends at i, cache[i] = true
		cache[0] = true;
		for (int i = 0; i <= s.size(); i++) {
			for (int j = i - 1; j >= 0; j--) {
				if (cache[j]) {
					//Look backward and start at the end place of previous word
					string word = s.substr(j, i - j); // s[j...i-1]
					if (wordDict.find(word) != wordDict.end()) {
						cache[i] = true;
						break;
					}
				}
			}
		}
		return cache[s.size()];
	}

这里面向前迭代不断寻找cache[i]并尝试的情况，对应于之前思路1里面找到可用单词后的决定是否使用的分支情况。但是由于减少了一大堆递归调用，所以实际情况下的复杂度降低了不少。

Categories
不学无术

LeetCode 151. Reverse Words in a String

题目

Given an input string, reverse the string word by word.
For example,
Given s = “the sky is blue“,
return “blue is sky the“.
Update (2015-02-12):
For C programmers: Try to solve it in-place in O(1) space.

思路

一！定！要！考！虑！各！种！情！况！比如

" "//一个空格
"   What am   I doing     "

然后这种倒转问题的原地处理思路应该都明白的，先把整个字符串倒转一遍，然后按照单词再倒转回来，拿”the sky is blue”为例：

  1. “eulb si yks eht“
  2. “blue si yks eht”
  3. “blue is yks eht”
  4. …
  5. “blue is sky the”

代码

class Solution {
public:
	void reverseWordsSub(string &s, int start, int end) {
		//[start,end]
		char c;
		int count = 0;
		const int maxInd = (end - start - 1) / 2 + start;
		for (int i = start; i <= maxInd; i++) {
			c = s[i];
			s[i] = s[end - count];
			s[end - count] = c;
			count++;
		}
	}
	void clearStr(string &s) {
		//Clear unnecessary spaces
		int validIndex = -1;
		bool spaceFlag = false;
		for (int i = 0; i<s.size(); i++) {
			if (s[i] != ' ') {
				s[++validIndex] = s[i];
				spaceFlag = false;
			}
			else if (!spaceFlag) {
				if (validIndex < 0) {
					continue;
				}
				spaceFlag = true;
				s[++validIndex] = s[i];
			}
		}
		if (spaceFlag)
			validIndex--;
		if (validIndex < 0)
			s = "";
		else
			s = s.substr(0, validIndex + 1);
	}
	void reverseWords(string &s) {
		clearStr(s);
		int strSz = s.size();
		reverseWordsSub(s, 0, strSz - 1);
		int start = 0;
		for (int i = 0; i<strSz; i++) {
			if (s[i] == ' ') {
				reverseWordsSub(s, start, i - 1);
				start = i + 1;
			}
		}
		reverseWordsSub(s, start, strSz - 1);
	}
};

 

Categories
不学无术

LeetCode 9. Palindrome Number

题目

Determine whether an integer is a palindrome. Do this without extra space.

Some hints:Could negative integers be palindromes? (ie, -1)
If you are thinking of converting the integer to string, note the restriction of using extra space.
You could also try reversing an integer. However, if you have solved the problem “Reverse Integer”, you know that the reversed integer might overflow. How would you handle such case?
There is a more generic way of solving this problem.

思路

首先要注意，负数不是回文数。
然后题目中要求不能使用额外的空间，我的理解是O(1)空间复杂度，即不能用字符串来存储?

代码

我这个解决方案不知道是不是违规了，如果再苛刻一点，那就是每次测试当前数字的位数（连续除10），然后用除法和模10判断首位和末尾的数字。

class Solution {
public:
    bool isPalindrome(int x) {
        if(x < 0)
            return false;
        int cover = 1;
        int x_copy = x;
        while(x_copy/10 > 0){
            x_copy /= 10;
            cover *= 10;
        }
        while(cover >= 10){
            int front = x/cover;
            int end = x%10;
            if(front != end){
                return false;
            }
            x -= front * cover;
            x /= 10;
            cover /= 100;
        }
        return true;
    }
};

 

Categories
不学无术

LeetCode 8. String to Integer (atoi)

题目

Implement atoi to convert a string to an integer.
Hint: Carefully consider all possible input cases. If you want a challenge, please do not see below and ask yourself what are the possible input cases.
Notes: It is intended for this problem to be specified vaguely (ie, no given input specs). You are responsible to gather all the input requirements up front.
Update (2015-02-10):
The signature of the C++ function had been updated. If you still see your function signature accepts a const char * argument, please click the reload button to reset your code definition.

思路

这道题没什么思路，但是要主要一定要在溢出之前解决溢出！不同的编译器对溢出的处理方法不一样的，所以得到的溢出结果也是不同的，比如int的正整数溢出就是负整数什么的就肯定不对。我的想法是用unsigned int把可能溢出的情况兜住判断，可能溢出的情况无非两个，乘以10的时候，加一个个位数的时候。

代码

class Solution {
public:
    bool willOverflow(unsigned int currNum, char i, bool negFlag){
        const unsigned int M_INTM = INT_MAX / 10;
        if(currNum > M_INTM){
            return true;
        } else if(currNum == M_INTM){
            if(!negFlag){
                if(i - '0' > 7) {
                    return true;
                }
            } else{
                if(i - '0' > 8){
                    return true;
                }
            }
        }
        return false;
    }
    int myAtoi(string str) {
        unsigned int retVal = 0;
        bool negFlag = false;
        bool overflow = false;
        if(str.size() < 1)
            return 0;
        int i=0;
        while(str[i] == ' '){
            i++;
        }
        if(str[i] == '+')
            i++;
        else if(str[i] == '-'){
            i++;
            negFlag = true;
        }
        int digCount = 0;
        while(i < str.size() && str[i] >= '0' && str[i] <= '9'){
            if(digCount < 9 || !willOverflow(retVal, str[i], negFlag)){
                retVal = retVal * 10 + str[i] - '0';
            } else {
                //overflow!
                overflow = true;
                break;
            }
            i++;
            digCount++;
        }
        if(!overflow){
            if(negFlag)
                return -retVal;
            else
                return retVal;
        } else {
            return negFlag? INT_MIN: INT_MAX;
        }
    }
};

 

Categories
不学无术

LeetCode 236. Lowest Common Ancestor of a Binary Tree

题目

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.
According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

        _______3______
       /              \
    ___5__          ___1__
   /      \        /      \
   6      _2       0       8
         /  \
         7   4

For example, the lowest common ancestor (LCA) of nodes 5 and 1 is 3. Another example is LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

思路1

找两个节点的公共最小祖先，可以利用递归的思想，即假设我们有个函数，能判断root为根节点的子树里有几个符合的节点（0，1或2个），在递归跳出的过程中，一旦我们发现有返回2个节点的，那这个根元素就肯定是p和q的最低公共节点了。

思路2

假设要找的节点是5和1，那么从根节点通往5的路径是3->5，通往1的路径是3->1。可以用递归方法构造一个路径栈，比较容易地找到路径，然后就变成两条路径的最长公共节点的问题了，“分岔”的地方就是LCA.
相比思路1，这个方法实施起来简单一些，但是要遍历两遍树，会稍微慢一点。

代码1

* struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int LCASub(TreeNode* root, TreeNode* p, TreeNode* q, TreeNode*& retNode){
        //If we find p or q, return 1
        //If we find root contains p and q, return 2 and set the retNode to common node
        //Else return 0
        if(root == NULL)
            return 0;
        int leftRet = LCASub(root->left, p, q, retNode);
        if(leftRet == 2)
            return 2;
        int rightRet = LCASub(root->right, p, q, retNode);
        if(rightRet == 2){
            return 2;
        }
        if(leftRet + rightRet == 2){
            retNode = root;
            return 2;
        } else if(root == p || root == q){
            if(leftRet==1 || rightRet == 1){
                retNode = root;
                return 2;
            } else {
                return 1;
            }
        } else {
            return leftRet + rightRet;
        }
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        TreeNode* retVal = NULL;
        LCASub(root, p, q, retVal);
        return retVal;
    }
};

代码2

class Solution {
public:
    bool getPath(TreeNode* root, TreeNode* p, stack<TreeNode*>& path){
        //Get path from root to p
        //If not available, return false
        if(root == NULL || root == p){
            path.push(root);
            return true;
        }
        bool foundPath = false;
        if(root->left != NULL){
            //try left
            foundPath = getPath(root->left, p, path);
            if(foundPath){
                //Mission complete, push current node and return
                path.push(root);
                return true;
            }
        }
        if(root->right != NULL){
            foundPath = getPath(root->right, p, path);
            if(foundPath){
                path.push(root);
                return true;
            }
        }
        return false;
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        stack<TreeNode*> pPath;
        stack<TreeNode*> qPath;
        getPath(root, p, pPath);
        getPath(root, q, qPath);
        TreeNode* result = NULL;
        while(!pPath.empty() && !qPath.empty()){
            if(pPath.top() != qPath.top())
                break;
            result = pPath.top();
            pPath.pop();
            qPath.pop();
        }
        return result;
    }
};

 

Categories
不学无术

C++11里头的thread初探

C++11标准给了很多“终于等到了”的功能，其中一项就是线程类<thread> ，有朝一日终于可以减少操作系统相关了，隔壁J家笑而不语。
 
用法真是简单多了，最简单的一种如下：

#include <thread>
#include <iostream>
using namespace std;
void pause_thread(int n) {
	this_thread::sleep_for(chrono::seconds(2));
	cout << "thread of " << n << " ended\n";
}
int main() {
	int N = 0;
	cin >> N;
	thread* ths = new thread[N];
	for (int i = 0; i < N; i++) {
		ths[i] = thread(pause_thread, i);
	}
	cout << "Finished spawning threads." << endl;
	for (int i = 0; i < N; i++) {
		ths[i].join();
	}
	cout << "All threads joined!" << endl;
	delete[]ths;
	return 0;
}

上面程序的输出：
cpp11_thread
当然由于我的函数里定义的不是原子操作，所以cout的时候就混杂了~
所以可以用到<mutex> 类里面的互斥量来解决一下，比如这样

#include <thread>
#include <mutex>
#include <iostream>
using namespace std;
void pause_thread(int n, mutex* mtx) {
	this_thread::sleep_for(chrono::seconds(2));
	(*mtx).lock();
	cout << "thread of " << n << " ended\n";
	(*mtx).unlock();
}
int main() {
	int N = 0;
	cin >> N;
	thread* ths = new thread[N];
	mutex mtx;
	for (int i = 0; i < N; i++) {
		ths[i] = thread(pause_thread, i, &mtx);
	}
	cout << "Finished spawning threads." << endl;
	for (int i = 0; i < N; i++) {
		ths[i].join();
	}
	cout << "All threads joined!" << endl;
	delete[]ths;
	return 0;
}

然后我们可以看到，输出不会绕在一起了~当然还是无序的，哈哈
cpp11_mutex
 
查文档的时候注意到，竟然还有死锁检测相关的exception可能会抛出，有点良心的…这几天好好研究一下~
 

Categories
不学无术

LeetCode 319. Bulb Switcher 智商碾压题

There are n bulbs that are initially off. You first turn on all the bulbs. Then, you turn off every second bulb. On the third round, you toggle every third bulb (turning on if it’s off or turning off if it’s on). For the ith round, you toggle every i bulb. For the nth round, you only toggle the last bulb. Find how many bulbs are on after n rounds.
Example:

Given n = 3.
At first, the three bulbs are [off, off, off].
After first round, the three bulbs are [on, on, on].
After second round, the three bulbs are [on, off, on].
After third round, the three bulbs are [on, off, off].
So you should return 1, because there is only one bulb is on.

我的超时解

递推法，当从n-1到n时，新加上去的一次操作是判断从[1,n]里面n的因子个数，这里记作f(n)好了，即a[n] = a[n-1] + f(n)
因子个数的求法可以精简一下时间，排除0,1,2这三个特殊值后，计算[2, sqrt(n)]里头能整除的数的个数就行了，如果碰到个平方数那个数+1，不然个数就是+2的（i能被n整除，那么它的补数n/i也行）。
这个方法的复杂度嘛，O(n^1.5)吧

class Solution {
public:
    int factors(int n){
        if(n == 0){
            return 0;
        } else if(n == 1){
            return 1;
        } else if(n == 2){
            return 2;
        }
        int count = 2;  //1和自己
        int sqr = (int)(sqrt(n));
        for(int i=2; i <= sqr; i++){
            if(n % i == 0){
                if(i *i == n)
                    count += 1; //平方数
                else
                    count += 2; //一个数和它的补数
            }
        }
        return count;
    }
    int bulbSwitch(int n) {
        if(n < 1){
            return 0;
        }
        int bCount = 0;
        for(int i=1; i<=n; i++){
            if((factors(i)&1) == 1){
                bCount ++;
            }
        }
        return bCount;
    }
};

智商碾压，O(1)解

真正的奥义用一行代码就能解释

class Solution {
public:
    int bulbSwitch(int n) {
        return sqrt(n);
    }
};

呵呵哒！这个规律如果多试几次说不定能发现，0,1,1,1,2,2,2,2,2,3这种数列嘛
https://leetcode.com/discuss/91371/share-my-o-1-solution-with-explanation
大概意思是，要在[1,n]里头找哪些灯泡被执行了奇数次操作

  •  对于一个非平方数来说（比如12），因为有成对的补数（1vs12; 2vs6），所以总是会按下2的倍数次
  • 但是对于一个平方数来说（比如36），因为其中有个数(6)它的补数是自己，所以会按被下奇数次

然后这道题就变成了找[1,n]中间有几个平方数了
OMG…

Categories
不学无术

LeetCode 322. Coin Change

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.
Example 1:
coins = [1, 2, 5], amount = 11
return 3 (11 = 5 + 5 + 1)
Example 2:
coins = [2], amount = 3
return -1.
Note:
You may assume that you have an infinite number of each kind of coin.

思路

动态规划的问题，不过如果倒着做的话，似乎会超时…
所以考虑往前递推的情况，即当前要解决X元的找零问题的最佳解法且已知<X时的解法，手头有一堆面值为coins[i]的硬币的时候，对于每种可用的硬币我们要做的选择是：

  • 尝试使用coin[i]，即当前的最优结果=(X-coins[i])元时的最优结果+1，这个1就是用了coins[i]这个硬币；
  • 保持现有结果不变

这两个方法当然是取最好的存下来了。

代码

class Solution {
public:
    int MAX_NUM = 65535;
    int coinChange(vector<int>& coins, int amount) {
        vector<int> solutions(amount+1, MAX_NUM); //0~amount，共amount+1个
        solutions[0] = 0;
        int coinSz = coins.size();
        for(int i=1; i<=amount; i++){
            for(int c=0; c<coinSz; c++){
                //得到当前的amount，要么就是用原有的结果，要么就是使用amount[i-coin] + 1个当前面值的
                if(coins[c] <= i){
                    solutions[i] = min(solutions[i], 1 + solutions[i-coins[c]]);
                }
            }
        }
        if(solutions[amount] == MAX_NUM)
            return -1;
        return solutions[amount];
    }
};