当前位置:网站首页>Problem solving-->Online OJ (19)
Problem solving-->Online OJ (19)
2022-08-10 14:54:00 【Constantly improving Nan】
解题-->在线OJ(十九)
1.单词长度的最大乘积
解题思路:
双层for循环,Checks whether two strings contain the same characters,如果不包含,Calculate the product of these two strings,同时,更新ret的值.
class Solution {
public static int maxProduct(String[] words) {
int ret=0;
for(int i=0;i<words.length;i++){
for(int j=i+1;j<words.length;j++){
//如果两个字符串不包含相同的字符
if(isNotContains(words[i],words[j])){
//Calculates the product of the lengths of two strings
int product=words[i].length() * words[j].length();
ret=Math.max(ret,product);
}
}
}
return ret;
}
//Check if two strings contain the same characters
public static boolean isNotContains(String s1,String s2){
HashSet set=new HashSet();
for(int i=0;i<s1.length();i++){
set.add(s1.charAt(i));
}
for(int i=0;i<s2.length();i++){
if(set.contains(s2.charAt(i))){
return false;
}
}
return true;
}
}
2.每日温度
class Solution {
public static int[] dailyTemperatures(int[] temperatures) {
int[] result=new int[temperatures.length];
for(int i=0;i<temperatures.length;i++){
int count=0;
for(int j=i+1;j<temperatures.length;j++){
if(temperatures[j]>temperatures[i]){
count++;
result[i]=count;
break;
}else{
count++;
}
}
}
result[result.length-1]=0;
return result;
}
}
3.最小时间差
class Solution {
public static int findMinDifference(List<String> timePoints) {
int[] temp=new int[timePoints.size()];
int num=0;
for(String s:timePoints){
temp[num]=(60*((s.charAt(0)-'0')*10+(s.charAt(1)-'0'))+((s.charAt(3)-'0')*10+(s.charAt(4))-'0'));
num++;
}
Arrays.sort(temp);
int min=24*60-temp[temp.length-1]+temp[0];
for(int i=0;i<temp.length-1;i++){
min=Math.min(min,temp[i+1]-temp[i]);
}
return min;
}
}
4.最长连续序列
class Solution {
public static int longestConsecutive(int[] nums) {
//如果数组长度是0,直接返回0
if(nums.length==0){
return 0;
}
//将数组进行排序
Arrays.sort(nums);
int result=1;
int count=1;
//for循环数组
for(int i=0;i<nums.length-1;i++){
//If the difference between the two numbers before and after is equal to 1,count++,If the difference between the two numbers is equal to 0,continue,否则,就把count重新赋值给1
if(Math.abs(nums[i+1]-nums[i])==1){
count++;
}else if(Math.abs(nums[i+1]-nums[i])==0){
continue;
}else{
count=1;
}
//result时时更新
result=Math.max(result,count);
}
return result;
}
}
5.0和1个数相同的子数组
解题思路:
class Solution {
public static int findMaxLength(int[] nums) {
int max=0;
HashMap<Integer,Integer> hashMap=new HashMap<>();
int sum=0;
//首先,给hashMap里面存入(0,-1)
hashMap.put(0,-1);
for(int i=0;i<nums.length;i++){
//如果nums[i]等于1,就赋值给1,否则,就赋值给-1
sum+=(nums[i]==1?1:-1);
//判断hashMap里面是否包含sum.如果包含,下标i-hashMap.get(sum)within the range of 0和1个数相同的子数组
if(hashMap.containsKey(sum)){
max=Math.max(max,i-hashMap.get(sum));
}else{
//如果hashMap当中不包含sum,hashMap里面直接put数据即可
hashMap.put(sum,i);
}
}
return max;
}
}
6.不含重复字符的最长子字符串
1.定义两个下标,iResponsible head,jresponsible for the tail
2.如果hashMap当中不包含s.charAt(j),那么就更新最大值,并且,往hashMap当中,store this value;
3.如果hashMap当中包含s.charAt(j),那么更新i的值,i=Math.max(i,hashMap.get(s.charAt(j))),从hashMapobtained from its.charAt(j),与i进行比较,取较大值.
4.更新完i下标之后,Then update the maximum summap当中s.charAt(j)的下标.
class Solution {
public static int lengthOfLongestSubstring(String s) {
if(s==""){
return 0;
}
int max=0;
HashMap<Character,Integer> hashMap=new HashMap<>();
int i=0;
int j=0;
for(;j<s.length();j++){
if(hashMap.containsKey(s.charAt(j))){
i=Math.max(hashMap.get(s.charAt(j)),i);
}
max=Math.max(max,j-i+1);
hashMap.put(s.charAt(j),j+1);
}
return max;
}
}
7.链表中的两数相加
解题思路:
1.先计算出两个链表的长度;
2.If both linked lists are of the same length1的话,进行求和,And judge whether the sum is greater than or equal to10,This determines whether the number of returned nodes is one or two;
3.If one of the linked lists is longer than 1Or the length of both linked lists is greater than1的话,Just flip the linked list,比如,将,7->2->4->3翻转成3->4->2->7;
4.Flip the sum of the linked list,Do the linked list again,Summation of two nodes,在求和的过程中,需要注意:Whether the sum of two nodes is greater than9,如果大于,The carry value needs to be assigned a value.
5.Flip the linked list after the summation,最后,返回head即可.
class Solution {
public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
//First record the length of the two linked lists
ListNode le=l1;
int length1=0;
while(le!=null){
length1++;
le=le.next;
}
ListNode le2=l2;
int length2=0;
while(le2!=null){
length2++;
le2=le2.next;
}
//If both linked lists are of length 1的话,And the sum of the two values is less than10的话,直接返回一个节点,The value is the sum of the two nodes
if(length1==1 && length2==1){
int temp=l1.val+l2.val;
//If the sum of the values of the two nodes is greater than or equal to10的话,One more node is needed,来保存进位值
if(temp>=10){
int t1=temp;
ListNode node=new ListNode(temp%10);
ListNode node2=new ListNode(t1/10);
node2.next=node;
node.next=null;
return node2;
}else{
return new ListNode(l1.val+l2.val);
}
}
ListNode head = new ListNode(-1);
ListNode move=head;
//只有链表长度大于1的时候,Just need to reverse the linked list
if(length1>1){
l1 = reverseList(l1);
}
if(length2>1){
l2=reverseList(l2);
}
//For the two linked lists after inversion,进行求和
int ret=0;
while(l1!=null && l2!=null){
int temp=0;
temp+=l1.val;
temp+=l2.val;
int count=temp;
ListNode node=new ListNode((ret+temp)%10);
move.next=node;
move=move.next;
ret=(ret+temp)/10;
l1=l1.next;
l2=l2.next;
}
//当链表1不为空,链表2 为空的时候
while (l1!=null){
int temp=0;
temp+=l1.val;
ListNode node=new ListNode((ret+temp)%10);
move.next=node;
move=move.next;
ret=(ret+temp)/10;
l1=l1.next;
}
//当链表1为空,链表2不为空的时候
while (l2!=null){
int temp=0;
temp+=l2.val;
ListNode node=new ListNode((ret+temp)%10);
move.next=node;
move=move.next;
ret=(ret+temp)/10;
l2=l2.next;
}
//When the carry value is not equal to0的时候,One more node needs to be created to hold this carry value
if(ret!=0){
ListNode node=new ListNode(ret);
move.next=node;
move=move.next;
}
move.next=null;
//Sum the sum over all nodes,Reverse the linked list again
head=reverseList(head.next);
return head;
}
//This method is an inversion of control linked list
public static ListNode reverseList(ListNode l1){
ListNode pre=l1;
ListNode node=l1.next;
pre.next=null;
while(node!=null && node.next!=null){
ListNode nodeNext=node.next;
node.next=pre;
pre=node;
node=nodeNext;
}
node.next=pre;
return node;
}
}
8.删除链表的倒数第n个节点
class Solution {
public static ListNode removeNthFromEnd(ListNode head, int n) {
ListNode temp=head;
int length=0;
//计算链表长度
while(temp!=null){
length++;
temp=temp.next;
}
//如果有5个节点,删除倒数第2个节点,It is equivalent to deleting the first number of positive numbers4个节点
int ret=length-n+1;
//如果链表长度大于等于1,To delete the first node,直接返回head.next即可
if(length>=1 && ret==1){
return head.next;
}
ListNode pre=head;
ListNode node=head.next;
//走到这一步,It proves that the deletion is not the first node,count就赋值于2
//定义三个变量,pre,node,nodeNext
//如果nodeNot the node to be deleted,pre.next=node
//如果node是待删除节点,pre.next=nodeNext
int count=2;
while(node!=null){
ListNode nodeNext=node.next;
//此时,node就是待删除节点
if(count==ret){
pre.next=nodeNext;
node=nodeNext;
count++;
continue;
}
//nodeNot the node to be deleted
pre.next=node;
pre=node;
node=nodeNext;
count++;
}
//返回头节点即可
return head;
}
}
9.重排链表
1.计算链表长度,链表长度<=2的,直接返回
2.找到链表的中间节点,将链表一分为二,Reverse the linked list in the second half.
3.定义一个新的节点,Add data to the new node in turn,规律是,Add a node for the first half,Add another node for the reversed second half
4.Then add the remaining nodes to newNode节点之后
class Solution {
public static void reorderList(ListNode head) {
int leng=0;
ListNode temp=head;
//计算链表的长度
while (temp!=null){
leng++;
temp=temp.next;
}
//如果链表长度<=2直接返回
if(leng==1||leng==2){
return;
}
//找到链表的中间节点
ListNode fast=head;
ListNode slow=head;
ListNode pslow=new ListNode(-1);
while(fast!=null && fast.next!=null){
pslow=slow;
slow=slow.next;
fast=fast.next.next;
}
ListNode newList1=head;
pslow.next=null;
//以slow为分界线,将链表分为两部分,The second half is reversed
ListNode newList2=reverseList(slow);
//定义一个新的节点,Used to synthesize two linked lists
ListNode newNode=new ListNode(-1);
//Add data to the back of the new linked list
while(newList1!=null && newList2!=null){
newNode.next=newList1;
newNode=newNode.next;
newList1=newList1.next;
newNode.next=newList2;
newNode=newNode.next;
newList2=newList2.next;
}
//If the first half of the linked list is not empty,Just add the rest
if(newList1!=null){
newNode.next=newList1;
}
//If the first half of the linked list is not empty,Just add the rest
if(newList2!=null){
newNode.next=newList2;
}
}
//反转链表
public static ListNode reverseList(ListNode head){
ListNode pre=head;
ListNode node=head.next;
pre.next=null;
while(node!=null){
ListNode nodeNext=node.next;
node.next=pre;
pre=node;
node=nodeNext;
}
return pre;
}
}
10.链表中环的入口节点
public class Solution {
public static ListNode detectCycle(ListNode head) {
ListNode slow=head;
ListNode fast=head;
//Find the meeting point first
while(fast!=null && fast.next!=null){
slow=slow.next;
fast=fast.next.next;
//After finding the encounter node,fast=head
//然后fast=fast.next;slow=slow.next
//当再次相遇的时候,此时,The encounter node is the entry node of the ring in the circular linked list
if(fast==slow){
fast=head;
while(fast!=slow){
fast=fast.next;
slow=slow.next;
}
return slow;
}
}
return null;
}
}
边栏推荐
- 王学岗—————————哔哩哔哩直播-手写哔哩哔哩硬编码录屏推流(硬编)(26节课)
- websocket实现实时变化图表内容
- 640. Solving Equations: Simple Simulation Problems
- 高薪程序员&面试题精讲系列135之你对分布式是怎么理解的?CAP理论你知道吗?
- How does vue clear the tab switching cache problem?
- How is the monthly salary table stored in the database?Ask for a design idea
- win2012安装Oraclerac失败
- 蓝帽杯半决赛火炬木wp
- 【数仓设计】企业数仓为什么要进行分层?(六大好处)
- 文件系统设计
猜你喜欢
[Gazebo Introductory Tutorial] Lecture 3 Static/Dynamic Programming Modeling of SDF Files
MySQL 原理与优化:Update 优化
Unfinished mathematics test paper ----- test paper generator (Qt includes source code)
Using data intelligence, Amazon cloud technology helps companies build endogenous brand growth
QOS功能介绍
MySQL - 数据库的存储引擎
Azure IoT 合作伙伴技术赋能工作坊:IoT Dev Hack
SWIG教程《一》
Analysys and the Alliance of Small and Medium Banks jointly released the Hainan Digital Economy Index, so stay tuned!
【有限元分析】异型密封圈计算泄漏量与参数化优化过程(带分析源文件)
随机推荐
leetcode 739. Daily Temperatures Daily Temperatures (Moderate)
2012年下半年 系统架构设计师 下午试卷 II
PCL 最小二乘拟合空间曲线
The a-modal in the antd component is set to a fixed height, and the content is scrolled and displayed
解读STEAM教育中的表现性评价
MySQL - 数据库的存储引擎
EVE模拟器的使用-带图超详细(学网络用)「建议收藏」
file system design
阿里五位MySQL封神大佬耗17个月总结出53章性能优化法则
兆骑科创创业赛事活动发布平台,创业赛事,项目路演
systemui状态栏添加新图标
PyTorch multi-machine multi-card training: DDP combat and skills
机器学习总结(一)
PAT甲级 1014 排队等候(队列大模拟+格式化时间)
每个月工资表在数据库如何存储?求一个设计思路
2011年下半年 系统架构设计师 下午试卷 II
websocket实现实时变化图表内容
无线网络、HTTP缓存、IPv6
Flask框架——基于Celery的后台任务
物资采购小程序开发制作功能介绍