算法-刷题

桃扇骨 2022-09-09 02:26 292阅读 0赞

剑指Offer快速过了一遍

字节-飞书高频题-前15

各公司的高频面试算法题，可在 CodeTop查询

(1) 146. LRU 缓存机制

我的实现：

  1. class LRUCache {
  4.     ArrayDeque<Integer> queue;
  5.     Map<Integer, Integer> cacheMap;
  6.     private int capacity;
  7.     private int size;
  8.     public LRUCache(int capacity) {
  10.         if (capacity < 1) {
  12.             throw new RuntimeException("capacity is error");
  13.         }
  14.         this.capacity = capacity;
  15.         queue = new ArrayDeque<>();
  16.         cacheMap = new HashMap<>();
  17.         size = 0;
  19.     }
  21.     public int get(int key) {
  23.         if (cacheMap.isEmpty()) {
  25.             return -1;
  26.         }
  27.         if (cacheMap.containsKey(key)) {
  29.             queue.remove(key);
  30.             queue.add(key);
  31.             return cacheMap.get(key);
  32.         } else {
  34.             return -1;
  35.         }
  36.     }
  38.    public void put(int key, int value) {
  40.         if (cacheMap.containsKey(key)) {
  42.             cacheMap.put(key, value);
  43.             queue.remove(key);
  44.             queue.add(key);
  45.         } else {
  47.             size ++;
  48.             if (size > capacity) {
  50.                 int needDelete = queue.pop();
  51.                 cacheMap.remove(needDelete);
  52.             }
  53.             cacheMap.put(key, value);
  54.             queue.add(key);
  55.         }
  56.     }
  57. }

官方实现：

  1. public class LRUCache {
  3.     class DLinkedNode {
  5.         int key;
  6.         int value;
  7.         DLinkedNode prev;
  8.         DLinkedNode next;
  9.         public DLinkedNode() {
  10.     }
  11.         public DLinkedNode(int _key, int _value) {
  12.     key = _key; value = _value;}
  13.     }
  15.     private Map<Integer, DLinkedNode> cache = new HashMap<Integer, DLinkedNode>();
  16.     private int size;
  17.     private int capacity;
  18.     private DLinkedNode head, tail;
  20.     public LRUCache(int capacity) {
  22.         this.size = 0;
  23.         this.capacity = capacity;
  24.         // 使用伪头部和伪尾部节点
  25.         head = new DLinkedNode();
  26.         tail = new DLinkedNode();
  27.         head.next = tail;
  28.         tail.prev = head;
  29.     }
  31.     public int get(int key) {
  33.         DLinkedNode node = cache.get(key);
  34.         if (node == null) {
  36.             return -1;
  37.         }
  38.         // 如果 key 存在，先通过哈希表定位，再移到头部
  39.         moveToHead(node);
  40.         return node.value;
  41.     }
  43.     public void put(int key, int value) {
  45.         DLinkedNode node = cache.get(key);
  46.         if (node == null) {
  48.             // 如果 key 不存在，创建一个新的节点
  49.             DLinkedNode newNode = new DLinkedNode(key, value);
  50.             // 添加进哈希表
  51.             cache.put(key, newNode);
  52.             // 添加至双向链表的头部
  53.             addToHead(newNode);
  54.             ++size;
  55.             if (size > capacity) {
  57.                 // 如果超出容量，删除双向链表的尾部节点
  58.                 DLinkedNode tail = removeTail();
  59.                 // 删除哈希表中对应的项
  60.                 cache.remove(tail.key);
  61.                 --size;
  62.             }
  63.         }
  64.         else {
  66.             // 如果 key 存在，先通过哈希表定位，再修改 value，并移到头部
  67.             node.value = value;
  68.             moveToHead(node);
  69.         }
  70.     }
  72.     private void addToHead(DLinkedNode node) {
  74.         node.prev = head;
  75.         node.next = head.next;
  76.         head.next.prev = node;
  77.         head.next = node;
  78.     }
  80.     private void removeNode(DLinkedNode node) {
  82.         node.prev.next = node.next;
  83.         node.next.prev = node.prev;
  84.     }
  86.     private void moveToHead(DLinkedNode node) {
  88.         removeNode(node);
  89.         addToHead(node);
  90.     }
  92.     private DLinkedNode removeTail() {
  94.         DLinkedNode res = tail.prev;
  95.         removeNode(res);
  96.         return res;
  97.     }
  98. }
  100. 作者：LeetCode-Solution
  101. 链接：https://leetcode-cn.com/problems/lru-cache/solution/lruhuan-cun-ji-zhi-by-leetcode-solution/
  102. 来源：力扣（LeetCode）

(2) 3. 无重复字符的最长子串

  1. class Solution {
  3.     public int lengthOfLongestSubstring(String s) {
  5.         if (s == null || s.length() == 0) {
  7.             return 0;
  8.         }
  9.         int max = 0;
  10.         int left = 0;
  11.         HashMap<Character, Integer> map = new HashMap<>();
  12.         for (int i = 0; i< s.length(); i++ ) {
  14.             Character charTemp = s.charAt(i);
  15.             if (map.containsKey(charTemp)) {
  17.                 left = Math.max(left, map.get(charTemp) + 1);
  18.             }
  19.             map.put(charTemp, i);
  20.             max = Math.max(max, i - left + 1);
  21.         }
  22.         return max;
  23.     }
  24. }

(3) 206. 反转链表

  1. /**
  2.  * Definition for singly-linked list.
  3.  * public class ListNode {
  4.  *     int val;
  5.  *     ListNode next;
  6.  *     ListNode() {}
  7.  *     ListNode(int val) { this.val = val; }
  8.  *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  9.  * }
  10.  */
  11. class Solution {
  13.     public ListNode reverseList(ListNode head) {
  15.         if (head == null || head.next == null) {
  17.             return head;
  18.         }
  19.         ListNode preNode = null;
  20.         ListNode currentNode = head;
  21.         while (currentNode != null) {
  23.             ListNode next = currentNode.next;
  24.             currentNode.next = preNode;
  25.             preNode = currentNode;
  26.             currentNode = next;
  27.         }
  28.         return preNode;
  29.     }
  30. }

(4) 103. 二叉树的锯齿形层序遍历

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode() {}
  8.  *     TreeNode(int val) { this.val = val; }
  9.  *     TreeNode(int val, TreeNode left, TreeNode right) {
  10.  *         this.val = val;
  11.  *         this.left = left;
  12.  *         this.right = right;
  13.  *     }
  14.  * }
  15.  */
  16. class Solution {
  18.     public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
  20.         List<List<Integer>> result = new LinkedList<List<Integer>>();
  21.         if (root == null) {
  23.             return result;
  24.         }
  25.         Deque<TreeNode> deque = new LinkedList<>();
  26.         deque.offer(root);
  27.         int currentLevel = 0;
  28.         while (!deque.isEmpty()) {
  30.             int levelSize = deque.size();
  31.             Deque<Integer> currentList = new LinkedList<>();
  32.             for (int i=0; i< levelSize; i++) {
  34.                 TreeNode currentNode = deque.peek();
  35.                 if (currentNode.left != null) {
  37.                     deque.offer(currentNode.left);
  38.                 }
  39.                 if (currentNode.right != null) {
  41.                     deque.offer(currentNode.right);
  42.                 }
  43.                 if (currentLevel % 2 == 0) {
  45.                     currentList.offerLast(currentNode.val);
  46.                 } else {
  48.                     currentList.offerFirst(currentNode.val);
  49.                 }
  50.                 deque.poll();
  51.             }
  52.             currentLevel ++ ;
  53.             result.add(new LinkedList<>(currentList));
  54.         }
  55.         return result;
  57.     }
  58. }

该题是 102.二叉树的层序遍历 的变换之后的题目，下面是 二叉树层序遍历的实现：

  1. class Solution {
  3.     public List<List<Integer>> levelOrder(TreeNode root) {
  5.        List<List<Integer>> result = new LinkedList<List<Integer>>();
  6.         if (root == null) {
  8.             return result;
  9.         }
  10.         Deque<TreeNode> deque = new LinkedList<TreeNode>();
  11.         deque.offer(root);
  12.         while (!deque.isEmpty()) {
  14.             int size = deque.size();
  15.             List<Integer> currentList = new LinkedList<>();
  16.             for (int i=0; i< size; i++) {
  18.                 TreeNode currentNode = deque.peek();
  19.                 currentList.add(currentNode.val);
  20.                 if (currentNode.left != null) {
  22.                     deque.offer(currentNode.left);
  23.                 }
  24.                 if (currentNode.right != null) {
  26.                     deque.offer(currentNode.right);
  27.                 }
  28.                 deque.poll();
  29.             }
  30.             result.add(currentList);
  31.         }
  32.         return result;
  33.     }
  34. }

(5) 121.买卖股票的最佳时机

  1. public class Solution {
  3.     /**
  4.      *暴力解法
  5.      * @param prices
  6.      * @return
  7.      */
  8.     public int maxProfit1(int[] prices) {
  10.         int maxProfit = 0;
  11.         for (int i = 0; i<prices.length - 1; i++) {
  13.             for (int j = i+1; j < prices.length; j++) {
  15.                 int currentProfit = prices[j] - prices[i];
  16.                 if (currentProfit > maxProfit) {
  18.                     maxProfit = currentProfit;
  19.                 }
  20.             }
  21.         }
  22.         return maxProfit;
  23.     }
  25.     /**
  26.      * 非暴力
  27.      * @param prices
  28.      * @return
  30.     */
  31.     public int maxProfit(int[] prices) {
  33.         int minPrice = Integer.MAX_VALUE;
  34.         int maxProfit = 0;
  35.         for (int i = 0; i<prices.length; i++) {
  37.            if (prices[i] < minPrice) {
  39.                minPrice = prices[i];
  40.            } else if (prices[i] - minPrice > maxProfit) {
  42.                maxProfit = prices[i] - minPrice;
  43.            }
  44.         }
  45.         return maxProfit;
  46.     }
  48. }

(6) 41.缺失的第一个正数

  1. class Solution {
  3.     public int firstMissingPositive(int[] nums) {
  5.         for (int i = 0; i<nums.length;i++) {
  7.             while (nums[i] >=1 && nums[i]<=nums.length && nums[i] != nums[nums[i] -1]) {
  9.                 swap(nums, i, nums[i] -1);
  10.             }
  11.         }
  13.         for (int i=0;i<nums.length;i++) {
  15.             if (i != nums[i]-1) {
  17.                 return i+1;
  18.             }
  19.         }
  20.         return nums.length +1;
  21.     }
  24.     private void swap(int[] nums, int i,int j) {
  26.         int temp = nums[i];
  27.         nums[i] = nums[j];
  28.         nums[j] = temp;
  29.     }
  30. }

(7) 46.全排列

  1. public class Permute {
  4.     public List<List<Integer>> permute(int[] nums) {
  6.         List<List<Integer>> result = new ArrayList<>();
  7.         if (nums == null || nums.length == 0) {
  9.             return result;
  10.         }
  11.         List<Integer> outPut = new ArrayList<>();
  12.         for (int i=0; i< nums.length; i++) {
  14.             outPut.add(nums[i]);
  15.         }
  16.         backTrack(0, nums.length, outPut, result);
  17.         return result;
  18.     }
  20.     public void backTrack(int first, int n, List<Integer> outPut, List<List<Integer>> result) {
  22.         if (first == n) {
  24.             result.add(new ArrayList<>(outPut));
  25.         }
  26.         for (int i = first; i<n; i++) {
  28.             Collections.swap(outPut, first, i);
  29.             backTrack(first+1, n, outPut, result);
  30.             Collections.swap(outPut, first, i);
  31.         }
  32.     }
  33. }

(8) 1. 两数之和

  1. class Solution {
  3.     public int[] twoSum(int[] nums, int target) {
  5.         HashMap<Integer, Integer> numAndIndex = new HashMap<>();
  6.         for (int i=0;i<nums.length;i++) {
  8.             int b = target - nums[i];
  9.             if (numAndIndex.containsKey(b)) {
  11.                 return new int[]{
  12.     i, numAndIndex.get(b)};
  13.             }
  14.             numAndIndex.put(nums[i], i);
  15.         }
  16.         return new int[0];
  17.     }  
  18. }

(9) 128. 最长连续序列

  1. public int longestConsecutive(int[] nums) {
  3.         HashSet<Integer> numSet = new HashSet<>();
  4.         for (int i=0; i<nums.length;i++) {
  6.             numSet.add(nums[i]);
  7.         }
  8.         int maxLength = 0;
  9.         for (int i =0;i<nums.length;i++) {
  11.             if (!numSet.contains(nums[i] - 1)) {
  13.                 int currentNum = nums[i];
  14.                 int currentLength = 1;
  15.                 while (numSet.contains(currentNum + 1)) {
  17.                     currentNum +=1;
  18.                     currentLength ++;
  19.                 }
  20.                 maxLength = Math.max(maxLength, currentLength);
  21.             }
  22.         }
  23.         return maxLength;
  24.     }

发表评论

表情：
评论列表 （有 0 条评论，292人围观）

还没有评论，来说两句吧...

相关阅读

    相关 算法刷题：位运算

    位运算 程序中的所有数在计算机内存中都是以 0、1 二进制的形式储存的。位运算就是直接对整数在内存中的二进制位进行操作。 计算机对二进制数据进行的运算(+、-

    谁践踏了优雅谁践踏了优雅/ 0 赞/ 198 阅读

    相关 贪心算法刷题

    1.递增数组 题目链接：[递增数组][Link 1] 题目介绍： > 牛牛有一个数组array，牛牛可以每次选择一个连续的区间，让区间的数都加1，他想知道把这

    快来打我*快来打我*/ 0 赞/ 85 阅读

    相关 算法-刷题

    剑指Offer快速过了一遍 字节-飞书高频题-前15 各公司的高频面试算法题，可在 [CodeTop][]查询 (1) 146. LRU 缓存机制 我的实现

    桃扇骨桃扇骨/ 0 赞/ 293 阅读

    相关 【自用】刷算法题路径

    知识点总结： 排序算法（堆排序、快排、归并） 动态规划 回溯算法 链表、二叉树、数组、堆、栈 路径： 1. 把总结的题目复习一遍 2. 复习牛

    蔚落蔚落/ 0 赞/ 343 阅读