来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/wildcard-matching

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

一、题目描述

给定一个字符串 (s) 和一个字符模式 (p) ，实现一个支持 '?' 和 '*' 的通配符匹配。

• '?' 可以匹配任何单个字符。
• '*' 可以匹配任意字符串（包括空字符串）。

两个字符串完全匹配才算匹配成功。

说明：

• s 可能为空，且只包含从 a-z 的小写字母。
• p 可能为空，且只包含从 a-z 的小写字母，以及字符 ? 和 *。

示例 1：

• 输入：s = "aa", p = "a"
• 输出：false
• 解释："a" 无法匹配 "aa" 整个字符串。

示例 2：

• 输入：s = "aa", p = "*"
• 输出: true
• 解释: '*' 可以匹配任意字符串。

示例 3：

• 输入：s = "cb", p = "?a"
• 输出：false
• 解释：'?' 可以匹配 'c', 但第二个 'a' 无法匹配 'b'。

二、题解

动态规划，使用dp[i][j]表示字符串s的第i个字符和模式串p的第j个字符的匹配状况，如果匹配上了设置为true，否则为false。

dp[i][j]何时为true：

• 当s[i] == p[j]或者p[j] == '?'的时候，只要两个字符串前面的字符匹配上（也就是dp[i - 1][j - 1] = ture），那么这里的两个字符也匹配上。

• 当s[i] == '*'的时候，有两种情况能匹配上：

  1. 字符串s的前面一个字符就已经能匹配上模式串p了，即dp[i - 1][j] = true时，如s=ab, p=ab*。
  2. 模式串p的前面一个字符已经匹配上字符串s了，即dp[i][j - 1] = true时，如s=abcd, p=ab*。
  3. 注意这里的状态并不是d[i - 1][j - 1]控制的，因为一个*可以匹配多个字符，而?只能匹配一个字符。

初始情况下：

• dp[0][0] = true：空字符串s和空字符p，匹配上。
• dp[0][j]：s为空，p不为空，只有p是*时值才为true。
• dp[i][0]：s不为空，p为空，永远不可能匹配上，都是false。

基于以上几点，就可以写出代码了。

三、代码

bool isMatch(string s, string p) {
    int i, j;
    vector<vector<bool>> dp(s.length() + 1, vector<bool>(p.length() + 1, false));

    // 初始化数组
    dp[0][0] = true;
    for (j = 1; j <= p.length(); j++) {
        if (p[j - 1] == '*')
            dp[0][j] = dp[0][j - 1];
        else
            break;
    }

    for (i = 1; i <= s.length(); i++) {
        for (j = 1; j <= p.length(); j++) {
            if ((s[i - 1] == p[j - 1] || p[j - 1] == '?'))
                dp[i][j] = dp[i - 1][j - 1];
            if (p[j - 1] == '*' && (dp[i - 1][j] || dp[i][j - 1])) {
                dp[i][j] = true;
            }
        }
    }
    return dp[s.length()][p.length()];
}

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/matrix-cells-in-distance-order

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

一、题目描述

给出 R 行 C 列的矩阵，其中的单元格的整数坐标为 (r, c)，满足 0 <= r < R 且 0 <= c < C。另外，我们在该矩阵中给出了一个坐标为 (r0, c0) 的单元格。返回矩阵中的所有单元格的坐标，并按到 (r0, c0) 的距离从最小到最大的顺序排。

其中，两单元格(r1, c1) 和 (r2, c2) 之间的距离是曼哈顿距离：|r1 - r2| + |c1 - c2|，你可以按任何满足此条件的顺序返回答案。

示例 1：

• 输入：R = 1, C = 2, r0 = 0, c0 = 0
• 输出：[[0,0],[0,1]]
• 解释：从 (r0, c0) 到其他单元格的距离为：[0,1]

示例 2：

• 输入：R = 2, C = 2, r0 = 0, c0 = 1
• 输出：[[0,1],[0,0],[1,1],[1,0]]
• 解释：从 (r0, c0) 到其他单元格的距离为：[0,1,1,2]，[[0,1],[1,1],[0,0],[1,0]] 也会被视作正确答案。

示例 3：

• 输入：R = 2, C = 3, r0 = 1, c0 = 2
• 输出：[[1,2],[0,2],[1,1],[0,1],[1,0],[0,0]]
• 解释：从 (r0, c0) 到其他单元格的距离为：[0,1,1,2,2,3]其他满足题目要求的答案也会被视为正确，例如 [[1,2],[1,1],[0,2],[1,0],[0,1],[0,0]]。

二、题目解析

思路：列出所有的节点并计算和单元格的距离，然后根据距离排序，最后返回所有的节点。

三、代码

不使用map，直接使用vector完成：

题解区看到的一个思路清晰、容易理解的代码。

class Solution {
private:
    static bool sortFunc(vector<int> &a, vector<int> &b) {
        return a[2] < b[2];
    }
public:
    vector<vector<int>> allCellsDistOrder(int R, int C, int r0, int c0) {
        int x, y, i = 0;
        vector<vector<int>> v(R*C, vector<int>(3));
        // 计算所有点的坐标和距离
        for (x = 0; x < R; x++) {
            for (y = 0; y < C; y++) {
                v[i][0] = x;
                v[i][1] = y;
                v[i][2] = abs(r0 - x) + abs(c0 - y); // 计算曼哈顿距离
                i++;
            }
        }
        // 根据曼哈顿距离排序
        sort(v.begin(), v.end(), sortFunc);
        // 弹出曼哈顿距离
        for (i = 0; i < R * C; i++) {
            v[i].pop_back();
        }
        return v;
    }
};

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/next-greater-element-iii

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

一、题目描述

给定一个32位正整数 n，你需要找到最小的32位整数，其与 n 中存在的位数完全相同，并且其值大于n。如果不存在这样的32位整数，则返回-1。

示例 1：

• 输入: 12
• 输出: 21

示例 2：

• 输入: 21
• 输出: -1

二、题目解析

题目意思梳理：给定一个数字n（假设是523486，六位数），用同样的数字组成（5、2、3、4、8、6）组合成另外一个六位数，要求这个新组成的数字是所有组合中第一个大于原数字的。注意n是32位的正整数，如果不存在的话返回-1。

看完题目可能并没有好的思路，可以先考虑一下，什么场景下会不存在这个数字。例如：

• 99999
• 98765
• 33322

可以看出的一个规律是：如果数字都是降序排列的话，是找不到一个比它大数字的。为什么呢？如果一个数，低位的数字比高位的数字都小，那么不可能存在一种办法可以把低位较小的数字放到高位去反而比原来的数字还要大的。

只存在一种情况就是把低位较大的数字和高位较小的数字对换才会比原来数字大。那也就说明，如若要找到一个比原来数大的组合，这n的内部一定存在一个数，比它右边的数字要小。进而就说明，从低位往高位，一定存在降序数列。例如：

• 95876 ==> 96578
• 82431 ==> 83124

在知晓了这个情况之后，如何取得最小值呢？

以95876为例，从低位往高位数，第一个降序的位置是[..., 5, 8, ...]，如果在这里用一个低位的大于5的数字替换掉它就可以得到一个大于95876的数字了。那么如何替换才能最小？肯定是把右边大于5的最小的数字替换过来才最小，也就是用6来替换了，替换后得到96875。

96875是最小的吗？不是，96578才是最小。96875和96578有什么区别？最后三位数字排序不一样，一个升序排列，一个降序排列。降序排列数字由大到小，排列出来肯定是大于升序序列的。

所以能总结出来的操作是：

1. 从低位往高位寻找到一个降序序列[i, i+1]，记录下i的位置。如果不存在这个序列，说明不存在符合条件的数字。
2. 如果找到了i，从i的右边开始，找到一个最小的大于i的数字，替换它。
3. 最后把i右边的数据反转，得到一个升序序列。

除此之外，还有一个要注意的问题是要考虑数据溢出，可能原始数据没有溢出，但是比它大的那个数字就溢出了。例如1999999999，比它大的最小的数字是9199999999，这个数字溢出了。

三、代码实现

3.1 考虑数字溢出

leetcode第七题“正数反转”就已经遇到过这个问题了。假设抓换后的当前数字为x，新计算出来的x = x * 10 + y。当x > INT_MAX / 10 或者x == INT_MAX / 10 && y > 7的时候，计算x会溢出，具体的可以参考：leetcode7-整数反转。

3.2 数字反转

需要实现一个函数，反转固定区间内的数字：

/*
 * 反转数组，左闭右开区间[left, right)。
 * @left 左下标，包含当前值
 * @right 右下标，不包含当前值
 */
void reverse(vector<int> &v, size_t left, size_t right) {
    int tmp;
    size_t idx;
    for (idx = left; idx < (left + right) / 2; idx++) {
        tmp = v[idx];
        v[idx] = v[right - 1 - (idx - left)];
        v[right - 1 - (idx - left)] = tmp;
    }
}

3.3 交换函数

void my_swap(int &a, int &b) {
    int c = a;
    a = b;
    b = c;
}

3.4 实现

    int nextGreaterElement(int n) {
        int x = n, output = 0;
        int i, dec_idx = -1, y;
        vector<int> v;

        // 按位放到数组中去，并按照逻辑顺序把数组反转
        while (x) {
            v.push_back(x % 10);
            x /= 10;
        }
        reverse(v, 0, v.size());

        // 找到第一个下降的元素下标
        for (i = v.size() - 1; i > 0; i--) {
            if (v[i] > v[i - 1]) {
                dec_idx = i - 1;
                break;
            }
        }
        // 没有找到
        if (i == 0)
            return -1;

        // y是最小的大于v[dec_idx]的元素的下标，它不可能是-1，一定能找到
        y = dec_idx + 1;
        for (i = dec_idx + 2; i < v.size(); i++) {
            if (v[i] > v[dec_idx] && v[i] <= v[y]) {
                y = i;
            }
        }

        // 交换
        my_swap(v[dec_idx], v[y]);
        // 反转右边的数字
        reverse(v, dec_idx + 1, v.size());

        // 把数组转换成单个数字
        for (i = 0; i < v.size(); i++) {
            // 处理数据溢出
            if (output > INT_MAX / 10 || (output == INT_MAX && v[i] > (INT_MAX % 10)))
                return -1;
            output = output * 10 + v[i];
        }

        return output;
    }

在题解中看到的一个可以优化的点是：找到i后，从i开始往右边找到一个最小的大于它的数字，可以使用二分查找来完成。不过题目限制的是32位整数，总共不超过10位，个人认为优化不明显。

实际测试中，使用这个二分法查找，执行耗时更短。

四、单元测试

测试案例的后面几个都是leetcode提交中出错的案例：

TEST(nextGreaterElement, leetcode) {
    Solution s;
    EXPECT_EQ(s.nextGreaterElement(877645132), 877645213);
    EXPECT_EQ(s.nextGreaterElement(12), 21);
    EXPECT_EQ(s.nextGreaterElement(21), -1);
    EXPECT_EQ(s.nextGreaterElement(12222333), 12223233);
    EXPECT_EQ(s.nextGreaterElement(12443322), 13222344);
    EXPECT_EQ(s.nextGreaterElement(1999999999), -1);
}

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/reverse-string

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

一、题目描述

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组char[]的形式给出。

不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

你可以假设数组中的所有字符都是ASCII码表中的可打印字符。

示例 1：

• 输入：["h","e","l","l","o"]
• 输出：["o","l","l","e","h"]

示例 2：

• 输入：["H","a","n","n","a","h"]
• 输出：["h","a","n","n","a","H"]

二、解析

从字符串开头遍历到中间位置，同时反转每个对应位置上的元素。很基础的题目，没有坑。

三、代码

class Solution {
public:
    void reverseString(vector<char>& s) {
        size_t i, len;
        char ch;

        len = s.size();
        for (i = 0; i < len / 2; i++) {
            ch = s[i];
            s[i] = s[len - 1 - i];
            s[len - 1 - i] = ch;
        }
    }
};

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/reverse-integer

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

一、题目描述

给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。

示例：

• 输入: 123
• 输出: 321

示例 2：

• 输入: -123
• 输出: -321

示例 3：

• 输入: 120
• 输出: 21

二、题解

题目很简单，基本的思路就是对n循环取模，然后乘10累加。但是问题的关键点不是在这里，关键点是数据溢出。假设传入数据比INT_MAX小，但是反转后比INT_MAX大，那就会产生溢出。

INT_MAX = 2147483647, INT_MIN = -2147483648;

假设反转后的值是output，被反转数字模10后得到y，那么output应该被设置为output * 10 + y。

此时output溢出的条件：

1. output > INT_MAX / 10或者output = INT_MAX / 10 && y > 7。
2. output < INT_MIN / 10或者output = INT_MIN / 10 && y < -8。

以第一点为例，假设此时output大于最大值除以10，那么它乘以10后肯定会大于最大值，也就会溢出。如果它等于最大值除10，那么只要y大于最大值取模，也会溢出。

三、代码

class Solution {
public:
    int reverse(int x) {
        int output = 0, y;
        while (x) {
            y = x % 10;
            if (output > INT_MAX / 10 || (output == INT_MAX / 10 && x > 7)) return 0;
            if (output < INT_MIN / 10 || (output == INT_MIN / 10 && x < -8)) return 0;
            output = output * 10 + y % 10;
            x /= 10;
        }
        return output;
    }
};

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/copy-list-with-random-pointer

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

一、题目描述

给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。要求返回这个链表的深拷贝。

我们用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个[val, random_index]表示：

• val：一个表示 Node.val 的整数。
• random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。

示例 1：

• 输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
• 输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

示例 2：

• 输入：head = [[1,1],[2,1]]
• 输出：[[1,1],[2,1]]

提示：

• -10000 <= Node.val <= 10000。
• Node.random 为空（null）或指向链表中的节点。
• 节点数目不超过 1000 。

二、题目解析

《剑指offer》原题，详细解析《剑指offer》面试题35：复杂链表的复制。

三、代码

class Solution {
private:
    /*
     * 克隆所有的节点，并串到原始节点中去
     * @head 链表的头结点
     */
    void clone_all_nodes(Node *head) {
        Node *node, *clone;
        node = head;
        while (node) {
            // 拷贝节点
            clone = new Node(node->val);
            clone->next = node->next;
            clone->random = node->random;
            // 修改p节点的下一个节点指向新创建的节点
            node->next = clone;
            // 移动p指针到下一个节点
            node = clone->next;
        }
    }

    /*
     * 修正所有克隆节点的随机指针的地址
     * @head 链表的头结点
     */
    void fix_random_nodes(Node *head) {
        // node/q节点分别表示原始节点和被克隆的节点
        Node *node, *clone;
        node = head;
        while (node) {
            clone = node->next;
            // 修正q节点的random指针，注意random可能为null
            if (clone->random)
                clone->random = clone->random->next;
            node = clone->next;
        }
    }

    Node *reconnect_nodes(Node *head) {
        Node *node, *clone;
        Node *new_head = head->next;

        node = head;
        while (node) {
            clone = node->next;
            // 备份下一个节点的指针
            node->next = clone->next;
            // 连接到新克隆的节点，注意next可能为null
            if (clone->next) {
                clone->next = clone->next->next;
            }
            node = node->next;
        }
        return new_head;
    }

public:
    Node *copyRandomList(Node *head) {
        Node *new_head;
        if (head == nullptr) {
            return nullptr;
        }
        clone_all_nodes(head);
        fix_random_nodes(head);
        new_head = reconnect_nodes(head);
        return new_head;
    }
};

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

一、题目描述

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。

例如：给定一个链表: 1->2->3->4->5, 和 n = 2。当删除了倒数第二个节点后，链表变为 1->2->3->5。

说明：

给定的 n 保证是有效的。

进阶：你能尝试使用一趟扫描实现吗？

二、题解

使用快慢指针，快指针先走n步，满指针再走，当快指针为空的时候满指针就是倒数第n个节点。

和《剑指offer》面试题22：链表中的倒数第k个节点类似，知识剑指offer中是返回倒数第n个节点，这道题目是删除倒数第n各节点，多了个删除操作。

三、代码

class Solution {
public:
    ListNode *removeNthFromEnd(ListNode *head, int n) {
        ListNode *prev, *fast, *slow;
        prev = nullptr;
        fast = head;
        slow = head;

        // 快指针先走n步
        while (fast && n--)
            fast = fast->next;

        // n大于链表长度，直接返回head
        if (!fast && n > 0)
            return head;

        // 遍历快慢指针，并备份慢指针
        while (fast != nullptr) {
            prev = slow;
            fast = fast->next;
            slow = slow->next;
        }

        // 删除节点，注意删除的节点可能是链表收尾节点
        if (prev) {
            // 如果删除的是最后一个节点，slow为空
            prev->next = slow ? slow->next : nullptr;
            return head;
        } else {
            // 删除的首节点，返回首节点的下一个节点
            return head->next;
        }
    }
};

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/range-sum-query-immutable

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

一、题目描述

给定一个整数数组 nums，求出数组从索引 i 到 j (i ≤ j) 范围内元素的总和，包含 i, j 两点。

示例：

给定 nums = [-2, 0, 3, -5, 2, -1]，求和函数为 sumRange()。

sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3

说明：

1. 你可以假设数组不可变。
2. 会多次调用 sumRange 方法。

二、题解

题目很迷幻，一眼看上去可能会误解成就是求指定区间的和，如果只是求指定区间内的和，除了遍历就没有其他办法了。而实际上整道题目的重点就是会多次调用，也就是说同一份数据，会有多个测试案例。

很容易能猜出最容易出现问题的地方就是超时了，因为实际的问题很简单，就是求和，求和只能遍历，不可能就这么简单每次就遍历求和。因此考虑的重点就在于如何在多次调用中减少时间占用。

减少计算时间的办法：缓存数据，即缓存下来部分数据的和，再根据缓存的和来计算特定范围的和。

以测试数据为例，以sum[i]表示下标i以前（不包括i）的所有数据之和，那么sum数组的值为：

0, -2, -2, 1, -4, -2, -3

sumRange(0, 2)就相当于计算sum[2 + 1] - sum[0] ，值为1。

sumRange(2, 5)就相当于计算sum[5 + 1] - sum[2]，值为-2。

在这种情况下能总结出来的规律是：sumRange(i, j) = sum[j + 1] - sum[i]。

三、代码

逻辑很简单，但关键点是：sum[i]表示的是i以前所有元素的和，所以要给sum[0]赋值上一个0值。

class NumArray {
private:
    vector<int> sum;
public:
    NumArray(vector<int>& nums) {
        // 构造函数中初始化sum数组
        size_t i;
        // 给sum[0]附上一个0值
        sum.push_back(0);
        for (i = 0; i< nums.size(); i++) {
            sum.push_back(sum[i] + nums[i]);
        }
    }

    int sumRange(int i, int j) {
        return sum[j + 1] - sum[i];
    }
};

优化

可以看到，时间消耗还是很大的，排名才击败了38%。代码中主要的耗时是vector数组的扩容导致的，因为够早的时候需要频繁push_back导致数组扩容和内存拷贝，比较费时。可以把vector改成数组形式，手动分配内存空间，减少vector频繁扩容。

class NumArray {
private:
    int *sum;
public:
    NumArray(vector<int>& nums) {
        size_t i;
        sum = new int[nums.size() + 1];
        sum[0] = 0;
        for (i = 0; i< nums.size(); i++) {
            sum[i + 1] = sum[i] + nums[i];
        }
    }

    int sumRange(int i, int j) {
        return sum[j + 1] - sum[i];
    }
};

重新提交后，时间消耗击败了86%的用户。

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/binary-search

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

一、题目描述

给定一个n个元素有序的（升序）整型数组nums和一个目标值target，写一个函数搜索nums中的 target，如果目标值存在返回下标，否则返回-1。

示例1：

• 输入：nums = [-1,0,3,5,9,12], target = 9
• 输出：4
• 解释：9出现在nums中并且下标为 4

示例 2：

• 输入：nums = [-1,0,3,5,9,12], target = 2
• 输出：-1
• 解释：2不存在nums中因此返回 -1

提示：

1. 你可以假设 nums 中的所有元素是不重复的。
2. n 将在 [1, 10000]之间。
3. nums 的每个元素都将在 [-9999, 9999]之间。

二、二分查找

二分查找的前提要求是数组有序，一趟二分查找的算法描述为：

1. 确定数组上下边界，然后取中间值mid。

2. 对比中间值mid和目标值target，此时有两种情况：

   • 如果target小于mid，说明目标值在下边界区，继续在下半边界执行步骤1。
   • 如果target大于mid，说明目标值在上边界区，继续在上半边界执行步骤1。
3. 如果上下边界一直找完都没有找到目标值，说明数组中不存在指定数据。

图文描述

在数组[2, 3, 4, 5, 6, 7, 8]中查找3。第一步，计算mid是下标为3的值5，此时5比目标值3要大，说明3出现在5左边，要在[low, mid)进行下一步查找：

第二步，重新定位修改区域，查找的下标范围是[0, 2]。此时mid计算出来等于1，下标等于1的元素值为3，刚好就是我们要找的目标值，查找完成：

三、代码

需要注意的点已经在代码中标出：

1. 注意有符号、无符号以及数据是否会溢出。当前题目中数据不大，所以直接使用int。
2. 循环结束的条件是low > high，所以循环条件一定是low <= high，不要少了等于符号。
3. 没有找到目标值的时候，返回-1。

这么简单的一个题目，提交了4次才通过。。。。基础很重要！！！

/*
* 二分查找法法
* @nums 数组
* @target 待查找的目标元素
* @return 找到返回数组下标，没找到返回-1
*/
int search(vector<int> &nums, int target) {
    // [1] 注意数据溢出
    int low, high, mid;

    low = 0;
    high = nums.size() - 1;

    // [2] 判断条件是小于等于，而不是小于
    while (low <= high) {
        mid = (low + high) / 2;
        if (target < nums[mid]) {
            high = mid - 1;
        } else if (target > nums[mid]) {
            low = mid + 1;
        } else {
            return mid;
        }
    }
    // [3] 没找到默认返回-1
    return -1;
}

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/paint-fence

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

一、题目描述

有 k 种颜色的涂料和一个包含 n 个栅栏柱的栅栏，每个栅栏柱可以用其中一种颜色进行上色。

你需要给所有栅栏柱上色，并且保证其中相邻的栅栏柱 最多连续两个 颜色相同。然后，返回所有有效涂色的方案数。

注意：n 和 k 均为非负的整数。

示例

• 输入：n = 3，k = 2
• 输出：6

• 解析：用 c1 表示颜色 1，c2 表示颜色 2，所有可能的涂色方案有

              柱 1    柱 2   柱 3     
   -----      -----  -----  -----       
     1         c1     c1     c2 
     2         c1     c2     c1 
     3         c1     c2     c2 
     4         c2     c1     c1  
     5         c2     c1     c2
     6         c2     c2     c1

二、题解

leetcode标注是简单题目，但是对我这种脑袋不太灵光的人来说，并不太简单，所以多参考了几种解题思路。

2.1 递推

假设前一个栅栏的颜色数量为f(n - 1)，再前一个栅栏的颜色数量为f(n - 2。

递推的思路：

1. 如果当前栅栏颜色和前一个栅栏颜色一样，它的选择是k - 1（因为当前栅栏和前一个栅栏颜色一样，所以前一个栅栏颜色和更前一个展览的颜色不能一样，少一种颜色选择），这种情况的颜色数量为f(n - 2) * (k - 1)。
2. 如果当前栅栏颜色和前一个栅栏颜色不一样，那么当前栅栏的颜色选择就只有k - 1种，总的颜色数量为f(n - 1) * (k - 1)。

总结出来的递推公式：f(n) = f(n - 1) * (k - 1) + f(n - 2) * (k - 1)。

代码：

class Solution {
public:
     int numWays(int n, int k) {
        int prev, pprev, rs, i;
        if (n <= 0 || k <= 0)
            return 0;

        if (n == 1)
            return k;

        pprev = k;
        prev = k * k;
        rs = prev;
        for (i = 2; i < n; i++) {
            rs = pprev * (k - 1) + prev * (k - 1);
            pprev = prev;
            prev = rs;
        }

        return rs;
    }
};

2.2 动态规划

以前面两个栅栏的颜色来确定当前栅栏的颜色：

1. 如果前两个栅栏的颜色相同，那么当前栅栏的颜色有k - 1种。
2. 如果前两个栅栏的颜色不同，那么当前栅栏的颜色有k种。

分别以dp1和dp2保存颜色相同和不同的种数，可以总结出来的状态转移方程：

• dp1 = prev_dp1
• dp2 = (k - 1) * (dp1 + dp2)

dp1是相同的颜色数量，它和上一个栅栏颜色相同，所以就等于上一个栅栏颜色数量。dp2是不同的颜色数量，它等于上一个栅栏颜色总量的和乘以k - 1。

代码：

class Solution {
public:
    int numWays(int n, int k) {
        int dp1, dp2, rs, i;
        if (n <= 0 || k <= 0)
            return 0;

        if (n == 1)
            return k;

        dp1 = k;
        dp2 = k * (k - 1);
        for (i = 2; i < n; i++) {
            rs = (dp1 + dp2) * (k - 1);
            dp1 = dp2;
            dp2 = rs;
        }
        return dp1 + dp2;
    }
};