笔试狂刷--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);
    }
}

总结:

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