LeetCode 179周赛

刚刚交完卷子,来整理个新鲜的。
这次的周赛题目总体来说还算平和,但是想拿到分还是需要一些技巧,相比于上一次,这一次的题目在数据上开始卡算法的时间复杂度了,一些暴力的写法可能过不了一些题。
咱一道一道说。

生成每种字符都是奇数个的字符串

题目
这个题,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];
    }
}
上一篇:Kruskal实现最小生成树


下一篇:克鲁斯卡尔算法与公交问题