星星博客 »  > 

20210503:力扣第239周周赛题解

力扣第239周周赛

  • 题目
  • 思路与算法
  • 代码实现
  • 写在最后

题目

    1. 到目标元素的最小距离
      在这里插入图片描述
    1. 将字符串拆分为递减的连续值
      在这里插入图片描述
    1. 邻位交换的最小次数
      在这里插入图片描述

思路与算法

    1. 到目标元素的最小距离:直接遍历,维护结果就行。
    1. 将字符串拆分为递减的连续值:遍历操作,用到一个dfs的递归形式,注意数据大小需要用long 来存放。
    1. 邻位交换的最小次数:本题很好理解,我们先找到第k个最小秒数,再进行遍历比较,中途维护ans即可。

代码实现

    1. 到目标元素的最小距离
class Solution {
public:
    int getMinDistance(vector<int>& nums, int target, int start) {
        int ans = INT_MAX;
        for (int i = 0; i < nums.size(); ++i) {
            if (nums[i] == target) {
                ans = min(ans,abs(i - start));
            }
        }
        return ans;
    }
};
    1. 将字符串拆分为递减的连续值
class Solution {
public:
    bool splitString(string s) {
        // 去除前导0
        while (s[0] == '0') {
            s = s.substr(1,s.length() - 1);
        }
        // 如果去完前导0没了或者只剩1位,那么直接返回false
        if (s.length() <= 1) {
            return false;
        }
        // 找到前面大的那个数转为long int型的first,然后dfs判断是否满足条件
        for (int i = 1; i <= s.length() / 2 + 1; ++i) {
            long first = stol(s.substr(0,i));
            if (dfs(s,first,i)) {
                return true;
            }
        }
        return false;
    }

    // 从字符串中找到比当前first小1的值是否存在,若找到,则从找到的索引位置继续递归,i为当前first索引在s中的索引位置。
    bool dfs(string s, long first, int start) {
        long j = start, second = -1;

        // 从之前first出现的索引位置往后找,拿到的数为t,t每次增加一位,直到找完为止。
        while (j < s.length() && second < first) {
            long t = stol(s.substr(start,j - start + 1));
            if (t < first) {
                second = t;
            } else {
                break;
            }
            j++;
        }

        // 结束条件注意分类,第一类刚好遍历完所有字符,且刚好满足first比second大1
        if (j == s.length() && second == first - 1) {
            return true;
        } else if (second == first - 1) { // 第二类还未遍历完字符串,找到了second小于first刚好1,则递归即可
            return dfs(s,second,j);
        } else {
            return false;
        }
    }
};
    1. 邻位交换的最小次数
class Solution {
public:
    int getMinSwaps(string num, int k) {
        string target(num);
        for (int i = 0; i < k; ++i)
            next_permutation(target.begin(), target.end());
        
        int ans = 0, n = num.size();
        for (int i = 0; i < n; ++i) {
            if (num[i] != target[i]) {
                int j = i + 1;
                while (num[j] != target[i])
                    j++;
                for (; j > i; --j)
                    swap(num[j], num[j - 1]), ans++;
            }
        }
        
        return ans;
    }
};

写在最后

  1. 加油加油冲冲冲!

相关文章