请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
class Solution {
public:
void replaceSpace(char *str, int length) {
if (str == nullptr)return;
int numspace = 0;
int strlen= 0;
while (str[strlen] != '\0')
{
if (str[strlen] == ' ')
numspace++;
strlen++;
}
int new_strlen = strlen+numspace * 2+1;
if (new_strlen > length)return;
str[new_strlen - 1] = '\0';
//str[length - 1] = '\0';
int p1 = strlen - 1, p2 = new_strlen - 2;
while (p1 != p2 && p1>=0)
{
if (str[p1] == ' ')
{
str[p2] = '0'; p2--;
str[p2] = '2'; p2--;
str[p2] = '%'; p2--;
p1--;
}
else
{
str[p2] = str[p1];
p1--;
p2--;
}
}
}
};
用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。
c++ code:牛客网没有考虑两个栈都是空，即可通过。
class Solution
{
public:
void push(int node) {
stack1.push(node);
}
int pop() {
int deletenode;
if (!stack2.empty())
{
deletenode = stack2.top();
stack2.pop();
return deletenode;
}
else
{
while (!stack1.empty())
{
int temp = stack1.top();
stack1.pop();
stack2.push(temp);
}
deletenode = stack2.top();
stack2.pop();
return deletenode;
}
}
private:
stack<int> stack1;
stack<int> stack2;
};
输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。 C++
方法一：利用栈
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};
class Solution {
public:
vector<int> printListFromTailToHead(ListNode* head) {
vector<int> res;
stack<ListNode*>sNode;
ListNode* pNode = head;
while (pNode!=nullptr)
{
sNode.push(pNode);
pNode = pNode->next;
}
while (!sNode.empty())
{
pNode = sNode.top();
res.push_back(pNode->val);
sNode.pop();
}
return res;
}
};
完整测试代码：
#include<List.h>
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<stack>
#include<sstream>
#include<assert.h>
#include<math.h>
using namespace std;
class Solution {
public:
vector<int> printListFromTailToHead(ListNode* head) {
vector<int> res;
stack<ListNode*>sNode;
ListNode* pNode = head;
while (pNode != nullptr)
{
sNode.push(pNode);
pNode = pNode->m_pNext;
}
while (!sNode.empty())
{
pNode = sNode.top();
res.push_back(pNode->m_nValue);
sNode.pop();
}
return res;
}
};
int main() {
printf("\nTest1 begins.\n");
ListNode* pNode1 = CreateListNode(1);
ListNode* pNode2 = CreateListNode(2);
ListNode* pNode3 = CreateListNode(3);
ListNode* pNode4 = CreateListNode(4);
ListNode* pNode5 = CreateListNode(5);
ConnectListNodes(pNode1, pNode2);
ConnectListNodes(pNode2, pNode3);
ConnectListNodes(pNode3, pNode4);
ConnectListNodes(pNode4, pNode5);
vector<int>res= Solution().printListFromTailToHead(pNode1);
for (vector<int>::iterator iter = res.begin(); iter != res.end();iter++)
cout << *iter <<" ";
return 0;
}
方法二：利用递归
class Solution {
public:
vector<int> printListFromTailToHead(ListNode* head) {
vector<int> res(0);
ListNode* pNode = head;
if (pNode != nullptr)
{
if (pNode->m_pNext != nullptr)
{
res = printListFromTailToHead(pNode->m_pNext);//注意一定要写res; 否则res没有更新
}
res.push_back(pNode->m_nValue);
}
return res;
}
};
重建二叉树
class Solution {
public:
TreeNode* reConstructBinaryTree(vector<int> pre, vector<int> vin) {
if (pre.size() <= 0)return nullptr;
return Construct(pre, 0, pre.size() - 1, vin, 0, vin.size() - 1);
}
TreeNode* Construct(vector<int> pre, int pleft, int pright,
vector<int> vin, int inleft, int inright) {
TreeNode* root = new TreeNode(pre[pleft]);
root->left = root->right = nullptr;
if(pleft==pright)
{
if(inleft==inright&&vin[inleft]==vin[inright])
return root;
}
int vincenter;
for (int i = inleft; i<=inright; i++)
{
if (pre[pleft] == vin[i])
{
vincenter = i;
break;
}
}
int leftlen = vincenter - inleft;
if (leftlen>0)
root->left = Construct(pre, pleft + 1, pleft+leftlen, vin, inleft, vincenter-1);
if (leftlen<pright-pleft)
root->right = Construct(pre, pleft + leftlen+1, pright, vin, vincenter + 1, inright);
return root;
}
};
大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。
n<=39
递归：
class Solution {
public:
int Fibonacci(int n) {
if(n==0) return 0;
if(n==1||n==2) return 1;
else
return Fibonacci(n-1)+Fibonacci(n-2);
}
};
循环：
class Solution {
public:
int Fibonacci(int n) {
int f0 = 0;
int f1 = 1, f2 = 1;
int fn;
if (n == 0) return 0;
if (n == 1 || n == 2) return 1;
for (int i = 3; i <= n; i++)
{
fn = f1 + f2;
f1 = f2;
f2 = fn;
}
return fn;
}
};
旋转数组的最小数字:
- 直接排序通过，但是还不如直接查找
class Solution {
public:
int minNumberInRotateArray(vector<int> rotateArray) {
if(rotateArray.size()==0)return 0;
for(int i=0;i<rotateArray.size();i++){
if(rotateArray[i]<0)return 0;
}
std::sort(rotateArray.begin(),rotateArray.end());
return rotateArray[0];
}
};
- 利用二分查找的思想：
class Solution {
public:
int minNumberInRotateArray(vector<int> rotateArray) {
if (rotateArray.size() == 0)return 0;
int index1 = 0;
int index2 = rotateArray.size() - 1;
int midindex = index1;
while (rotateArray[index1] >= rotateArray[index2])
{
if (index2 - index1 == 1)
{
midindex = index2;
break;
}
midindex = (index1 + index2) / 2;
if (rotateArray[index1] == rotateArray[index2] && rotateArray[index1] == rotateArray[midindex])
{
return minNum(index1, index2, rotateArray);
}
if (rotateArray[midindex] >= rotateArray[index1])
{
index1 = midindex;
}
if (rotateArray[midindex] <= rotateArray[index2])
{
index2 = midindex;
}
}
return rotateArray[midindex];
}
int minNum(int i, int j, vector<int> Array)
{
int min = Array[i];
for (int k = i; k <= j; k++)
{
if (min>Array[k])
min = Array[k];
}
return min;
}
};
二进制中1的个数
class Solution {
public:
int NumberOf1(int n) {
int flag=1,count=0;
while(flag)//循环到32位结束为止
{
if(n&flag)count++;
flag=flag<<1;
}
return count;
}
};
class Solution {
public:
int NumberOf1(int n) {
int count=0;
while(n)//n有几个1就循环几次
{
n=(n-1)&n;
count++;
}
return count;
}
};
网友评论