1608. 特殊数组的特征值

思路一：暴力

1
2
3
4
5
6
7
8
9
10
11
12
13
int specialArray(vector<int>& nums) {

    for(int i = 1;i<1000;i++)
    {
        int count = 0;
        for(int j =0;j<nums.size();j++)
        {
            if(nums[j]>=i) count++;
        }
        if(count == i) return i;
    }
    return -1;
}

**思路二：**降序排序+一次遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int specialArray(vector<int>& nums) {
        sort(nums.begin(), nums.end(), greater<int>());
        int n = nums.size();
        for (int i = 1; i <= n; ++i) {
            if (nums[i - 1] >= i && (i == n || nums[i] < i)) {
                return i;
            }
        }
        return -1;
    }
};

**思路三：**模拟（计数+枚举）

V1.0

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int specialArrayvector<int>& nums) {
        int cnts[1010];
        for (int x : nums) cnts[x]++;
        for (int i = 1009, tot = 0; i >= 0; i--) {
            tot += cnts[i];
            if (i == tot) return i;
        }
        return -1;
    }
}

为什么说如果存在一定是唯一的呢？个数和值的单调性是相反的，参考判断的值越大，那对应满足条件的个数就越小。而将数组降序或者升序排序后，判断个数与值大小的顺序就要与数组的升降序相反。个数的变化是严格单调的。因此如果有满足条件的交点特征值，那这个值一定也是唯一的！

可以理解为两条线的n个点：横坐标范围为1到n，一条是可能不严格单调的折线纵坐标为排序后的数组值nums，另一条是严格单调(斜率为1)纵坐标为1到n的直线，这样最多只会有一个交点。

V2.0

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    int specialArray(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        for (int x = 1, n = nums.size(); x <= n; ++x) {
            if (x == n - (lower_bound(nums.begin(), nums.end(), x) - nums.begin()))                    return x;
        }
        return -1;
    }
};

思路四: 排序+枚举+二分**

V1.0 ：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int specialArray(vector<int>& nums) {
    int n = nums.size();
    sort(nums.begin(),nums.end(),greater<int>());
    for (int x = 0; x < 1010; x++) {
        int l = 0, r = n - 1;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (nums[mid] >= x) r = mid;
            else l = mid + 1;
        }
        if (nums[r] >= x && x == n - r) return x;
    }
    return -1;
};

排序的基础上，二分暴力。

V2.0 放弃枚举，在枚举数据上继续二分(两次二分)。

670.最大交换

思路一：将原 int 放到数组里，再copy 一份降序数组，比对两数组，生成int

V1.0

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
class Solution {
public:
    int maximumSwap(int num) {
        //初始化数组和数组副本
        vector<int> v,v1; 
        int count = 1 , dummy = 10;
        while(num/dummy!=0){count++; dummy*=10;} 
        while(count--){dummy/=10;v.push_back((num/dummy)%10);} 
        v1 = v;
        sort(v1.begin(),v1.end(),greater<int>());
        
        if(v1==v) return num;
        //正着找最大值交换
        for(count=0;v[count]==v1[count];count++); //这里是找到数据直接定位
        swap(v[count],v1[count]);                 //可以遍历if来替代，更好理解。
        //倒着找被交换数
        for(int i = v.size()-1;i>=0;i--)
        {
            if(v[i]==v[count]) swap(v[i],v1[count]); 
        }
        //输出
        num = 0;
        for(int i=0;i<v.size();i++)
            num = num*10 + v[i];
        return num;

    }
};

这道题用了1h 。 比想象中要多得多。做题太慢了。以后做题要计时。

V2.0

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
class Solution {
public:
    static char cmp(char a , char b){  //辅助将string从大到小排序
        return a>b;
    }
    int maximumSwap(int num) {
        string change = to_string(num);
        string exchange = change;
        sort(exchange.begin(),exchange.end(),cmp);
    
        char small = ' ';    
        char big = ' ';
        for(int i = 0 ; i< change.size(); i++){
            if(exchange[i] != change [i]) { 
                small = change[i];
                big = exchange[i];
                change[i]= exchange[i];
                break;
            }
        }
        for(int i = change.size()-1 ; i >=0; i--){
          if(small!= ' ' && change[i] == big) {
                change[i] =small;
                break;
            }
        }

        int res = stoi(change);
        return res;
    }
};

优化：

  • 用 string 替代 vector 容器，从而规避了对 int 数据逐个写入数组的过程。
  • 通过if语句的使用，兼容了 要求数据和原数据相同的情况。（1.0版本在中间单独穿插了if，冗余）

V3.0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int maximumSwap(int num) {
        string str = to_string(num);
        string tmp = str;
        sort(tmp.rbegin(), tmp.rend());
        for (int i = 0; i < str.size(); ++i) {
            if (str[i] != tmp[i]) {
                for (int j = str.size() - 1; j >= 0; --j) {
                    if (str[j] == tmp[i]) {
                        swap(str[i], str[j]);
                        return stoi(str);
                    }
                }
            }
        }
        return num;
    }
};

减少代码长度而已。效率上和2.0一样。

思路二：暴力重排列两两交还，记录最大值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int maximumSwap(int num) {
        string charArray = to_string(num);
        int n = charArray.size();
        int maxNum = num;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                swap(charArray[i], charArray[j]);
                maxNum = max(maxNum, stoi(charArray));
                swap(charArray[i], charArray[j]);
            }
        }
        return maxNum;
    }
};

思路三：贪心 : 将最大值和最前面的值交换

V1.0 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
public:
    int maximumSwap(int num) {
        string charArray = to_string(num);
        int n = charArray.size();
        int maxIdx = n - 1;
        int idx1 = -1, idx2 = -1;
        for (int i = n - 1; i >= 0; i--) {
            if (charArray[i] > charArray[maxIdx]) {
                maxIdx = i;
            } else if (charArray[i] < charArray[maxIdx]) {
                idx1 = i;
                idx2 = maxIdx;
            }
        }
        if (idx1 >= 0) {
            swap(charArray[idx1], charArray[idx2]);
            return stoi(charArray);
        } else {  //遍历后都相等，idx没变
            return num;
        }
    }
};

V2.0:

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 {
public:
    int maximumSwap(int num) {
        string s = to_string(num);
        for(int i=1;i<s.size();++i){
            if(s[i]>s[i-1]){ //如果大于前面的值
                int idx = i;
                for(int k = idx + 1;k<s.size();k++){ 
                    if(s[idx]<=s[k]){//等号意味着相等的选靠后的
                        idx = k;        //找到后面的值的最大值 
                    }
                }
                int j = i-1;
                while(j>=0 && s[j]<s[idx]) j-= 1; //到数据最前面 
                char c = s[idx];  //交换最前面的值 和 后面的最大值
                s[idx] = s[j+1];
                s[j+1] = c;
                break;
            }
        }
        return atoi(s.c_str());
    }
};

总结：

  • atoi()函数和to_string()函数的使用
  • int 为了利用 string 容器特性的转换。
  • 双指针强化。

按照频率将数组升序排序

哈希表+排序+模拟

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
vector<int> frequencySort(vector<int>& nums) {
    multimap<int ,int,less<int> >  order;
    int rate = 0;
    sort(nums.begin(),nums.end(),greater<int>());
    for(int i=0;i<nums.size();i++)
    {
        if(i!=0&&nums[i]!=nums[i-1]){ 
            order.insert(make_pair(rate,nums[i-1]));
            rate = 0;
            }
        rate++;        //记录频率
    }
    order.insert(make_pair(rate,nums[nums.size()-1]));//最后一个数
    //记录完毕，开始整理
    int flag = 0;
    for(auto it = order.begin();it!=order.end();it++)
    {
        
        for(int i = it->first;i!=0;i--)
            nums[flag++] = it->second; 
    }
    return nums;
}

用到了map容器，哈希表+排序+模拟

优化版：（官方题解）

1
2
3
4
5
6
7
8
9
10
11
12
13
vector<int> frequencySort(vector<int>& nums) {
    unordered_map<int, int> cnt;
    for (int num : nums) {
        cnt[num]++;
    }
    sort(nums.begin(), nums.end(), [&](const int a, const int b) {
        if (cnt[a] != cnt[b]) {
            return cnt[a] < cnt[b];
        }
        return a > b;
    });
    return nums;
}

桶排序：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
vector<int> frequencySort(vector<int>& nums) {
    int rate1[110] = {0};
    int rate2[110] = {0};
    for(auto num:nums)
    {
        if(num>=0) rate1[num]++;
        else rate2[abs(num)]++;
    }
    int flag = 0;
    for(int j = 1;j<=100;j++)
    {
        for(int i = 100;i>=0;i--)
        {
            if(rate1[i]==j) 
                while(rate1[i]--) nums[flag++] = i;
        }
        for(int i = 0;i<=100;i++)
        {
            if(rate2[i]==j)
                while(rate2[i]--) nums[flag++] = -i;
        }
    }
    return nums;

带分数

100 可以表示为带分数的形式：100 = 3 + 69258 / 714。
还可以表示为：100 = 82 + 3546 / 197。
注意特征：带分数中，数字1~9分别出现且只出现一次（不包含0）。
类似这样的带分数，100 有 11 种表示法

输入一个整数num ，求它有多少种表示法。

全排列 + 枚举

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include<iostream>
using namespace std;
//全排列
//分三部分:  (1,i) (i+1,j) (j,9)  两层循环， 1<=i<=7 , i+1<=j<=8
//判断是否满足: f + (f1/f2) == num
int num,a[15];
int res;

int toNum(int a[],int l,int r)
{
    int temp = 0;
    while(l<=r)
    {
        temp = temp*10+a[l];
        l++;
    }
    return temp;
}

void swap(int &a,int &b)
{
    int temp = a;
    a = b;
    b = temp;
}

void judge()
{
    for(int i=1;i<=7;i++){
        for(int j=i+1;j<=8;j++){
            int f = toNum(a,1,i);
            int f1 = toNum(a,i+1,j);
            int f2 = toNum(a,j+1,9);
            if(f+(f1/f2)==num && f1%f2==0){
                res++;
            }
        }
    }
    
}

void perm(int a[],int l,int r)
{
    if(l==r){//到达二叉树根
        judge(); //已经拥有一个全排列数据了，判断是否满足
    }
    else{
        //还没有到二叉树根
        for(int i=l;i<=r;i++)
        {
            swap(a[l],a[i]); //原地修改
            perm(a,l+1,r);   //递归深度遍历
            swap(a[l],a[i]); //回溯
        }
    }
}

int main(void)
{
    for(int i=0;i<=9;i++) a[i] = i;
    cin>>num;
    perm(a,1,9);
    cout<<res;
    
}

快来参与讨论吧~