2274. Maximum Floors Without Special Floors

Question

Alice manages a company and has rented some floors of a building as office space. Alice has decided some of these floors should be special floors, used for relaxation only.

You are given two integers bottom and top, which denote that Alice has rented all the floors from bottom to top (inclusive). You are also given the integer array special, where special[i] denotes a special floor that Alice has designated for relaxation.

Return the maximum number of consecutive floors without a special floor.

Solution

可以视为特殊的动态规划。

计算每个特殊房间与上一个特殊房间的层数。(可以将底层的上一个房间视为特殊房间,需要将第一个房间设置为bottom-1)。
当距离大于当前结果时则更新res。

最后需要计算最后一层到上一个特殊房间的距离。(可以将顶楼的上一层视为特殊房间,因此直接计算top - lastRoom的层数即可)

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public int maxConsecutive(int bottom, int top, int[] special) {
int res = 0;
int lastRoom = bottom-1;
Arrays.sort(special);

for(int room : special){
int temp = room - lastRoom - 1;
res = Math.max(res, temp);
lastRoom = room;

}
int temp = top - lastRoom;
res = Math.max(res, temp);

return res;
}
}

2273. Find Resultant Array After Removing Anagrams

Problem

You are given a 0-indexed string array words, where words[i] consists of lowercase English letters.

In one operation, select any index i such that 0 < i < words.length and words[i - 1] and words[i] are anagrams, and delete words[i] from words. Keep performing this operation as long as you can select an index that satisfies the conditions.

Return words after performing all operations. It can be shown that selecting the indices for each operation in any arbitrary order will lead to the same result.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase using all the original letters exactly once. For example, "dacb" is an anagram of "abdc".

Solution

由于只用查看上一个元素。
记录一个prev[]数组记录上一个元素的字符情况。
遍历words,用数组bin[]统计每个字母出现的次数,同时减去prev数组的统计数字。
如果数组中的每个统计结果都为0,则是上一个字符串的Anagram。
否则是一个新的字符串,将其加入结果。
然后将上一个数组prev更新为当前的统计数组bin[]。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public List<String> removeAnagrams(String[] words) {
int[] prev = new int[26];

List<String> ans = new ArrayList<>();

for(String word : words){
int[] bin = new int[26];
char[] chars = word.toCharArray();
for(int i = 0; i < chars.length; i++){
prev[chars[i]-'a']--;
bin[chars[i]-'a']++;
}
if(!allZero(prev)){
ans.add(word);
}
prev = bin;
}
return ans;
}

private boolean allZero(int[] bin){
for(int num : bin){
if(num != 0) return false;
}
return true;
}
}
1302. Deepest Leaves Sum

1302. Deepest Leaves Sum

Question

Given the root of a binary tree, return the sum of values of its deepest leaves.

Solution

BFS搜索,层序遍历,每次计算每个层级的总和。
最后返回最后一个层级总和。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int deepestLeavesSum(TreeNode root) {
Deque<TreeNode> q = new LinkedList<>();
int res = 0;

q.offer(root);

int level = q.size();

while(!q.isEmpty()){
int sum = 0;
for(int i = 0; i < level; i++){
TreeNode curr = q.poll();
sum += curr.val;
if(curr.left != null) q.offer(curr.left);
if(curr.right != null) q.offer(curr.right);
}
res = sum;
level = q.size();
}
return res;
}
}
743. Network Delay Time

743. Network Delay Time

Question

You are given a network of n nodes, labeled from 1 to n. You are also given times, a list of travel times as directed edges times[i] = (u<sub>i</sub>, v<sub>i</sub>, w<sub>i</sub>), where u<sub>i</sub> is the source node, v<sub>i</sub> is the target node, and w<sub>i</sub> is the time it takes for a signal to travel from source to target.

We will send a signal from a given node k. Return the time it takes for all the n nodes to receive the signal. If it is impossible for all the n nodes to receive the signal, return -1.

Solution

Dijkstra算法

此题可以转化为求起始节点到最远距离的节点的距离。单源最短路径问题,可以采用Dijkstra算法。

采用一个visited[]数组记录初始节点的访问状况。
同时dist[]数组记录到达这一节点的最小距离,初始化为无限大。

进行BFS搜索,每次优先访问当前节点的子节点的最近子节点,并更新子节点与初始节点距离。
最后遍历dist[]数组,如果有元素仍为无限大,则BFS搜索未遍历到,返回-1。
否则返回数组内最大的距离即可。

建立映射

首先通过哈希表,将起始节点与有向边建立起映射关系。列表中储存子节点和对应边上的权值。
注意由于index是-1的,因此在组成列表时需要将当前数字减一。

优先级队列

采用优先级队列组成小根堆,每次将当前的最小距离作为权值加入队列。
初始化队列时需要将起始节点(k-1)放入,此时的总距离为0。

当当前的子节点的cost加上起始节点的距离小于子节点的最小距离时,更新子节点最小距离。
同时将子节点当前最小距离作为比较对象传入优先级队列。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Solution {
public int networkDelayTime(int[][] times, int n, int k) {
HashMap<Integer, List<int[]>> edges = new HashMap<>();

for(int[] time : times){ //建立有向边
int source = time[0] - 1, kid = time[1] - 1, cost = time[2]; //注意index需要-1
List<int[]> list = edges.getOrDefault(source, new ArrayList<>());
list.add(new int[]{kid, cost}); //建立起点——终点映射
edges.put(source, list);
}

int[] visited = new int[n];
int[] dist = new int[n];
Arrays.fill(dist, Integer.MAX_VALUE);

PriorityQueue<int[]> pq = new PriorityQueue<>((a,b) -> a[1] - b[1]); //优先级队列,最小堆每次访问距离最近的节点

int start = k-1;
dist[start] = 0;
pq.offer(new int[]{start, 0}); //start为初始节点,后面的距离为了实现优先级队列

while(!pq.isEmpty()){
int[] curr = pq.poll();
int source = curr[0];

if(visited[source] == 1) continue;
visited[source] = 1;

List<int[]> children = edges.getOrDefault(source, new ArrayList<>()); //获取当前起点的所有边
for(int[] child : children){
int kid = child[0], cost = child[1];

if(cost + dist[source] < dist[kid]){ //如果新的距离小于之前的最小距离,则更新距离并将新的起点加入优先级队列
dist[kid] = cost + dist[source];
pq.offer(new int[]{kid, dist[kid]}); //更新的距离是从出发节点到当前节点的距离,每次优先访问最近的节点
}
}
}

int res = 0;

for(int d : dist){ //最后遍历,距离的最大值就是结果
res = Math.max(res, d);
}
return res == Integer.MAX_VALUE ? -1 : res;
}
}
Unity: Trigger, Collider, UI & NPC Interaction

Unity: Trigger, Collider, UI & NPC Interaction

触发器与碰撞器 Trigger & Collider:

Unity中的物体可以根据双方的触发器与碰撞器产生交互。
触发器与碰撞器有三种不同的状态,Enter,Stay与Exit。

1
2
3
4
5
6
7
8
//触发器事件, Tigger
private void OnTriggerEnter(Collider other)
private void OnTriggerStay(Collider other)
private void OnTriggerExit(Collider other)
//碰撞器事件, Collision
private void OnCollisionEnter(Collision collision)
private void OnCollisionStay(Collision collision)
private void OnCollisionExit(Collision collision)

不同的移动方法与触发器和碰撞器产生的交互也不相同:

Math Function:

  • 遇到目标即使是碰撞器,依然穿透
  • 不管自身是否是碰撞器或者触发器,当它接触到目标的时候(碰撞器/触发器),此时交互没有反应

Character Controller:

  • 碰撞器:有阻挡效果,没有办法接收碰撞器Collision事件
  • 触发器:可穿透,可以接收Tigger事件

Rigidbody:

  • 刚体自身的Collider如果是碰撞器,则只响应碰撞器事件。
  • 刚体自身的Collider如果是触发器,则同时响应碰撞器和触发器事件。

角色交互 NPC Interaction:

实现角色之间的交互,当玩家接近NPC时,NPC会面向玩家。当玩家远离NPC时,NPC会回归自己的朝向。

当NPC的触发器与玩家接触时(Enter),调用OnTriggerEnter(),修改枚举状态。
计算NPC到玩家的方向向量,将NPC旋转指向玩家。

当NPC的触发器与玩家分离时(Exit), 调用OnTriggerExit(),修改枚举状态。
将NPC的方向恢复到原有的方向向量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public class NPC : MonoBehaviour
{
public enum emTriggerType
{
None,
Enter,
Exit,
}
private Transform m_tfPlayer;
private emTriggerType m_emTriggerType;
private float m_fRotateSpeed;
private float m_fTimer;

private Quaternion m_srcRotation;

// Start is called before the first frame update
void Start()
{
m_tfPlayer = GameObject.FindObjectOfType<Player>().transform;
m_emTriggerType = emTriggerType.None;
m_fRotateSpeed = 3f;
m_fTimer = 0f;
m_srcRotation = transform.rotation;

SphereCollider trigger = transform.gameObject.AddComponent<SphereCollider>();
trigger.isTrigger = true;
trigger.radius = 10f;
}

// Update is called once per frame
void Update()
{
if(m_emTriggerType == emTriggerType.Enter)
{
//玩家位置减去NPC位置,得到非单位化的向量dir,几何意义是NPC指向玩家位置的方向向量
Vector3 dir = m_tfPlayer.transform.position - transform.position;
Quaternion targetQ = Quaternion.LookRotation(dir, Vector3.up);
transform.rotation = Quaternion.Lerp(transform.rotation, targetQ, Time.deltaTime * m_fRotateSpeed);

m_fTimer += Time.deltaTime; //计时器

if (m_fTimer >= 1f) {
m_emTriggerType = emTriggerType.None; //置空占位
m_fTimer = 0;
}
}
else if(m_emTriggerType == emTriggerType.Exit)
{
transform.rotation = Quaternion.Lerp(transform.rotation, m_srcRotation, Time.deltaTime * m_fRotateSpeed);
m_fTimer += Time.deltaTime;

if (m_fTimer >= 1f)
{
m_emTriggerType = emTriggerType.None;
m_fTimer = 0;
}
}
}

private void OnTriggerEnter(Collider other)
{
if (other.transform != m_tfPlayer) return;
m_emTriggerType = emTriggerType.Enter;
//Debug.Log("Trigger enter");

//弹出对话
}

private void OnTriggerExit(Collider other)
{
if (other.transform != m_tfPlayer) return;
m_emTriggerType = emTriggerType.Exit;
//Debug.Log("Trigger exit");

//关闭对话
}
}

UI元素添加 UI Component:

添加UI组件:

调用Resource下的相对路径文件。
导入UnityEngine.UI包。

将UI对象实例化,并挂载到附节点上。
从Resource中获得Text,Image等UI对象。

根据场景决定显示NPC名字还是HP血条。

在进行显示时,需要将NPC和玩家的世界坐标系位置转化到屏幕坐标系,将名字显示在屏幕。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
using System.Collections;
using System.Collections.Generic;
using UnityEngine;
using UnityEngine.UI; //UI的命名空间

public class Unity_Entity : MonoBehaviour
{
private GameObject m_objModel;

private Text m_txtCharacterName;
private GameObject m_objHPBar;
private Image m_imgHP;

public Vector3 mv3Offset;
// Start is called before the first frame update
void Start()
{
GameObject uiUnit = Resources.Load<GameObject>("Prefabs/UI/Unit_Entity"); //获取UI单元
uiUnit.SetActive(false);

mv3Offset = new Vector3(0f, 2f, 0f);

m_objModel = Instantiate<GameObject>(uiUnit); //实例化对象
m_objModel.transform.parent = GameObject.Find("UnitEntityRoot").transform; //将对象添加到附节点

m_txtCharacterName = m_objModel.transform.Find("Context/txtCharacterName").GetComponent<Text>(); //获取名称
m_objHPBar = m_objModel.transform.Find("Context/HPBar").gameObject;
m_imgHP = m_objModel.transform.Find("Context/HPBar/hp").GetComponent<Image>(); //获取血条图片资源

m_txtCharacterName.text = this.gameObject.name;
m_objHPBar.SetActive(!SceneManager.Instance.isMainScene); //不在主场景时才激活血条
}

// Update is called once per frame
void Update()
{
m_objModel.transform.position = Camera.main.WorldToScreenPoint(this.transform.position + mv3Offset);
//从世界坐标系转换为屏幕坐标系,将血条显示在屏幕上
}
}

为了判断我们的场景,我们需要创建一个SceneManager并挂载到Manager上。
当当前场景是主场景时返回true。

场景判断:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public class SceneManager : MonoBehaviour
{
public static SceneManager Instance;
public bool isMainScene
{
get //get和set可以封装public的field(Member Variable)
{
UnityEngine.SceneManagement.Scene curScene = UnityEngine.SceneManagement.SceneManager.GetActiveScene();
//由于Unity已经有ScenceManager类,因此需要额外注明命名空间
return curScene.name == "MainScene";
}
}
// Start is called before the first frame update
void Awake() //Awake的执行顺序优先于Start()
{
Instance = this;
}

// Update is called once per frame
void Update()
{

}
}