当前位置:网站首页>Problem solving-->Online OJ (19)

Problem solving-->Online OJ (19)

2022-08-10 14:54:00 Constantly improving Nan

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;
    }
}
原网站

版权声明
本文为[Constantly improving Nan]所创,转载请带上原文链接,感谢
https://yzsam.com/2022/222/202208101432332402.html