LeetCode 101- - 《LeetCode》

120. Triangle
122. Best Time to Buy and Sell Stock II
125. Valid Palindrome
136. Single Number
152. Maximum Product Subarraymax
189. Rotate Array
190. Reverse Bits
191. Number of 1 Bits
204. Count Primes
206. Reverse Linked List
217. Contains Duplicate
236. Lowest Common Ancestor of a Binary Tree
237. Delete Node in a Linked List
242. Valid Anagram
268. Misssing Number
283. Move Zeros
326. Power of Three
344. Reverse String
349. Intersection of Two Arrays
350. Intersection of Two Arrays II
387. First Unique Character in a String
412. Fizz Buzz
445. Add Two Numbers II
461. Hamming Distance
542. 01 Matrix
704. Binary Search
724. Find Pivot Index
852. Peak Index in Mountain Array
1103. Distribute Candies to People

120. Triangle

Array/Dynamic Programming
反向的动态规划，相比正向，不需要最后再找出最小值，了解了vector的初始化的新方式

class Solution
{
public:
    int minimumTotal(vector<vector<int>> &triangle)
    {
        vector<int> dp = triangle[triangle.size() - 1];
        for (int i = triangle.size() - 2; i >= 0; --i) //行号
        {
            for (int j = 0; j <= i; ++j) //列号
            {
                dp[j] = triangle[i][j] + (dp[j] > dp[j + 1] ? dp[j + 1] : dp[j]);
            }
        }
        return dp[0];
    }
};

122. Best Time to Buy and Sell Stock II

Greedy/Array
暴力法反而可能成了最难懂的动态规划的理解也有一定难度
暴力法也不是纯粹的暴力法，有了一定的筛选

class Solution
{
public:
    int maxProfit(vector<int> &prices)
    {
        if (prices.size() < 2)
        {
            return 0;
        }
        int count = 0;
        for (int i = 1; i < prices.size(); ++i)
        {
            if (prices[i] > prices[i - 1])
            {
                count += prices[i] - prices[i - 1];
            }
        }
        return count;
    }
};

125. Valid Palindrome

Two Pointers / String

lowb版本

class Solution
{
public:
    bool isValid(char c)
    {
        if ((c >= '0' && c <= '9') || (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z'))
        {
            return true;
        }
        return false;
    }
    void handleString(string &s)
    {
        int index = 0;
        for (int i = 0; i < s.size(); ++i)
        {
            if (isValid(s[i]))
            {
                s[index++] = s[i];
            }
        }
        s.erase(s.begin() + index, s.end());
        transform(s.begin(), s.end(), s.begin(), ::tolower);
    }
    bool isPalindrome(string s)
    {
        //因为"    "也算回文，所以还是直接预处理，而不是跳过字符比较好
        handleString(s);
        if (!s.size())
        {
            return true;
        }
        int left = 0, right = s.size() - 1;
        while (left <= right)
        {
            if (s[left++] == s[right--])
            {
                continue;
            }
            return false;
        }

        return true;
    }
};

哎，人比人，气死人
了解了 isalnum 和 tolower 还有 transform

class Solution
{
public:
    bool isPalindrome(string s)
    {
        string str = "";
        for (char c : s)
        {
            if (isalnum(c))
            {
                str += tolower(c);
            }
        }
        for (int i = 0, size = str.size(); i < size / 2; ++i)
        {
            if (str[i] != str[size - 1 - i])
            {
                return false;
            }
        }
        return true;
    }
};

136. Single Number

Bit Manipulation/Hash Table
我用了哈希表，看了题解的数学法还有异或很秀，秀秀秀

class Solution
{
public:
    int singleNumber(vector<int> &nums)
    {
        unordered_set<int> signal;
        for (int i : nums)
        {
            if (signal.find(i) != signal.end())
            {
                signal.erase(i);
            }
            else
            {
                signal.emplace(i);
            }
        }
        return *signal.begin();
    }
};

152. Maximum Product Subarraymax

Array/DynamicProgramming
发现wadliang的题解集合，似乎只比我大一岁，但却比我强多了，我好菜
wadliang还使用了直接双向遍历，保存最大值的做法，当然这样做我觉得效率比用DP低
一般来说，用数组的DP都能简化为一行或者一列

class Solution
{
public:
    int maxProduct(vector<int> &nums)
    {
        int n = nums.size();
        int ans = INT_MIN; //防止nums为空，所以不赋值为nums[0]
        int max_v = 1, min_v = 1;
        for (int i = 0; i < n; i++)
        {
            if (nums[i] < 0)
                swap(max_v, min_v);
            max_v = max(max_v * nums[i], nums[i]); //存储当前点连续乘积最大值
            min_v = min(min_v * nums[i], nums[i]); //存储当前点连续乘积最小值
            ans = max(max_v, ans);                 //保存全局最大值
        }
        return ans;
    }
};

189. Rotate Array

Array
想到了用三次反转是因为知道可以这么做，也有考虑到环状替换，明显会更好，但是代码不好写

class Solution
{
public:
    void rotate(vector<int> &nums, int k)
    {
        k %= nums.size();//k可能大于数组长度
        reverse(nums.begin(), nums.end());
        reverse(nums.begin(), nums.begin() + k);
        reverse(nums.begin() + k, nums.end());
    }
};

环状替换

class Solution
{
public:
    void rotate(vector<int> &nums, int k)
    {
        k %= nums.size();
        if (!k)//如果k == 0直接退出
        {
            return;
        }
        int count = 0;
        for (int start = 0; count < nums.size(); ++start) //当k取余后和nums.size()有整除关系时，第一个环替换完后还存在其他环，而其他情况则只需要一个环就可以替换完成，所以只能通过替换次数是否等于元素个数来判断
        {
            int index = start, previous = nums[index];
            do
            {

                index = (index + k) % nums.size();
                int temp = nums[index];
                nums[index] = previous;
                previous = temp;
                count++;

            } while (index != start); //使得最初一个元素被赋值后再退出循环
        }
    }
};

190. Reverse Bits

Bit Manipulation
我用的是从右至左的遍历，这个方法用的是从左至右，也可
wuindliang的题解方法二我能说啥，666完了

class Solution
{
public:
    uint32_t reverseBits(uint32_t n)
    {
        uint32_t res = 0;
        for (int i = 0; i < 32; ++i)
        {
            res <<= 1; //先移位，第一次是0位，第二次是1位，放在for结尾则会出错，因为32位数，实际上应该移动31次
            res |= n & 1;//res += n & 1; 也可
            n >>= 1;
        }
        return res;
    }
};

191. Number of 1 Bits

Bit Manipulation
Hamming weight 计算二进制形式中1的个数

彩笔代码

class Solution
{
public:
    int hammingWeight(uint32_t n)
    {
        int count = 0;
        while (n)
        {
            if (n % 2 == 1)
            {
                ++count;
            }
            n /= 2;
        }
        return count;
    }
};

移位运算符

class Solution
{
public:
    int hammingWeight(uint32_t n)
    {
        unsigned int mask = 1;//需要使用unsigned int，否则移位操作会报错
        int bits = 0;
        for (int i = 0; i < 32; ++i)
        {
            if ((n & mask) != 0)
            {
                ++bits;
            }
            mask <<= 1;//左移一位
        }
        return bits;
    }
};

天秀操作

class Solution
{
public:
    int hammingWeight(uint32_t n)
    {
        int bits = 0;
        while (n)
        {
            bits++;
            n &= (n - 1);
        }
        return bits;
    }
};

204. Count Primes

Hash Table / Math
彩笔版本

class Solution
{
public:
    bool isPrime(int n)
    {
        for (int i = 2; i * i <= n; ++i)
        {
            if (n % i == 0)
            {
                return false;
            }
        }
        return true;
    }
    int countPrimes(int n)
    {
        int count = 0;
        for (int i = 2; i < n; ++i)
        {
            if (isPrime(i))
            {
                ++count;
            }
        }
        return count;
    }
};

Sieve of Eratosthenes 牛皮啊，直接看算法的提示可能可以更快的了解这个算法

class Solution
{
public:
    int countPrimes(int n)
    {
        vector<int> prime(n, 1);
        int count = 0;
        for (int i = 2; i * i < n; ++i)
        {
            if (!prime[i])
            {
                continue;
            }
            for (int j = i * i; j < n; j += i)
            {
                //不能在这里算不是质数的数量，因为还是存在一些重复计算，比如2算过的12还会被3计算
                prime[j] = 0;
            }
        }
        for (int i = 2; i < n; ++i)
        {
            if (prime[i])
            {
                ++count;
            }
        }
        return count;
    }
};

206. Reverse Linked List

Linkde List

迭代

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution
{
public:
    ListNode *reverseList(ListNode *head)
    {
        /*原版
        if (head == NULL)
        {
            return NULL;
        }
        ListNode *next = head->next, *temp;
        head->next = NULL;
        while (next)
        {
            temp = next;
            next = next->next;
            temp->next = head;
            head = temp;
        }
        return head;
        */
        //优化版
        ListNode *pre = NULL, *temp;
        while (head)
        {
            temp = head;
            head = head->next;
            temp->next = pre;
            pre = temp;
        }
        return pre;   

    }
};

递归版
递归法想起来有点困难，这个可以帮助理解以下，其实觉得还是迭代法比较好，不过多个思路也行吧
这个代码里的reutrn是把尾节点一路给传回来

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution
{
public:
    ListNode *reverseList(ListNode *head)
    {
        if (head == NULL || head->next == NULL)//可能传进来就是空链表
        {
            return head;
        }
        ListNode *res = reverseList(head->next);
        head->next->next = head;
        head->next = NULL;//防止成环，中间过程不加可能没有影响，但是链首的最后逆置会有问题
        return res;
    }
};

217. Contains Duplicate

Array/Hash Table

class Solution
{
public:
    bool containsDuplicate(vector<int> &nums)
    {
        unordered_set<int> signal;
        for (int i : nums)
        {
            if (signal.find(i) != signal.end())
            {
                return true;
            }
            signal.emplace(i);
        }
        return false;
    }
};

神奇的是看了这道题提交结果界面的范例，很明显无逻辑且错误

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        for (int i = 1; i < nums.size(); i++) {
           for (int j = i - 1; j >= 0; j--) {
               if (nums[i] > nums[j]) {
                   break;
               } else if (nums[i] == nums[j]) {
                   return true;
               }
           }

       }
       return false;
    }
};

236. Lowest Common Ancestor of a Binary Tree

Tree
其实还是DFS遍历的问题，但还是不熟悉
这两个题解都不错题解1 题解2 题解1甚至写的更好些，思想更精妙
有想法很重要，但能写出来来也很重要

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution
{
public:
    TreeNode *ans;
    bool dfs(TreeNode *root, TreeNode *p, TreeNode *q)
    {
        if (root == nullptr)
            return false;
        bool lson = dfs(root->left, p, q);
        bool rson = dfs(root->right, p, q);
        if ((lson && rson) || ((root->val == p->val || root->val == q->val) && (lson || rson)))
        {
            ans = root;
        }
        return lson || rson || (root->val == p->val || root->val == q->val);
    }
    TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q)
    {
        dfs(root, p, q);
        return ans;
    }
};

237. Delete Node in a Linked List

Linked List
题目有点绕，读懂需要一会

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution
{
public:
    void deleteNode(ListNode *node)
    {
        node->val = node->next->val;
        node->next = node->next->next;
        //还可以一行代码解决问题，直接替换指针指向对象
        //*node = *(node->next);
    }
};

242. Valid Anagram

Sort / Hash Table
沙雕题目，anagram 的定义 tm 都不给一个，为什么“a”和“a”也算 anagram 了，「is a word the valid anagram of itself」，好像解答的人多是做就完事了，什么都没有疑问，我还去了外网看了「Is “a” a anagram of “a”?」，2015年就有的疑惑，到现在也没有解决，还有一个问题，Follow up 给出的问题，有 Unicode Letter怎么办，都 tm 不说清楚是要删除还是干什么，Unicode Letter 和 Anagram 定义中的 Letter 是一回事吗，有包含关系吗？ mmp 到是学了个数据类型转换的函数 lexical_cast(object) 还学会了 unorderd_map 的 foreach 遍历，其中的数据类型为 pair，要获取元素的方式为 .first 和 .second

class Solution
{
public:
    /* 
    void handleString(string &s){
        int index=0;
        for(int i =0;i<s.size();++i){
            if(lexical_cast<int>(s[i])<128){
                s[index++]=s[i];
            }
        }
        s.erase(s.begin()+index,s.end());
    }*/
    bool isAnagram(string s, string t)
    {
        //unicode是ascii的超集
        //----------------
        if (s.size() != t.size()) //长度不同直接返回
        {
            return false;
        }
        if (s.size() == 0)//因为count计数，若长度为0，相同则返回false，此时s和t长度必相同
        {
            return true;
        }
        int count = 0;
        unordered_map<char, int> record;
        for (int i = 0; i < s.size(); ++i)
        {
            if (s[i] == t[i])
            {
                ++count;
            }
            ++record[s[i]];
            --record[t[i]];
        }
        if (count == s.size())
        {
            return false;
        }
        for (auto a : record_s)
        {
            if (!a.second)//不为0
            {
                return false;
            }
        }
        return true;
    }
};

268. Misssing Number

Bit Manipulation / Array /Math

最初的彩笔代码

class Solution
{
public:
    int missingNumber(vector<int> &nums)
    {
        int max_num = 0, sum = 0;
        for (int i : nums)
        {
            max_num = max(i, max_num);
            sum += i;
        }
        if (max_num + 1 == nums.size())//可能没有缺失，缺失的是最后一位数字
        {
            return max_num + 1;
        }
        else
        {
            return (0 + max_num) * (max_num + 1) / 2 - sum;
        }
    }
};

优化版

class Solution
{
public:
    int missingNumber(vector<int> &nums)
    {
        int sum = 0; //根本不用计算最大值，目标数列的最大值就是数组长度，因为数列从0开始
        for (int i : nums)
        {
            sum += i;
        }

        return nums.size() * (nums.size() + 1) / 2 - sum; //目标数列和减去实际数列和
        //目标数列数组个数为nums.size()+1，头为0，尾为nums.size()，这里直接省略了0
    }
};

异或确实是有点NP，可以多了解一下。相同为0，不同为1，同时异或满足交换律，所以目标数列的所有值加上现有数列全部异或一次，就可以获得缺失的数字

class Solution
{
public:
    int missingNumber(vector<int> &nums)
    {
        int aim = nums.size(); //目标数列最大值，其余用下标代替
        for (int i = 0; i < nums.size(); ++i)
        {
            aim ^= i ^ nums[i];
        }

        return aim;
    }
};

283. Move Zeros

Array/Two Pointers
善用swap

class Solution
{
public:
    void moveZeroes(vector<int> &nums)
    {
        int index = 0;
        for (int i = 0; i < nums.size(); ++i)
        {
            if (nums[i])//不为0
            { 
                nums[index++] = nums[i];
                //swap(nums[index++], nums[i]);
                //使用swap，不需要最后的置0
            }
        }

        for (; index < nums.size(); ++index)
        {
            nums[index] = 0;
        }
    }
};

326. Power of Three

Math
题解解法很多，基准转换加正则真的厉害了，还可以使用log来做
还是要多熟悉int以外的数字类型，还要了解return可以直接返回判断结果
骚的解答方式真的是一堆，直接把结果给写了出来
这个更是骚了 return n > 0 && 1162261467 % n == 0;

class Solution
{
public:
    bool isPowerOfThree(int n)
    {
        int index = 1;
        while (index < n && index <= INT_MAX / 3)
        {
            index *= 3;
        }
        if (index == n)
        {
            return true;
        }
        return false;
    }
};

代码优化

class Solution
{
public:
    bool isPowerOfThree(int n)
    {
        long long index = 1;
        while (index < n)
        {
            index *= 3;
        }
        return index == n;
    }
};

//----------除法--------------
class Solution
{
public:
    bool isPowerOfThree(int n)
    {
        if (n < 1) //若n=0，不加判断则超出时间限制
        { 
            return false;
        }

        while (n % 3 == 0)
        {
            n /= 3;
        }

        return n == 1;
    }
};

344. Reverse String

Two Pointers / String
Python的reverse函数使用了递归的方式，但C++却不同，不同的语言实现方式可能不同吧

class Solution
{
public:
    void reverseString(vector<char> &s)
    {
        for (int i = 0; i < s.size() / 2; ++i)
        {
            swap(s[i], s[s.size() - 1 - i]);
        }
    }
};

349. Intersection of Two Arrays

Sort / Hash table / Two Pointers / Binary Search
了解了 set、unordered_set 的使用，与 vector 之间的转换

class Solution
{
public:
    vector<int> intersection(vector<int> &nums1, vector<int> &nums2)
    {
        unordered_set<int> n(nums1.begin(), nums1.end());
        vector<int> result;
        for (auto i : nums2)
        {
            if (n.find(i) != n.end())
            {
                n.erase(i);//nums2中可能存在重复值，所以n中需要删去，否则结果中会有重复值
                result.push_back(i);
            }
        }
        return result;
    }
};

350. Intersection of Two Arrays II

Sort/Hash Table/Two Pointers/Binary Search
官方题解的解法三完全不了解，看来还得补修C++ 进阶问题
原来.being()还可以写成begin()

class Solution
{
public:
    vector<int> intersect(vector<int> &nums1, vector<int> &nums2)
    {
        vector<int> res;
        unordered_map<int, int> signal;
        for (int i : nums1)
        {
            signal.count(i) ? signal[i]++ : signal[i] = 1;//存在则自增，否则添加
        }
        for (int i : nums2)
        {
            if (signal.count(i))
            {
                signal[i]--;
                res.push_back(i);
                if (!signal[i])//value为0则删除
                {
                    signal.erase(i);
                }
            }
        }
        return res;
    }
};

387. First Unique Character in a String

Hash Table / String
还在想一遍遍历能不能做出来，但是那样对哈希表又不能简单的使用了，有时候还是要老老实实做

class Solution
{
public:
    int firstUniqChar(string s)
    {
        unordered_map<char, int> map;
        for (char c : s)
        {
            ++map[c];//可以直接创建map[c]，不需要先map[c]=0
        }
        for (int i = 0; i < s.size(); ++i)
        {
            if (map[s[i]] == 1)
            {
                return i;
            }
        }
        return -1;
    }
};

412. Fizz Buzz

再简单的题，也能从题解里学到点东西

class Solution
{
public:
    vector<string> fizzBuzz(int n)
    {
        vector<string> res;
        for (int i = 1; i <= n; ++i)
        {
            if (i % 15 == 0)
            {
                res.emplace_back("FizzBuzz");
            }
            else if (i % 5 == 0)
            {
                res.emplace_back("Buzz");
            }
            else if (i % 3 == 0)
            {
                res.emplace_back("Fizz");
            }
            else
            {
                res.emplace_back(to_string(i));
            }
        }
        return res;
    }
};

一次优化

class Solution
{
public:
    vector<string> fizzBuzz(int n)
    {
        vector<string> res;
        for (int i = 1; i <= n; ++i)
        {
            //少了15的求余数判断，但是多了个ans的是否为空的判断，应该还是少了些的
            string ans = "";
            if (i % 3 == 0)
            {
                ans+="Fizz";
            }
            if (i % 5 == 0)
            {
                ans+="Buzz";
            }
            if(ans.empty())
            {
                ans+=to_string(i);
            }
            res.emplace_back(ans);
        }
        return res;
    }
};

方便扩展版本

class Solution
{
public:
    vector<string> fizzBuzz(int n)
    {
        map<int, string> dict = {{3, "Fizz"}, {5, "Buzz"}};//map自带排序，红黑树

        vector<string> res;
        for (int i = 1; i <= n; ++i)
        {
            string ans = "";
            for (pair p : dict)
            {
                if (i % p.first == 0)
                {
                    ans += p.second;
                }
            }

            if (ans.empty())
            {
                ans += to_string(i);
            }
            res.emplace_back(ans);
        }
        return res;
    }
};

445. Add Two Numbers II

Linked List
~~不反转就用栈~~ 这个题解没用栈，也是一种方法

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution
{
public:
    ListNode *addTwoNumbers(ListNode *l1, ListNode *l2)
    {
        stack<int> s1, s2;
        while (l1)
        {
            s1.push(l1->val);
            l1 = l1->next;
        }
        while (l2)
        {
            s2.push(l2->val);
            l2 = l2->next;
        }
        int carry = 0, a, b, cur;
        ListNode *head = nullptr;
        while (!s1.empty() || !s2.empty() || carry != 0)
        {
            a = s1.empty() ? 0 : s1.top();
            b = s2.empty() ? 0 : s2.top();
            if (!s1.empty())
                s1.pop();
            if (!s2.empty())
                s2.pop();
            cur = a + b + carry;
            carry = cur / 10;
            cur %= 10;
            ListNode *curnode = new ListNode(cur);
            curnode->next = head;
            head = curnode;
        }
        return head;
    }
};

461. Hamming Distance

Bit Manipulation

low逼版本，学吧，哎

class Solution
{
public:
    int hammingDistance(int x, int y)
    {
        int mask = 1, index1, index2, count = 0;
        for (int i = 0; i < 31; ++i)
        {
            index1 = mask & x;
            index2 = mask & y;
            count += (index1 != index2);
            mask <<= 1;
        }
        return count;
    }
};

优化版
直接转换到 191 题的解法，还是菜啊我

class Solution
{
public:
    int hammingDistance(int x, int y)
    {
        int n = x ^ y, count = 0;//^,&都是对每一位都实施操作
        while (n)
        {
            ++count;
            n &= (n - 1);
        }
        return count;
    }
};

542. 01 Matrix

Depth-first Search / Breadth-first Search Dynamic Programming(我加的标签)

Depth-first Search 广度优先搜索不用考虑会不会存在更短的路径，因为如果有更短的路径那么肯定提前已经入队了，但是深度优先搜索就需要考虑这个问题了，因为确实可能存在更短的路径，这个题解就是将DFS的，思路感觉不错，将周围全是1的1，即距离必为2及以上的值先设置为极大值，再求最短路径
这个题解动态规划原理讲的不错，和DFS一样设置极大值

class Solution
{
public:
    vector<vector<int>> updateMatrix(vector<vector<int>> &matrix)
    {
        int m = matrix.size(), n = matrix[0].size();
        int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        vector<vector<int>> dist(m, vector<int>(n));
        vector<vector<int>> seen(m, vector<int>(n));
        queue<pair<int, int>> q;
        for (int i = 0; i < m; ++i)
        {
            for (int j = 0; j < n; ++j)
            {
                if (matrix[i][j] == 0)
                {
                    q.emplace(i, j);//入队居然不用写pair(i,j),直接传递两个参数就可以了
                    seen[i][j] = 1;
                }
            }
        }

        while (!q.empty())
        {
            auto [i, j] = q.front();    //看来需要了解一下auto的用法了，不知道C++也可以这么写了
            q.pop();
            for (int d = 0; d < 4; ++d)
            {
                int ni = i + dirs[d][0];
                int nj = j + dirs[d][1];
                if (ni >= 0 && ni < m && nj >= 0 && nj < n && !seen[ni][nj])
                {
                    dist[ni][nj] = dist[i][j] + 1;
                    q.emplace(ni, nj);
                    seen[ni][nj] = 1;
                }
            }
        }

        return dist;
    }
};

704. Binary Search

Binary Search
了解了二分查找的用法，还了解了一些进阶形式，二分查找其实并不简单，细节很多

class Solution
{
public:
    int search(vector<int> &nums, int target)
    {
        int left = 0, right = nums.size() - 1, middle;
        while (left <= right)
        {
            middle = left + (right - left) / 2;
            if (nums[middle] == target)
            {
                return middle;
            }
            else if (nums[middle] > target)
            {
                right = middle - 1;
            }
            else
            {
                left = middle + 1;
            }
        }
        return -1;
    }
};

724. Find Pivot Index

Array

错误版本，因为存在负数，所以这种写法错误

class Solution
{
public:
    int pivotIndex(vector<int> &nums)
    {
        if (nums.empty())
        {
            return -1;
        }
        int left = 0, right = nums.size() - 1, sum = 0;
        while (left < right)
        {
            if (sum > 0)
            {
                sum -= nums[right--];
            }
            else
            {
                sum += nums[left++];
            }
        }
        if (!sum)
        {                 //如果不加前面nums.size()的判断，那么数组长度小于2时就会出错
            return left; //因为最后的位置是
        }
        else
        {
            return -1;
        }
    }
};

Answer

class Solution
{
public:
    int pivotIndex(vector<int> &nums)
    {
        int sum = 0, left_sum = 0;
        for (const int &i : nums)
        {
            sum += i;
        }
        for (int i = 0; i < nums.size(); ++i)
        {
            if (left_sum * 2 + nums[i] == sum)
            {
                return i;
            }
            left_sum += nums[i];
        }
        return -1;
    }
};

852. Peak Index in Mountain Array

Binary Search

class Solution
{
public:
    int peakIndexInMountainArray(vector<int> &A)
    {
        int left = 0, right = A.size() - 1;
        while (left <= right)
        {
            int mid = left + (right - left) / 2;
            if (A[mid] > A[mid - 1] && A[mid] > A[mid + 1])
            {
                return mid;
            }
            else if (A[mid] < A[mid + 1])
            {
                left = mid + 1;
            }
            else
            {
                right = mid - 1;
            }
        }
        return left;//写了只是为了编译不报错，给定的初始条件决定了不会运行到这一句
    }
};

1103. Distribute Candies to People

Math
直接用了暴力做法一遍遍循环，但实际上应该有数学做法，但是嫌写起来麻烦，想想还是暴力法算了，一开始还想先算出能完美分所有人几遍，但看了解答发现计算能给出几份完美的礼物显然更好
都忘了vector设置长度的方式，菜了菜了

class Solution
{
public:
    vector<int> distributeCandies(int candies, int num_people)
    {
        vector<int> res(num_people);
        int index = 0, number = 1;
        while (candies >= number)
        {
            res[index] += number;
            candies -= number++;
            index = index == num_people - 1 ? 0 : index + 1;
        }
        res[index] += candies;
        return res;
    }
};

优化暴力法，暴力法都写不完美，菜鸡啊啊啊啊

class Solution
{
public:
    vector<int> distributeCandies(int candies, int num_people)
    {
        vector<int> res(num_people, 0);
        int index = 0;
        while (candies > 0)
        {
            res[index % num_people] += min(candies, index + 1);
            candies -= index + 1;
            index++;
        }
        return res;
    }
};