剑指offer刷题笔记（一）

一、数组

3.数组中重复的数字

题目一

题目描述
在一个长度为n的数组里的所有数字都在0到n-1的范围内。数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2
简单解法：

用一个长度为n的check数组，当check[numbers[i]]>0时，表示numers[i]出现过，返回false；否则继续检查，直到遍历完numbers。空间复杂度：O(n),时间复杂度：O(n)

class Solution {
public:
    // Parameters:
    //        numbers:     an array of integers
    //        length:      the length of array numbers
    //        duplication: (Output) the duplicated number in the array number
    // Return value:       true if the input is valid, and there are some duplications in the array number
    //                     otherwise false
    bool duplicate(int numbers[], int length, int* duplication) {
         if(numbers==NULL||length<=0)//判断为空
          return false;
          int *check = new int[length];
        for(int i = 0;i < length;i++)//初始化
        {
            check[i] = 0;
        }
        
        for(int i = 0;i < length;i++)
        {
            if(check[numbers[i]]==1)
            {
                *duplication = numbers[i];
                return true;
                
            }
            check[numbers[i]]++;
        }
        delete[] check;
        return false;
        
    }
};

hash表来存储，空间复杂度：O(n),时间复杂度：O(n)
先排序，再查找。时间复杂度O(nlogn)
最优解法：时间复杂度O(n)
遍历numbers,如果numbers[i]等于i，说明位于自己所在位置，否则

循环判断，直到numbers[i]等于i
- 与i位置上的数字进行比较，如果不等于，则交换

如果相等则得到重复的数字。

    bool duplicate(int numbers[], int length, int* duplication) {
         if(numbers==NULL||length<=0)
          return false;
        for(int i = 0; i < length; i++)
        {
            if(numbers[i] < 0 || numbers[i] > length-1 )
                return false;
        }
        for(int i = 0;i < length; i++)
        {
            
            while(numbers[i] != i)
            {
                int temp = numbers[i];
                if(numbers[i]!=numbers[temp])
                numbers[i] = numbers[temp];
                else
                {
                  *duplication = numbers[temp];
                  return true;
                }
                numbers[temp] = temp;
            }
            
        }
        return false;
    }
};

注意：判断所有的数字是否在合法范围

题目二

在一个长度为n+1的数组里的所有数字都在1到n的范围内，所以数组中至少有一个数字是重复的。请找出数组中任意一个重复的数字，但不能修改输入的数组。例如，如果输入长度为8的数组{2, 3, 5, 4, 3, 2, 6, 7}，那么对应的输出是重复的数字2或者3。

简单解法：

check数组，同题目一空间复杂度：O(n),时间复杂度：O(n)
二分法：

以数m为分界分为两类数组，1~m，m+1~n
分别统计以上两类数字出现的次数，如果任意一类出现的次数超过m（或n-m），则说明重复的数字在那一类中出现
再从出现重复数字的一类中继续以中间数分为两类，重复1、2两步，直到找到重复数字

由于countNum的时间复杂度是O(n)，而且会被调用O(logn)次，所以最终的时间复杂度是O(nlogn)。空间复杂度为O(1)。

class Solution {
public:
    // Parameters:
    //        numbers:     an array of integers
    //        length:      the length of array numbers
    //        duplication: (Output) the duplicated number in the array number
    // Return value:       true if the input is valid, and there are some duplications in the array number
    //                     otherwise false
	int getCount(const int *numbers, int length, int start, int end)
	{
		int count = 0;
		for(auto number :numbers)
		{
			if(number>=start&&number<=end)
			count++;
		}
		return count;
	}
    bool getDuplication(const int* numbers, int length) {
	if (numbers == nullptr || length < 0)
	{
		return -1;
	}
	int start = 1,end = length -1,mid = 0;
	while(start != end)
	{
		mid =(end + start) >> 1;
		if(getCount(numbers, length, start,mid) >(mid - start + 1))//mid会变，不能用mid作为判断条件
		{
			end = mid ;
		}
		else{
			start = middle + 1;
		}
		
		
	}
	
	if (start == end && countNum(numbers, length, start, end ) > 1)
		return start;
	return -1;
    }
};

4. 二维数组中的查找

题目
在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

穷举。时间复杂度O(m*n)
结合折半查找
最优：从右上角比较，如果

如果= target，返回
如果 < target,这一行剔除;
如果 > target,这一列剔除。
时间复杂度O(m+n)

bool Find(int target, vector<vector<int> > array) {
       int rowSize = array.size();
       int colSize = array[0].size();
       int i = 0,j = colSize-1;
       while(i < rowSize && j >=0 )//同时考虑i和j
       {
        if(array[i][j]==target)
        {
            return true;
        }
        else if(array[i][j]< target)
        {
            i++;
        }
        else{
          j--;
        }
       }
   //注意边界问题
    return false;

   }

21. 调整数组顺序使奇数位于偶数前面

题目
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
解法

两个数组存，一个存奇数，一个存偶数，拼接(保证相对顺序)。时间复杂度：O(n);空间复杂度：O(n)
每当遇到一个偶数，把后面的数往前移动一位,然后这个数放到最后面。时间复杂度O(n^2)

前后双指针：一个指针指向第一个，另一个指向最后一个。如果前一个指向偶数，后一个指向奇数，则交换两个数。时间复杂度：O(n)

牛客解法（要求保证相对顺序）
class Solution {
public:
    void reOrderArray(vector<int> &array) {
        if(array.size()==0)
        return ;
        
        vector<int> orderArray;
        for(auto number:array)
        {
            if(number % 2 == 1)
            {
               orderArray.push_back(number);
               
            }
           
            
        }
        for(auto number:array)
        {
            if(number % 2 == 0)
            orderArray.push_back(number);
             
        }
        array =  orderArray;
 
    }
};
剑指offer解法：函数指针
class Solution {
public:
    bool isEven(int num)
    {
       
        return (num & 1) ==0;
    }
    void reOrder(int* array,size_t length,bool(* func)(int))
    {
        int * head,* end;
        head = array;
        end = array +(length - 1);
        while(head < end)
        {
            if(func(*head)!=0)
            head++;
            if(func(*end)==0)
            end--;
            
            if(func(*head)==0&&func(*end)!=0)
            {
                swap(*head,*end);//伪代码，具体实现省略
            }

        }

    }

29. 顺时针打印矩阵

题目
输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下矩阵： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.

我的解法-只适用于方阵
剑指offer；

选取左上角start(startX,startX);
发现只要满足rows > startX 2，colums>startX2,循环满足条件
标准解法

class Solution {
public:

    void printResult(vector<vector<int>>& matrix,int start, int columns,int rows,vector<int>& result)
    {
       int endX = rows - 1 - start;
       int endY = columns - 1 - start;
       for(int j = start;j<=endY;j++)
       {
           result.push_back(matrix[start][j]);
       }
       if(start < endX)
       {
           for(int i = start + 1;i <= endX;i++)
           {
               result.push_back(matrix[i][endY]);
           }
       }
       if(start < endX && start < endY)
       {
           for(int j = endY - 1;j>=start;j-- )
           {
               result.push_back(matrix[endX][j]);
           }
       }
        if(start < endY)
        {
            for(int i = endX -1;i>start;i--)
            {
                result.push_back(matrix[i][start]);
            }
        }

    }
    vector<int> printMatrix(vector<vector<int> > matrix) {
        vector<int> result;
        int columns = matrix[0].size();
        int rows = matrix.size();
        int start = 0;
       while(columns>start*2&&rows>start*2)
       {
           printResult(matrix,start,columns,rows,result);
           start++;
       }
      return result;
    }
};

39. 数组中超过一半的数字

题目
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。
解法：

先排序，再查找。排序时间复杂度：O(n*log(n))
遍历数组，使用一个变量存num，另一个存count. 与下一个数字比较。时间复杂度O(n)，空间复杂度O(1)。

如果相等，count++
如果不等，count–

如果==0，num存放下一个数字
最后，得到一个count>=1的数字和num，遍历数组判断num次数，得到数字。

方法二
class Solution {
public:
    int checkNum(vector<int>& numbers,int num)
    {
        int times = 0;
        for(auto number:numbers)
        {
            if(number==num)
             times++;
        }
        if(times>numbers.size()/2)
         return num;
        else
        return 0;
    }
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        if(numbers.size()<=0)
        return 0;
        
        int num = numbers[0],count=1;
    
        for(int i=0;i<numbers.size()-1;i++)
        {
            if(num!=numbers[i+1])
            {
              count--;
              if(count == 0)
              {
               i++;
               num=numbers[i+1];
               count=1;
              }
            }
            else{
                count++;
                
            }
        }
           return checkNum(numbers,num);

    }
};

快速排序实现

基于Partition函数的时间复杂度为O(n)的算法

关于Partition的实现

实现快速排序的关键，先选中一个，接下来把数组数字分为两部分，比选择小的数字移到数组的左边，比选择数字大的数字移到数组的右边。如下实现
int Partition(int data[], int length, int start, int end)
{
	if(data==nullptr||length<=0||start<0||end>=length)
	throw new std::exception("Invalid Parameters");
	
	int index = RandomInRange(start,end); //生成一个start到end的随机数
	Swap(&data[index],&data[end]);   //把index置于尾部

	int small = start -1;
	for(index=start;index<end;++index)
	{
	if(data[index]<data[end])
	{
		++small
		if(small!=index)
			Swap(&data[index],&data[small]);//把比target小的数字和大的数字交换
	}


}
++small;
Swap(&data[small],&data[end]);//把target和small交换，完成 small|target|big 的排序

return small;  //返回target的位置
}
基于Partition的快排
void QuickSort(int data[],int length,int start,int end)
{
	if(start==end)
	return ;
	int index = Partition(data,length,start,end);
	
	if(index>start)
	QuickSort(data,length,start,index-1);
	if(index<end)
	QuickSort(data,length,index+1,end);
	
}

bool g_bInputInvalid = false;

bool CheckInvalidArray(int* numbers, int length)
{
    g_bInputInvalid = false;
    if(numbers == nullptr && length <= 0)
        g_bInputInvalid = true;

    return g_bInputInvalid;
}

bool CheckMoreThanHalf(int* numbers, int length, int number)
{
    int times = 0;
    for(int i = 0; i < length; ++i)
    {
        if(numbers[i] == number)
            times++;
    }
 
    bool isMoreThanHalf = true;
    if(times * 2 <= length)
    {
        g_bInputInvalid = true;
        isMoreThanHalf = false;
    }

    return isMoreThanHalf;
}

// ====================方法1====================
int MoreThanHalfNum_Solution1(int* numbers, int length)
{
    if(CheckInvalidArray(numbers, length))
        return 0;
 
    int middle = length >> 1;
    int start = 0;
    int end = length - 1;
    int index = Partition(numbers, length, start, end);
    while(index != middle)
    {
        if(index > middle)
        {
            end = index - 1;
            index = Partition(numbers, length, start, end);
        }
        else
        {
            start = index + 1;
            index = Partition(numbers, length, start, end);
        }
    }
 
    int result = numbers[middle];
    if(!CheckMoreThanHalf(numbers, length, result))
        result = 0;

    return result;
}

42. 连续子数组的最大和(动态规划)

题目描述
HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。你会不会被他忽悠住？(子向量的长度至少是1)
解法

找规律法，时间复杂度：O(n)

使用两个变量，一个存放每一步的sum，另一个存放maxSum。每一步考虑
sum < 0 ? sum = array[i] : sum += array[i]
maxSum > sum ? 1 : maxSum = sum
遍历整个数组可得结果

class Solution {
public:
    int FindGreatestSumOfSubArray(vector<int> array) {
       int maxSum = INT_MIN,num = 0;
        for(int i = 0;i<array.size();i++)
        {
            if(num < 0)
            {
                num = array[i];

            }
            else{
                num += array[i];
            }
            if(num > maxSum)
            {
                    maxSum = num;
            }
            
            
        }
    
        return maxSum;
    }
};

动态规划法（与上一方法相同）
51. 数组中的逆序对

解法：
穷举比较时间复杂度O(n^2)
空间换时间（归并排序）时间复杂度：O(n*log(n)),空间复杂度：O(n)
先对数组二分，然后合并的时候排序并统计逆序对的数量。等同于归并排序。
归并排序

int InversePairs(int* data, int length)
{
    if(data == nullptr || length < 0)
        return 0;

    int* copy = new int[length];
    for(int i = 0; i < length; ++i)
        copy[i] = data[i];

    int count = InversePairsCore(data, copy, 0, length - 1);
    delete[] copy;

    return count;
}

int InversePairsCore(int* data, int* copy, int start, int end)
{
    if(start == end)
    {
        copy[start] = data[start];
        return 0;
    }

    int length = (end - start) / 2;

    int left = InversePairsCore(copy, data, start, start + length);
    int right = InversePairsCore(copy, data, start + length + 1, end);

    // i初始化为前半段最后一个数字的下标
    int i = start + length;
    // j初始化为后半段最后一个数字的下标
    int j = end;
    int indexCopy = end;
    int count = 0;
    while(i >= start && j >= start + length + 1)
    {
        if(data[i] > data[j])
        {
            copy[indexCopy--] = data[i--];
            count += j - start - length;
        }
        else
        {
            copy[indexCopy--] = data[j--];
        }
    }

    for(; i >= start; --i)
        copy[indexCopy--] = data[i];

    for(; j >= start + length + 1; --j)
        copy[indexCopy--] = data[j];

    return left + right + count;
}

57. 和为s的数字

和为S的两个数字-题目描述
输入一个递增排序的数组和一个数字S，在数组中查找两个数，他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。
输出描述：对应每个测试案例，输出两个数，小的先输出。
解法：
双指针，一个head从前往后，另一个tail从后往前,遍历数组。

如果array[head] + array[tail] < sum;head++
如果array[head] + array[tail] > sum;tail–
如果相等，有输出条件，则head++,tail–
时间复杂度O(n)

class Solution {
public:
    vector<int> FindNumbersWithSum(vector<int> array,int sum) {
        int head =0,tail =array.size()-1; 
        int mul = INT_MAX;
        vector<int> nums;
        int n1 =0,n2 =0;
        if( array.size() < 2 ||  array[0] >= sum )
            return nums;
        while(head<tail)
        {
            if(array[head]+array[tail] < sum)
            {
                head++;
            }
            else if(array[head]+array[tail] > sum)
            {
                tail--;
            }
            else{
                if(mul >= array[head] * array[tail])
                {
                    mul = array[head]  * array[tail];
                    n1 = array[head];
                    n2 = array[tail];
                }
                head++;
                tail--;
            }
        }
        if(mul == INT_MAX)
        return nums;
        
        nums.push_back(n1);
        nums.push_back(n2);
        return nums;
        
     }
};

66. 构建乘积数组

Alt text
解法：

遍历，对每个B[i]都从头到尾遍历A数组相乘，时间复杂度：O(n^2)
递归解法

从B[0]到B[1],推广到B[0]到B[n-1]
每一趟迭代B[i]并计算sum值
因为B[end]=sum;B[i]‘=B[i]*A[end]，时间复杂度:O(n*log(n))

class Solution {
public:
    void mul(const vector<int>& A,vector<int>& B,int start,int end,int& sum)
    {
        if(end - start > 1)
        {
            mul(A,B,start,end - 1,sum);
            B.push_back(sum);
            for(int i = start;i<end;i++)
            {   
               
                B[i]=A[end]*B[i];
            }
            sum = sum * A[end];
        }
        else{
            B.push_back(A[end]);
            B.push_back(A[start]);
            sum = A[start]*A[end];
        }
        
        
    }
    vector<int> multiply(const vector<int>& A) {
    int arraySize = A.size();
    int start = 0;
    int end = arraySize-1;
    int sum = 0;
    vector<int> B;
    if(arraySize < 1)
    return B;
        
   mul( A,B,start,end,sum);
        return B;
    }
};

构建矩阵求解

把B[i]看成A[0] A[1] … A[i-1]和A[i+1] … *A[n-1]

void BuildProductionArray(const vector<double>& input, vector<double>& output)
{
    int length1 = input.size();
    int length2 = output.size();

    if(length1 == length2 && length2 > 1)
    {
        output[0] = 1;
        for(int i = 1; i < length1; ++i)
        {
            output[i] = output[i - 1] * input[i - 1];
        }

        double temp = 1;
        for(int i = length1 - 2; i >= 0; --i)
        {
            temp *= input[i + 1];
            output[i] *= temp;
        }
    }
}

二、字符串

5. 替换空格

Alt text

不要使用辅助数组，因为传入的是*str，也就是指针，只能修改指针所指的内容，如果想修改指针指向哪里，就必须传入的是**str，即指针的指针。

解法:
双指针:时间复杂度O(n)
先计算出空格数量，然后p2指向预计的最后位置，p1指向初始结尾。如果p1遇到空格，复制%20到p2的位置，否则正常复制，直到p1==p2
Alt text

class Solution {
public:
	void replaceSpace(char *str,int length) {
        int newLength = 0,spaceCount = 0;
        for(int i=0;i<=length;i++)
        {
            if(str[i]==' ')
            spaceCount++;
            
        }
        newLength = length + spaceCount*2;
        char *p1 =&str[length],*p2 =&str[newLength];
        while(p1!=p2)
        {
           if(*p1==' ')
           {
             *p2='0';
              p2--;
             *p2='2';
              p2--;
             *p2='%';
              p2--;
           }
           else{
               *p2 = *p1;
               p2--;
           }
            p1--;
        }

	}
};

20. 表示数值的字符串

三、链表

6. 从尾到头打印链表

Alt text
解法

使用栈,顺序push,然后pop打印。时间复杂度O(n),空间复杂度O(n)。(空间占用过多)

递归实现。时间复杂度O(n)

class Solution {
public:
    void print(ListNode* cursor,vector<int>& results)
    {
        if(cursor!=nullptr)
        {
            if(cursor->next!=nullptr)
              print(cursor->next,results);
            
            results.push_back(cursor->val);     
        }
    }
    vector<int> printListFromTailToHead(ListNode* head) {
        vector<int> results;
        ListNode* cursor = head;
        if(head ==nullptr)
            return results;
        
        print(cursor,results);
        return results;
    }
};

18. 删除链表的节点

题目一

Alt text
解法

把要删除节点的后一个节点的值赋值到当前节点，然后删除后一个节点。
考虑节点是头结点和尾节点的情况

时间复杂度O(1)

ListNode* deleteDuplication(ListNode* pHead,ListNode* cursor)
{
	if(cursor->next!=nullptr)
	{
		ListNode* p = cursor->next;
		cursor->val = cursor->next->val
		cursor->next = p->next;
		delete p;
		p = nullptr;
		return pHead;
	}
	else if(phead == cursor)
	{
		delete phead;
		phead =nullptr;
	}
	else{
		ListNode* p = phead;
		while(p->next!=cursor)
		{
		p = p->next;
		}
		p->next = nullptr;
		delete cursor;
		cursor = nullptr;
		
	}
		
}

题目二-

Alt text

三个指针：pPreNode->前一个节点，pNode->当前节点，pNext->下一个节点
如果pNode->val == pNext->val,设置Flag == true
如果 Flag == true，那么设置delNode = pNode,delvalue = pNode->val

直到删除所有重复节点，注意考虑pPreNode == nullptr,pNode = pHead

ListNode* deleteDuplication(ListNode* pHead)
   {
       if(pHead == nullptr||pHead->next== nullptr)
        return pHead;
       ListNode* pPreNode = nullptr,* pNode = pHead;
       while(pNode!=nullptr)
       {
           bool delFlag = false;
           ListNode* pNext = pNode->next;
           if(pNext!=nullptr&&pNode->val==pNext->val)
             delFlag = true;
           
           if(delFlag == false)
           {
               pPreNode = pNode;
               pNode = pNext;
           }
           else{
               int delvalue = pNode->val;
               ListNode* delNode = pNode;
               while(delNode!=nullptr&&delNode->val==delvalue)
               {
                     pNext = delNode->next;
                     delete delNode;
                     delNode = nullptr;
                     delNode = pNext;
               }
           }
               if(pPreNode == nullptr)
                  pHead = pNext;
               else
                  pPreNode->next = pNext;
           
               pNode = pNext;
              
           
           
       }
       return pHead;
       
   }

22. 链表中倒数第k个节点

Alt text

遍历链表获得长度，然后让pointer走n-k+1步（需要遍历两次链表）时间复杂度O(n^2)

双指针:前后距离为k-1,当后一个pointer走到尾部，返回前一个指针时间复杂度O(n)

注意：k <1,head ==nullptr 和k>链表size三情况返回nullptr。

解法2
  ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
            if( pListHead == nullptr || k == 0 )
            return nullptr;
            ListNode* preNode = nullptr,*Node = pListHead;
            for(unsigned int i = 0;i < k - 1;++i)
            {
                if(Node->next!=nullptr)
                Node = Node->next;
                else
                    return nullptr;
            }
        
           preNode = pListHead;
            while(Node->next!=nullptr)
            {
                Node = Node->next;
                preNode = preNode->next;
            }
            
            return preNode;
    
    }

23. 链表中环的入口节点

Alt text
分两部分：

判断是否有环

快慢指针:两个指针指向head，一个走1步，一个走2步，如果相遇则证明有环。
差值为环上节点个数k

判断入口节点

双指针：前后距离为k，同步推进，直到相遇，相遇的节点即为环的入口。

class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead)
    {
        if(pHead == nullptr)
            return nullptr;
        ListNode* fast = pHead,* slow = pHead;
        int count = 0;
        while(fast->next!=nullptr&&fast->next->next!=nullptr)
        {
            fast = fast->next->next;
            slow = slow->next;
            count++;
            if(fast == slow)
            {
                ListNode* prev = pHead,*node = pHead;
                for(int i = 0;i < count;i++)
                {
                    node = node->next;
                }
                while(node!=prev)
                {
                    node=node->next;
                    prev = prev->next;
                    
                }
                return node;
            }
            
        }
        return nullptr;

    }
};

24. 反转链表

Alt text
解法
三指针法：

判断是否head为空或者只有head
prev指向nullptr，current指向head，forward指向head->next
遍历list
- current->next = prev;prev =current;current=forward;

最后current->next=prev;forward->next = current;

class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        if(pHead==nullptr||pHead->next==nullptr)
         return pHead;

        ListNode* prev =nullptr ,*current =pHead,*forward = pHead->next;
        for(;forward->next!=nullptr;forward=forward->next)
        {
            current->next = prev;
            prev = current;
            current = forward;
        }
        current->next = prev;
        forward->next = current;
        
        return forward;
        
        
    }
};

25. 合并两个排序的链表

Alt text

递归解法

class Solution {
public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
    {
        if(pHead1==nullptr)
            return pHead2;
        if(pHead2==nullptr)
            return pHead1;
        ListNode* merge = nullptr;
        if(pHead1->val<pHead2->val)
        {
            merge = pHead1;
            merge->next = Merge(merge->next,pHead2);
        }
         else
        {
            merge = pHead2;
            merge->next = Merge(pHead1,merge->next);
        }
        return merge;
    }
};

35. 复杂链表的复制

题目描述：
输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）
解法：

暴力法解法

首先遍历一遍复制链表
然后复制random指针，每一次复制都必须从头遍历。
时间复杂度：O(n^2)

利用hash表存储映射信息

遍历复制链表的时候使用hashtable存储<N,N’>的对应信息
根据信息复制random指针
时间复杂度：O(n)，空间复杂度O(n)

巧妙解法

遍历链表在Node n后面复制n‘
遍历链表复制random指针
拆分链表
时间复杂度：O(n)

class Solution {
public:
    RandomListNode* Clone(RandomListNode* pHead)
    {
        if(pHead==nullptr)
           return nullptr;
        RandomListNode* cursor = pHead;
        //1. 复制节点到原节点后面
        while(cursor != nullptr)
        {
            RandomListNode* copyCursor = new RandomListNode(cursor->label);
            copyCursor->next = cursor->next;
            cursor->next = copyCursor;
            cursor = copyCursor->next;
        }
        //2. 定位random
        cursor = pHead;
        //RandomListNode* copyCursor = pHead->next;
        
        while(cursor!=nullptr)
        {
            RandomListNode* copyCursor = cursor->next;
            if(cursor->random != nullptr)
            copyCursor->random = cursor->random->next;
            
            cursor = copyCursor->next;
        }
        
        //3. 拆分链表
        cursor = pHead;
 
        RandomListNode* copyHead = pHead->next;
        while(cursor!=nullptr)
        {
            RandomListNode* copyCursor = cursor->next;
            cursor->next = copyCursor->next;
            cursor = cursor->next;
            if(cursor!=nullptr)
            copyCursor->next = cursor->next;
            else
            copyCursor->next = nullptr;
        }
        
        return copyHead;
        
        
        
        
        
    }
};

53. 两个链表的第一个公共节点

题目描述
输入两个链表，找出它们的第一个公共结点。
解法
考虑问题

从头到尾找？还是从尾到头找？
单链表从尾到头怎么找？考虑时间复杂度和空间复杂度？
解决问题
从尾到头找。
对于list m，list n。利用stack模拟从尾到头遍历，时间复杂度和空间复杂度O(m + n)。
然后遍历栈，寻找第一个不同的元素，前一个被pop的就是公共节点。
遍历的时间复杂度O(k),k为公共节点数+1

四、树

7. 重建二叉树++

递归解法

class Solution {
public:
    TreeNode* Construct(vector<int>& pre,vector<int>& vin,int preStart,int preEnd,int vinStart,int vinEnd)
    {
        int rootValue = pre[preStart];
        TreeNode* root = new TreeNode(rootValue);
        if(preStart==preEnd)
        {
        if(vinStart==vinEnd&&pre[preStart]==vin[vinStart])
            return root; 
        }
        int rootInOrder = vinStart;
        while(rootInOrder<=vinEnd&&vin[rootInOrder]!=rootValue)
        {
            rootInOrder++;
        }
        int leftLength = rootInOrder - vinStart;
        int leftPreEnd = preStart + leftLength;
        if(leftLength > 0)
        root->left =Construct(pre,vin,preStart+1,leftPreEnd,vinStart,rootInOrder-1);
        if(leftLength < preEnd - preStart)
        root->right = Construct(pre,vin,leftPreEnd+1,preEnd,rootInOrder+1,vinEnd);
        
        return root;
    }
    
    
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin)
    {
        if(pre.size()==0||vin.size()==0)
        return nullptr;
        
        return Construct(pre,vin,0,pre.size()-1,0,vin.size()-1);
    }
};

8. 二叉树的下一个节点+

Alt text
解法：

首先判断Node是否有right节点
- 如果有，一直向left查找是否有left节点，返回最left的节点
- 如果没有返回right节点
判断是否是root节点

如果是返回nullptr

3. 双指针：

current指向当前node，parent指向parent node
如果parent!=nullptr且current==parent->right，则一直向上遍历
否则跳出循环返回parent节点

class Solution {
public:
    TreeLinkNode* GetNext(TreeLinkNode* pNode)
    {
        TreeLinkNode* nextNode = nullptr;
        if(pNode->right!=nullptr)
        {
            TreeLinkNode* cursor = pNode->right;
            while(cursor->left!=nullptr)
            {
                cursor = cursor->left;
                
            }
            return cursor;
            
        }
        else if(pNode->next!=nullptr){ 
               TreeLinkNode* current = pNode;
               TreeLinkNode* parent = pNode->next;
                   while(parent!=nullptr&&current==parent->right)
                   {
                       current = parent;
                       parent = parent->next; 
                   }
            nextNode = parent;
        }
        return nextNode;
        
    }
};

26. 树的子结构+

Alt text
解法:双重递归

首先查找val相等的节点。

从这个node对比t1和t2是否为同一子树
如果t2==nullptr，(说明t2已经遍历完成，证明t2是t1的子结构
如果t2!=nullptr&&t1==nullptr,说明(t2的节点t1没有，则返回false)
如果两个节点val不相等，也返回false
然后递归比较left和right

如果子树判断不相等，则继续比较t1->left和t2已经t1->right和t2

bool doesT1HaveT2(TreeNode*pRoot1,TreeNode* pRoot2)
   {
       if(pRoot2==nullptr)
         return true;
       if(pRoot1==nullptr)
         return false;
       if(pRoot1->val!=pRoot2->val)
         return false;
       
       return doesT1HaveT2(pRoot1->left,pRoot2->left)&&doesT1HaveT2(pRoot1->right,pRoot2->right);
       
   }
   
   bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2)
   {
     bool result = false;
       
     if(pRoot1!=nullptr&&pRoot2!=nullptr)
     {
        if(pRoot1->val==pRoot2->val) 
        {
            result = doesT1HaveT2(pRoot1,pRoot2);
        }
         if(!result)
            result = HasSubtree(pRoot1->left,pRoot2);
         if(!result)
            result = HasSubtree(pRoot1->right,pRoot2);
     }
       return result;

   }

27. 二叉树的镜像

题目：完成一个函数，输入一棵二叉树，该函数输出它的镜像。
解法:
递归

判断是否nullptr或单节点，是则返回
交换left和right
遍历Tree

class Solution {
public:
   
    void Mirror(TreeNode *pRoot) {
        if(pRoot == nullptr)
            return;
        if(pRoot->left==nullptr&&pRoot->right==nullptr)
            return;
        
        
        TreeNode* temp;
        
        temp = pRoot->left;
        pRoot->left = pRoot->right;
        pRoot->right = temp;
        
        Mirror(pRoot->left);
        Mirror(pRoot->right);    

    }
};

28. 对称的二叉树

Alt text
解法:

使用对称的先序遍历，判断是否为对称二叉树

class Solution {
public:
    bool isSymTree(TreeNode* t1,TreeNode* t2)
    {
        if((t1==nullptr)&&(t2==nullptr))
            return true;
        if(t1==nullptr||t2==nullptr)
            return false;
        if(t1->val!=t2->val)
            return false;
        
            return isSymTree(t1->left,t2->right)&&isSymTree(t1->right,t2->left);
        
    }
    bool isSymmetrical(TreeNode* pRoot)
    {
        bool result = false;
        if(pRoot==nullptr||(pRoot->left==nullptr&&pRoot->right==nullptr))
        {
            return true;
        }
        if(pRoot->left!=nullptr&&pRoot->right!=nullptr)
        {
            result = isSymTree(pRoot->left,pRoot->right);
        }
        else{
            return false;
        }
        return result;
    
    }

};

32. 从上到下打印二叉树(层序遍历)

Alt text
1.使用queue

先把root放入queue
然后每次把front节点的left和right放入queue
pop front节点，放入vector，直到queue为空
最后返回vector

class Solution {
public:
    vector<int> PrintFromTopToBottom(TreeNode* root) {
        vector<int> result;
        queue<TreeNode*> nodeQueue;
           if(root==nullptr)
            return result;
        nodeQueue.push(root);
        while(!nodeQueue.empty())
        {
            TreeNode* cursor = nodeQueue.front();
            if(cursor->left!=nullptr)
                nodeQueue.push(cursor->left);
            if(cursor->right!=nullptr)
                nodeQueue.push(cursor->right);
            result.push_back(cursor->val);
            nodeQueue.pop();
           
        }
        return result;
        
        

    }
};

33. 二叉搜索树的后序遍历序列

Alt text

1.我的解法

首先空树返回 false
然后计算从与root相比大小的跳变次数进行计数
对于大的子树在小的子树前面的情况要首先排除
如果跳变次数大于1则为false

时间复杂度O(n)

class Solution {
public:
    bool VerifySquenceOfBST(vector<int> sequence) {
        if(sequence.size()==0)
            return false;
        int root = sequence[sequence.size()-1];
        int flagCount = 0;
        for(int i=0;i<sequence.size()-1;i+=1)
        {
            if((sequence[i]-root)>0&&(sequence[i+1]-root)<0)
                return false;
            if((sequence[i]-root)*(sequence[i+1]-root)<0)
            {
                  flagCount++;
            }
            
        }

        if(flagCount>1)
            return false;
        else
            return true;
        
    }
};

offer解法

bool VerifySquenceOfBST(int sequence[], int length)
{
    if(sequence == nullptr || length <= 0)
        return false;

    int root = sequence[length - 1];

    // 在二叉搜索树中左子树的结点小于根结点
    int i = 0;
    for(; i < length - 1; ++ i)
    {
        if(sequence[i] > root)
            break;
    }
    // i = 左侧最大的小于root节点
    // 在二叉搜索树中右子树的结点大于根结点
    int j = i;
    for(; j < length - 1; ++ j)
    {
        if(sequence[j] < root)
            return false;
    }
 // j = 末尾root前一个节点
    // 判断左子树是不是二叉搜索树
    bool left = true;
    if(i > 0)
        left = VerifySquenceOfBST(sequence, i);

    // 判断右子树是不是二叉搜索树
    bool right = true;
    if(i < length - 1)
        right = VerifySquenceOfBST(sequence + i, length - i - 1);

    return (left && right);
}

34. 二叉树中和为某一值的路径

题目描述
输入一颗二叉树的跟节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前)
解法
1.考虑问题

以叶子节点为终点，判断是否是一条符合要求路径。递归可以实现回溯
保存一个路径长度，考虑回溯要剪短路径长度

前序遍历可以满足遍历，使用递归解法。

class Solution {
public:
    static bool myCompare(const vector<int>& a1,const vector<int>& a2)
	{
    return a1.size() >= a2.size();
	}
	void findPathCore(TreeNode* cursor,int expect,vector<vector<int>>& results,vector<int>& path,int& pathSum)
	{
        path.push_back(cursor->val);
		pathSum += cursor->val;
        
		if(cursor->left==nullptr&&cursor->right==nullptr)
		{
		   if(pathSum == expect)
		   results.push_back(path);
		 //  return ;
		}
		
		if(cursor->left!=nullptr)
		findPathCore(cursor->left,expect,results,path,pathSum);
		if(cursor->right!=nullptr)
		findPathCore(cursor->right,expect,results,path,pathSum);	
		
        path.pop_back();
        pathSum -= cursor->val;
	}
    vector<vector<int> > FindPath(TreeNode* root,int expectNumber) {
        vector<vector<int>> results;
		vector<int> path;
		int pathSum = 0;
		if(root==nullptr)
		return results;
	
		TreeNode* cursor = root;
		
		findPathCore(cursor,expectNumber,results,path,pathSum);

	//	sort(results.begin(),results.end(),myCompare);
        return results;

    }
};

40. 最小的k个数（Top k问题）**

题目描述
输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。

提示：在STL中，set和multiset都是基于红黑树实现的。
解法分析：

最直接的方法
先排序（O(nlogn)）,然后取前k个数
基于Partition的方法（不借助辅助空间）

相当于对于第k个数，左边都是小于k的数，右边都是大于k的数。
时间复杂度O(n)
限制：需要修改数组，如果不能修改怎么办？

时间复杂度为O(logk)的算法（适合海量数据）

首先创建一个大小为k的容器存储最小的k个数字
考虑如果容器没满
1. 从数组中读一个数T放在容器
考虑如果容器满了
1. 在容器里找最大的数S
2. 如果T > S则不操作，如果T < S则删除S并插入T

考虑使用什么数据结构作为容器（从CRUD的角度考虑）

最大堆（查找最大值O(1),插入和删除O(logk)）

红黑树（查询，插入和删除O(logk)）

解法一
class Solution {
public:
    int Random(int start,int end)
    {
        default_random_engine e;
        uniform_int_distribution<int> u(start,end);
        return u(e);
        
    }
    void Swap(int& a,int& b)
    {
        int temp = b;
        b = a;
        a = temp;
        
    }  
    int Partition(vector<int>& input,int start,int end)
    {
        int index = Random(start,end);
        
        Swap(input[index],input[end]);
        int small = start - 1;
        for(index = start;index < end;index++)
        {
            if(input[index]<input[end])
            {
                
                small++;
                if(index!=small)
                 Swap(input[index],input[small]);
        
            }
            
            
            
        }
        
        Swap(input[++small],input[end]);
        return small;
    }
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        vector<int> result;
        if(input.size()==0||k <= 0||k>input.size())
        {
            return result;
        }
        
        int start = 0;
        int end = input.size() - 1;
        int index = Partition(input,start,end);
        
        while(index!=k-1)
        {
            if(index < k-1)
            {
                start = index + 1;
                index = Partition(input,start,end);
            }
            else
            {
                end = index - 1;
                index = Partition(input,start,end);
                
            }
            
            
        }
        
        for(int i = 0;i < k;i++)
        {
            result.push_back(input[i]);
        }
        return result;
            
    }
};

解法二：利用红黑树的查询，插入，删除特性。从海量数据中处理topk问题
class Solution {
public:
    typedef    multiset<int,std::greater<int>>  greaterSet;
    typedef    multiset<int,std::greater<int>>::iterator setIterator;
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        
        
         vector<int> result;
         greaterSet leastNumbersSet;
         leastNumbersSet.clear();
        if(input.size()==0||k <= 0||k>input.size())
        {
            return result;
        }
        
        for(auto iter = input.begin();iter < input.end();iter++)
        {
            if(leastNumbersSet.size()<k)
            {
                leastNumbersSet.insert(*iter);
                
            }
            else{
                setIterator sIter = leastNumbersSet.begin();
                if(*sIter > *iter)
                {
                    leastNumbersSet.erase(sIter);
                    leastNumbersSet.insert(*iter);
                }
                
            }
        }
        
        
        for(setIterator iter = leastNumbersSet.begin();iter!=leastNumbersSet.end();iter++)
        {
            result.push_back(*iter);
        }
        
        return result;
        
        
        
    }
};

五. 栈和队列

通常栈不需要考虑排序问题，所以一般要查找最大或者最小元素时需要O(n)的时间复杂度,但是经过改造可以在O(1)时间查找最大和最小。

9. 用两个栈实现队列

Alt text

使用两个栈模拟队列

push()

元素都放入stack1中

pop()

考虑两种情况
如果stack2为空，那么把stack1全部元素放到stack2中,输出栈顶，stack2.pop()
如果stack2不为空，那么直接输出栈顶，stack2.pop()

Alt text

class Solution
{
public:
    void push(int node) {
        stack1.push(node);
        
    }

    int pop() {\
        if(stack2.empty())
        {
            while(!stack1.empty())
            {
                int element = stack1.top();
                stack2.push(element);
                stack1.pop();
            }
        }
        
       int result = stack2.top();
       stack2.pop();
       return result;
            
       
    }

private:
    stack<int> stack1;
    stack<int> stack2;
};

30. 包含min函数的栈（最小栈）

Alt text
借助一个辅助栈(空间换时间)
每次push的时候比较辅助stack栈顶和value的大小，如果value<stack2.top;push value到stack2的栈顶，否则把top再push一遍
。每次pop时候，两个stack同时pop。

class Solution {
public:
    void push(int value) {
        if(stack2.empty()||stack2.top()>value)
        {
            stack2.push(value);
        }
        else{
            stack2.push(stack2.top());
        }
        stack1.push(value);
        
        
    }
    void pop() {
        stack2.pop();
        stack1.pop();
        
    }
    int top() {
        return stack1.top();
    }
    int min() {
        return stack2.top();
        
    }
 private:   
    stack<int> stack1;
    stack<int> stack2;
   
};

31. 栈的压入、弹出序列

Alt text
方法:

借助一个辅助栈，两个指针

如果push数组指针对应的不等于pop数组对应的，则压入stack。
如果相等，同时推进两个指针，直到push数组遍历完成。

然后对应pop数组遍历，和stack的top比较，

如果不等返回false
如果相等继续遍历

最后判断stack是否为空。如果不为空，返回false。为空返回true。

class Solution {
public:
    bool IsPopOrder(vector<int> pushV,vector<int> popV) {
        stack<int> tempStack;
        if(pushV.size()==0)
            return false;
       int pushCursor = 0,popCursor=0;
        while(pushCursor < pushV.size())
        {
            if(pushV[pushCursor]!=popV[popCursor])
            {
                tempStack.push(pushV[pushCursor]);
            }
            else{
                popCursor++;

            }
             pushCursor++;
            
        }
        while(popCursor < popV.size())
        {
            if(tempStack.top()!=popV[popCursor])
            {
                return false;
            }
            popCursor++;
            tempStack.pop();
        }
        
        if(!tempStack.empty())
         return false;
        else
        return true;
        
      
    }
};

六、其他

16. 数值的整数次方

Alt text
我的解法

class Solution {
public:
    double Power(double base, int exponent) {
        double result = 0;
        if(exponent==0)
        {
         result = 1.0;
         return result;
        }  
        else
        {
            result = base;
            for(int i=0;i<abs(exponent)-1;i++)
            {
                
                
               result*=base;
            }
            
            
        }
        if(exponent<0)
        {
            result = 1 / result ;
        }
        else{
            result = result * 1;
        }
        return result;
    }
};

递归解法

class Solution {
public:
    double Power(double base, int exponent) {
        if(exponent == 0 )
          return 1;
        if(exponent == 1)
          return base;
        
        double result = Power(base,exponent>>1);
        result *= result;
        if(exponent&0x1 == 1)
        result *= base;
        
        return result;
    
    }
};

七、递归和循环

10. 斐波那契数列(青蛙跳台阶)

题目一

Alt text

递归

int fib(int n)
{
	if(n == 0)
	return 0;
	if(n == 1)
    return 1;
    
  return fib(n-1)+fib(n-2);
}

循环

 long long Fibonacci_Solution2(unsigned n)
{
    int result[2] = {0, 1};
    if(n < 2)
        return result[n];

    long long  fibNMinusOne = 1;
    long long  fibNMinusTwo = 0;
    long long  fibN = 0;
    for(unsigned int i = 2; i <= n; ++ i)
    {
        fibN = fibNMinusOne + fibNMinusTwo;

        fibNMinusTwo = fibNMinusOne;
        fibNMinusOne = fibN;
    }

     return fibN;
}

题目二

Alt text
想法是青蛙一次可以跳一步，也可以跳两步。
那么就是跳一步和f(n-1)；跳两步和f(n-2)。
和斐波那契同理。

class Solution {
public:
    int jumpFloor(int number) {
        int count = 0;
        if(number == 0)
        return 0;
        if(number == 1)
          return 1;
        else if(number == 2)
          return 2;
        else 
        {
      count = jumpFloor(number-1) + jumpFloor(number-2);
        }   
       return count;
    }
};

题目三

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

返回2^(n-1)

class Solution {
public:
    int jumpFloorII(int number) {
        int count = 1;
        if(number ==0)
         return 0;
        else 
        {
        for(int i =1;i<number;i++)
        {
            count = count <<1;
        }
        }
        
        return count;
    }
};

八、位运算

15. 二进制中1的个数

九、回溯法

12. 矩阵中的路径

题目描述
请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则之后不能再次进入这个格子。例如 a b c e s f c s a d e e 这样的3 X 4 矩阵中包含一条字符串”bcced”的路径，但是矩阵中不包含”abcb”路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。
解法
考虑两个问题

走错路怎么办（即matrix[row*cols+col]==str[pathLength]但是它的上下左右没有找到符合str[pathLength+1]的点）
避免走重复路（用一个visited[]数组，标记走过的路，如果为true表明已经走过且符合要求，不能重复走）
回溯法
如果matrix[row*cols+col]==str[pathLength]说明当前位于str对应的位置上，考虑上下左右四个方向走pathLength+1的方向
当str[pathLength]=='\0'时，说明已经找到最终位置，开始返回true。

class Solution {
public:
    bool hasPathCore(char* matrix,int rows,int cols,int row,int col,char* str,int& pathLength,bool* visited)
    {
        if(str[pathLength]=='\0')
            return true;
        bool hasPath = false;
        if(row>=0&&row<rows&&col>=0&&col<cols&&matrix[row*cols+col]==str[pathLength]&&!visited[row*cols+col])
        {
            pathLength++;
            visited[row*cols+col] = true;
            hasPath = hasPathCore(matrix,rows,cols,row-1,col,str,pathLength,visited)
                ||hasPathCore(matrix,rows,cols,row+1,col,str,pathLength,visited)
                ||hasPathCore(matrix,rows,cols,row,col-1,str,pathLength,visited)
                ||hasPathCore(matrix,rows,cols,row,col+1,str,pathLength,visited);
            
            if(!hasPath)
            {
                pathLength--;
                visited[row*cols+col] = false;
            }
            
            
            
        }
        return hasPath;
        
        
    }
    bool hasPath(char* matrix, int rows, int cols, char* str)
    {
        if(matrix==nullptr||rows<1||cols<1||str==nullptr)
           return false;
        
        bool* visited = new bool[rows * cols];
        int pathLength = 0;
        memset(visited,false,rows * cols);
        
        for(int row = 0;row < rows;row++)
        {
            for(int col = 0;col < cols;col++)
            {
                if(hasPathCore(matrix,rows,cols,row,col,str,pathLength,visited))
                   return true;
            }
        }
        
        delete[] visited;
        return false;
    
    }


};

剑指offer刷题笔记（一）

剑指offer刷题笔记（一）