力扣(LeetCode)剑指offer刷题笔记(java),持续更新!!!

发布时间:2021-10-14 15:04:32



文章目录
3、数组中重复的数字4、二维数组中的查找5、替换空格6、从尾到头打印链表



3、数组中重复的数字

题目描述


找出数组中重复的数字。


在一个长度为 n 的数组 nums 里的所有数字都在 0~n-1 的范围内。数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。


示例


输入:


[2, 3, 1, 0, 2, 5, 3]

输出:


2或3

思路分析


思路一:题目说要寻找一个重复的元素,因此可以考虑使用HashSet来解决该问题。集合中不能存在重复的元素,将数组中每个元素都添加到Set中,如果添加失败,则代表该元素是重复元素。使用这种方法相当于以空间换时间,时间复杂度会最小


思路二:原地交换法,题目隐藏了条件就是所有数字都在 0~n-1 的范围内,因此我们可以考虑使用原地交换的方法。遍历数组,如果数组索引等于对应的元素,则跳过,否则;则进行交换,即把数值为n的元素放在数组的第n个索引,当发现第n个索引已经有相同的元素时,则返回重复的元素。


代码


思路一:


class Solution {
public int findRepeatNumber(int[] nums) {
Set set = new HashSet<>();
int result = -1;

for(int num:nums){
if(!set.add(num)){
result=num;
}
}
return result;


}
}

思路二:


class Solution {
public int findRepeatNumber(int[] nums) {

for(int i=0; i
if(i == nums[i]){
continue;
}else{
if(nums[i] == nums[nums[i]]) return nums[i];
int temp = nums[i];
nums[i]=nums[nums[i]];
nums[temp]=temp;
}
}
return -1;
}
}

4、二维数组中的查找

题目描述


在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。


示例


输入:


[[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]],7

输出:


true

思路分析


因为这个一个排好序的二维数组,查找时考虑使用二分查找。然而由题目可知,这个二维数组的排序有一定规律,按照二分查找的思路就是选定一个mid点,然而进行查找。因此考虑选择二维数组右上方的元素作为mid,如果target等于mid,则找到;如果target大于mid,就说明target不在第一行,此时接着判断第二行和最后一列,循环即可;如歌targte小于mid,就说明target不在最后一列,此时接着判断第一行和倒数第二列,循环即可。


代码


class Solution {
public boolean findNumberIn2DArray(int[][] matrix, int target) {
if(matrix.length == 0 || matrix[0].length == 0) return false;
int i = 0;
int j = matrix[0].length-1;
boolean flag = false;
while(i<=matrix.length-1 && j>=0){
if(target == matrix[i][j]){
flag=true;
break;
}
else if(target > matrix[i][j]){
i++;
}
else{
j--;
}
}
return flag;

}
}

5、替换空格

题目描述


请实现一个函数,将一个字符串中的每个空格替换成“%20”。


示例


输入:


"We Are Happy"

输出:


"We%20Are%20Happy"

思路分析


题目需要替换字符串,因此考虑使用StringBuffer类来实现。新建一个StringBuffer,遍历原字符串,如果字符为空格,则在sb中添加一个%20,如果字符不为空格,则添加该字符。


代码


public String replaceSpace (String s) {

StringBuffer sb = new StringBuffer();

for(int i=0; i
if(s.charAt(i)==){
sb.append("%20");
}
else{
sb.append(s.charAt(i));
}
}
return sb.toString();
}

6、从尾到头打印链表

题目描述


输入一个链表的头节点,从尾到头反过来返回每个节点的值(用数组返回)。


示例


输入:


head = [1,3,2]

输出:


[2,3,1]

思路分析


思路一:从尾到头打印这个链表,会考虑到使用先进后出的栈来解决。


思路二:另外一个思路也可以首先遍历一遍链表,记录下其长度,然后建立一个相同长度的数组,从后往前赋值即可。


代码


思路一:


class Solution {
public int[] reversePrint(ListNode head) {
Stack stack = new Stack();

for(ListNode node=head; node!=null; node=node.next){
stack.push(node);
}
int size = stack.size(); //记录栈长度,否则随着出栈栈长度会变小
int[] result = new int[size];

for(int i=0; i
result[i]=stack.pop().val;
}

return result;

}
}

思路二:


class Solution {
public int[] reversePrint(ListNode head) {

ListNode tmp = head;
int len = 0;
while(tmp!=null){
tmp=tmp.next;
len++;
}

int[] array = new int[len];
for(int j=len-1; j>=0; j--){
array[j] = head.val;
head=head.next;
}
return array;
}
}

相关文档

  • 建设手机银行限额修改
  • 什么学习方法最有效
  • 小学一年级语文上册期中考试卷
  • 2017年高级理财规划师常考知识点
  • 学生心语进步与收获
  • python如何运用到财务工作中存在的问题_财务工作存在问题及整改措施三篇
  • 包含九字的成语大全
  • 描写火锅的散文
  • Go语言sync包的应用详解
  • 2020年山东省聊城市妇幼保健院招聘双一流高校毕业生招聘简章
  • a2197屏幕多大
  • 我心中的青奥会初中作文
  • 《匆匆》读后感600字
  • 自己洗车发朋友圈说说22句
  • 玄幻小说图片素材无字
  • 关于在Spring Cloud Feign工程中使用Hystrix配置不生效的问题
  • 大学生组织部工作总结
  • 音乐教学论文
  • 逻辑回归损失函数和对数损失函数的关系
  • java 缓冲流 和流_java 文件字节和字符流 缓冲流
  • 华为p40麦克风在哪设置
  • 小学文化常识100题答案
  • Java 查找算法
  • 2019中考:盘点数学复习中常见的误区
  • 自己做手机主题的软件
  • 丙肝患者如何摄取营养治疗
  • 滑雪技巧
  • 20200802:力扣200周周赛题解
  • 农村年终工作总结优质范本
  • 小虾吃什么,养虾要注意什么
  • 猜你喜欢

  • 基于51单片机函数信号发生器设计
  • 幼儿园大班2019年新学期保教工作计划
  • (健康快乐悦读)地理常识悦读_台风是怎么样形成的
  • SDF—1a/54/KDEL基因电穿孔Molt-4细胞株的转染条件优化
  • 未成年人保护法的心得体会
  • 八项规定自查报告范文
  • 酒店员工仪容仪表检查标准
  • 解梦之梦见和尚
  • 东北版本四大天王是谁啊
  • 六年级作文诗歌:请你一定要比我幸福
  • 清徐县徐沟惠英毛衣编织店企业信息报告-天眼查
  • 一年级数学下册课件- 比较数的大小-人教版(共17张PPT)
  • 2012-2016年 配制的橡胶促进剂(HS381210 )进出口分析报告
  • 七年级历史与社会上册复*提纲
  • 经营连锁餐饮店也是一种艺术
  • 2019-2020年度重点小学一年级语文上学期期中考试试题赣莫?附解析
  • 二年级上册语文课件-第7单元第22课 狐狸分奶酪 课后作业(B组)人教(部编版) (共10张PPT)
  • 《如何成为一名优秀员工》培训有感.doc
  • 湖南省益阳市2016-2017学年高一下学期3月月考试题 数学 Word版含答案
  • 2021年扬州大学兽医学院829生物化学(自)考研仿真模拟五套题
  • 联想战略规划系统案例分析PPT精品文档47页
  • 微信心灵鸡汤经典语录
  • 论《三国演义》人物的悲剧色彩
  • 复旦大学微观经济学2004真题及答案
  • 最适合穷人的创业小项目
  • 第二炮兵工程学院简洁蓝色毕业论文答辩PPT模板毕业论文毕业答辩开题报告优秀PPT模板
  • 【数学课件】2018年吉林市中考数学一轮复*第41讲:操作探究型问题
  • 【感谢信】给朋友的感谢信3篇
  • 江苏省南京市玄武区2017-2018学年八年级下学期期末检测政治试题(图片版,答案不全)
  • 币须知道 |马云又抢占了一块高地,蚂蚁金服区块链跨境汇款正式落地,2018世界杯板块排名涨幅第一...
  • 如何才能做好私营企业的办公室主任
  • 马鞍山市隆鑫金属材料贸易有限公司企业信用报告-天眼查
  • 2019-2020年九年级科学考点跟踪训练 37 常见的化学反应 浙教版
  • (完整版)2019年内部控制手册-专利管理制度
  • 总经理的自我介绍演讲稿最新
  • 众口嚣嚣成语解释
  • 年产xx套汽车传感器生产建设项目可行性研究报告
  • 上海团荣贸易有限公司企业信用报告-天眼查
  • 初中春游活动方案
  • 莱阳九月婚礼策划有限公司企业信用报告-天眼查
  • 帅气的图片大全动漫
  • 高三写景作文《写景作文:落叶》600字
  • 电脑版