✅ 463. 岛屿的周长
描述
给定一个包含 0 和 1 的二维网格地图，其中 1 表示陆地 0 表示水域。
网格中的格子水平和垂直方向相连（对角线方向不相连）。整个网格被水完全包围，但其中恰好有一个岛屿（或者说，一个或多个表示陆地的格子相连组成的岛屿）。
岛屿中没有“湖”（“湖” 指水域在岛屿内部且不和岛屿周围的水相连）。格子是边长为 1 的正方形。网格为长方形，且宽度和高度均不超过 100 。计算这个岛屿的周长。
示例 :
输入:
[[0,1,0,0],
[1,1,1,0],
[0,1,0,0],
[1,1,0,0]]
输出: 16
解释: 它的周长是下面图片中的 16 个黄色的边：
解答
way1: 关注每个是1 的方格，关注其上下左右，是边界吗？（是则+1）是0 吗？（是则+1）
way2: 直接遍历数组，只要前面有相邻的方格，就-2
cpp
- way1
class Solution {
public:
int islandPerimeter(vector<vector<int>>& grid) {
int res = 0;
for(int i = 0; i < grid.size(); i++) {
for (int j = 0; j < grid[i].size(); j++) {
if (grid[i][j] == 1) {
//up
if(i == 0) {
//first row
res++;
}
if(i > 0 && grid[i-1][j] == 0) {
res++;
}
//down
if(i == (grid.size() - 1)) {
//last row
res++;
}
if (i < (grid.size() - 1) && grid[i + 1][j] == 0) {
res++;
}
//left
if(j == 0) {
res++;
}
if(j > 0 && grid[i][j-1] == 0){
res++;
}
//right
if(j == grid[i].size() - 1) {
//last col
res++;
}
if (j < (grid[i].size() - 1) && grid[i][j+1] == 0) {
res++;
}
}
}
}
return res;
}
};
/*执行用时 :
112 ms
, 在所有 C++ 提交中击败了
18.37%
的用户
内存消耗 :
16.3 MB
, 在所有 C++ 提交中击败了
13.37%
的用户*/
way2
class Solution {
public:
int islandPerimeter(vector<vector<int>>& grid) {
int res = 0;
for(int i = 0; i < grid.size(); i++) {
for (int j = 0; j < grid[i].size(); j++) {
if (grid[i][j] == 1) {
res += 4;
if (i > 0 && grid[i-1][j] == 1) {
res -= 2;
}
if (j > 0 && grid[i][j-1] == 1) {
res -= 2;
}
}
}
}
return res;
}
};
/*执行用时 :
72 ms
, 在所有 C++ 提交中击败了
76.66%
的用户
内存消耗 :
16.4 MB
, 在所有 C++ 提交中击败了
13.37%
的用户*/
py
✅ 1122. 数组的相对排序
描述
给你两个数组，arr1 和 arr2，
arr2 中的元素各不相同
arr2 中的每个元素都出现在 arr1 中
对 arr1 中的元素进行排序，使 arr1 中项的相对顺序和 arr2 中的相对顺序相同。未在 arr2 中出现过的元素需要按照升序放在 arr1 的末尾。
示例：
输入：arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6]
输出：[2,2,2,1,4,3,3,9,6,7,19]
提示：
arr1.length, arr2.length <= 1000
0 <= arr1[i], arr2[i] <= 1000
arr2 中的元素 arr2[i] 各不相同
arr2 中的每个元素 arr2[i] 都出现在 arr1 中
解答
【错误】思路： 找到 arr2 的最左侧 的数组 x， 和最右侧的数字 y， 把arr1 中剩下的， 小于x 的数字，升序排好 的到 f， 把arr1 中剩下的，大于y 的， 升序排好， 得到g。
然后 返回： f + arr2 + g。 即可
正确 ： 桶排序
Java题解：该题就是一个桶排序，先把arr2中的数按顺序拿完，在把桶中剩下的按顺序拿完。
public int[] relativeSortArray(int[] arr1, int[] arr2) {
int[] bucket = new int[1001];// java 帮你自动初始化 局部变量到0
for (int i = 0; i < arr1.length; i++)
bucket[arr1[i]]++;
int idx = 0;
for (int i = 0; i < arr2.length; i++)
while (bucket[arr2[i]] > 0) {
bucket[arr2[i]]--;
arr1[idx++] = arr2[i];
}
for (int i = 0; i < bucket.length; i++)
while (bucket[i] > 0) {
bucket[i]--;
arr1[idx++] = i;
}
return arr1;
}
cpp
class Solution {
public:
vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) {
int bucket[1001] = {0};
int res[1001];
int index = 0;
//arr1 all nums put in bucket
for (int i = 0; i < arr1.size(); i++) {
bucket[arr1[i]]++;
}
//find all nums in bucket which employ arr2 as sol
for(int i = 0; i < arr2.size(); i++) {
while(bucket[arr2[i]] > 0) {
//printf("%d:", arr2[i]);
res[index++] = arr2[i];
bucket[arr2[i]]--;
}
}
//printf("::%d:", index);
//for all nums left in bucket
for (int i = 0; i < 1001; i++) {
while (bucket[i] > 0) {
printf("bucket[%d] : %d,", i, bucket[i]);
res[index++] = i;
bucket[i]--;
}
}
vector<int> ret(res, res + sizeof(res) / sizeof(int));
return ret;
}
};// 该死的c sb初始化 todo 0219 rev below:
class Solution {
public:
vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) {
int bucket[1001] = {0};
int res[arr1.size()] = {0};
int index = 0;
//arr1 all nums put in bucket
for (int i = 0; i < arr1.size(); i++) {
bucket[arr1[i]]++;
}
//find all nums in bucket which employ arr2 as sol
for(int i = 0; i < arr2.size(); i++) {
while(bucket[arr2[i]] > 0) {
//printf("%d:", arr2[i]);
res[index++] = arr2[i];
bucket[arr2[i]]--;
}
}
//printf("::%d:", index);
//for all nums left in bucket
for (int i = 0; i < end(bucket) - begin(bucket); i++) {
while (bucket[i] > 0) {
printf("bucket[%d] : %d,", i, bucket[i]);
res[index++] = i;
bucket[i]--;
}
}
// 注意 构造函数：
vector<int> ret(res, res + sizeof(res) / sizeof(int));
return ret;
}
};// 该死的c sb初始化
/*执行用时 :
0 ms
, 在所有 C++ 提交中击败了
100.00%
的用户
内存消耗 :
9.2 MB
, 在所有 C++ 提交中击败了
9.25%
的用户*/
py
✅ 876. 链表的中间结点
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，我们返回第二个结点。
解答
思路： 遍历，计数，总长 为 n 那么，拿 奇数： n/2 ；；偶数（n + 1）/ 2
eg. 奇数 n = 5 >> 5 / 2 = 2 ;;ok (1, 2, 3, 4, 5)
eg. 偶数 n = 6 >> 6 + 1 = 7; 7 / 2 = 3 ;;ok (1, 2, 3, 4, 5, 6)
上述的思路，结合map 才能做好，但是c++ 的map 实在是非常难用
于是给出 java 双指针解法：
快慢指针，寻找中间节点，倒数第K节点，判断是否有环都可用这个来解决
public ListNode middleNode(ListNode head) {
ListNode fast=head,slow=head;
while(fast!=null && fast.next!=null){
fast=fast.next.next;
slow=slow.next;
}
return slow;
}
cpp
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* middleNode(ListNode* head) {
ListNode *fast = head, *slow = head;
while(fast != NULL && fast->next != NULL) {
fast = fast->next->next;
slow = slow->next;
}
return slow;
}
};
/*执行用时 :
4 ms
, 在所有 C++ 提交中击败了
64.24%
的用户
内存消耗 :
8.6 MB
, 在所有 C++ 提交中击败了
9.32%
的用户*/
✅ 1160. 拼写单词
https://leetcode-cn.com/problems/find-words-that-can-be-formed-by-characters/
描述
给你一份『词汇表』（字符串数组） 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。
解答
如果用py 则是， 有个 set.issubset() 的方法可以用。
cpp
class Solution {
public:
int countCharacters(vector<string>& words, string chars) {
vector<int> htc(26);
for (char ch : chars) {
htc[ch - 'a']++;
}
int ans = 0;
for (string &w : words) {//tt todo 注意什么是 & 的意思
vector<int> htw(26);//tt 这到底构造出来了什么玩意？26 长的vector
int i;
for (i = 0; i < w.size(); i++) {
if (++htw[w[i] - 'a'] > htc[w[i] - 'a']) {
break;
}
}
if (i >= w.size()) {
ans += w.size();
}
}
return ans;
}
};
/*执行用时 :
60 ms
, 在所有 C++ 提交中击败了
91.29%
的用户
内存消耗 :
20.3 MB
, 在所有 C++ 提交中击败了
45.27%
的用户*/
他人java
有人比我更慢吗= = 我真的菜得可以
class Solution {
public int countCharacters(String[] words, String chars) {
String kkp=chars;
int count=0;
int number=0;
for (int i = 0; i < words.length; i++) {
for (int j = 0; j < words[i].length(); j++) {
if (chars.contains(String.valueOf(words[i].charAt(j)))){
int num=chars.indexOf(String.valueOf(words[i].charAt(j)));
chars=chars.substring(0,num)+chars.substring(num+1);
count++;
}
if (count==words[i].length()){
number+=count;
break;
}
}
count=0;
chars = kkp;
}
return number;
}
}
py
class Solution(object):
def countCharacters(self, words, chars):
"""
:type words: List[str]
:type chars: str
:rtype: int
"""
ans = 0
for w in words:
for i in w:
if w.count(i) <= chars.count(i):
flag = 1
continue
else:
flag = 0
break
if flag == 1:
ans+=len(w)
return ans