ARTS-week50

发表于 2019-07-14 分类于 ARTS 本文字数： 1.8k 阅读时长 ≈ 2 分钟

Algorithms

String Compression
思路: 指针i指向修改内容的位置，指针j遍历整个数组chars，当下一个字符与当前字符不相同时，直接将该字符赋值到i处，然后i++，j++；若相同，k指向j所在位置，j继续向前出发遍历所有与k处相同的字符，则相同的个数为j-k，将j-k转化为字符串s，将s的每一个字符都赋值在i所在位置开始的chars中。

class Solution {
public:
    int compress(vector<char>& chars) {
        int i = 0, j = 0, n = chars.size();
        while (j < n) {
            if (j == n - 1 || chars[j] != chars[j + 1]) {
                chars[i++] = chars[j++];
            } else {
                chars[i++] = chars[j];
                int k = j;
                while (j < n && chars[j] == chars[k]) {
                	j++;
                }
                string s = to_string(j - k);
                for (char c : s) {
                	chars[i++] = c;
                }
            }
        }
        return i;
    }
};

Find All Numbers Disappeared in an Array
思路: 将nums[i]置换到其对应的位置nums[nums[i]-1]上去，比如[4,3,2,7,8,2,3,1]，其中4应该和7交换位置，以此类推，最后得到的顺序应该是[1, 2, 3, 4, 3, 2, 7, 8]，最后在对应位置进行检验，如果nums[i]和i+1不等，将i+1存入结果res中即可。

class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        vector<int> res;
        for (int i = 0; i < nums.size(); ++i) {
            if (nums[i] != nums[nums[i] - 1]) {
                swap(nums[i], nums[nums[i] - 1]);
                --i;
            }
        }
        for (int i = 0; i < nums.size(); ++i) {
            if (nums[i] != i + 1) {
                res.push_back(i + 1);
            }
        }
        return res;
    }
};