练习题

发表于   |   分类于   |  

替换空格

题目描述

请实现一个函数，将一个字符串中的空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

思路：

在原数组上替换，不额外申请数组，这样从后往前替换比较好，从前往后替换则需要经常移动后面的数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
//length为规定字符串输出的最大长度，固定为一个常数
class Solution {
public:
	void replaceSpace(char *str,int length) {
        if(str==NULL||length==0)
            return;
		int originalLength=0;
        int blank=0;
        int i=0;
        while(str[i]!='\0')
        {
        	originalLength++;
            if(str[i]==' ')
            {
            	blank++;    
            }
            i++;
        }
        int newLength=originalLength+blank*2;
        if(newLength>length)
            return;
        int p=originalLength;
        int q=newLength;
        while(p>=0)
        {
            if(str[p]!=' ')
            {
                str[q]=str[p];
                p--;
                q--;
            }
            else
            {
             	str[q]='0';
                str[q-1]='2';
                str[q-2]='%';
                q=q-3;
                p--;
            }
        } 
	}
};

从尾到头打印链表

如果不允许改变链表的结构，
方法一
这里申请了一个vector，不断的头插，（即为栈）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<int> printListFromTailToHead(struct ListNode* head) {
          vector<int> v;
    ListNode*p=head;
    if(p==NULL)
    {
        return v;
    }
    else
    {
    	while(p!=NULL)
        {
        	v.insert(v.begin(),p->val);
            p=p->next;
        }
        
    }
       return v;
    }
};

方法二 递归

1
2
3
4
5
6
7
8
9
10
11
void printReverseNode(ListNode * head)
{
	if(head!=NULL)
	{
		if(head->next!=NULL)
		{
			printReverseNode(head->next);
		}
		printf("%d",head->val);	
	}
}

如果可以改变链表的结构，则直接把链表逆序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
ListNode * reverseList (ListNode* head)
{
	ListNode *pNode=head;
	ListNode *pre=NULL;
	ListNode *pNext=NULL;
	while(p->next!=NULL)
	{
		pNext=pNode->next;
		pNode->next=pre;
		pre=pNode;
		pNode=pNext;
	}
	return pNode;
}