剑指offer第一周

目录

二维数组中的查找

旋转数组的最小数字

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

数组中出现次数超过一半的数字

替换空格

从尾到头打印链表

重建二叉树

矩形覆盖

链表中倒数最后k个结点

二进制中1的个数

合并两个排序的链表

树的子结构

二叉树的镜像

---

​​​​​​​二维数组中的查找

解法：模拟

        第一种想到的做法是两层for循环来查找，但会超时；

        优化：两层for循环查找本质是一个一个排查，根据题目的行递增与列递增：根据第一行的最大值：第一行的最后一个元素（或者第一列的最后一个）作为参照物：

        如果target比我大，说明target不可能在当前行，往下找；

        如果target比我小，说明target不可能在当前列，往左找；

#include <algorithm>
class Solution
{
public:bool Find(int target, vector<vector<int>> &array){int i = 0, j = array[0].size() - 1;while (i < array.size() && j >= 0){if (array[i][j] < target)i++; // 排除一行else if (array[i][j] > target)j--; // 排除一列elsereturn true;}return false;}
};

旋转数组的最小数字

解法：二分

        数组通过非递减的方式以某个下标为旋转点进行旋转后，此时会分为两段非递减区域：左半段区域的所有值全都大于有半段的所有值，找出单调性（题目要用logn时间）我们就可能尝试使用二分解决：以nums[right]作为参照物(以nums[left]作为操作物情况有n多种)，根据以下动图理解移动逻辑：

//a[right]作为参照物
class Solution
{
public:int minNumberInRotateArray(vector<int> &nums){int left = 0, right = nums.size() - 1;// 要以a[right]为参照物while (left < right){int mid = (left + right) / 2;// mid和right都在右半段且目标值在mid左边if (nums[mid] < nums[right])right = mid;// mid在左半段区间else if (nums[mid] > nums[right])left = mid + 1;// 不知道mid情况,right往后移动缩小范围elseright--;}return nums[left];}
};//以a[left]作为参照物
class Solution
{
public:int minNumberInRotateArray(vector<int> &nums){int left = 0, right = nums.size() - 1;while (left < right){if (left + 1 == right)break; // 这里不判断会死循环int mid = (left + right) / 2;// nums[left] nums[mid] nums[right]三者都相等,只能在该范围内一个一个查找// 例如：[2,2,2,1,2]if (nums[left] == nums[mid] && nums[mid] == nums[right]){int minval = 10001;for (int i = 0; i <= right; i++)minval = min(minval, nums[i]);return minval;}if (nums[left] <= nums[mid])//说明目标值在mid右边left = mid;else//说明目标值在mid左边right = mid;}return min(nums[left], nums[right]);}
};

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

解法1：模拟

创建数组，先枚举奇数统计，再枚举偶数统计

解法2：插入排序

使用插入排序思想：枚举到奇数位置时，把奇数插入到偶数前面

可以直接套用插入排序代码，但是可以将它进行优化：

其中使用k表示：【0，k】区间内已经完成奇数位于偶数前面；假设枚举到i位置，此时它是奇数时，只需移动移动（k，i）区间的偶数整体向前移动一个单位即可；

class Solution
{
public:vector<int> reOrderArray(vector<int> &array){int n = array.size(), k = 0;for (int i = 0; i < n; i++){if (array[i] & 1) // 枚举到奇数时{int tmp = array[i], j = i;//(k,j)未移动while (j > k){array[j] = array[j - 1];j--;}array[k++] = tmp;}}return array;// 下面代码优化：用k表示:[0,k]区间已经移动完成//  int n=array.size(),k=0;//  for(int i=0;i<n;i++)//  {//      if(array[i] & 1)//枚举到奇数时//      {//          int tmp=array[i],j=i;//          //(k,j)未移动//          while(j>k)//          {//              array[j]=array[j-1];//              j--;//          }//          array[k++]=tmp;//      }//  }//  return array;// 插入排序的思想,找奇数前插到偶数前// int n=array.size();// for(int i=0;i<n;i++)// {//     if(array[i] & 1)//枚举到奇数时//     {//         int tmp=array[i],j=i-1;//         while(j>=0)//         {//             if((array[j] & 1) ==0)//偶数往后移//             {//                 array[j+1]=array[j];//                 j--;//             }//             else break;//         }//         array[j+1]=tmp;//     }// }// return array;// vector<int> ret;// for(auto& e:array)// {//     if(e%2!=0) ret.push_back(e);// }// for(auto& e:array)// {//     if(e%2==0) ret.push_back(e);// }// return ret;}
};

数组中出现次数超过一半的数字

（前提：输入数据必有答案，所以次数最多的数字就是答案）

解法1：哈希表

哈希表统计后出现次数最多的数字（时间 O(n) 空间 O(n)）

解法2：排序

排序完后中间的数字就是出现次数最多的数字（时间 O(nlogn) 空间 O(n)）

解法3：候选法

定义变量people为当前候选人，定义变量cnt为1表示当前people人数；进行遍历时如果遇到相等就cnt++，否则就cnt--；当cnt为0时说明当前people一定不是出现次数最多的人（因为次数最多的cnt不会有等于0的情况），重新选择下一个候选人进行遍历..直到枚举结束，当前people即为数组中出现次数最多数字（时间 O(n）空间O(1))

class Solution
{
public:int MoreThanHalfNum_Solution(vector<int> &numbers){int n = numbers.size(), people = numbers[0], cnt = 1, j = 1;while (j < n){if (cnt == 0){people = numbers[j];cnt = 1;j++;}if (people == numbers[j])cnt++;elsecnt--;j++;}return people;}
};

替换空格

解法：模拟

方法1：重新定义一个string：从前往后遍历s：如果遇到空格，就添加"%20"；否则就添加原有字符

方法2：先遍历一遍找出有多少空格（一个空格就多加2个位置的空间），计算string一共需要多少空间，定义两个指针：begin指向原来string的末尾，end指向预留空间的string的末尾；如果s[begin]等于空格，end就要从后往前一次添加‘0’ ‘2’ ‘%’，否则就添加s[begin]的字符

class Solution
{
public:string replaceSpace(string s){int k = 0;for (auto &e : s){if (e == ' ')k++;}int begin = s.size() - 1, length = s.size() + 2 * k;s.resize(length);int end = length - 1;while (end > 0){if (s[begin] == ' '){s[end--] = '0';s[end--] = '2';s[end--] = '%';begin--;}else{s[end--] = s[begin--];}}return s;// string ret;// for(auto& e:s)// {//     if(e==' ') ret+="%20";//     else ret+=e;// }// return ret;}
};

从尾到头打印链表

解法1：模拟

基本链表的头插操作，然后把新链表遍历节点保留在数组中；

解法2：递归

递归到尾节点存值到数组中

class Solution
{
public:vector<int> ret;void dfs(ListNode *head){if (head == nullptr)return;dfs(head->next);ret.push_back(head->val);}vector<int> printListFromTailToHead(ListNode *head){dfs(head);return ret;// ListNode* tmp=new ListNode(-1),*tail=nullptr;// while(head)// {//     ListNode*next=head->next;//     head->next=tail;//     tmp->next=head;//     tail=head;//     head=next;// }// ListNode* head1=tmp->next;// delete tmp;// vector<int> ret;// while(head1)// {//     ret.push_back(head1->val);//     head1=head1->next;// }// return ret;}
};

重建二叉树

解法：递归

重复子问题

通过前序数组的第一个根的值，将中序数组分为左右子树两个区间；

根据中序数组的左子树区间计算出左子树的个数；

通过左子树的个数就可以将前序数组也分为左右子树两个区间；

接下来通过前序数组的第二个根的值再次划分区间...

在划分区间（递归）之前把根的值new出来，等到左右子树通过递归构建好后就return

#include <vector>
class Solution {
public:TreeNode* dfs(vector<int>& pre,int pre_begin,int pre_end,vector<int>& vin,int vin_begin,int vin_end){if(pre_begin>pre_end) return nullptr;TreeNode* root=new TreeNode(pre[pre_begin]);for(int i=vin_begin;i<=vin_end;i++){if(vin[i]==pre[pre_begin]){//找到中序遍历后的根节点，把它划分成左右子树两段区间【vin_begin,i-1】 i 【i+1,vin_end】//前序遍历中左子树节点区间【pre_begin+1, pre_begin+1 + i-1-vin_begin+1(vin左子树的个数)-1】root->left=dfs(pre,pre_begin+1,pre_begin+i-vin_begin,vin,vin_begin,i-1);//前序遍历中左子树节点区间就好计算了root->right=dfs(pre,pre_begin+i-vin_begin+1,pre_end,vin,i+1,vin_end);}}return root;}TreeNode* reConstructBinaryTree(vector<int>& preOrder, vector<int>& vinOrder) {if(preOrder.empty()) return nullptr;return dfs(preOrder,0,preOrder.size()-1,vinOrder,0,vinOrder.size()-1);}
};//前后序重建二叉树
TreeNode* dfs(int prev[], int pre_begin, int pre_end, int after[], int aft_begin, int aft_end)
{if (pre_begin>pre_end) return nullptr;TreeNode* root = new TreeNode(prev[pre_begin]);if (pre_begin == pre_end) return root;//剩下一个直接返回int tmp = prev[pre_begin + 1],leftsize;//通过前序遍历的下一个节点来确定左右子树个数for (int i = aft_begin; i <= aft_end; i++){if (tmp == after[i]){leftsize = i - aft_begin + 1;break;}}root->left = dfs(prev, pre_begin + 1, pre_begin +leftsize, after, aft_begin, aft_begin+leftsize-1);root->right = dfs(prev, pre_begin + leftsize + 1, pre_end, after, aft_begin + leftsize, aft_end - 1);return root;
}//中后序重建二叉树
TreeNode* dfs(int mid[], int mid_begin, int mid_end, int after[], int aft_begin, int aft_end)
{if (mid_begin>mid_end||aft_begin>aft_end) return nullptr;TreeNode* root = new TreeNode(after[aft_end]);int tmp = after[aft_end];//通过前序遍历的下一个节点来确定左右子树个数for (int i = mid_begin; i <= mid_end; i++){if (tmp == mid[i]){root->left = dfs(mid, mid_begin, i - 1, after, aft_begin, aft_begin + i - mid_begin - 1);root->right = dfs(mid, i+1, mid_end, after, aft_begin + i - mid_begin, aft_end - 1);break;}}return root;
}

矩形覆盖

解法：规律

斐波那契数的变形

class Solution
{
public:int rectCover(int number){if (number < 4)return number;int a = 2, b = 3, c;while (number >= 4){c = a + b;a = b;b = c;number--;}return c;}
};

链表中倒数最后k个结点

解法1：模拟

统计节点个数n后从头节点走n-k步就到指定的位置

解法2：前后双指针

它们从头节点开始：先让前指针走k步，再让它们一起走...直到前指针为空停止，返回后指针；如果前指针走不到k步（走到k步）为空，直接返回空

class Solution
{
public:ListNode *FindKthToTail(ListNode *pHead, int k){// 前后指针进行移动ListNode *front = pHead, *rear = pHead;while (k-- && front)front = front->next;// 如果没有倒数第k个节点不进来while (front){front = front->next;rear = rear->next;}return k >= 0 ? front : rear;// 根据节点个数n后走n-k步// ListNode* head=pHead;// int n=0;// while(head)// {//     n++;//     head=head->next;// }// if(n-k<0) return nullptr;// n-=k;// while(n--)// {//     pHead=pHead->next;// }// return pHead;}
};

二进制中1的个数

解法：位运算

n的32位与1 &，为1代表这一位是1

或者 n = n & (n-1) 每进行一次n的最后位数(从左到右)的1被消除

class Solution
{
public:int NumberOf1(int n){int ret = 0;while (n){ret++;n &= (n - 1); // 每次减少二进制的1}// for(int i=0;i<32;i++)// {//     if(1&(n>>i)) ret++;// }return ret;}
};

解法1：三指针

定义三个指针指向节点进行反转移动，有一定的细节

解法2：递归

明白每一层在干什么？ 把后一个的节点的下一个节点指向自己，向上返回尾节点

解法2：头插法

利用带头链表进行插头最简单~

class Solution
{
public:ListNode *ReverseList(ListNode *head){// 三指针// 空或者一个节点不用移动if (head == nullptr || head->next == nullptr)return head;ListNode *prev = head, *mid = head->next, *tail = head->next->next;while (tail){mid->next = prev;prev = mid;mid = tail;tail = tail->next;}// mid在尾节点mid->next = prev;// 头节点的下一个值空head->next = nullptr;return mid;// 递归//  if(head==nullptr || head->next==nullptr) return head;// ListNode*Phead = ReverseList(head->next);// if(head->next) head->next->next=head; //后面节点连接前面节点// head->next=nullptr; //为了第一个节点的下一个置空// return Phead;// 头插法//  ListNode* Phead=new ListNode(-1),*tail=nullptr;//  while(head)//  {//      ListNode* next=head->next;//     head->next=tail;//     Phead->next=head;//     tail=head;//     head=next;// }// ListNode* ret=Phead->next;// delete Phead;// return ret;}
};

合并两个排序的链表

解法1：双指针

从左向右同时遍历两个链表，取小的节点进行尾插后往后走，直到一个或者两个链表为空后直接将另一个链表进行尾插

解法2：递归

递归之前去小的节点放到定义的head节点中，然后往后走，直到一个或者两个链表为空后直接将另一个链表进行尾插

class Solution
{
public:ListNode *Merge(ListNode *pHead1, ListNode *pHead2){// 递归if (pHead1 == nullptr)return pHead2;else if (pHead2 == nullptr)return pHead1;ListNode *head = nullptr; //,*tail=head;if (pHead1->val < pHead2->val){head = pHead1;pHead1 = pHead1->next;}else{head = pHead2;pHead2 = pHead2->next;}head->next = Merge(pHead1, pHead2);return head;// 比较节点大小进行合并超时// if(pHead1==nullptr) return pHead2;// else if(pHead2==nullptr) return pHead1;// ListNode* head=nullptr,*tail=nullptr;// while(pHead1 && pHead2)// {//     if(pHead1->val<=pHead2->val)//     {//         if(head==nullptr) head=tail=pHead1;//         else//         {//             tail->next=pHead1;//             tail=pHead1;//         }//         pHead1=pHead1->next;//     }//     else//     {//         if(head==nullptr) head=tail=pHead2;//         else//         {//             tail->next=pHead2;//             tail=pHead2;//         }//         pHead2=pHead2->next;//     }// }// if(pHead1==nullptr) tail->next=pHead2;// else if(pHead2==nullptr) tail->next=pHead1;// return head;}
};

树的子结构

解法：递归

递归1：找两颗数的头节点是否相同，相同就让一个递归函数IsSame帮助我们判断；

递归2：判断两颗数是否相同采用的是前序遍历思想：先比较头节点，头节点相同就递归比较左右子树，两种情况都为true就表明两颗树是相同的

class Solution
{
public:bool IsSame(TreeNode *root1, TreeNode *root2){// root2为空就说明找到结尾了if (root2 == nullptr)return true;// root1为空就说明在root1中没有root2的节点if (root1 == nullptr)return false;if (root1->val == root2->val)return IsSame(root1->left, root2->left) && IsSame(root1->right, root2->right);elsereturn false;}bool HasSubtree(TreeNode *pRoot1, TreeNode *pRoot2){// 空树不是任意一个树的子结构if (pRoot1 == nullptr || pRoot2 == nullptr)return false;if (pRoot1->val == pRoot2->val){if (IsSame(pRoot1, pRoot2))return true;}return HasSubtree(pRoot1->left, pRoot2) || HasSubtree(pRoot1->right, pRoot2);}
};

二叉树的镜像

解法：递归

前序遍历的思想：从根节点开始，交换左右子树的节点

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

以上便是全部内容，有问题欢迎在评论区指正，感谢观看！