剑指offer----数组、数值

  1. 下面代码的输出是什么
int GetSize(int data[])
{
    return sizeof(data);
}
int main()
{

    int data1[]= {1,2,3,4,5};
    int size1 = sizeof(data1);
    int *data2 = data1;
    int size2 = sizeof(data2);
    int size3 = GetSize(data1);
    cout <<size1 << " " << size2 << "  " << size3 << endl;
}

20 8  8

因为sizeof(data1)是求数组的大小,每个整数占4个字节;
第二个是因为指针占8个字节;
第三个是因为数组作为函数参数进行传递,数组退化为指针,也为8个字节。

  1. 面试题:找出数组中任意一个重复的数字,数组满足:长度为n的数组里所有数字都在0~n-1的范围内。
  • 思路:若不重复,每个下标对应一个等于下标值的数。对下标im=arr[i]作比较,不相等交换arr[i]arr[m]
  • 时间复杂度O(n),空间复杂度O(1)
#include <iostream>
#include<vector>
#include<algorithm>
using namespace std;

bool duplicate(vector<int> &arr, int &answer)
{
  for(auto i:arr)
    if(i<0 ||i>arr.size()-1)
      return false;
  for(auto i=0; i<arr.size();++i)
  {
    while(arr[i]!=i)
    {
      if(arr[i]==arr[arr[i]])
      {
        answer = arr[i];
        return true;
      }
      else
      {
        swap(arr[i], arr[arr[i]]);
      }
    }
  }
  return false;
}
int main() {
  int answer;
  vector<int> t={2,3,1,0,2,5,3};
  if(duplicate(t, answer))
    cout << "one duplicate number is: " << answer << endl;
  else
    cout << "no duplicate number ." << endl;
}

one duplicate number is: 2
  1. 不修改数组找出重复的数字,数组满足:长度为n+1的数组里所有的数字都在1~n范围内,因此至少有一个数字是重复的。找出任意一个数字。
  • 思路:辅助数组的方法O(n)时间复杂度,O(n)空间复杂度,空间换时间;折半查找的方法O(n\lg n)时间复杂度,O(1)空间复杂度,时间换空间。
  • 排查数组哪一半的数字有重复,遍历数组所有数,计数每个数是否在下标范围,总计数值超过的这一半的大小的话,有重复元素;
#include <iostream>
#include<vector>
#include<algorithm>
using namespace std;


int countRage(const vector<int> &arr,const int &start,const int &end)
{
  int count = 0;
  for(auto iter:arr)
  {
    if(start<=iter && iter<=end)
      ++count;
  }
  return count;
}
int getDuplication(const vector<int> &arr)
{
  int start =1;
  int end = arr.size()-1;
  //直到二分数组大小为1为止
  while(end>=start)
  {
    int middle=((end-start)>>1) + start;
    int count=countRage(arr, start, middle);
    //大小为1
    if (end==start)
    {
      //单个数字的计数是否重复
      if(count>1)
        return start;
      else
        break;
    }
    
    if(count > middle-start+1) //是否在左侧
      end = middle;
    else
      start = middle+1;
  }
  return -1;
}

int main() {
 
  vector<int> t={2,3,5,4,3,2,6,7};
  int answer=getDuplication(t);
  if(answer>=0)
    cout << "one duplicate number is: " << answer << endl;
  else
    cout << "no duplicate number ." << endl;
}

方法2:

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) {
    for(int i=0;i!=length;++i){
        int index=numbers[i]%length;
        if(numbers[index]>=length){
            *duplication=index;
            return 1;
        }              
        numbers[index]+=length;  
    }
    return 0;
}
};
  1. 有规律的二维数组中找出某一个数:数组满足每行数大小递增,每一列大小递增。
  • 从第一行最后一列排除:
//number 是要找的数
bool Find(vector<vector<int>> &mat,const int &rows, const int &columns, const int &number)
{
  bool find = false;
  if (rows>0 && columns>0)
  {
    int row=0, column=columns-1;
    while(row<rows && column >=0)
    {
      if(mat[row][column] == number)
      {
        find = true;
        break;
      }
      else if(mat[row][column] > number)
        --column;
      else
        ++row;
    }
  }
  return find;
}

int main() {
 
  vector<vector<int>> test={{1,2,8,9},{2,4,9,12},{4,7,10,13},{6,8,11,15}};
  int ans=7;
  int answer=Find(test,0, 4, ans);
  if(answer>=0)
    cout << "find answer: " << ans << endl;
  else
    cout << "no answer ." << endl;
}
  1. 数值的整数次方:给定一个double类型的浮点数baseint类型的整数exponent。求baseexponent次方。
  • 解:
    利用了公式:
    a^n = \begin{cases} a^{n/2} * a^{n/2}, & n 为偶数\\ a^{(n-1)/2} * a^{(n-1)/2}*a, & n 为奇数 \end{cases}

实现的时候先对目标target的一半运算出来,然后判断是否是奇数。

class Solution {
public:
    double Power(double base, int exponent) {
        // 直接返回
        if(base==0)
            return 0;
        //对数的绝对值
        unsigned int absExponent=(unsigned int)(abs(exponent));
        double ans = _power(base, absExponent);
        if(exponent<0)
            ans = 1.0/ans;
        return ans;
    }
private:
    //避免复杂度高,利用公式递归求解;
    double _power(int base, unsigned int absExponent)
    {
        if(absExponent==0)
            return 1;
        if(absExponent==1)
            return base;
        //递归公式
        double result=_power(base, absExponent>>1);
        //还剩一半的部分
        result *= result;
        //若为奇数值,乘上少乘的一个基底
        if(absExponent&0x1 ==1)
            result*=base;
        return result;
    }
};
  1. 调整数组顺序使得奇数位于偶数前面

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

  • 解:
    相对位置不变--->保持稳定性;奇数位于前面,偶数位于后面 --->存在判断,挪动元素位置; 这些都和内部排序算法相似,考虑到具有稳定性的排序算法不多,例如插入排序,归并排序等;
class Solution {
public:
    static bool isOk(int n){return (n&0x1)==1;}
    //stable_partition 这个函数函数功能是将数组中 isOk为真的放在数组前,假的放在数组后,和题意相符
    //stable_partition函数源码其实是开辟了新的空间,然后把符合条件的放在新空间的前面,其他的放在后面。
    void reOrderArray(vector<int> &array) {
        stable_partition(array.begin(),array.end(),isOk);
    }

};

29、顺时针打印矩阵

输入一个矩阵,按照从外向里以顺时针的顺序依次打印出每一个数字,例如,如果输入如下4 X 4矩阵: 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.

  • 解:需要分析它的边界:
    打印四个边,什么时候退出:行、列数目大于2倍起点的时候;起点是每次的左上角位置;

打印第一步:因为打印一圈至少有一步,所以直接打印;
打印第二步:行号大于起点行号才能多处行往下打印;
打印第三步:考虑这时候不能为一行一列的打印,至少是两行两列;
打印第四步:考虑已经少了一行数目;

class Solution {
public:
    vector<int> printMatrix(vector<vector<int> > matrix) {
        vector<int> ans;
        if(matrix.empty()) return ans;
        int rows=matrix.size();
        int cols=matrix[0].size();
        int position = 0;
        //退出条件是两倍位置大小
        while(rows> 2*position && cols > 2*position)
        {
            print(matrix,position,rows,cols, ans);
            ++position;
        }
        return ans;
    }
private:
    void print(const vector<vector<int>> &mat,int position, int rows, int cols,vector<int>& ans)
    {
        rows = rows-position-1;
        cols = cols-position-1;
        
        //case1:多余的列存在
        for(int i=position; i<=cols; ++i)
        {
            ans.push_back(mat[position][i]);
        }
        //case2:多余的行存在
        if(position<rows)
        {
            for(int i=position+1;i<=rows;++i)
            {
                ans.push_back(mat[i][cols]);
            }
        }
        //case3:从右到左打印;排除一行一列的打印
        if(position<rows && position<cols)
        {
            for(int i=cols-1;i>=position;--i)
            {
                ans.push_back(mat[rows][i]);
            }
        }
        //case4:从下到上打印
        if(position+1<rows && position<cols)
        {
            for(int i=rows-1;i>=position+1;--i)
                ans.push_back(mat[i][position]);
        }     
    }
};

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

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

  • 解: 两种方法实现:1,快排分割,元素被放置在中间位置,则找到结果;2.设置每次遇到的该数为result,并计数1,若下次遇到的
    是该数,计数增加,若不是,计数减少,当计数为0,设result为新的该数字,最后被保存的result肯定是超过一半的数字
class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        if(numbers.empty()) return 0;
        int result = numbers[0];
        int count = 1;
        for(int i=1; i<numbers.size();++i)
        {
            if(numbers[i] == result)
            {
                count++;
            }
            else
            {
                count--;
                if (count==0)
                {
                    result = numbers[i];
                    count=1;
                }
            }
        }
        //检查该数组是否是满足题意的数组;
        count=0;
        for(int i=0; i<numbers.size(); ++i)
        {
            if(numbers[i]==result)
                count++;
        }
        if(count*2<=numbers.size())
            return false;
        return result;
    }
};

方法1:

class Solution {
public:
    int MoreThanHalfNum_Solution(vector<int> numbers) {
        if(numbers.empty()) return 0;
        int middle = numbers.size()>>1;
        int start = 0;
        int end = numbers.size()-1;
        int index = partition(start, end, numbers);
        while(index!=middle)
        {
            //在下标小于中位数,它的middle应该在右边
            if(index<middle)
            {
                start = index+1;
                index = partition(start,end, numbers);
            }
            else
            {
                end = index-1;
                index = partition(start, end, numbers);
            }
        }
        //检查是否有是合格的组数
        int result = numbers[index];
        int count = 0;
        for(int i=0; i<numbers.size(); ++i)
        {
            if(numbers[i] == result)
                count++;
        }
        if(count*2<=numbers.size())
            return false;
        return result;
    }
private:
    //返回元素的中间位置
    int partition(int start,int end,vector<int>& arr)
    {
        int pivot = arr[start];
        size_t position = start;//记录哨兵最后放置的位置
        for(int i=start+1; i<= end; ++i)
        {
            if(arr[i]<pivot)//只放置小的在左边就行
            {
                position++;//遇到一个小的元素,往前走一步做交换
                if(i!=position)//头元素是povit,这个位置最后交换
                    swap(arr[i], arr[position]);
            }
        }
        swap(arr[position], arr[start]);
        return position;
    }
};

40、最小的k个数

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

  • 解析:第一种一般可想到是堆排序,且不会修改输入数据,适合在处理海量数据中进行查找,STL中的setmultiset的底层是红黑树实现的,可以满足在O(\lg n)时间内完成查找、删除、插入。第二种方法是partition.

方法1:

class Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        int len=input.size();
        if(len<=0 || k>len || k<=0) return vector<int>();
        vector<int> ans;
        for(int i=0;i<k;++i)//先插入前main的k个后建立大顶堆
            ans.push_back(input[i]);
        //建堆
        make_heap(ans.begin(), ans.end());
        for(int i=k; i<input.size(); ++i)
        {
            if(input[i]<ans[0]) //比堆顶元素还大,那么替换该元素放入ans,然后维持堆性质
            {
                pop_heap(ans.begin(), ans.end()); //最大元素放到末尾;
                ans.pop_back();//弹出最大的元素
                ans.push_back(input[i]); 
                push_heap(ans.begin(), ans.end());//维持堆性质
            }     
        }
        //使其从小到大输出
        sort_heap(ans.begin(),ans.end());
        return ans;
    }
};

方法2:

class Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        int len=input.size();
        if(len<=0||k>len || k<=0) return vector<int>();
         
        //仿函数中的greater<T>模板,从大到小排序
        multiset<int, greater<int> > leastNums;
        vector<int>::iterator vec_it=input.begin();
        for(;vec_it!=input.end();vec_it++)
        {
            //将前k个元素插入集合
            if(leastNums.size()<k)
                leastNums.insert(*vec_it);
            else
            {
                //第一个元素是最大值
                multiset<int, greater<int> >::iterator greatest_it=leastNums.begin();
                //如果后续元素<第一个元素,删除第一个,加入当前元素
                if(*vec_it<*(leastNums.begin()))
                {
                    leastNums.erase(greatest_it);
                    leastNums.insert(*vec_it);
                }
            }
        }
         
        return vector<int>(leastNums.begin(),leastNums.end());
    }
};

41、数据流中的中位数

如何得到一个数据流中的中位数?如果从数据流中读出奇数个数值,那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值,那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流,使用GetMedian()方法获取当前读取数据的中位数。

  • 解析: 假设整个数据容器分割为两部分,位于容器左边的部分比右边的部分小;容器左数组的最右边指向该部分最大的数;同样, 容器右数组的最左边指向该部分最小的数;
    具体实现:左边用最大堆,右边用最小堆;首先保证数据平均分配到两个堆中,因此这两个堆中的数据数目之差不超过1,用偶数的数字都插入最小堆;保证最大堆中的数都小于最小堆,当前插入数字小于最大堆堆顶元素,可以把该堆的堆顶元素排除,插入到最小堆,然后把该数字插入最大堆中.
class Solution {
private:
        vector<int> min;
        vector<int> max;
public:
        //第0个元素先插入到min中,之后第1个元素插入到max中.若元素有5个,那么0,2,4被插入到min中,可以看到
        //若元素有6个,0,2,4,被插入到min中,1,3,5被插入到max中。
        //因此min只用的元素大于等于max
        //元素为奇数时,返回min的元素
        void Insert(int num)
        {
           if(((min.size()+max.size())&1)==0)//偶数时 ,放入最小堆
           {
              if(max.size()>0 && num<max[0])
              {
                // push_heap (_First, _Last),要先在容器中加入数据,再调用push_heap ()
                 max.push_back(num);//先将元素压入容器
                 push_heap(max.begin(),max.end(),less<int>());//调整最大堆
                 num=max[0];//取出最大堆的最大值
                 //pop_heap(_First, _Last),要先调用pop_heap()再在容器中删除数据
                 pop_heap(max.begin(),max.end(),less<int>());//删除最大堆的最大值
                 max.pop_back(); //在容器中删除
              }
              min.push_back(num);//压入最小堆
              push_heap(min.begin(),min.end(),greater<int>());//调整最小堆
           }
           else//奇数时候,放入最大堆
           {
              if(min.size()>0 && num>min[0])
              {
                // push_heap (_First, _Last),要先在容器中加入数据,再调用push_heap ()
                 min.push_back(num);//先压入最小堆
                 push_heap(min.begin(),min.end(),greater<int>());//调整最小堆
                 num=min[0];//得到最小堆的最小值(堆顶)
                 //pop_heap(_First, _Last),要先调用pop_heap()再在容器中删除数据
                 pop_heap(min.begin(),min.end(),greater<int>());//删除最小堆的最大值
                 min.pop_back(); //在容器中删除
              }
              max.push_back(num);//压入数字
              push_heap(max.begin(),max.end(),less<int>());//调整最大堆
           }   
        }
        /*获取中位数*/      
        double GetMedian()
        {
            int size=min.size()+max.size();
            if(size<=0) //没有元素,抛出异常
                return 0;//throw exception("No numbers are available");
            if((size&1)==0)//偶数时,去平均
                return ((double)(max[0]+min[0])/2);
            else//奇数,去最小堆,因为最小堆数据保持和最大堆一样多,或者比最大堆多1个
                return min[0];
        }
};

42、连续子数组的最大和

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

  • 解析:1。动态规划问题,设在位置n-1处结尾的数组最大和为f(n-1),那前面长度为n的数组的最大连续子序列的和为:
    f(n)= \begin{cases} data(n), & n=0 \bigcup f(n-1) < 0 \\ f(n-1) + data(n), & n \neq 0 \bigvee f(n-1) >0 \end{cases}

可以理解,如果前面的结尾的子串为负数,可以不加;若为正数,可以考虑加上这个值。最后还需要求 max_{(i=1,2,3,....,N)}f(i) 找出最大的和:

class Solution {
public:
    /*
    dp = max{f(i)},i=0,1,...,N
    f(i) = f(i-1) + data[i] if (i!= 0 && f(i-1)>0) else data[i].
    */
    int FindGreatestSumOfSubArray(vector<int> array) {
        if(array.empty()) return 0;
        vector<int> arr;
        int ans = INT_MIN;
        for(int i=0; i<array.size(); ++i)
        {
           ans = max(ans, dp(i,arr,array));
        }
        return ans;
    }
private:
    //position给出结尾的位置
    //position结尾的最大和存入arr
    //target是原来的数组,用来查看当前的结尾数
    int dp(int position,vector<int>& arr,const vector<int> &target)
    {
        if(position && arr[position-1] > 0)
        {
            int ans = target[position] + arr[position-1];
            arr.push_back(ans);
            return ans;
        }
        else
        {
            arr.push_back(target[position]);
            return target[position];
        }
    }
};

2.跟据求和的性质,若为负,丢弃当前和,并记录每一的最大和;

public:
    int FindGreatestSumOfSubArray(vector<int> array) {
        if(array.empty())
        {
            InvalidInput = true;//判断是否无效输入而非最大和为0
            return 0;
        }
        int nCurSum=0;
        int great =0x80000000;
        for(int i=0; i<array.size();++i)
        {
            if(nCurSum<=0) //若为0或负值,那么略去这个求和,设新的求和为当前数
                nCurSum=array[i]; //
            else
                nCurSum+=array[i];
            if(nCurSum>great)//记录最大子数组和
                great = nCurSum;
        }
        return great;
        
    }
private:
    bool InvalidInput = false;
};

43、1~n整数中1出现的次数

求出113的整数中1出现的次数,并算出1001300的整数中1出现的次数?为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数(从1 到 n 中1出现的次数)。

  • 解析: 方法1:nlog(n)暴力搜索,对每一个数求一个计数1的函数;
    方法2:log(n) 考虑问题本身的性质;
//方法1:nlog(n)
class Solution {
public:
    /*
    方法1:nlog(n)暴力搜索,对每一个数求一个计数1的函数;
    方法2:log(n) 考虑问题本身的性质;
    */
    int NumberOf1Between1AndN_Solution(int n)
    {
        int number = 0;
        for(int i=1; i<=n; ++i)
        {
            number += Numberi(i);
        }
        return number;
    }
private:
    int Numberi(int i)
    {
        int number=0;
        while(i)
        {
            if(i%10==1)
                number+=1;
            i=i/10;
        }
        return number;
    }
};

方法2:参考第三题:https://www.jianshu.com/p/1582fbaf05f7

当 N 为 1 位数时,对于 N>=1,1 的个数 f(N) 为1。
当 N 为 2 位数时,则个位上1的个数不仅与个位数有关,还和十位数字有关。
比如当 N=23 时,个位上 1 的个数有 1、11、21 共3个,十位上1的个数为10,11...19 共10个,所以 1 的个数 f(N) = 3+10 = 13。
看出来有规律一:
如果 N 的个位数 >=1,则个位出现1的次数为十位数的数字加1;如果 N 的个位数为0,则个位出现 1 的次数等于十位数的数字。
十位数上出现1的次数类似,如果N的十位数字等于1,则十位数上出现1的次数为各位数字加1;如果N的十位数字大于1,则十位数上出现1的次数为10。
当 N 为 3 位数时,同样分析可得1的个数。如 N=123,可得 1出现次数 = 13+20+24 = 57。当 N 为 4,5...K 位数时,

我们假设 N=abcde,则要计算百位上出现1的数目,则它受到三个因素影响:百位上的数字,百位以下的数字,百位以上的数字。
如果百位上数字为0,则百位上出现1的次数为更高位数字决定。如 N=12013,则百位出现1的数字有100~199, 1000~1199, 21002199...11100111999 共 1200 个,等于百位的更高位数字(12)当前位数(100)。
如果百位上数字为1,则百位上出现1的次数不仅受更高位影响,还受低位影响。如12113,则百位出现1的情况共有 1200+114=1314 个,也就是高位影响的 12 * 100 + 低位影响的 113+1 = 114 个。
如果百位上数字为其他数字,则百位上出现1的次数仅由更高位决定。如 12213,则百位出现1的情况为 (12+1)
100=1300。

N=12013 i 是百位为0,高位是12现在从低位走到高位,即1~12013中,百位出现的1的数如下:
1 100~199
2 1100~1199
3 2100~1299
.. ...........
10 9100~9199
11 10100~10199
12 11100~11199

总共有12*100个1出现在百位。结论是位数为0时,只受高位数的影响,为高位数的值 * 当前位 。其他位的分析类似。

有以上分析思路,写出下面的代码。其中 low 表示低位数字,curr 表示当前考虑位的数字,high 表示高位数字。一个简单的分析,考虑数字 123,则首先考虑个位,则 curr 为 3,低位为 0,高位为 12;然后考虑十位,此时 curr 为 2,低位为 3,高位为 1。其他的数字可以以此类推,实现代码如下:

class Solution {
public:
    int NumberOf1Between1AndN_Solution(int n)
    {
        int count = 0;//1的个数
        int i = 1;//乘积因子
        int current = 0,after = 0,before = 0;
        while((n/i)!= 0){           
            current = (n/i)%10; //当前位数字
            before = n/(i*10); //高位数字
            after = n-(n/i)*i; //低位数字
            //如果为0,出现1的次数由高位决定,等于高位数字 * 当前位数
            if (current == 0)
                count += before*i;
            //如果为1,出现1的次数由高位和低位决定,高位*当前位+低位+1
            else if(current == 1)
                count += before * i + after + 1;
            //如果大于1,出现1的次数由高位决定,//(高位数字+1)* 当前位数
            else{
                count += (before + 1) * i;
            }    
            //前移一位
            i = i*10;
        }
        return count;
    }
};

45、把数组排成最小的数

输入一个正整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。例如输入数组{3,32,321},则打印出这三个数字能排成的最小数字为321323。

  • 解析:数组内的数变为string之后做拼接,按照字符串排序便可,拼接之后字符串AB>BA,那么有B<A,应该把B排前面。
class Solution {
public:
    //数组内的数变为string之后做拼接排序
    string PrintMinNumber(vector<int> numbers) {
        sort(numbers.begin(), numbers.end(), cmp);
        string ans="";
        for(int i=0; i<int(numbers.size());++i) ans+=to_string(numbers[i]);
        return ans;
    }
private:
    static bool cmp(int a, int b)
    {
        string sa=to_string(a), sb =to_string(b);
        return sa +sb < sb + sa;
    }
};

做法2:

//写的比较骚气的整型到string
string itos(int x){
    return (x > 9 ? itos(x / 10) : "") + char(x % 10 + '0');
}
//比较字符函数
bool cmp(int a, int b){
    return itos(a) + itos(b) < itos(b) + itos(a);
}

class Solution {
public:
    string PrintMinNumber(vector<int> a) {
        sort(a.begin(), a.end(), cmp);
        string s = "";
        //转为字符再追加到s
        for(int i = 0; i < int(a.size()); ++i) s += itos(a[i]);
        return s;
    }
};

49、第N个丑数。

把只包含质因子2、3和5的数称作丑数(Ugly Number)。例如6、8都是丑数,但14不是,因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。

  • 解析:
    空间换时间,记录存储下丑数,丑数按递增大小寻找;
    当前的丑数已经被找到,那么该丑数之前的数字都是排好序的,
    下一个丑数也是2、3、5的倍数,且大于当前丑数;找到每一个2、3、5倍数里最小的作为下一个丑数
    排序好的丑数中,前面的丑数是后面选出的丑数的因子之一,用下标跟随前面的因子与2、3、5的乘积>大于当前丑数
    丑数定义:1是最小的丑数,只能被2或者3或者5整除的数是丑数;
class Solution {
public:
    int GetUglyNumber_Solution(int index) {
        if(index<=0) return 0;
        vector<int> uglyVec={1}; 
        //作为下标记录2、3、5因子里前面
        int index2=0, index3=0, index5=0;
        while(uglyVec.size()<index)
        {
            uglyVec.push_back(min(uglyVec[index2]*2, min(uglyVec[index3]*3, uglyVec[index5]*5)));
            if(uglyVec[index2]*2== uglyVec.back()) //等号的意义是丑数不重复
                index2++;
            if(uglyVec[index3]*3 == uglyVec.back())
                index3++;
            if(uglyVec[index5]*5== uglyVec.back())
                index5++;
        }
        return uglyVec.back();
    }
};

51、逆序对

在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007

  • 解析:

/*归并排序的改进,把数据分成前后两个数组(递归分到每个数组仅有一个数据项),

合并数组,合并时,出现前面的数组值array[i]大于后面数组值array[j]时;则前面

数组array[i]~array[mid]都是大于array[j]的,count += mid+1 - i

参考剑指Offer,但是感觉剑指Offer归并过程少了一步拷贝过程。

还有就是测试用例输出结果比较大,对每次返回的count mod(1000000007)求余

*/

/*参考《剑指offer》,有两种思路。第一就是暴力求解法,时间复杂度为o(n^2),空间复杂度o(1)
第二种思路就是使用归并排序的思想进行处理,时间复杂度o(nlog(n)),空间复杂度0(n)*/
class Solution {
public:
    int InversePairs(vector<int> data) {
        if(data.size()<=1) return 0;//如果少于等于1个元素,直接返回0
        int* copy=new int[data.size()];
        //初始化该数组,该数组作为存放临时排序的结果,最后要将排序的结果复制到原数组中
        for(unsigned int i=0;i<data.size();i++)
            copy[i]=0;
        //调用递归函数求解结果
        int count=InversePairCore(data,copy,0,data.size()-1);
        delete[] copy;//删除临时数组
        return count;
    }
     //程序的主体函数
    int InversePairCore(vector<int>& data,int*& copy,int start,int end)
    {
        if(start==end)
        {
            copy[start]=data[start];
            return 0;
        }
        //将数组拆分成两部分
        int length=(end-start)/2;//这里使用的下标法,下面要用来计算逆序个数;也可以直接使用mid=(start+end)/2
        //分别计算左边部分和右边部分
        int left=InversePairCore(data,copy,start,start+length)%1000000007;
        int right=InversePairCore(data,copy,start+length+1,end)%1000000007;
        //进行逆序计算
        int i=start+length;//前一个数组的最后一个下标
        int j=end;//后一个数组的下标
        int index=end;//辅助数组下标,从最后一个算起
        int count=0;
        while(i>=start && j>=start+length+1)
        {
            if(data[i]>data[j])
            {
                copy[index--]=data[i--];
                //统计长度
                count+=j-start-length;
                if(count>=1000000007)//数值过大求余
                    count%=1000000007;
            }
            else
            {
                copy[index--]=data[j--];
            }
        }
        for(;i>=start;--i)
        {
            copy[index--]=data[i];
        }
        for(;j>=start+length+1;--j)
        {
            copy[index--]=data[j];
        }
        //排序
        for(int i=start; i<=end; i++) {
            data[i] = copy[i];
        }
        //返回最终的结果
        return (count+left+right)%1000000007;
    }
};

56、数组中数字出现的次数

一个整型数组里除了两个数字之外,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度O(1),空间复杂度O(n).

  • 解析:

61、扑克牌顺子

LL今天心情特别好,因为他去买了一副扑克牌,发现里面居然有2个大王,2个小王(一副牌原本是54张_)...他随机从中抽出了5张牌,想测测自己的手气,看看能不能抽到顺子,如果抽到的话,他决定去买体育彩票,嘿嘿!!“红心A,黑桃3,小王,大王,方片5”,“Oh My God!”不是顺子.....LL不高兴了,他想了想,决定大\小 王可以看成任何数字,并且A看作1,J为11,Q为12,K为13。上面的5张牌就可以变成“1,2,3,4,5”(大小王分别看作2和4),“So Lucky!”。LL决定去买体育彩票啦。 现在,要求你使用这幅牌模拟上面的过程,然后告诉我们LL的运气如何, 如果牌能组成顺子就输出true,否则就输出false。为了方便起见,你可以认为大小王是0

  • 解析:/先计算0,然后去掉0的部分,遍历这个数组,看相等的时候直接返回0,不连续的时候,累加间隔大小
class Solution {
public:
    bool IsContinuous( vector<int> numbers) {
        if(numbers.empty()) return false;
        sort(numbers.begin(), numbers.end());
        int countZero=0,unequal=0; //计数0的个数,计算不等数字的间隔
        for(int i=0;i<numbers.size() && numbers[i]==0;++i)
            countZero++;
        //先计算出0的个数,这些0不在我们的规则内;
        for(int i=countZero+1; i<numbers.size(); ++i)
        {
            if(numbers[i]==numbers[i-1])
                return false;
            if(numbers[i-1]+1 != numbers[i])
                unequal= unequal + numbers[i] - numbers[i-1] - 1;
        }
        if(unequal>countZero)
            return false;
        else
            return true;
    }
};

62、约斯夫环

每年六一儿童节,牛客都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此。HF作为牛客的资深元老,自然也准备了一些小游戏。其中,有个游戏是这样的:首先,让小朋友们围成一个大圈。然后,他随机指定一个数m,让编号为0的小朋友开始报数。每次喊到m-1的那个小朋友要出列唱首歌,然后可以在礼品箱中任意的挑选礼物,并且不再回到圈中,从他的下一个小朋友开始,继续0...m-1报数....这样下去....直到剩下最后一个小朋友,可以不用表演,并且拿到牛客名贵的“名侦探柯南”典藏版(名额有限哦!!_)。请你试着想下,哪个小朋友会得到这份礼品呢?(注:小朋友的编号是从0到n-1)

  • : 约瑟夫环两种解法,1循环链表,2是找规律直接算出结果;
class Solution {
public:
    int LastRemaining_Solution(int n, int m)
    {
        if(n<=0) return -1;
        list<int> numbers;
        for(unsigned int i=0; i<n;++i)
            numbers.push_back(i);
        list<int>::iterator iter = numbers.begin();
        while(numbers.size()>1)
        {
            //先游走m步,这里的i=1,因为删除第m个
            for(int i=1; i<m; ++i)
            {
                iter++;
                if(iter==numbers.end())
                    iter = numbers.begin();
            }
            //查看是否是迭代器最后一个位置
            list<int>::iterator next=++iter;
            if(next==numbers.end()) next = numbers.begin();
            --iter;
            numbers.erase(iter);
            iter = next;
        }
        return *(iter);
    }
};

66、乘积数组

给定一个数组A[0,1,...,n-1],请构建一个数组B[0,1,...,n-1],其中B中的元素B[i]=A[0]A[1]...A[i-1]A[i+1]...A[n-1]。不能使用除法。

  • 解析:分析递归式如图:
    剑指的思路:

B[i]的值可以看作下图的矩阵中每行的乘积。

下三角用连乘可以很容求得,上三角,从下向上也是连乘。

因此我们的思路就很清晰了,先算下三角中的连乘,即我们先算出B[i]中的一部分,然后倒过来按上三角中的分布规律,把另一部分也乘进去。

841505_1472459965615_8640A8F86FB2AB3117629E2456D8C652.jpg
//B[i]=A[0]*A[1]*...*A[i-1]*A[i+1]*...*A[n-1]
//从左到右算 B[i]=A[0]*A[1]*...*A[i-1]
//从右到左算B[i]*=A[i+1]*...*A[n-1]
class Solution {
public:
    vector<int> multiply(const vector<int>& A) {
     
        int n=A.size();
        vector<int> b(n);
        int ret=1;
        for(int i=0;i<n;ret*=A[i++]){
            b[i]=ret;
        }
        ret=1;
        for(int i=n-1;i>=0;ret*=A[i--]){
            b[i]*=ret;
        }
        return b;
    }
};

64、

  • 利用短路原理:
class Solution {
public:
    int Sum_Solution(int n) {
        int ans = n;
        ans && (ans += Sum_Solution(n - 1));
        return ans;
    }
};

65、不用加减乘除法做加法

写一个函数,求两个整数之和,要求在函数体内不得使用+、-、*、/四则运算符号。

  • 分析:考虑位运算,先相加,不进位,对进位的位置再做相加。
class Solution {
public:
    int Add(int num1, int num2)
    {
        int sum, carry;
        do
        {
            sum = num1 ^ num2; // 异或运算:0+1、1+0都是1,其他都是0;
            carry = (num1 & num2) << 1; //与运算,只有1+1才为1,然后左移1位;
            num1 = sum;    // 第三部求和是一个循环过程,直到没有进位,也就是num2为0
            num2 = carry;  // 下一次循环中更新sum
        }
        while(num2!=0);
        return num1;
        
    }
};
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 216,142评论 6 498
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 92,298评论 3 392
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 162,068评论 0 351
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 58,081评论 1 291
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 67,099评论 6 388
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 51,071评论 1 295
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 39,990评论 3 417
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 38,832评论 0 273
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 45,274评论 1 310
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,488评论 2 331
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,649评论 1 347
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 35,378评论 5 343
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 40,979评论 3 325
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,625评论 0 21
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,796评论 1 268
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 47,643评论 2 368
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 44,545评论 2 352

推荐阅读更多精彩内容