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();
}
阅读剩余 87%

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

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

相关文章

  • Java 实战项目锤炼之网上图书馆管理系统的实现流程

    Java 实战项目锤炼之网上图书馆管理系统的实现流程 本文将详细讲解如何实现一个网上图书馆管理系统，包括前端页面设计、后端接口实现等方面的内容。 前端页面设计 1. 首页 首页应该包含以下内容： 搜索框：用户可以在搜索框中输入书名、作者、ISBN等信息，以便找到他们想要借阅的书籍。 推荐书单：系统会根据用户的阅读历史等信息，为用户推荐一些可能感兴趣的书籍。 …

    Java 2023年5月24日
    00

  • 详细分析Java 泛型的使用

    详细分析Java 泛型的使用 一、什么是Java泛型 Java泛型是Java SE 5引入的一种新特性，它为Java的类型系统引入了参数化类型的概念。我们在定义类、接口、方法时，可以指定使用泛型来处理这些类型参数，从而使得代码更加通用。 二、为什么要使用Java泛型 类型安全：泛型可以让代码更加健壮和安全，因为泛型会在编译时期进行类型检查。 代码复用：通过使…

    Java 2023年5月26日
    00

  • Spring-Data-JPA整合MySQL和配置的方法

    下面是Spring-Data-JPA整合MySQL和配置的详细攻略： 1. 添加依赖 首先，在项目的Maven或Gradle配置文件中，添加以下依赖来引入Spring-Data-JPA和MySQL的相关依赖。 Maven: <dependency> <groupId>org.springframework.boot</group…

    Java 2023年5月20日
    00

  • spring data jpa 创建方法名进行简单查询方式

    Spring Data JPA 是Spring Data 技术栈中的一个子项目，它简化了基于 JPA 技术栈的数据访问层的开发，其中使用方法名进行简单查询是其特性之一。 1. 配置 Spring Data JPA 首先需要在 Spring Boot 项目中配置 Spring Data JPA 支持，具体步骤如下： 在 pom.xml 中引入 Spring D…

    Java 2023年6月3日
    00

  • Java与SpringBoot对redis的使用方式

    Java与SpringBoot对redis的使用方式可以通过Spring Data Redis进行实现。接下来以示例的方式详细讲解Java与Spring Boot对redis的使用方式。 环境准备 首先需要引入相关依赖： <dependency> <groupId>org.springframework.boot</groupI…

    Java 2023年5月19日
    00

  • springboot聚合工程的部署与深入讲解

    SpringBoot聚合工程的部署与深入讲解 什么是SpringBoot聚合工程？ SpringBoot聚合工程是指在一个工程中集成了多个模块，每个模块都是一个独立的SpringBoot项目。这些模块可以共享公共的代码和资源，同时也可以单独部署和运行。SpringBoot聚合工程的好处在于将多个关联的应用程序组合在一起，简化了项目的部署、维护和扩展。 如何创…

    Java 2023年5月20日
    00

  • Java的Struts框架报错“ActionServletMappingException”的原因与解决办法

    当使用Java的Struts框架时，可能会遇到“ActionServletMappingException”错误。这个错误通常由以下原因之一起： ServletMapping配置错误：如果配置文件中没有正确ServletMapping，则可能会现此错误。在这种情况下，需要检查文件以解决此问题。 ServletMapping无效：如果ServletMappin…

    Java 2023年5月5日
    00

  • mybatis plus实体类中字段映射mysql中的json格式方式

    下面是关于如何使用MybatisPlus实体类中字段映射MySQL中JSON格式的完整攻略。 1. 引入依赖 在pom.xml中加入以下依赖： <dependency> <groupId>com.baomidou</groupId> <artifactId>mybatis-plus-boot-starter&l…

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