franki Blog

make a small progress every day

leetcode 146题

leetcode 146题 LRU缓存机制运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。实现 LRUCache 类： LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存 int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。 void put(...

Posted by franki on November 15, 2020

双向链表常见操作

双向链表双向链表顾名思义，有两条链，即是每个节点都包含一个 prev，next 指向，下面是双向链表的常见操作，手写双向链表的感觉有点嗨！(参考 google 后大神写的代码) ps: 之前没有想过可以不断改变 tail 的指向来达到不断添加新的节点到链表结尾，学到了，哈哈！双向链表图示：代码 // DoublyLinklistNode class DoublyLinke...

Posted by franki on November 14, 2020

leetcode 160题

leetcode 160题相交链表编写一个程序，找到两个单链表相交的起始节点。如下面的两个链表在节点 c1 开始相交。思路利用双指针 pa、pb同时在链表a、链表b上行走，假设链表b比较短，pb先走完，会去到链表a的头结点开始继续走 pa在链表上走完后，会继续去到链表b上的头结点继续走，最终会消除高度差，相遇的节点即为要求出的节点代码 function g...

Posted by franki on November 12, 2020

leetcode 109题

有序链表转换二叉搜索树思路先把链表的值逐一存入数组利用二分，把数组的值先确定中位数为root，然后根据root划分左子树、右子树代码 function sortedListToBST(head) { var arr = []; while (head) { arr.push(head.val); head = head.ne...

Posted by franki on November 11, 2020

leetcode 21题

leetcode 21题合并两个有序链表将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。示例 1 输入：1->2->4, 1->3->4 输出：1->1->2->3->4->4 思路使用 prehead prev 记录 l1 l2 走过的节点，当前 l1 当前的值小于 l...

Posted by franki on November 10, 2020

剑指offer 24题

剑指offer 24题反转链表定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。示例 1 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL 思路使用三个变量 prev cur next，循环当中改变其指向代码 function reve...

Posted by franki on November 9, 2020

leetcode 61题

leetcode 61题旋转链表给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。示例 1 输入: 1->2->3->4->5->NULL, k = 2 输出: 4->5->1->2->3->NULL 解释: 向右旋转 1 步: 5->1->2->3->4->N...

Posted by franki on November 8, 2020

leetcode 24题

leetcode 24题两两交换链表中的节点给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。示例 1 输入：head = [1,2,3,4] 输出：[2,1,4,3] 示例 2 输入：head = [] 输出：[] 示例 3 输入：head = [1] 输出：[1] 思路利用递归的思路...

Posted by franki on November 8, 2020

leetcode 232题

leetcode 232题用栈实现队列请你仅使用两个栈实现先入先出队列。队列应当支持一般队列的支持的所有操作（push、pop、peek、empty）：实现 MyQueue 类： void push(int x) 将元素 x 推到队列的末尾 int pop() 从队列的开头移除并返回元素 int peek() 返回队列开头的元素 boolean empty() 如果队列为空，返回...

Posted by franki on November 7, 2020

leetcode 394题

leetcode 394题字符串解码给定一个经过编码的字符串，返回它解码后的字符串。编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。此外，你可以认为原始数据不包含数字，所有的数字只表示重...

Posted by franki on November 6, 2020