JZX 轻语

LeetCode 1017 - 负二进制转换

首先对数字按正常的二进制展开，然后如果某个二进制位在新的表示法中属于负数，则需要”往前借一位”，比如，第3个比特在新的表示法中是-8，如果需要表示8，则需要利用第4个比特，即8 = -8 + 16，然后再进一步处理16之后的数字(前面的处理结果已经固定了，无后效)。如果某一位比特不仅原来的表示法需要使用到，且前面的数字又存在进位，则需要合并、往后面继续进位，如24 = 8 + 16 = -8...

Posted by Jeza Chen on April 28, 2024

LeetCode 779 - 第K个语法符号

Flash 此文章属于Flash闪念部分的短文

数组规律题，可以通过列举前面几层得出规律：0 -> 0,1 -> 0,1,1,0 -> 0,1,1,0,1,0,0,1 -> 0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0。每一层的长度都是上一层长度的两倍(一个数分裂出两个数)，且前半段即上一层数组，后半段是前半段的取反。令k从0开始计数，因此，第k位的取值，是第k - int(sqrt(k)) * ...

Posted by Jeza Chen on April 26, 2024

LeetCode 1146 - 快照数组

Flash 此文章属于Flash闪念部分的短文

简单想法是每次快照时，都存一份完整的列表，但这样会导致内存超限。优化思路类似于开散列法的哈希表。其中每个索引self._arr[i]使用一个桶来存储快照信息，其元素为一个记录快照id和值的元组(snap_id, val)。只有调用set保存的时候，才针对index新建一个快照信息。当使用get查询某个索引index内特定快照snap_id的值时，使用二分法搜索桶内self._arr[inde...

Posted by Jeza Chen on April 26, 2024

LeetCode 2385 - 感染二叉树需要的总时间

Flash 此文章属于Flash闪念部分的短文

有点难度的二叉树递归，节点的感染路径有三个方向：往下感染左子树，右子树以及往上感染祖先。可以通过一次遍历得到结果：使用一个变量ans维护当前的感染最长路径，按后序遍历树节点，如果遇到了start节点，则先将ans设置为其子树的高度。否则，对于某个节点，如果其左子树包含start节点，则可能的最长感染路径为start节点->...[从左子树往上感染]->本节点->...[往下...

Posted by Jeza Chen on April 24, 2024

LeetCode 1052 - 爱生气的书店老板

Flash 此文章属于Flash闪念部分的短文

题目中带有”连续”、”只能使用一次”等字眼，说明可以尝试使用滑动窗口解决。首先计算老板不抑制情绪的情况下，原始的满意度orig_satisfied = sum(cnt * (1 - is_grumpy) for cnt, is_grumpy in zip(customers, grumpy))，然后使用一个大小为minutes的窗口，计算窗口下抑制情绪所能带来的满意度提升，然后不断向右滑动窗...

Posted by Jeza Chen on April 23, 2024

LeetCode 39 & 216 & 377 - 组合总和相关问题

Flash 此文章属于Flash闪念部分的短文

这三天的每日一题都是组合总和的问题：第一天的题目39可以用回溯法解决，在参数中记录当前回溯的数组开始位置（由于重复选取，下一次回溯的数组开始位置可以和本次相同）、当前所选用的数字组合arr及其和cur_sum = sum(arr)。如果当前的cur_sum等于target，则加入到结果列表中并返回。为了加快搜寻，如果下一次回溯的cur_sum已经大于target，则直接剪...

Posted by Jeza Chen on April 22, 2024

LeetCode 725 - 分割链表

Flash 此文章属于Flash闪念部分的短文

链表题，首先需要遍历一次得到链表的长度length，然后按k切分链表，如果块i满足i < length % k，则该块的长度为length // k + 1（如果切分不均匀，前面的块比后面的块长）；否则，该块的长度为length // k。遍历的时候，使用两个变量curr和prev分别指向当前节点及前驱节点，当curr刚好指向某个块的头节点，则断开prev和curr的联系，将curr添...

Posted by Jeza Chen on April 21, 2024

LeetCode 713 - 乘积小于K的子数组

Flash 此文章属于Flash闪念部分的短文

使用一个滑动窗口维护当前乘积小于k的最长连续子数组。每当窗口右侧向右扩展一个元素时，结果(有效子数组数量)加上新窗口的长度(即，新增了以窗口当前右侧元素结尾的长度为1,2,…,滑动窗口大小的数组)。当窗口无法向右扩展时，则左侧边界向右移动以减少乘积，直到下一次尝试向右扩展成功。 class Solution: def numSubarrayProductLessThanK(se...

Posted by Jeza Chen on April 18, 2024

LeetCode 712 - 两个字符串的最小ASCII删除和

Flash 此文章属于Flash闪念部分的短文

带权重的编辑问题，其中删除一个字符的成本为字符的ASCII值。令dp[i][j]为子串s1[:i]和s2[:j]的最小编辑距离：如果s1[i - 1]等于s2[j - 1]，则dp[i][j] = dp[i - 1][j - 1](两字符串该字符无需修改)，否则dp[i][j] = min(dp[i][j - 1] + ord(s2[j - 1]), dp[i - 1][j] + ord(s...

Posted by Jeza Chen on April 18, 2024

LeetCode 2007 - 从双倍数组中还原数组

Flash 此文章属于Flash闪念部分的短文

数组题，朴素的想法是遍历数组，对于数字i寻找是否有i // 2或者i * 2，但这样子如果都存在上述两种可能，则无法确定用哪个（如果用i // 2，则可能会存在i // 2 // 2找不到匹配的情况，而这个数是用来匹配i * 2的）。因此，需要使用贪心的办法，从小到大寻找双倍匹配，如果其中有个数无法找到双倍匹配，则直接返回空数组。有两种做法：一种基于哈希表，另一种则基于双指针查找。 ...

Posted by Jeza Chen on April 18, 2024

LeetCode 1017 - 负二进制转换

LeetCode 779 - 第K个语法符号

LeetCode 1146 - 快照数组

LeetCode 2385 - 感染二叉树需要的总时间

LeetCode 1052 - 爱生气的书店老板

LeetCode 39 & 216 & 377 - 组合总和相关问题

LeetCode 725 - 分割链表

LeetCode 713 - 乘积小于K的子数组

LeetCode 712 - 两个字符串的最小ASCII删除和

LeetCode 2007 - 从双倍数组中还原数组

FEATURED TAGS

ABOUT ME

RECOMMENDATIONS

MY REPOS

SSEPy

Searchable Symmetric Encryption

PyQtInspect

MendeleyDesktop For Ubuntu 22.04