江西网站建设公司哪家好,什么公司需要建立网站,网站seo课设,公司网站备案名称题目
编写一个函数#xff0c;其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。
不要给另外的数组分配额外的空间#xff0c;你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
你可以假设数组中的所有字符都是 ASCII 码表中的可打印…题目
编写一个函数其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。
不要给另外的数组分配额外的空间你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。 示例 1 输入[h,e,l,l,o] 输出[o,l,l,e,h] 示例 2 输入[H,a,n,n,a,h] 输出[h,a,n,n,a,H] 思路
先引用原文中作者的一些经验之谈
对于这道题目一些同学直接用C里的一个库函数 reverse调一下直接完事了 相信每一门编程语言都有这样的库函数。
如果这么做题的话这样大家不会清楚反转字符串的实现原理了。
但是也不是说库函数就不能用是要分场景的。
如果在现场面试中我们什么时候使用库函数什么时候不要用库函数呢
如果题目关键的部分直接用库函数就可以解决建议不要使用库函数。
毕竟面试官一定不是考察你对库函数的熟悉程度 如果使用python和java 的同学更需要注意这一点因为python、java提供的库函数十分丰富。
如果库函数仅仅是 解题过程中的一小部分并且你已经很清楚这个库函数的内部实现原理的话可以考虑使用库函数。
建议大家平时在leetcode上练习算法的时候本着这样的原则去练习这样才有助于我们对算法的理解。
不要沉迷于使用库函数一行代码解决题目之类的技巧不是说这些技巧不好而是说这些技巧可以用来娱乐一下。真正自己写的时候要保证理解可以实现是相应的功能。
接下来再来讲一下如何解决反转字符串的问题大家应该还记得我们之前反转链表那道题在反转链表中使用了双指针的方法。那么反转字符串依然是使用双指针的方法只不过对于字符串的反转其实要比链表简单一些。因为字符串也是一种数组所以元素在内存中是连续分布这就决定了反转链表和反转字符串方式上还是有所差异的。
对于字符串我们定义两个指针也可以说是索引下标一个从字符串前面一个从字符串后面两个指针同时向中间移动并交换元素。
以字符串hello为例过程如下 不难写出如下C代码:
void reverseString(vectorchar s) {for (int i 0, j s.size() - 1; i s.size()/2; i, j--) {swap(s[i],s[j]);}
}
循环里只要做交换s[i] 和s[j]操作就可以了那么我这里使用了swap 这个库函数。大家可以使用。
因为相信大家都知道交换函数如何实现而且这个库函数仅仅是解题中的一部分 所以这里使用库函数也是可以的。
swap可以有两种实现。
一种就是常见的交换数值
int tmp s[i];
s[i] s[j];
s[j] tmp;
一种就是通过位运算
s[i] ^ s[j];
s[j] ^ s[i];
s[i] ^ s[j];
如果题目关键的部分直接用库函数就可以解决建议不要使用库函数。如果库函数仅仅是 解题过程中的一小部分并且你已经很清楚这个库函数的内部实现原理的话可以考虑使用库函数。本着这样的原则本题没有使用reverse库函数而使用swap库函数。
在字符串相关的题目中库函数对大家的诱惑力是非常大的因为会有各种反转切割取词之类的操作这也是为什么字符串的库函数这么丰富的原因。
C代码如下
class Solution {
public:void reverseString(vectorchar s) {for (int i 0, j s.size() - 1; i s.size()/2; i, j--) {swap(s[i],s[j]);}}
}; 时间复杂度: O(n)空间复杂度: O(1)
