LeetCode：27、28、35、38

27、移除元素

/*
 * @Author: 零泽
 * @LastEditors: 零泽
 * @Description:
 * @Date: 2021/04/25 11:03:16
 * @LastEditTime: 2021/04/25 11:08:30
 * @FilePath: \vscode\leetcode\27.移除元素.cpp
 */
/*
 * @lc app=leetcode.cn id=27 lang=cpp
 *
 * [27] 移除元素
 */

// @lc code=start
#include <iostream>
#include <vector>
using namespace std;
class Solution {
  public:
    /**
     * @description:
     * @event:
     * @param {vector<int>} &nums
     * @param {int} val
     * @return {*}
     */
    int removeElement(vector<int> &nums, int val) {
        int len = nums.size();
        for (int i = 0; i < len; i++) {
            if (nums.at(i) == val) {
                for (int j = i; j < len - 1; j++) {
                    nums.at(j) = nums.at(j + 1);
                }
                i--;
                len--;
            }
        }
        return len;
    }
    //一遍过
    // 113/113 cases passed (0 ms)
    // Your runtime beats 100 % of cpp submissions
    // Your memory usage beats 89.61 % of cpp submissions (8.4 MB)
    //这次成绩很好，但是用的算法是和26一样的，可26速度就很慢，不是很懂
};
// @lc code=end

28、28.实现-str-str

/*
 * @Author: 零泽
 * @LastEditors: 零泽
 * @Description:
 * @Date: 2021/04/25 11:08:59
 * @LastEditTime: 2021/04/25 11:17:13
 * @FilePath: \vscode\leetcode\28.实现-str-str.cpp
 */
/*
 * @lc app=leetcode.cn id=28 lang=cpp
 *
 * [28] 实现 strStr()
 */

// @lc code=start
#include <iostream>
#include <string.h>
using namespace std;
class Solution {
  public:
    int strStr(string haystack, string needle) {
        int haylen = haystack.length();
        int neelen = needle.length();
        if (neelen == 0) {
            return 0;
        }
        for (int i = 0; i < haylen - neelen + 1; i++) {
            if (haystack.substr(i, neelen) == needle) {
                return i;
            }
        }
        return -1;
    }
    // 79/79 cases passed (0 ms)
    // Your runtime beats 100 % of cpp submissions
    // Your memory usage beats 20.19 % of cpp submissions (6.9 MB)
};
// @lc code=end

35、搜索插入位置

/*
 * @Author: 零泽
 * @LastEditors: 零泽
 * @Description:
 * @Date: 2021/04/25 11:17:50
 * @LastEditTime: 2021/04/25 11:41:13
 * @FilePath: \vscode\leetcode\35.搜索插入位置.cpp
 */
/*
 * @lc app=leetcode.cn id=35 lang=cpp
 *
 * [35] 搜索插入位置
 */

// @lc code=start
#include <iostream>
#include <vector>
using namespace std;
class Solution {
  public:
    int searchInsert(vector<int> &nums, int target) {
        if (nums.at(0) > target) {
            nums.push_back(nums.at(nums.size() - 1));
            for (int i = nums.size() - 1; i > 0; i--) {
                nums.at(i) = nums.at(i - 1);
            }
            nums.at(0) = target;
            return 0;
        }
        for (int i = 0; i < nums.size(); i++) {
            if (nums.at(i) == target) {
                return i;
            }
            if (nums.at(i) > target && nums.at(i - 1) < target) {
                nums.push_back(nums.at(nums.size() - 1));
                for (int j = nums.size() - 1; j >= i + 1; j--) {
                    nums.at(j) = nums.at(j - 1);
                }
                nums.at(i) = target;
                return i;
            }
        }
        if (nums.at(nums.size() - 1) < target) {
            nums.push_back(target);
            return nums.size() - 1;
        }
        return -1;
    }
    // 62/62 cases passed (4 ms)
    // Your runtime beats 88.27 % of cpp submissions
    // Your memory usage beats 74.81 % of cpp submissions (9.3 MB)
    // TODO:代码有些复杂，有空的时候优化一下代码
};
// @lc code=end

38、外观数列

/*
 * @Author: 零泽
 * @Date: 2021/04/26 10:02:00
 * @LastEditors: 零泽
 * @LastEditTime: 2021/04/26 15:52:53
 * @FilePath: \vscode\leetcode\38.外观数列.cpp
 * @Description:
 */
/*
 * @lc app=leetcode.cn id=38 lang=cpp
 *
 * [38] 外观数列s
 */

// @lc code=start
#include <iostream>
#include <string.h>
using namespace std;
class Solution {
  public:
    /**
     * @Author: 零泽
     * @param {int} n
     * @return {*}
     * @description:
     * 利用pos记录每个相同区段的数字开头，和array.at(pos)不相同时开始正式操作
     * 使用递归来减少空间的使用
     */
    string countAndSay(int n) {
        if (n == 1) {
            return "1";
        }
        string array = countAndSay(n - 1);
        string temp;
        int pos = 0;
        for (int i = 1; i < array.length(); i++) {
            if (array.at(i) != array.at(pos)) {
                temp.push_back(i - pos + '0');
                temp.push_back(array.at(i - 1));
                pos = i;
            }
        }
        temp.push_back(array.length() - pos + '0');
        temp.push_back(array.at(array.length() - 1));
        return temp;
    }
    // 30/30 cases passed (4 ms)
    // Your runtime beats 82.52 % of cpp submissions
    // Your memory usage beats 91.98 % of cpp submissions (6.3 MB)
};
// @lc code=end