笔试狂刷--Day12(模拟 + 链表的公共节点 + dp)

2024-05-04 15:04

本文主要是介绍笔试狂刷--Day12(模拟 + 链表的公共节点 + dp),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

大家好,我是LvZi,今天带来笔试狂刷--Day12(模拟 + 链表的公共节点 + dp)
在这里插入图片描述

一.删除公共字符(哈希)

题目链接:删除公共字符(哈希)
在这里插入图片描述

分析:

分别读取俩个字符串,将第二个字符串存储到set之中,再遍历第一个字符串,删除公共字符

代码:

import java.util.*;// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);char[] str1 = in.nextLine().toCharArray();char[] str2 = in.nextLine().toCharArray();Set<Character> set = new HashSet<>();for(char ch : str2) set.add(ch);StringBuffer ret = new StringBuffer();for(int i = 0; i < str1.length; i++)if(!set.contains(str1[i]))ret.append(str1[i] + "");System.out.print(ret.toString());}
}

二.两个链表的第⼀个公共结点

题目链接:两个链表的第⼀个公共结点
在这里插入图片描述

分析:

模拟即可

代码一:

暴力解法(最容易想到的方法,本质是计数)

  • 分别统计出两个链表的长度,求出差值,让两个链表的长度一致
  • 遍历两个链表,直到值相同
import java.util.*;
/*
public class ListNode {int val;ListNode next = null;ListNode(int val) {this.val = val;}
}*/
public class Solution {public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {if(pHead1 == null || pHead2 == null) return null;// 先统计两个链表的长度int len1 = 0, len2 = 0;ListNode c1 = pHead1, c2 = pHead2;while(c1 != null) {c1 = c1.next; len1++;}while(c2 != null) {c2 = c2.next; len2++;}c1 = pHead1; c2 = pHead2;int gap = Math.abs(len1 - len2);if(len1 > len2) {while(gap-- > 0) c1 = c1.next;}else {while(gap-- > 0) c2 = c2.next;}while(c1 != null && c1.val != c2.val) {c1 = c1.next; c2 = c2.next;}return c1;}
}

代码二:

利用等量关系:
创建两个指针cur1和cur2,同时往后走,如果走到节点的末尾(null),就让指针指向另一个节点的头结点,继续往后走,直到两个指针所处的节点相同

在这里插入图片描述


代码二:

import java.util.*;
/*
public class ListNode {int val;ListNode next = null;ListNode(int val) {this.val = val;}
}*/
public class Solution {public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {if(pHead1 == null || pHead2 == null) return null;ListNode cur1 = pHead1, cur2 = pHead2;while(cur1 != cur2) {cur1 = cur1 == null ? pHead2 : cur1.next;cur2 = cur2 == null ? pHead1 : cur2.next;}return cur1;}
}

三.mari和shiny(dp)

题目链接:mari和shiny(dp)
在这里插入图片描述

分析:

分别统计s,sh,shy的数量即可
使用cnt1来统计字符s的数量,使用cnt2统计字符sh的数量,使用ret统计shy的数量

代码:

import java.util.Scanner;// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);int n = in.nextInt();char[] str = in.next().toCharArray();long cnt1 = 0, cnt2 = 0, ret = 0;for(int i = 0; i < n; i++) {if(str[i] == 's') cnt1++;else if(str[i] == 'h') cnt2 += cnt1;else if(str[i] == 'y') ret += cnt2;}System.out.print(ret);}
}

总结:

  • 本题不要想复杂了,实际上只需要维护两个字符的数量即可,本质上是一个简单的动态规划的思想

这篇关于笔试狂刷--Day12(模拟 + 链表的公共节点 + dp)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/959480

相关文章

【前端学习】AntV G6-08 深入图形与图形分组、自定义节点、节点动画(下)

【课程链接】 AntV G6:深入图形与图形分组、自定义节点、节点动画(下)_哔哩哔哩_bilibili 本章十吾老师讲解了一个复杂的自定义节点中,应该怎样去计算和绘制图形,如何给一个图形制作不间断的动画,以及在鼠标事件之后产生动画。(有点难,需要好好理解) <!DOCTYPE html><html><head><meta charset="UTF-8"><title>06

hdu4826(三维DP)

这是一个百度之星的资格赛第四题 题目链接:http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1004&cid=500 题意:从左上角的点到右上角的点,每个点只能走一遍,走的方向有三个:向上,向下,向右,求最大值。 咋一看像搜索题,先暴搜,TLE,然后剪枝,还是TLE.然后我就改方法,用DP来做,这题和普通dp相比,多个个向上

hdu1011(背包树形DP)

没有完全理解这题, m个人,攻打一个map,map的入口是1,在攻打某个结点之前要先攻打其他一个结点 dp[i][j]表示m个人攻打以第i个结点为根节点的子树得到的最优解 状态转移dp[i][ j ] = max(dp[i][j], dp[i][k]+dp[t][j-k]),其中t是i结点的子节点 代码如下: #include<iostream>#include<algorithm

【C++】_list常用方法解析及模拟实现

相信自己的力量,只要对自己始终保持信心,尽自己最大努力去完成任何事,就算事情最终结果是失败了,努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一:什么是list? •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二:list常用接口 •🌰1.默认成员函数 🔥构造函数(⭐) 🔥析构函数 •🌰2.list对象

hdu4865(概率DP)

题意:已知前一天和今天的天气概率,某天的天气概率和叶子的潮湿程度的概率,n天叶子的湿度,求n天最有可能的天气情况。 思路:概率DP,dp[i][j]表示第i天天气为j的概率,状态转移如下:dp[i][j] = max(dp[i][j, dp[i-1][k]*table2[k][j]*table1[j][col] )  代码如下: #include <stdio.h>#include

csu1329(双向链表)

题意:给n个盒子,编号为1到n,四个操作:1、将x盒子移到y的左边;2、将x盒子移到y的右边;3、交换x和y盒子的位置;4、将所有的盒子反过来放。 思路分析:用双向链表解决。每个操作的时间复杂度为O(1),用数组来模拟链表,下面的代码是参考刘老师的标程写的。 代码如下: #include<iostream>#include<algorithm>#include<stdio.h>#

poj1330(LCA最近公共祖先)

题意:求最近公共祖先 思路:之前学习了树链剖分,然后我就用树链剖分的一小部分知识就可以解这个题目了,记录每个结点的fa和depth。然后查找时,每次将depth大的结点往上走直到x = y。 代码如下: #include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<cstring>

usaco 1.2 Transformations(模拟)

我的做法就是一个一个情况枚举出来 注意计算公式: ( 变换后的矩阵记为C) 顺时针旋转90°:C[i] [j]=A[n-j-1] [i] (旋转180°和270° 可以多转几个九十度来推) 对称:C[i] [n-j-1]=A[i] [j] 代码有点长 。。。 /*ID: who jayLANG: C++TASK: transform*/#include<

usaco 1.1 Broken Necklace(DP)

直接上代码 接触的第一道dp ps.大概的思路就是 先从左往右用一个数组在每个点记下蓝或黑的个数 再从右到左算一遍 最后取出最大的即可 核心语句在于: 如果 str[i] = 'r'  ,   rl[i]=rl[i-1]+1, bl[i]=0 如果 str[i] = 'b' ,  bl[i]=bl[i-1]+1, rl[i]=0 如果 str[i] = 'w',  bl[i]=b

day-51 合并零之间的节点

思路 直接遍历链表即可,遇到val=0跳过,val非零则加在一起,最后返回即可 解题过程 返回链表可以有头结点,方便插入,返回head.next Code /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}*