题目4-6¶
4 二维数组中的查找¶
题目描述
在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
[
[ 1, 5, 9],
[10, 11, 13],
[12, 13, 15]
]
解题思路
从右上角或左下角开始查找，假设从右上角开始查找，如果待查找的数小于当前位置的数，那么一定在当前位置的左边，即当前位置的下边不可能存在比自己小的数。 同理，如果待查找的数大于当前位置的数，那么一定在当前位置的下边，即当前位置的左边不可能存在比自己大的数。这一原则也就意味着不能从左上角或右下角开始查找， 因为查找的过程中无法做到精准无误的排除不可能区域。
选择从右上角开始查找
class Solution
{
public:
bool Find(vector<vector<int> > array,int target)
{
bool res = false;
int row = array.size( );
int col = array[0].size( );
// 我们从右上角的元素找起来
// 如果查找的元素比当前位置元素小, 就向左走
// 如果查找的元素比当前位置元素大, 就向下走
for(int i = 0, j = col -1;
(i >=0 && i < row) && (j >= 0 && j < col);)
{
if(target == array[i][j])
{
res = true;
break;
}
else if(target < array[i][j]) // 小的元素在当前位置左侧
{
j--;
}
else
{
i++;
}
}
return res;
}
};
利用 python 实现一下
# -*- coding:utf-8 -*-
class Solution:
# array 二维列表
def Find(self, array, target):
row = len(array)
col = len(array[0])
res = False
x = 0
y = col -1
while 0 <= x < row and 0 <= y < col:
if array[x][y] == target:
res = True
break
elif array[x][y] < target:
x += 1
else:
y -= 1
return res
牛客上利用 python 字符串方法实现的查找
# -*- coding:utf-8 -*-
class Solution:
# array 二维列表
def Find(self, target, array):
# write code here
n=len(array)
flag='false'
for i in range(n):
if target in array[i]:
flag='true';
break
return flag
while True:
try:
S=Solution()
# 字符串转为list
L=list(eval(raw_input()))
array=L[1]
target=L[0]
print(S.Find(target, array))
except:
break
5 空格替换¶
题目描述
请实现一个函数，将一个字符串中的空格替换成“%20”。 例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
We Are Happy
We%20Are%20Happy
解题思路
思路分为两种，第一是不在原来的字符串上替换，直接新开一个数组然后一次赋值，这个很简单，但我想可能不是出题人希望考察的；第二是在原来的字符串上进行替换 那么因为空格和“%20”的长度不同，就相当于存在一个插入操作。
一种思路是，依次遍历，发现空格就增加字符串长度，然后填入 “%20” 后面的字符全部向前移两位，这样的话如果遇到连续的空格那么就可能会做无用功
另一种思路是，先遍历一遍字符串，统计出空格的数目，这样就知道了替换后字符串的总长度，然后再对字符串进行替换，避免了无用的移动工作。
之所以选择从后往前遍历，是因为如果空格足够多的话，这样的遍历方式在一开始一段时间内是不需要移动的，只需要复制。
/*
一个偷懒的写法，利用 string 的 find 方法实现，最后再转换回 char*
*/
class Solution
{
public:
void replaceSpace(char *str, int length)
{
string a(str);
int pos = 0;
while (pos != string::npos)
{
pos = a.find(" ", pos);
if (pos != string::npos)
{
a.replace(pos, 1, "%20");
}
}
cout << "fuck" << endl;
//最后将 string 转换为 char*
strcpy(str, a.data());
}
};
/*
笨拙型
*/
#include <iostream>
#include <Windows.h>
using namespace std;
#define __tmain main
class Solution
{
public:
void replaceSpace(char *str,int length)
{
int i = length - 1, j;
int len = length;
// 从后往前遍历
for(i = length - 1; i >= 0; i--)
{
//cout <<str[i] <<endl;
// 如果当前字符是空格
if(str[i] == ' ')
{
// 从空格变成%20长度增加了2
len += 2;
for(j = len - 1; j > i + 2; j--)
{
str[j] = str[j - 2];
}
str[j--] = '0';
str[j--] = '2';
str[j--] = '%';
}
//cout <<str <<endl;
}
str[len] = '\0';
}
};
int __tmain( )
{
char str[10 + 1] = "a b c d";
Solution solu;
solu.replaceSpace(str, 10);
cout <<str <<endl;
system("pause");
return 0;
}
// 优化型
#include <iostream>
#include <Windows.h>
using namespace std;
#define __tmain main
class Solution
{
public:
void replaceSpace(char *str, int length)
{
int i, j;
int count = 0;
int len = length;
for(int i = 0; i < length; i++)
{
if(str[i] == ' ')
{
count++;
}
}
len = length + count * 2;
for(i = length - 1, j = len - 1;
i >= 0 && j >= 0;)
{
if(str[i] == ' ')
{
str[j--] = '0';
str[j--] = '2';
str[j--] = '%';
i--;
}
else
{
str[j--] = str[i--];
}
}
str[len] = '\0';
}
};
int __tmain( )
{
char str[10 + 1] = "a b c d";
Solution solu;
solu.replaceSpace(str, 10);
cout << str << endl;
system("pause");
return 0;
}
python 实现
# -*- coding:utf-8 -*-
class Solution:
# s 源字符串
def replaceSpace(self, s):
# write code here
s = list(s)
count=len(s)
for i in range(0,count):
if s[i]==' ':
s[i]='%20'
return ''.join(s)
6 从尾到头打印链表¶
题目描述
输入一个链表，从尾到头打印链表每个节点的值。
输入描述：
输入为链表的表头
输出描述：
输出为需要打印的 vector
解题思路
首先我们想到的就是反转链表了，甚至可以利用 reverse 方法，这样再次遍历的时候就相当于从尾到头打印了。
但是修改输入数据真的可行么？在面试时候，如果我们打算修改输入的数据，最好先问问面试官是不是允许修改 通常打印只是一个只读操作，我们肯定不希望输入时候修改链表的内容
1.利用栈的先进后出特性，每经过一个结点的时候，把该结点放到一个栈中。当遍历完整个链表后，再从栈顶开始逐个输出结点的值，此时输出的结点的顺序已经反转过来了。
struct ListNode
{
public:
int val;
struct ListNode *next;
/*ListNode(int x) :
val(x), next(NULL)
{
}*/
};
class Solution
{
public:
vector<int> printListFromTailToHead(struct ListNode* head)
{
ListNode *node = head;
stack<int> st;
int count = 0;
while (node != NULL)
{
dout << node->val << " in stack" << endl;
st.push(node->val);
count++;
node = node->next;
}
vector<int> res(count);
dout << "count = " << count << endl;
for (int i = 0; i < count && st.empty() != true; i++)
{
dout << st.top() << " in vector" << endl;
//res.push_back(st.top( ));
res[i] = st.top();
st.pop();
}
return res;
}
};
2.利用递归。因为递归本来就是一个函数压栈的过程，所以很自然的适合此题的场景
class Solution
{
public:
//利用 递归的实现
vector<int> res; //因为利用了递归，所以不能定义在函数内部
vector<int> printListFromTailToHead_0(struct ListNode* head)
{
if(head != NULL)
{
printListFromTailToHead(head->next);
res.push_back(head->val);
}
return res;
}
};
- 不使用 栈 也不使用 递归，利用链表的头插法的逆序特性
但此方法会改变原链表
class Solution
{
public:
//利用头插法实现
vector<int> printListFromTailToHead(struct ListNode* head)
{
ListNode *Head = new ListNode;//头节点 即 -1 节点
Head->next = NULL;
ListNode *cur = head;
for (; cur != NULL;)
{
ListNode* temp = cur->next;
cur->next = Head->next;
Head->next = cur;
cur = temp;
}
Head = Head->next;
vector<int> array;
for (; Head != NULL;Head = Head->next)
{
array.push_back(Head->val);
}
return array;
}
};