1. Python技术站首页
  2. 其他
  3. Java

剑指Offer之Java算法习题精讲链表与字符串及数组

• Java

剑指Offer之Java算法习题精讲链表与字符串及数组

概述

这篇文章将介绍剑指Offer中Java算法习题中链表、字符串以及数组部分的完整攻略。涵盖了题目的基本概念、思路分析以及代码实现。通过学习这些算法题解，读者可以提高对数据结构和算法的理解以及编程能力。

链表

链表是一种基本的数据结构，是由一些列结点组成的，每个结点包含数据和指向下一个结点的指针。常见的链表有单链表、双向链表等。链表相较于数组具有更好的动态性及灵活性，但是相对于数组会更加消耗空间。

链表的基本操作

1. 链表的遍历
public void printLinkList(ListNode head){
  ListNode node = head;
  while(node!=null){
    System.out.print(node.variable+" ");
    node = node.next;
  }
}
2. 链表的删除
public ListNode deleteNode(ListNode head, ListNode toDelete){
  if(head==null||toDelete==null) return null;
  if(toDelete.next!=null){
    //如果要删除的节点不是尾节点
    ListNode nextNode = toDelete.next;
    toDelete.variable = nextNode.variable;
    toDelete.next = nextNode.next;
  }else if(toDelete==head){
    //链表中只有一个节点，删除头节点（也是尾节点）
    head = null;
  }else{
    //链表中有多个节点，删除尾节点
    ListNode node = head;
    while(node.next!=toDelete){
      node = node.next;
    }
    node.next = null;
  }
  return head;
}
3. 链表的插入
public ListNode insertIntoTail(ListNode head, int val){
  ListNode newNode = new ListNode(val);
  if(head==null){
    head = newNode;
  }else{
    ListNode node = head;
    while(node.next!=null){
      node = node.next;
    }
    node.next = newNode;
  }
  return head;
}

链表的常见问题

1. 反转链表

题目描述：输入一个链表，反转链表后，输出链表的所有元素。

解题思路：从头遍历链表，使用pre、current、next节点记录当前节点的前一个节点、当前节点、下一个节点。每次将current节点指向pre节点，然后pre节点后移，current节点后移，反转后的链表的头结点就是最后一个遍历到的节点。

代码实现：

public ListNode reverseList(ListNode head){
  if(head==null||head.next==null) return head;
  ListNode pre = null, current = head, next = null;
  while(current!=null){
    next = current.next;
    current.next = pre;
    pre = current;
    current = next;
  }
  return pre;
}
2. 链表中倒数第k个节点

题目描述：输入一个链表的头结点，输出链表中倒数第k个节点的值。链表的尾节点定义为倒数第一个节点。

解题思路：设链表长度为n，则倒数第k个节点为从头结点开始的第n-k+1个节点。可以使用两个指针p1和p2，初始时都指向头结点。p1先移动k-1个节点，然后p1和p2同时移动，直到p1到达尾节点。此时p2所指向的节点就是所要求的节点。

代码实现：

public ListNode findKthToTail(ListNode head, int k){
  if(head==null||k<=0) return null;
  ListNode p1 = head, p2 = head;
  while(k>1&&p1.next!=null){
    p1 = p1.next;
    k--;
  }
  if(k>1) return null;
  while(p1.next!=null){
    p1 = p1.next;
    p2 = p2.next;
  }
  return p2;
}

字符串

字符串是由多个字符组成的数据类型，通常使用字符数组来实现。Java中的字符串是不可变的，即一旦创建就不能改变。因此，在修改字符串时，需要使用StringBuilder或StringBuffer类。

字符串的基本操作

1. 字符串的遍历
public void printString(String s){
  for(int i=0;i<s.length();i++){
    System.out.print(s.charAt(i));
  }
}
2. 字符串的比较
public boolean isEqual(String s1, String s2){
  if(s1==null||s2==null) return false;
  if(s1.length()!=s2.length()) return false;
  for(int i=0;i<s1.length();i++){
    if(s1.charAt(i)!=s2.charAt(i)){
      return false;
    }
  }
  return true;
}
3. 字符串的替换
public String replaceSpace(String s){
  if(s==null) return null;
  StringBuilder sb = new StringBuilder();
  for(int i=0;i<s.length();i++){
    char c = s.charAt(i);
    if(c==' '){
      sb.append("%20");
    }else{
      sb.append(c);
    }
  }
  return sb.toString();
}

字符串的常见问题

1. 替换空格

题目描述：请实现一个函数，将一个字符串中的空格替换成"%20"。

解题思路：因为字符串的长度会变化，所以首先需要遍历字符串得到空格的总数，然后使用StringBuilder类创建一个新的字符串，使用两个指针i和j，分别指向原字符串和新字符串。遍历原字符串，如果当前字符不是空格，则直接将其添加到新的字符串中，否则将"%20"添加到新字符串中。每次添加时将指针j向后移动。

代码实现：

public String replaceSpace(String s){
  if(s==null) return null;
  int count = 0;
  for(int i=0;i<s.length();i++){
    if(s.charAt(i)==' '){
      count++;
    }
  }
  int i = s.length()-1, j = i+count*2;
  StringBuilder sb = new StringBuilder(j+1);
  while(i>=0){
    char c = s.charAt(i);
    if(c==' '){
      sb.setCharAt(j--, '0');
      sb.setCharAt(j--, '2');
      sb.setCharAt(j--, '%');
    }else{
      sb.setCharAt(j--, c);
    }
    i--;
  }
  return sb.toString();
}
2. 是否旋转词

题目描述：如果两个字符串str1和str2都由各个字符重新排列组成，那么这两个字符串互为旋转词。输入两个字符串，判断其中一个字符串是否是另一个字符串的旋转词。

解题思路：若str1和str2是旋转词，那么将str1半轴对称后得到的字符串（例如abcdef，变为defabc）就一定是包含str2的字符串。因此判断str2是否是字符串str1+str1的子串即可。

代码实现：

public boolean isRotation(String s1, String s2){
  if(s1==null||s2==null||s1.length()!=s2.length()) return false;
  return (s1+s1).contains(s2);
}

数组

数组是一种线性结构，由一系列相同类型的元素组成的，可以使用下标随机访问数组中的元素。Java中的数组是有序的，可以由数组的下标进行访问，并且数组的元素类型也可以为对象类型。

数组的基本操作

1. 数组的遍历
public void printArray(int[] arr){
  for(int i=0;i<arr.length;i++){
    System.out.print(arr[i]+" ");
  }
}
2. 数组的查找
public int binarySearch(int[] arr, int target){
  int left = 0, right = arr.length-1, mid;
  while(left<=right){
    mid = (left+right)/2;
    if(arr[mid]==target){
      return mid;
    }else if(arr[mid]<target){
      left = mid+1;
    }else{
      right = mid-1;
    }
  }
  return -1;
}
3. 数组的排序
public void sortArray(int[] arr){
  Arrays.sort(arr);
}

数组的常见问题

1. 二维数组中的查找

题目描述：在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。输入一个二维数组和一个整数，判断数组中是否含有该整数。

解题思路：考虑数组中的一个元素，它左边的元素都比它小，下边的元素都比它大，因此可以从右上角（或左下角）开始查找，每次都将查找的元素与目标值进行比较，如果目标值大于该元素，则将查找范围缩小到该元素下方的区域；如果目标值小于该元素，则将查找范围缩小到该元素左边区域。

代码实现：

public boolean find(int[][] arr, int target){
  if(arr==null||arr.length==0||arr[0].length==0) return false;
  int rows = arr.length, columns = arr[0].length;
  int r = 0, c = columns-1;
  while(r<rows&&c>=0){
    if(arr[r][c]==target){
      return true;
    }else if(arr[r][c]>target){
      c--;
    }else{
      r++;
    }
  }
  return false;
}
2. 顺时针打印矩阵

题目描述：输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。

解题思路：按层循环，从左到右、从上到下、从右到左、从下到上。需要注意当矩阵为单行或单列时，可能会遍历两次相同的元素。

代码实现：

public ArrayList<Integer> printMatrix(int[][] matrix){
  ArrayList<Integer> res = new ArrayList<>();
  if(matrix==null) return res;
  int rows = matrix.length, columns = matrix[0].length;
  int start = 0;
  while(start*2<rows&&start*2<columns){
    int endX = columns-1-start, endY = rows-1-start;
    // 从左到右
    for(int i=start;i<=endX;i++){
      res.add(matrix[start][i]);
    }
    // 从上到下
    for(int i=start+1;i<=endY;i++){
      res.add(matrix[i][endX]);
    }
    // 从右到左
    if(start<endY){
      for(int i=endX-1;i>=start;i--){
        res.add(matrix[endY][i]);
      }
    }
    // 从下到上
    if(start<endX){
      for(int i=endY-1;i>=start+1;i--){
        res.add(matrix[i][start]);
      }
    }
    start++;
  }
  return res;
}

示例说明

示例一：链表

题目描述：输入一个链表，反转链表后，输出链表的所有元素。

解题思路：从头遍历链表，使用pre、current、next节点记录当前节点的前一个节点、当前节点、下一个节点。每次将current节点指向pre节点，然后pre节点后移，current节点后移，反转后的链表的头结点就是最后一个遍历到的节点。

代码实现：

public ListNode reverseList(ListNode head){
  if(head==null||head.next==null) return head;
  ListNode pre = null, current = head, next = null;
  while(current!=null){
    next = current.next;
    current.next = pre;
    pre = current;
    current = next;
  }
  return pre;
}

示例二：字符串

题目描述：请实现一个函数，将一个字符串中的空格替换成"%20"。

解题思路：因为字符串的长度会变化，所以首先需要遍历字符串得到空格的总数，然后使用StringBuilder类创建一个新的字符串，使用两个指针i和j，分别指向原字符串和新字符串。遍历原字符串，如果当前字符不是空格，则直接将其添加到新的字符串中，否则将"%20"添加到新字符串中。每次添加时将指针j向后移动。

代码实现：

public String replaceSpace(String s){
  if(s==null) return null;
  int count = 0;
  for(int i=0;i<s.length();i++){
    if(s.charAt(i)==' '){
      count++;
    }
  }
  int i = s.length()-1, j = i+count*2;
  StringBuilder sb = new StringBuilder(j+1);
  while(i>=0){
    char c = s.charAt(i);
    if(c==' '){
      sb.setCharAt(j--, '0');
      sb.setCharAt(j--, '2');
      sb.setCharAt(j--, '%');
    }else{
      sb.setCharAt(j--, c);
    }
    i--;
  }
  return sb.toString();
}

本站文章如无特殊说明，均为本站原创，如若转载，请注明出处：剑指Offer之Java算法习题精讲链表与字符串及数组 - Python技术站

赞 (0)
0 0 打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2023年5月19日
下一篇 2023年5月19日

相关文章

  • Spring Native打包本地镜像的操作方法(无需通过Graal的maven插件buildtools)

    Spring Native打包本地镜像的操作方法 简介 Spring Native是Spring团队推出的一款可以将Java代码编译成本地可执行二进制文件的工具，在性能、启动速度等方面拥有很大的优势。本文主要介绍如何使用Spring Native将Java应用打包成本地镜像。 环境准备 在开始之前，需要确保以下工具已经安装好并配置： Docker Java …

    Java 2023年6月2日
    00

  • 基于JSP实现一个简单计算器的方法

    基于JSP实现一个简单计算器的方法 1. 准备工作 确定需要实现的计算器功能，例如加减乘除四则运算、开方、取余等功能。 创建基于Maven的Web项目，添加所需的依赖。 “`xml javax.servlet jstl 1.2 taglibs standard 1.1.2 “` 在项目的src/main/webapp目录下创建转发器(Dispatcher…

    Java 2023年6月15日
    00

  • spring的maven配置文件整理

    下面是关于“spring的maven配置文件整理”的完整攻略： 1. 前言 Maven 是一个 Java 项目的自动化构建工具，它不仅可以自动下载所依赖的 JAR 包，还可以自动生成项目的目录结构，打包，测试等功能，是 Java 开发中不可缺少的工具。当我们使用 Maven 进行 Spring 项目配置的时候，一些配置文件需要整理好，以便使得 Maven 自…

    Java 2023年6月15日
    00

  • 浅谈Java中Spring Boot的优势

    浅谈Java中SpringBoot的优势 介绍 Spring Boot是一个基于Spring框架的开发、构建和运行应用的框架、工具集，它能够让开发者极少的配置和快速构建出现代化的基于Spring的企业应用程序。本文将深入探讨Spring Boot在Java应用程序开发中的优势。 优势 快速搭建项目 Spring Boot可以通过约定的方式快速地构建出一个标准…

    Java 2023年5月15日
    00

  • c#使用反射调用类型成员示例

    下面是详细讲解“c#使用反射调用类型成员示例”的完整攻略。 什么是反射 反射是指程序在运行时能够访问、检查和修改它本身状态或行为的一种能力。在C#语言中，使用反射可以探测对象的类型信息、访问和操纵对象的属性和方法，甚至创建对象的实例。 如何使用反射调用类型成员 在C#中进行反射操作之前，需要先获取目标类型的System.Type对象。获取Type对象主要有以…

    Java 2023年6月15日
    00

  • java HttpClient传输json格式的参数实例讲解

    Java HttpClient传输JSON格式参数实例讲解 1. 什么是HttpClient HttpClient是一个HTTP客户端工具包，Apache HttpClient的封装版本是阿希替（AxTire）HTTP Client。 HttpClient我们可以用它来模拟浏览器的请求，实现登录、提交表单、发送请求等功能，适用于各种简单和复杂的操作。 2. …

    Java 2023年5月26日
    00

  • TOMCAT+IIS配置方法

    下面是 “TOMCAT+IIS配置方法” 的完整攻略： 前置条件 安装好 TOMCAT 及 IIS，并且都能正常启动。 配置步骤 步骤一：修改 IIS 默认端口 为了确保 IIS 和 TOMCAT 能够同时运行，我们需要将 IIS 默认端口从 80 改为其他端口（如：8080）。 打开 IIS 管理器。 点击左边菜单栏的“默认网站”，然后在右边窗口中找到“基…

    Java 2023年5月19日
    00

  • java显示当前美国洛杉矶时间

    要在Java中显示当前美国洛杉矶时间，可以使用Java提供的时间日期API，以下是完整的攻略： 获取当前时间 使用Java提供的Date类可以获取当前时间。代码如下： Date date = new Date(); 设置时区为美国洛杉矶 使用Java提供的TimeZone类可以设置时区。代码如下： TimeZone timeZone = TimeZone.g…

    Java 2023年5月20日
    00
合作推广
合作推广
分享本页
返回顶部