约瑟夫环

普通的解法:构建环然后循环去除元素

int JosephuseCircle(unsigned int n,unsigned int m){
if(n<1||m<1) return -1;
unsigned int i=0;
list<int> l;
for(i=0;i<n;++i)
l.push_back(i);
list<int>::iterator cur = l.begin();
while(l.size()>1){
for(int i=1;i<m;++i){
cur++;
if(cur == l.end())
cur = l.begin();
}
list<int>::iterator next = ++cur;
if(next == l.end())
next = l.begin();
–cur;
l.erase(cur);
cur = next;
}
return *(cur);
}

更高效的解决方法:构建递推公式

  1.  定义关于数据长度n和删除步进m的方程F(n,m),表示在n个数字0,1,…,n-1中每次删除第m个数字后最后剩下的一个数字。
  2. 在n的数字中,第一个被删除的是(m-1)%n,简记为k。那么剩下的n-1个数字是0,1,…,k-1,k+1,…,n-1.并且下一次删除从k+1开始。
  3. 在第二次删除时,数字序列是 k+1,k+2,…,n-1,0,1,…k-1。
  4. 此时的函数F(n,m)的数字序列发生了变化,为了适应该变化我们将此时的F(n,m)记为F'(n-1,m)
  5. 由于F与F’的结果都是最后一个数字,那么F(n,m)=F'(n-1,n)
  6. 然后对第二次的数字序列做映射:

k+1              ===>                       0

k+2              ===>                       1

n-1              ===>                       n-1-k-1=n-k-2

0                  ===>                       n-k-1

1                   ===>                      n-k

k-1                ===>                       n-2

7.从上面得出映射 p(x) = (x-k-1)%n,表示当前映射数字x实际上是F(n,m)中的第(x-k-1)%n个数字。逆映射p^-1(x) = (x+k+1)%n;

8.由于映射后的序列与最初的序列都具有同样的形式即都从0开始,那么仍然可以F(n-1,m)表示。可以得出

F'(n-1,m) = p^-1(F(n-1,m))=映射之前剩下的最后一个数字=[F(n-1,m)+k+1]%n

把k = (m-1)%n带入,那么F(n,m) = F'(n-1,m)=[F(n-1,m)+m]%n

9:上面的公式可以归纳为以下公式:

F(n,m)=0 if  n=1 else [F(n-1,m)+m]%n 

这是一个递归的求解过程,因为最后n=1时有具体的结果不会再继续递归下去。
int JosephuseCircle2(unsigned int n,unsigned int m){
if(n<1||m<1)
return -1;
int last = 0;
for(int i=2;i<=n;++i){
last = (last+m)%i;
}
return last;
}

快速排序之中间基准值的实现[C++实现]

在很多时候写快排选择基准值时都是使用第一个元素作为基准,今天使用了中间元素作为基准值来实现快排。

Tips:比较重要的一点是要更新基准值的位置

—————————————————————

#include <iostream>
#include <vector>
using namespace std;
int Partition(vector<int> &v,int low,int high){

int pivot = low+(high-low)/2;
while(low<high){
while(low<high&&v[high]>v[pivot]) –high;
while(low<high&&v[low]<v[pivot]) ++low;
if(low<high){
//交换元素
v[low]^=v[high];
v[high]^=v[low];
v[low]^=v[high];
//基准追踪
if(low==pivot) pivot = high;
else if(high==pivot) pivot=low;
//循环退出
if(v[low]==v[pivot]&&v[high]==v[pivot]) ++low;
}
}
return pivot;

}
void quickSort(vector<int> &v,int low,int high){
if(low<high){
int pos = Partition(v,low,high);
quickSort(v,low,pos-1);
quickSort(v,pos+1,high);
}
}

int main(){
vector<int> v={1,3,2,4,5,7,2,1};
quickSort(v,0,v.size()-1);
for(auto vi = v.begin();vi!=v.end();++vi) cout<<*vi<<” “;
cout<<endl;
return 0;
}

动态规划算法解决查找最长回文问题

class Solution {
public:
string longestPalindrome(string s) {
//BOTTOM-TOP 动态规划实现查找最长回文串
//初始化备忘矩阵
const int sz = s.size();
bool**q = new bool*[sz];
for (int i = 0; i < sz; ++i){
q[i] = new bool[sz];
for (int j = 0; j < sz; ++j){
q[i][j] = false;
}
}
//开始自底部向顶部动态规划
//首先初始化回文串起始终止位置
int pstart = -1, pend = pstart;
for (int i = sz – 1; i >= 0; –i){
for (int j = i; j < sz; ++j){
//如果子串的首尾字符相同,并且其距离不大于2或者首尾之间的子子串在备忘中是true的,
//该字串肯定是一个回文
//cout << i << “->” << j<<“|”;
if (s[i] == s[j] && (j – i <= 2 || q[i+1][j-1])==true){
q[i][j] = true;
if ((j – i+1)>(pend – pstart)) {
pstart = i;
pend = j;
//cout << i << “->” << j << endl;
}
}
}//end for

}//enf for
delete[] q;
return s.substr(pstart, pend – pstart + 1);
}

};

c++的左值与右值

C++左值与右值的含义与误区

术语 “L-Values” 和 “R-Values” 是很容易被搞混的,因为它们的历史渊源也是混淆。他们最初起源是编译器的设计者,从字面上来理解就是表达式左边的值和表达式右边的值。它们的含义一直在演 化而名字却没变,现在已经“名”不副“实”了。虽然还是称为left-value 和right-value,但是他们的含义已经大大不同了。

C++ 03 标准上是这样写的: “每一个表达式要么是一个 lvalue,要么就是一个 rvalue。”

记住,lvalue和rvalue是针对表达式而言的。

lvalue 是指那些单一表达式结束之后依然存在的持久对象。例如: obj,*ptr, prt[index], ++x 都是 lvalue。

rvalue 是指那些表达式结束时(在分号处)就不复存在了的临时对象。例如:1729 , x + y , std::string(“meow”) , 和 x++ 都是 rvalue。

++x 和 x++ 的区别的语义上的区别: 当写 int i = 10 ; 时, i 是一个 lvalue,它实际代表一个内存里的地址,是持久的。 表达式 ++x 也是一个 lvalue,它修改了 x 的值,但还是代表原来那个持久对象。但是,表达式 i++ 却是一个 rvalue,它只是拷贝一份i的初值,再修改i的值,最后返回那份临时的拷贝,那份拷贝是临时对象。 ++i 和 i++ 都递增i,但 ++i 返回i本身,而 i++ 返回临时拷贝。这就是为什么 ++i 之所以是一个 lvalue,而 i++ 是一个 rvalue。

lvalue 与 rvalue 之分不在于表达式做了什么,而在于表达式代表了什么(持久对象或临时产物)。

判断一个表达式是不是 lvalue 的直接方法就是“能不能对表达式取址?”。如果能够,那就是一个 lvalue;如果不能,那就是一个 rvalue。