小Q最近遇到了一个难题：把一个字符串的大写字母放到字符串的后面，各个字符的相对位置不变，且不能申请额外的空间。 你能帮帮小Q吗？

这是一道2017腾讯暑假实习生的编程题

这道题的简单版本

剑指offer 21
剑指offer的第21道题，并没有要求相对顺序保持不变，所以解法很简单

代码实现

    public int[] exchange(int[] nums) {
         int i = 0;
        int j = nums.length-1;
        int temp;
        while (i<j){
            while(i < j && (nums[i] & 1) == 1) i++;
            while(i < j && (nums[j] & 1) == 0) j--;
            temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
        return nums;
    }

腾讯升级版

小Q最近遇到了一个难题：把一个字符串的大写字母放到字符串的后面，各个字符的相对位置不变，且不能申请额外的空间。 你能帮帮小Q吗？
而这道题，保持相对顺序不变，嗯这个简单，用多个数组保存一下就ok了，但是题目要求不能申请额外的空间，那我们应该从哪里下手呢？
我们可以这样，我们用一个big指针来指向大写字母，index指针来遍历，当index指针遇到小写字母时,有如下几种情况

1. 大写字母还没出现呢，我们直接跳过
2. 前面有大写字母出现了 ：这时分两种情况
   a .big在index前面，这种情况好说,我们直接交换就完事
   b. big不在index前面，说明big和index之前有好几个大写字母呢，如果直接交换，必然不满足题目要求，那这种场景，会不会让你想到这种东西–插入排序。

没错，我们可以用插入排序的思想，先保存原先index指向的值value，然后让big~(index-1)之间整体往后移动一个位置，然后把value插入到big的位置，就搞定了！

代码实现

	public  String getResult(String str){
        char[] c = str.toCharArray();
        int index = 0;
        int big = 0;
        while (big<c.length&&index<c.length){
            if (isSmall(c[index])){        //说明碰到小写字母了
                if(big<index){  //说明之前有big出现
                    if (index-big==1){ //big的下一个是小写字母 那么我们可以直接交换
                        char temp = c[big];
                        c[big] = c[index];
                        c[index] = temp;
                        big = index;
                    }else {     //big的下一个还是big 如果贸然交换 相对顺序就变了 所以我们要插入排序
                        char value = c[index];
                        while (index>big){
                            c[index] = c[index-1];
                            index--;
                        }
                        c[index] = value;
                        big = big+1;
                    }
                }else { //这种情况说明之前还没有big出现
                    big++;
                }
            }
            index++;
        }
        return String.valueOf(c);
    }

    public boolean isSmall(char c){
        if (c-'A'<26){
            return false;
        }else
            return true;
    }

如果这篇文章有帮到你 麻烦点个赞 让我收到你的支持 这是我分享知识的动力 谢谢你！