当前位置: 首页 > 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
  • 动态内存的开辟
  • JS 中的深拷贝与浅拷贝
  • @angular/forms 源码解析之双向绑定
  • [译]如何构建服务器端web组件,为何要构建?
  • 《用数据讲故事》作者Cole N. Knaflic:消除一切无效的图表
  • 【347天】每日项目总结系列085(2018.01.18)
  • 【前端学习】-粗谈选择器
  • JavaScript DOM 10 - 滚动
  • js递归,无限分级树形折叠菜单
  • React 快速上手 - 06 容器组件、展示组件、操作组件
  • Travix是如何部署应用程序到Kubernetes上的
  • WePY 在小程序性能调优上做出的探究
  • 从零开始的无人驾驶 1
  • 多线程 start 和 run 方法到底有什么区别?
  • 关于Android中设置闹钟的相对比较完善的解决方案
  • 前端学习笔记之观察者模式
  • 入门级的git使用指北
  • 微信小程序实战练习(仿五洲到家微信版)
  • 为什么要用IPython/Jupyter?
  • 昨天1024程序员节,我故意写了个死循环~
  • ​猴子吃桃问题:每天都吃了前一天剩下的一半多一个。
  • "无招胜有招"nbsp;史上最全的互…
  • # 学号 2017-2018-20172309 《程序设计与数据结构》实验三报告
  • #、%和$符号在OGNL表达式中经常出现
  • #pragma预处理命令
  • #微信小程序:微信小程序常见的配置传值
  • $(function(){})与(function($){....})(jQuery)的区别
  • (1)Map集合 (2)异常机制 (3)File类 (4)I/O流
  • (Spark3.2.0)Spark SQL 初探: 使用大数据分析2000万KF数据
  • (zt)最盛行的警世狂言(爆笑)
  • (附源码)计算机毕业设计SSM智慧停车系统
  • (论文阅读32/100)Flowing convnets for human pose estimation in videos
  • (转载)跟我一起学习VIM - The Life Changing Editor
  • .NET 使用 ILMerge 合并多个程序集,避免引入额外的依赖
  • .NET的数据绑定
  • /etc/fstab和/etc/mtab的区别
  • @NoArgsConstructor和@AllArgsConstructor,@Builder
  • [2669]2-2 Time类的定义
  • [3300万人的聊天室] 作为产品的上游公司该如何?
  • [acwing周赛复盘] 第 69 场周赛20220917
  • [CareerCup] 12.3 Test Move Method in a Chess Game 测试象棋游戏中的移动方法