当前位置: 首页 > news >正文

为了之后找工作不被虐,每天刷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;
    }
}

相关文章:

  • React 入门(超详细)
  • 蓝桥杯Web前端练习-----渐变色背景生成器
  • 区块链基本原理
  • Redis单线程还是多线程?IO多路复用原理
  • Element table组件内容\n换行解决办法
  • Day14 文件操作
  • 【百面成神】Redis基础11问,你能坚持到第几问
  • 配置IDEA自带Maven插件的镜像源
  • 简介虚拟地址空间:保障进程间独立性的机制
  • 【剑指offer】旋转数组的最小数字
  • 手写一个简单的RPC框架
  • 如何创建和编写项目管理计划?
  • 算法设计与分析 实验五 贪心算法
  • 正式环境关闭swagger
  • 动态内存的开辟
  • SegmentFault for Android 3.0 发布
  • android百种动画侧滑库、步骤视图、TextView效果、社交、搜房、K线图等源码
  • canvas 高仿 Apple Watch 表盘
  • JavaScript工作原理(五):深入了解WebSockets,HTTP/2和SSE,以及如何选择
  • javascript面向对象之创建对象
  • Java的Interrupt与线程中断
  • js面向对象
  • node 版本过低
  • Redash本地开发环境搭建
  • supervisor 永不挂掉的进程 安装以及使用
  • Vue.js源码(2):初探List Rendering
  • 阿里云爬虫风险管理产品商业化,为云端流量保驾护航
  • 函数式编程与面向对象编程[4]:Scala的类型关联Type Alias
  • 记一次删除Git记录中的大文件的过程
  • 让你成为前端,后端或全栈开发程序员的进阶指南,一门学到老的技术
  • 容器化应用: 在阿里云搭建多节点 Openshift 集群
  • 使用putty远程连接linux
  • 微信小程序上拉加载:onReachBottom详解+设置触发距离
  • 为什么要用IPython/Jupyter?
  • 硬币翻转问题,区间操作
  • 再谈express与koa的对比
  • 阿里云IoT边缘计算助力企业零改造实现远程运维 ...
  • ​七周四次课(5月9日)iptables filter表案例、iptables nat表应用
  • # Java NIO(一)FileChannel
  • # 透过事物看本质的能力怎么培养?
  • (4)logging(日志模块)
  • (M)unity2D敌人的创建、人物属性设置,遇敌掉血
  • (二十一)devops持续集成开发——使用jenkins的Docker Pipeline插件完成docker项目的pipeline流水线发布
  • (仿QQ聊天消息列表加载)wp7 listbox 列表项逐一加载的一种实现方式,以及加入渐显动画...
  • (附源码)ssm高校志愿者服务系统 毕业设计 011648
  • (力扣记录)1448. 统计二叉树中好节点的数目
  • (十)c52学习之旅-定时器实验
  • *** 2003
  • ..回顾17,展望18
  • .jks文件(JAVA KeyStore)
  • .net core使用RPC方式进行高效的HTTP服务访问
  • .NET 中让 Task 支持带超时的异步等待
  • .NET 中使用 TaskCompletionSource 作为线程同步互斥或异步操作的事件
  • .NET/C# 避免调试器不小心提前计算本应延迟计算的值
  • .w文件怎么转成html文件,使用pandoc进行Word与Markdown文件转化