LeetCode_Nov_1st_Week

November 1st：575. 分糖果
November 2nd：237. 删除链表中的节点
November 3rd： 407. 接雨水 II
November 4th： 367. 有效的完全平方数
November 5th： 1218. 最长定差子序列
November 6th： 268. 丢失的数字
November 7th： 598. 范围求和 II

---

November 1st : 575. 分糖果

偶数长度数组表示糖果的个数，要求弟弟妹妹均分后，妹妹所得糖果的最大种类数是多少。

贪心思想，对于妹妹而言，每种糖果都先取一个，已经取过的种类的糖果都给弟弟：

• 如果糖果种类数大于等于数组长度的一半，则所获最大种类数即为数组长度的一半；
• 如果糖果种类数小于数组长度的一半，则所获最大种类数即为糖果的种类数；

//version 1
class Solution {
    
public:
    int distributeCandies(vector<int>& candyType) {
    
        unordered_set<int> types;
        for(auto candy : candyType) 
            if(types.find(candy) == types.end()) 
                types.insert(candy);
        return min(types.size(), candyType.size()/2);
    }
};
//version 2
class Solution {
    
public:
	int distributeCandier(vector<int>& candyType) {
    
		return min(unordered_set<int>(candyType.begin(), candyType.end()).size(),
		           candyType.size()/2);
	}
};

---

November 2nd : 237. 删除链表中的节点

给定要删除的节点的指针作为函数参数，则我们无法得到要删除节点的pre节点。

作为替代，则将要删除节点的值赋给要删除的节点node->val = node->next->val，再将要删除节点的next指向要删除节点的next的next节点node->next = node->next->next即可。

评论：脑筋急转弯，没啥意思。

/** * 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;
    }
};

---

November 3rd : 407. 接雨水 II

使用图的广度优先遍历来解决，想一下木桶效应，对于一个被周围四个格子包围的格子而言，其储水的多少应当是：

around_height_min =  min(height_up, height_down, height_left, height_right);
height_cur > around_height_min ? height_cur - around_height_min : 0;

所以需要用到周边格子的最小高度，那么将广度优先遍历所使用的队列替换为优先队列，也即最小堆即可。

对地图进行遍历时，每次取出已遍历过的格子中最矮的那个，将其四周的格子的储水量进行计算，累加，并更新遍历集。重复这个操作，直至遍历完整个地图，即可得到题解。

class Solution {
    
public:
    int trapRainWater(vector<vector<int>>& heightMap) {
    
        int m = heightMap.size(), n = heightMap[0].size();
        if(m <= 2 || n <= 2) return 0; //若是地图长宽不均大于2，则无法接到雨水
        //创建最小堆，也即是每次从堆中取出的格子，都是堆中最矮的
        priority_queue<pair<int,int>, vector<pair<int, int>>, greater<pair<int, int>>> heap;
        //记录是否已经处理过
        vector<vector<bool>> visited(m, vector<bool>(n, false));
        //由于边界的格子不可能储水，所以将处于边界的格子加入到堆中去，并标记处理过
        for(int i = 0; i < m; ++i) {
    
            for(int j = 0; j < n; ++j) {
    
                if(i == 0 || i == m-1 || j == 0 || j == n-1) {
    
                    heap.push({
    heightMap[i][j], i*n+j});
                    visited[i][j] = true;
                }
            }
        }
        int ret = 0;
        //四个方向数组，具体方向见下
        vector<int> direct = {
    0, 1, 0, -1, 0}; //up right down left
        //只要堆不空，说明格子没有完全处理完，则继续取出进行处理
        while(!heap.empty()) {
    
            int curHeight = heap.top().first; //所取出格子的高度
            int curX = heap.top().second / n, curY = heap.top().second % n; //所取出格子的坐标
            heap.pop();
            for(int k = 0; k < 4; ++k) {
     //沿着四个方向取出在地图中且未处理的格子
                int solX = curX + direct[k], solY = curY + direct[k+1];
                if(solX > 0 && solX < m && solY > 0 && solY < n && !visited[solX][solY]) {
    
                    if(heightMap[solX][solY] < curHeight) {
     //如果旁边的格子高度小于所取格子高度，则可储水
                        ret += curHeight - heightMap[solX][solY]; //也即是进行广度优先图遍历
                    }
                    visited[solX][solY] = true; //再进行标记
                    heap.push({
    max(heightMap[solX][solY], curHeight), solX*n+solY}); //将旁边格子加入到最小堆
                    //max(heightMap[solX][solY], curHeight)对于[solX][solY]的旁边格子，储水高度是依照旁边格子的
                    //若是所取格子高度小于[solX][solY]格子，则加入堆时，应当是heightMap[solX][solY]
                }
            }
        }
        return ret;
    }
};

---

November 4th : 367. 有效的完全平方数

使用sqrt()内置函数，若是不能够完全平方，则向下取整，e.g. sqrt(5) = 2；

使用二分法，若是能够完全平方，m = l + r >> 1， ret = num / m，s.t. ret == m && num % m == 0，则是完全平方数，若是num % m != 0则说明 m 偏小(整数除法是地板除法，即5 / 2 = 2)，调整二分范围即可。

//version 1
class Solution {
    
public:
    bool isPerfectSquare(int num) {
    
        int a = sqrt(num);
        // cout << a << endl;
        if(a * a < num) return false;
        return true;
    }
};

//version 2
class Solution {
    
public:
    bool isPerfectSquare(int num) {
    
        if(num == 1) return true;
        int l = 1, r = num;
        while(l <= r) {
    
            int m = l + (r - l)/2;
            int ret = num / m;
            if(ret == m) {
    
                if(num % m == 0) return true;
                l = ++m;
            }
            else if(ret > m) l = ++m;
            else r = --m;
        }
        return false;    
    }
};

---

November 5th : 1218. 最长定差子序列

• ① 依次找到以序列中的各个元素为起点的等差数序列 $O(n)$，则 $n$ 个元素的话就有 $n$ 个序列，所以总的时间复杂度为 $O(n^2)$，超时；
• ② 动态规划，从左往右遍历 $arr$，$dp(i)$ 表示以 $arr[i]$ 为结尾的子数组中最长等差子序列长度，若有 $j=arr[i]-difference$ 且 $0<=j<i$，则 $dp(i)=dp(j)+1$，同时更新最长的等差子序列长度值。写代码时配合 hashmap 对先前是否已遍历到过 $j$ 进行记录，也即 $dp[arr[i]]=dp[arr[i]-difference]+1$。

//version 1
class Solution {
    
public:
    int longestSubsequence(vector<int>& arr, int difference) {
    
        int ret = 1;
        for(int i = 0; i < arr.size()-1; ++i) {
    
            int cur = 1, pre = i, next = i+1;
            while(next < arr.size()) {
    
                if(arr[next] - arr[pre] == difference) {
    
                    cur++;
                    ret = ret > cur ? ret : cur;
                    pre = next;
                } 
                next++;
            }
        }
        return ret;
    }
};

//version 2
class Solution {
    
public:
    int longestSubsequence(vector<int>& arr, int difference) {
    
        unordered_map<int, int> rcd;
        int ret = 1;
        for(int i = 0; i < arr.size(); ++i) {
    
            rcd[arr[i]] = rcd[arr[i] - difference] + 1;
            ret = max(ret, rcd[arr[i]]);
        }
        return ret;
    }
};

---

November 6th : 268. 丢失的数字

• ① 先排序，然后遍历，若是序号对应的元素不等于序号则该序号即为丢失的数字，若是数组中都能对应，则丢失的数据为 $n$，时间复杂度为 $O(nlgn)$，空间复杂度为 $O(1)$；
• ② 首先将 nums.size() 对应的元素定为 $-1$，对序号和序号所对应元素不匹配的情况进行元素交换，同时更新记录 $-1$ 的下标位置，将整个数组遍历一遍后，直接返回所记录的 $-1$ 下标位置即可，时间复杂度为 $O(n)$，空间复杂度为 $O(1)$；
• ③ 看了评论才知道的位运算方法，和只出现依次的数字有些相同，以 $[0,3,2]$ 为例，若是对序号和序号对应元素进行异或计算(丢失的数字只参与异或运算一次，其余数字均参与两次)，也即 3\^0\^0\^1\^3\^2\^2 = 1，即可找到丢失的数字 $1$，时间复杂度为 $O(n)$，空间复杂度为 $O(1)$；

//version 1
class Solution {
    
public:
    int missingNumber(vector<int>& nums) {
    
        sort(nums.begin(), nums.end());
        for(int i = 0; i < nums.size(); ++i) {
    
            if(i != nums[i]) return i;
        }
        return nums.size();
    }
};

//version 2
class Solution {
    
public:
    int missingNumber(vector<int>& nums) {
    
        int idx = nums.size();
        for(int i = 0; i < nums.size(); ++i) {
    
            while(nums[i] != i && nums[i] != -1) {
    
                if(nums[i] == nums.size()) {
     //-1初始位置在nums.size()
                    nums[i] = -1;
                    idx = i; //对-1位置更新
                } else if(nums[i] != i) {
     //不匹配进行交换
                    int tmp_idx = nums[i], tmp = nums[tmp_idx];
                    nums[tmp_idx] = nums[i];
                    nums[i] = tmp; 
                    if(nums[i] == -1) idx = i; //对-1位置更新
                }
            }
        }
        return idx;
    }
};

//version 3
class Solution {
    
public:
    int missingNumber(vector<int>& nums) {
    
        int ret = nums.size(); //对应上题解中3
        for(int i = 0; i < nums.size(); ++i) {
    
            ret ^= nums[i]; //对应上题解中nums[i]
            ret ^= i; //对应上题解中i
        }
        return ret; //返回丢失的数字
    }
};

---

November 7th : 598. 范围求和 II

找到操作中最小的行数和列数，返回最小的行数和最小的列数的乘积即可。需要注意的是当无操作的时候，整个矩阵均为 $0$，则需要返回矩阵的大小，因为矩阵所有元素都是最大整数。

class Solution {
    
public:
    int maxCount(int m, int n, vector<vector<int>>& ops) {
    
        if(ops.size() == 0) return m*n;
        int rMin = INT_MAX, cMin = INT_MAX;
        for(int i = 0; i < ops.size(); i++) {
    
            rMin = min(ops[i][0] > m ? m : ops[i][0], rMin);
            cMin = min(ops[i][1] > n ? n : ops[i][1], cMin);
        }
        return rMin * cMin;
    }
};