刚刚交完卷子，来整理个新鲜的。
这次的周赛题目总体来说还算平和，但是想拿到分还是需要一些技巧，相比于上一次，这一次的题目在数据上开始卡算法的时间复杂度了，一些暴力的写法可能过不了一些题。
咱一道一道说。
生成每种字符都是奇数个的字符串
题目
这个题，emm，可以算是出题人的一种迷惑性行为。我盯着题目，再三确认，最终，明白了规则只限定了字符串中的字符出现次数为奇数，只要求字符是小写字母，没有要求每种字符个数。
所以作法很简单
当长度是奇数的时候全部填充一种字符即可
当长度是偶数的时候填充一个其它字符，剩下的全部填充一个字符即可
我选择了a和b两个字符
代码：
class Solution {
public String generateTheString(int n) {
String ans = "";
if((n & 1) == 1)
{
for(int i = 1;i <= n;i++)
{
ans += "a";
}
}
else
{
for(int i = 1;i < n;i++)
{
ans += "a";
}
ans += "b";
}
return ans;
}
}
还是想感慨一句：Java处理字符串真的好方便！！！
灯泡开关 III
题目
这个题，暴力的想，n方的模拟应该很好写，但从数据五万来看，这点不太合适。
这里提供两种做法：
O(nlogn)
需要想办法把复杂度优化到O(nlogn)。比赛的时候，看到前面的灯必须全部都亮这个条件，我的第一反应是需要一种logn的结构来访问区间和。于是我想到了树状数组。
大致步骤就是，每次点亮一个灯后，在该位置+1.判断它是否会变蓝，就求它前面的区间和是否等于它的下标，也就是判断它前面亮着的灯的个数是否为灯的个数。
如果变蓝了，则接着向后遍历亮着的灯，他们也应该是变蓝的，遇到灭的就停止。
处理完这个时刻的灯之后，把蓝灯的数目和时刻数进行比较，统计答案即可。
当然，也可以将题目看作是求一个时刻时，图上连通块的个数，每次点亮某盏灯，就是插入这个点并将它和前后亮着的灯进行连接。符合要求的时刻，连通块个数为1且第一盏灯必须包含在连通块中。
可以用并查集进行维护。
树状数组代码：
class Solution {
int[] a = new int[100050];
boolean[] isOpen = new boolean [100050];
private int lowbit(int k)
{
return k & (-k);
}
private int get(int k)
{
int sum = 0;
while(k > 0)
{
sum += a[k];
k -= lowbit(k);
}
return sum;
}
private void add(int k,int num,int n)
{
while(k <= n)
{
a[k] += num;
k += lowbit(k);
}
}
public int numTimesAllBlue(int[] light) {
int ans = 0;
int l = light.length;
int sum = 0;
for(int i = 0,k;i < l;i++)
{
add(light[i],1,l);
isOpen[light[i]] = true;
if(get(light[i]) == light[i])
{
k = light[i];
while(k <= l && isOpen[k])
{
sum++;
k++;
}
}
if(sum == i + 1)
{
ans++;
}
}
return ans;
}
}
O(n)
其实，观察到这道题变蓝的特殊性，即必须所有前面的灯亮着，那么如果一盏灯点亮后该变蓝，那么它前面的灯一定是蓝色的（第一盏灯除外）。所以判断是否变蓝就没有必要用lO(logn)的复杂度了，O(1)比较即可。
最终复杂度为O(n)
O(n)代码：
class Solution {
boolean[] isBlue = new boolean[100000];
boolean[] isOpen = new boolean[100000];
public int numTimesAllBlue(int[] light) {
int ans = 0;
int l = light.length;
int sum = 0;
isBlue[0] = true;
for(int i = 0,k;i < l;i++)
{
isOpen[light[i]] = true;
if(isBlue[light[i] - 1])
{
k = light[i];
while(k <= l && isOpen[k])
{
isBlue[k] = true;
sum++;
k++;
}
}
if(sum == i + 1)
{
ans++;
}
}
return ans;
}
}
嗯。。。简单许多
通知所有员工所需的时间
题目
这个题和最后一个题都是树的遍历。对于这个题目，建好树之后，通知时间就是到子节点的边长。遍历求最长路径即可。复杂度O(n)
代码：
class Solution {
class V
{
V(int k,int next)
{
this.k = k;
this.next = next;
}
int k;
int next;
}
V[] nxt;
int[] head;
int tot = 0;
private int dfs(int k,int[] time,int sum)
{
int ans = sum;
for(int i = head[k];i != 0;i = nxt[i].next)
{
ans = Math.max(ans,dfs(nxt[i].k,time,sum + time[k]));
}
return ans;
}
public int numOfMinutes(int n, int headID, int[] manager, int[] informTime)
{
nxt = new V[n + 5];
head = new int [n];
for(int i = 0;i < n;i++)
{
if(manager[i] == -1)
{
continue;
}
nxt[++tot] = new V(i,head[manager[i]]);
head[manager[i]] = tot;
}
return dfs(headID,informTime,0);
}
}
比赛代码，写的丑，不要介意
T 秒后青蛙的位置
题目
这个题实际上也是个树的遍历。需要注意的就是：
- 这棵树是无根树，需要标记访问
- 对子节点的概率分布是相等的，所以进入子节点的概率应是到自己的概率除以子节点个数
- 1节点概率为1.0
- 有两种情况让该店存在概率：没有子节点或到该点时时间为零。
- 不满足上条情况的点青蛙不可能停在那里，即概率为零
代码：
class Solution {
class V
{
V(int k,int next)
{
this.k = k;
this.next = next;
}
int k;
int next;
}
V[] nxt;
int[] head,sNum;
int tot = 0;
double[] p;
boolean[] vis;
private void dfs(int k,double po,int t)
{
vis[k] = true;
if(t == 0 || sNum[k] == 1)
{
p[k] = po;
return;
}
po /= (sNum[k] - 1);
for(int i = head[k];i != 0;i = nxt[i].next)
{
if(vis[nxt[i].k])
{
continue;
}
dfs(nxt[i].k,po,t - 1);
}
}
public double frogPosition(int n, int[][] edges, int t, int target)
{
p = new double[n + 1];
nxt = new V[n * 4];
head = new int[n + 1];
sNum = new int[n + 1];
vis = new boolean[n + 1];
for(int i = 0;i < edges.length;i++)
{
nxt[++tot] = new V(edges[i][0],head[edges[i][1]]);
head[edges[i][1]] = tot;
nxt[++tot] = new V(edges[i][1],head[edges[i][0]]);
head[edges[i][0]] = tot;
sNum[edges[i][0]]++;
sNum[edges[i][1]]++;
}
sNum[1]++;
dfs(1,1.0,t);
return p[target];
}
}