Climbing Stairs
Just Fibonacci. Dynamic Programming's space complexity can be optimized by only store previous two value.
Sort Colors
- traverse one pass, counting all elements then rearrange.
- 3 pointers
void swap(int &a, int &b){
int temp = a;
a=b;
b=temp;
}
public:
void sortColors(vector<int>& nums) {
int low = 0;
int high = nums.size()-1;
int mid = 0;
while(mid<=high){
if(nums[mid]==0){
swap(nums[mid],nums[low]);
low++;
mid=low;
}
else if(nums[mid]==2){
swap(nums[mid], nums[high]);
high--;
}
else
mid++;
}
}
When swap in place, one thing need to pay attention is that the swapped value will change to an unknown value, so mid cannot move, need to judge again.
- Still 3 pointers
void sortColors(int A[], int n) {
int n0 = -1, n1 = -1, n2 = -1;
for (int i = 0; i < n; ++i) {
if (A[i] == 0)
{
A[++n2] = 2; A[++n1] = 1; A[++n0] = 0;
}
else if (A[i] == 1)
{
A[++n2] = 2; A[++n1] = 1;
}
else if (A[i] == 2)
{
A[++n2] = 2;
}
}
}
All pointers begin at 0 and then add up.
