///二分查找
int binary_search(int* a,int length,int gold){
    int low = 0;
    int high = length - 1;

    while(low<high){
        int middle = (high - low)/2 + low;

        if (a[middle] == gold)
        {
            return middle;
        }eles if (a[middle]>gold)
        {   
            high = middle-1;
        }eles{
            low = middle+1;
        }
    }
    return -1;
}


int binary_search(int *a,in† length,in† gold){
    int low = 0;
    int high = length - 1;
    int middle = (high-low)/2+low;
    if (middle == gold)
    {
        return middle;
    }eles if (middle > gold)
    {
        high = middle-1;
    }eles{
        low = middle+1;
    }

    if (low > high)
    {
        return -1;
    }eles{
        binary_search(a,length,gold);
    }
}

void reverse(List* list)
{ 
    Node* before = list->first;  
    if (before != NULL)
    {
        Node* after = before->next;  
        before->next = NULL;  
        while (after)  
        {  
            //交换指针  
            Node* temp = after->next;  
            after->next = before;  
            before = after;  
            after = temp;  
        }  
    }
}



void reverse(List* list){
    Node* head = list->head;

    if (head)
    {
        Node *next = list->next;
        head->next = NULL;

        while(next){
            next->next = head;
            head = next;
            next = next->next;
        }
    }

}

//字符串转数字算法
int atoii(char* string){
    assert(NULL!=string);
    
    int result = 0;
    while(*string>='0'&&*string<='9'){
        result *= 10;
        result += *string - '0';
        string++;
    }
    
    return result;
}
bool isSwap(char*str,int begin,int end){
    for (int i = begin; i < end; ++i)
    {
        if (str[i] == str[end])
        {
            result false;
        }
    }
    return true;
}
void AllRange(char *str, int start,int lenth){

    if (start == lenth)
    {
        static int index = 1;
        printf("%d%s\n", index++,str);
    }else{
        for (int i = start; i < lenth; ++i)
        {
            if (isSwap(str,start,i))
            {
                swap(str,start,i);
                AllRange(str,start+1,lenth);
                swap(str,start,i);
            }

        }
    }
}

//翻转字符串
//按char翻转字符串
void reverseByChar(char* begin,char* end){
    while (begin<end) {
        char temp = *begin;
        *begin = *end;
        *end = temp;
        begin++;
        end--;
    }
}

//按照word翻转字符转
void reverseByWord(char* str){
    char* begin = str;
    char* end;
    for (end = begin; *end!='\0'; end++);
    end--;
//    or
//    long lenth = strlen(str);
//    end = begin + lenth -1;
    reverseByChar(begin, end);
    
    while (begin<=end) {
        char* charEnd ;
        //find begin  find first not ' '
        for (; *begin==' '; begin++);
        //find charEnd  find first  ' '
        for (charEnd = begin; *charEnd!=' '&&charEnd<=end; charEnd++);
        charEnd--;
        reverseByChar(begin, charEnd);
        begin = ++charEnd;
    }
    
    NSLog(@"%s",str);
}
int main(int argc, char *argv[])
{
    char s1[] = "I am a student";
    reverseByWord(s1);
    return 0;
}

//合并两个有序链表

typedef struct List {
    int value;
    struct List* next;
}list,*plist;

plist mergeNode(plist a,plist b){
    plist resultNode;
    plist curNode;
    plist pa = a->next;
    plist pb = b->next;
    
    curNode = a;
    resultNode = curNode;
    while(pa&&pb){
        
        if (pa == pb) {
            pb = NULL;
            break;
        }
        
        if (pa->value<pb->value)
        {
            curNode->next = pa;
            curNode = pa;
            pa = pa->next;
        }else{
            if (pa->value != pb->value) {
                curNode->next = pb;
                curNode = pb;
            }
           
            pb = pb->next;
        }
    }
    
    curNode->next = pa?pa:pb;
    return resultNode;
}

//翻转二叉树
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
TreeNode invertTree(TreeNode root) {
    if (root == null) {
        return null;
    }
    TreeNode right = invertTree(root.right);
    TreeNode left = invertTree(root.left);
    root.left = right;
    root.right = left;
    return root;
}

//堆排序
//最大堆初始化
void initMaxHeap(int arr[],int lenth){
    for (int i = (lenth-1)/2; i >= 0; --i)
    {
        adjustHeap(arr,lenth,i);
    }
}

//调整堆
void adjustHeap(int arr[],int lenth,int parentNodeIndex){
    if (lenth<=1)
    {
        return;
    }

    int targetIndex = -1;

    int leftChildIndex = 2*parentNodeIndex + 1;
    int rightChildIndex = 2*parentNodeIndex + 2;

    if (leftChildIndex>=lenth)
    {
        return;
    }

    if (rightChildIndex>=lenth)
    {
        targetIndex = leftChildIndex;
    }else{
        targetIndex = arr[leftChildIndex]>arr[rightChildIndex]?leftChildIndex:rightChildIndex;
    }

    if (arr[targetIndex]>arr[parentNodeIndex])
    {
        int temp = arr[targetIndex];
        arr[targetIndex] = arr[parentNodeIndex];
        arr[parentNodeIndex] = temp;

        //换位后可能导致不是最大堆，需要调整
        adjustHeap(arr,lenth,targetIndex);
    }

}

//排序
void heapSort(int arr[], int lenth){
    if (lenth<=1)
    {
        return;
    }

    //初始化
    initMaxHeap(arr,lenth);

    for (int i = lenth-1; i > 0 ; --i)
    {
        if (arr[0]>arr[i])
        {
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
        }

        adjustHeap(arr,i-1,0);
    }

}