lushylin的博客

原创 644.奇怪的打印机（困难）

题目：有台奇怪的打印机有以下两个特殊要求：打印机每次只能打印由 同一个字符 组成的序列。 每次可以在任意起始和结束位置打印新字符，并且会覆盖掉原来已有的字符。 给你一个字符串 s，你的任务是计算这个打印机打印它需要的最少打印次数。示例：解题思路：最值问题首先想到动态规划。定义一个dp[i][j]表示打印i到j所有字符需要的最少次数。情况一：如果s.charAt(i)==s.charAt(j)，说明打印i字符时可以顺带打印j字符，反过来说也是一样的。 这种情况不会增加次数。即dp[i][

原创 浅拷贝深拷贝

尚硅谷视频地址：https://www.bilibili.com/video/BV1G4411c7N4?p=53&spm_id_from=pageDriver

原创 工厂模式UML类图（Pizza为例）

简单工厂模式：工厂方法模式：抽象方法模式：

原创 810. 黑板异或游戏

题目：黑板上写着一个非负整数数组 nums[i] 。Alice 和 Bob 轮流从黑板上擦掉一个数字，Alice 先手。如果擦除一个数字后，剩余的所有数字按位异或运算得出的结果等于 0 的话，当前玩家游戏失败。 (另外，如果只剩一个数字，按位异或运算得到它本身；如果无数字剩余，按位异或运算结果为 0。）换种说法就是，轮到某个玩家时，如果当前黑板上所有数字按位异或运算结果等于 0，这个玩家获胜。假设两个玩家每步都使用最优解，当且仅当 Alice 获胜时返回 true。示例：解题思路：

原创 单例模式

设计模式分类设计模式是针对某类问题的通用解决方案。单例模式懒加载就是用到就创建，用不到就不创建-饿汉式静态常量public class SingletonTest01 { public static void main(String[] args) { Singleton instance01 = Singleton.getInstance(); Singleton instance02 = Singleton.getInstance

原创 1035.不相交的线段

题目：在两条独立的水平线上按给定的顺序写下 nums1 和 nums2 中的整数。现在，可以绘制一些连接两个数字 nums1[i] 和 nums2[j] 的直线，这些直线需要同时满足满足：nums1[i] == nums2[j]绘制的直线不与任何其他连线（非水平线）相交。请注意，连线即使在端点也不能相交：每个数字只能属于一条连线。以这种方法绘制线条，并返回可以绘制的最大连线数。解题思路：遇到最大连接数问题首先想到动态规划。【动态规划】定义dp[i][j]表示nums1前i个数与n

原创 692.前K个高频单词

题目：给一非空的单词列表，返回前 k 个出现次数最多的单词。返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率，按字母顺序排序。示例：解题思路：先不考虑复杂度，这个题涉及到字符串排序，首先想到大根堆小根堆以及hashmap。大根堆小根堆还不熟，先考虑hashmap，想法是key,value(String,Integer)，每重复一个加1，先设默认值，用hashmap.getOrDefault(String a,0)来设初始Integer为零。第一步遍历完之后，时间复杂

原创 55.平衡二叉树

题目：输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。示例：解题思路：这个题需要自底向上做遍历，可以直接用递归来做。但是一边要记录树的高度一边又要记录是否满足二叉树条件。这个时候千万不要想着一个函数用来传深度int一个函数用来传是否满足二叉得boolean。最好用int做返回，true的时候返回深度，false的时候返回-1即可。自底向上的方式可以选择后序遍历:左子节点-右子节点-根节点也可以选择：右子节点-

原创 UML类图类的关系

辅助记忆：依赖和关联依赖：包含泛化和实现关联：包含聚合和组合**依赖：**用到了就叫依赖**泛化：**其实就是继承关系**实现：**就是指A类实现B类的意思关联：聚合：组合：

原创 144.二叉树的前序遍历

题目：给你二叉树的根节点 root ，返回它节点值的 前序 遍历。示例：解题思路：凡是涉及到树节点遍历的先考虑队列栈这两类数据结构，建议解题直接用双端队列，可以自由选择进出顺序。本题用队列去遍历每一个节点，遍历顺序为根节点-左节点-右节点。实现逻辑：将当前节点进队列，然后判断左子节点如果不为空就将左子节点进队列，然后一样去判断右子节点。这是循环逻辑，切入点在于要在进入这个循环之前将根节点进入队列中，然后以队列不为空的条件进行迭代。参考：本题可以参考leetcode其他题解Java代

原创 199.二叉树的右视图

题目：给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。示例：解题思路：解法1：层序遍历。将用一个queue去遍历每一层的节点，记住每一层的size，取最后一个值保存到arraylist即可。解法2：深度遍历，以根-右子树-左子树的方式遍历(与先序遍历相反)。同时记录深度，用list保存某一深度的第一个节点。参考：甜姐力扣199题解Java代码//解法1class Solution { public List<Integer

原创 96.不同的二叉搜索树

题目：给你一个整数 n，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树有多少种？返回满足题意的二叉搜索树的种数。解题思路：给出 n，要求利用 1-n 这些数字组成二叉排序树，有多少种不同的树的形态，输出这个个数。这题的解题思路是 DP。dp[n] 代表 1-n 个数能组成多少个不同的二叉排序树，F(i,n) 代表以 i 为根节点，1-n 个数组成的二叉排序树的不同的个数。由于题意，我们可以得到这个等式：dp[n] = F(1,n) + F(2,n) + F(3,

原创 C++链表传址和传引用的区别是什么？（求解）

都可以改变原来的值，但是这样有什么区别吗？

转载 剑指offer35-36 c++ vector操作

//36.摘抄自题解class Solution {public://vector.begin,end是一个左开右闭区间[) vector<Node*> arr; void help(Node* root) { if(root==NULL)return; help(root->left); arr.push_back(root); help(root->right); } ...

转载 C++ push_back和emplace_back

http://c.biancheng.net/view/6826.html

原创 剑指offer30 包含min函数的栈（关于栈的操作）

stack<int> stk;stk.pop; is wrongstk.pop();int res;res=stk.pop(); is wrong ,because pop is no return.stk.empty();stk.size();

原创 剑指offer29 顺时针打印矩阵 vector操作

vector返回类型如果为空返回{}而不是[];vector.size is valid but vector.length is invalid;vector 操作可以声明之后直接push_backexp: vector<int> res;res.push_back(1);

原创 剑指offer21-解耦拓展的一种范例

将所有整型数组的奇数放在偶数前面。拓展--整型数据进行条件排列。

转载 学习记录-C++ operator重载操作符

还不是很懂，先码住https://blog.csdn.net/liitdar/article/details/80654324

原创 剑指offer13 机器人的运动范围/回溯法、递归

剑指offer13. 机器人的运动范围class Solution {public: int movingCount(int m, int n, int k) { if (m<1||n<1||k<0){ return 0; } bool *visited = new bool[m*n]; for(int i=0;i<m*n;i++){ visited[i]=f

转载 C++ 快速排序讲解

C++快速排序算法https://blog.csdn.net/elma_tww/article/details/86164674

原创 C++ 左值/右值/引用/参数传递/模板template/const

左值/右值引用：https://www.cnblogs.com/Bylight/p/10530274.html模板template T：https://blog.csdn.net/biu__biu_biu/article/details/78020620const引用传递https://blog.csdn.net/hnxyxiaomeng/article/details/100516525

转载 vs 解决方案文件格式讲解

https://blog.csdn.net/asbbv/article/details/105693037

原创 值类型/引用类型/值传递/引用传递/

https://www.cnblogs.com/LauSir139/p/11097761.html值传递/引用传递/值类型和引用类型

原创 C++ 数组/整型/指针-剑指offer38页

sizeof用法总结/32位和64位：https://blog.csdn.net/xunfeng13/article/details/51011509

原创 求解问题：关于C++指针变量&、*的疑惑

定义整型变量a，指针变量p。给a赋值，p存储a的地址*&p：输出结果等效于p**&p：输出结果等效于*p，即输出123*&*p：输出结果等效于*p，即输出123(&*p)：输出结果等效于p（&**p，&*&p,&&*p,*&&p）：报错Questions：不能理解&*&，&&*的报错,&*p的成功代码及结果图：...

转载 python的算数运算符

原创 LeetCode python 杨辉三角 递推

给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。在杨辉三角中，每个数是它左上方和右上方的数的和。示例:执行代码class Solution(object): def generate(self, numRows): """ :type numRows: int :rtype: List[List[int]] """ #定义返回数组 rect = [] .

转载 LeetCode-两两交换链表中的节点-递归

LeetCode-两两交换链表中的节点代码如下给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。给定 1->2->3->4, 你应该返回 2->1->4->3.代码如下# Definition for singly-linked list.# class ListNode(object):# def __init__(self, x):# self.val