Coding Exercise - Sort Letters by Case | 编程练习题 - 排序字母
Given a string which contains only letters. Sort it by lower case first and upper case second.
Example
For "abAcD", a reasonable answer is "acbAD"
Challenge
Do it in one-pass and in-place.
C++ Solution
No additional space should be used. We can use two pointers to skip in-place characters from both end, swap them if they are not until they meet in the middle.
The space complexity is O(1) and the time complexity is O(n).
class Solution {
public:
/*
* @param chars: The letter array you should sort by Case
* @return: nothing
*/
void sortLetters(string &chars) {
int i = 0, j = chars.length() - 1;
while (i <= j) {
// skipping in-place lower characters from the begining
while ((chars[i] >= 'a') && (chars[i] <= 'z') && i < j) i ++;
// skipping in-place upper characters from the end
while ((chars[j] >= 'A') && (chars[j] <= 'Z') && i < j) j --;
// swap
auto t = chars[i];
chars[i] = chars[j];
chars[j] = t;
i ++;
j --;
}
}
};
Support me and my work as a witness by
Thank you! Some of My Contributions: SteemIt Tutorials, Robots, Tools and APIs
Also reposted to my blog: https://helloacm.com/coding-exercise-sort-letters-by-case-c/
这题的关键在于不能额外开内存。我们可以分别从字符串的首尾开始来检查,直到它们在中间相遇。如果首指针遇到了大写字母,尾指针遇到了小写字母 就把它们交换一下即可。
时间复杂度是 O(n), 空间复杂度是 O(1)
支持我的工作 支持我成为 见证人
- 请在 这里 投我一票, 或者
- 设置我 为代理.
谢谢您! 我的贡献:SteemIt 工具、API接口、机器人和教程
股东工具
请注意:每次代理都是以最后一次输入的SP数量为标准,比如已经代理10 SP,想多代理5 SP则需要输入 最后的数字 15 SP(而不是 5!)
This is exactly what I want to learn right now
Thank you for posting this at this moment
I want to learn so let me follow you for more
Thank you @justyy
This steemcoin png for you from Nov2016
Thank you.
行长是工程师吗?我代理过啦,得慢慢的赞SP了~
算是吧, 非常 感谢。
不客气,明年我来收麦子!哈哈~