数据结构与算法常考面试题

第01讲：常用数据结构

数组和字符串是最基本的数据结构，在很多编程语言中都有着十分相似的性质，而围绕着它们的算法面试题也是最多的。

很多时候，在分析字符串相关面试题的过程中，我们往往要针对字符串当中的每一个字符进行分析和处理，甚至有时候我们得先把给定的字符串转换成字符数组之后再进行分析和处理。

举例：翻转字符串“algorithm”。

解法：用两个指针，一个指向字符串的第一个字符 a，一个指向它的最后一个字符 m，然后互相交换。交换之后，两个指针向中央一步步地靠拢并相互交换字符，直到两个指针相遇。这是一种比较快速和直观的方法。

注意：由于无法直接修改字符串里的字符，所以必须先把字符串变换为数组，然后再运用这个算法。

public class Test {

public static void main(String[] args) {

String str = "algorithm";

char[] arr = str.toCharArray();

for (int i = 0; i < arr.length/2; i++) {

char tmp = arr[i];

arr[i] = arr[arr.length-1-i];

arr[arr.length-1-i] = tmp;

}

String ret = String.valueOf(arr);

String ret1 = new String(arr);

System.out.println(ret);

System.out.println(ret1);

}

}

LeetCode 第 242 题：给定两个字符串 s 和 t，编写一个函数来判断 t 是否是 s 的字母异位词。

说明：你可以假设字符串只包含小写字母。

示例 1

输入: s = "anagram", t = "nagaram"

输出: true

示例 2

输入: s = "rat", t = "car"

输出: false

public class TestDemo {

public static boolean isAnagram(String s,String t) {

if(s.length() != t.length()) {

return false;

}

int[] a = new int[26];

int[] b = new int[26];

for (int i = 0; i < 26; i++) {

a[i] = 0;

b[i] = 0;

}

for (int i = 0; i < s.length(); i++) {

a[s.charAt(i) - 'a'] ++;

b[s.charAt(i) - 'a'] ++;

}

for (int i = 0; i < 26; i++) {

if(a[i] != b[i]) {

return false;

}

}

return true;

}

public static void main(String[] args) {

String s = "anagram";

String t = "nagaram";

System.out.println(isAnagram(s, t));

}

}

public class TestDemo {

public static boolean isAnagram(String s,String t) {

if(s.length() != t.length()) {

return false;

}

int[] a = new int[26];

for (int i = 0; i < 26; i++) {

a[i] = 0;

}

for (int i = 0; i < s.length(); i++) {

a[s.charAt(i) - 'a'] ++;

}

for (int i = 0; i < t.length(); i++) {

a[t.charAt(i) - 'a'] --;

}

for (int i = 0; i < 26; i++) {

if(a[i] != 0) {

return false;

}

}

return true;

}

public static void main(String[] args) {

String s = "anagram";

String t = "nagaram";

System.out.println(isAnagram(s, t));

}

}

public static boolean isAnagram(String s,String t) {

if(s.length() != t.length()) {

return false;

}

char[] a = s.toCharArray();

char[] b = t.toCharArray();

Arrays.sort(a);

Arrays.sort(b);

for (int i = 0; i < b.length; i++) {

if(a[i] != b[i]) {

return false;

}

}

return true;

}

第08讲：高频真题解析 I

LeetCode 第 03 题：给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。

示例 1
输入："abcabcbb"
输出：3
解释：因为无重复字符的最长子串是"abc"，其长度为3。

示例 2
输入："bbbbb"
输出：1
解释：因为无重复字符的最长子串是 "b"，其长度为 1。

示例 3
输入："pwwkew"
输出：3
解释：因为无重复字符的最长子串是 "wke"，其长度为 3。
注意：答案必须是子串的长度，"pwke" 是一个子序列，不是子串。

public static int lengthOfLongestSubstring(String s) {

Set<Character> set = new HashSet<Character>();

int max = 0;

for (int j = 0; j < s.length(); j++) {

int i = 0;

while(set.contains(s.charAt(j))) {

set.remove(s.charAt(i));

i++;

}

set.add(s.charAt(j));

max = Math.max(max, set.size());

}

return max;

}

优化的线性法：

public static int lengthOfLongestSubstring(String s){

Map<Character,Integer> map = new HashMap<>();

int max = 0;

for(int i = 0, j = 0; j < s.length(); j++) {

if (map.containsKey(s.charAt(j))) {

i = Math.max(i, map.get(s.charAt(j)) + 1);

}

map.put(s.charAt(j), j);

max = Math.max(max, j - i + 1);

}

return max;

}

相关知识

Android数据结构与算法之一 基础简介
重读《学习JavaScript数据结构与算法
借花献佛！朋友干了5年整的Java面试官，给我分享了一份面试官最爱问的Java面试题
破解菜鸟算法题：新手必看的高效解题技巧与实战案例
2024年前端框架：第二章：Layui(类UI ) 框架：关于2，2024年最新初级Web前端开发面试题
机器学习算法
腾讯T2大牛亲自教你！javaif语句判断月份在哪个季节
揭秘高效修剪工具：算法革新带你轻松打理数字森林
数据结构
堪称最好最全的A*算法详解（译文）

网址: 数据结构与算法常考面试题 https://www.huajiangbk.com/newsview1134456.html