牛客网算法——名企高频面试题143题（10）

题目描述

给出一个升序排序的链表，删除链表中的所有重复出现的元素，只保留原链表中只出现一次的元素。 例如： 给出的链表为1→2→3→3→4→4→51 \to 2\to 3\to 3\to 4\to 4\to51→2→3→3→4→4→5, 返回1→2→51\to 2\to51→2→5. 给出的链表为1→1→1→2→31\to1 \to 1\to 2 \to 31→1→1→2→3, 返回2→32\to 32→3.

package 名企高频面试题143;

import org.junit.Test;

/**
 * @Classname 链表删除所有重复元素
 * @Description TODO
 * @Date 2020/12/18 10:03
 * @Created by xjl
 */
public class 链表删除所有重复元素 {
    public class ListNode {
        int val;
        ListNode next;

        public ListNode(int val) {
            this.val = val;
        }
    }

    /**
     * @description TODO 删除的是的链表的重复的元素
     * @param: head
     * @date: 2020/12/18 10:04
     * @return: ListNode
     * @author: xjl
     */
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null)
            return null;
        ListNode dumy = new ListNode(0);
        dumy.next = head;

        ListNode pre = dumy;
        ListNode curr = head;

        while (curr != null&&curr.next != null ) {
            ListNode future = curr.next;
            if (future.val != curr.val) {
                pre = pre.next;
                curr = curr.next;
            } else {
                while (future != null && future.val == curr.val) {
                    future = future.next;
                }
                pre.next = future;
                curr = future;
            }
        }
        return dumy.next;
    }

    public ListNode deleteDuplicates2(ListNode head) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;

        ListNode prev = dummy;
        ListNode curr = head;

        while (curr != null && curr.next != null) {
            if (curr.val == curr.next.val) {
                ListNode future = curr.next;
                while (future != null && future.val == curr.val) {
                    future = future.next;
                }
                prev.next = future;
                curr = future;
            } else {
                prev = prev.next;
                curr = curr.next;
            }
        }
        return dummy.next;
    }

    @Test
    public void test() {
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(1);
        ListNode node3 = new ListNode(1);
        ListNode node4 = new ListNode(1);
        ListNode node5 = new ListNode(1);
        ListNode node6 = new ListNode(4);
        ListNode node7 = new ListNode(5);
        ListNode node8 = new ListNode(6);
        node1.next = node2;
        node2.next = node3;
//        node3.next = node4;
//        node4.next = node5;
//        node5.next = node6;
//        node6.next = node7;
//        node7.next = node8;

        ListNode res = deleteDuplicates(node1);
        while (res != null) {
            System.out.print(res.val + " ");
            res = res.next;
        }
    }
}

题目描述

现在有一个只包含数字的字符串，将该字符串转化成IP地址的形式，返回所有可能的情况。

例如：

给出的字符串为"25525522135",

返回["255.255.22.135", "255.255.221.35"]. (顺序没有关系)

package 名企高频面试题143;

import java.util.ArrayList;
import java.util.List;

/**
 * @Classname 字符串转化为的IP地址
 * @Description TODO
 * @Date 2020/12/18 13:27
 * @Created by xjl
 */
public class 字符串转化为的IP地址 {
    ArrayList res = new ArrayList();

    public ArrayList restoreIpAddresses(String s) {
        ArrayList segment = new ArrayList();
        //开始搜索
        dfs(s, 0, segment);
        return res;
    }

    private void dfs(String s, int start, List segment) {
        if (start == s.length()) {
            if (segment.size() == 4) {
                StringBuilder sb = new StringBuilder();
                for (int i = 0; i < segment.size(); i++) {
                    sb.append(segment.get(i));
                    if (i != segment.size() - 1) sb.append('.');
                }
                res.add(sb.toString());
            } else {
                return;
            }
        } else {
            if (segment.size() >= 4) {
                return;
            }
            for (int i = start; i < s.length() && i < start + 3; i++) {
                String str = s.substring(start, i + 1);
                if (str.charAt(0) == '0' && str.length() > 1) break;
                int num = Integer.parseInt(str);
                if (num >= 0 && num