老猫轩仔的博客 -

题目描述给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。此外，你可以假设该网格的四条边均被水包围。示例 1：输入：grid = [ ["1","1","1","1","0"], ["1","1","0","1","0"], ["1","1","0","0","0"], ["0","0","0","0","0"] ] 输出：1 示例 2：输入：grid = [ ["1","1","0","0","0"], ["1","1","0","0","0"], ["0","0","1","0","0"], ["0","0","0","1","1"] ] 输出：3 提示： m == grid.length n == grid[i].length 1 <= m, n <= 300 grid[i][j] 的值为 '0' 或 '1' 解题思路这道题主要考察对DFS的掌握。这道题中如果陆地能相连，也就是上下左右位如果为'1'，那么就属于一个岛屿，那么我们就需要遍历所有的位置，根据未经访问的陆地点的数量来判断到底有多少个岛屿。对于每一个位置，我们都需要访问同属于一个岛屿的位置。我们可以使用一个visited数组来记录该陆地是否被访问过，如果该陆地已经被访问过，就打上标记，来避免不必要的重复。那么我们的一个重点就是对于每一个点，如果递归的标记同属于一个岛屿的陆地。这时候我们需要借鉴一下对树的遍历方法。首先，需要定义递归的出口。在树的遍历中，结点为空为出口；那么，我们可以定义所访问的点(i,j)不在grid中时为出口。在树的遍历中，我们需要依次遍历树的左右结点；那么，在这道题中，我们就需要遍历(i,j)点的上下左右四个位置。根据算法思路，我们可以得到相应的代码。 PS：这道题也可以通过并查集来进行求解，但是DFS的方法更为常用。示例代码 void DFS(vector<vector<char>>&grid,vector<vector<bool>>&visited,int i,int j) { if(i<0||j<0||i>=grid.size()||j>=grid[0].size()) return; if(grid[i][j]=='1'&&visited[i][j]==false) { visited[i][j]=true; DFS(grid,visited,i-1,j); DFS(grid,visited,i+1,j); DFS(grid,visited,i,j-1); DFS(grid,visited,i,j+1); } } int numIslands(vector<vector<char>>& grid) { vector<vector<bool>>visited(grid.size(),vector<bool>(grid[0].size(),false)); int res=0; for(int i=0;i<grid.size();++i) { for(int j=0;j<grid[0].size();++j) { if(!visited[i][j]&&grid[i][j]=='1') res++; DFS(grid,visited,i,j); } } return res; }

2021年4月17日 0Comments 8Browse 1Like agedcat_xuanzai Read more

题目描述整数数组 nums 按升序排列，数组中的值互不相同。在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标从 0 开始计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。给你旋转后的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。示例 1：输入：nums = [4,5,6,7,0,1,2], target = 0 输出：4 示例 2：输入：nums = [4,5,6,7,0,1,2], target = 3 输出：-1 示例 3：输入：nums = [1], target = 0 输出：-1 提示： 1 <= nums.length <= 5000 -10^4 <= nums[i] <= 10^4 nums 中的每个值都独一无二题目数据保证 nums 在预先未知的某个下标上进行了旋转 -10^4 <= target <= 10^4 解题思路这道题一看按升序排列，就首先想到了二分法。但是其中有部分连续序列是经过旋转处理的，整体就不再是有序的了，那么我们还能使用二分法么？答案是肯定的（不行也要创造条件上！）。这道题的一个难点就是得观察得出：当整个序列从mid出分为两部分后，总有一部分是有序的。据此，我们考虑使用二分法来解答这道题。具体的过程如下：如果左半部分有序如果target处于左半部分中，那么只需在左半部分中二分查找；如果target不在左半部分中，那么在后半部分查找即可；如果后半部分有序如果target处于右半部分中，那么只需在右半部分中二分查找；如果target不在右半部分中，那么在左半部分查找即可。根据思路，我们可以得出相应的代码。示例代码递归版本 int research_run(vector<int>&nums,int target,int left,int right) { int mid=(left+right)/2; if(target==nums[mid]) return mid; if(left==right&&nums[left]!=target) return -1; if(nums[left]<nums[mid]) { if(nums[left]<=target&&target<=nums[mid]) { return research_run(nums,target,left,mid-1); } else{ return research_run(nums,target,mid+1,right); } } else{ if(nums[mid]<=target&&target<=nums[right]) { return research_run(nums,target,mid+1,right); } else{ return research_run(nums,target,left,mid-1); } } } int search(vector<int>&nums,int target) { return research_run(nums,target,0,nums.size()-1); } 这个版本在本地IDE显示答案正确，但是提交显示超时。所以，对代码进行了进一步的简化：将能合并的逻辑判断进行了合并，得到了AC的递归版本： int research_run(vector<int>&nums,int target,int left,int right) { int mid=(left+right)/2; if(target==nums[mid]) return mid; if(left==right&&nums[left]!=target) return -1; if(nums[left]<nums[mid]&&nums[left]<=target&&target<=nums[mid]) { return research_run(nums,target,left,mid-1); } else if(nums[left]>nums[mid]&&!(nums[mid]<=target&&target<=nums[right])) { return research_run(nums,target,left,mid-1); } else{ return research_run(nums,target,mid+1,right); } } int search(vector<int>&nums,int target) { return research_run(nums,target,0,nums.size()-1); } 迭代版本将递归版本改为迭代版本如下： int search(vector<int>&nums,int target) { return research_run(nums,target,0,nums.size()-1); }

2021年4月14日 0Comments 18Browse 1Like agedcat_xuanzai Read more

题目描述给你一个 m 行 n 列的矩阵 matrix ，请按照顺时针螺旋顺序，返回矩阵中的所有元素。示例 1：输入：matrix = [[1,2,3],[4,5,6],[7,8,9]] 输出：[1,2,3,6,9,8,7,4,5] 示例 2：输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]] 输出：[1,2,3,4,8,12,11,10,9,5,6,7] 提示： m == matrix.length n == matrix[i].length 1 <= m, n <= 10 -100 <= matrix[i][j] <= 100 解题思路这道题不涉及复杂难懂的算法，是一道模拟题。我们只需要去模拟螺旋的过程就可以得出答案。为了模拟螺旋的过程，我们需要标记二维表的四个角的位置：左上（top,left)，左下(bottom,left)，右上(top,right)，右下(bottom,right)。容易看出的是，我们只需要标记上(top)下(bottom)左(left)右(right)四个边界就可以了。然后就是螺旋的过程，每一次都按螺旋的顺序遍历最外层的元素：从左到右遍历上侧元素，依次为 (top,left) 到(top,right)，然后top++；从上到下遍历右侧元素，依次为 (top,right) 到 (bottom,right)，然后right--；从右到左遍历下侧元素，依次为(bottom,right) 到 (bottom,left)，然后bottom--；从下到上遍历左侧元素，依次为(bottom,left) 到(top,left)，然后left++。在遍历每一层的时候都需要符合条件top<=bottom && left<=right`，并且，在进行以上4个步骤的时候也需要符合条件`top<=bottom && left<=right。最终，我们可以得出完整代码。示例代码 vector<int> spiralOrder(vector<vector<int>>& matrix) { vector<int>res; if(matrix.size()==0||matrix[0].size()==0) { return {}; } int top=0; int bottom=matrix.size()-1; int left=0; int right=matrix[0].size()-1; while(top<=bottom && left<=right) { if(top<=bottom && left<=right) { for(int i=left;i<=right;++i) { res.push_back(matrix[top][i]); } } top++; if(top<=bottom && left<=right) { for(int i=top;i<=bottom;++i) { res.push_back(matrix[i][right]); } } right--; if(top<=bottom && left<=right) { for(int i=right;i>=left;--i) { res.push_back(matrix[bottom][i]); } } bottom--; if(top<=bottom && left<=right) { for(int i=bottom;i>=top;--i) { res.push_back(matrix[i][left]); } } left++; } return res; }

2021年4月8日 0Comments 30Browse 1Like agedcat_xuanzai Read more

题目描述给定一个没有重复数字的序列，返回其所有可能的全排列。示例: 输入: [1,2,3] 输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ] 解题思路这道题不涉及巧妙头疼的算法，只是单纯的考察递归回溯的编程技巧。我们以示例数据为例，分析一下我们的思路，力求清晰易懂。 [1,2,3]的全排列怎么求呢？按照我们高中学的排列组合的知识，全排列的求解相当于在_ _ _三个位置上依次选择一个数字填入。在第一个位置可以选择1，2，3中的任意一个，第二个位置可以选择除去第一个位置选择的数字之外的所有数字，第三个位置只能选择剩下的唯一一个数字。比如，如果第一个位置选择1，2，3中的1，那么第二个位置可以选择2，3中的一个任意一个，假设选择3，那么第三个位置就只能选择2。上述过程就是求解全排列的过程，然后我们思考怎么用递归的方式去模拟这一过程。为了避免选择之前位置已经选择的数字，我们使用一个visited数组去记录当前数字是否已经被选择。我们用path数组去记录一个排列，res数组去记录最终答案。用一个for循环去模拟一个位置选择不同数字的过程，不同位置的切换用递归的特性去模拟。最后最重要的就是回溯的过程，当递归结束的时候，当前的状态需要重置，也就是visited数组对应位置置为false，path数组将该数字退出。然后还有一个不可获取的部分就是获得答案的过程： if(path.size()==nums.size()) { res.push_back(path); return; } 示例代码 void DFS(vector<int>&nums,vector<bool>&visited,vector<vector<int>>&res,vector<int>&path) { if(path.size()==nums.size()) { res.push_back(path); return; } for(int i=0;i<nums.size();++i) { if(!visited[i]) { visited[i]=true; path.push_back(nums[i]); DFS(nums,visited,res,path); visited[i]=false; path.pop_back(); } } } vector<vector<int>> permute(vector<int>& nums) { vector<vector<int>>res; vector<int>path; vector<bool>visited(nums.size(),false); DFS(nums,visited,res,path); return res; }

2021年4月8日 0Comments 30Browse 1Like agedcat_xuanzai Read more

什么是线程池线程池是一项程序开发人员以简单和有效的方式去利用现代处理器的并发性来榨取处理器性能的方法。简而言之，线程池通过对线程的有效管理，提高了CPU的并发性。一般的流程是，提交一项任务后，线程池分配线程在不阻塞主线程的情况下完成这项工作。并且，线程池并不是每提交一项任务初始化一次，而是一次初始化，保持非活跃状态直至一些任务完成。这样的话，也减小了系统开销。线程池的原理示意图如下：什么情况下需要使用线程池有这样一个项目：公司需要为某某超市做一套对每天进入超市的顾客做用户画像的系统。基本流程是：对海康摄像头拍摄到的每一帧画面做人脸检测，然后对每个人脸进行年龄、性别和特征点的计算，最后将结果post到服务端进行后续处理。大家都知道人脸相关算法耗时是较高的，如果所有计算任务都放在主线程进行，那么势必会阻塞主线程的处理流程，无法做到实时处理。使用多线程技术是大家自然而然想到的方案，对每一帧都创建一个新的线程来做这系列的处理是否合理呢？相信大家都知道，线程的创建和销毁都是需要时间的，在上述的场景中必然会频繁的创建和销毁线程，这样的开销相信是不能接受的，此时线程池技术便是很好的选择。另外，在一些高并发的网络应用中，线程池也是常用的技术。陈硕大神推荐的C++多线程服务端编程模式为：one loop per thread + thread pool，通常会有单独的线程负责接受来自客户端的请求，对请求稍作解析后将数据处理的任务提交到专门的计算线程池。如何实现一个简易的线程池首先，我们使用一个队列来存储任务序列。这一部分的核心就是怎么实现将一个任务提交到任务序列，也就是入队。一个任务，一般可以表示为一个函数。那么我们需要传入的参数就有一个函数指针以及这个函数的所有参数。其中一个问题是这个函数的参数往往不是不确定的，类型也是未知的，因此，我们需要使用可变参数函数模板。二者，里面的一个难点在于怎么将各种不同的类型统一。我们使用std::bind+std::funtion+std::packaged_task等层层封装。最后就是同步和互斥操作。接着，就是线程池的工作过程。我们用一个vector来存储线程。主要的思路就是在没任务的时候保持线程处于非活跃状态，有任务的时候进行处理。其中也利用了lambda表达式的特性，以及同步和互斥操作。最后，就是线程池的析构实现。用一个bool变量来存储是否要停止使用线程池，当需要析构的时候，唤醒所有线程，并且逐个join。示例代码头文件如下： #include<thread> #include<condition_variable> #include<mutex> #include<vector> #include<queue> #include<future> class ThreadPool{ private: bool m_stop; std::vector<std::thread>m_thread; std::queue<std::function<void()>>tasks; std::mutex m_mutex; std::condition_variable m_cv; public: explicit ThreadPool(size_t threadNumber):m_stop(false){ for(size_t i=0;i<threadNumber;++i) { m_thread.emplace_back( [this](){ for(;;) { std::function<void()>task; { std::unique_lock<std::mutex>lk(m_mutex); m_cv.wait(lk,[this](){ return m_stop||!tasks.empty();}); if(m_stop&&tasks.empty()) return; task=std::move(tasks.front()); tasks.pop(); } task(); } } ); } } ThreadPool(const ThreadPool &) = delete; ThreadPool(ThreadPool &&) = delete; ThreadPool & operator=(const ThreadPool &) = delete; ThreadPool & operator=(ThreadPool &&) = delete; ~ThreadPool(){ { std::unique_lock<std::mutex>lk(m_mutex); m_stop=true; } m_cv.notify_all(); for(auto& threads:m_thread) { threads.join(); } } template<typename F,typename... Args> auto submit(F&& f,Args&&... args)->std::future<decltype(f(args...))>{ auto taskPtr=std::make_shared<std::packaged_task<decltype(f(args...))()>>( std::bind(std::forward<F>(f),std::forward<Args>(args)...) ); { std::unique_lock<std::mutex>lk(m_mutex); if(m_stop) throw std::runtime_error("submit on stopped ThreadPool"); tasks.emplace([taskPtr](){ (*taskPtr)(); }); } m_cv.notify_one(); return taskPtr->get_future(); } }; 测试代码如下： #include<iostream> #include<vector> #include<future> #include<functional> #include"ThreadPool.h" #include<random> std::random_device rd; std::mt19937 mt(rd()); std::uniform_int_distribution<int> dist(-1000, 1000); auto rnd = std::bind(dist, mt); void simulate_hard_computation() { std::this_thread::sleep_for(std::chrono::milliseconds(2000 + rnd())); } void multiply(const int a, const int b) { simulate_hard_computation(); const int res = a * b; std::cout << a << " * " << b << " = " << res << std::endl; } void multiply_output(int & out, const int a, const int b) { simulate_hard_computation(); out = a * b; std::cout << a << " * " << b << " = " << out << std::endl; } int multiply_return(const int a, const int b) { simulate_hard_computation(); const int res = a * b; std::cout << a << " * " << b << " = " << res << std::endl; return res; } int main(void) {…

2021年3月23日 6Comments 126Browse 1Like agedcat_xuanzai Read more

什么是大端小端所谓的大端小端就是数据对齐的端模式，也就是计算机中采用的两种常用的字节存储机制，与CPU相关。小端：低位字节（也就是数据）放在内存的低地址端，高位字节放在内存的高地址端。大端：高位字节（也就是数据）放在内存的低地址端，低位字节放在内存的高地址端。举个例子： 0x123456在内存中是怎么存储的呢？大端模式低地址---------->高地址 0x12 | 0x34 | 0x56 小端模式低地址---------->高地址 0x56 | 0x34 | 0x12 如何判断大端小端方法一强制类型转换用字符变量b来获取数字变量a的低地址部分，然后来进行判断。 bool isBigEndian() { short a=0x1234; char b=*(char *)&a; if(0x12==b) return true; return false; } 方法二利用联合体联合体内存储方式是小端。联合体内共享同一块内存，b会获取a的低地址数据，然后可以根据此进行判断。 bool isBigEndian() { union NUM { short a; char b; }num; num.a=0x1234; if(0x12==num.b) return true; return false; }

2021年3月20日 2Comments 78Browse 3Like agedcat_xuanzai Read more

C++中引入内联函数的目的是为了提高程序运行速度而做的一项改进。内联函数与常规函数之间的区别也不在编写方式，而在于C++编译器是怎么将他们组合到程序中的。为了更深层次的理解，我们需要首先了解一下函数代码是怎么发挥作用的。代码要发挥作用，最终是要转化为可执行程序，也就是一组机器语言指令。在运行程序时，操作系统将这些指令加载到计算机内存中，从而实现了相关的功能。因此，每一条指令都必须有特定的内存地址。计算机将逐步执行这些指令。而存在函数调用的时候，将会使程序跳到另一个地址（函数的地址），并且在函数结束的时候返回。我们更详细地解释一下里面的步骤。执行到函数调用指令时，程序将在函数调用后立即存储该指令的内存地址，并且将函数参数复制到堆栈，跳转到标记函数起点的内存单元，执行函数代码，然后返回到地址被保存的指令处。在使用函数的时候，来回跳转并且记录跳转位置会带来一定的开销。因而，引入了内联函数。内联函数在编译的时候将使用相应的函数代码来替换函数调用。这样一来，程序就不用跳转到另一个位置去执行函数代码了（因为你已经有副本了嘛）。所以，运用内联函数会带来运行速度的提升。然而，执行速度的提升并非没有代价的：内联函数的使用会带来“代码膨胀”的问题，也需要占用更多的内存；对内联函数进行任何修改，都需要重新编译函数的所有客户端，因为编译器需要重新更换一次所有的代码，否则将会继续使用旧的函数。所以，我们要分情况来决定要不要使用内联函数。如果，如果函数体内的代码比较长，使得内联将导致内存消耗代价比较高；如果函数体内出现循环，那么执行函数体内代码的时间要比函数调用的开销大；那么就不宜使用内联函数。要使用这项特性，必须采取下述措施之一：在函数声明前加关键字inline；在函数定义前加关键字inline；示例： inline int Max(int x, int y) { return (x > y)? x : y; }

2021年3月20日 0Comments 82Browse 0Like agedcat_xuanzai Read more

前两天面试的时候碰到了SQL查询命令，让查询综合成绩2到4名的学生学号，一下子蒙住了。下来赶紧整理一下，发现mySQL好坑啊！！！来一张可爱的猫咪图缓解一下郁闷的心情。废话不多说。首先给了一个很典型的学生成绩数据表：成绩表： score(s_id,c_id,s_s_score) –学生编号,课程编号,分数我们在数据库里面创建表并且写入数据： -- 1 创建表格 create table if not exists score ( s_id VARCHAR(20) not null, c_id VARCHAR(20) not null, s_score VARCHAR(20) default null ) engine=INNODB default charset=utf8; -- 2 插入数据 insert into score(s_id,c_id,s_score) values('01','01','80'); insert into score(s_id,c_id,s_score) values('01','02','90'); insert into score(s_id,c_id,s_score) values('01','03','99'); insert into score(s_id,c_id,s_score) values('02','01','70'); insert into score(s_id,c_id,s_score) values('02','02','60'); insert into score(s_id,c_id,s_score) values('02','03','80'); insert into score(s_id,c_id,s_score) values('03','01','80'); insert into score(s_id,c_id,s_score) values('03','02','80'); insert into score(s_id,c_id,s_score) values('03','03','80'); insert into score(s_id,c_id,s_score) values('04','01','50'); insert into score(s_id,c_id,s_score) values('04','02','30'); insert into score(s_id,c_id,s_score) values('04','03','20'); insert into score(s_id,c_id,s_score) values('05','01','76'); insert into score(s_id,c_id,s_score) values('05','02','87'); insert into score(s_id,c_id,s_score) values('06','01','31'); insert into score(s_id,c_id,s_score) values('06','03','34'); insert into score(s_id,c_id,s_score) values('07','02','89'); insert into score(s_id,c_id,s_score) values('07','03','98'); 然后我们看一下这个表的所有信息： select * from score; 然后我们考虑一下如何实现。由于要找出排名2到4的学生，那么我们必须得出排名。我们以学号分组，然后用sun()函数求出每个学生总成绩，然后运用order by对其降序排列。此时，我们已经可以得到排完序后的学生信息，但是我们仍然需要排名。我们用@cur变量来指示排名或者用row_number()窗口函数来完成这一操作。最后，用where或者having语句限制到排名2到4的学生即可。下面，分别给出5.7版本和8.0版本的mySQL示例代码： 5.7版本mySQL 由于5.7版本mySQL不支持窗口函数，只能用变量来指示排名。而且，使用变量的方式两个版本的实现还是不一样的！！！ mysql> select s_id,scoreSum,scoreRank -> from -> ( -> select b.s_id,b.scoreSum,@cur:=@cur+1 as scoreRank -> from -> ( -> select s_id,sum(s_score) as scoreSum -> from score -> group by s_id -> order by sum(s_score) desc -> ) b, -> (select @cur:=0) c -> ) r -> where scoreRank between 2 and 4 -> ; 8.0版本mySQL 首先就是用变量来指示排名的实现方式：注意观察一下与5.7版本实现方式的区别！ mysql> set @cur=0; Query OK, 0 rows affected (0.00 sec) mysql> select s_id,scoreSum,scoreRank -> from -> ( -> select b.s_id,b.scoreSum,@cur:=@cur+1 as scoreRank -> from -> ( -> select s_id,sum(s_score) as scoreSum -> from score -> group by s_id -> order by sum(s_score) desc -> ) b -> ) r -> where scoreRank between 2 and 4 -> ; 第二种方法就是用8.0版本支持的row_number()窗口函数的实现方式： mysql> select s_id,scoreSum,scoreRank -> from -> ( -> select s_id,sum(s_score) as scoreSum, -> row_number() over(order by sum(s_score) desc) as scoreRank -> from score ->…

2021年3月19日 1Comments 78Browse 1Like agedcat_xuanzai Read more

题目描述输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。为了让您更好地理解问题，以下面的二叉搜索树为例：我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表，第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点。下图展示了上面的二叉搜索树转化成的链表。“head” 表示指向链表中有最小元素的节点。特别地，我们希望可以就地完成转换操作。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。解题思路这道题要将一颗二叉搜索树转变为有序链表，而二叉搜索树的中序遍历就是有序的，所以我们遍历结点的方法就可以选用中序遍历的方法。然后就是关键的转变过程。由于需要转化为双向链表，所以需要一个指针标记当前指针的前一个结点，记为pre。由于需要构造循环链表，我们再用一个指针标记头结点。当整颗树完成转化之后，要将头尾指针连接起来。头结点我们可以通过判断pre指针是不是为空来标记（pre指针只有当前结点为整颗树的最左端结点的时候才为空），而尾结点正好是处理完整颗树之后的pre结点指向的结点（因为pre结点只有当前结点非空的时候会更新到当前结点）。示例代码 class Node { public: int val; Node* left; Node* right; Node() {} Node(int _val) { val = _val; left = NULL; right = NULL; } Node(int _val, Node* _left, Node* _right) { val = _val; left = _left; right = _right; } }; Node *pre,*head; void treeToDoublyList_run(Node* cur) { if(cur==nullptr) return; treeToDoublyList_run(cur->left); if(pre==nullptr) { head=cur; } else{ pre->right=cur; } cur->left=pre; pre=cur; treeToDoublyList_run(cur->right); } Node* treeToDoublyList(Node* root) { if(root==nullptr) return nullptr; treeToDoublyList_run(root); head->left=pre; pre->right=head; return head; }

2021年3月14日 0Comments 40Browse 1Like agedcat_xuanzai Read more

题目描述翻转一棵二叉树。示例：输入： 4 / \ 2 7 / \ / \ 1 3 6 9 输出： 4 / \ 7 2 / \ / \ 9 6 3 1 备注: 这个问题是受到 Max Howell 的原问题启发的：谷歌：我们90％的工程师使用您编写的软件(Homebrew)，但是您却无法在面试时在白板上写出>>翻转二叉树这道题，这太糟糕了。这是永远的嘲讽啊！太狠了解题思路运用递归的思想，先将左子树和右子数递归翻转，然后将翻转后的左子树和右子树调换位置。递归出口就是根节点为空或者只有根节点的情况。示例代码 TreeNode* invertTree(TreeNode* root) { if(root==nullptr) return nullptr; if(!root->left&&!root->right) return root; TreeNode* left=invertTree(root->left); TreeNode* right=invertTree(root->right); TreeNode* temp=left; root->left=root->right; root->right=temp; return root; }

2021年3月14日 0Comments 66Browse 0Like agedcat_xuanzai Read more

12 3 4

Leetcode200. 岛屿数量

Leetcode33. 搜索旋转排序数组

Leetcode54. 螺旋矩阵

Leetcode46: 全排列

用C++实现一个简易的线程池

C++之如何判断大端小端

C++之内联函数

SQL命令—查询综合成绩2到4名的学生学号

剑指 Offer 36. 二叉搜索树与双向链表

Leetcode 226 : 翻转二叉树