题目：给定一个无序整数数组arr，请使之有序。思路：找到一个数p，把arr分成两部分，左边部分所有数都小于或等于p,右边部分所有数都大于或等于p。然后对左右两部分继续应用此规则。如何找数p? 首先让p等于arr[0]，然后两个指针l、r从左右两边同时遍历，左边遇到大于p的数，停下，右边遇到小于p的数，停下，然后交换l、r。重复这个动作，直到l、r相遇。然后arr[0]和arr[l]交换。此时数组被p分为左右两部分，左边的数都小于p，右边的数都大于p。代码：class QuickSort { public: void quickSort(vector<int>& arr,int left, int right) { if (left < right) { int l = left, r = right; while (l < r) { while (l < r && arr[left] <= arr[r]) {
题目：有三根柱子，从左到右排列，编号分别是0、1、2。0号柱子上有n个盘子，从上到下，盘子依次增大，编号为1、2、3、···、n。现在需要将0号柱子上的盘子搬到右方编号为2的柱子上。有三条规则：一次搬一只盘子。每根柱子只有最上面的盘子可被搬动。大盘子不可置于小盘子的上方。思路：要想把0号柱子最底下的n号盘子放到2号柱子上，需要先把1～n-1号盘子移到1号柱子上。再把n号盘子移动到2号柱子上。然后再把1~n-1号盘子从1号柱子移动到2号柱子上。工作结束。那怎么把1~n-1号盘子移动到1号柱子上呢？这个问题和题目的问题是一样的，只是问题规模变小了，可以使用递归处理。代码：class Solution { public: void hanota(vector<int>& A, vector<int>& B, vector<int>& C) { int n = A.size(); hanotaRecursive(n, A,B,C); } void hanotaRecursive(
题目：有三根柱子，从左到右排列，编号分别是0、1、2。0号柱子上有n个盘子，从上到下，盘子依次增大，编号为1、2、3、···、n。现在需要将0号柱子上的盘子搬到右方编号为2的柱子上。有三条规则：一次搬一只盘子。每根柱子只有最上面的盘子可被搬动。大盘子不可置于小盘子的上方。思路：本题是经典问题，常规解法就是使用递归。本次尝试采用for循环来解决（思路来自《图解算法》(俞征武著)一书）。通过观察，发现要把n个盘子从0柱移到2柱需要移动2n-1次。所以一个循环,i从1到2n-1。计算最大的k,使得i=2k * y（故本次将搬动第k+1号盘子）当n为偶数且k+1为奇数时，移动第k+1号盘子从当前的s柱子半岛第(s+1)%3柱子当n为偶数且k+1为偶数时，移动第k+1号盘子从当前的s柱子半岛第(s-1)%3柱子当n为奇数且k+1为奇数时，移动第k+1号盘子从当前的s柱子半岛第(s-1)%3柱子当n为奇数且k+1为偶数时，移动第k+1号盘子从当前的s柱子半岛第(s+1)%3柱子代码：class Hanota { public: void hanota(vector<int>&a
题目：一个 n x n 整数矩阵 arr ，请返回 非零偏移下降路径 数字和的最小值。非零偏移下降路径 定义为：从 arr 数组中的每一行选择一个数字，且按顺序选出来的数字中，相邻数字不在原数组的同一列。思路：从整数矩阵arr的顶部到底部，定义dp[i][j]为从顶部到第i行，第j个数的 非零偏移下降路径 数字和的最小值，则答案为min(dp[n-1][i]),0<=i<=n-1 。记第i-1行的最小值为first,次小值为second。则状态转移方程为 dp[i][j]=first+arr[i][j],first和arr[i][j]不同一列 d[i][j] = second+arr[i][j]，first和arr[i][j]同一列。边界dp[0][i] = arr[0][i] ,0<=i<=n-1,时间复杂度为O(n2),空间复杂度为O(1)代码：class Solution { public: int minFallingPathSum(vector<vector<int>>& grid) { int
题目 已知一个数组中存在一个众数，请找出这个众数。众数是指一个数组中的数出现的次数超过数组长度的一半。思路 看到这道题的第一眼，想到的方法是，遍历数组，给每个数计数，然后找到数量最多的数返回。这个算法的时间和空间复杂度都是O(n)。没想到还有更优秀的做法。这个方法就是摩尔投票法。摩尔投票法的思路就是，遍历数组，也是给数计数，不过有点不一样。 首先任选一个候选人，计数为1，一般都是从第一个数开始。遇到相同的数就加1，遇到不同的就减1，如果计数为0，则把当前的数作为候选人，计数为1。重复这个过程到数组的最后。候选人就是答案。时间复杂度为O(n),空间复杂度为O(1)代码class Solution { public: int majorityElement(vector<int>& nums) { int count = 1; int maj = nums[0]; for(int i = 1;i < nums.size();i++) {
