画图、举例子和分解这三种办法能够帮助我们解决复杂的编程问题。
图形能使抽象的问题形象化，如涉及链表、 二叉树等数据结构时， 如果在纸上画几张草图， 数形结合，抽象问题中中隐藏的规律就有可能变得很直观。
一个或两个简单而有代表性的例子能使抽象的问题具体化。很多与算法相关的问题都很抽象，未必一眼就能看出它们的规律。 这个时候我们不妨举几个例子， —步一步模拟运行的过程， 说不定就能发现其中的规律， 从而找到解决问题的窍门。
把复杂问题分解成若干个小问题， 是解决很多复杂问题的有效方法。如果我们遇到的问题很大， 可以尝试先把大问题分解成小问题， 然后再递归地解决这些小问题。 分治法、 动态规划等方法都是应用分解复杂问题的思路。从整体上来说，面向过程和面向对象的设计哲学都有这种分解思维的体现，面向对象：函数分解。面向过程：类与对象分解，在类的内部再分解出成员函数。
题目：请实现一个函数，把字符串中的每个空格替换成"%20"。例如输入“We are happy.”，则输出“We%20are%20happy.”。
在网络编程中，如果URL参数中含有特殊字符，如空格、'#'等，可能导致服务器端无法获得正确的参数值。我们需要将这些特殊符号转换成服务器可以识别的字符。转换的规则是在'%'后面跟上ASCII码的两位十六进制的表示。比如空格的ASCII码是32，即十六进制的0x20，因此空格被替换成"%20"。再比如'#'的ASCII码为35，即十六进制的0x23，它在URL中被替换为"%23"。
看到这个题目，我们首先应该想到的是原来一个空格字符，替换之后变成'%'、'2'和'0'这3个字符，因此字符串会变长。如果是在原来的字符串上做替换，那么就有可能覆盖修改在该字符串后面的内存。如果是创建新的字符串并在新的字符串上做替换，那么我们可以自己分配足够多的内存。
现在我们考虑怎么做替换操作。最直观的做法是从头到尾扫描字符串，每一次碰到空格字符的时候做替换。由于是把1个字符替换成3个字符，我们必须要把空格后面所有的字符都后移两个字节，否则就有两个字符被覆盖了。
举个例子，我们从头到尾把"We are happy."中的每一个空格替换成"%20"。为了形象起见，我们可以用一个表格来表示字符串，表格中的每个格子表示一个字符。
我们替换第一个空格，这个字符串变成下图中的内容：
表格中灰色背景的格子表示需要做移动的区域。接着我们替换第二个空格，替换之后的内容如下图所示：
同时，我们注意到用深灰色背景标注的"happy"部分被移动了两次。
假设字符串的长度是n。对每个空格字符，需要移动后面O(n)个字符，因此对含有O(n)个空格字符的字符串而言总的时间效率是O(n2)。
在前面的分析中，我们发现数组中很多字符都移动了很多次，能不能减少移动次数呢？答案是肯定的。我们换一种思路，把从前向后替换改成从后向前替换。
我们可以先遍历一次字符串，这样就能统计出字符串中空格的总数，并可以由此计算出替换之后的字符串的总长度。每替换一个空格，长度增加2，因此替换以后字符串的长度等于原来的长度加上2乘以空格数目。我们还是以前面的字符串"We are happy."为例，"We are happy."这个字符串的长度是14（包括结尾符号'\0'），里面有两个空格，因此替换之后字符串的长度是18。
我们从字符串的后面开始复制和替换。首先准备两个指针，P1和P2。P1指向原始字符串的末尾，而P2指向替换之后的字符串的末尾，如下图所示：
接下来我们向前移动指针P1，逐个把它指向的字符复制到P2指向的位置，直到碰到第一个空格为止。此时字符串包含如下图所示：
灰色背景的区域是做了字符拷贝（移动）的区域。碰到第一个空格之后，把P1向前移动1格，在P2之前插入字符串"%20"。由于"%20"的长度为3，同时也要把P2向前移动3格如下图所示：
我们接着向前复制，直到碰到第二个空格，如下图所示：
和上一次一样，我们再把P1向前移动1格，并把P2向前移动3格插入"%20"，如下图所示：
此时P1和P2指向同一位置，表明所有空格都已经替换完毕。
从上面的分析我们可以看出，所有的字符都只复制（移动）一次，因此这个算法的时间效率是O(n)，比第一个思路要快。
代码：
#include <stdio.h>
#include <string>
/*length 为字符数组string的总容量*/
void ReplaceBlank(char string[], int length)
{
if(string == NULL && length <= 0)
return;
/*originalLength 为字符串string的实际长度*/
int originalLength = 0;
int numberOfBlank = 0;
int i = 0;
while(string[i] != '\0')
{
++ originalLength;
if(string[i] == ' ')
++ numberOfBlank;
++ i;
}
/*newLength 为把空格替换成'%20'之后的长度*/
int newLength = originalLength + numberOfBlank * 2;
if(newLength > length)
return;
int indexOfOriginal = originalLength;
int indexOfNew = newLength;
while(indexOfOriginal >= 0 && indexOfNew > indexOfOriginal)
{
if(string[indexOfOriginal] == ' ')
{
string[indexOfNew --] = '0';
string[indexOfNew --] = '2';
string[indexOfNew --] = '%';
}
else
{
string[indexOfNew --] = string[indexOfOriginal];
}
-- indexOfOriginal;
}
}
void Test(char* testName, char string[], int length, char expected[])
{
if(testName != NULL)
printf("%s begins: ", testName);
ReplaceBlank(string, length);
if(expected == NULL && string == NULL)
printf("passed.\n");
else if(expected == NULL && string != NULL)
printf("failed.\n");
else if(strcmp(string, expected) == 0)
printf("passed.\n");
else
printf("failed.\n");
}
// 空格在句子中间
void Test1()
{
const int length = 100;
char string[length] = "hello world";
Test("Test1", string, length, "hello%20world");
}
// 空格在句子开头
void Test2()
{
const int length = 100;
char string[length] = " helloworld";
Test("Test2", string, length, "%20helloworld");
}
// 空格在句子末尾
void Test3()
{
const int length = 100;
char string[length] = "helloworld ";
Test("Test3", string, length, "helloworld%20");
}
// 连续有两个空格
void Test4()
{
const int length = 100;
char string[length] = "hello world";
Test("Test4", string, length, "hello%20%20world");
}
// 传入NULL
void Test5()
{
Test("Test5", NULL, 0, NULL);
}
// 传入内容为空的字符串
void Test6()
{
const int length = 100;
char string[length] = "";
Test("Test6", string, length, "");
}
//传入内容为一个空格的字符串
void Test7()
{
const int length = 100;
char string[length] = " ";
Test("Test7", string, length, "%20");
}
// 传入的字符串没有空格
void Test8()
{
const int length = 100;
char string[length] = "helloworld";
Test("Test8", string, length, "helloworld");
}
// 传入的字符串全是空格
void Test9()
{
const int length = 100;
char string[length] = " ";
Test("Test9", string, length, "%20%20%20");
}
int main()
{
Test1();
Test2();
Test3();
Test4();
Test5();
Test6();
Test7();
Test8();
Test9();
while(1);
return 0;
}这个问题看似稍微有点复杂，但分解后，再组合成相互调用关系，就简单了。
某年日历输出可以分解为以下函数功能：
void PrintHead(int m);// 打印每月日历的头部
bool IsLeapYear(int y);// 是否闰年
int FirstDayOfYear(int y);// 元旦是周几
int DaysOfMonth(int m);// 某月天数
void PrintMonth(int m);// 打印某月日历代码：
#include<iostream>
using namespace std;
#include<iomanip>
void PrintHead(int m);// 打印每月日历的头部
bool IsLeapYear(int y);// 是否闰年
int FirstDayOfYear(int y);// 元旦是周几
int DaysOfMonth(int m);// 某月天数
void PrintMonth(int m);// 打印某月日历
int weekDay;// 每月1号是周几
int year;
void main()
{
cerr<<"请输入您想要打印的年份:\n";
cin>>year;
if(year<1900)
{
//cerr<<"年份不能小于1900。\n";
//return;
}
weekDay=FirstDayOfYear(year);// 一年的第一天星期几
cout<<"\n\n "<<year<<" 年日历\n";// 打印年标题
cout<<"\n ===================================================";
for(int i=1;i<=12;i++)// 打印每个月
PrintMonth(i);
cout<<endl;
system("pause");
}
void PrintMonth(int m)// 某个月打印函数
{
PrintHead(m);// 打印月标题
int days=DaysOfMonth(m);// 该月的天数
for(int i=1;i<=days;i++)
{
cout<<setw(6)<<i;
weekDay=(weekDay+1)%7;
if(weekDay==0)// 打印下一天时判断是否换行
{
cout<<endl;
cout<<setw(10)<<" ";// 行首空格
}
}
}
void PrintHead(int m)// 打印月标题
{
cout<<"\n\n"<<setw(6)<<m<<"月"<<setw(6)<<" "<<"日";
cout<<" 一 二 三 四 五 六\n"; // 字符前都有4个空格
cout<<setw(10)<<" ";// 行首空格
for(int i=0;i<weekDay;i++)
cout<<setw(6)<<" ";
}
int DaysOfMonth(int m)// 判断某月天数的函数
{
switch(m){
case 1:
case 3:
case 5:
case 7:
case 8:
case 10:
case 12:return 31;
case 4:
case 6:
case 9:
case 11:return 30;
case 2:if(IsLeapYear(year))
return 29;
else
return 28;
}
return 0;
}
bool IsLeapYear(int y)// 判断是否为闰年
{
return((y%4==0&&y%100!=0)||year%400==0);
}
int FirstDayOfYear(int y) // 判断某年的1月1日是星期几
{
// 公元1年1月1日是周1
// 如果不考虑闰年，则一年是365天，365%7=1，所以公元2年的第一天是周二、
// 公元3年的第一天是周三……这样，再把闰年考虑进来即可
return (y+(y-1)/400+(y-1)/4-(y-1)/100)%7; //
}3.1 删除链表中指定的元素
代码：
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
// 创建虚拟头结点
ListNode* dummyHead = new ListNode(0);
dummyHead->next = head;
ListNode* cur = dummyHead;
while(cur->next != NULL){
if(cur->next->val == val){
ListNode* delNode = cur->next;
cur->next = delNode->next;
delete delNode;
}
else
cur = cur->next;
}
ListNode* retNode = dummyHead->next;
delete dummyHead;
return retNode;
}
};3.2 反转链表
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* pre = NULL;
ListNode* cur = head;
while(cur != NULL){
ListNode* next = cur->next;
cur->next = pre;
pre = cur;
cur = next;
}
return pre;
}
};3.3 层次遍历二叉树
3.4 移除倒数第n个节点
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* dummyHead = new ListNode(0);
dummyHead->next = head;
ListNode* p = dummyHead;
ListNode* q = dummyHead;
for( int i = 0 ; i < n + 1 ; i ++ ){
q = q->next;
}
while(q){
p = p->next;
q = q->next;
}
ListNode* delNode = p->next;
p->next = delNode->next;
delete delNode;
ListNode* retNode = dummyHead->next;
delete dummyHead;
return retNode;
}
};3.5 二分查找
#include<iostream> // 二分查找的递归与非递归实现
using namespace std; // 分治法，可分，可合，子问题有独立性
int bisoLoop(int arr[], int len, int findData)
{
if(arr==NULL || len <=0)
return -1;
int start = 0;
int end = len-1;
while(start<=end)
{
int mid = start+(end-start)/2;
if(arr[mid] == findData)
return mid;
else if(findData < arr[mid])
end = mid-1;
else
start = mid+1;
}
return -1;
}
// 递归有自调用的问题，需要将start和end写在参数列表中
// 来标记和动态变更搜索范围的开始和结束
int bisoRecurs(int arr[], int findData, int start, int end)
{
if(arr==NULL || start>end)
return -1;
int mid = start+(end-start)/2;
if(arr[mid] == findData)
return mid;
else if(findData < arr[mid])
bisoRecurs(arr, findData, start, mid-1);
else
bisoRecurs(arr, findData, mid+1, end);
}
void main()
{
int arr[] = {1,2,3,4,5,6,7,8,9};
int len = sizeof(arr)/sizeof(arr[0]);
int index = bisoLoop(arr,len,6);
int index2 = bisoRecurs(arr,6,0,len-1);
cout<<index<<endl;
cout<<index2<<endl;
system("pause");
}ref：《剑指Offer：名企面试官精讲典型编程题》
－End－
联系客服
