每日一题打卡刷题计划 2020 / 03

我第一天就没有做,因为我看到这个活动的时候已经是第二天了。
而且我每天都不打卡,因为我拒绝在Leetcode公开发表题解。

1. 反转链表 [2020.03.02]

反转一个单链表。

样例

示例 1:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

代码

我对这题有及其深的印象,因为我大一上学期期末考试之前不会做,跑去问了一个学长。这个学长不是zz,但是由于zz今天惹我生气气了所以我要特别说明此事(哼。
然而考试并没有考到,现在我也完全不记得当时他的回答是什么了……
还是蛮简单的,虽然我被卡了一小下,原因是我不记得一些链表相关知识了……
题目有提示,递归迭代两种方法。

递归

思路很简单,记录当前节点和前驱节点,一直递归到$NULL$,找到答案的头节点并返回。回溯的时候给当前节点的$next$赋值。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

ListNode* ans;
ListNode* pre;
void dfs(ListNode* now, ListNode* pre) {
    if(now == NULL) {
        ans = pre;
        return;
    }
    dfs(now->next, now);
    now->next = pre;
}

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        dfs(head, NULL);
        return ans;
    }
};

迭代

写迭代的时候卡住了一小下,因为我太久没有用指针了……如果将一个指针a赋值成另一个指针b,那么它们会指向同一片内存区域。改$b$的$next$的时候,$a$的$next$也会修改……我好春虫虫……
用一个变量$tmp$来临时记录当前$head$的前驱节点,然后不停迭代和赋值。
注意在给当前节点赋值$next$时,要先修改$head=head->next$,不然就会出现我上面说的错误qwq。

/**
 * 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) {
        ListNode* ans = NULL;
        
        while(head != NULL) {
            ListNode* tmp = ans;
            ans = head;
            head = head->next;
            ans->next = tmp;
        }
        return ans;
    }
};

2. 合并排序的数组 [2020.03.03]

给定两个排序后的数组 A 和 B,其中 A 的末端有足够的缓冲空间容纳 B。
编写一个方法,将 B 合并入 A 并排序。
初始化 A 和 B 的元素数量分别为 m 和 n。

样例

示例 1:

输入:
A = [1,2,3,0,0,0], m = 3
B = [2,5,6], n = 3
输出: [1,2,2,3,5,6]

代码

emmm,我怎么感觉这个每日打卡的题都好简单,也许以后会难起来吧。
想到了三种方法。

合并后排序

排序的复杂度还是会高一些,$O((m+n)log(m+n))$。

class Solution {
public:
    void merge(vector<int>& A, int m, vector<int>& B, int n) {
        for(int i=0; i<n; i++) A[m+i] = B[i];
        sort(A.begin(), A.end());
    }
};

双指针

一开始就是无脑用双指针做的,然后发现不对,这样会不停的修改$A$数组导致错误。
所以需要另外开辟一个长度为$m+n$的数组记录答案,空间复杂度有些高噢。

class Solution {
public:
    void merge(vector<int>& A, int m, vector<int>& B, int n) {
        vector<int> ans;
        int p1 = 0, p2 = 0;
        while(p1 < m && p2 < n) {
            if(A[p1] < B[p2]) ans.push_back(A[p1++]);
            else ans.push_back(B[p2++]);
        }
        while(p1 < m) ans.push_back(A[p1++]);
        while(p2 < n) ans.push_back(B[p2++]);
        A = ans;
    }
};

逆向双指针

感觉这个有点类似于背包问题里的逆向遍历,就是为了不让修改值覆盖原值而倒过来处理。
从$A$和$B$的尾部开始遍历,比较得来的值放入$A$的末尾。

class Solution {
public:
    void merge(vector<int>& A, int m, vector<int>& B, int n) {
        int p1 = m - 1, p2 = n - 1, now = m + n - 1;
        while(p1 >= 0 && p2 >= 0) {
            if(A[p1] < B[p2]) A[now--] = B[p2--];
            else A[now--] = A[p1--];
        }
        while(p2 >= 0) A[now--] = B[p2--];
    }
};

3. 腐烂的橘子 [2020.03.04]

在给定的网格中,每个单元格可以有以下三个值之一:

  • 值 0 代表空单元格;
  • 值 1 代表新鲜橘子;
  • 值 2 代表腐烂的橘子。
    每分钟,任何与腐烂的橘子(在 4 个正方向上)相邻的新鲜橘子都会腐烂。

返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能,返回 -1。

样例

示例 1:

输入:[[2,1,1],[1,1,0],[0,1,1]]
输出:4

示例 2:

输入:[[2,1,1],[0,1,1],[1,0,1]]
输出:-1
解释:左下角的橘子(第 2 行, 第 0 列)永远不会腐烂,因为腐烂只会发生在 4 个正向上。

示例 3:

输入:[[0,2]]
输出:0
解释:因为 0 分钟时已经没有新鲜橘子了,所以答案就是 0 。

提示

  • 1 <= grid.length <= 10
  • 1 <= grid[0].length <= 10
  • gridi 仅为 0、1 或 2

代码

按照橘子腐烂的定义,就可以看出这是一个BFS的过程。
只有一个橘子腐烂很好办,从这个橘子开始BFS,到达距离最远的那个不烂的橘子的距离即为答案。
然而现在有很多个橘子,把它们一起塞进队列就好
可以想象这个图上有一个隐形的橘子,在一切开始的前一天就把图上烂掉的橘子都污染了。按照BFS的思路,这个隐形的橘子第一个入队列,然后被取出,并塞入第一批烂掉的橘子入队列。所以,忽略掉这个隐形的橘子,把所有烂掉的橘子塞入初始队列就好啦。

class Solution {
public:
    int orangesRotting(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();

        int cnt = 0;
        int dist[105][105]; memset(dist, -1, sizeof(dist));
        queue<pair<int, int>> que;
        for(int i=0; i<n; i++) {
            for(int j=0; j<m; j++) {
                if(grid[i][j] == 2) {
                    que.push(make_pair(i, j));
                    dist[i][j] = 0;
                }
                else if(grid[i][j] == 1) cnt++;
            }
        }

        int ans = 0;
        int dx[] = {0, 0, 1, -1};
        int dy[] = {1, -1, 0, 0};
        while(!que.empty()) {
            pair<int, int> now = que.front(); que.pop();
            int x = now.first, y = now.second;
            for(int i=0; i<4; i++) {
                int tx = x + dx[i], ty = y + dy[i];
                if(tx < 0 || tx >= n || ty < 0 || ty >= m) continue;
                if(grid[tx][ty] == 0) continue;
                if(dist[tx][ty] == -1 || dist[tx][ty] > dist[x][y] + 1) {
                    dist[tx][ty] = dist[x][y] + 1;
                    que.push(make_pair(tx, ty));
                    if(grid[tx][ty] == 1) {
                        cnt--;
                        ans = max(ans, dist[tx][ty]);
                        continue;
                    }
                }
            }
        }
        return cnt == 0 ? ans : -1;
    }
};

4. 分糖果 [2020.03.05]

排排坐,分糖果。
我们买了一些糖果 candies,打算把它们分给排好队的 n = num_people 个小朋友。
给第一个小朋友 1 颗糖果,第二个小朋友 2 颗,依此类推,直到给最后一个小朋友 n 颗糖果。
然后,我们再回到队伍的起点,给第一个小朋友 n + 1 颗糖果,第二个小朋友 n + 2 颗,依此类推,直到给最后一个小朋友 2 * n 颗糖果。
重复上述过程(每次都比上一次多给出一颗糖果,当到达队伍终点后再次从队伍起点开始),直到我们分完所有的糖果。注意,就算我们手中的剩下糖果数不够(不比前一次发出的糖果多),这些糖果也会全部发给当前的小朋友。
返回一个长度为 num_people、元素之和为 candies 的数组,以表示糖果的最终分发情况(即 ans[i] 表示第 i 个小朋友分到的糖果数)。

样例

示例 1:

输入:candies = 7, num_people = 4
输出:[1,2,3,1]
解释:
第一次,ans[0] += 1,数组变为 [1,0,0,0]。
第二次,ans[1] += 2,数组变为 [1,2,0,0]。
第三次,ans[2] += 3,数组变为 [1,2,3,0]。
第四次,ans[3] += 1(因为此时只剩下 1 颗糖果),最终数组变为 [1,2,3,1]。

示例 2:

输入:candies = 10, num_people = 3
输出:[5,2,3]
解释:
第一次,ans[0] += 1,数组变为 [1,0,0]。
第二次,ans[1] += 2,数组变为 [1,2,0]。
第三次,ans[2] += 3,数组变为 [1,2,3]。
第四次,ans[0] += 4,最终数组变为 [5,2,3]。

提示

  • 1 <= candies <= 10^9
  • 1 <= num_people <= 1000

代码

暴力法

看糖果的数量是$10^9$,估算暴力不超时,所以怎么分的糖果就怎么模拟就好了。

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

数学法

// 今天忙着写代码白天没来得及写题。
// 然而现在麻麻占了书房上网课,我用着她无法手写的电脑也没有纸笔。
// 再加上昨天睡得不好现在很困,算不明白,有空再补吧qwq。


5. 和为s的连续正数序列 [2020.03.06]

输入一个正整数 target ,输出所有和为 target 的连续正整数序列(至少含有两个数)。
序列内的数字由小到大排列,不同序列按照首个数字从小到大排列。

样例

示例 1:

输入:target = 9
输出:[[2,3,4],[4,5]]

示例 2:

输入:target = 15
输出:[[1,2,3,4,5],[4,5,6],[7,8]]

提示

  • 1 <= target <= 10^5

代码

简简单单的滑动窗口,$O(n)$的复杂度遍历一遍$[1,target]$。
如果当前和小于目标,右移右指针。
如果当前和大于目标,右移左指针。
如果当前和等于目标,记录答案后右移左指针。

class Solution {
public:
    vector<vector<int>> findContinuousSequence(int target) {
        int left = 1, right = 1, sum = 1;
        vector<vector<int>> ans;
        while(right < target) {
            if(sum < target) {
                right++;
                sum += right;
            }
            else if(sum > target) {
                sum -= left;
                left++;
            }
            else {
                vector<int> now;
                for(int i=left; i<=right; i++) now.push_back(i);
                ans.push_back(now);
                sum -= left;
                left++;
            }
        }
        return ans;
    }
};

6. 队列的最大值 [2020.03.07]

请定义一个队列并实现函数 max_value 得到队列里的最大值,要求函数max_value、push_back 和 pop_front 的时间复杂度都是O(1)。
若队列为空,pop_front 和 max_value 需要返回 -1。

样例

示例 1:

输入:
[“MaxQueue”,”push_back”,”push_back”,”max_value”,”pop_front”,”max_value”]
[[],[1],[2],[],[],[]]
输出: [null,null,null,2,1,2]

示例 2:

输入:
[“MaxQueue”,”pop_front”,”max_value”]
[[],[],[]]
输出: [null,-1,-1]

提示 

  • 1 <= push_back,pop_front,max_value的总操作数 <= 10000
  • 1 <= value <= 10^5

代码

题目的重点在于找到队列中的最大值,考虑单调栈
然后又觉得单调栈有一丢丢小问题,就用队列实现了。
维护一个单调不增的双向队列,每当插入元素时,就在双向队列的队尾比较,不断弹出直至找到合适位置;每当弹出元素时,若元素为双向队列队头,将其弹出;查询最大值时,双向队列头即为答案。

class MaxQueue {
public:
    queue<int> que;
    deque<int> deq;
    MaxQueue() {
        
    }
    
    int max_value() {
        if(deq.empty()) return -1;
        return deq.front();
    }
    
    void push_back(int value) {
        que.push(value);
        if(deq.empty()) deq.push_back(value);
        else {
            while(!deq.empty() && deq.back() < value) deq.pop_back();
            deq.push_back(value);
        }
    }
    
    int pop_front() {
        if(que.empty()) return -1;
        int x = que.front(); que.pop();
        if(!deq.empty() && deq.front() == x) deq.pop_front();
        return x;
    }
};

/**
 * Your MaxQueue object will be instantiated and called as such:
 * MaxQueue* obj = new MaxQueue();
 * int param_1 = obj->max_value();
 * obj->push_back(value);
 * int param_3 = obj->pop_front();
 */

7. 零钱兑换 [2020.03.08]

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额,返回 -1。

样例

示例 1:

输入: coins = [1, 2, 5], amount = 11
输出: 3
解释: 11 = 5 + 5 + 1

示例 2:

输入: coins = [2], amount = 3
输出: -1

代码

一开始想的类似背包的DP,但是没想明白,就开始暴搜,然后剪枝失败。
然后就用DP写了。状态转移方程$F(i)=min(F(i-c_j)+1)$,其中$j∈[0,n-1]$。
很好理解,如果最后一枚硬币的面额是$c_j$,那么需要从$i-c_j$则个状态转移过来。

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int n = coins.size();
        int dp[amount+1]; memset(dp, 0x3f, sizeof(dp));
        dp[0] = 0;
        for(int i=1; i<=amount; i++) {
            for(int j=0; j<n; j++) {
                if(coins[j] <= i) dp[i] = min(dp[i], dp[i-coins[j]]+1);
            }
        }
        return dp[amount] == 0x3f3f3f3f ? -1 : dp[amount];
    }
};

8. 买卖股票的最佳时期 [2020.03.09]

给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易(即买入和卖出一支股票),设计一个算法来计算你所能获取的最大利润。
注意你不能在买入股票前卖出股票。

样例

示例 1:

输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天(股票价格 = 1)的时候买入,在第 5 天(股票价格 = 6)的时候卖出,最大利润 = 6-1 = 5 。注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。

示例 2:

输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

代码

太简单了,遍历一遍数组,边遍历边记录目前的最小值,并更新最大差值作为答案。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int ans = 0, mn = 1e9;
        for(auto u: prices) {
            if(u < mn) mn = u;
            ans = max(ans, u-mn);
        }
        return ans;
    }
};

9. 二叉树的直径 [2020.03.10]

给定一棵二叉树,你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过根结点。

样例

示例 1:

给定二叉树

      1
     / \
    2   3
   / \     
  4   5    

返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。
注意:两结点之间的路径长度是以它们之间边的数目表示。

代码

其实就是在求二叉树的深度过程中加一行更新答案的代码。
DFS求二叉树时,需要分别DFS左子树和右子树的深度,在这时记录左子树和右子树的深度和,并更新答案。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
int ans;
int dfs(TreeNode* root) {
    if(root == NULL) return 0;
    int L = dfs(root->left);
    int R = dfs(root->right);
    ans = max(ans, L + R);
    return max(L, R) + 1;
}
class Solution {
public:
    int diameterOfBinaryTree(TreeNode* root) {
        ans = 0; dfs(root);
        return ans;
    }
};

10. 将数组分成和相等的三个部分 [2020.03.11]

给你一个整数数组 A,只有可以将其划分为三个和相等的非空部分时才返回 true,否则返回 false。
形式上,如果可以找出索引 i+1 < j 且满足 (A[0] + A[1] + … + A[i] == A[i+1] + A[i+2] + … + A[j-1] == A[j] + A[j-1] + … + A[A.length – 1]) 就可以将数组三等分。

样例

示例 1:

输出:[0,2,1,-6,6,-7,9,1,2,0,1]
输出:true
解释:0 + 2 + 1 = -6 + 6 – 7 + 9 + 1 = 2 + 0 + 1

示例 2:

输入:[0,2,1,-6,6,7,9,-1,2,0,1]
输出:false

示例 3:

输入:[3,3,6,5,-2,2,5,1,-9,4]
输出:true
解释:3 + 3 = 6 = 5 – 2 + 2 + 5 + 1 – 9 + 4

提示:

  • 3 <= A.length <= 50000
  • -10^4 <= A[i] <= 10^4

代码

一开始想的是直接遍历,和如果达到$sum/3$计数加一,最后看计数值是不是$3$。然后发现在$0$的处理上有问题,例如这个数组可以被分解为$4$个$0$,那么按照这个方法会返回false,但其实任意两个相邻的$0$都可以被合并为一个。
首先预处理求前缀和。为了控制段数正好为$3$,我用了$left$和$right$两个指针,将整个数组分为$[0,left]$、$(left,right]$和$(right,n-1]$三段。
首先$left$和$right$一起向右移动直至找到第一个合适的位置,之后再移动$right$找到第二个合适的位置。

const int MAXN = 5e4 + 5;
class Solution {
public:
    bool canThreePartsEqualSum(vector<int>& A) {
        int sum[MAXN]; sum[0] = 0;
        int n = A.size();
        for(int i=0; i<n; i++) sum[i+1] = sum[i] + A[i];
        int left = 0, right = 0;
        while(left <= right && right < n) {
            int x = sum[left+1] - sum[0];
            int y = sum[right+1] - sum[left+1];
            int z = sum[n] - sum[right+1];
            if(x == sum[n] / 3 && y == sum[n] / 3 && z == sum[n] / 3 && left != right && right != n-1) 
                return true;
            if(x == sum[n] / 3) right++;
            else left++, right++;
        }
        return false;
    }
};

11. 字符串的最大公因子 [2020.03.12]

对于字符串 S 和 T,只有在 S = T + … + T(T 与自身连接 1 次或多次)时,我们才认定 “T 能除尽 S”。
返回最长字符串 X,要求满足 X 能除尽 str1 且 X 能除尽 str2。

样例

示例 1:

输入:str1 = “ABCABC”, str2 = “ABC”
输出:”ABC”

示例 2:

输入:str1 = “ABABAB”, str2 = “ABAB”
输出:”AB”

示例 3:

输入:str1 = “LEET”, str2 = “CODE”
输出:””

提示

  • 1 <= str1.length <= 1000
  • 1 <= str2.length <= 1000
  • str1[i] 和 str2[i] 为大写英文字母

代码

这题我并不会,看题解的啦,实在是太妙了。
首先,两个字符串拥有最大公因子的充要条件是$str1+str2=str2+str1$。
其次,两个字符串的最大公因子的长度为两个字符串长度的最大公因子。

class Solution {
public:
    int gcd(int x, int y) {
        if(y == 0) return x;
        return gcd(y, x % y);
    }
    string gcdOfStrings(string str1, string str2) {
        if(str1+str2 != str2 + str1) return "";
        int n1 = str1.size(), n2 = str2.size();
        int len = gcd(n1, n2);
        return str1.substr(0, len);
    }
};

12. 多数元素 [2020.03.13]

给定一个大小为 n 的数组,找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的,并且给定的数组总是存在多数元素。

样例

示例 1:

输入: [3,2,3]
输出: 3

示例 2:

输入: [2,2,1,1,1,2,2]
输出: 2

代码

这题太简单了,我知道可以$O(n)$,但是为了少写点代码就$O(nlogn)$排个序啦。
排序返回中间的数即为所求。

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        return nums[n / 2];
    }
};

13. 最长上升子序列 [2020.03.14]

给定一个无序的整数数组,找到其中最长上升子序列的长度。

样例

示例 1:

输入: [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长的上升子序列是 [2,3,7,101],它的长度是 4。

代码

动态规划

我以前一直不会写这题,这次居然直接写出来了,可喜可贺。
遍历数组,对于每一个元素进行DP。
例如,现在遍历到$nums[i]$。遍历所有下标小于$i$的元素,因为关于$i$的最长上升子序列只能从$i$前面的转移。而这个转移很简单,$dp[j]$表示以$nums[j]$结尾的最长上升子序列的长度,如果$nums[i]>nums[j]$的话,$dp[i]=dp[j]+1$。

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        if(n == 0) return 0;
        int dp[n]; memset(dp, 0, sizeof(dp));
        dp[0] = 1;
        int ans = 1;
        for(int i=1; i<n; i++) {
            for(int j=0; j<i; j++) {
                if(nums[j] < nums[i]) dp[i] = max(dp[i], dp[j] + 1);
                else dp[i] = max(dp[i], 1);
            }
            ans = max(dp[i], ans);
        }
        return ans;
    }
};

二分

这个方法我也是一直有所耳闻,但是一直都没有写过。这次也没想出来,不过看了题解的思路就自己写出来啦。
维护一个数组$d$,表示长度为$i$的最长上升子序列的末尾元素的最小值。
遍历数组,对于每一个元素,如果这个元素比$d$的末尾要大,那么直接放入$d$的末尾;否则,在$d$数组里进行二分查找,找到合适的位置放入。
至于二分查找的具体内容,就是找第一个比当前元素大的位置,然后替换掉这位的数字。想一想就通了嘛,要让上升子序列尽可能的长,就需要让序列上升得尽可能慢,所以每次在上升子序列最后加上的那个数要尽可能的小。

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> d;
        for(auto x: nums) {
            if(d.empty() || x > d.back()) d.push_back(x);
            else {
                int left = 0, right = d.size() - 1, ans = 0;
                while(left <= right) {
                    int mid = (left + right) >> 1;
                    if(d[mid] >= x) {
                        ans = mid;
                        right = mid - 1;
                    }
                    else left = mid + 1;
                }
                d[ans] = x;
            }
        }
        return d.size();
    }
};

14. 岛屿的最大面积 [2020.03.15]

给定一个包含了一些 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。

代码

看到数据范围选择$BFS$。
遍历数组,遇到是岛屿的$1$开始BFS并计算面积。在所有面积中取最大值。

class Solution {
public:
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        int dx[] = {0, 0, 1, -1};
        int dy[] = {1, -1, 0, 0};
        int mx = 0;
        bool vis[55][55]; memset(vis, false, sizeof(vis)); 
        queue<pair<int, int>> que; 
        for(int i=0; i<n; i++) {
            for(int j=0; j<m; j++) {
                if(grid[i][j] == 0) continue;
                if(vis[i][j]) continue;

                que.push(make_pair(i, j));
                int ans = 0; vis[i][j] = true;
                
                while(!que.empty()) {
                    pair<int, int> now = que.front(); que.pop();
                    int x = now.first, y = now.second;
                    ans++;
                    for(int i=0; i<4; i++) {
                        int tx = x + dx[i], ty = y + dy[i];
                        if(tx < 0 || tx >= n || ty < 0 || ty >= m) continue;  
                        if(grid[tx][ty] == 0) continue;
                        if(!vis[tx][ty]) {
                            que.push(make_pair(tx, ty));
                            vis[tx][ty] = true;
                        } 
                    }
                }    
                mx = max(mx, ans);
            }
        }
        return mx;
    }
};

15. 字符串压缩 [2020.03.16]

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

样例

示例 1:

输入:”aabcccccaaa”
输出:”a2b1c5a3″

示例 2:

输入:”abbccd”
输出:”abbccd”
解释:”abbccd”压缩后为”a1b2c2d1″,比原字符串长度更长。

提示

  • 字符串长度在[0, 50000]范围内。

代码

我感觉这道题就是单纯的代码题,毕竟$O(n)$也不可能再优化了。
遍历一遍,当一种连续的字母结束就把结果统计入da’an

class Solution {
public:
    string compressString(string s) {
        int n = s.size(), now = 1;
        string ans = "";
        if(s.size() == 1) return s;
        for(int i=1; i<n; i++) {
            if(s[i] == s[i-1]) now++;
            else {
                ans += s[i-1];
                string tmp = "";
                while(now) {
                    int x = now % 10;
                    tmp += x + '0';
                    now /= 10;
                }
                for(int i=tmp.size()-1; i>=0; i--) ans += tmp[i];
                now = 1;
            }
            if(i == n-1) {
                ans += s[n-1];
                string tmp = "";
                while(now) {
                    int x = now % 10;
                    tmp += x + '0';
                    now /= 10;
                }
                for(int i=tmp.size()-1; i>=0; i--) ans += tmp[i];
            }
        }  
        return ans.size() >= s.size() ? s : ans;
    }
};

16. 拼写单词 [2020.03.17]

给你一份『词汇表』(字符串数组) words 和一张『字母表』(字符串) chars。
假如你可以用 chars 中的『字母』(字符)拼写出 words 中的某个『单词』(字符串),那么我们就认为你掌握了这个单词。
注意:每次拼写时,chars 中的每个字母都只能用一次。
返回词汇表 words 中你掌握的所有单词的 长度之和

样例

示例 1:

输入:words = [“cat”,”bt”,”hat”,”tree”], chars = “atach”
输出:6
解释:
可以形成字符串 “cat” 和 “hat”,所以答案是 3 + 3 = 6。

示例 2:

输入:words = [“hello”,”world”,”leetcode”], chars = “welldonehoneyr”
输出:10
解释:
可以形成字符串 “hello” 和 “world”,所以答案是 5 + 5 = 10。

提示

  • 1 <= words.length <= 1000
  • 1 <= words[i].length, chars.length <= 100
  • 所有字符串中都仅包含小写英文字母

代码

这题太简单了,我都不想写题解了……
统计给出单词中每个字母的数量,对于要判断的每个单词,遍历并与拥有的字母数量进行比较。

class Solution {
public:
    int countCharacters(vector<string>& words, string chars) {
        int cnt[26]; memset(cnt, 0, sizeof(cnt));
        for(auto c: chars) cnt[c-'a']++;
        int ans = 0;
        for(auto word: words) {
            bool flag = true;
            int now[26]; memset(now, 0, sizeof(now));
            for(auto c: word) {
                now[c-'a']++;
                if(now[c-'a'] > cnt[c-'a']) flag = false;
            }
            if(flag) ans += word.size();
        }
        return ans;
    }
};

17. 矩形重叠 [2020.03.17]

矩形以列表 [x1, y1, x2, y2] 的形式表示,其中 (x1, y1) 为左下角的坐标,(x2, y2) 是右上角的坐标。
如果相交的面积为正,则称两矩形重叠。需要明确的是,只在角或边接触的两个矩形不构成重叠。
给出两个矩形,判断它们是否重叠并返回结果。

样例

示例 1:

输入:rec1 = [0,0,2,2], rec2 = [1,1,3,3]
输出:true

示例 2:

输入:rec1 = [0,0,1,1], rec2 = [1,0,2,1]
输出:false

提示

  • 两个矩形 rec1 和 rec2 都以含有四个整数的列表的形式给出。
  • 矩形中的所有坐标都处于 -10^9 和 10^9 之间。

代码

自己的想法不够精妙,看到题解里一个转化为区间覆盖问题的。
将两个矩形投影至$x$轴和$y$轴,两个矩形相交的充要条件是两个矩形在$x$轴和$y$轴的投影都有相交。

class Solution {
public:
    bool isRectangleOverlap(vector<int>& rec1, vector<int>& rec2) {
        bool ans1 = !(rec2[0] >= rec1[2] || rec2[2] <= rec1[0]);
        bool ans2 = !(rec2[1] >= rec1[3] || rec2[3] <= rec1[1]);
        return ans1 && ans2;
    }
};

18. 最长回文串

给定一个包含大写字母和小写字母的字符串,找到通过这些字母构造成的最长的回文串。
在构造过程中,请注意区分大小写。比如 “Aa” 不能当做一个回文字符串。

样例

示例 1:
输入:
“abccccdd”
输出:
7
解释:
我们可以构造的最长的回文串是”dccaccd”, 它的长度是 7。

提示

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

代码

太简单了。我严重怀疑做完这个每日打卡的人连能否通过大一C语言考试都是问题。
偶数个数的字母一定可以被全部用上,奇数个数的字母最多只有一个能被全用上,其余只能用数量-1。

class Solution {
public:
    int longestPalindrome(string s) {
        int cnt[52]; memset(cnt, 0, sizeof(cnt));
        for(auto c: s) {
            if('a'<=c && c<='z') cnt[c-'a']++;
            else cnt[26+c-'A']++;
        }
        int ans = 0, odd = 0;
        for(int i=0; i<52; i++) {
            if(cnt[i] & 1) odd++;
            ans += cnt[i];
        }
        return odd <= 1 ? ans : ans - odd + 1;
    }
};

19. 最小的k个数 [2020.03.20]

输入整数数组 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

代码

直接sort法

不好意思,看到这道题我真的很想这么写完就关掉窗口了。
直接调用sort,然后返回前$k$个。

class Solution {
public:
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        sort(arr.begin(), arr.end());
        vector<int> ans;
        for(int i=0; i<k; i++) ans.push_back(arr[i]);
        return ans;
    }
};

快排

但是我的良心不允许我这样做,所以我去重新学习了一下快排。
根据快排的过程,每一次它都会将一个数字移到它的目标位置,该位置前面的数比这个数小,后面的数比这个数大。所以当目标位置为$k$时,直接拷贝目标位置之前的数即可。

class Solution {
public:
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        vector<int> ans;
        if(arr.size() == 0 || k == 0) return ans;
        return quickSearch(arr, 0, arr.size()-1, k-1);
    }
    vector<int> quickSearch(vector<int>& nums, int lo, int hi, int k) {
        int j = partition(nums, lo, hi);
        if(j == k) {
            vector<int> ans;
            for(int i=0; i<=j; i++) ans.push_back(nums[i]);
            return ans;
        }
        return j > k ? quickSearch(nums, lo, j-1, k) : quickSearch(nums, j+1, hi, k);
    }
    int partition(vector<int>& nums, int lo, int hi) {
        int v = nums[lo];
        int i = lo, j = hi + 1;
        while(true) {
            while(++i <= hi && nums[i] < v);
            while(--j >= lo && nums[j] > v);
            if(i >= j) break;
            int t = nums[j];
            nums[j] = nums[i];
            nums[i] = t;
        }
        nums[lo] = nums[j];
        nums[j] = v;
        return j;
    }
};
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇