循环不变式

一个字符串中只包含‘’和数字,请把所有‘’放在开头?

思路

采用快排的partition模式处理——数字的相对顺序会变化

循环不变式:[0..i-1]都是*,[i,j-1]都是数字,[j..n-1]都是未探测。

伪代码:

int n = len(str);
for(int i = 0,j=0; j<n; j++)
{
    if(str[j]=='*') 
        swap(str[i++],str[j]);
}

考虑:

两个指针i和j,i相当于“锚点”,永远指向已搜索区间中从前往后数第一个不是‘’的位置,j是搜索指针不断向后搜索,当j发现‘’时,将‘’与i位置进行数据交换,此时第i位变成‘’,所以要i++。

在1的基础上,要求不改变数字的相对位置顺序。

思路

在思路1的基础上,将遍历顺序从0~n改为从n~0(倒叙),将发现的数字逐个往后挪,然后在开头补‘*’

伪代码

int j = len(str)-1;
for(int i = 0; i < len(str); i++)
{
    if( str[i] == '*' )
    {

    }
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据