当前位置:网站首页>力扣+牛客--刷题记录
力扣+牛客--刷题记录
2022-08-10 15:13:00 【即将秃头的菜鸟】
活动地址:CSDN21天学习挑战赛
一、字符串中的第一个唯一字符
第一种方法
根据题意是返回字符的索引,所以我没可以把字符串放到数组中,又因为一共有26个字母,所以我没创建一个容量为26的数组把字符串放进去,利用哈希的思想来统计数据,最后看第一个字母数量为1的,返回就行。
public int firstUniqChar(String s) {
int[] arr = new int[26];
char[] chars = s.toCharArray();
//统计
for (int i = chars.length - 1; i >= 0; i--) {
arr[chars[i] - 'a'] = arr[chars[i] - 'a'] + 1;
}
//找出第一次出现的字母
for (int i = 0; i < chars.length; i++) {
if (arr[chars[i] - 'a'] == 1) {
return i;
}
}
return -1;
}
第二种方法
双层循环,一个一个检验。遍历一圈后如果没有和当前待检验的字符相同且下标不同的字符,则输出当前字符下标,否则,继续检验下一个字符,全部检验完后未发现符合条件字符,则输出-1。然后通过continue跳出内层循环,直接开启下一个外层循环。
public int firstUniqChar(String s) {
char[] arr = s.toCharArray();
int i = 0 , len = arr.length;
label:
while(i < len){
for(int j=0; j<len; ++j){
if(arr[i]==arr[j] && i != j){
++i; continue label;
}
}
return i;
}
return -1;
}
第三种方法
利用哈希的思想,第一次遍历的时候记录每个字符出现的次数,然后再第二次遍历的时候,只要他对应的value值是一,那么就返回。
public int firstUniqChar(String s) {
Map<Character, Integer> map = new HashMap<>();
for (int i = 0; i < s.length(); ++i) {
char ch = s.charAt(i);
map.put(ch, map.getOrDefault(ch, 0) + 1);
}
for (int i = 0; i < s.length(); ++i) {
if (map.get(s.charAt(i)) == 1) {
return i;
}
}
return -1;
}
二、实现strStr()
思路
我这里的想法很粗暴,就是让字符串 needle 与字符串 haystack 的所有长度为 m 的子串都匹配一次,匹配失败就break,进行下一次匹配。都匹配就返回-1。
public int strStr(String haystack, String needle) {
int haylen = haystack.length();
int needlen = needle.length();
for (int i = 0; i + haylen <= needlen; i++) {
boolean flag = true;
for (int j = 0; j < haylen; j++) {
if (haystack.charAt(i + j) != needle.charAt(j)) {
flag = false;
break;
}
}
if (flag) {
return i;
}
}
return -1;
}
三、存在重复元素
第一种方法
直接对数组排序,然后判断相邻元素是否相等。
public boolean containsDuplicate(int[] nums) {
Arrays.sort(nums);
for (int i = 0; i < nums.length - 1; i++) {
if (nums[i] == nums[i+1]) {
return true;
}
}
return false;
}
第二种方法
利用哈希的思想,因为set里面不允许出现重复的元素,所以直接遍历数组,看数组元素是否以及再set集合中。
public boolean containsDuplicate(int[] nums) {
Set<Integer> set = new HashSet<>();
for (int x : nums) {
if (!set.add(x)) {
return true;
}
}
return false;
}
四、存在重复元素Ⅱ
思路
这个题和上面那个题没什么不同,也是用哈希的思想,还是利用set,因为一个哈希集合里面最多存在k个元素,如果有重复出现的值,那么就说明再k的距离范围内,存在重复的元素。
public boolean containsNearbyDuplicate(int[] nums, int k) {
HashSet<Integer> set = new HashSet<>();
for(int i = 0; i < nums.length; i++) {
if(set.contains(nums[i])) {
return true;
}
set.add(nums[i]);
if(set.size() > k) {
set.remove(nums[i - k]);
}
}
return false;
}
五、链表的中间节点
思路
快慢指针,用两个指针 slow与 fast
一起遍历链表。slow
一次走一步,fast
一次走两步。那么当 fast
到达链表的末尾时,slow
必然位于中间。
public ListNode middleNode(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
边栏推荐
- Introduction to program debugging and its use
- Asterisk SIP media path
- Cesium Quick Start 4-Polylines primitive usage explanation
- Yi Gene|In-depth review: epigenetic regulation of m6A RNA methylation in brain development and disease
- Based on Azuki Series: NFT Valuation Analysis Framework "DRIC"
- Programmer = overtime??- Master the time to master the life
- Zhaoqi Technology Innovation High-level Talent Entrepreneurship Competition Platform
- Go Context基本使用
- FP6378AS5CTR SOT - 23-5 effective 1 mhz2a synchronous buck regulator
- "NIO Cup" 2022 Nioke Summer Multi-School Training Camp 7
猜你喜欢
Meaning and names of 12 nautical miles, 24 nautical miles and 200 nautical miles
SWIG tutorial "two"
Understanding_Data_Types_in_Go
SWIG教程《一》
[Semantic Segmentation] DeepLab Series
MySQL Principle and Optimization: Update Optimization
持续集成实战 —— Jenkins自动化测试环境搭建
Rich Dad Poor Dad Reading Notes
Scala collections
使用 ABAP 正则表达式解析 uuid 的值
随机推荐
Redis -- Nosql
网络初识(二)
Please check the preparation guide for the 2022 Huawei Developer Competition
fatal error C1083 无法打开包括文件'io.h' No such file
scala集合
NFT digital collection development issue - digital collection platform
Boss raises salary!Look at my WPF Loading!!!
易基因|深度综述:m6A RNA甲基化在大脑发育和疾病中的表观转录调控作用
使用 ABAP 正则表达式解析 uuid 的值
Yi Gene|In-depth review: epigenetic regulation of m6A RNA methylation in brain development and disease
基于 Azuki 系列:NFT估值分析框架“DRIC”
紫金示例
一个 ABAP 工具,能打印系统里某个用户对 BSP 应用的浏览历史记录
Detailed understanding of anonymous functions and all built-in functions (Part 2)
Community News——Congratulations to Dolphin Scheduling China User Group for 9 new "Community Administrators"
metaForce佛萨奇2.0系统开发功能逻辑介绍
redis 源码源文件说明
LeetCode_2598_剑指Offer Ⅱ 091.粉刷房子
640. Solving Equations: Simple Simulation Problems
丁香园