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日

相关文章

  • java高级用法之JNA中的Structure

    下面详细讲解一下Java高级用法之JNA中的Structure: 什么是JNA？ JNA全称为Java Native Access，它是一个开源的Java库，可以让Java程序无需写任何Native代码实现直接访问本地DLL、 shared libraries和C等 Native语言编写的动态库(so)等。 Structure在JNA中的作用 在JNA中，S…

    Java 2023年5月26日
    00

  • Win2003平台上jsp虚拟主机环境的架设(IIS6+J2SDK+resin)

    这里提供Win2003平台上jsp虚拟主机环境的架设攻略，该环境采用IIS6+J2SDK+Resin，具体步骤如下： 准备工作 下载并安装J2SDK（Java SE Development Kit） 下载Resin，并解压到指定目录下。 下载并安装IIS6。 安装Resin 进入Resin解压后的主目录，找到bin目录。 右键点击resin.exe，选择“以…

    Java 2023年6月15日
    00

  • Struts2学习笔记(9)-Result配置全局结果集

    首先我们需要了解什么是Struts2的Result配置。 在Struts2中，Result是将Action执行后返回的结果封装成一个对象，通常包含视图名称、视图类型和一些其它相关的信息。通过配置Result，我们可以指定如何处理Action执行后返回的结果，例如将结果转发到某个JSP或者跳转到某个URL等。 全局结果集是一种在Struts2中配置全局Resu…

    Java 2023年5月20日
    00

  • 简介Java的Spring框架的体系结构以及安装配置

    下面我将详细讲解“简介Java的Spring框架的体系结构以及安装配置”的完整攻略。 1. 介绍 Spring框架是一款轻量级的开源Java框架，用于构建企业级应用程序。它提供了全方位的功能来支持开发大型、复杂的企业级应用程序。Spring框架由多个模块组成，每个模块负责提供不同的功能，每个模块都可以独立使用，也可以一起使用，非常灵活。 2. Spring框…

    Java 2023年5月19日
    00

  • 2022最新Java泛型详解(360度无死角介绍)

    2022最新Java泛型详解(360度无死角介绍) 什么是Java泛型？ Java泛型是Java SE 5.0版本中的新特性，提供了一种对类型进行参数化的机制，让代码的重用性和类型安全性都得到了极大的提高。 泛型主要有以下特点： 提高代码的可读性和可维护性 在编译期进行类型检查，提高代码的安全性 可以适用于各种类型，提高代码的重用性 如何使用Java泛型？ …

    Java 2023年5月26日
    00

  • 一文详解Java中字符串的基本操作

    一文详解Java中字符串的基本操作 字符串定义 在Java中，字符串是一种数据类型，用来表示一系列的字符组合。在Java中，字符串是用双引号（” “）括起来的，可以包含任意数量的字符。 String str1 = "hello world"; 字符串拼接 在Java中，字符串可以通过加号（+）进行拼接。 String str1 = &qu…

    Java 2023年5月26日
    00

  • js简单的分页器插件代码实例

    下面是关于“js简单的分页器插件代码实例”的完整攻略： 1. 什么是分页器 分页器是一种常见的网页分页功能，在信息展示较多的网页中特别常见，例如商品列表、新闻列表、书籍列表等。通俗的讲，分页器就是把一系列信息按一定的规则分成若干页，然后在页面上生成一个标准的页码导航，方便用户快速地切换页面。 2. 如何实现一个简单的分页器 下面介绍一种简单的前端JS分页器实…

    Java 2023年6月16日
    00

  • Spring Boot外部化配置实战解析

    SpringBoot外部化配置实战解析 SpringBoot是一个非常流行的Java Web框架，它可以帮助我们快速构建Web应用程序。在实际开发中，我们通常需要将一些配置信息从代码中分离出来，以便于在不同的环境中进行配置。本文将详细讲解SpringBoot外部化配置实战解析的完整攻略，并提供两个示例。 1. 配置文件 在SpringBoot中，我们可以使用…

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