程序员面试金典:翻转子串、链表中倒数第k个结点

2023-12-19 21:58

本文主要是介绍程序员面试金典:翻转子串、链表中倒数第k个结点,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

1.翻转子串

题目描述

假定我们都知道非常高效的算法来检查一个单词是否为其他字符串的子串。请将这个算法编写成一个函数,给定两个字符串s1和s2,请编写代码检查s2是否为s1旋转而成,要求只能调用一次检查子串的函数。

给定两个字符串s1,s2,请返回bool值代表s2是否由s1旋转而成。字符串中字符为英文字母和空格,区分大小写,字符串长度小于等于1000。

测试样例:

"Hello world","worldhello "
返回:false
"waterbottle","erbottlewat"
返回:true

解法1:将两个字符串变成char数组,然后再进行排序,最后用equals方法比较两个字符数组

import java.util.*;public class ReverseEqual {public boolean checkReverseEqual(String s1, String s2) {if(s1.length()!=s2.length())	return false;char []ch1=s1.toCharArray();char []ch2=s2.toCharArray();Arrays.sort(ch1);Arrays.sort(ch2);if(Arrays.equals(ch1,ch2))return true;return false;}
}

解法2:将两个字符串变成char数组,排序然后挨个比较是否相等

import java.util.*;public class ReverseEqual {public boolean checkReverseEqual(String s1, String s2) {if(s1.length()!=s2.length())	return false;char ch1[]=s1.toCharArray();	char ch2[]=s2.toCharArray();Arrays.sort(ch1);Arrays.sort(ch2);for (int i = 0; i < ch2.length; i++) {if(ch1[i]!=ch2[i]){return false;}}return true;}
}

解法3:通过两个字符串拼接,然后看看这个字符串是否包含其中的单个字符串

import java.util.*;public class ReverseEqual {public boolean checkReverseEqual(String s1, String s2) {String str=s1+s1;return str.contains(s2);}
}

解法4:用两个int数组分别统计两个字符串中字母的个数是否相等。

import java.util.*;public class ReverseEqual {public boolean checkReverseEqual(String s1, String s2) {// write code hereif(s1.length()!=s2.length())	return false;byte arr1[]=new byte[128];byte arr2[]=new byte[128];for (int i = 0; i < s1.length(); i++) {arr1[s1.charAt(i)]++;arr2[s2.charAt(i)]++;}for (int i = 0; i < arr2.length; i++) {if(arr1[i]!=arr2[i])return false;}return true;}
}

2.链表中倒数第k个结点

题目描述

输入一个链表,输出该链表中倒数第k个结点。

方法1:找到倒数第k个节点,返回其头节点

public class Main{public static void main(String[] args) {//链表:1->3->5->8->6->5		k=2ListNode t1=new ListNode(1);ListNode t2=new ListNode(3);ListNode t3=new ListNode(5);ListNode t4=new ListNode(8);ListNode t5=new ListNode(6);ListNode t6=new ListNode(5);t1.next=t2;t2.next=t3;t3.next=t4;t4.next=t5;t5.next=t6;ListNode tt=FindKthToTail(t1, 2);while(tt!=null){System.out.print(tt.val+"->");tt=tt.next;}}public static ListNode FindKthToTail(ListNode head,int k) {ListNode node = head;if(node==null) return null;int length=0;while(node!=null){node=node.next;length++;}if(k>length) return null;ListNode list=head;for(int i=0;i<length-k;i++){list=list.next;}return list;}
}

方法2:用两个指针,一个先移k个,然后让第二个移动,当第一个移到结尾时,第二个就移到倒数第k个节点了

import util.java.Algorithm.ListNode;public class Main{public static void main(String[] args) {//链表:1->3->5->8->6->5		k=2ListNode t1=new ListNode(1);ListNode t2=new ListNode(3);ListNode t3=new ListNode(5);ListNode t4=new ListNode(8);ListNode t5=new ListNode(6);ListNode t6=new ListNode(5);t1.next=t2;t2.next=t3;t3.next=t4;t4.next=t5;t5.next=t6;ListNode tt=FindKthToTail(t1, 2);while(tt!=null){System.out.print(tt.val+"->");tt=tt.next;}}public static ListNode FindKthToTail(ListNode head,int k) {ListNode p=head;ListNode pre=head;int a=k;int count=0;while(p!=null){p=p.next;count++;if(k<=0){pre=pre.next;}k--;}if(count<a)	return null;return pre;}
}

这篇关于程序员面试金典:翻转子串、链表中倒数第k个结点的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/513837

相关文章

使用C++实现链表元素的反转

《使用C++实现链表元素的反转》反转链表是链表操作中一个经典的问题,也是面试中常见的考题,本文将从思路到实现一步步地讲解如何实现链表的反转,帮助初学者理解这一操作,我们将使用C++代码演示具体实现,同... 目录问题定义思路分析代码实现带头节点的链表代码讲解其他实现方式时间和空间复杂度分析总结问题定义给定

字节面试 | 如何测试RocketMQ、RocketMQ?

字节面试:RocketMQ是怎么测试的呢? 答: 首先保证消息的消费正确、设计逆向用例,在验证消息内容为空等情况时的消费正确性; 推送大批量MQ,通过Admin控制台查看MQ消费的情况,是否出现消费假死、TPS是否正常等等问题。(上述都是临场发挥,但是RocketMQ真正的测试点,还真的需要探讨) 01 先了解RocketMQ 作为测试也是要简单了解RocketMQ。简单来说,就是一个分

poj2406(连续重复子串)

题意:判断串s是不是str^n,求str的最大长度。 解题思路:kmp可解,后缀数组的倍增算法超时。next[i]表示在第i位匹配失败后,自动跳转到next[i],所以1到next[n]这个串 等于 n-next[n]+1到n这个串。 代码如下; #include<iostream>#include<algorithm>#include<stdio.h>#include<math.

poj3261(可重复k次的最长子串)

题意:可重复k次的最长子串 解题思路:求所有区间[x,x+k-1]中的最小值的最大值。求sa时间复杂度Nlog(N),求最值时间复杂度N*N,但实际复杂度很低。题目数据也比较水,不然估计过不了。 代码入下: #include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<cstring

spoj705( 求不相同的子串个数)

题意:求串s的不同子串的个数 解题思路:任何子串都是某个后缀的前缀,对n个后缀排序,求某个后缀的前缀的个数,减去height[i](第i个后缀与第i-1 个后缀有相同的height[i]个前缀)。 代码如下: #include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<cstrin

csu1329(双向链表)

题意:给n个盒子,编号为1到n,四个操作:1、将x盒子移到y的左边;2、将x盒子移到y的右边;3、交换x和y盒子的位置;4、将所有的盒子反过来放。 思路分析:用双向链表解决。每个操作的时间复杂度为O(1),用数组来模拟链表,下面的代码是参考刘老师的标程写的。 代码如下: #include<iostream>#include<algorithm>#include<stdio.h>#

秋招最新大模型算法面试,熬夜都要肝完它

💥大家在面试大模型LLM这个板块的时候,不知道面试完会不会复盘、总结,做笔记的习惯,这份大模型算法岗面试八股笔记也帮助不少人拿到过offer ✨对于面试大模型算法工程师会有一定的帮助,都附有完整答案,熬夜也要看完,祝大家一臂之力 这份《大模型算法工程师面试题》已经上传CSDN,还有完整版的大模型 AI 学习资料,朋友们如果需要可以微信扫描下方CSDN官方认证二维码免费领取【保证100%免费

深入手撕链表

链表 分类概念单链表增尾插头插插入 删尾删头删删除 查完整实现带头不带头 双向链表初始化增尾插头插插入 删查完整代码 数组 分类 #mermaid-svg-qKD178fTiiaYeKjl {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-

建立升序链表

题目1181:遍历链表 时间限制:1 秒 内存限制:32 兆 特殊判题:否 提交:2744 解决:1186 题目描述: 建立一个升序链表并遍历输出。 输入: 输入的每个案例中第一行包括1个整数:n(1<=n<=1000),接下来的一行包括n个整数。 输出: 可能有多组测试数据,对于每组数据, 将n个整数建立升序链表,之后遍历链表并输出。 样例输

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟)

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟) 题目描述 给定一个链表,链表中的每个节点代表一个整数。链表中的整数由 0 分隔开,表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点,新节点的值为原区间内所有节点值的和。合并后,需要移除所有的 0,并返回修改后的链表头节点。 思路分析 初始化:创建一个虚拟头节点