每日刷题记录 (十三)

文章目录

第一题: 剑指 Offer II 015. 字符串中的所有变位词

LeetCode: 剑指 Offer II 015. 字符串中的所有变位词
描述:
给定两个字符串 s 和 p，找到 s 中所有 p 的 变位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

变位词 指字母相同，但排列不同的字符串。

解题思路:

1. 这里创建一个大小为 p.length() 的滑动窗口
2. 使用一个数组 pArr 记录 p字符串中, 每个字符出现的次数. sArr 记录当前窗口中字符串中每个字符出现的次数.
3. 遍历字符串 s 始终保持滑动窗口的大小, 如果当前的 sArr 和 pArr中内容一致. 就返回当前遍历到的下标(左窗口下标).

代码实现:

classSolution{publicList<Integer>findAnagrams(String s,String p){List<Integer> res =newArrayList<>();int pLen = p.length();int sLen = s.length();if(pLen > sLen)return res;int[] pArr =newint[26];int[] sArr =newint[26];for(int i =0; i < pLen; i++){
            pArr[p.charAt(i)-'a']++;
            sArr[s.charAt(i)-'a']++;}if(Arrays.equals(pArr,sArr)){
            res.add(0);}for(int i =0; i < sLen-pLen; i++){
            sArr[s.charAt(i)-'a']--;
            sArr[s.charAt(i+pLen)-'a']++;if(Arrays.equals(pArr,sArr)){
                res.add(i+1);}}return res;}}

第二题: 剑指 Offer II 025. 链表中的两数相加

LeetCode: 剑指 Offer II 025. 链表中的两数相加

描述:
给定两个 非空链表 l1和 l2 来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。

可以假设除了数字 0 之外，这两个数字都不会以零开头。

解题思路:

1. 这里使用两个栈, 分别将两个链表的元素入栈
2. 将两个栈元素出栈, 相加, 看是否需要进位, 或者上一次是否需要进位
3. 注意当出栈完之后, 还需要判断是否需要进位.

代码实现:

classSolution{publicListNodeaddTwoNumbers(ListNode l1,ListNode l2){Stack<Integer>A=newStack<>();Stack<Integer>B=newStack<>();while(l1 !=null){A.push(l1.val);
            l1=l1.next;}while(l2 !=null){B.push(l2.val);
            l2=l2.next;}ListNode tmp =null;int ret =0;while(!A.isEmpty()||!B.isEmpty()|| ret !=0){int a =A.isEmpty()?0:A.pop();int b =B.isEmpty()?0:B.pop();int sum = a + b + ret;
            ret =(a + b + ret)/10;
            sum %=10;ListNode node =newListNode(sum);
            node.next = tmp;
            tmp = node;}return tmp;}}

第三题: 剑指 Offer II 026. 重排链表

LeetCode: 剑指 Offer II 026. 重排链表

描述:
给定一个单链表

L

的头节点

head

，单链表

L

表示为：

L0 → L1 → … → Ln-1 → Ln 

请将其重新排列后变为：

L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …

不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

解题思路:

1. 这里首先找到中间节点. - 快慢指针的方式就可以找到中间节点
2. 让中间节点到尾节点部分进行反转. - 三个引用遍历进行.
3. 然后对前半部分 和 后半部分进行组织

代码实现:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */classSolution{publicvoidreorderList(ListNode head){if(head ==null)return;ListNode mid =getMid(head);ListNode midNext = mid.next;
        mid.next =null;ListNode ret = head;ListNode tmp =reverse(midNext);while(ret !=null&& tmp !=null){ListNode retNext = ret.next;ListNode tmpNext = tmp.next;
            ret.next = tmp;
            tmp.next = retNext;

            ret = retNext;
            tmp = tmpNext;}}publicListNodegetMid(ListNode head){ListNode fast = head;ListNode slow = head;while(fast.next !=null&& fast.next.next !=null){
            slow = slow.next;
            fast = fast.next.next;}return slow;}publicListNodereverse(ListNode head){ListNode pre =null;ListNode cur = head;while(cur !=null){ListNode curNext = cur.next;
            cur.next = pre;
            pre = cur;
            cur = curNext;}return pre;}}

第四题: 剑指 Offer II 030. 插入、删除和随机访问都是 O(1) 的容器

LeetCode: 剑指 Offer II 030. 插入、删除和随机访问都是 O(1) 的容器

描述:
设计一个支持在平均 时间复杂度 O(1) 下，执行以下操作的数据结构：

• insert(val)：当元素 val 不存在时返回 true ，并向集合中插入该项，否则返回 false 。
• remove(val)：当元素 val 存在时返回 true ，并从集合中移除该项，否则返回 false 。
• getRandom：随机返回现有集合中的一项。每个元素应该有 相同的概率 被返回。

解题思路:

1. 这里使用一个 哈希表来进行记录, key 为当前插入的值, value为插入对应的List的下标
2. 这里用一个list进行插入.
3. 在插入的时候, 判断哈希表中是否有这个val了, 如果有直接返回false, 如果没有就将val插入list中, 并将val以及对应的list中的下标插入map中.返回true;
4. 在删除的时候, 判断哈希表中是否有这个val, 如果没有直接返回false, 如果有, 获取到这个val的下标, 将list中最后一个元素和当前下标进行交换, 然后删除list最后一个元素, 删除哈希表中对应的key值,返回true;
5. 随机访问, 创建一个random,大小为当前list的大小的随机数, 随机得到这个范围内的一个数,并返回.

代码实现:

classRandomizedSet{privateMap<Integer,Integer> map;privateList<Integer> list;privateRandom random;/** Initialize your data structure here. */publicRandomizedSet(){
        map =newHashMap();
        list =newArrayList<>();
        random =newRandom();}/** Inserts a value to the set. Returns true if the set did not already contain the specified element. */publicbooleaninsert(int val){if(map.containsKey(val)){returnfalse;}
        list.add(val);
        map.put(val,list.size()-1);returntrue;}/** Removes a value from the set. Returns true if the set contained the specified element. */publicbooleanremove(int val){if(!map.containsKey(val)){returnfalse;}int index = map.get(val);int last = list.get(list.size()-1);
        list.set(index,last);
        map.put(last,index);
        list.remove(list.size()-1);
        map.remove(val);returntrue;}/** Get a random element from the set. */publicintgetRandom(){return list.get(random.nextInt(list.size()));}}

第五题: 剑指 Offer II 032. 有效的变位词

LeetCode: 剑指 Offer II 032. 有效的变位词

描述:
给定两个字符串 s 和 t ，编写一个函数来判断它们是不是一组变位词（字母异位词）。

注意：若 s 和 t 中每个字符出现的次数都相同且字符顺序不完全相同，则称 s 和 t 互为变位词（字母异位词）。

解题思路:

1. 首先对 字符串 s 和 字符串 t 进行比较, 看是否相同, 如果相同直接返回false;
2. 使用数组来记录 s中字符出现的次数, 只要出现了, 就++
3. 再遍历字符串 t , 如果字符出现了, 就--
4. 遍历当前的数组, 是否有元素不为0, 不为0就表示不满足题意, 返回false
5. 遍历结束 返回 true

代码实现:

classSolution{publicbooleanisAnagram(String s,String t){if(s.equals(t))returnfalse;int[] arr =newint[26];for(char ch : s.toCharArray()){
            arr[ch-'a']++;}for(char ch : t.toCharArray()){
            arr[ch-'a']--;}for(int val : arr){if(val !=0)returnfalse;}returntrue;}}

第六题: 剑指 Offer II 033. 变位词组

LeetCode: 剑指 Offer II 033. 变位词组

描述:
给定一个字符串数组 strs ，将 变位词 组合在一起。 可以按任意顺序返回结果列表。

注意: 若两个字符串中每个字符出现的次数都相同，则称它们互为变位词。

解题思路:

1. 遍历strs, 将每一个元素变成char数组进行排序
2. 然后将char数组变成一个字符串, 利用哈希表, 判断当前字符串是否存在于哈希表 - 如果不存在, 就创建一个list, 将str放入进去, 然后存入map中- 如果存在, 直接得到当前字符串对应的list, 然后将str放进去.
3. 遍历结束, 将map变成ArrayList返回.

代码实现:

classSolution{publicList<List<String>>groupAnagrams(String[] strs){Map<String,List<String>> map =newHashMap<>();for(String str : strs){char[] ch = str.toCharArray();Arrays.sort(ch);String s =newString(ch);if(!map.containsKey(s)){List<String> ret =newArrayList<>();
                ret.add(str);
                map.put(s,ret);}else{
                map.get(s).add(str);}}returnnewArrayList(map.values());}}