实习+秋招刷题016-018（牛客刷题）剑指offer

016替换空格
题目描述

请实现一个函数，将一个字符串s中的每个空格替换成“%20”。
例如，当字符串为We Are Happy.则经过替换之后的字符串
为We%20Are%20Happy。

关键解题思路
【知识点巩固】
替换或者修改字符串中任意位置的内容
方法1：【只能将String中某个字符替换为另一个字符】
使用String类的replace方法：

String str = "hello world";
String newStr = str.replace('o', 'e');
System.out.println(newStr);

方法2：【可替换为字符串】
String转化为char，然后再将修改完的char转化为String

char[] chars = str.toCharArray(); // 将整个String字符串转化为char类型的数组
String s1 = String.valueOf(chars1);//将字符数组转化为String字符串

方法3：【可替换为字符串】
将String改为StringBuilder

StringBuilder sb = new StringBuilder(str);//String转为StringBuilder
//使用StringBuilder的append方法添加内容
sb.toString();//StringBuilder转换为字符串

总结：方法2和方法3可以分别扩充char数组或者StringBuilder容量来将String某个位置字符替换成字符串。
Solution

import java.util.*;
public class Solution {
   
    /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param s string字符串 * @return string字符串 */
    public String replaceSpace (String s) {
   
        // write code here
        StringBuilder sb = new StringBuilder();
        for(int i=0;i <s.length(); i++){
   
            if(s.charAt(i)== ' '){
   
                sb.append("%20");
            }
            else{
   
                sb.append(s.charAt(i));
            }
        }
        return sb.toString();
    }
}

017判断给定的链表中是否有环
题目描述

判断给定的链表中是否有环，如果有环则返回true，否则返回false。

关键解题思路
HashSet：唯一但无序
使用HashSet的contains方法来判断节点是否已经存在，用add方法来添加结点。
Solution

import java.util.*;
/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */
public class Solution {
   
    public boolean hasCycle(ListNode head) {
   
        HashSet<ListNode> hset = new  HashSet<>();
        ListNode res = head;
        while(res!=null){
   
            // boolean ans = hset.add(res.val);
            // System.out.println(!hset.add(res.val));
            if(hset.contains(res)){
   
                // System.out.print(res);
                return true;
            }
            else{
   
                hset.add(res);
            }
            res = res.next;
        }
        return false;
    }
}

018链表中环的入口结点
题目描述

给一个长度为n链表，若其中包含环，请找出该链表的环的入口结点，否则，返回null。

关键解题思路
HashSet：唯一但无序
使用HashSet的contains方法来判断节点是否已经存在，如果已存在，返回该节点。用add方法来添加结点。

Solution

import java.util.*;
/* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } } */
public class Solution {
   

    public ListNode EntryNodeOfLoop(ListNode pHead) {
   
        HashSet<ListNode> hset = new HashSet<>();
        ListNode node = pHead;
        while(node!=null){
   
            if(hset.contains(node)){
   
                return node;
            }
            else{
   
                hset.add(node);
            }

            node = node.next;
        }
        
        return null;

    }
}