OJ每日练习（12）

Posted on | In

（周末两天均在完善Json解析器与生成器，现如今可以腾出手来刷题）

题目名称

  1. 数字序列中某一位的数（剑指offer #44）
  2. 把数组排成最小的数（剑指offer #45）
  3. 把数字翻译成字符串（剑指offer #46)
  4. 礼物的最大价值（剑指offer #47)
  5. 最长不含重复字符的子字符串（剑指offer #48)
  6. 丑数（剑指offer #49）
  7. 第一个只出现一次的字符（剑指offer #50）
  8. 数组中的逆序对（剑指offer #51）
  9. 两个链表的第一个公共节点（剑指offer #52）
  10. 在排序数组中查找数字（剑指offer #53）

数字序列中某一位的数（剑指offer #44）

解题思路

寻找规律，首先明确当前输入在哪一个区段，然后根据偏移量完成求解。这道题毫无难点，就是写起来很不舒服。

解题方案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int findNthDigit(int n) {
        if(n<=9)
            return n;
	    int digitNum = 1, numberNum = 9, start = 1;
        while(numberNum < n/digitNum){
            n -= digitNum * numberNum;
            start *= 10;
            digitNum += 1;
            numberNum *= 10;
        }
        int nthDigit  = 0;
        if(n%digitNum == 0){
            nthDigit = (start + n/digitNum-1) % 10;
        }else{
            int nthNumber = (start + n/digitNum);
            nthDigit = to_string(nthNumber)[n%digitNum-1] - '0';
        }
        return nthDigit;
    }
};

把数组排成最小的数（剑指offer #45）

解题思路

这道题的难点在于排序规律，而非组合。我们完全可以将所有数字变为字符串存入vector中，然后利用C++ STL 接收谓词作为排序规则的特性对该vector排序（排序规则为s1+s2<s2+s1），最终将vector转为string即可。

解题方案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    string PrintMinNumber(vector<int> numbers) {
        if(numbers.empty())
            return string();
        vector<string> ns;
        for(auto i:numbers)
            ns.push_back(to_string(i));
        sort(ns.begin(),ns.end(),[](const string&s1,const string& s2){return s1+s2<s2+s1;});
        string res;
        for(auto& s:ns)
            res+=s;
        return res;
    }
};

把数字翻译成字符串（剑指offer #46)

解题思路

动态规划问题，dp[i]=f[i]*dp[i-1]+g[i]*dp[i-2]。其中dp[i]为前i个字符所能构成的组合数。f[i]表征s[i-1]为数字且不为0，g[i]表征s[i-1]是否能与前一个字符构成组合。需要注意的是‘0‘略微繁琐，这是一道细节题。

解题方案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int numDecodings(string s) {
         if(s.length()==0 || s[0] == '0') return 0;
        vector<int> dp(s.size()+1,0);
        dp[0]= 1,dp[1] = 1;
        for(int i=2;i<=s.size();i++){
            if(s[i-1]>='1' && s[i-1]<='9')
                dp[i] += dp[i-1];
            if(s[i-2]=='1' || (s[i-2]=='2' && s[i-1]>='0' && s[i-1]<='6'))
                dp[i] += dp[i-2];           
        }
        return dp[s.size()];
    }
};

礼物的最大价值

解题思路

这又是一道典型的动态规划。但有所区别的是，这道题没必要设立m*n的矩阵来保存临时值。由于到达坐标(i,j)的格子时能够拿到的礼物的最大价值只依赖坐标为(i-1,j)与(i,j-1）的格子，因此只需要使用一个长度为n的一维数组即可，数组中前j个数字为f(i,0)直到f(i,j)，后面的则为f(i-1,j)直到f(i-1,n-1)。

解题方案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int getMax(vector<vector<int> > v){
        if(v.empty()||v[0].empty())
            return 0;
        vector<int> dp(v[0].size());
        for(size_t i=0;i!=v.size();++i)
            for(size_t j=0;j!=v[0].size();++j){
                int up = i==0?0:dp[j];
                int left = j==0?0:dp[j-1];
                dp[j]=max(up,left)+v[i][j];
            }
        return dp[v[0].size()-1];
    }
}

最长不含重复字符的子字符串（剑指offer #48)

解题思路

这道题没必要使用动规。假设子串里含有重复字符，则父串必含有重复字符，单个子问题足以决定父问题，因此可以使用贪心。在动规中，单个子问题影响父问题，并不足以决定父问题。

从左向右扫描，当遇到重复字母时，以上一个重复字母的index+1作为搜索起始位置，复杂度为O（n）。

解题方案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        vector<int> map(256,-1);
        int slow=0,fast=0;
        int maxlen=0;
        for(fast=0;fast<s.size();++fast){
            if(map[s[fast]]>-1){
                maxlen=max(maxlen,fast-slow);
                slow=max(map[s[fast]]+1,slow);
            }
            map[s[fast]]=fast;
        }
        return max(maxlen,fast-slow);
    }
};

丑数（剑指offer #49）

解题思路

将之前所有的丑数全部存储起来，并且额外保存factor2、3、5作为当前的丑数因子。若当前factorn为最小，则更新其为n*ugly[++indexn];

解题方案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int nthUglyNumber(int n) {
        vector<int> ugly(n);
        ugly[0]=1;
        int index2=0,index3=0,index5=0;
        int factor2=2,factor3=3,factor5=5;
        for(int i=1;i<n;++i){
            int minf =min(min(factor2,factor3),factor5);
            ugly[i]=minf;
            if(factor2==minf)
                factor2=2*ugly[++index2];
            if(factor3==minf)
                factor3=3*ugly[++index3];
            if(factor5==minf)
                factor5=5*ugly[++index5];
        }
        return ugly[n-1];
    }
};

第一个只出现一次的字符（剑指offer #50）

解题思路

用一个hashtable保存字符出现的次数，然后遍历字符串找到这个字符即可。

解题方案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int FirstNotRepeatingChar(string str) {
        if(str.empty())
            return -1;
        unordered_map<char,int> res;
        for(auto c:str)
            res[c]++;
        for(size_t i=0;i!=str.size();++i)
            if(res[str[i]]==1)
                return i;
        return -1;
    }
};

数组中的逆序对

解题思路

采用归并排序的策略，其中递归基是beg==end。需要注意的地方在于，若前一半的元素i大于后一半的元素j，则此时存在逆序对的个数为后一般数组剩余元素数，此外，每一次计算后都需要对原有数组完成排序。

解题方案

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
31
32
33
34
35
36
class Solution {
public:
    int InversePairs(vector<int> data) {
        if(data.size()<=1) return 0;
        vector<int> copy(data.size());
        int count = aux(data,copy,0,data.size()-1);
        return count;
    }
private:
    int aux(vector<int>&data,vector<int>& copy,int beg,int end){
        if(beg==end){
            copy[beg]=data[beg];
            return 0;
        }
        int mid = beg+(end-beg)/2;
        int left = aux(data,copy,beg,mid)%1000000007;
        int right = aux(data,copy,mid+1,end)%1000000007;
        int i=mid;
        int j=end;
        int index=end;
        int count=0;
        while(i>=beg && j>=mid+1){
            if(data[i]>data[j]){
                copy[index--]=data[i--];
                count+=j-mid;
                count%=1000000007;
            }
            else
                copy[index--]=data[j--];
        }
        while(i>=beg) copy[index--]=data[i--];
        while(j>=mid+1) copy[index--]=data[j--];
        for(int i=beg; i<=end; i++) data[i] = copy[i];
        return (count+left+right)%1000000007;
    }
};

两个链表的第一个公共节点（剑指offer #52）

解题思路

假定两个链表长度为a+n与b+n，n为共有部分，那么两个链表一起走a+b+n步后必然相遇，相遇点为第一个共同点或nullptr（n==0）。具体实现就是一旦走到绝地就转向别人的头部。

解题方案

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    ListNode* FindFirstCommonNode( ListNode* head1, ListNode* head2) {
        ListNode* p = head1, *q = head2;
        while(p!=q){
            p=p?p->next:head2;
            q=q?q->next:head1;
        }
        return p;
    }
};

在排序数组中查找数字（剑指offer #53）

解题思路

本质上就是实现STL算法：equal_range;

解题方案

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 {
public:
    int GetNumberOfK(vector<int> data ,int k) {
        if(data.empty())
            return 0;
        if(data.size()==1)
            return data[0]==k?1:0;
        int lo=0;
        int hi=data.size();
        while(lo<hi){
            int mid = lo+(hi-lo)/2;
            if(data[mid]<k)
                lo=mid+1;
            else
                hi=mid;
        }
        int start = lo;
        hi=data.size();
        while(lo<hi){
            int mid = lo+(hi-lo)/2;
            if(k<data[mid])
                hi=mid;
            else
                lo=mid+1;
        }
        int end = lo;
        return end-start;
    }
};