若干数据结构 && 算法面试题【二】 （更新完毕）

class Solution 
{
public:
	int jumpFloor(int number) 
	{
		if (number <= 1)
		{
			return number;
		}
		int first = 1;
		int second = 1;
		while (--number)
		{
			int tmp = second;
			second += first;
			first = tmp;
		}
		return second;
	}
};

int  NumberOf1(int n)
	{
		int cur = 0x00000001;
		int count = 0;
		for (int i = 0; i < 32; i++)
		{
			if ( (n & cur) != 0)
			{
				count++;
			}
			cur = cur << 1;
		}
		return count;
	}

	//最优解
	int NumberOf1Best(int n)
	{
		int count = 0;
		while (n != 0)
		{
			++count;
			n = (n - 1) & n;
		}
		return count;
	}

ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
	{
		if (pHead1 == NULL && pHead2 == NULL)
		{
			return NULL;
		}
		if (pHead1 == NULL)
		{
			return pHead2;
		}
		if (pHead2 == NULL)
		{
			return pHead1;
		}
		ListNode *cur1 = pHead1;
		ListNode *cur2 = pHead2;
		ListNode *NewNode = NULL;
		if (cur1->val <= cur2->val)
		{
			NewNode = cur1;
			cur1 = cur1->next;
		}
		else
		{
			NewNode = cur2;
			cur2 = cur2->next;
		}
		ListNode *NewHead = NewNode;
		while (cur1 != NULL && cur2 != NULL)
		{
			if (cur1->val <= cur2->val)
			{
				NewNode->next = cur1;
				NewNode = NewNode->next;
				cur1 = cur1->next;
			}
			else
			{
				NewNode->next = cur2;
				NewNode = NewNode->next;
				cur2 = cur2->next;
			}
		}
		if (cur1 != NULL)
		{
			NewNode->next = cur1;
		}
		else if (cur2 != NULL)
		{
			NewNode->next = cur2;
		}
		return NewHead;
	}

void Mirror(TreeNode *pRoot) 
 {
  if (pRoot == NULL)
  {
   return;
  }
  _Mirror(pRoot);
 }
protected:
 void _Mirror(TreeNode* pRoot)
 {
  if (pRoot == NULL)
  {
   return;
  }
  if (pRoot->left == NULL && pRoot->right == NULL)
  {
   return;
  }
  swap(pRoot->left, pRoot->right);
  _Mirror(pRoot->left);
  _Mirror(pRoot->right);
 }

vector<int> printMatrix(vector<vector<int> > matrix) 
 {
  int max_line = matrix.size();
  int max_col = matrix[0].size();
  int size = max_line * max_col;
  int count = 0;
  int min_line = 0;
  int min_col = 0;
  int cur_line = 0;
  int cur_col = 0;
  vector<int> ret;
  while (count < size)
  {
   //横，从左向右
   for (cur_col; cur_col < max_col; ++cur_col)
   {
    ret.push_back(matrix[cur_line][cur_col]);
    count++;
   }
   cur_col = max_col - 1;
   cur_line = min_line + 1;
   min_line++;
   //纵，从上到下
   for (cur_line; cur_line < max_line; cur_line++)
   {
    ret.push_back(matrix[cur_line][cur_col]);
    count++;
   }
   if (count >= size)  //这里需要判断一下
   {
    return ret;
   }
   cur_col = max_col - 2;
   cur_line = max_line - 1;
   max_col--;
   //横，从右到左
   for (cur_col; cur_col >= min_col; cur_col--)
   {
    ret.push_back(matrix[cur_line][cur_col]);
    count++;
   }
   cur_col = min_col;
   cur_line = max_line - 2;
   max_line--;
   //纵，从下到上
   for (cur_line; cur_line >= min_line; cur_line--)
   {
    ret.push_back(matrix[cur_line][cur_col]);
    count++;
   }
   cur_col = min_col + 1;
   cur_line = min_line;
   min_col++;
  }
  return ret;
 }

class Solution
{
public:
 void push(int value)
 {
  _Data.push(value);
  if (_MinData.empty() || value < _MinData.top())
  {
   _MinData.push(value);
  }
 }
 void pop() 
 {
  if (_Data.top() == _MinData.top())
  {
   _MinData.pop();
  }
  _Data.pop();
 }
 int top() 
 {
  return _Data.top();
 }
 int min() 
 {
  return _MinData.top();
 }
protected:
 stack<int> _Data;
 stack<int> _MinData; 
};

vector<int> PrintFromTopToBottom(TreeNode *root)
 {
  vector<int> ret;
  if (root == NULL)
  {
   return ret;
  }
  if (root->left == NULL && root->right == NULL)
  {
   cout << root->val << endl;
   ret.push_back(root->val);
   return ret;
  }
  vector<TreeNode*> box;
  TreeNode *cur = root;
  TreeNode *prev = cur;
  
  while (ret.empty() || !box.empty())
  {
   if (!box.empty())
   {
    cur = box.front();
    box.erase(box.begin());
   }
   cout << cur->val << " ";
   ret.push_back(cur->val);
   if (cur->left)
   {
    //cout << cur->left->val << " ";
    box.push_back(cur->left);
   }
   if (cur->right)
   {
    //cout << cur->right->val << " ";
    box.push_back(cur->right);
   }
  }
  return ret;
 }

RandomListNode* Clone(RandomListNode* pHead)
 {
  if (pHead == NULL)
  {
   return NULL;
  }
  RandomListNode *cur = pHead;
  while (cur)
  {
   RandomListNode *tmp = cur->next;
   RandomListNode *NewNode = new RandomListNode(cur->label);
   cur->next = NewNode;
   NewNode->next = tmp;
   cur = tmp;
  }
  cur = pHead;
  while (cur)
  {
   RandomListNode *pos = cur->next;
   if (cur->random)
   {
    pos->random = (cur->random)->next;
   }
   cur = pos->next;
  }
  cur = pHead;
  RandomListNode *cur1 = cur->next;
  RandomListNode *NewHead = cur1;
  while (cur->next->next != NULL)
  {
   cur->next = cur->next->next;
   cur = cur->next;
   cur1->next = cur1->next->next;
   cur1 = cur1->next;
  }
  return NewHead;
 }

int MoreThanHalfNum_Solution(vector<int> numbers) 
	{
		if (numbers.empty())
		{
			return 0;
		}
		int sz = numbers.size();
		vector<int> HashList;
		HashList.resize(numbers[0] + 1);
		for (int i = 0; i < sz; ++i)
		{
			if (numbers[i] + 1 > HashList.size())
			{
				HashList.resize(numbers[i] + 1);
			}
			++HashList[numbers[i]];
			if (HashList[numbers[i]] > sz / 2)
			{
				return numbers[i];
			}
		}
		return 0;
	}

vector<int> GetLeastNumbers_Solution(vector<int> input, int k) 
	{
		vector<int> HashList;
		vector<int> Ret;
		if (k > input.size())
		{
			return Ret;
		}
		for (size_t i = 0; i < input.size(); ++i)
		{
			if (HashList.size() < input[i] + 1)
			{
				HashList.resize(input[i] + 1);
			}
			++HashList[input[i]];
		}
		for (size_t i = 0; i < HashList.size(); ++i)
		{
			while (HashList[i]--)
			{
				Ret.push_back(i);
				k--;
				if (k == 0)
				{
					return Ret;
				}
			}
		}
		return Ret;
	}