Leetcode周赛394
100294. 统计特殊字母的数量 I
解法一
将小写字母放到一个集合中，将大写字母变成小写字母放到另一个集合中，取两个集合之间的交集。
class Solution {
public int numberOfSpecialChars(String word) {
Set<Character> lowercaseSet = new HashSet<>();
Set<Character> uppercaseSet = new HashSet<>();
for (char c : word.toCharArray()) {
if (Character.isLowerCase(c)) {
lowercaseSet.add(c);
} else if (Character.isUpperCase(c)) {
uppercaseSet.add(Character.toLowerCase(c));
}
}
Set<Character> intersection = new HashSet<>(lowercaseSet);
intersection.retainAll(uppercaseSet); /
return intersection.size();
}
}
解法二
位运算，大写字母和小写字母的区别，在于8位中第三为一个是0一个是1, 后五位表示是什么字母。
-
ASCII >> 5 & 1 判断是小写还是大写
-
ASCII & 31 取这个字母是第几个字母
-
通过位运算往集合里面添加元素 |= 1 << i
-
集合求交集 A & B
-
集合求大小 Integer.bitCount()
class Solution { public int numberOfSpecialChars(String word) { int[] mask = new int[2]; for (char c : word.toCharArray()) { mask[c >> 5 & 1] |= 1 << (c & 31); } return Integer.bitCount(mask[0] & mask[1]); } }
100291. 统计特殊字母的数量 II
解法一
模拟
class Solution {
public int numberOfSpecialChars(String word) {
int ans = 0;
int[] state = new int[27];
for (char c : word.toCharArray()) {
int x = c & 31; // 转成数字 1~26
if ((c & 32) > 0) { // 小写字母
if (state[x] == 0) {
state[x] = 1;
} else if (state[x] == 2) {
state[x] = -1;
ans--;
}
} else { // 大写字母
if (state[x] == 0) {
state[x] = -1;
} else if (state[x] == 1) {
state[x] = 2;
ans++;
}
}
}
return ans;
}
}
解法二
位运算, 创建一个小写集合，大写集合，非法集合。如果在小写字母判断中发现已经存在大写集合中，则加入非法集合，最后判断小写集合和大写集合的交集并且没在非法集合的元素。
1. 元素是否在集合中 bit & A > 0
1. 元素在A中 ，不能在B中 *A*&∼*B*
class Solution {
public int numberOfSpecialChars(String word) {
int lower=0,upper=0, invalid=0;
for(char c :word.toCharArray()){
int bit = 1 << (c&31);
if( (c >> 5 & 1) == 1){
lower |= bit;
if((upper & bit) > 0){
invalid |= bit;
}
}else{
upper |= bit;
}
}
return Integer.bitCount(lower & upper & ~invalid);
}
}
100290. 使矩阵满足条件的最少操作次数
将操作最少的元素改为保留最多的元素，最后才进行减去
class Solution {
public int minimumOperations(int[][] grid) {
int m = grid.length, n= grid[0].length;
int f0 = 0, f1 = 0, pre = -1;
for(int i=0;i<n;i++){
int[] cnt = new int[10];
// 统计每行的元素
for(int[] row:grid){
cnt[row[i]]++;
}
// 本列的最大值 和次大值， 以及选取的元素
int mx = -1, mx2 =0, x = -1;
for(int v=0;v<10;v++){
int res = (v!=pre?f0:f1) + cnt[v];
if(res>mx){
mx2 = mx;
mx = res;
x = v;
}else if(res>mx2){
mx2 = res;
}
}
f0 = mx;
f1 = mx2;
pre = x;
}
return m*n -f0;
}
}
3123. 最短路径中的边
如何保证找到的边一定在从0出发的最短路上？
dis[x] + w(x, y) = dis[y]
如何保证找到的边一定在从0到n-1的最短路上，倒着出发
dis[x] + w(x,y) = dis[y]
将边进行构图
List<int[]>[] g = new ArrayList[n];
Arrays.setAll(g, i -> new ArrayList<>());
for (int i = 0; i < edges.length; i++) {
int[] e = edges[i];
int x = e[0], y = e[1], w = e[2];
g[x].add(new int[]{y, w, i});
g[y].add(new int[]{x, w, i});
}
Dijkstra算法模板
long[] dis = new long[n];
Arrays.fill(dis, Long.MAX_VALUE);
dis[0] = 0;
PriorityQueue<long[]> pq = new PriorityQueue<>((a, b) -> Long.compare(a[0], b[0]));
pq.offer(new long[]{0, 0});
while (!pq.isEmpty()) {
long[] dxPair = pq.poll();
long dx = dxPair[0];
int x = (int) dxPair[1];
if (dx > dis[x]) {
continue;
}
for (int[] t : g[x]) {
int y = t[0];
int w = t[1];
long newDis = dx + w;
if (newDis < dis[y]) {
dis[y] = newDis;
pq.offer(new long[]{newDis, y});
}
}
}
整体
class Solution {
public boolean[] findAnswer(int n, int[][] edges) {
List<int[]>[] g = new ArrayList[n];
Arrays.setAll(g, i -> new ArrayList<>());
for (int i = 0; i < edges.length; i++) {
int[] e = edges[i];
int x = e[0], y = e[1], w = e[2];
g[x].add(new int[]{y, w, i});
g[y].add(new int[]{x, w, i});
}
long[] dis = new long[n];
Arrays.fill(dis, Long.MAX_VALUE);
dis[0] = 0;
PriorityQueue<long[]> pq = new PriorityQueue<>((a, b) -> Long.compare(a[0], b[0]));
pq.offer(new long[]{0, 0});
while (!pq.isEmpty()) {
long[] dxPair = pq.poll();
long dx = dxPair[0];
int x = (int) dxPair[1];
if (dx > dis[x]) {
continue;
}
for (int[] t : g[x]) {
int y = t[0];
int w = t[1];
long newDis = dx + w;
if (newDis < dis[y]) {
dis[y] = newDis;
pq.offer(new long[]{newDis, y});
}
}
}
boolean[] ans = new boolean[edges.length];
// 图不连通
if (dis[n - 1] == Long.MAX_VALUE) {
return ans;
}
// 从终点出发 DFS
boolean[] vis = new boolean[n];
dfs(n - 1, g, dis, ans, vis);
return ans;
}
private void dfs(int y, List<int[]>[] g, long[] dis, boolean[] ans, boolean[] vis) {
vis[y] = true;
for (int[] t : g[y]) {
int x = t[0];
int w = t[1];
int i = t[2];
if (dis[x] + w != dis[y]) {
continue;
}
ans[i] = true;
if (!vis[x]) {
dfs(x, g, dis, ans, vis);
}
}
}
}