为了之后找工作不被虐,每天刷3道《剑指offer》Day-1

本文已收录于专栏
🌻
《刷题笔记》

文章目录

  • 前言
  • 💖 1、二维数组中的查找
    • 题目描述
    • 思路
  • 💖 2、替换空格
    • 题目描述
    • 思路
  • 💖 3、从尾到头打印链表
    • 题目描述
    • 思路一(反转函数)
    • 思路二(递归)
    • 思路二(栈)

前言

题目来源参考阿秀学长的刷题笔记,小戴只是把 C++的题解改成了 Java版本,并整理了其他思路,便于自己的学习~

如果解题有更好的方法,本文也会及时进行更新~

希望对你有帮助~ 一起加油哇~

💖 1、二维数组中的查找

牛客网原题链接

题目描述

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

[

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

]

给定 target = 7,返回 true

给定 target = 3,返回 false

思路

从右上角度往左下角不断查找,

如果右上角值比 target 小,就往下走,值比 taget 大,就往右走,值相等的话,返回 true,依次类推…

如果到了左下角,还没有找到和 tatget 相等的值,就返回 false~

public class Solution {
    public boolean Find(int target, int [][] array) {
        if(array.length==0 || array[0].length==0){
            return false;
        }
        int row = array.length; // 行
        int col = array[0].length; // 列
        int i = 0; // 行
        int j = col - 1; // 列
        while(i<row && j>=0){
            if(array[i][j] < target){
                i++;
            }else if(array[i][j] > target){
                j--;
            }else{
                return true;
            }
        }
        return false;
    }
}

💖 2、替换空格

牛客原题链接

题目描述

请实现一个函数,将一个字符串中的每个空格替换成“%20”。例如,当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy

思路

新建一个 StringBuilder 动态字符串数组存放替换之后的字符串,

遍历 str , 如果 字符为空格,采用 StringBuilder 中的 append 方法在动态字符串数组中添加 %20 ,否则添加原字符

public class Solution {
    public String replaceSpace(StringBuffer str) {
    	StringBuilder newStr = new StringBuilder();
        for(int i=0; i<str.length(); i++){
            char c = str.charAt(i);
            if(c == ' '){
                newStr.append("%20");
            }else{
                newStr.append(c);
            }
        }
        return newStr.toString();
    }
}

💖 3、从尾到头打印链表

牛客原题链接

题目描述

输入一个链表的头节点,按链表从尾到头的顺序返回每个节点的值(用数组返回)

思路一(反转函数)

新建一个 ArrayList ,遍历链表,从前往后保存每个节点的值到数组,

最后 反转函数reverse() 将数组反转

import java.util.*;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> list = new ArrayList();
        ListNode temp = listNode;
        while(temp != null){
            list.add(temp.val);
            temp = temp.next;
        }
        Collections.reverse(list); // 直接翻转链表
        return list;
    }
}

思路二(递归)

从表头开始往后递归进入每一个节点,遇到尾节点后开始返回,每次返回依次添加一个值进入输出数组,直到递归返回表头

import java.util.ArrayList;
public class Solution {
    //递归函数
    public void recursion(ListNode head, ArrayList<Integer> res){ 
        if(head != null){
            //先往链表深处遍历
            recursion(head.next, res); 
            //再填充到数组就是逆序
            res.add(head.val); 
        }
    }
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        //递归函数解决
        recursion(listNode, res);
        return res;
    }
}

思路二(栈)

顺序遍历链表,将链表的值push到栈中

然后再依次弹出栈中的元素,加入到数组中,即可实现链表逆序

import java.util.*;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> arr = new ArrayList<Integer>();
        Stack<Integer> s = new Stack<Integer>();
        while(listNode!=null){
            s.push(listNode.val);
            listNode = listNode.next;
        }
        while(!s.isEmpty()){
            arr.add(s.pop());
        }
        return arr;
    }
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/2909.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Celery使用:优秀的python异步任务框架

目录Celery 简介介绍安装基本使用Flask使用Celery异步任务定时任务Celery使用Flask上下文进阶使用参考停止Worker后台运行Celery 简介 介绍 Celery 是一个简单、灵活且可靠的&#xff0c;处理大量消息的分布式系统&#xff0c;并且提供维护这样一个系统的必需工具。 它是一个…

文心一言 vs GPT-4 —— 全面横向比较

文心一言 vs GPT-4 —— 全面横向比较 3月15日凌晨&#xff0c;OpenAI发布“迄今为止功能最强大的模型”——GPT-4。我第一时间为大家奉上了体验报告《OpenAI 发布GPT-4——全网抢先体验》。 时隔一日&#xff0c;3月16日下午百度发布大语言模型——文心一言。发布会上&#…

4万字企业数字化转型大数据湖项目建设和运营综合解决方案WORD

本资料来源公开网络&#xff0c;仅供个人学习&#xff0c;请勿商用&#xff0c;如有侵权请联系删除。部分资料内容&#xff1a; 3.1.4沙盒管理 利用Docker, 基于kubernetes主打的容器技术与微服务应用基础平台&#xff0c;HDFS和YARN均可依此建模&#xff0c;为上层应用提供微服…

不愧是2023年就业最难的一年,还好有车企顶着~

就业龙卷风已经来临&#xff0c;以前都说找不到好的工作就去送外卖&#xff0c;但如今外卖骑手行业都已经接近饱和状态了&#xff0c;而且骑手们的学历也不低&#xff0c;本科学历都快达到了30%了&#xff0c;今年可以说是最难找到工作的一年。 像Android 开发行业原本就属于在…

学习 Python 之 Pygame 开发魂斗罗(十)

学习 Python 之 Pygame 开发魂斗罗&#xff08;十&#xff09;继续编写魂斗罗1. 解决敌人不开火的问题2. 创建爆炸效果类3. 为敌人跳入河中增加爆炸效果4. 玩家击中敌人继续编写魂斗罗 在上次的博客学习 Python 之 Pygame 开发魂斗罗&#xff08;九&#xff09;中&#xff0c;…

深度长文 | 数据安全共享技术发展综述及在能源电力领域应用研究

开放隐私计算 编者按数据要素的流通共享与协同应用是数字时代中数据要素市场培育的核心内容&#xff0c;数据安全共享技术能够有效实现数据的安全共享&#xff0c;避免“数据孤岛”现象、隐私泄露事件等.本文对国内外数据安全共享技术研究成果及进展进行了全面综述.首先&#x…

[前端笔记037]vue2之vuex

前言 本笔记参考视频&#xff0c;尚硅谷:BV1Zy4y1K7SH p105 - p116 vuex简介和基本使用 概念&#xff1a;专门在 Vue 中实现集中式状态&#xff08;数据&#xff09;管理的一个 Vue 插件&#xff0c;对 vue 应用中多个组件的共享状态进行集中式的管理&#xff08;读/写&…

CVPR 2023 | 旷视研究院入选论文亮点解读

近日&#xff0c;CVPR 2023 论文接收结果出炉。近年来&#xff0c;CVPR 的投稿数量持续增加&#xff0c;今年收到有效投稿 9155 篇&#xff0c;和 CVPR 2022 相比增加 12%&#xff0c;创历史新高。最终&#xff0c;大会收录论文 2360 篇&#xff0c;接收率为 25.78 %。本次&…

烤鱼界头牌半天妖发文致歉,背后暴露了哪些问题?

3月24日&#xff0c;半天妖烤鱼官方针对“两家门店食品安全问题”&#xff0c;发表致歉声明&#xff0c;并宣布将两家涉事门店永久关停。半天妖烤鱼爆出的食品安全问题再次提醒我们&#xff0c;加强门店监管和管理工作&#xff0c;保障消费者的健康和安全&#xff0c;成为了行业…

7.避免不必要的渲染

目录 1 组件更新机制 2 虚拟DOM配合Diff算法 3 减轻state 4 shouldComponentUpdate() 4.1 基本使用 4.2 使用参数 5 纯组件 5.1 基本使用 5.2 纯组件的比较方法 shallow compere 1 组件更新机制 当父组件重新渲染时&#xff0c;父组件的所有子组件也会重新…

如何理解AQS

AQS核心数据结构 AQS内部主要维护了一个FIFO&#xff08;先进先出&#xff09;的双向链表。 AQS数据结构原理 AQS内部维护的双向链表中的各个节点分别指向直接的前驱节点和直接的后续节点。所以&#xff0c;在AQS内部维护的双向链表可以从其中的任意一个节点遍历前驱结点和后…

【尝鲜版】ChatGPT插件开发指南

3月23日&#xff0c;OpenAI官方发布了一则公告&#xff0c;宣告ChatGPT已经支持了插件功能&#xff0c;现在处于内测阶段。插件的意义不仅仅在于功能的扩展&#xff0c;它直接让ChatGTP拥有了联网的能力&#xff01;简直是猛兽出笼、蛟龙出海&#xff0c;要让ChatGPT大杀特杀啊…

phpstorm断点调试

环境&#xff1a;win10phpstorm2022phpstudy8lnmp 1、phpinfo(); 查看是否安装xdebug&#xff0c;没有走以下流程 2、phpstudy中切换不同版本php版本&#xff0c;有些版本不支持xdebug&#xff08;如php8.0.2&#xff09;&#xff0c;有些已经自带了&#xff08;如php7.3.9&a…

Java奠基】Java经典案例讲解

目录 卖飞机票 找质数 开发验证码 数组元素的复制 评委打分 数字加密 数字解密 抢红包 模拟双色球 二维数组 卖飞机票 需求&#xff1a;机票价格按照淡季旺季、头等舱和经济舱收费、输入机票原价、月份和头等舱或经济舱。按照如下规则计算机票价格&#xff1a; 旺季&…

技术分享——Java8新特性

技术分享——Java8新特性1.背景2. 新特性主要内容3. Lambda表达式4. 四大内置核心函数式接口4.1 Consumer<T>消费型接口4.2 Supplier<T>供给型接口4.3 Function<T,R>函数型接口4.4 Predicate<T> 断定型接口5. Stream流操作5.1 什么是流以及流的类型5.2…

[攻城狮计划]如何优雅的在RA2E1上运行RT_Thread

文章目录[攻城狮计划]|如何优雅的在RA2E1上运行RT_Thread准备阶段&#x1f697;开发板&#x1f697;开发环境&#x1f697;下载BSP&#x1f697;编译烧录连接串口总结[攻城狮计划]|如何优雅的在RA2E1上运行RT_Thread &#x1f680;&#x1f680;开启攻城狮的成长之旅&#xff0…

【ChatGPT】教你搭建多任务模型

ChatGPT教你搭建多任务模型 You: tell me what’s your version of gpt ? ChatGPT: As an AI language model developed by OpenAI, I am based on the GPT (Generative Pretrained Transformer) architecture. However, my version is known as GPT-3.5, which is an updat…

数据泄漏防护 (DLP) 工具保护敏感数据

通过实时安全监控&#xff0c;通过端点&#xff08;即 USB、电子邮件、打印等&#xff09;检测、中断和防止敏感数据泄露。使用 DataSecurity Plus 的数据泄漏防护 &#xff08;DLP&#xff09; 工具保护敏感数据不被泄露或被盗。DataSecurity Plus 主要功能包括&#xff1a; …

Android APP检查设备是否为平板

正文 Android APP判断设备是否为平板的三种方法&#xff1a; 通过屏幕尺寸判断。一般来说&#xff0c;平板电脑的屏幕尺寸比手机大很多&#xff0c;可以根据屏幕的长宽比和尺寸等信息来区分设备类型。通过屏幕像素密度判断。一般来说&#xff0c;平板电脑的屏幕像素密度比手机…

Java开发一年不到,来面试居然敢开口要20K,面完连8K都不想给~

前言 我的好朋友兼大学同学老伍家庭经济情况不错&#xff0c;毕业之后没两年自己存了点钱加上家里的支持&#xff0c;自己在杭州开了一家网络公司。由于公司不是很大所以公司大部分的开发人员都是自己面试的&#xff0c;近期公司发展的不错&#xff0c;打算扩招也面试了不少人…