CCF 202104-1 灰度直方圖 和 LeetCode 93 復原IP地址

CCF 202104-1 灰度直方圖

思路：

影像識別中經常用到像素矩陣問題，如卷積神經網路的卷積操作，注意像素的范圍即ASCII范圍0-255之間，本題目描述復雜（ccf一貫作風）但是核心其實是在統計：輸入n行m列個元素，且元素范圍位于0到L-1之間的整數，即[0，L），每個元素出現的次數，即輸出為L個資料，

代碼實作

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 260;
int n, m, L;
int s[N];//定義最多含有260個元素的陣列，4<=L<=256
int main()
{
    scanf_s("%d%d%d", &n, &m, &L);//輸入行數列數及多少元素
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
        {
            int x;
            scanf_s("%d", &x);//依次輸入每行每列的元素值
            s[x] ++;//累計計算當前輸入元素的出現次數
        }
    for (int i = 0; i < L; i++)
        printf("%d ", s[i]);//輸出所有元素出現的次數
    return 0;
}

LeetCode 93 復原IP地址

思路

注意：回溯是一種演算法思想，可以用遞回實作，基本是相輔相成的，回溯函式或者遞回函式其實都可以，本題屬于海大計算機技術考綱中遞回和遞推問題，可以解決字串切割、回文子串等關于字串的問題，當然遞回也可以解決多種問題，如2020年考察的八皇后問題等，
題目給定的就是一個字串，切割成4塊，判定是不是符合ip地址，那么可以使用遞回來實作，通過下圖可以看出當我們開始切割至最后我們一直在判斷當前切割的字符是不是符合ip地址，直到切割成4塊，即一條道走到黑，那么可以使用DFS（深度優先搜索）的思想，

代碼實作

class Solution {
private:
    vector<string> result;// 記錄結果
    // startIndex: 搜索的起始位置，pointNum:添加逗點的數量
    void backtracking(string& s, int startIndex, int pointNum) {
        if (pointNum == 3) { // 逗點數量為3時，分隔結束
            // 判斷第四段子字串是否合法，如果合法就放進result中
            if (isValid(s, startIndex, s.size() - 1)) {
                result.push_back(s);
            }
            return;
        }
        for (int i = startIndex; i < s.size(); i++) {
            if (isValid(s, startIndex, i)) { // 判斷 [startIndex,i] 這個區間的子串是否合法
                s.insert(s.begin() + i + 1 , '.');  // 在i的后面插入一個逗點
                pointNum++;
                backtracking(s, i + 2, pointNum);   // 插入逗點之后下一個子串的起始位置為i+2
                pointNum--;                         // 回溯
                s.erase(s.begin() + i + 1);         // 回溯刪掉逗點
            } else break; // 不合法，直接結束本層回圈
        }
    }
    // 判斷字串s在左閉右閉區間[start, end]所組成的數字是否合法
    bool isValid(const string& s, int start, int end) {
        if (start > end) {
            return false;
        }
        if (s[start] == '0' && start != end) { // 0開頭的數字不合法
                return false;
        }
        int num = 0;
        for (int i = start; i <= end; i++) {
            if (s[i] > '9' || s[i] < '0') { // 遇到非數字字符不合法
                return false;
            }
            num = num * 10 + (s[i] - '0');
            if (num > 255) { // 如果大于255了不合法
                return false;
            }
        }
        return true;
    }
public:
    vector<string> restoreIpAddresses(string s) {
        result.clear();
        if (s.size() > 12) return result; // 算是剪枝了
        backtracking(s, 0, 0);
        return result;
    }
};

當然還有一種最原始的暴力破解方式，直接把4中分割情況用四重回圈表示出來，每一重檢查當前字符塊是不是符合ip地址要求：

class Solution {
public:
    vector<string> restoreIpAddresses(string s) {
        vector<string> res;

        for (int a = 1; a < 4; a ++ )
            for (int b = 1; b < 4; b ++ )
                for (int c = 1; c < 4; c ++ )
                    for (int d = 1; d < 4; d ++ )           //abcd分別表示四段ip地址長度
                    {
                        if (a + b + c + d == s.size())      //四段長度剛好
                        {
                            string s1 = s.substr(0, a);     //分別截取四段ip地址
                            string s2 = s.substr(a, b);
                            string s3 = s.substr(a + b, c);
                            string s4 = s.substr(a + b + c);

                            if (check(s1) && check(s2) && check(s3) && check(s4))
                            {
                                string ip = s1 + '.' + s2 + '.' + s3 + '.' + s4;
                                res.push_back(ip);
                            }
                        }
                    }

        return res;
    }

    bool check(string s)        //判斷ip地址每段的第一位不為0，或只有一位且該位為0
    {
        if (stoi(s) <= 255)
            if (s[0] != '0' || (s[0] == '0' && s.size() == 1)) return true;
        
        return false;
    }
};