franki Blog

make a small progress every day

leetcode 104题

leetcode 104题二叉树的最大深度给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。说明: 叶子节点是指没有子节点的节点。示例：给定二叉树 [3,9,20,null,null,15,7]， 3 / \ 9 20 / \ 15 7 返回它的最大深度 3 。思路使用广度优先搜索，...

Posted by franki on November 16, 2020

leetcode 100题

leetcode 100题相同的树给定两个二叉树，编写一个函数来检验它们是否相同。如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。示例输入: 1 1 / \ / \ 2 3 2 3 [1,2,3], [1,2,3] 输出: true 来源...

Posted by franki on November 16, 2020

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