当前位置:网站首页>每日刷题记录 (十三)
每日刷题记录 (十三)
2022-07-05 00:41:00 【独一无二的哈密瓜】
文章目录
第一题: 剑指 Offer II 015. 字符串中的所有变位词
LeetCode: 剑指 Offer II 015. 字符串中的所有变位词
描述:
给定两个字符串 s 和 p,找到 s 中所有 p 的 变位词 的子串,返回这些子串的起始索引。不考虑答案输出的顺序。
变位词 指字母相同,但排列不同的字符串。
解题思路:
- 这里创建一个大小为
p.length()
的滑动窗口- 使用一个数组
pArr
记录 p字符串中, 每个字符出现的次数.sArr
记录当前窗口中字符串中每个字符出现的次数.- 遍历字符串
s
始终保持滑动窗口的大小, 如果当前的sArr
和pArr
中内容一致. 就返回当前遍历到的下标(左窗口下标).
代码实现:
class Solution {
public List<Integer> findAnagrams(String s, String p) {
List<Integer> res = new ArrayList<>();
int pLen = p.length();
int sLen = s.length();
if(pLen > sLen) return res;
int[] pArr = new int[26];
int[] sArr = new int[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 之外,这两个数字都不会以零开头。
解题思路:
- 这里使用两个栈, 分别将两个链表的元素入栈
- 将两个栈元素出栈, 相加, 看是否需要进位, 或者上一次是否需要进位
- 注意当出栈完之后, 还需要判断是否需要进位.
代码实现:
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
Stack<Integer> A = new Stack<>();
Stack<Integer> B = new Stack<>();
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 = new ListNode(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 → …
不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。
解题思路:
- 这里首先找到中间节点.
- 快慢指针的方式就可以找到中间节点
- 让中间节点到尾节点部分进行反转.
- 三个引用遍历进行.
- 然后对前半部分 和 后半部分进行组织
代码实现:
/** * 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; } * } */
class Solution {
public void reorderList(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;
}
}
public ListNode getMid(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;
}
public ListNode reverse(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
:随机返回现有集合中的一项。每个元素应该有 相同的概率 被返回。
解题思路:
- 这里使用一个 哈希表来进行记录, key 为当前插入的值, value为插入对应的List的下标
- 这里用一个list进行插入.
- 在插入的时候, 判断哈希表中是否有这个val了, 如果有直接返回false, 如果没有就将val插入list中, 并将val以及对应的list中的下标插入map中.返回true;
- 在删除的时候, 判断哈希表中是否有这个val, 如果没有直接返回false, 如果有, 获取到这个val的下标, 将list中最后一个元素和当前下标进行交换, 然后删除list最后一个元素, 删除哈希表中对应的key值,返回true;
- 随机访问, 创建一个random,大小为当前list的大小的随机数, 随机得到这个范围内的一个数,并返回.
代码实现:
class RandomizedSet {
private Map<Integer,Integer> map;
private List<Integer> list;
private Random random;
/** Initialize your data structure here. */
public RandomizedSet() {
map = new HashMap();
list = new ArrayList<>();
random = new Random();
}
/** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
public boolean insert(int val) {
if(map.containsKey(val)){
return false;
}
list.add(val);
map.put(val,list.size()-1);
return true;
}
/** Removes a value from the set. Returns true if the set contained the specified element. */
public boolean remove(int val) {
if(!map.containsKey(val)){
return false;
}
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);
return true;
}
/** Get a random element from the set. */
public int getRandom() {
return list.get(random.nextInt(list.size()));
}
}
第五题: 剑指 Offer II 032. 有效的变位词
LeetCode: 剑指 Offer II 032. 有效的变位词
描述:
给定两个字符串 s 和 t ,编写一个函数来判断它们是不是一组变位词(字母异位词)。
注意:若 s 和 t 中每个字符出现的次数都相同且字符顺序不完全相同,则称 s 和 t 互为变位词(字母异位词)。
解题思路:
- 首先对 字符串
s
和 字符串t
进行比较, 看是否相同, 如果相同直接返回false;- 使用数组来记录
s
中字符出现的次数, 只要出现了, 就++
- 再遍历字符串
t
, 如果字符出现了, 就--
- 遍历当前的数组, 是否有元素不为0, 不为0就表示不满足题意, 返回
false
- 遍历结束 返回
true
代码实现:
class Solution {
public boolean isAnagram(String s, String t) {
if(s.equals(t)) return false;
int[] arr = new int[26];
for(char ch : s.toCharArray()) {
arr[ch-'a']++;
}
for(char ch : t.toCharArray()) {
arr[ch-'a']--;
}
for(int val : arr) {
if(val != 0) return false;
}
return true;
}
}
第六题: 剑指 Offer II 033. 变位词组
LeetCode: 剑指 Offer II 033. 变位词组
描述:
给定一个字符串数组 strs ,将 变位词 组合在一起。 可以按任意顺序返回结果列表。
注意: 若两个字符串中每个字符出现的次数都相同,则称它们互为变位词。
解题思路:
- 遍历strs, 将每一个元素变成char数组进行排序
- 然后将char数组变成一个字符串, 利用哈希表, 判断当前字符串是否存在于哈希表
- 如果不存在, 就创建一个list, 将str放入进去, 然后存入map中
- 如果存在, 直接得到当前字符串对应的list, 然后将str放进去.
- 遍历结束, 将map变成ArrayList返回.
代码实现:
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
Map<String,List<String>> map = new HashMap<>();
for(String str : strs) {
char[] ch = str.toCharArray();
Arrays.sort(ch);
String s = new String(ch);
if(!map.containsKey(s)) {
List<String> ret = new ArrayList<>();
ret.add(str);
map.put(s,ret);
}else{
map.get(s).add(str);
}
}
return new ArrayList(map.values());
}
}
边栏推荐
- uniapp微信小程序拿来即用的瀑布流布局demo2(方法二)(复制粘贴即可使用,无需做其他处理)
- NPM install error forced installation
- URLs and URIs
- 程序员SQL数据脚本编码能力弱,BI做不出来怎么办?
- Learn C language from scratch day 024
- Fs8b711s14 electric wine bottle opener MCU IC scheme development special integrated IC
- 【selenium自动化】常用注解
- 有哪些收益稳定的理财产品,这两个都不错
- Reasons and solutions of redis cache penetration and avalanche
- pycharm专业版下载安装教程
猜你喜欢
4. Scala writes HelloWorld in idea, in-depth analysis of accompanying objects, and association of source packages
基本放大电路的学习
Learn C language from scratch day 024
ORB(Oriented FAST and Rotated BRIEF)
leetcode494,474
SAP UI5 应用开发教程之一百零六 - 如何提高 SAP UI5 应用路由 url 的可读性试读版
Detailed explanation of openharmony resource management
【路径规划】RRT增加动力模型进行轨迹规划
Reasons and solutions of redis cache penetration and avalanche
巩固表达式C# 案例简单变量运算
随机推荐
How many triangles are there in the golden K-line diagram?
Which financial products with stable income are good
Daily practice (18): stack containing min function
Acwing164. Accessibility Statistics (topological sorting +bitset)
4. Scala writes HelloWorld in idea, in-depth analysis of accompanying objects, and association of source packages
Get to know ROS for the first time
The most complete regular practical guide of the whole network. You're welcome to take it away
abc 258 G - Triangle(bitset)
Actual combat simulation │ JWT login authentication
SAP UI5 应用开发教程之一百零六 - 如何提高 SAP UI5 应用路由 url 的可读性试读版
GDB常用命令
P4281 [ahoi2008] emergency assembly / gathering (LCA)
leetcode494,474
打新债开户注册安全吗?有没有风险的?靠谱吗?
创新引领方向 华为智慧生活全场景新品齐发
Deux nombres se remplacent
MongoDB系列之学习笔记教程汇总
P4281 [AHOI2008]紧急集合 / 聚会(LCA)
Huawei employs millions of data governance experts! The 100 billion market behind it deserves attention
Learning of basic amplification circuit