笔试练习(一)

1.二维数组中的查找

• 思路：根据矩阵特点，左下角和右上角对应的值对应两个方向上递增或者递减
• 问题1：编码中ncol中没有添加下标
• 问题2：比较时i和j搞混了
• 问题3：二维数组初始化问题

ac代码

#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
	bool Find(vector<vector<int> > array,int target)
	{
		int nrow = array.size();        
		int ncol = array[0].size();        

		int i = ncol-1;
		int j = 0;

		for(i,j; i>=0 && j<=(nrow-1);)
		{
			if(array[j][i] == target) return true;
			else if(array[j][i] > target) i--;
			else if(array[j][i] < target) j++;
		}
		return false;
	}
};

2.替换空格

• 问题1：t未初始化
• 问题2：for中停止条件不是p!=str，而是str-1

ac代码

void replaceSpace(char *str,int length) 
{
	char* p = str;	
	int   t = 0;			//计数
	
	for(p; *p != 0; p++)
		if(*p == ' ') t++;

	for(p; p != str-1; p--)
	{
		if( *p != ' ') 
		{
			*(p+t*2) = *p;
		}
		else
		{
			 *(p+t*2) = '0';
			 *(p+t*2-1) = '2';
			 *(p+t*2-2) = '%';
			 t--;
		}
	}
}

3.从尾到头打印链表

ac代码

struct ListNode
{
	int val;
	struct ListNode *next;
	ListNode(int x) :
	val(x), next(NULL) {}
};

vector<int> printListFromTailToHead(struct ListNode* head) 
{
	vector<int> ret;
	stack<int>  st;

	if(head == NULL) return ret;
	struct ListNode* p = head;
	
	for(p; p!=NULL; p=p->next)
	{
		st.push(p->val);
	}
	
	while(!st.empty()) 
	{
		ret.push_back(st.top());
		st.pop();
	}
	return ret;
}