书到用时方恨少，枉我最近一直在疯狂刷题找状态，没想到关键时刻还是掉链子了。

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/binary-tree-right-side-view

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

一、题目描述

给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

示例：

• 输入: [1,2,3,null,5,null,4]
• 输出: [1, 3, 4]
• 解释:

   1            <---
 /   \
2     3         <---
 \     \
  5     4       <---

二、题解

2.1 广度优先遍历

看到题目第一个想到的就是广度优先遍历，因为右视图看到的都是每一层最右边的节点，直接通过广搜层次遍历，然后取每层最后元素即可。

2.2 深搜+递归

深搜的过程：一直读右子树的节点，直到右子树不存在，然后遍历左子树。同时，给每层数据都加上层数标记，因为遍历了右子树后还需要遍历左子树，如果当前层已经找过到了最右边的节点，就继续往下找。

三、代码

广搜代码

class Solution {
public:
    vector<int> rightSideView(TreeNode *root) {
        int i, n;
        queue<TreeNode *> q;
        TreeNode *p;
        vector<int> ans;

        if (root == nullptr) {
            return ans;
        }

        q.push(root);

        while (!q.empty()) {
            n = q.size();

            for (i = 0; i < n; i++) {
                p = q.front();
                q.pop();
                if (p->left)
                    q.push(p->left);
                if (p->right)
                    q.push(p->right);
            }

            ans.push_back(p->val);
        }

        return ans;
    }
};

深搜代码

class Solution {
private:
    void f(vector<int> &ans, int depth, TreeNode *root) {
        TreeNode *p;
        int n;

        if (root == nullptr)
            return;

        if (ans.size() <= depth) {
            ans.push_back(root->val);
        }

        if (root->right) {
            f(ans, depth + 1, root->right);
        }
        if (root->left) {
            f(ans, depth + 1, root->left);
        }
    }
public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> ans;
        f(ans, 0, root);
        return ans;
    }
};

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/edit-distance

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

一、题目描述

给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作：

1. 插入一个字符
2. 删除一个字符
3. 替换一个字符

示例 1：

• 输入：word1 = "horse", word2 = "ros"
• 输出：3

• 解释：

  horse -> rorse (将 'h' 替换为 'r')
  rorse -> rose (删除 'r')
  rose -> ros (删除 'e')

示例 2：

• 输入：word1 = "intention", word2 = "execution"
• 输出：5

• 解释：

  intention -> inention (删除 't')
  inention -> enention (将 'i' 替换为 'e')
  enention -> exention (将 'n' 替换为 'x')
  exention -> exection (将 'n' 替换为 'c')
  exection -> execution (插入 'u')

二、题目解析

这道题目和leetcode44-通配符匹配很类似，比较两个字符串之间的状态，因此也可以使用相同的办法。

以dp[i][j]表示word1的第i个字符到word2的第j字符转换需要的最小操作数，动态转移方程可以表示为：

$$\begin{equation} dp[i][j]= \begin{cases} dp[i-1][j-1] & word1[i]=word2[j]\\ min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1 & word1[i] \ne word2[j]\end{cases} \end{equation}$$

说明：如果word1[i]和word2[j]相等，那么最小操作次数就等于dp[i-1][j-1]。如果不相等，那么操作次数就应该是两个字符串的前一个字符匹配结果中的最小值加一。

三、代码

static inline int min(int x, int y) {
    return x < y ? x : y;
}

class Solution {
public:
    int minDistance(string word1, string word2) {
        int i, j, row, col;
        vector<vector<int>> dp;

        if (word1.empty() || word2.empty())
            return word1.size() + word2.size();

        row = word1.size();
        col = word2.size();
        dp.reserve(row + 1);

        for (i = 0; i <= row; i++) {
            dp.emplace_back();
            vector<int> &v = dp[i];
            dp[i].reserve(col + 1);
            for (j = 0; j <= col; j++) {
                if (j == 0) {
                    dp[i].push_back(i);
                } else if (i == 0) {
                    dp[i].push_back(j);
                } else {
                    dp[i].push_back(0);
                }
            }
        }

        for (i = 1; i <= word1.size(); i++) {
            for (j = 1; j <= word2.size(); j++) {
                if (word1[i - 1] == word2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = min(min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
                }
            }
        }
        return dp[row][col];
    }
};

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/lfu-cache

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

一、题目描述

设计并实现最不经常使用（LFU）缓存的数据结构。它应该支持以下操作：get和put。

• get(key) - 如果键存在于缓存中，则获取键的值（总是正数），否则返回 -1。
• put(key, value) - 如果键不存在，请设置或插入值。当缓存达到其容量时，它应该在插入新项目之前，使最不经常使用的项目无效。在此问题中，当存在平局（即两个或更多个键具有相同使用频率）时，最近最少使用的键将被去除。

进阶：

你是否可以在 O(1) 时间复杂度内执行两项操作？

示例：

LFUCache cache = new LFUCache( 2 /* capacity (缓存容量) */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // 返回 1
cache.put(3, 3);    // 去除 key 2
cache.get(2);       // 返回 -1 (未找到key 2)
cache.get(3);       // 返回 3
cache.put(4, 4);    // 去除 key 1
cache.get(1);       // 返回 -1 (未找到 key 1)
cache.get(3);       // 返回 3
cache.get(4);       // 返回 4

二、题目解析

LFU算法是LRU算法的改进版本，LRU算法强调最近最少使用，逐步淘汰掉很久没有使用的缓存。而LFU在LRU的基础上引入了使用频率限制，优先使用频率来淘汰缓存。在频率同等的情况下，再通过LRU淘汰较久没有使用的。

虽然只是增加了一个维度的判断，但是在逻辑和编码上，多出来的就麻烦了不止一个档次。因为题目要求在O(1)的时间复杂度内完成两项操作。对于get操作而言，如果使用哈希表来保存所有的缓存节点，可以在O(1)的时间复杂度完成。但是对于put操作来说，想要把它在O(1)的时间复杂度内插入，就不简单了，必须要有合适的数据结构来支撑才行，因为除了保存频次以外还有记录节点的使用时间。如果像LRU一样使用链表来存，每个缓存节点都要先找到合适的位置才能插入，时间复杂度是O(n)。

这里可以采取的方式是使用两个哈希表来保存所有的节点，其中一个以缓存的key值作为哈希表的key，另外一个以缓存出现的频率作为哈希表的key。假设保存所有缓存节点的哈希表为cache，保存频率的哈希表为freq，那么它的操作逻辑为：

三、代码

// 缓存节点
struct cacheNode {
    int key, val, freq; // 键
};

class LFUCache {
private:
    unordered_map<int, list<cacheNode *>> freq; // 保存所有频次的节点
    unordered_map<int, cacheNode *> cache; // 保存所有的缓存节点
    int min; // 出现最小的频次
    int capacity; // 容量
    int size; // 大小

    void incrFreq(unordered_map<int, cacheNode *>::iterator &itCache) {
        cacheNode *node;
        unordered_map<int, list<cacheNode *> >::iterator itFreq;

        node = itCache->second;

        // 找到对应频率的链表
        itFreq = freq.find(node->freq);
        if (itFreq == freq.end())
            throw logic_error("unexpect error: cannot file list in freq map");

        // 从当前链表移除
        itFreq->second.remove(node);
        if (itFreq->second.empty()) {
            freq.erase(node->freq);
            // 当前删除的节点是最小频率节点
            if (node->freq == min)
                min++;
        }

        // 增加频率
        node->freq++;
        itFreq = freq.find(node->freq);
        if (itFreq == freq.end()) {
            freq.insert(pair<int, list<cacheNode *>>(node->freq, list<cacheNode *>()));
            itFreq = freq.find(node->freq);
        }

        itFreq->second.push_front(node);
    }

    // 添加新节点
    void putNewNode(int key, int value) {
        cacheNode *node, *p;
        unordered_map<int, cacheNode *>::iterator itCache;
        unordered_map<int, list<cacheNode *> >::iterator itFreq;

        if (this->size == this->capacity) {
            // 缓存容量上限了，到使用频率最低的删除最近最少使用
            itFreq = freq.find(min);
            if(itFreq == freq.end()) // 这里必须要有节点，否则异常
                throw logic_error("unexpect error: cannot find list in min freq map");

            if (itFreq->second.empty()) // 链表的节点数量不为0
                throw logic_error("unexpect error: min freq list is empty");

            node = itFreq->second.back();
            // 弹出最近最少使用的，先清除缓存列表中的
            cache.erase(node->key);
            // 然后清除频率表中的
            itFreq->second.pop_back();
            if (itFreq->second.empty()) {
                // 如果列表中的元素删完了，完全移除key
                freq.erase(min);
            }
            this->size--;
        } else {
            node = new cacheNode;
        }
        // 给node节点赋值
        min = node->freq = 1;
        node->key = key;
        node->val = value;
        // 先插入到以频率为key的哈希表
        itFreq = freq.find(min);
        if(itFreq == freq.end()) { // 这里可能是不存在对应节点的，如果不存在，创建一个节点
            freq.insert(pair<int, list<cacheNode *>>(min, list<cacheNode *>()));
            itFreq = freq.find(min);
        }
        itFreq->second.push_front(node);
        // 然后插入到缓存哈希表
        cache.insert(pair<int, cacheNode*>(key, node));
        this->size++;
    }

    // 插入已经存在的节点
    void putExistNode(int key, int value, unordered_map<int, cacheNode *>::iterator &itCache) {
        cacheNode *node;
        unordered_map<int, list<cacheNode *> >::iterator itFreq;

        // 找到了对应的缓存，更新缓存的value，然后把频率加一
        node = itCache->second;
        node->val = value;

        incrFreq(itCache);
    }
public:
    LFUCache(int capacity) {
        this->size = 0;
        this->min = 0;
        this->capacity = capacity;
    }

    int get(int key) {
        cacheNode *node;
        unordered_map<int, cacheNode *>::iterator itCache;
        unordered_map<int, list<cacheNode *> >::iterator itFreq;

        if (capacity == 0)
            return -1;

        itCache = cache.find(key);
        if (itCache == cache.end()) // 没有找到对应的cache，直接返回
            return -1;

        incrFreq(itCache);
        return itCache->second->val;
    }

    void put(int key, int value) {
        cacheNode *node;
        unordered_map<int, cacheNode *>::iterator itCache;
        unordered_map<int, list<cacheNode *> >::iterator itFreq;

        if (capacity == 0)
            return;

        itCache = cache.find(key);
        if (itCache == cache.end()) {
            // 插入新值
            putNewNode(key, value);
        } else {
            // 更新旧值
            putExistNode(key, value, itCache);
        }
    }
};

[leetcode]125-验证回文串

这道题本身是非常简单的，但是由于审题不仔细，忽略一个细节，导致提交了6次才成功，要检讨！

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/valid-palindrome

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

一、题目描述

给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。

说明：本题中，我们将空字符串定义为有效的回文串。

示例 1：

• 输入: "A man, a plan, a canal: Panama"
• 输出: true

示例 2：

• 输入: "race a car"
• 输出: false

二、题解

思路：使用双指针，一个从前往后遍历，一个后从往前遍历。遇到非数字和字符就跳过，如果发现两个指针的字符不一样就返回false，直到两个指针汇合，返回true。

要特别注意到的是回文串也包含了数字，我就是因为没看到还包含了数字，所以提交了6次才过。一直卡在测试案例"0P"上，注意是“零+P”，不是“欧+P”。网页上的显示0和O太像了，我看成了"OP"，本地测没问题，提交就有问题，最后失败了5次才发现，看评论区才知道大家都被这个输入坑了！！

三、代码

// 判断是否是字符或数字
bool isCharOrNum(char ch) {
    return (ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z') || (ch >= '0' && ch <= '9');
}

class Solution {
public:
    bool isPalindrome(string s) {
        int i = 0, j = s.size() - 1;
        while (i < j) {
            // 跳过非字符
            if (!isCharOrNum(s[j])) {
                j--;
                continue;
            }
            if (!isCharOrNum(s[i])) {
                i++;
                continue;
            }

            // 忽略大小写
            if (tolower(s[i]) != tolower(s[j]))
                return false;
            i++, j--;
        }
        return true;
    }
};

单元测试：

#include <gtest/gtest.h>

TEST(leetcode, demo) {
    string s1("A man, a plan, a canal: Panama"), s2("race a car"), s3("OP");
    Solution s;
    EXPECT_TRUE(s.isPalindrome(s1));
    EXPECT_FALSE(s.isPalindrome(s2));
    EXPECT_FALSE(s.isPalindrome(s3));
}

TEST(leetcode, OP) {
    string s1("PO"), s2("0P");
    Solution s;
    EXPECT_FALSE(s.isPalindrome(s1));
    EXPECT_FALSE(s.isPalindrome(s2));
}

int main() {
    ::testing::InitGoogleTest();
    return RUN_ALL_TESTS();
}

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/the-masseuse-lcci

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

一、题目描述

一个有名的按摩师会收到源源不断的预约请求，每个预约都可以选择接或不接。在每次预约服务之间要有休息时间，因此她不能接受相邻的预约。给定一个预约请求序列，替按摩师找到最优的预约集合（总预约时间最长），返回总的分钟数。

注意：本题相对原题稍作改动

示例 1：

• 输入： [1,2,3,1]
• 输出： 4
• 解释： 选择 1 号预约和 3 号预约，总时长 = 1 + 3 = 4。

示例 2：

• 输入： [2,7,9,3,1]
• 输出： 12
• 解释： 选择 1 号预约、 3 号预约和 5 号预约，总时长 = 2 + 9 + 1 = 12。

示例 3：

• 输入： [2,1,4,5,3,1,1,3]
• 输出： 12
• 解释： 选择 1 号预约、 3 号预约、 5 号预约和 8 号预约，总时长 = 2 + 4 + 3 + 3 = 12。

二、题解

这道题目和198-打家劫舍几乎完全一样，思路也完全一样，代码都不用做太多更改。

思路：对于第i个用户，有2种策略选择，预约或不预约。

• 如果预约，那么说明上一个用户不能预约，只能取上上个用户的最优解加上当前用户的预约时长。
• 如果不预约，最优解就是上一个用户的最优解。

总结出来的状态转移（递推）方程：

$$dp[i] = max(dp[i-1], dp[i-2]+nums[i]])$$

三、代码实现

class Solution {
public:
    int massage(vector<int> &nums) {
        int pprev, prev, output, i;
        output = prev = pprev = 0;

        if (nums.empty()) {
            return 0;
        } else if (nums.size() == 1) {
            return nums[0];
        }

        prev = nums[0];
        for (i = 1; i < nums.size(); i++) {
            output = max(prev, pprev + nums[i]);
            pprev = prev;
            prev = output;
        }

        return output;
    }
};

单元测试：

TEST(leetcode, demo) {
    Solution s;
    // leetcode样本数据
    vector<int> v1{1, 2, 3, 1}, v2{2, 7, 9, 3, 1}, v3{2, 1, 4, 5, 3, 1, 1, 3};
    // 特殊数据
    vector<int> v4{1}, v5{1, 2}, v6;

    EXPECT_EQ(s.massage(v1), 4);
    EXPECT_EQ(s.massage(v2), 12);
    EXPECT_EQ(s.massage(v3), 12);

    // 1个元素的数组
    EXPECT_EQ(s.massage(v4), 1);
    // 2个元素的数组
    EXPECT_EQ(s.massage(v5), 2);
    // 空数组
    EXPECT_EQ(s.massage(v6), 0);
}

头一回打败全部打败100%（其实是新题提交的人太少了）：

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/middle-of-the-linked-list

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

一、题目描述

给定一个带有头结点 head 的非空单链表，返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

示例1：

• 输入：[1,2,3,4,5]
• 输出：此列表中的结点 3 (序列化形式：[3,4,5])
• 返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。

注意，我们返回了一个 ListNode 类型的对象 ans，这样：
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL

示例2：

• 输入：[1,2,3,4,5,6]
• 输出：此列表中的结点 4 (序列化形式：[4,5,6])
• 由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。

提示：

给定链表的结点数介于 1 和 100 之间。

二、题解

使用快慢指针，快指针每次走2步，慢指针每次走1步。当快指针指向null的时候慢指针就是中间节点。

问题的一个关键点是：如果有两个中间节点，返回第二个。因此要当快指针的下一个节点指向null时结束，否则结束条件是快指针的下一个节点是null。

三、代码

class Solution {
public:
    ListNode *middleNode(ListNode *head) {
        ListNode *fast, *slow;

        // 链表为空或者只有一个节点
        if (head == nullptr || head->next == nullptr) {
            return head;
        }

        // 快慢指针初始化
        fast = head->next;
        slow = head;

        while (fast != nullptr) {
            // 快慢指针分别走一步
            fast = fast->next;
            slow = slow->next;

            // 快指针在没有到达末尾的时候再走一步
            if (fast) {
                fast = fast->next;
            }
        }

        return slow;
    }
};

测试案例：

TEST(leetcode, demo) {
    int i;
    Solution s;
    ListNode *nodes[6];

    for (i = 0; i < 6; i++) {
        nodes[i] = new ListNode(i);
    }

    // 测试空链表
    EXPECT_EQ(nullptr, s.middleNode(nullptr));
    // 测试只有一个节点的链表
    EXPECT_EQ(nodes[5], s.middleNode(nodes[5]));
    // 测试有两个节点的链表
    EXPECT_EQ(nodes[4], s.middleNode(nodes[4]));
    // 测试n个节点的链表，n为奇数
    EXPECT_EQ(nodes[1], s.middleNode(nodes[1]));
    // 测试n个节点的链表，n为偶数
    EXPECT_EQ(nodes[0], s.middleNode(nodes[0]));
}

int main() {
    ::testing::InitGoogleTest();
    return RUN_ALL_TESTS();
}

一、题目描述

输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。

示例 1：

• 输入：arr = [3,2,1], k = 2
• 输出：[1,2] 或者 [2,1]

示例 2：

• 输入：arr = [0,1,2,1], k = 1
• 输出：[0]

限制：

• 0 <= k <= arr.length <= 10000
• 0 <= arr[i] <= 10000

二、题解

解法一：排序

一个最简单的思路是先对所有元素排序，然后输出前面k个元素。使用快速排序的话，时间复杂度O(nlog(n))。

解法二：时间复杂度为O(n)的快速排序

快速排序的特点是：每次排序后，标杆元素左边的元素都比它小，右边的元素都比它大。因此可以利用这一个特性，对数组中的元素进行部分排序，直到返回的标杆元素下标等于k，那么这个标杆元素的左边就是所有需要的目标数据。

相较于快排来说，只需要对目标区间（标杆元素左边或者右边）进行排序就行了，无需对左右两边的区间都进行排序。因此时间复杂度降为O(n)。

解法三：最大堆

最大堆的性质是：堆上层的元素都大于等于下层元素。因此，只要维护一个大小为k的最大堆，循环遍历数组，如果元素大于堆顶元素，就替换掉堆顶元素，重新建堆。堆里面保存的就是k个最小的元素了。时间复杂度O(nlog(k))，空间复杂度O(k)。

三、代码：

3.1 基于快排思想的算法

class Solution {
private:
    int partition(vector<int> &arr, int left, int right) {
        int i, j, key;

        if (left >= right)
            return left;

        i = left;
        j = right;

        key = arr[i];
        while (i < j) {
            while (i < j && arr[j] >= key) {
                j--;
            }
            if (i < j && arr[j] < key) {
                arr[i] = arr[j];
            }

            while (i < j && arr[i] <= key) {
                i++;
            }
            if (i < j && arr[i] > key) {
                arr[j] = arr[i];
            }
        }
        arr[i] = key;

        return i;
    }

public:
    vector<int> getLeastNumbers(vector<int> &arr, int k) {
        int idx, left, right;
        vector<int> output;

        if (arr.size() <= k)
            return arr;
        if (arr.size() == 0)
            return output;

        left = 0;
        right = arr.size() - 1;
        // 循环分区，找到第k个标杆元素
        idx = partition(arr, left, right);
        while (idx != k) {
            if (idx > k) {
                // 标杆元素的下标大于k，要在左区间继续找
                right = idx - 1;
                idx = partition(arr, left, right);
            } else {
                // 标杆元素的下标小于k，要在右区间继续找
                left = idx + 1;
                idx = partition(arr, left, right);
            }
        }

        // 预分配空间，不要直接push_back，否则会浪费很多重新开辟空间的时间
        output.reserve(k);
        for (idx = 0; idx < k; idx++) {
            output.push_back(arr[idx]);
        }

        return output;
    }
};

3.2 使用最大堆

class Solution {
private:
    // 执行最大堆化
    void maxHeapify(vector<int> &v, int idx) {
        int mid, i, left, right, largest;
        left = (idx * 2) + 1;
        right = left + 1;

        if (left < v.size() && v[left] > v[idx])
            largest = left;
        else
            largest = idx;

        if (right < v.size() && v[right] > v[largest])
            largest = right;

        if (largest != idx) {
            swap(v[largest], v[idx]);
            maxHeapify(v, largest);
        }
    }
public:
    vector<int> getLeastNumbers(vector<int> &arr, int k) {
        int i, j, len;
        vector<int> output;

        if (k >= arr.size())
            return arr;

        if (k == 0)
            return output;

        len = 0;
        output.reserve(k);

        for (i = 0; i < arr.size(); i++) {
            if (len < k) {
                // 当最大堆的元素个数小于k时，直接插入到堆
                output.push_back(arr[i]);
                len++;

                // 堆塞满后，构造最大堆
                if (len == k) {
                    for (j = k / 2; j >= 0; j--) {
                        maxHeapify(output, j);
                    }
                }

            } else {
                // 元素小于堆顶元素，替换掉首元素
                if (arr[i] < output[0]) {
                    output[0] = arr[i];
                    maxHeapify(output, 0);
                }
            }
        }

        return output;
    }
};

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/longest-palindrome

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

坚持打卡的第10天！

一、题目描述

给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。

在构造过程中，请注意区分大小写。比如 "Aa" 不能当做一个回文字符串。

注意:

假设字符串的长度不会超过 1010。

示例 1：

• 输入："abccccdd"
• 输出：7
• 解释：我们可以构造的最长的回文串是"dccaccd", 它的长度是7。

二、题解

回文串的规律：从左往右数和从右往左数的相同位置上的字符是一样的。那么要想得到回文串，必须找到成对出现的字符。

因此只要从左往右遍历所有的字符，统计出每个字符出现的次数，只要字符出现的次数超过两次，它就能成为回文串中的一员。而出现次数只有一次的字符，就只能乖乖放在最中间了，并且所有只出现一次的字符中，只能选一个放到中间。

三、代码

class Solution {
public:
    int longestPalindrome(string s) {
        int stat[52] = { 0 };
        int i, idx, cnt, flag;
        // 统计所有字符串出现的次数
        for (i = 0; i < s.size(); i++) {
            if (s[i] >= 'a' && s[i] <= 'z') {
                stat[s[i] - 'a']++;
            } else {
                stat[s[i] - 'A' + 26]++;
            }
        }

        // flag用来标记是否存在不重复的字符，可以放在最中间
        flag = 0;
        cnt = 0;
        for (i = 0; i < 52; i++) {
            if (stat[i] >= 2)
                cnt += 2 * (stat[i] / 2);

            if (!flag && stat[i] % 2)
                flag = 1;
        }
        return cnt + flag;
    }
};

来源：力扣（LeetCode）

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

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

一、题目描述

字符串压缩。利用字符重复出现的次数，编写一种方法，实现基本的字符串压缩功能。比如，字符串aabcccccaaa会变为a2b1c5a3。若“压缩”后的字符串没有变短，则返回原先的字符串。你可以假设字符串中只包含大小写英文字母（a至z）。

示例1：

• 输入："aabcccccaaa"
• 输出："a2b1c5a3"

示例2：

• 输入："abbccd"
• 输出："abbccd"
• 解释："abbccd"压缩后为"a1b2c2d1"，比原字符串长度更长。

提示：字符串长度在[0, 50000]范围内。

二、题解

一道很简单的字符串处理题型，思路：

1. 使用一个计数器保存每个重复字符的个数。
2. 遇到相同字符，计数加一。
3. 遇到不同字符，把前面的字符和计数加到输出字符串末尾，计数器归零。

三、代码

class Solution {
public:
    string compressString(string S) {
        char ch;
        int i, cnt;
        string output;
        stringstream ss;

        if (S.size() <= 1)
            return S;

        cnt = 1;
        ch = S[0];
        for (i = 1; i < S.size(); i++) {
            if (S[i] == ch) {
                cnt++;
            } else {
                // 压入到字符串流
                ss << ch << cnt;
                // 重新计数
                cnt = 1;
                ch = S[i];
            }
        }
        // 最后一个字符和计数也放到字符串流里面去
        ss << ch << cnt;
        // 打印到输出字符串
        ss >> output;

        return output.size() < S.size() ? output : S;
    }
};

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/max-area-of-island

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

一、题目描述

给定一个包含了一些 0 和 1的非空二维数组 grid , 一个 岛屿 是由四个方向 (水平或垂直) 的 1 (代表土地) 构成的组合。你可以假设二维矩阵的四个边缘都被水包围着。

找到给定的二维数组中最大的岛屿面积。(如果没有岛屿，则返回面积为0。)

示例 1：

[[0,0,1,0,0,0,0,1,0,0,0,0,0],
 [0,0,0,0,0,0,0,1,1,1,0,0,0],
 [0,1,1,0,1,0,0,0,0,0,0,0,0],
 [0,1,0,0,1,1,0,0,1,0,1,0,0],
 [0,1,0,0,1,1,0,0,1,1,1,0,0],
 [0,0,0,0,0,0,0,0,0,0,1,0,0],
 [0,0,0,0,0,0,0,1,1,1,0,0,0],
 [0,0,0,0,0,0,0,1,1,0,0,0,0]]

对于上面这个给定矩阵应返回 6。注意答案不应该是11，因为岛屿只能包含水平或垂直的四个方向的‘1’。

示例 2：

[[0,0,0,0,0,0,0,0]]

对于上面这个给定的矩阵, 返回 0。

注意: 给定的矩阵grid 的长度和宽度都不超过 50。

二、题解

和地图相关的题目求最值，第一个想到的都应该是深度优先搜索，例如求两点间的最短路径、迷宫找最短出口等，都可以用深搜来解决问题。当然，出了深搜以外，还可以通过回溯来解决。深搜实际上是递归，而回溯则是迭代。

使用深搜的思路：遍历每个地图点，如果是陆地，就往四个方向上继续蔓延，一旦遍历到非陆地或者超出地图范围了就返回。

要注意的问题是，当一个点蔓延到另外一个点后，另外一个点也可能会蔓延回来。例如A是B的左节点，B作为陆地蔓延到A后又会作为A的右节点蔓延回来。这种情况下就导致重复计算，所以为了避免重复处理，需要特殊处理这个问题。可以采取的办法是每访问到一个节点，就把它变成海洋。

输入数据需要考虑的特殊场景：空地图，地图只有一列或一行。

三、代码

class Solution {
    /*
     * @grid 地图
     * @i/j 需要计算的地图坐标
     * @row/col 地图的行数和列数
     * @return 返回相连的面积
     */
    int dfs(vector<vector<int>> &grid, int i, int j, const int row, const int col) {
        int top, bottom, left, right;
        // dfs退出条件，到达了边界，或者当前值为0
        if (i < 0 || i >= row || j < 0 || j >= col || grid[i][j] == 0)
            return 0;

        // 已经访问过的节点置为0，避免重复计算
        grid[i][j] = 0;

        // 分别计算上下左右四个方向上的面积
        top = dfs(grid, i + 1, j, row, col);
        bottom = dfs(grid, i - 1, j, row, col);
        right = dfs(grid, i, j + 1, row, col);
        left = dfs(grid, i, j - 1, row, col);

        // 返回总面积
        return top + bottom + left + right + 1;
    }

public:
    int maxAreaOfIsland(vector<vector<int>> &grid) {
        int i, j, row, col, res;

        if (grid.empty())
            return 0;

        row = grid.size();
        col = grid[0].size();

        res = 0;
        for (i = 0; i < row; i++) {
            for (j = 0; j < col; j++) {
                // 提前剪枝
                if (grid[i][j] == 0)
                    continue;

                // 遍历每一个节点
                res = max(res, dfs(grid, i, j, row, col));
            }
        }
        return res;
    }
};

测试案例：

TEST(leetcode, demo) {
    Solution s;
    vector<vector<int>> input1{
            {0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0},
            {0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0},
            {0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0},
            {0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0},
            {0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0},
            {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0},
            {0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0},
            {0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0}
    }, input2{{1}}, input3{{0,0,0,0,0,0}}, input4;

    EXPECT_EQ(s.maxAreaOfIsland(input1), 6);
    EXPECT_EQ(s.maxAreaOfIsland(input2), 1);
    EXPECT_EQ(s.maxAreaOfIsland(input3), 0);
    EXPECT_EQ(s.maxAreaOfIsland(input4), 0);
}