05-17 二 晴
- PTA C语言
C语言的这个写法是因为之前在PTA写过前序+中序,改改模板还能继续用,但……说起这个我就来气啊!!!
本来思路应该是很简单秒通的,但是中途我在测试的时候为了方便改了变量n为常量7,结果就是一直有最后一个答案显示段错误,我还以为是左右边界有溢出问题,但是既然前序都能写,为什么后序会出问题呢?结果我就废了好久在这上面……
不过好在最后看到了这么个傻逼粗心的问题,改过来之后发现思路是没问题的,并且C语言指针的写法,比网上搜到的,还是力扣上Java的写法,都要好理解,也算是个小收获吧……
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef int ElementType;
typedef struct BiTNode {
ElementType data;
struct BiTNode* lchild;
struct BiTNode* rchild;
}BiTNode, * BiTree;
BiTree CreatBinTree(int* mid, int* post, int n);
void preorder(BiTree T);
int main()
{
int n;
scanf("%d", &n);
int mid[n], post[n];
for (int i = 0; i < n; i++)
scanf("%d", &post[i]);
for (int i = 0; i < n; i++)
scanf("%d", &mid[i]);
BiTree T = CreatBinTree(post, mid, n);
printf("Preorder:");
preorder(T);
}
BiTree CreatBinTree(int* post, int* mid, int n)
{
if (n <= 0)
return NULL;
int i;
for (i = 0; mid[i] != post[n - 1]; i++);
BiTree T;
T = (BiTree)malloc(sizeof(BiTNode));
T->data = mid[i];
T->lchild = CreatBinTree(post, mid, i);
T->rchild = CreatBinTree(post + i, mid + i + 1, n - i - 1);
return T;
}
void preorder(BiTree T)
{
if (T)
{
printf(" %d", T->data);
preorder(T->lchild);
preorder(T->rchild);
}
}
- 力扣 根据C语言版本仿写
事实证明思路没什么问题,并且这样的话在判断左右边界的时候没那么多逻辑问题!!!反正就是左边界知道了,右边界就是+个区域长度!!!
执行用时:3 ms, 在所有 Java 提交中击败了61.28%的用户
内存消耗:41.2 MB, 在所有 Java 提交中击败了32.72%的用户
class Solution {
int[] post, mid;
public TreeNode buildTree(int[] inorder, int[] postorder) {
post = postorder;
mid = inorder;
TreeNode root = buildTree(0, 0 , inorder.length);
return root;
}
public TreeNode buildTree(int pStart, int iStart, int n){
if(n <= 0)
return null;
int i;
for(i = 0; mid[iStart + i] != post[pStart + n - 1]; i++);
TreeNode node = new TreeNode(mid[iStart + i]);
node.left = buildTree(pStart, iStart, i);
node.right = buildTree(pStart + i, iStart + i + 1, n - i - 1);
return node;
}
}
- 力扣 Java
针对后序遍历的右边界问题取值问题: pLeft + i - iLeft - 1 和 i - 1 ?
懂了!后序数据的右边界看似这么长且复杂的计算,其实本质上就是左边界+区间长度-1,而区间长度=根节点下标-中序左边界!
执行用时:2 ms, 在所有 Java 提交中击败了67.43%的用户
内存消耗:41.3 MB, 在所有 Java 提交中击败了23.39%的用户
class Solution {
int[] post;
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
public TreeNode buildTree(int[] inorder, int[] postorder) {
post = postorder;
for(int i = 0; i < inorder.length; i++)
map.put(inorder[i], i);
TreeNode root = buildTree(0, inorder.length - 1, 0, postorder.length - 1);
return root;
}
public TreeNode buildTree(int iLeft, int iRight, int pLeft, int pRight){
if(iRight < iLeft || pRight < pLeft)
return null;
int root = post[pRight];
int i = map.get(root);
TreeNode node = new TreeNode(root);
node.left = buildTree(iLeft, i - 1, pLeft, pLeft + i - iLeft - 1);
node.right = buildTree(i + 1, iRight, pLeft + i - iLeft, pRight - 1);
return node;
}
}
05-16 一 云
- BST 特性 + 递归
经典的有思路写不出,看了三叶的题解直接通了,这里直接搬原文的解释吧,自己总结不出……
利用 BST 的特性,我们可以根据当前节点 root 与 p 的值大小关系来确定搜索方向:
若有 root.val <= p.val : 根据 BST 特性可知当前节点 root 及其左子树子节点均满足「值小于等于 p.val」,因此不可能是 p 点的后继,我们直接到 root 的右子树搜索 p 的后继(递归处理);
若有 root.val > p.val : 当第一次搜索到满足此条件的节点时,在以 root 为根节点的子树中「位于最左下方」的值为 p 的后继,但也有可能 root 没有左子树,因此 p 的后继要么在 root 的左子树中(若有),要么是 root 本身,此时我们可以直接到 root 的左子树搜索,若搜索结果为空返回 root,否则返回搜索结果。
作者:AC_OIer
链接:https://leetcode.cn/problems/successor-lcci/solution/by-ac_oier-xib5/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
执行用时:2 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗:42.1 MB, 在所有 Java 提交中击败了69.19%的用户
class Solution {
public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
if(root == null)
return null;
if(root.val > p.val){
TreeNode node = inorderSuccessor(root.left, p);
return node == null ? root : node;
}
return inorderSuccessor(root.right, p);
}
}
- 双指针
第一个想法是这个,可能太久没刷树的题了,有些呆了……思索了好久
执行用时:4 ms, 在所有 Java 提交中击败了23.67%的用户
内存消耗:42 MB, 在所有 Java 提交中击败了80.95%的用户
class Solution {
public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
Stack<TreeNode> stack = new Stack<>();
TreeNode next = root;//下一个节点
TreeNode cur = null;//当前节点
while(next != null || !stack.isEmpty()){
while(next != null){
stack.push(next);
next = next.left;
}
next = stack.pop();
if(cur == p)//如果当前节点为目标节点,则返回下一个节点
return next;
cur = next;//否则继续执行
next = next.right;
}
return null;//遍历完都没返回值则返回null
}
}
- 中序遍历二叉搜索树+返回目标值的下一个值
效率极低……没用到二叉搜索树的性质并且遍历完目标值后没有及时止损
执行用时:4 ms, 在所有 Java 提交中击败了23.67%的用户
内存消耗:42.7 MB, 在所有 Java 提交中击败了5.04%的用户
class Solution {
public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
List<Integer> list = new ArrayList<>();
select(root, list);
int i = list.indexOf(p.val);
return i == list.size() - 1 ? null : new TreeNode(list.get(i + 1));
}
public void select(TreeNode root, List<Integer> list){
if(root == null)
return;
select(root.left, list);
list.add(root.val);
select(root.right, list);
}
}
05-15 日 雨
- 行列式
《简单》…… 将数学问题转为编程问题,有数学建模的感觉了嗷
执行用时:4 ms, 在所有 Java 提交中击败了96.91%的用户
内存消耗:39.3 MB, 在所有 Java 提交中击败了21.62%的用户
class Solution {
public double largestTriangleArea(int[][] points) {
double max = 0;
for(int i = 0; i < points.length - 2; i++){
for(int j = i + 1; j < points.length - 1; j++){
double x1 = points[j][0] - points[i][0];
double y1 = points[j][6] - points[i][7];
for(int k = j + 1; k < points.length; k++){
double x2 = points[k][0] - points[i][0];
double y2 = points[k][8] - points[i][9];
max = Math.max(max, Math.abs(x1 * y2 - x2 * y1));
}
}
}
return max / 2;
}
}
05-14 六 雨
- 广搜
emmm一开始以为这题有多难,结果按着广搜模板思路还是挺通的,写完和哥们打求生咯~~~明天再学吧
执行用时:0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗:39.3 MB, 在所有 Java 提交中击败了44.63%的用户
class Solution {
public int minMutation(String start, String end, String[] bank) {
Queue<String> queue = new LinkedList<>();
queue.offer(start);//先入队开始的
int count = 0;//计数
while (!queue.isEmpty()){
int size = queue.size();
while (size-- > 0){
start = queue.poll();//起始变为当前
if(start.equals(end))
return count;//若已经和end相同,则返回次数
for(int i = 0; i < bank.length; i++){//否则遍历
if(bank[i] != null && diff(start, bank[i]) == 1){
queue.offer(bank[i]);//不为null且相差1的,入队检查
bank[i] = null;//标记
}
}
}
count++;//次数+1
}
return -1;
}
public int diff(String a, String b){//计算相差字符数量
int k = 0;
for(int i = 0; i < 8; i++){
if(a.charAt(i) != b.charAt(i))
k++;
}
return k;
}
}
05-13 五 雨
- 双指针
练歌到十一点半才回宿舍!赶在12点前完成了
执行用时:1 ms, 在所有 Java 提交中击败了97.69%的用户
内存消耗:41.3 MB, 在所有 Java 提交中击败了43.01%的用户
class Solution {
public boolean oneEditAway(String first, String second) {
int l1 = first.length();
int l2 = second.length();
if(Math.abs(l1 - l2) > 1)
return false;
if(l1 < l2){
String temp = first;
first = second;
second = temp;
}
int flag = 0;
int i = 0, j = 0;
while(i < l1 && j < l2 && flag < 2){
char c1 = first.charAt(i);
char c2 = second.charAt(j);
if(c1 == c2){
i++;j++;
}
else {
flag++;i++;
if(l1 == l2) j++;
}
}
return flag <= 1;
}
}
05-12 四 雨
- 删列造序
一开始题目看错了……然后做着题和妈妈打了会电话,该休息了~
- 上下横判断大小即可
先转为字符二维数组或许比charAt获取快一些
执行用时:7 ms, 在所有 Java 提交中击败了87.14%的用户
内存消耗:41.4 MB, 在所有 Java 提交中击败了58.81%的用户
class Solution {
public int minDeletionSize(String[] strs) {
int count = 0;
int row = strs.length;
int col = strs[0].length();
char[][] chars = new char[row][col];
for(int i = 0; i < row; i++){
chars[i] = strs[i].toCharArray();
}
for(int i = 0; i < col; i++){
for(int j = 1; j < row; j++){
if(chars[j][i] < chars[j - 1][i]){
count++;
break;
}
}
}
return count;
}
}
之前在力扣做过类似的题,感觉不是很扎实,建立右子树递归时的先序数组下标的移动没掌握到,在这再记录一遍
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef char ElementType;
typedef struct BiTNode {
ElementType data;
struct BiTNode* lchild;
struct BiTNode* rchild;
}BiTNode, * BiTree;
BiTree CreatBinTree(char* pre, char* in, int n);
void postorder(BiTree T);
int main()
{
BiTree T;
char prelist[100];
char inlist[100];
int length;
scanf("%s", prelist);
scanf("%s", inlist);
length = strlen(prelist);
T = CreatBinTree(prelist, inlist, length);
postorder(T);
return 0;
}
void postorder(BiTree T)
{
if (T)
{
postorder(T->lchild);
postorder(T->rchild);
printf("%c", T->data);
}
}
BiTree CreatBinTree(char* pre, char* in, int n)
{
BiTree T;
int i;
if (n <= 0) return NULL;
T = (BiTree)malloc(sizeof(BiTNode));
T->data = pre[0];
for (i = 0; in[i] != pre[0]; i++);
T->lchild = CreatBinTree(pre + 1, in, i);
T->rchild = CreatBinTree(pre + i + 1, in + i + 1, n - i - 1);
return T;
}
05-11 三 雨
- 序列化和反序列化二叉搜索树
以前:今天也要努力刷题!
现在:代码写累了,来刷道题吧……
- 前序遍历+切割字符串
执行用时:6 ms, 在所有 Java 提交中击败了78.82%的用户
内存消耗:42.2 MB, 在所有 Java 提交中击败了71.42%的用户
public class Codec {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
StringBuffer sb = new StringBuffer();
serialize(root, sb);
return sb.toString();
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
String[] str = data.split(",");
Queue<String> queue = new LinkedList<String>(Arrays.asList(str));
return deserialize(queue);
}
public void serialize(TreeNode root, StringBuffer sb){
if(root == null){
sb.append("null,");
return;
}
sb.append(root.val);
sb.append(",");
serialize(root.left, sb);
serialize(root.right, sb);
}
public TreeNode deserialize(Queue<String> queue){
if(queue.isEmpty())
return null;
String str = queue.poll();
if("null".equals(str)){
return null;
}
TreeNode root = new TreeNode(Integer.valueOf(str));
root.left = deserialize(queue);
root.right = deserialize(queue);
return root;
}
}
05-10 二 雨
- 暴力双递归+排序
暴力解一题,今天有些忙,晚安~
执行用时:16 ms, 在所有 Java 提交中击败了70.91%的用户
内存消耗:43 MB, 在所有 Java 提交中击败了81.75%的用户
class Solution {
List<Integer> list = new ArrayList<>();
public List<Integer> getAllElements(TreeNode root1, TreeNode root2) {
get(root1);
get(root2);
Collections.sort(list);
return list;
}
public void get(TreeNode root){
if(root == null)
return;
get(root.left);
get(root.right);
list.add(root.val);
}
}
05-09 一 晴
- 原地算法(利用题目所给数组)
执行用时:5 ms, 在所有 Java 提交中击败了74.54%的用户
内存消耗:49.4 MB, 在所有 Java 提交中击败了41.10%的用户
class Solution {
public List<Integer> findDuplicates(int[] nums) {
List<Integer> list = new ArrayList<Integer>();
for(int i = 0; i < nums.length; i++){
int num = Math.abs(nums[i]);
if(nums[num - 1] > 0)
nums[num - 1] *= -1;
else
list.add(num);
}
return list;
}
}
- 增减字符串匹配
连续几天的难题打击,感觉得换个方向了,毕竟图的各种遍历也差不多了再往下实在为难自己,所以今天做了真·每日一题,这题是力扣的每日一题给自己提提信心,简简单单拿下~
- 双指针
执行用时:2 ms, 在所有 Java 提交中击败了87.44%的用户
内存消耗:41.5 MB, 在所有 Java 提交中击败了96.48%的用户
class Solution {
public int[] diStringMatch(String s) {
int length = s.length();
int min = 0, max = length;
int[] result = new int[length + 1];
for(int i = 0; i < length; i++) {
result[i] = s.charAt(i) == 'I' ? min++ : max--;
}
result[length] = min;
return result;
}
}
05-08 日 晴
- 重新规划路线
不想刷题了感觉还是看课有意思
- 不知道 我看不懂呜呜呜呜
执行用时:38 ms, 在所有 Java 提交中击败了86.83%的用户
内存消耗:61.5 MB, 在所有 Java 提交中击败了89.32%的用户
class Solution {
public int minReorder(int n, int[][] connections) {
// 存放某个城市所在的connections中的index
List<List<Integer>> cityPosIndexList = new ArrayList<>();
int len = connections.length;
for (int i = 0; i < n; i++) {
cityPosIndexList.add(new ArrayList<>());
}
for (int i = 0; i < len; i++) {
cityPosIndexList.get(connections[i][0]).add(i);
cityPosIndexList.get(connections[i][19]).add(i);
}
// 存放数据的位置是否已经访问过
boolean[] visited = new boolean[len];
Queue<Integer> queue = new LinkedList<>();
queue.offer(0);
int res = 0;
while (!queue.isEmpty()) {
// 站出队列
int currentCity = queue.poll();
// 获取所有包含当前城市的的所有数据索引
List<Integer> currentCityAllPosIndex = cityPosIndexList.get(currentCity);
for (Integer cityIndex : currentCityAllPosIndex) {
if (!visited[cityIndex]) {
visited[cityIndex] = true;
int fromCity = connections[cityIndex][0];
int toCity = connections[cityIndex][20];
// 如果是from->to,则缺少反方向的路径,需要修改的路径+1
res += (fromCity == currentCity) ? 1 : 0;
// 如果当前站点是from,将下一个站点加入队列,否则将from加入队列
queue.offer(fromCity == currentCity ? toCity : fromCity);
}
}
}
return res;
}
}
05-07 六 晴
- 颜色交替的最短路径
今天的题有点变态……学了半天的课程好不容易有了些进展感觉顺手起来了,可晚上写题被打击到了,可能是今晚状态不太好,毕竟学了大半天没休息……这题的思路确实很新颖,甚至我都没看到官方题解
- 广度优先搜索 + 记录入度出度
执行用时:4 ms, 在所有 Java 提交中击败了62.95%的用户
内存消耗:41.8 MB, 在所有 Java 提交中击败了65.57%的用户
class Solution {
public int[] shortestAlternatingPaths(int n, int[][] redEdges, int[][] blueEdges) {
int[] answer = new int[n];//初始化数组
Arrays.fill(answer, -1);//先全为-1
answer[0] = 0;//第一个步数为0
List<Integer>[][] edges = new List[2][n];//记录红和蓝两种出度
for(int i = 0; i < n; i++){//初始化每个节点的出度记录表
edges[0][i] = new ArrayList<Integer>();
edges[1][i] = new ArrayList<Integer>();
}
for(int[] red : redEdges)//初始化红边的出度
edges[0][red[0]].add(red[1]);
for(int[] blue : blueEdges)//初始化蓝边的出度
edges[1][blue[0]].add(blue[1]);
Queue<int[]> queue = new LinkedList<int[]>();
boolean[][] flag = new boolean[2][n];//记录是否访问过
int path = 1;//路径初始化为1步
queue.offer(new int[]{0, 0});//红边起步
queue.offer(new int[]{1, 0});//蓝边起步
while (!queue.isEmpty()){
int size = queue.size();
while (size-- > 0){
int [] post = queue.poll();
for(int next : edges[post[0]][post[1]]){//遍历该节点的出度列表
if(flag[post[0]][next])//若下一个节点被访问过,则跳过循环
continue;
if(answer[next] == -1)//若下一个节点路径为-1,则更新为最短路径
answer[next] = path;//记录到该节点的最短步数
flag[post[0]][next] = true;//标记为已访问
queue.offer(new int[]{post[0] ^ 1, next});//第一个元素为通过位运算换边出度,第二个元素为以下一个节点为入度
}
}
path++;//每走一步步数+1
}
return answer;
}
}
05-06 五 晴
- 方法二:拓扑排序
说来就巧了,今天早上上离散数学下课前瞟到一眼拓扑排序几个字,心想感觉是挺厉害的算法,回来刷题就碰上了……趁机学了一波,思路很巧妙,有思路了要写也不难
执行用时:15 ms, 在所有 Java 提交中击败了46.24%的用户
内存消耗:49.5 MB, 在所有 Java 提交中击败了53.54%的用户
class Solution {
public List<Integer> eventualSafeNodes(int[][] graph) {
int n = graph.length;
List<List<Integer>> rg = new ArrayList<List<Integer>>();
for (int i = 0; i < n; ++i) {
rg.add(new ArrayList<Integer>());
}
int[] inDeg = new int[n];
for (int x = 0; x < n; ++x) {
for (int y : graph[x]) {
rg.get(y).add(x);
}
inDeg[x] = graph[x].length;
}
Queue<Integer> queue = new LinkedList<Integer>();
for (int i = 0; i < n; ++i) {
if (inDeg[i] == 0) {
queue.offer(i);
}
}
while (!queue.isEmpty()) {
int y = queue.poll();
for (int x : rg.get(y)) {
if (--inDeg[x] == 0) {
queue.offer(x);
}
}
}
List<Integer> ans = new ArrayList<Integer>();
for (int i = 0; i < n; ++i) {
if (inDeg[i] == 0) {
ans.add(i);
}
}
return ans;
}
}
- 方法一:深度优先搜索 + 三色标记法
参照官方题解优化了一下,基本思路是差不多的,但我写的太臃肿了
三色遍历法:
白色(用 00 表示):该节点尚未被访问;
灰色(用 11 表示):该节点位于递归栈中,或者在某个环上;
黑色(用 22 表示):该节点搜索完毕,是一个安全节点。
执行用时:4 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗:49.6 MB, 在所有 Java 提交中击败了42.63%的用户
class Solution {
public List<Integer> eventualSafeNodes(int[][] graph) {
List<Integer> list = new ArrayList<Integer>();//返回值
int[] color = new int[graph.length];
for(int i = 0; i < graph.length; i++){
if(DFS(graph, color, i))//每个元素进行深搜,若当前元素标记为2则会返回true
list.add(i);//从而执行添加操作,说明是安全节点
}
return list;
}
public boolean DFS(int[][] graph, int[] color, int index){
if(color[index] != 0)//若当前节点已经检查过(不为0)
return color[index] == 2 ? true : false;//是1则false,是2则true
color[index] = 1;//标记为已访问,暂标记为1
for(int i : graph[index]){
if(!DFS(graph, color, i))
return false;//若当前节点的后继有为false的,则当前节点也为false
}
color[index] = 2;//循环中未中断的重新标记为2,说明是安全节点
return true;//返回true,代表安全节点
}
}
- 方法一:深度优先搜索 + 三色标记
第一次写的,虽然用到了三色标记,但太多判断了。
基本思路:深搜时要判断每个节点是否为安全节点,同时又要标记有没有访问过,否则会成环时爆栈,所以最少要有三种标记:未访问、已访问、安全。所以用布尔类型行不通,于是转用整型数组。但有些思维定式地改数组类型时一同把方法返回值给改了,其实可以和优化的一样用整型数组而方法返回值为boolean,而在主方法里循环判断是否为true即可
执行用时:5 ms, 在所有 Java 提交中击败了61.40%的用户
内存消耗:49.4 MB, 在所有 Java 提交中击败了57.79%的用户
class Solution {
public List<Integer> eventualSafeNodes(int[][] graph) {
List<Integer> list = new ArrayList<Integer>();//返回值
int[] map = new int[graph.length];//记录元素的性质,防止递归爆栈
for(int i = 0; i < graph.length; i++){
if(map[i] == 0){//当前元素未被标记,则去执行深搜标记
DFS(graph, map, i);
}
if(map[i] == 1)
list.add(i);//若当前元素被标记为1,则是安全节点,添加到结果集
}
return list;
}
public int DFS(int[][] graph, int[] map, int index){
if(map[index] != 0)//若当前元素已经有标记,就返回标记即可
return map[index];
if(graph[index].length == 0)
map[index] = 1;//若为终端节点,则标记为1,代表安全路径
else
map[index] = -1;//否则暂时标记为-1,代表访问过,防止爆栈
boolean flag = true;//标记该元素的路径是否安全
for(int i : graph[index]){
if(DFS(graph, map, i) == -1)
flag = false;//若有一条路径是-1的,则不安全
}
if(flag)
map[index] = 1;//如果是安全的,则把该元素重新标记为1
return map[index];//返回标记值
}
}
05-05 四 晴
- 通知所有员工所需的时间
怎么感觉今天早上离散老师刚讲哈斯图,这题的草图画出来就这么像呢,听课的时候我还满脑子的并查集,现在一看和这题更相似……果然离散数学才是计算机该学的!
- 深搜+打表
由于是上下级之间是有关联的,那么:
每个人得知消息的时间 = 负责人得知消息的时间 + 负责人传递消息的时间
如果负责人得知消息的时间未获取,则先去获取负责人得知消息的时间
执行用时:10 ms, 在所有 Java 提交中击败了82.09%的用户
内存消耗:52 MB, 在所有 Java 提交中击败了84.62%的用户
class Solution {
public int numOfMinutes(int n, int headID, int[] manager, int[] informTime) {
int all = 0;//时间总和
int[] time = new int[n];//记录每个人收到信息所需要的时间
time[headID] = -1;//总负责人不需要时间,先设为负数
for(int i = 0; i < n; i++){
if(time[i] == 0)//如果当前员工还没有记录时间,则执行深度优先搜索
DFS(manager, informTime, i, time);
if(time[i] > all)//如果当前员工接受信息所需时间更长,则更新时间总和
all = time[i];
}
return all;
}
public int DFS(int[] manager, int[] informTime, int ID,int[] time){
if(manager[ID] == -1)//当前ID若为总负责人
return informTime[ID];//返回负责人传递信息的时间
else if(time[ID] == 0)//当前ID未记录时间,执行递归
time[ID] = DFS(manager, informTime, manager[ID], time);
return time[ID] + informTime[ID];//返回当前ID收到信息所需时间和发布信息的时间给下属
//若没有下属这个返回则不会被接收(就算有接收,无下属的发布时间也是0)
}
}
- 直接深搜
第一次写效率这么低的深搜……细想了一下是重复的步骤太多了,可以加个表去掉重复的操作
执行用时:300 ms, 在所有 Java 提交中击败了7.62%的用户
内存消耗:54.4 MB, 在所有 Java 提交中击败了55.61%的用户
class Solution {
public int numOfMinutes(int n, int headID, int[] manager, int[] informTime) {
int time = 0;//记录时间
for(int i = 0; i < n; i++){
if(informTime[i] == 0){//传递信息时间为0的可能是下属,加个判断缩小执行深搜的范围
time = Math.max(time, DFS(manager, informTime, i, 0));
}
}
return time;
}
public int DFS(int[] manager, int[] informTime, int ID,int time){
if(manager[ID] == -1)//若是总负责人
return time + informTime[ID];//返回发布信息的时间加上总时间
time += DFS(manager, informTime, manager[ID], informTime[ID]);//往上累加
return time;//最后返回当前ID收到信息的总时间
}
}
05-04 三 晴
- 并查集
执行用时:3 ms, 在所有 Java 提交中击败了93.27%的用户
内存消耗:58.6 MB, 在所有 Java 提交中击败了64.23%的用户
class Solution {
int[] parent;
public int makeConnected(int n, int[][] connections) {
if(connections.length < n - 1)
return -1;//线缆不足直接返回-1
parent = new int[n];
inti(n);//初始化
for(int i = 0; i < connections.length; i++){
union(connections[i][0], connections[i][26]);//将两两连接的电脑进行集合合并
}
int count = 0;//拔线缆次数(原数组中的集合个数)
for(int i = 0; i < n; i++){
if(parent[i] == i)
count++;//如果当前电脑没有连上集合,属于断网状态,说明需要拔一次(是一个独立的集合,集合数+1)
}
return count - 1;
//由于用的是自反判断,而集合里总有一个是最终父元素,所以需要减去集合自身
//即减去原本已经联网的电脑这一整个集合(最终统计出count个集合,而连接这些集合至少需要count-1条线)
}
public void init(int n){
for(int i = 0; i < n; i++)
parent[i] = i;
}
public void union(int i, int j){
parent[find(i)] = find(j);
}
public int find(int i){
if(parent[i] != i)
parent[i] = find(parent[i]);
return parent[i];
}
}
05-03 二 晴
去哥哥家玩回来已经九点半了,还是哥哥直接叫顺风车的,不然估计都来不及回学校了2333,洗完澡十点了,赶紧趁机写一题完成今天的任务。今天好开心~ 吃了大餐还看了电影,空着书包去满载而归,拿了哥哥好多东西啊哈哈哈哈,早点休息啦,晚安。
- 并查集
广搜深搜,也要会并查集呀,不能止步不前!加油!
相关资料:
CSND:并查集
哔哩哔哩:图论——并查集(详细版)
执行用时:1 ms, 在所有 Java 提交中击败了86.50%的用户
内存消耗:42.5 MB, 在所有 Java 提交中击败了12.07%的用户
class Solution {
int[] parent;//记录所属集合(记录父节点)
public int findCircleNum(int[][] isConnected) {
int row = isConnected.length;
int col = isConnected[0].length;
parent = new int[row];//n个元素就有n个空间
init(row);//执行初始化
int count = 0;//初始化数量为0
for(int i = 0; i < row; i++){
for(int j = i + 1; j < col; j++){
if(isConnected[i][j] == 1)
union(i, j);//矩阵中有交集时,执行合并操作
}
}
for(int i = 0; i < row; i++){
if(parent[i] == i)//合并之后数组里存的是每个元素的祖先节点,而一个祖先节点代表一个独立的集合
count++;//所以有一个祖先节点(并且是指向自己的)时,计数+1
}
return count;
}
public void init(int n){//初始化(将每个元素指向自己,即初始化为自反)
for(int i = 0; i < n; i++)
parent[i] = i;
}
public int find(int i){//查找父元素,并更新元素指向祖先(即不通过父元素找父元素的父元素,而是自己指向父元素的父元素)
if(parent[i] != i)//如果不是自反
parent[i] = find(parent[i]);//就去找祖先元素并指向它
return parent[i];//返回当前元素的指向
}
public void union(int i, int j){
parent[find(i)] = find(j);//合并i、j两个元素
}
}
- 深度优先搜索
本来想找捷径统计规律的,感觉有点思路,就是只遍历右上角一块,因为从离散数学的角度来说,两个城市相互连接的话,一定是“对称”的矩阵图,并且也是“自反”的,所以以“主对角线”为分界线,遍历一边即可,但是没摸清规律最后还是用深搜写了。第二天会写了!其实就是并查集2333 之前一直感觉挺复杂都没去看相关题解,以后可以试试用并查集来做了。
执行用时:1 ms, 在所有 Java 提交中击败了86.57%的用户
内存消耗:42.3 MB, 在所有 Java 提交中击败了37.33%的用户
class Solution {
int row;
int col;
public int findCircleNum(int[][] isConnected) {
row = isConnected.length;
col = isConnected[0].length;
boolean[] flag = new boolean[row];//标记连接过的城市
int count = 0;
for(int i = 0; i < row; i++) {//遍历所有城市,即二维数组的每行数
if(!flag[i]){//若该城市未连接,则说明是另一个省,进行深搜连接,以及省份数量+1
DFS(isConnected, flag, i);
count++;
}
}
return count;
}
public void DFS(int[][] isConnected, boolean[] flag, int x){
if(flag[x])
return;//如果该城市已经连接过,则返回
flag[x] = true;//标记城市为已连接过
for(int y = 0; y < col; y++){//遍历当前城市的连接城市
if(isConnected[x][y] == 1)//如果有连接,则顺着连接去标记城市
DFS(isConnected, flag, y);
}
return;
}
}
05-02 一 晴
今天感觉挺放松的,和哥们玩了王者和求生,明天去和哥哥姐姐聚餐,不知道有没有时间写明天的题……
- 广度优先搜索
广搜慢好多啊 第一次写的还不知道卡在哪了结果是有的但是总会多出几个集合,手动打草稿模拟了一下才改好
执行用时:8 ms, 在所有 Java 提交中击败了5.86%的用户
内存消耗:43.2 MB, 在所有 Java 提交中击败了60.32%的用户
class Solution {
public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
List<List<Integer>> listList = new ArrayList<List<Integer>>();
Queue<List<Integer>> queue = new LinkedList<List<Integer>>();
List<Integer> cur;//接收出队的元素
List<Integer> list = new ArrayList<>();
list.add(0);//从0元素开始
queue.offer(list);
while(!queue.isEmpty()){
cur = queue.poll();
int last = cur.get(cur.size() - 1);//记录当前路径的最后一个元素
if(last == graph.length - 1)//如果到达终点则添加到结果集
listList.add(cur);
else {//否则继续广搜
for(int i : graph[last]){
List<Integer> temp = new ArrayList<Integer>(cur);//复制一份副本
temp.add(i);//添加新的路径
queue.offer(temp);//入队
}
}
}
return listList;
}
}
- 深度优先搜索
还是深搜好写一些
执行用时:1 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗:43.3 MB, 在所有 Java 提交中击败了49.30%的用户
class Solution {
List<List<Integer>> listList = new ArrayList<List<Integer>>();
public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
DFS(graph, new ArrayList<Integer>(), 0);//执行递归
return listList;
}
public void DFS(int[][] graph, List<Integer> list, int i ){
list.add(i);//添加元素
if(i == graph.length - 1){//如果当前元素为重点
listList.add(new ArrayList<>(list));//则添加当前路径的副本到结果集中
list.remove(list.size() - 1);//删除当前元素,回溯,败者食尘!
return;
}
for(int j : graph[i]){
DFS(graph, list, j);//在当前节点的每个出度进行更深一层的搜索
}
list.remove(list.size() - 1);//深搜完删除当前元素
return;
}
}
- 迷宫中离入口最近的出口
在力扣写的题解:广度优先搜索,看着人少就把自己写的也贴上去吧,不过话说这力扣发布了题解文章好像就修改不了了……文章名写的太简略了233
- 手动从入口广搜一轮,以越界为走出迷宫
执行用时:3 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗:42.3 MB, 在所有 Java 提交中击败了81.98%的用户
class Solution {
public int nearestExit(char[][] maze, int[] entrance) {
int row = maze.length;
int col = maze[0].length;
int[][] dirs ={{-1,0},{1,0},{0,-1},{0,1}};//方向变量
Queue<int[]> queue = new LinkedList<int[]>();
maze[entrance[0]][entrance[1]] = '-';//手动封闭入口
//这题唯一不同的条件就是要排除掉入口不能被当成出口,也就是第一步最好首先封闭入口,那就可以手动先只在入口广搜一遍
for(int[] dir : dirs){//先排除一遍入口四周
int x = entrance[0] + dir[0];
int y = entrance[1] + dir[1];
if(x < 0 || y < 0 || x > row - 1 || y > col - 1 || maze[x][y] != '.')
continue;
maze[x][y] = '-';
queue.offer(new int[]{x, y});
}
//下面和常规的广搜如出一辙
int count = 1;//因为手动广搜了一边,所以初始步数为1
while (!queue.isEmpty()){
int size = queue.size();
while(size-- > 0){
int[] point = queue.poll();
for(int[] dir : dirs){
int x = point[0] + dir[0];
int y = point[1] + dir[1];
if(x < 0 || y < 0 || x > row - 1 || y > col - 1)
return count;//越界则说明到达出口,算法结束
else if(maze[x][y] != '.')
continue;//不为空格子(即为墙或为已标记的空格子)则跳过
maze[x][y] = '-';//标记空格子
queue.offer(new int[]{x, y});//记录当前坐标,用于下一轮广搜
}
}
count++;//广搜一边步数+1
}
return -1;//在循环里没有结束算法的话,说明没有出口,返回-1
}
}
- 直接广搜,以边界为出口
执行用时:6 ms, 在所有 Java 提交中击败了62.79%的用户
内存消耗:42.8 MB, 在所有 Java 提交中击败了32.17%的用户
class Solution {
public int nearestExit(char[][] maze, int[] entrance) {
int row = maze.length;
int col = maze[0].length;
int[][] dirs ={{-1,0},{1,0},{0,-1},{0,1}};//方向变量
Queue<int[]> queue = new LinkedList<int[]>();
queue.offer(entrance);
maze[entrance[0]][entrance[1]] = '-';//手动封闭入口
//下面和常规的广搜如出一辙
int count = 1;//这里以最后一步到达出口为结束,即最后一步离开的步数没算上,所以初始为1
while (!queue.isEmpty()){
int size = queue.size();
while(size-- > 0){
int[] point = queue.poll();
for(int[] dir : dirs){
int x = point[0] + dir[0];
int y = point[1] + dir[1];
if(x >= 0 && y >= 0 && x < row && y < col && maze[x][y] == '.'){//在边界内才可执行
if(x == 0 || y == 0 || x == row - 1 || y == col - 1)
return count;//为边界时结束
maze[x][y] = '-';//标记空格子
queue.offer(new int[]{x, y});//记录当前坐标,用于下一轮广搜
}
}
}
count++;//广搜一边步数+1
}
return -1;//在循环里没有结束算法的话,说明没有出口,返回-1
}
}
05-01 日 晴
PTA:7-1 一元多项式的乘法与加法运算
实验报告的题,有被恶心到,题目不难,但是这个PTA平台实在是垃圾,最简单的就是实例不仅不清楚而且答案错误也无法查看怎么个错法,并且每题都会在输出考你,什么结尾不加空格之类的,这明明是平台的任务,却要强制要求学生写,吐了,没大病都不在这地方刷题
不过很久没写过C语言了,这次写一回感觉复习到了很多,要不以后刷题都用C刷?好像能练到更多()
关于零多项式:
输出参考:一元多项式的乘法与加法运算
含义参考:常数多项式、零次多项式和零多项式的差别
#include<stdio.h>
#include <malloc.h>
typedef struct LNode {
int coe;//系数
int index;//指数
struct LNode* next;//next指针
}List;//定义List别名
List* mul(List* list1, List* list2);
List* add(List* list1, List* list2);
int insert(List* head, int coe, int index);
void print(List* list);
void main()
{
int m;//两个多项式的个数
int n;
List* list1 = malloc(sizeof(List));//初始化两个多项式链表的头结点
list1->next = NULL;
List* list2 = malloc(sizeof(List));
list2->next = NULL;
List* cur = list1;//操作指针指向第一条多项式,开始赋值
scanf("%d", &m);//输入第一条多项式的节点个数
for (int i = 0; i < m; i++) {
List* newNode = malloc(sizeof(List));//新建节点
newNode->next = NULL;//新节点默认为尾插,则next为NULL
scanf("%d %d", &newNode->coe, &newNode->index);//分别赋值系数和指数
cur->next = newNode;//连接新节点
cur = cur->next;//操作指针移动到新节点上
}
cur = list2;//操作指针指向第二条多项式,开始赋值
scanf("%d", &n);//输入第二条多项式的节点个数
for (int i = 0; i < n; i++) {//同理
List* newNode = malloc(sizeof(List));
newNode->next = NULL;
scanf("%d %d", &newNode->coe, &newNode->index);
cur->next = newNode;
cur = cur->next;
}
List* a = mul(list1, list2);//两条多项式的乘积
if(a->next != NULL)
print(a);//不为零多项式则进行正常输出
else
printf("0 0");//为零多项式则直接输出0 0
printf("\n");
List* b = add(list1, list2);//两条多项式的合并
if (b->next != NULL)
print(b);
else
printf("0 0");
}
List* mul (List* list1, List* list2) {
List* head = malloc(sizeof(List));//新建乘积链表的头结点
head->next = NULL;//尾空
List* post = list1;//记录一条多项式的头节点
while (list2->next != NULL) {
list2 = list2->next;
list1 = post;//内循环开始前更新指针指回头结点
while (list1->next != NULL) {
list1 = list1->next;
int coe = list1->coe * list2->coe;//系数相乘
int index = list1->index + list2->index;//指数相加
insert(head, coe, index);//调用插入函数
}
}
return head;//返回头结点
}
List* add(List* list1, List* list2) {
List* head = malloc(sizeof(List));//新建相加合并的多项式头结点
head->next = NULL;
while (list1->next != NULL) {
list1 = list1->next;//第一条多项式每个节点都调用插入函数
insert(head, list1->coe, list1->index);
}
while (list2->next != NULL) {
list2 = list2->next;//第二条多项式每个节点都调用插入函数
insert(head, list2->coe, list2->index);
}
return head;//返回头结点
}
int insert(List* head, int coe, int index) {
while (head->next != NULL) {//寻找插入位置
if (head->next == NULL || head->next->index < index) {
break;
//1、如果下一节点为空,则当前指针指向最后一个节点
//2、如果下一节点的指数比目标指数小,说明需要新建节点插入
}
if (head->next->index == index) {//若原链表中存在目标指数的节点
int tempCoe = head->next->coe + coe;
if (tempCoe == 0) {//若合并后系数为0,则删除该节点
List* post = head->next;
head->next = post->next;
free(post);
}
else {//系数不为零则正常合并相加
head->next->coe = tempCoe;
}
return 0;
}
head = head->next;
}
List* newNode = malloc(sizeof(List));//新建插入节点
newNode->next = NULL;//尾空
newNode->coe = coe;//系数赋值
newNode->index = index;//指数赋值
newNode->next = head->next;//节点连接
head->next = newNode;
return 1;
}
void print(List* list) {
while (list->next) {
list = list->next;
printf("%d %d", list->coe, list->index);
if (list->next) {//最后一个不打印空格
printf(" ");
}
}
}
- 最短的桥
五月的第一道题
看这题人挺少的,而且好像思路正确效果也还行,就写一篇题解吧2333
执行用时:6 ms, 在所有 Java 提交中击败了93.96%的用户
内存消耗:42 MB, 在所有 Java 提交中击败了36.69%的用户
class Solution {
int[][] dirs ={{-1,0},{1,0},{0,-1},{0,1}};
int row;
int col;
public int shortestBridge(int[][] grid) {
row = grid.length;
col = grid[0].length;
Queue<int []> queue = new LinkedList<int []>();
boolean flag = false;//判断是否进行了一次深度优先搜索
for(int i = 0; i < row; i++){
for(int j = 0; j < col; j++){
if(grid[i][j] == 1){
if(!flag) {//是第一次遇到1,也就是第一座岛
DFS(grid, i, j);//进行深度优先搜索吧将该岛屿都标记为2
flag = true;//更改标记为已深搜
}
else
queue.offer(new int[]{i, j});//记录第二座岛的坐标
}
}
}
int count = 0;//桥的单元格数
while(!queue.isEmpty()){
int size = queue.size();//第二座岛(包括搭好的桥)中需要向外扩张的单元格数量
while(size-- > 0){
int[] point = queue.poll();
for (int[] dir : dirs){
int x = point[0] + dir[0];
int y = point[1] + dir[1];
if(x < 0 || y < 0 || x > row - 1 || y > col - 1 || grid[x][y] == 1)
continue;//越界或为岛屿时跳过循环
else if(grid[x][y] == 2)
return count;//桥搭建到了第一座岛则返回count
grid[x][y] = 1;//标记为第二座岛在这里搭过桥
queue.offer(new int[]{x, y});
}
}
count++;//扩张一步桥的长度+1
}
return count;
}
public void DFS(int[][] grid, int i, int j){
grid[i][j] = 2;//将第一座岛屿都标记为2
for (int[] dir : dirs){
int x = i + dir[0];
int y = j + dir[1];
if(x < 0 || y < 0 || x > row - 1 || y > col - 1 || grid[x][y] != 1)
continue;//越界或为已标记的岛屿时跳过循环
DFS(grid,x, y);//上下左右深搜
}
}
}
抱大腿
(/ω\)安和好久不见
我也要高考啦
疫情啦,现在二模都是线上在考,两个星期没去学校已经失忆了(
23333失忆了可太真实
唉疫情搞的,当时我在家也是学不下去,网课害人不浅(虽然现在感觉网课是真的香)
这五月还没开始呢就有页面了