《剑指offer》week5

发表于 | 分类于 ，

问题一：数字序列中某一位的数字

问题描述

数字以0123456789101112131415…的格式序列化到一个字符序列中。

在这个序列中，第5位（从0开始计数）是5，第13位是1，第19位是4，等等。

请写一个函数求任意位对应的数字。

样例

1
2
3
输入：13

输出：1

问题分析

这里需要通过三步来确定：

  • 对于任给的一个数n，首先需要确定n这个数对应的是几位数，比如13对应的肯定是一个两位数，200对应的是一个三位数
    • 一位数：共9个，每一个长度为1，总长度是9*1
    • 两位数：共90个，每一个长度是2，总长度是90*2
    • 三位数：共900个，每一个长度是3，总长度是900*3
    • 四位数：共9000，每一个长度是4，总长度是9000*4
  • 确定好n对应的次序的数是几位数之后，需要确定好是对应的次序的数的数值是多少
  • 确定好数值之后就确定对应这个数值的从左到右第几位上

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
/*
1、确定是几位数(i)
2、确定是第几位数的数值(number)
3、确定那几个数的第几位(r)
时间复杂度：O(logn)
*/
public:
    int digitAtIndex(int n) {
        long long i=1,s=9,base=1;  //i表示的是第i位数，s表示的是第i位数公有多少个数，base表示第i位数的第一个数是多少
        while(n>i*s){   //1*9,2*90,3*900，只要n大于第i位所有数字数量和
            n-=s*i;
            i++;
            s*=10;
            base*=10;
        }
        //此时n表示的是i位数的第n个数，n-1*9-2*90-3*900
        
        
        int number=base+(n+i-1)/i-1;   //向上取整，用(n+i-1)/i代替向上取整，number表示的是第i位数的第几个数
        
        int r=n%i?n%i:i;    //这一步求的是第i位数的第r位
        
        for(int j=0;j<i-r;j++) number/=10;   //如果n=1234,有上面的步骤求得number=448,r=1，这一步就是将后面的第i-r位数去掉
        
        return number%10;
        
        
    }
};

问题二：把数组排成最小的数

问题描述

输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。

例如输入数组[3, 32, 321]，则打印出这3个数字能排成的最小数字321323。

样例

1
2
3
输入：[3, 32, 321]

输出：321323

注意：输出数字的格式为字符串。

问题分析

重新定义一种排序的方法，排序后的数组只要从前往后加起来就可以得到要求的输出结果。

在这里我给出定义在这种运算的定义：$a<b \Leftrightarrow ab <ba$

解释：定义a<b，当且仅当ab<ba

由于ab和ba有可能超过int的表示范围，那么我们如果直接比较的话很可能会溢出，又因为ab和ba的长度是相同的，那么只需要把ab和ba表示成字符串，直接比较字符串就可以。

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
//定义一种运算
    static bool cmp(int a,int b){  //升序排列
        auto as=to_string(a),bs=to_string(b);
        return as+bs<bs+as;   //字符创比较大小是从左到右依次进行比较
    }
    string printMinNumber(vector<int>& nums) {
        sort(nums.begin(),nums.end(),cmp);
        string res;
        for(auto x:nums){
            res+=to_string(x);
        }
        return res;
    }
};

总结

在上述思路中，由于我们定义了一种新的比较两个数字大小的规则，这种规则是不是有效的？另外，我们只是定义了比较两个数字的规则，却用它来排序一个含有多个数字的数组，最终拼接数组中的所有数字得到的是不是真的就是最小的数字？

我们首先需要证明之前定义的比较两个数字大小的规则是有效的。一个有效的比较规则需要3个条件：自反性、对称性和传递性。假设a,b是属于集合的元素,R是关系,则有:

  • 自反性—-即对集合中的每一个元素a都有aRa
  • 对称性—-即对集合中的任意元素aRb,aRb成立当且仅当bRa
  • 传递性—-即对集合中的任意元素abc若aRb和bRc成立则aRc一定成立

如果a小于b，则ab<ba。假设a和b用十进制表示时分别有l位和m位，于是$ab=a10^l+b,ba=b10^m+a$

$ab<ba \rightarrow a10^m+b<b10^l+a \rightarrow a10^m-a<b10^l-b\rightarrow a(10^m-1)<b(10^l-1)\rightarrow a/(10^l-1)<b/(10^m-1) $

同理，如果b小于c，则bc<cb。假设c用十进制数表示时有n位，和前面的证明过程一样，可以得到$b/(10^m-1)<c/(10^n-1)$

$a/(10^l-1)<b/(10^m-1)$并且$b/(10^m-1)<c/(10^n-1) \rightarrow a/(10^l-1)<c/(10^n-1)\rightarrow a(10^n-1)<c(10^l-1)\rightarrow a10^n+c<c10^l+a\rightarrow ac<ca \rightarrowca \rightarrow a<b$

于是我们证明了这种比较规则满足自反性、对称性、传递性

问题三：把数字翻译成字符串

问题描述

给定一个数字，我们按照如下规则把它翻译为字符串：

0翻译成”a”，1翻译成”b”，……，11翻译成”l”，……，25翻译成”z”。

一个数字可能有多个翻译。例如12258有5种不同的翻译，它们分别是”bccfi”、”bwfi”、”bczi”、”mcfi”和”mzi”。

请编程实现一个函数用来计算一个数字有多少种不同的翻译方法。

样例

1
2
3
输入："12258"

输出：5

问题分析

动态规划

f[i]表示第i位字符最多有多少种翻译方法

还记得经典的爬楼梯(斐波那契数列)吗？每次可以走1步或者2步，问n个台阶一共有多少种爬楼梯的方法？
dp[i]=dp[i-1]+dp[i-2]

这道题相当于加了一些限制条件。

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int getTranslationCount(string s) {
        int n=s.size();
        vector<int> f(n+1);
        f[0]=1;
        for(int i=1;i<=n;i++){
            f[i]=f[i-1];
            if(i>=2){
                int t=(s[i-2]-'0')*10+s[i-1]-'0';
                if(t>=10&&t<=25) f[i]+=f[i-2];
            }
        }
        return f[n];
    }
};

动态规划

动态规划就是说一个大问题可以划分为许多的小问题，将许多的小问题的解合并起来就可以得到大问题的解，比如前面的剪绳子那一题。

问题四：礼物的最大价值

问题描述

在一个m×n的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于0）。

你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格直到到达棋盘的右下角。

给定一个棋盘及其上面的礼物，请计算你最多能拿到多少价值的礼物？

注意：

  • m,n>0m,n>0

样例：

1
2
3
4
5
6
7
8
9
10
输入：
[
  [2,3,1],
  [1,7,1],
  [4,6,1]
]

输出：19

解释：沿着路径 2→3→7→6→1 可以得到拿到最大价值礼物。

问题分析

动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
/*动态规划
1、状态表示f[i,j]
2、状态转移f[i,j]=max(f[i-1,j],f[i,j-1])+gift[i,j]
3、边界检查f[i,0]=f[0,j]=0
*/
public:
    int getMaxValue(vector<vector<int>>& grid) {
    	int m=grid.size(),n=grid[0].size();
    	vector<vector<int>> f(m+1,vector<int>(n+1,0));
    	int i=1,j=1;
    	int res=0;
    	for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                f[i][j]=max(f[i-1][j],f[i][j-1])+grid[i-1][j-1];
         return f[m][n];
    }
}

总结

动态规划三要素：

  • 状态表示（初始状态要给出或者是默认为0）
  • 转态转移
  • 边界检查（一般会在行或者列多设一行或者一列）

问题五：最长不含重复字符的子字符串

问题描述

请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。

假设字符串中只包含从’a’到’z’的字符。

样例

1
2
3
输入："abcabc"

输出：3

问题分析

双指针法

设置两个指针i、j，j从前往后依次扫描，i表示的是i到j最长的不重复子字符串。

在使用双指针的时候需要保证i和j都是单调的，也就是j向后移动的话i也要向后移动

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
/*双指针做法：
每个指针只能够走n步
每个指针的走法都是往后面移动一格，也就是单调的
*/
public:
    int longestSubstringWithoutDuplication(string s) {
        unordered_map<char,int> count;
        int res=0;
        for(int i=0,j=0;j<s.size();j++){  //每一个j都对应于一个i
            if(++count[s[j]]>1){   //如果之前出现过s[j]
                while(count[s[i]]==1) count[s[i++]]--;   //将新的j到原来旧的i之间出现的数都置为0，也就保证了新的j对应的i之前的都是为0
                count[s[i++]]--;   //这里的i应该就是和j具有相同的值
            }
            res=max(res,j-i+1);   //最终的所有的i到j的map对应的结果都是1
        }
        return res;
    }
};

总结

在使用双指针的时候，一定要保证两个指针都是单调的增加，要不然就不能采用双指针的方法。

这个题目也可以采用动态规划的方法，用f(i)表示以i个字符结尾不包含重复子字符串的最长长度，从左向右扫描

  • 若第i个字符在之前没出现过，则 f(i) = f(i-1) + 1;
  • 若第i个字符在之前出现过，计算第i个字符距离上次出现之间的距离为d
    • 若d <= f(i-1)，则说明第i个字符上次出现在f(i-1)对应的不重复字符串之内，那么这时候更新 f(i) = d
    • 若d > f(i-1)，则无影响,f(i) = f(i-1) + 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if (s.length() == 0)
            return 0;
        int curLen = 0, maxLen = 0;
        int* position = new int[26];  //用来存储每个字符上次出现在该字符串中位置的下标
        for (int i = 0; i < 26; i++)
            position[i] = -1;

        for (int i = 0; i < s.length(); i++){
            int preIndex = position[s[i] - 'a'];
            if (preIndex < 0 || i - preIndex > curLen) // 没出现过，或者d>f(i-1)
                curLen++;
            else{                      // 出现过了
                if (curLen > maxLen)
                    maxLen = curLen;
                curLen = i - preIndex  // f(i) = d
            }
            position[s[i] - 'a'] = i;
        }
        if (curLen > maxLen)
            maxLen = curLen;

        delete[] position;
        return maxLen;
};

问题六：丑数

问题描述

我们把只包含因子2、3和5的数称作丑数（Ugly Number）。

例如6、8都是丑数，但14不是，因为它包含因子7。

求第n个丑数的值。

样例

1
2
3
输入：5

输出：5

注意：习惯上我们把1当做第一个丑数。

问题分析

创建一个数组，里面的每一个数字是已经排序好的丑数，每个丑数是前面的丑数乘以2、3或者5得到的。

这种思路的关键就是怎么样确保里面的数组是排好序的。假设数组中已经有若干个排好序的丑数，并把最大的丑数记为M，接下来分析如何生成下面一个丑数。该丑数一定是前面一个丑数乘以2、3或者5的结果，所以我们首先考虑把已有的丑数每个乘以2.在乘以2的时候，能够得到若干个小于或者等于M的结果。由于是顺序生成的，小于或者等于M的肯定已经在数组中了，我们不需要再次考虑；还会得到若干大于M的结果，但是我们只需要第一个大于M的结果，因为我们希望得到的丑数是按照从小到大的顺序生成的，其它更大的结果以后再说。我们把得到的第一个乘以2后大于M的结果记为$M_2$。同样，我们把已有的每个丑数乘以3和5，能够得到第一个大于M的结果$M_3$和$M_5$。那么下一个丑数应该就是$M_2、M_3、M_5$这三个数中的最小数。

在前面的分析中，对于乘以2而言，一定存在一个丑数$T_2$，排在它前面的每个丑数乘以2得到的结果都会小于已有的最大的丑数，在它之后的每个丑数乘以2得到的结果都会大于已有的丑数，我们只需要记下这个丑数的位置，同时每次在生成新的数组的时候需要去更新$T_2$，同理也可以得到$T_3、T_5$.

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int getUglyNumber(int n) {
        vector<int> v;
      	v.push_back(1);
      	int i=0,j=0,k=0;
      	while(--n){
  			int t=min(v[i]*2,v[j]*3),v[k]*5;
          	v.push_back(t);
          	if(v[i]*2==t) i++;
          	if(v[j]*3==t) j++;
          	if(v[k]*5==t) k++;
          	
		}
    }
};

问题七：字符串中第一个只出现一次的字符

问题描述

在字符串中找出第一个只出现一次的字符。

如输入"abaccdeff"，则输出b。

如果字符串中不存在只出现一次的字符，返回#字符。

样例：

1
2
3
输入："abaccdeff"

输出：'b'

问题分析

哈希表

只需要定义一个哈希表，记录每个字符出现的次数

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    char firstNotRepeatingChar(string s) {
    	unordered_map<char,int> count;
    	for(int i=0;i<s.size();i++){
  			count[s[i]]++;
		}
		int res='#'
    	for(auto x:s){
  			if(count[x]==1) res=x,break;
		}
	}
}

总结

  • 定义一个函数，输入两个字符串，从第一个字符串中删除在第二个字符串中出现过的所有的字符。
    • 这里我们可以用一个哈希表来存储第二个字符串，这样我们从头到尾扫描第一个字符串的每个字符，用$O(1)$时间就能够判断出该字符是不是在第二个字符中。
  • 定义一个函数，删除字符串中所有重复出现的字符
    • 创建一个哈希表，用于保存从头到尾扫描到的每一个字符串中的每个字符，如果扫描到该字符时发现哈希表对应的内容为true，那么表示这个字符在之前出现过，直接删除就可以
  • 在英语中，如果两个单次出现的字母相同，并且每个字母出现的次数也相同，那么这两个单词就是变位词
    • 创建一个哈希表，用来统计字符串中每个字符出现的次数。当扫描到第一个字符串中每个字符时，为哈希表对应的项的值加1.接下来扫描第二个字符串，当扫描到每个字符的时候，为哈希表对应的项减去1.如果扫描完第二个字符串后，哈希表中所有的值都是0，那么这两个字符串就是变位词。

问题八：字符流中第一个只出现一次的字符

问题描述

请实现一个函数用来找出字符流中第一个只出现一次的字符。

例如，当从字符流中只读出前两个字符”go”时，第一个只出现一次的字符是’g’。

当从该字符流中读出前六个字符”google”时，第一个只出现一次的字符是’l’。

如果当前字符流没有存在出现一次的字符，返回#字符。

样例

1
2
3
4
5
输入："google"

输出："ggg#ll"

解释：每当字符流读入一个字符，就进行一次判断并输出当前的第一个只出现一次的字符。

问题分析

(哈希表，队列) $O(n)$

维护一个队列使得其中所有的元素都只存在一个，则队列头部则为第一个出现的数字

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution{
/*思想：维护一个队列，使得这个队列中所有的元素都是只出现一次的字符
队列就是相当于双指针i,j，i指向当前第一个出现的元素，j指向扫描到的元素，并且可以知道i,j都是单调的
*/
public:
    unordered_map<char,int> count;
    queue<char> q;
    //Insert one char from stringstream
    void insert(char ch){
        if(++count[ch]>1){   //如果新加入的元素在之前出现过
            while(q.size()&&count[q.front()]>1) q.pop();   //则将队列队头出现次数大于1的元素删除掉，这也就是可以保证队列中不会有重复字母，并且队头元素出现的次数只能为1
        }
        else{
            q.push(ch);
        }
    }
    //return the first appearence once char in current stringstream
    char firstAppearingOnce(){
        if(q.empty()) return '#';
        return q.front();
        
    }
};

问题九：数组中的逆序对

问题描述

在数组中的两个数字如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。

输入一个数组，求出这个数组中的逆序对的总数。

样例

1
2
3
输入：[1,2,3,4,5,6,0]

输出：6

问题分析

归并排序$O(nlogn)$

先把数组分割成子数组，统计出子数组内部的逆序对的数目，然后统计出两个相邻子数组之间的逆序对的数目。在统计逆序对的过程中，还需要对数组进行排序。

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
/*
这个题目就是采用归并排序的思想：
先把数组分隔成子数组，统计出子数组内部的逆序对数目，然后统计出两个相邻子数组之间的逆序对的数目
*/    

public:
    int merge(vector<int>& nums,int l,int r){
        if(l>=r) return 0;
        int mid=l+r>>1;
        int res=merge(nums,l,mid)+merge(nums,mid+1,r);    //先把这两部分的逆序对加上
        int i=l,j=mid+1;
        vector<int> temp;
        while(i<=mid&&j<=r){
            if(nums[i]<=nums[j]) temp.push_back(nums[i++]);
            else{   //出现逆序对的情况
                temp.push_back(nums[j++]);
                res+=mid-i+1;
            }
        }
        while(i<=mid) temp.push_back(nums[i++]);
        while(j<=r) temp.push_back(nums[j++]);
        i=l;
        for(auto x:temp) nums[i++]=x;
        return res;
    }
    int inversePairs(vector<int>& nums) {
        return merge(nums,0,nums.size()-1);
    }
};

总结

设两段有序表$A[low…mid]A[mid+1…high]$存放在同一顺序表中相邻的位置上，先将它们复制到辅助数组B中。每次从对应$B$的两个段中取出一个记录进行关键字的比较，将较小者放入$A$中，当数组$B$中有一段的下标超出其对应表的表长时（即该段的所有元素已经完全复制到A中），将另一段剩余部分直接复制到A中。

1
2
3
4
5
6
7
8
9
10
11
12
13
ElemType *B=(ElemType *)malloc((n+1)*sizeof(ElemType));
void Merge(ElemType A[],int low,int mid,int high){
  	for(int i=low;i<=high;i++)
  		B[i]=A[i];
  	for(i=low,j=mid+1,k=i;i<=mid&&j<=high;k++){
  		if(B[i]<=B[j])
  			A[k]=B[i++];
  		else
  			A[k]=B[j++];
	}
	while(i<=mid) A[k++]=B[i++];
	while(j<=high) A[k++]=B[j++];
}

递归形式的2-路归并排序算法是基于分治的，其基本过程如下：

  • 分解：将含有n个元素的待排序表分成各含n/2个元素的子表，采用2-路归并排序算法对两个子表递归地进行排序
  • 合并两个已排好序的子表得到的结果
1
2
3
4
5
6
7
8
void MergeSort(ElemType A[],int low,int high){
  	if(low<high){
  		int mid=(low+high)/2;   //从中间划分为两个字序列
  		MergeSort(A,low,mid);   //对左侧子序列进行递归排序
  		MergeSort(A,mid+1,high);   //对右侧子序列进行递归排序
  		Merge(A,low,mid,high);   //归并
	}
}

问题十： 两个链表的第一个公共结点

问题描述

输入两个链表，找出它们的第一个公共结点。

当不存在公共节点时，返回空节点。

样例

1
2
3
4
5
6
7
8
给出两个链表如下所示：
A：        a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗            
B:     b1 → b2 → b3

输出第一个公共节点c1

问题分析

双指针法

由样例，设A中不重合的长度为a，B中不重合的长度为b，A和B重合的长度为c（c可能为0，当为0的时候表示没有公共节点）

指针q由a1出发，一直访问到c3，然后从b1出发

指针p由b1出发，一直访问到c3，然后从a1出发

在上面的两个过程中，如果由公共节点的话，那么a+c+b=b+c+a，那么指针q和指针p第一次遇见的点就是公共节点；如果没有公共节点的话，那么a+b=b+a，最终q和p都是为null

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *findFirstCommonNode(ListNode *headA, ListNode *headB) {
    	auto p=headA,q=headB;
    	while(p!=q){
  			if(p) p=p->next;
  			else p=headB;
  			if(q) q=q->next;
  			else q=headA;
		}
		return q;
	}
}

问题十一：数字在排序数组中出现的次数

问题描述

统计一个数字在排序数组中出现的次数。

例如输入排序数组[1, 2, 3, 3, 3, 3, 4, 5]和数字3，由于3在这个数组中出现了4次，因此输出4。

样例

1
2
3
输入：[1, 2, 3, 3, 3, 3, 4, 5] ,  3

输出：4

问题分析

二分查找

由于是已经排好序的数组，我们要查找的数是一段折线，中间的就是我们需要查找到的数。

我们只需要找到中间直线的左端点和右端点，那么我们就可以得到该数出现的次数。

那么我们在确定k的左端点时，只需要排除左边的数字，判别条件nums[mid]<k,令l=mid

在确定k的右端点的时候，只需要排除右边的数字

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
/*
利用二分查找，我们知道k可能出现多次，在坐标轴上表现的就是中间有一段是平行的，值为k，
那么我们在确定k的左端点时，只需要排除左边的数字，判别条件nums[mid]<k,令l=mid
在确定k的右端点的时候，只需要排除右边的数字
*/
public:
    int getNumberOfK(vector<int>& nums , int k) {
       if(nums.empty()) return 0;
       int l=0,r=nums.size()-1;
       while(l<r){   //查找左端点
           int mid=l+r>>1;
           if(nums[mid]<k) l=mid+1;   //左端点是在右半边
           else r=mid;
       }
       if(nums[l]!=k) return 0;
       int left=l;
       
       l=0,r=nums.size()-1;
       while(l<r){    //查找右端点
           int mid=l+r+1>>1;
           if(nums[mid]<=k) l=mid;   //右端点也是在右半边
           else r=mid-1;
       }
       if(nums[l]!=k) return 0;
       int right=r;
       return right-left+1;
    }
};

总结

  • 0~n-1中缺失的数字：一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0~n-1之内，在范围0~n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数组
    • 如果中间元素的值和下标相等，那么下一轮查找只需要查找右半边；如果中间元素的值和下标不相等，并且它前面一个元素和它的下标相等，这意味着中间的这个数字正好是第一个值和下标不相等的元素；如果中间元素的值和下标不相等，并且它前面一个元素和它的下标也不相等，这意味着中间的这个数字正好是第一个值和下标不相等的元素，这意味着下一轮查找只需要查找左半边。
  • 数组中数值和下标相等的元素：单调递增的数组{-3，-1，1，3，5}，数字3和它的下标相等
    • 直接用二分查找
分享到： 收藏夹 复制网址 邮件 微信 QQ空间 腾讯微博 豆瓣 一键分享 更多