代码随想录 Day16
16 May 2023
513. Find Bottom Left Tree Value
思路：
- 递归: 用中序遍历确保左节点最先visit，再记录最大深度
- BFS
// 递归
class Solution {
public:
int depth = INT_MIN;
int res = 0;
void traverse(TreeNode* root, int d) {
if (!root) {
return;
}
traverse(root->left, d + 1);
if (!root->left && !root->right) {
if (d > depth) {
res = root->val;
depth = d;
}
return;
}
traverse(root->right, d + 1);
}
int findBottomLeftValue(TreeNode* root) {
traverse(root, 0);
return res;
}
};
- 如果需要搜索整棵二叉树且不用处理递归返回值，递归函数就不要返回值。（113.路径总和ii）
- 如果需要搜索整棵二叉树且需要处理递归返回值，递归函数就需要返回值。 （236. 二叉树的最近公共祖先中介绍）
- 如果要搜索其中一条符合条件的路径，那么递归一定需要返回值，因为遇到符合条件的路径了就要及时返回。
106. Construct Binary Tree from Inorder and Postorder Traversal
class Solution {
public:
TreeNode* helper(int postend, int instart, int inend, vector<int>&in, vector<int>&post) {
if (postend < 0 || instart > inend) {
return NULL;
}
TreeNode* root = new TreeNode(post[postend]);
int idx = 0;
for (int i = instart; i <= inend; i++) {
if (in[i] == post[postend]) {
idx = i;
break;
}
}
root->left = helper(postend - (inend - idx + 1), instart, idx - 1, in, post);
root->right = helper(postend - 1, idx + 1, inend, in, post);
return root;
}
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
return helper(postorder.size() - 1, 0, inorder.size() - 1, inorder, postorder);
}
};
105. Construct Binary Tree from Preorder and Inorder Traversal
class Solution {
public:
TreeNode* helper(int prestart, int instart, int inend, vector<int>&pre, vector<int>&in) {
if (prestart >= pre.size() || instart > inend) {
return NULL;
}
TreeNode* root = new TreeNode(pre[prestart]);
int idx = 0;
for (int i = instart; i <= inend; i++) {
if (in[i] == pre[prestart]) {
idx = i;
break;
}
}
root->left = helper(prestart + 1, instart, idx - 1, pre, in);
root->right = helper(prestart + idx - instart + 1, idx + 1, inend, pre, in);
return root;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
return helper(0, 0, inorder.size() - 1, preorder, inorder);
}
};
前序和后序不能唯一确定一棵二叉树，因为没有中序遍历无法确定左右部分，无法分割。
训练营 Day1
15 May 2023
题目：给你一个升序数组nums和一个目标值target，返回目标值target在数组nums中的下标，如果不存在则返回-1
思路：二分查找
class Solution {
public:
int search(vector<int>& nums, int target) {
int l = 0;
int r = nums.size(
while (l <= r) {
int mid = l + (r - l) / 2;
if (nums[mid] < target) {
l = mid + 1;
} else if (nums[mid] > target) {
r = mid - 1;
} else {
return mid;
}
}
return -1;
}
};
题目：给你一个数组nums和一个值val，要求你把数组中值为val的元素全部删掉，而且不允许你使用额外的数组来辅助解决这题，返回移除val后数组的长度
思路：快慢指针，快指针遍历数组，慢指针遍历当前不重复的下标。不重复的数一定小于等于原数组，所以不会写到快指针 还没有遍历的数
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int i = 0;
int curr = 0;
int cnt = 0;
for (int i = 0; i < nums.size(); i++) {
if (nums[i] != val) {
nums[curr] = nums[i];
curr++;
cnt++;
}
}
return cnt;
}
};
代码随想录 Day15
15 May 2023
求高度（该节点到叶子节点），后序遍历
class Solution {
public:
int getHeight(TreeNode* root) {
if(!root) {
return 0;
}
int l = getHeight(root->left);
if (l == -1) {
return -1;
}
int r = getHeight(root->right);
if (r == -1) {
return -1;
}
return abs(l - r) <= 1 ? 1 + max(l, r) : -1;
}
bool isBalanced(TreeNode* root) {
return getHeight(root) == -1 ? false : true;
}
};
void traversal(TreeNode* cur, string path, vector
迭代: 如果是模拟前中后序遍历就用栈，如果是适合层序遍历就用队列，当然还是其他情况，那么就是 先用队列试试行不行，不行就用栈
代码随想录 Day14
14 May 2023
104. Maximum Depth of Binary Tree
前序求的是深度，后序求的是高度。 二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数或者节点数（取决于深度从0开始还是从1开始） 二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数后者节点数（取决于高度从0开始还是从1开始）
class solution {
public:
int getdepth(treenode* node) {
if (node == NULL) return 0;
int leftdepth = getdepth(node->left); // 左
int rightdepth = getdepth(node->right); // 右
int depth = 1 + max(leftdepth, rightdepth); // 中
return depth;
}
int maxdepth(treenode* root) {
return getdepth(root);
}
};
class solution {
public:
int result;
void getdepth(treenode* node, int depth) {
result = depth > result ? depth : result; // 中
if (node->left == NULL && node->right == NULL) return ;
if (node->left) { // 左
getdepth(node->left, depth + 1);
}
if (node->right) { // 右
getdepth(node->right, depth + 1);
}
return ;
}
int maxdepth(treenode* root) {
result = 0;
if (root == 0) return result;
getdepth(root, 1);
return result;
}
};
105.Minimum Depth of Binary Tree
class Solution {
public:
int minDepth(TreeNode* root) {
if (root == NULL) return 0;
if (root->left == NULL && root->right != NULL) {
return 1 + minDepth(root->right);
}
if (root->left != NULL && root->right == NULL) {
return 1 + minDepth(root->left);
}
return 1 + min(minDepth(root->left), minDepth(root->right));
}
};
class Solution {
private:
int result;
void getdepth(TreeNode* node, int depth) {
if (node->left == NULL && node->right == NULL) {
result = min(depth, result);
return;
}
// 中 只不过中没有处理的逻辑
if (node->left) { // 左
getdepth(node->left, depth + 1);
}
if (node->right) { // 右
getdepth(node->right, depth + 1);
}
return ;
}
public:
int minDepth(TreeNode* root) {
if (root == NULL) return 0;
result = INT_MAX;
getdepth(root, 1);
return result;
}
};
222. Count Complete Tree Nodes
class Solution {
public:
int countNodes(TreeNode* root) {
if (root == NULL) return 0;
return 1 + countNodes(root->left) + countNodes(root->right);
}
};
class Solution {
public:
int countNodes(TreeNode* root) {
if (root == nullptr) return 0;
TreeNode* left = root->left;
TreeNode* right = root->right;
int leftDepth = 0, rightDepth = 0; // 这里初始为0是有目的的，为了下面求指数方便
while (left) { // 求左子树深度
left = left->left;
leftDepth++;
}
while (right) { // 求右子树深度
right = right->right;
rightDepth++;
}
if (leftDepth == rightDepth) {
return (2 << leftDepth) - 1; // 注意(2<<1) 相当于2^2，所以leftDepth初始为0
}
return countNodes(root->left) + countNodes(root->right) + 1;
}
};
Spring5 AOP, MVC, IOC (pdai)
07 May 2023
Inversion of Control Container
Dependency Injection
Java without Enterprise JavaBeans (EJBs)
Allow enterprise development without application server
Plain Old Java Objects (POJO)
Unobtrusive
AOP/Proxies
Best Practices
Testability/Maintainability/Scalability/Complexity/Business Focus
WORA: Write Once Run Anywhere
AppConfig @Configuration
@Bean
Setter ingestion/constructor ingestion
Spring Scopes and Autowiring
Scopes:
Singleton: One instantiation, single instance per Spring container @Scope(“singleton”)
Prototype: new bean per request
@Scope(“prototype”)
Valid only in web-aware Spring projects: Request, Session, Global
AOP
连接点(Jointpoint):在哪里干;
切入点(Pointcut): 在哪里于的集合;
通知(Advice)为于什么;
方面/切面(Aspect):于什么(引入什么);
目标对象(Target Object):在AOP中表示为对谁于;
织入(Weaving):怎么实现的;
AOP代理(AOP Proxy):怎么实现的一种典型方式;
前置通知(Before advice):在某连接点之前执行的通知,但这个通知不能阻止连接点之前的执行流程(除非它 抛出一个异常)。
后置通知(After returning advice):在某连接点正常完成后执行的通知:例如,一个方法没有抛出任何异常, 正常返回。
异常通知(After throwing advice):在方法抛出异常退出时执行的通知。
最终通知(After (finally) advice):当某连接点退出的时候执行的通知(不论是正常返回还是异常退出)。
环绕通知(Around Advice):包围一个连接点的通知,如方法调用。这是最强大的一种通知类型。环绕通知可 以在方法调用前后完成自定义的行为。它也会选择是否继续执行连接点或直接返回它自己的返回值或抛出异常来 结束执行。
动态织入的方式是在运行时动态将要增强的代码织入到目标类中,这样往往是通过动态代理技术完成的,如Java JDK的动态代理(Proxy. 底层通过反射实现)或者CGLIB的动态代理(底层通过继承实现), Spring AOP采用的就是基于 运行时增强的代理技术Apectu采用的就是静态织入的方式。Apectu主要采用的是编译期织入,在这个期间使用
Aspect的acj编译器(类似javac)把aspect类编译成class字节码后,在java目标类编译时织入,即先编译aspect类再编 译目标类。
Model, View , Controller
BeanFactory： 工厂模式定义了IOC容器的基本功能规范
ListableBeanFactory、HierarchicalBeanFactory 和AutowireCapableBeanFactory
BeanRegistry： 向IOC容器手工注册 BeanDefinition 对象的方法
BeanDefinition 定义了各种Bean对象及其相互的关系BeanDefinitionReader 这是BeanDefinition的解析器
BeanDefinitionHolder 这是BeanDefination的包装类，用来存储BeanDefinition，name以及aliases等。
ApplicationContext：IOC接口设计和实现
访问资源： 对不同方式的Bean配置（即资源）进行加载。(实现ResourcePatternResolver接口)
国际化: 支持信息源，可以实现国际化。（实现MessageSource接口）
应用事件: 支持应用事件。(实现ApplicationEventPublisher接口)
GenericApplicationContext： 是初始化的时候就创建容器，往后的每次refresh都不会更改
AbstractRefreshableApplicationContext： AbstractRefreshableApplicationContext及子类的每次refresh都是先清除已有(如果不存在就创建)的容器，然后再重新创建；AbstractRefreshableApplicationContext及子类无法做到GenericApplicationContext混合搭配从不同源头获取bean的定义信息
obtainFreshBeanFactory
loadBeanDefinitions
AbstractBeanDefinitionReader读取Bean定义资源
XmlBeanDefinitionReader加载Bean定义资源
DocumentLoader将Bean定义资源转换为Document对象
XmlBeanDefinitionReader解析载入的Bean定义资源文件
DefaultBeanDefinitionDocumentReader对Bean定义的Document对象解析
BeanDefinitionParserDelegate解析Bean定义资源文件生成BeanDefinition
解析过后的BeanDefinition在IoC容器中的注册
DefaultListableBeanFactory向IoC容器注册解析后的BeanDefinition
解析bean的真正name，如果bean是工厂类，name前缀会加&，需要去掉无参单例先从缓存中尝试获取如果bean实例还在创建中，则直接抛出异常如果bean definition 存在于父的bean工厂中，委派给父Bean工厂获取标记这个beanName的实例正在创建确保它的依赖也被初始化真正创建 单例时原型时根据bean的scope创建
第一层缓存（singletonObjects）：单例对象缓存池，已经实例化并且属性赋值，这里的对象是成熟对象；
第二层缓存（earlySingletonObjects）：单例对象缓存池，已经实例化但尚未属性赋值，这里的对象是半成品对象；
第三层缓存（singletonFactories）: 单例工厂的缓存
“A对象setter依赖B对象，B对象setter依赖A对象”，A首先完成了初始化的第一步，而且将本身提早曝光到singletonFactories中，此时进行初始化的第二步，发现本身依赖对象B，此时就尝试去get(B)，发现B尚未被create，因此走create流程，B在初始化第一步的时候发现本身依赖了对象A，因而尝试get(A)，尝试一级缓存singletonObjects(确定没有，由于A还没初始化彻底)，尝试二级缓存earlySingletonObjects（也没有），尝试三级缓存singletonFactories，因为A经过ObjectFactory将本身提早曝光了，因此B可以经过ObjectFactory.getObject拿到A对象(半成品)，B拿到A对象后顺利完成了初始化阶段一、二、三，彻底初始化以后将本身放入到一级缓存singletonObjects中。此时返回A中，A此时能拿到B的对象顺利完成本身的初始化阶段二、三，最终A也完成了初始化，进去了一级缓存singletonObjects中，并且更加幸运的是，因为B拿到了A的对象引用，因此B如今hold住的A对象完成了初始化。
Spring无法解决除单例模式以外的循环依赖（构造器/prototype/多例）
解决方法：
- 使用@Lazy注解，延迟加载
- 使用@DependsOn注解，指定加载先后关系
- 修改文件名称，改变循环依赖类的加载顺序
如果 BeanFactoryPostProcessor 和 Bean 关联, 则调用postProcessBeanFactory方法.(即首先尝试从Bean工厂中获取Bean)
如果 InstantiationAwareBeanPostProcessor 和 Bean 关联，则调用postProcessBeforeInstantiation方法 根据配置情况调用 Bean 构造方法实例化 Bean。
利用依赖注入完成 Bean 中所有属性值的配置注入。
如果 InstantiationAwareBeanPostProcessor 和 Bean 关联，则调用postProcessAfterInstantiation方法和postProcessProperties
调用xxxAware接口 (BeanNameAware/BeanClassLoaderAware/BeanFactoryAware/EnvironmentAware/EmbeddedValueResolverAware/ApplicationContextAware)
如果 Bean 实现了 InitializingBean 接口，则 Spring 将调用 afterPropertiesSet() 方法。(或者有执行@PostConstruct注解的方法)
如果在配置文件中通过init-method属性指定了初始化方法，则调用该初始化方法。
如果 BeanPostProcessor 和 Bean 关联，则 Spring 将调用该接口的初始化方法 postProcessAfterInitialization()。此时，Bean 已经可以被应用系统使用了。
如果在中指定了该 Bean 的作用范围为 scope="singleton"，则将该 Bean 放入 Spring IoC 的缓存池中，将触发 Spring 对该 Bean 的生命周期管理；
如果在中指定了该 Bean 的作用范围为 scope="prototype"，则将该 Bean 交给调用者，调用者管理该 Bean 的生命周期，Spring 不再管理该 Bean。
如果 Bean 实现了 DisposableBean 接口，则 Spring 会调用 **destory()** 方法将 Spring 中的 Bean 销毁；(或者有执行@PreDestroy注解的方法)
如果在配置文件中通过 destory-method 属性指定了 Bean 的销毁方法，则 Spring 将调用该方法对 Bean 进行销毁。
AOP的创建工作是交给AnnotationAwareAspectJAutoProxyCreator来完成
实现了两类接口：BeanFactoryAware属于Bean级生命周期接口方法InstantiationAwareBeanPostProcessor 和BeanPostProcessor 这两个接口实现，一般称它们的实现类为“后处理器”，是容器级生命周期接口方法
核心的初始化方法肯定在postProcessBeforeInstantiation和postProcessAfterInitialization中
处理使用了@Aspect注解的切面类，然后将切面类的所有切面方法根据使用的注解生成对应Advice，并将Advice连同切入点匹配器和切面类等信息一并封装到Advisor的过程。
- 由IOC Bean加载方法栈中找到parseCustomElement方法，找到parse aop:aspectj-autoproxy的handler(org.springframework.aop.config.AopNamespaceHandler)
- AopNamespaceHandler注册了
- AspectJAutoProxyBeanDefinitionParser的parse 方法 通过AspectJAwareAdvisorAutoProxyCreator类去创建
- AspectJAwareAdvisorAutoProxyCreator实现了两类接口，BeanFactoryAware和BeanPostProcessor；根据Bean生命周期方法找到两个核心方法：postProcessBeforeInstantiation和postProcessAfterInitialization
- postProcessBeforeInstantiation：主要是处理使用了@Aspect注解的切面类，然后将切面类的所有切面方法根据使用的注解生成对应Advice，并将Advice连同切入点匹配器和切面类等信息一并封装到Advisor
- postProcessAfterInitialization：主要负责将Advisor注入到合适的位置，创建代理（cglib或jdk)，为后面给代理进行增强实现做准备。
Spring默认在目标类实现接口时是通过JDK代理实现的，只有非接口的是通过Cglib代理实现的。当设置proxy-target-class为true时在目标类不是接口或者代理类时优先使用cglib代理实现。
代理模式(Proxy pattern): 为另一个对象提供一个替身或占位符以控制对这个对象的访问
Cglib是一个强大的、高性能的代码生成包，它广泛被许多AOP框架使用，为他们提供方法的拦截。
JDK代理：
第一步：准备工作，将所有方法包装成ProxyMethod对象，包括Object类中hashCode、equals、toString方法，以及被代理的接口中的方法
第二步：为代理类组装字段，构造函数，方法，static初始化块等
第三步：写入class文件
MVC:
HandlerMapping是映射处理器
HandlerAdpter是处理适配器，用来找到你的Controller中的处理方法
HandlerExceptionResolver是当遇到处理异常时的异常解析器
首先用户发送请求——>DispatcherServlet，前端控制器收到请求后自己不进行处理，而是委托给其他的解析器进行 处理，作为统一访问点，进行全局的流程控制；
DispatcherServlet——>HandlerMapping， HandlerMapping 将会把请求映射为 HandlerExecutionChain 对象（包含一 个Handler 处理器（页面控制器）对象、多个HandlerInterceptor 拦截器）对象，通过这种策略模式，很容易添加新 的映射策略；
DispatcherServlet——>HandlerAdapter，HandlerAdapter 将会把处理器包装为适配器，从而支持多种类型的处理器， 即适配器设计模式的应用，从而很容易支持很多类型的处理器；
HandlerAdapter——>处理器功能处理方法的调用，HandlerAdapter 将会根据适配的结果调用真正的处理器的功能处 理方法，完成功能处理；并返回一个ModelAndView 对象（包含模型数据、逻辑视图名）；
ModelAndView 的逻辑视图名——> ViewResolver，ViewResolver 将把逻辑视图名解析为具体的View，通过这种策 略模式，很容易更换其他视图技术；
View——>渲染，View 会根据传进来的Model 模型数据进行渲染，此处的Model 实际是一个Map 数据结构，因此 很容易支持其他视图技术；
返回控制权给DispatcherServlet，由DispatcherServlet 返回响应给用户，到此一个流程结束。
Spring5 框架, 要点, IOC (pdai)
01 May 2023
Spring
ORM/DAO -> POJO (IOC容器) -> Service -> Controller
- 非侵入式：基于Spring开发的应用中的对象可以不依赖于Spring的API
- 控制反转：IOC——Inversion of Control，指的是将对象的创建权交给 Spring 去创建。使用 Spring之前，对象的创建都是由我们自己在代码中new创建。而使用 Spring 之后。对象的创建都是给了 Spring 框架。
- 依赖注入：DI——Dependency Injection，是指依赖的对象不需要手动调用 setXX 方法去设置，而是通过配置赋值。
- 面向切面编程：Aspect Oriented Programming——AOP容器：Spring是一个容器，因为它包含并且管理应用对象的生命周期组件化：Spring 实现了使用简单的组件配置组合成一个复杂的应用。在 Spring中可以使用XML和Java注解组合这些对象。
- 一站式：在 IOC 和 AOP的基础上可以整合各种企业应用的开源框架和优秀的第三方类库（实际上 Spring 自身也提供了表现层的 SpringMVC 和持久层的 Spring JDBC）
Core Container: beans, core, context (Application Context), SpEL
Data Access/Integration: JDBC/ORM (Object Relational Mapping)/OXM (Object/XML)/JMS (服务消息)/Transaction
Web: web, servlet, websocket, webflux (完全异步且非阻塞), Portlet
AOP, Aspects, Instrumentation (类工具的支持和类加载器的实现), Messaging, JCL (日志框架集成的模块)
Test: Junit, TestNG
/**
* aspect for every methods under service package.
*/
@Around("execution(* tech.pdai.springframework.service.*.*(..))")
public Object businessService(ProceedingJoinPoint pjp) throws Throwable {
// get attribute through annotation
Method method = ((MethodSignature) pjp.getSignature()).getMethod();
System.out.println("execute method: " + method.getName());
// continue to process
return pjp.proceed();
}
@Configuration: These classes consist principally of @Bean-annotated methods that define instantiation, configuration, and initialization logic for objects that are managed by the Spring IoC container.
@Configuration
public class AppConfig {
@Bean
public TransferService transferService() {
return new TransferServiceImpl();
}
}
@Service annotates classes at the service layer. 它将根据用户请求请求@Repository
@Repository annotates classes at the persistence layer, which will act as a database repository
IOC: 用户管理Bean转变为框架管理Bean
DI: 应用程序代码从Ioc Container中获取依赖的Bean，注入到应用程序中
IOC Config：XML, 注解， Java
依赖注入方式：构造方法注入（Construct注入），setter注入，基于注解的注入（接口注入）
@Autowired（自动注入）：Constructor，byType，byName
构造器注入的方式能够保证注入的组件不可变，并且确保需要的依赖不为空
@Target(ElementType.CONSTRUCTOR) #构造函数
@Target(ElementType.METHOD) #方法
@Target(ElementType.PARAMETER) #方法参数
@Target(ElementType.FIELD) #字段、枚举的常量
@Target(ElementType.ANNOTATION_TYPE) #注解
@Resource
@Target(ElementType.TYPE) #接口、类、枚举、注解
@Target(ElementType.FIELD) #字段、枚举的常量
@Target(ElementType.METHOD) #方法
@Inject
@Target(ElementType.CONSTRUCTOR) #构造函数
@Target(ElementType.METHOD) #方法
@Target(ElementType.FIELD) #字段、枚举的常量
- @Autowired、@Inject用法基本一样，不同的是@Inject没有required属性
- @Autowired、@Inject是默认按照类型匹配的，@Resource是按照名称匹配的
- @Autowired如果需要按照名称匹配需要和@Qualifier一起使用，@Inject和@Named一起使用，@Resource则通过name进行指定
并发编程 1, 2 (lianglianglee)
01 May 2023
创建线程方法
public class RunnableThread implements Runnable {
public class ExtendsThread extends Thread {
Callable, 线程池
实现 Runnable 接口比继承 Thread 类实现线程要好
- 实现了 Runnable 与 Thread 类的解耦，Runnable 里只有一个 run() 方法，它定义了需要执行的内容，Thread 类负责线程启动和属性设置等内容。
- 使用继承 Thread 类方式，每次执行一次任务，都需要新建一个独立的线程，执行完任务后线程走到生命周期的尽头被销毁，如果还想执行这个任务，就必须再新建一个继承了 Thread 类的类。 使用实现 Runnable 接口的方式，就可以把任务直接传入线程池，使用一些固定的线程来完成任务，不需要每次新建销毁线程，大大降低了性能开销
- Java 语言不支持双继承，如果我们的类一旦继承了 Thread 类，那么它后续就没有办法再继承其他的类，限制可拓展性
用 interrupt停止线程：请求中断，而不是强制停止，因为这样可以避免数据错乱，也可以让线程有时间结束收尾工作。
Thread.currentThread().isInterrupted()
如果 sleep、wait 等可以让线程进入阻塞的方法使线程休眠了，而处于休眠中的线程被中断，那么线程是可以感受到中断信号的，并且会抛出一个 InterruptedException 异常，同时清除中断信号，将中断标记位设置成 false。
已经被舍弃的 stop()、suspend() 和 resume()，它们由于有很大的安全风险比如死锁风险而被舍弃，而 volatile 这种方法在某些特殊的情况下，比如线程被长时间阻塞的情况，就无法及时感受中断，所以 volatile 是不够全面的停止线程的方法。
英雄算法联盟 Day30
30 April 2023
31. 状态压缩
题目描述：n integers from 1 to n, permutate, either: perm[i] % i == 0 or i % perm[i] == 0
class Solution {
public:
int countArrangement(int n) {
vector<int> f(1 << n);
f[0] = 1;
// 遍历所有可能情况
for (int mask = 1; mask < (1 << n); mask++) {
//被选中的个数
int num = __builtin_popcount(mask);
for (int i = 0; i < n; i++) {
//第i + 1位数被选中 && 可以被放到最高位上
if (mask & (1 << i) && (num % (i + 1) == 0 || (i + 1) % num == 0)) {
// 加上剩余n-1个数的可能排序方式的个数
f[mask] += f[mask ^ (1 << i)];
}
}
}
return f[(1 << n) - 1];
}
};
1255. Maximum Score Words Formed by Letters
题目描述：Given list of words, and list of single letters and score of every character, return maximum score of any valid set of words formed by the letters given. Each letter can only be used once.
思路：统计提供的字母次数 遍历所有可能情况，for (int s = 1; s < (1 « n); s++) { 统计子集中所有字母出现的次数 如果次数都没有超过提供的次数，将当前和与最大和比较，更新最大和
class Solution {
public:
int maxScoreWords(vector<string>& words, vector<char>& letters, vector<int>& score) {
int n = words.size(), res = 0;
vector<int> count(26);
for (auto c : letters) {
count[c - 'a']++;
}
for (int s = 1; s < (1 << n); s++) {
vector<int> wordCount(26); // 统计子集 s 所有单词的字母数目
for (int k = 0; k < n; k++) {
if ((s & (1 << k)) == 0) { // words[k] 不在子集 s 中
continue;
}
for (auto c : words[k]) {
wordCount[c - 'a']++;
}
}
bool ok = true; // 判断子集 s 是否合法
int sum = 0; // 保存子集 s 的得分
for (int i = 0; i < 26; i++) {
sum += score[i] * wordCount[i];
ok = ok && (wordCount[i] <= count[i]);
}
if (ok) {
res = max(res, sum);
}
}
return res;
}
};
30: 拓扑排序
1976. Number of Ways to Arrive at Destination
题目描述：Given integer n, and 2D array roads where roads[i] = [ui, vi, timei], meaning there is a road between ui, and vi, that takes timei to travel, return the number of ways can travel from 0 to n - 1 in the sortest amount of time, return ans % (109 + 1)
思路： 性质：在任意的合法方案中，途径的该路径中的每个点时，都是以最短路径的方式到达的 在跑「拓扑排序」过程中进行 DP，统计方案数
//dijkstra
while (!pq.empty()) {
auto [_, u] = pq.top();
pq.pop();
if (vis[u]) {
continue;
}
vis[u] = 1;
for (auto [v, w]: G[u]) {
if (dist[v] > dist[u] + w) {
dist[v] = dist[u] + w;
f[v] = f[u];
pq.push({dist[v], v});
} else if (dist[v] == dist[u] + w) {
f[v] = (f[u] + f[v]) % (long)(1e9 + 7);
}
}
}
英雄算法联盟 Day29
29 April 2023
29: 分而治之
dp[nums.size() - 1][target]
for (int i = 1; i < nums.size(); i++) {
for (int j = 1; j <= sum; j++) {
if (j - nums[i] >= 0) {
dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i]];
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
31: 状态压缩模版
const int maxn = 12;
const int inf = 100000000;
class Solution {
int n;
int mat[maxn][maxn]; // (1)
int f[maxn][maxn][1<<maxn]; // (2)
public:
void fillGraphMatrix(vector<vector<int>>& graph) { // (3)
memset(mat, 0, sizeof(mat));
for(int i = 0; i < n; ++i) {
for(int j = 0; j < graph[i].size(); ++j) {
mat[i][ graph[i][j] ] = 1;
}
}
}
int dfs(int st, int en, int state) { // (4)
if( !( (1<<st) & state ) ) { // (5)
return inf;
}
if( !( (1<<en) & state ) ) { // (6)
return inf;
}
if(st == en) {
if(state == (1<<st)) {
return 0; // (7)
}
}
int &ret = f[st][en][state];
if(ret != -1) {
return ret; // (8)
}
ret = inf;
for(int i = 0; i < n; ++i) { // (9)
// (st -> ... -> i) U (i -> en)
if(!mat[i][en]) { // (10)
continue;
}
int a = dfs(st, i, state); // (11)
int b = dfs(st, i, state ^ (1<<en)); // (12)
ret = min( ret, min(a, b) + 1 ); // (13)
}
return ret;
}
int shortestPathLength(vector<vector<int>>& graph) {
n = graph.size();
fillGraphMatrix(graph);
int ret = 100000000;
memset(f, -1, sizeof(f));
for(int i = 0; i < n; ++i) {
for(int j = 0; j < n; ++j) {
int &ans = f[i][j][(1<<n) - 1];
ans = dfs(i, j, (1<<n) - 1); // (14)
ret = min(ans, ret);
}
}
return ret;
}
};