数据结构与算法笔记 | 分治

分治思想又被称为分类讨论，将复杂问题分为易于讨论的简单子问题，不仅是计算机学科，在解决数理问题中的应用都很广泛。

1. 分类讨论状态

LC 58 最后一个单词的长度

#define MAX_N 10002

char word[MAX_N];

class Solution {
public:
    int lengthOfLastWord(string s) {
        int N = s.size();
        int state = 0;  // 0：待读取字符串，1：字符串读取完毕，2：正在读取字符串
        memset(word, 0, sizeof(word));
        for(int i=0,j=0; i<N; ++i) {
            if(s[i]==' ') {
                if(state == 2) {
                    state = 1;
                }
            } else {
                if(state == 0) {
                    word[j++] = s[i];
                    state = 2;
                } else if(state == 1) {
                    memset(word, 0, sizeof(word));
                    j = 0;
                    word[j++] = s[i];
                    state = 2;
                } else {
                    word[j++] = s[i];
                }
            }
        }
        return strlen(word);
    }
};

2. 分类讨论余数r的情况

统计1-n的n个数中出现的1的次数

typedef long long ll;

class Solution {
public:
    int countDigitOne(int n) {
        int res = 0;
        ll base = 1;
        int rebuild = 0;
        while(n > 0) {
            int r = n % 10;
            n /= 10;
            rebuild += r*base;
            if (r == 0) {
                res += n*base;
            } else if(r==1) {
                res += n*base+(rebuild-base+1);
            } else {
                res += (n+1)*base;
            }
            base *= 10;
        }
        return res;
    }
};