牛客网刷题

本是古典何须时尚 2023-10-10 15:13 15阅读 0赞

![ced485cbb11e458d81a746890b32cf3f.gif][]

> 作者：敲代码の流川枫
> 
> 博客主页：[流川枫的博客][Link 1]
> 
> 专栏：[和我一起学java][java]
> 
> 语录：Stay hungry stay foolish
> 
> 工欲善其事必先利其器，给大家介绍一款超牛的斩获大厂offer利器——牛客网
> 
> [点击注册和我一起刷题][Link 2]
> 
> ![c39e8efb4e414d24acdd03e5a62d16e5.png][]

**文章目录**

1.字符串中的第一个唯一字符

2. 只出现一次的数字

3.复制带随机指针的链表

--------------------

## 1.字符串中的第一个唯一字符 ##

> 给定一个字符串 `s` ，找到 *它的第一个不重复的字符，并返回它的索引* 。如果不存在，则返回 `-1` 。
> 
> ![ecb38048183b4623b818d610b7488d1b.png][]
> 
> ![1623a13b9e384cea81227eb41ca96e3d.png][]

在第一次遍历时，我们使用计数数组统计出字符串中每个字符出现的次数。在第二次遍历时，我们只要遍历到了一个只出现一次的字符，那么就返回它的索引，否则在遍历结束后返回 −1

class Solution {
        public int firstUniqChar(String s) {
            int[] arr = new int[26];
            for(int i = 0;i<s.length();i++){
                char ch = s.charAt(i);
                arr[ch-'a']++;
            }
            for(int i = 0;i<s.length();i++){
                char ch1 = s.charAt(i);
                if(arr[ch1-'a'] == 1){
                    return i;
                }
            }
            return -1;
    
        }
    }

## 2. 只出现一次的数字 ##

> 给定一个**非空**整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
> 
> 说明：
> 
> 你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
> 
> ![9c1ba89142bd4170828155678c6be70f.png][]

解法一：异或

异或解法：异或运算满足交换律，a^b^a=a^a^b=b,因此ans相当于nums\[0\]^nums\[1\]^nums\[2\]^nums\[3\]^nums\[4\]..... 然后再根据交换律把相等的合并到一块儿进行异或（结果为0），然后再与只出现过一次的元素进行异或，这样最后的结果就是，只出现过一次的元素（0^任意值=任意值）

class Solution {
        public int singleNumber(int[] nums) {
           int ret = nums[0];
           if(nums.length > 1){
               for(int i = 1;i<nums.length;i++){
                   ret = ret ^ nums[i];
               }
           }
           return ret;
        }
    }

解法二：HashSet

遍历数组，如果set不包含这个值，就添加，如果包含就删除，最后没被删除的就是只出现一次的数字

class Solution {
        public int singleNumber(int[] nums) {
            HashSet<Integer> set = new HashSet<>();
            for(int i =0 ;i< nums.length;i++){
                if(!set.contains(nums[i])){
                    set.add(nums[i]);
                }
                else{
                    set.remove(nums[i]);
                }
            }
            for(int i =0;i<nums.length;i++){
                if(set.contains(nums[i])){
                    return nums[i];
                }
            }
            return -1;
        }
    }

## 3.复制带随机指针的链表 ##

> 给你一个长度为 `n` 的链表，每个节点包含一个额外增加的随机指针 `random` ，该指针可以指向链表中的任何节点或空节点。
> 
> ![5c67f8e243d149cb8d5909e6848464eb.png][]

我们用哈希表来解决这个问题  
首先创建一个哈希表，再遍历原链表，遍历的同时再不断创建新节点  
我们将原节点作为**key**，新节点作为**value**放入哈希表中

![334fbb5321274e8c98dd9a11464694a0.png][]

第二步我们再遍历原链表，这次我们要将新链表的next和random指针给设置上

![bd2d1fe477b8474ebe6ef6e810e5ea3e.png][]

我们可以发现，原节点和新节点是一一对应的关系，所以

> map.get(原节点)，得到的就是对应的新节点  
> map.get(原节点.next)，得到的就是对应的新节点.next  
> map.get(原节点.random)，得到的就是对应的新节点.random

所以，我们只需要再次遍历原链表，然后设置：  
新节点.next -> map.get(原节点.next)  
新节点.random -> map.get(原节点.random)  
这样新链表的next和random都被串联起来了  
最后，我们然后map.get(head)，也就是对应的新链表的头节点，就可以解决此问题

代码

class Solution {
        public Node copyRandomList(Node head) {
            if(head==null) {
                return null;
            }
            HashMap<Node,Node> map = new HashMap<>();
            Node cur = head;
            while(cur != null){
                Node node = new Node(cur.val);
                map.put(cur,node);
                cur = cur.next;
            }
            cur = head;
            while(cur != null){
                map.get(cur).next = map.get(cur.next);
                map.get(cur).random = map.get(cur.random);
                cur = cur.next;
            }
            return map.get(head);
        }
    }

[ced485cbb11e458d81a746890b32cf3f.gif]: https://img-blog.csdnimg.cn/ced485cbb11e458d81a746890b32cf3f.gif
[Link 1]: https://blog.csdn.net/chenchenchencl?spm=1011.2421.3001.5343
[java]: https://blog.csdn.net/chenchenchencl/category_11932758.html
[Link 2]: https://www.nowcoder.com/link/pc_csdncpt_qdmdlcf_c
[c39e8efb4e414d24acdd03e5a62d16e5.png]: https://img-blog.csdnimg.cn/c39e8efb4e414d24acdd03e5a62d16e5.png
[ecb38048183b4623b818d610b7488d1b.png]: https://img-blog.csdnimg.cn/ecb38048183b4623b818d610b7488d1b.png
[1623a13b9e384cea81227eb41ca96e3d.png]: https://img-blog.csdnimg.cn/1623a13b9e384cea81227eb41ca96e3d.png
[9c1ba89142bd4170828155678c6be70f.png]: https://img-blog.csdnimg.cn/9c1ba89142bd4170828155678c6be70f.png
[5c67f8e243d149cb8d5909e6848464eb.png]: https://img-blog.csdnimg.cn/5c67f8e243d149cb8d5909e6848464eb.png
[334fbb5321274e8c98dd9a11464694a0.png]: https://img-blog.csdnimg.cn/334fbb5321274e8c98dd9a11464694a0.png
[bd2d1fe477b8474ebe6ef6e810e5ea3e.png]: https://img-blog.csdnimg.cn/bd2d1fe477b8474ebe6ef6e810e5ea3e.png