Isomorphic Strings

Given two strings s and t, determine if they are isomorphic.

Two strings are isomorphic if the characters in s can be replaced to get t.

All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character but a character may map to itself.

For example,
Given "egg", "add", return true.

Given "foo", "bar", return false.

Given "paper", "title", return true.

Note:
You may assume both s and t have the same length.

My solution:


#include<iostream>

#include<string>

#include<array>

using namespace std;

class Solution {

public:

        //compute code : egg maps to 10,20,20,  ddeea maps to 20;20;21;21;10

            //if two string are isomorphic iff they have same code       

            //input string s, output code



    void compute_code(string s, int code[], int N){

          int occur[N+1];

          for(int i=0;i<N+1;i++){

            occur[i]=0;

          }

          for(int i=0;i<N;i++){

            code[i]=0;

          }

          for(int i=0;i<s.size();i++){

            if(code[i]==0){

                //count the number of occurence of s[i]

                int counter=1;

                for (int j=i+1;j<s.size();j++){

                    if(s[j]==s[i]){counter++;}

                }

                int code_nr = 10*counter+occur[counter];

                occur[counter]++;

                for(int j=i;j<N;j++){

                    if(s[j]==s[i]){code[j]=code_nr;}

                }   

            }   

          }   

        return;    

    }   

    bool isIsomorphic(string s, string t) { 

         if(s.size()!=t.size())return false;



          int N = s.size();

          int code_s[N];

          int code_t[N];

          compute_code(s,code_s,N);

          compute_code(t,code_t,N);

          for(int i=0;i<N;i++){

            if(code_s[i]!=code_t[i]){return false;}

          }

          return true;

    }      

};

int main(){

    string s="add";

    string t="egg";

    Solution S;

    bool result = S.isIsomorphic(s,t);

    cout<<result<<endl;

    return 0;

}

Quick Sort

Quick Sort

 


#include<iostream>
using namespace std;

int partition(int a[], int low, int high, int p){
    //swap a[p] and a[0]
    int temp;
    if(p!=low){temp=a[low];a[low]=a[p];a[p]=temp;}
    int i=low+1;
    int j=high;
    do{
        while(a[i]<=a[low] && i<high){i++;}
        while(a[j]>a[low] && j>low){j--;}
        if(i<j){temp=a[i];a[i]=a[j];a[j]=temp;i++;j--;}
    }while(i<=j);
    //swap a[low] and a[j]
    if(j!=low){temp=a[low];a[low]=a[j];a[j]=temp;}
    return j;
}
void quick_sort(int a[],int low, int high){
    if(low<high){
        int p;
        int mid=(low+high)/2;
        p=partition(a,low,high,mid);
        quick_sort(a,low,p-1);
        quick_sort(a,p+1,high);
    }
return;
}

int main(){
int a[]={5,23,9,0,-1};
int n=sizeof(a)/sizeof(int);
for(int j=0;j<n;j++){cout<<a[j]<<" ";}cout<<endl;
quick_sort(a,0,n-1);
for(int j=0;j<n;j++){cout<<a[j]<<" ";}cout<<endl;
}




Merge Sort

Merge Sort

 


#include<iostream>

using namespace std;

void merge(int a[], int b[], int low, int mid, int high){
    for(int j=low;j<=high;j++){
        b[j]=a[j];
    }
int low1=low;
int low2=mid+1;
    int current=low;
    while(low1<=mid && low2<=high){
        if(b[low1]<=b[low2]){
            a[current]=b[low1];
            current++;
            low1++;
        }
        else{
            a[current]=b[low2];
           current++;
              low2++;
       }
    }

while(low1<=mid){
    a[current]=b[low1];
    low1++;
    current++;
}
return;
}

void merge_sort(int a[],int b[],int low, int high){
    if(low<high){
        int mid=(low+high)/2;
        merge_sort(a,b,low,mid);
        merge_sort(a,b,mid+1,high);
        merge(a,b,low, mid, high);
}
return;
}

int main(){
int a[]={5,23,9,0,-1};
int n=sizeof(a)/sizeof(int);
for(int j=0;j<n;j++){cout<<a[j]<<" ";}cout<<endl;
int b[n];
merge_sort(a,b,0,n-1);
for(int j=0;j<n;j++){cout<<a[j]<<" ";}cout<<endl;
}

Binary Search

Binary Search

 

#include<iostream>

using namespace std;

int binary_search(int a[], int n, int x){
    int low=0;
    int high=n-1;
    while(low<=high){
        int mid=(low+high)/2;
        if(a[mid]==x){return mid;}
        else if(a[mid]<x){
            low=mid+1;
}
else {high=mid-1;}
}
return -1;
//return low; if one wants to find out the insert position when x not found.
}

int main(){
int a[]={0,1,2,3,4,5,6};
cout<<binary_search(a,7,-1);
return 0;
}

按照Dr. Pan的建议 今天找出了以前数据结构课上的笔记 用白板练习基础的数据结构和算法 binary search, merge sort, quick sort, selection,… 明天继续

心不静,状态不佳,努力克服我的不淡定,只好带着白板在户外练习,下雨挺冷,但是空气好清新,看看天空和小草,人也跟着变轻松了,风水地理于心境的力量果然不容小觑。想想觉得,人为什么要朝九晚五坐在一个格子里工作呢,多么的变态和不和常理啊,要是能把办公桌搬到户外多好啊。希望有朝一日能实现我working outside的理想,只是现在的我,正为了能有个格子让我朝九晚五而奋斗着。

放松都变成了件难事,人,真是不断和自己做斗争的动物啊。淡定 淡定。

Gas Station

There are N gas stations along a circular route, where the amount of gas at station i is gas[i].

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.

Return the starting gas station’s index if you can travel around the circuit once, otherwise return -1.

Note:
The solution is guaranteed to be unique.

My solution: Started with a brutal force solution, then optimized it to the following linear solution. Finally got it right! 😀

class Solution {
public:
 int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {

int N=gas.size();
int try_start=0;
do{
int gas_left=0;
int j=0;
for( j=0;j<N;j++){
    gas_left+=gas[(try_start+j)%N]-cost[(try_start+j)%N];
    if(gas_left<0){
        try_start+=j+1;
        break;
    }
}
//cout<<j<<endl;
if(j==N) {return try_start;}
}while(try_start<N);
return try_start<N ? try_start: -1;
 }
};

Unique Binary Search Trees

Given n, how many structurally unique BST’s (binary search trees) that store values 1…n?

For example,
Given n = 3, there are a total of 5 unique BST’s.

 

My solution: This solution uses recursion. It can be modified to use dynamic programming to achieve higher efficiency at the cost of extra space.

class Solution {
public:
    int numTrees(int n) {
        if(n<0) return -1;
        if(n==0) return 1;
        else{
            int result=0;
            for(int r=0;r<n;r++){
                result=result+numTrees(r)*numTrees(n-r-1);
            }
            return result;
        }

    }
};