目录
0215 algo
https://leetcode-cn.com/problems/find-common-characters
给定仅有小写字母组成的字符串数组 A,返回列表中的每个字符串中都显示的全部字符(包括重复字符)组成的列表。例如,如果一个字符在每个字符串中出现 3 次,但不是 4 次,则需要在最终答案中包含该字符 3 次。
你可以按任意顺序返回答案。
示例 1:
输入:["bella","label","roller"]
输出:["e","l","l"]
示例 2:
输入:["cool","lock","cook"]
输出:["c","o"]
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/find-common-characters
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
本来的思路是 两个 array: book1 book2
book1 保存 list[string]
的 list[0]
里面的 所有出现的字符的;
如下图:(todo 0215 实现)
public List<String> commonChars(String[] A) {
List<String> list = new ArrayList<>();
int[] res = new int[26];
for (char c : A[0].toCharArray()) {
res[c - 'a']++;
}
for (int i = 1; i < A.length; i++) {
int[] temp = new int[26];
for (char c : A[i].toCharArray()) {
temp[c - 'a']++;
}
for (int j = 0; j < 26; j++) {
res[j] = Math.min(res[j], temp[j]);
}
}
for (int i = 0; i < res.length; i++) {
if (res[i] > 0) {
for (int j = 0; j < res[i]; j++) {
list.add(((char) ('a' + i) + ""));
}
}
}
return list;
}
class Solution:
def commonChars(self, A: List[str]) -> List[str]:
# mainly, we use Sting.count()
ret = []
if not A:
return ret
key = set(A[0]) # also, set("abcddd") return u: set(['a','b','c','d'])
for k in key:
minuim = min(a.count(k) for a in A)
ret += minuim * k # here is the string CAT way
return ret
'''
执行用时 :
72 ms
, 在所有 Python3 提交中击败了
19.02%
的用户
内存消耗 :
13.2 MB
, 在所有 Python3 提交中击败了
44.24%
的用户
'''
https://leetcode-cn.com/problems/shortest-distance-to-a-character
给定一个字符串 S 和一个字符 C。返回一个代表字符串 S 中每个字符到字符串 S 中的字符 C 的最短距离的数组。
示例 1:
输入: S = "loveleetcode", C = 'e'
输出: [3, 2, 1, 0, 1, 0, 0, 1, 2, 2, 1, 0]
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/shortest-distance-to-a-character
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
自己的思路是:两个左右兵 如下:
class Solution {
public:
vector<int> shortestToChar(string S, char C) {
vector<int> pos(S.size(), -2);
int pre = -1;
//direction: right to left
for (int i = S.size() - 1; i >= 0; i--){
if(S[i] == C) {
pre = i;
pos[i] = 0;
} else if(pre != -1) {
pos[i] = pre - i;
}
}
// clean env
pre = -1;
//direction: left to right
for (int i = 0; i < S.size(); i++) {
if(pre != -1) {
pos[i] = min(i - pre, pos[i]);
}
//this is for the most right part(to the right of last C),
// where all the pos[x] == -1, cause we dont set in first loop
// first loop : <-----
if(pos[i] == -2){
pos[i] = i - pre;
}
// u must move this if at last ,why? todo
if(S[i] == C) {
pre = i;
//pos[i] = 0;//useless, cause in first loop, we already set it to 0
}
}
return pos;
}
};
/*执行用时 :
4 ms
, 在所有 C++ 提交中击败了
94.40%
的用户
内存消耗 :
9.3 MB
, 在所有 C++ 提交中击败了
5.10%
的用户*/
class Solution:
def shortestToChar(self, S: str, C: str) -> List[int]:
c_pos = [i for i in range(len(S)) if C == S[i]]
return ([min(abs(x - i) for i in c_pos) for x in range(len(S))])
'''
执行用时 :
104 ms
, 在所有 Python3 提交中击败了
21.55%
的用户
内存消耗 :
13.1 MB
, 在所有 Python3 提交中击败了
52.14%
的用户
'''
https://leetcode-cn.com/problems/reformat-department-table
部门表 Department:
+---------------+---------+
| Column Name | Type |
+---------------+---------+
| id | int |
| revenue | int |
| month | varchar |
+---------------+---------+
(id, month) 是表的联合主键。
这个表格有关于每个部门每月收入的信息。
月份(month)可以取下列值 ["Jan","Feb","Mar","Apr","May","Jun","Jul","Aug","Sep","Oct","Nov","Dec"]。
编写一个 SQL 查询来重新格式化表,使得新的表中有一个部门 id 列和一些对应 每个月 的收入(revenue)列。
查询结果格式如下面的示例所示:
Department 表:
+------+---------+-------+
| id | revenue | month |
+------+---------+-------+
| 1 | 8000 | Jan |
| 2 | 9000 | Jan |
| 3 | 10000 | Feb |
| 1 | 7000 | Feb |
| 1 | 6000 | Mar |
+------+---------+-------+
查询得到的结果表:
+------+-------------+-------------+-------------+-----+-------------+
| id | Jan_Revenue | Feb_Revenue | Mar_Revenue | ... | Dec_Revenue |
+------+-------------+-------------+-------------+-----+-------------+
| 1 | 8000 | 7000 | 6000 | ... | null |
| 2 | 9000 | null | null | ... | null |
| 3 | null | 10000 | null | ... | null |
+------+-------------+-------------+-------------+-----+-------------+
注意,结果表有 13 列 (1个部门 id 列 + 12个月份的收入列)。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/reformat-department-table
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
第一步 列拆成行
首先,根据题意,需要将revenue列根据month拆成行,结果如下表,有两种方式,CASE WHEN或者IF语句。
CASE WHEN
SELECT id,
CASE `month` WHEN 'Jan' THEN revenue END Jan_Revenue,
CASE `month` WHEN 'Feb' THEN revenue END Feb_Revenue,
CASE `month` WHEN 'Mar' THEN revenue END Mar_Revenue,
CASE `month` WHEN 'Apr' THEN revenue END Apr_Revenue,
CASE `month` WHEN 'May' THEN revenue END May_Revenue,
CASE `month` WHEN 'Jun' THEN revenue END Jun_Revenue,
CASE `month` WHEN 'Jul' THEN revenue END Jul_Revenue,
CASE `month` WHEN 'Aug' THEN revenue END Aug_Revenue,
CASE `month` WHEN 'Sep' THEN revenue END Sep_Revenue,
CASE `month` WHEN 'Oct' THEN revenue END Oct_Revenue,
CASE `month` WHEN 'Nov' THEN revenue END Nov_Revenue,
CASE `month` WHEN 'Dec' THEN revenue END Dec_Revenue
FROM Department;
或者:
IF
SELECT id,
IF(`month`='Jan',revenue,NULL) Jan_Revenue,
IF(`month`='Feb',revenue,NULL) Feb_Revenue,
IF(`month`='Mar',revenue,NULL) Mar_Revenue,
IF(`month`='Apr',revenue,NULL) Apr_Revenue,
IF(`month`='May',revenue,NULL) May_Revenue,
IF(`month`='Jun',revenue,NULL) Jun_Revenue,
IF(`month`='Jul',revenue,NULL) Jul_Revenue,
IF(`month`='Aug',revenue,NULL) Aug_Revenue,
IF(`month`='Sep',revenue,NULL) Sep_Revenue,
IF(`month`='Oct',revenue,NULL) Oct_Revenue,
IF(`month`='Nov',revenue,NULL) Nov_Revenue,
IF(`month`='Dec',revenue,NULL) Dec_Revenue
FROM Department;
结果都是:
+------+-------------+-------------+-------------+-----+-------------+
| id | Jan_Revenue | Feb_Revenue | Mar_Revenue | ... | Dec_Revenue |
+------+-------------+-------------+-------------+-----+-------------+
| 1 | null | 7000 | null | ... | null |
| 3 | null | 10000 | null | ... | null |
| 1 | 8000 | null | null | ... | null |
| 2 | 9000 | null | null | ... | null |
| 1 | null | null | 6000 | ... | null |
+------+-------------+-------------+-------------+-----+-------------+
第二步 行合并
其次,根据题意,需要根据id,将相同id的行进行合并,结果如下表,采用分组的方式,可以对各月收入列求和(SUM)也可以求最大值(MAX)。
+------+-------------+-------------+-------------+-----+-------------+
| id | Jan_Revenue | Feb_Revenue | Mar_Revenue | ... | Dec_Revenue |
+------+-------------+-------------+-------------+-----+-------------+
| 1 | 8000 | 7000 | 6000 | ... | null |
| 2 | 9000 | null | null | ... | null |
| 3 | null | 10000 | null | ... | null |
+------+-------------+-------------+-------------+-----+-------------+
最终解法:
SELECT id,
SUM(CASE `month` WHEN 'Jan' THEN revenue END) Jan_Revenue,
SUM(CASE `month` WHEN 'Feb' THEN revenue END) Feb_Revenue,
SUM(CASE `month` WHEN 'Mar' THEN revenue END) Mar_Revenue,
SUM(CASE `month` WHEN 'Apr' THEN revenue END) Apr_Revenue,
SUM(CASE `month` WHEN 'May' THEN revenue END) May_Revenue,
SUM(CASE `month` WHEN 'Jun' THEN revenue END) Jun_Revenue,
SUM(CASE `month` WHEN 'Jul' THEN revenue END) Jul_Revenue,
SUM(CASE `month` WHEN 'Aug' THEN revenue END) Aug_Revenue,
SUM(CASE `month` WHEN 'Sep' THEN revenue END) Sep_Revenue,
SUM(CASE `month` WHEN 'Oct' THEN revenue END) Oct_Revenue,
SUM(CASE `month` WHEN 'Nov' THEN revenue END) Nov_Revenue,
SUM(CASE `month` WHEN 'Dec' THEN revenue END) Dec_Revenue
FROM Department
GROUP BY id;
我的理解是: 第二步 包含 了第一步的 行为。
SUM(CASE `month` WHEN 'Jan' THEN revenue END) Jan_Revenue,
表达了:求和(当月份是1月, 然后 返回revenue) 并且 改名字为 Jan_Revenue
'''
执行用时 :
565 ms
, 在所有 MySQL 提交中击败了
5.02%
的用户
内存消耗 :
0B
, 在所有 MySQL 提交中击败了
100.00%
的用户
'''
https://leetcode-cn.com/problems/n-repeated-element-in-size-2n-array
在大小为 2N 的数组 A 中有 N+1 个不同的元素,其中有一个元素重复了 N 次。
返回重复了 N 次的那个元素。
示例 1:
输入:[1,2,3,3]
输出:3
示例 2:
输入:[2,1,2,5,3,2]
输出:2
示例 3:
输入:[5,1,5,2,5,3,5,4]
输出:5
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/n-repeated-element-in-size-2n-array
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
思路: 如果遍历的时候,加入set中的时候,加入fail 说明已经有一个了,这就是那个重复的,返回之即可。
class Solution {
public:
int repeatedNTimes(vector<int>& A) {
std::set<int> myset;
std::set<int>::iterator it;//todo c++ 知识点1: iterator
std:pair<std::set<int>::iterator, bool> ret;//todo c++ 知识点2: pair 的 first
// 和 second
for(int i: A){//c++ 可以这样遍历
ret = myset.insert(i);
if(ret.second == false) it = ret.first;
}
return *it;//todo c++ 知识点1: iterator
}
};
/*执行用时 :
88 ms
, 在所有 C++ 提交中击败了
11.56%
的用户
内存消耗 :
17.5 MB
, 在所有 C++ 提交中击败了
5.32%
的用户*/
有一半的数相等,那么排列中要么所有相同的数都不相邻,要么就必定存在相邻并相等的情形。
int repeatedNTimes(int* A, int ASize) {
int i; if(A[1]==A[3]) return A[1];
for(i=0;i<ASize-1;i++)
if(A[i]==A[i+1])
return A[i];
return A[0];
}
class Solution {
public int repeatedNTimes(int[] A) {
Random r = new Random();
int len = A.length;
int a,b;
while(true){
a = r.nextInt(len);
b = r.nextInt(len);
if(a!=b && A[a]==A[b]){
return A[a];
}
}
}
}
解法1:先排序,再比较相邻的元素:
class Solution:
def repeatedNTimes(self, A):
"""
:type A: List[int]
:rtype: int
"""
A.sort()
for i in range(len(A) - 1):
if A[i] == A[i + 1]:
return A[i]
解法2:todo 写描述
class Solution:
def repeatedNTimes(self, A):
"""
:type A: List[int]
:rtype: int
"""
A.sort()
n = len(A) // 2
return A[0] if A[0] == A[n-1] else A[n]
手机扫一扫
移动阅读更方便
你可能感兴趣的文章