前言

昨天参加了阿里云的笔试，笔试是单独给我发了一个链接，不像是统一的笔试，两个小时做两个题也是我没有想到的，最后还是没有做完。所以就想着来整理以下这两个题目，下面就开始了。

LRU缓存

题目

• 第一题：
• 实现一个 LRU 缓存，支持指定缓存大小，支持 get 和 put 操作。使用频率越低的数据放在越后面，若缓存满了，删除最后面的数据。（语言不限）
• 输入：操作序列，包括 get 和 put 操作。
• 输出：根据 get 操作返回对应的值，put 操作无输出。
• 要求：时间复杂度为 O(1)。需要考虑编程习惯，包括但不限于可读性、可维护性、命名规范、代码风格等。

分析

1. 这个题是力扣第147题，如果我们要实现时间复杂度为O(1)的要求，而且要满足使用频率越低的数据放在最后，也就是说当我们put一个数据之后，首先需要查询这个数据是否存在，如果存在还需要把这个数据放到最前面，其次是get方法，也需要我们查找到一个数据，再返回。
2. 我们能够想到的查询方法基本上不会有O(1)的存在，所以这里我们需要借助多个数据结构，比如用一个HashMap记录每一个节点的id和节点，用一个双向链表记录节点之间的相对位置。每次get节点，就用这个id来获取节点信息，可以直接在哈希映射(Hashmap)里面查找，这个复杂度为O(1)，找到之后获取对应的节点，然后输出节点的value。
3. 在实现get功能的时候，我们也要知道怎么定义一个节点，也就是说节点类里面有什么信息，就像定义二叉树的节点一样，双向链表的节点如何定义呢？那就看以下代码：

class DlinkedNode{int key;int value;DlinkedNode prev;DlinkedNode next;DlinkedNode(){}DlinkedNode(int key_,int value_){key = key_;value = value_;}
}

由此能够构建一个双向链表。

代码

public class LRUCache {// 正是因为链表节点有向前和向后的指针，所以当我们在HashMap中找到他的时候，我们同样能够在双向链表中找到他的位置class DLinkedNode {int key;int value;DLinkedNode prev;DLinkedNode next;public DLinkedNode() {}public DLinkedNode(int _key, int _value) {key = _key; value = _value;}}// 用HashMap来存储节点和id, 一个LRUCache就包括以下内容，首先有一个HashMap// 其次就是双向链表所需要的头指针与尾指针，再就是Cache的容量和目前已有的数据个数private Map<Integer, DLinkedNode> cache = new HashMap<Integer, DLinkedNode>();private int size;private int capacity;private DLinkedNode head, tail;//初始化的时候就得将各个变量都初始化，而且形成双向链表public LRUCache(int capacity) {this.size = 0;this.capacity = capacity;// 使用伪头部和伪尾部节点head = new DLinkedNode();tail = new DLinkedNode();head.next = tail;tail.prev = head;}public int get(int key) {DLinkedNode node = cache.get(key);if (node == null) {return -1;}// 如果 key 存在，先通过哈希表定位，再移到头部moveToHead(node);return node.value;}public void put(int key, int value) {DLinkedNode node = cache.get(key);if (node == null) {// 如果 key 不存在，创建一个新的节点DLinkedNode newNode = new DLinkedNode(key, value);// 添加进哈希表cache.put(key, newNode);// 添加至双向链表的头部addToHead(newNode);++size;if (size > capacity) {// 如果超出容量，删除双向链表的尾部节点DLinkedNode tail = removeTail();// 删除哈希表中对应的项cache.remove(tail.key);--size;}}else {// 如果 key 存在，先通过哈希表定位，再修改 value，并移到头部node.value = value;moveToHead(node);}}private void addToHead(DLinkedNode node) {node.prev = head;node.next = head.next;head.next.prev = node;head.next = node;}private void removeNode(DLinkedNode node) {node.prev.next = node.next;node.next.prev = node.prev;}// 想要把一个节点移到头部，就得先删除这个节点，再加入这个节点private void moveToHead(DLinkedNode node) {removeNode(node);addToHead(node);}private DLinkedNode removeTail() {DLinkedNode res = tail.prev;removeNode(res);return res;}
}

符号排序

题目

• 第二题：
  // 给出一个长度为N的数组，每个元素可能是数字或者字母（数字、字母不混合），
  // 请用自己最熟悉、且性能较高的方式进行排序，输出两个数组。
  // 要求：
  // 1、数字数组从小到大排序，字母数组从A到Z排序（字母不区分大小写）
  // 2、如果是多个字母，从首字母开始按顺序逐个从A到Z排序。

• 示例1：
  // 输入：
  // {“1”, “3”, “2”, “1”,”C”,”A”};
  // 输出：
  // {“1”,”1”,”2”,“3”};
  // {“A”,“C”};

• 示例2：
  // 输入：
  // {“11”,“333”,“BC”,“1”,“BA”,“A”};
  // 输出：
  // {“1”,“111”,“333”};
  // {“A”, “BA”,“BC”};

分析

我在这个题目卡住的地方就是排序算法。所以我重点记录我的排序算法，大致思路也就是把数字和字符串分组，分组之后各自排序，然后输出，题目挺简单的，就是排序算法自己是真的不熟，也没有写好。这里有两种路径，一是自己写排序算法，二是重写Arrays.sort()的排序规则。

自己写排序算法

快速排序

public class QuickSort {public static void main(String[] args) {int[] nums = {3,4,5,2,6,7,8,2,1};quickSort(nums,0,nums.length-1);for(int num:nums){System.out.print(num+" ");}}public static void quickSort(int[] nums,int L,int R){/*主要思想：分治法1. 随机选取一个pivot值2. 将所有小于pivot的值放在它的左边3. 将所有大于pivot的值放在它的右边4. 对所得到的左右两个子序列分别进行上面三部操作*//*具体怎么放：1. 习惯取第一个值为pivot，最左边为left，最右边为right2. 从right开始往左遍历，直到碰到比pivot小的数，将这个数放在left位置3. 从left开始往右遍历，直到碰到比pivot大的数，将这个数放在right位置4. 重复2、3，直到left==right，将pivot放到这个位置*/// 这里必须是大于等于，不能是等于if(L>=R) return;int left = L,right = R;int pivot = nums[left];while(left<right){// 这里的判断必须加上while(nums[right]>=pivot && left<right) right--;if(nums[right]<pivot) nums[left] = nums[right];while (nums[left]<=pivot && left<right) left++;if(nums[left]>pivot) nums[right] = nums[left];// 这里必须是大于等于，不能是等于if(left>=right) nums[left] = pivot;}quickSort(nums,L,left-1);quickSort(nums,left+1,R);}
}

冒泡排序

public class 冒泡排序 {public static void main(String[] args) {int[] nums = {3,4,5,2,6,7,8,8,8,2,1};sort(nums);for(int num:nums){System.out.print(num+" ");}}public static void sort(int[] nums){/*主要思想：外层进行N-1此迭代，每次迭代都能确定一个最大值的位置（如果是升序排序）内层如何迭代：从第一个位置到第N-i个位置，i为已经确定位置的个数，每次比较当前元素和下一个元素，让大的放后面*/for(int i = 0;i<nums.length-1;i++){for(int j = 0;j<nums.length-i-1;j++){if(nums[j]>nums[j+1]){int temp = nums[j];nums[j] = nums[j+1];nums[j+1] = temp;}}}}
}

如何修改Arrays.sort()的排序方式

import java.util.Arrays;
import java.util.Comparator;public class Arrays的排序 {public static void main(String[] args) {int[][] nums = {{1,5},{2,3},{3,4}};Arrays.sort(nums,new Comparator<int[]>(){@Overridepublic int compare(int[] a,int[] b){return a[1]-b[1];}});String[] nums1 = {"sbc","csd","aaa","aaabc","csw"};// 这里实现了一个字符串的比较算法Arrays.sort(nums1,new Comparator<String>(){@Overridepublic int compare(String str1,String str2){int s1 = 0,s2 = 0;while(s1<str1.length() && s2<str2.length()){if(str1.charAt(s1)==str2.charAt(s2)){s1++;s2++;}else {return str1.charAt(s1)-str2.charAt(s2);}}// 按照第一个数减去第二个数的规律，就是升序return ((s1>=str1.length())?0:str1.charAt(s1)) - ((s2>=str2.length())?0:str2.charAt(s2));}});}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！