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日

相关文章

  • 基于MyBatis XML配置方法(全面了解)

    基于 MyBatis XML 配置方法完整攻略 1. 概述 MyBatis 是一款非常流行的 Java 持久化框架，它将 SQL 语句和 Java 对象之间的映射关系配置在 XML 文件中，极大地简化了数据库访问的开发工作。本文将介绍如何通过 XML 配置方式使用 MyBatis 进行数据库访问。 2. 准备工作 在开始使用 MyBatis 之前，需要进行以…

    Java 2023年5月20日
    00

  • java初学者如何让编程学习起来更简单

    这里提供一些帮助Java初学者更轻松学习编程的攻略： 1. 选择适合自己的学习方法 学习方法的选择对于学习编程语言来说非常重要。有的人更喜欢以视频教程和示例代码为主，而有些人则更喜欢以书本为主。此外，还有一些适用于不同学习风格的在线课程，例如交互式课程和mooc（大规模开放式在线课程）。初学者应该探索各种不同的学习途径，找出自己最适合的一种。 2. 坚持练习…

    Java 2023年5月19日
    00

  • 如何基于spring security实现在线用户统计

    基于 Spring Security 实现在线用户统计需要进行以下步骤： 引入 Spring Security 相关依赖 我们需要在项目中引入 Spring Security 相关依赖，可以通过 Maven / Gradle 等方式引入，示例 Maven 依赖如下： <dependency> <groupId>org.springfr…

    Java 2023年5月20日
    00

  • Springboot WebFlux集成Spring Security实现JWT认证的示例

    下面是关于“Springboot WebFlux集成Spring Security实现JWT认证的示例”的完整攻略。 一、简介 在开始之前，先简单介绍一下SpringBoot和SpringSecurity。 SpringBoot：是Spring官方提供的一个快速开发框架，它能够极大地简化项目的搭建和配置，提高开发效率。 SpringSecurity：是Spr…

    Java 2023年5月20日
    00

  • IIS和tomcat5多站点配置流程

    针对你提出的问题，“IIS和tomcat5多站点配置流程”的完整攻略，以下是步骤和示例： 1. 配置IIS IIS是Windows操作系统默认带的Web服务器，它可以作为一个反向代理服务器，把所有请求转发到Tomcat服务器。下面介绍如何配置IIS，使其可以代理多个Tomcat站点。 1.1 安装IIS 在Windows服务器上打开“服务器管理器”，选择“添…

    Java 2023年5月19日
    00

  • java实现多线程交替打印两个数

    要实现多线程交替打印两个数，可以使用Java提供的线程同步机制来完成。具体步骤如下： 1.创建两个线程对象，一个线程对象负责打印奇数，另一个线程对象负责打印偶数。 2.使用synchronized关键字来实现线程同步，确保只有一个线程在打印时另一个线程处于等待状态。 3.使用wait和notifyAll方法来实现线程同步。当一方线程打印完后调用wait方法使…

    Java 2023年5月18日
    00

  • java的io操作(将字符串写入到txt文件中)

    下面我将详细讲解“Java的IO操作(将字符串写入到txt文件中)”的完整攻略。 IO操作简介 在Java中，IO（Input/Output）操作是非常重要的一个主题。对于Java开发者来说，IO操作是必不可少的。在Java中，提供了java.io包和java.nio包分别供我们进行IO操作。 其中，java.io包位于Java1.0版本中，提供了非常丰富的…

    Java 2023年5月19日
    00

  • 如何基于SpringSecurity的@PreAuthorize实现自定义权限校验方法

    下面是详细攻略。 1. SpringSecurity基本概念 SpringSecurity是基于Spring框架的安全认证和授权模块，可以为我们的应用提供强大的安全管理。在SpringSecurity中，每个用户都有一个唯一的用户名和一个密码，SpringSecurity会在用户登录时对这些信息进行校验，如果校验通过则允许用户进行下一步操作，否则拒绝用户进行…

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