dhx_'blog

👉day09 递归/回溯 回溯算法和 DFS 算法⾮常类似，本质上就是⼀种暴⼒穷举算法。 回溯算法和 DFS 算法的细微差别是：回溯算法是在遍历「树枝」，DFS 算法是在遍历「节点」 可以直接把回溯算法当成多层的for循环来理解, 其实就是通过递归来少些多层的for循环 78. 子集 难度中等1765 给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。 解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。 回溯算法思路 本质上子集问题就是遍历这样用一棵回溯树： 12345678910111213141516class Solution { List<List<Integer>> res=new ArrayList<>(); LinkedList<Integer> track=new LinkedList<>();// 记录走过的路径 public List<List<Integer>> subsets(int[] nums) { backTrack(nums,0); return res; } void backTrack(int[]nums,int start){ res.add(new LinkedList<>(track)); for (int i = start; i < nums.length; i++) { track.addLast(nums[i]);// 做选择 backTrack(nums,i+1);// 注意这个地方是i+1, 不要写成start +1 , 如果是start+1 那么就会添加重复的元素 track.removeLast(); // 撤销选择 } }} 90. 子集 II 难度中等912 给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。 解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。 本题是上一题的进阶版本, 需要注意的就是要避免回溯相同 ...

👉 day06 DFS/BFS 200. 岛屿数量 难度中等1854 给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。 岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。 此外，你可以假设该网格的四条边均被水包围。 DFS遍历 , 将走过的1 的网格标记为0 如果可以走通的话 , 维护cnt最后返回即可 每次dfs , 如果遇到了1 的格子, 那么一定是一个新的岛屿 , 因为前面走过的都是0 123456789101112131415161718192021class Solution { public int numIslands(char[][] grid) { int cnt=0; for (int i = 0; i < grid.length; i++) { for (int j = 0; j < grid[0].length; j++) { if(grid[i][j]=='1') cnt++; dfs(grid,i,j); } } return cnt; } void dfs(char[][]grid,int i,int j){ // 标记一下 , 如果遇到了标记过的或者是 0 ,直接return if(i<0||j<0||i>=grid.length|j>=grid[0].length||grid[i][j]=='0') return ; grid[i][j]='0';// 使用! 标记为走过的 dfs(grid,i,j-1); dfs(grid,i,j+1); dfs(grid,i-1,j); dfs(grid,i+1,j); }} 547. 省份数量 难度中等853 有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。 省份 是 ...

4、响应处理 1.响应JSON 假设给前端自动返回json数据，需要引入相关的依赖 123456789101112<dependency> <groupId>org.springframework.boot</groupId> <artifactId>spring-boot-starter-web</artifactId></dependency><!-- web场景自动引入了json场景 --><dependency> <groupId>org.springframework.boot</groupId> <artifactId>spring-boot-starter-json</artifactId> <version>2.3.4.RELEASE</version> <scope>compile</scope></dependency> 控制层代码如下： 1234567891011121314@Controllerpublic class ResponseTestController { @ResponseBody //利用返回值处理器里面的消息转换器进行处理 @GetMapping(value = "/test/person") public Person getPerson(){ Person person = new Person(); person.setAge(28); person.setBirth(new Date()); person.setUserName("zhangsan"); return person; }} spring支持的返回值 123456789101112131415ModelAndViewModelViewResponseEntity ResponseBodyEmitterStreamingResponseBodyHttpEntityHttpHeadersCallableDeferredR ...

ACM赛制java输入输出 主要在leetcode上以核心代码模式刷题如果突然切换到ACM模式会很不习惯, 但是这也是在面试过程中可能会考察的 因此掌握ACM赛制java的基本输入输出操作十分必要 Scanner 和 System.out.print 在最开始会工作得很好，但是在处理更大的输入的时候会降低效率，因此我们会需要使用一些方法来提高 IO 速度。 总计 Java 算法的 ACM 模式需要注意的地方 输入输出模板 使用 Kattio + StringTokenizer 作为输入 最常用的方法之一是使用来自 Kattis 的 Kattio.java 来提高 IO 效率。 这个方法会将 StringTokenizer 与 PrintWriter 包装在一个类中方便使用。 而在具体进行解题的时候（假如赛会/组织方允许）可以直接使用这个模板。下方即为应包含在代码中的 IO 模板，由于 Kattis 的原 Kattio 包含一些并不常用的功能，下方的模板经过了一些调整（原 Kattio 使用 MIT 作为协议）。 而下方代码简单展示了 Kattio 的使用： Kattio.java 123456789101112131415161718192021222324252627class Kattio extends PrintWriter { private BufferedReader r; private StringTokenizer st; // 标准 IO public Kattio() { this(System.in, System.out); } public Kattio(InputStream i, OutputStream o) { super(o); r = new BufferedReader(new InputStreamReader(i)); } // 文件 IO public Kattio(String intput, String output) throws IOException { super(output); r = new BufferedReader(new FileReader(intput)); } ...

👉 day05 滑动窗口 438. 找到字符串中所有字母异位词 难度中等983 给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。 异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。 暴力解法 遍历s然后判断是否是字母异位词 , 最后返回结果集 123456789101112131415161718192021class Solution { public List<Integer> findAnagrams(String s, String p) { List<Integer> res=new ArrayList<>(); for(int x=0,y=p.length();y<=s.length();x++,y++){// sunstring() 左闭右开, 因此y 需要取到s.length() if(isAna(s.substring(x,y).toString().toCharArray(),p.toCharArray())) res.add(x); } return res; } boolean isAna(char[]chars1,char[]chars2){ int []cnt1=new int[26]; int []cnt2=new int[26]; for(char c: chars1){ cnt1[c-'a']++; } for(char c: chars2){ cnt2[c-'a']++; } return Arrays.equals(cnt1,cnt2); }} 暴力解法二 1234567891011121314151617181920212223242526class Solution { public List<Integer> findAnagrams(String s, String p) { if(s. ...

day01 二分 34. 在排序数组中查找元素的第一个和最后一个位置 难度中等1863 给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。 如果数组中不存在目标值 target，返回 [-1, -1]。 你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。 二分, 找到target之后, 向两边继续循环, 查看是否还有target 1234567891011121314151617181920212223242526272829class Solution { public int[] searchRange(int[] nums, int target) { int []res=new int[]{-1,-1}; int l=0,r=nums.length; if(nums.length==0) return res; while(l<r){ int mid=l+(r-l)/2; if(target>nums[mid]){ l=mid+1; }else if(target<nums[mid]){ r=mid; }else { int rightOp=mid; res[0]=mid; res[1]=mid; while(mid>=0&&nums[mid]==nums[res[0]]){ res[0]=mid; mid--; } while(rightOp<nums.length&&nums[rightOp]==nums[res[1]]){ res[1]=rightOp; right ...

date: 2022-8-18 22:18:22 tag: - 算法与数据结构 - leetcode title: 剑指offer java代码实现 （Buidling…） 剑指offer -java代码实现 点击题目名称可以跳转到leetcode练习 由于全部题目保存在一个文件中会导致Markdown非常卡顿 在这里分开了: 剑指offer3~13题 | dhx_'blog (adorabled4.github.io) 剑指offer14~25题 | dhx_'blog (adorabled4.github.io) 剑指offer26~36题 | dhx_'blog (adorabled4.github.io) 剑指offer37~47题 | dhx_'blog (adorabled4.github.io) 剑指offer48~58题 | dhx_'blog (adorabled4.github.io) 剑指offer59~69 | dhx_'blog (adorabled4.github.io)

点击题目名称跳转到 leetcode 页面 [算法基础day 1~4 | dhx_'blog (adorabled4.github.io)](https://adorabled4.github.io/2022/08/22/算法与数据结构/leetcode算法基础勋章/算法基础day 1~4/) [算法基础day 5~8 | dhx_'blog (adorabled4.github.io)](https://adorabled4.github.io/2022/08/22/算法与数据结构/leetcode算法基础勋章/算法基础day 5~8/)

图的概念 相关术语 图是由节点和连接节点之间的边组成的，与连线的长度，节点的位置没有关系。一个图是一个三元组<V(G), E(G), F>，其中V是一个非空的节点集合，E是边集合，F是从边集合E到节点序偶(无序偶或有序偶)集合上的函数。若图中边总是两个节点的关联，则图可简记为G=<G, E>。树可以是空树但图不能是空图。图的结点集不能为空但边集可以为空。 无向图：若图中所有边都是无向边，则图是无向图； 有向图：若所有边都是有向边，则图是有向图； 混合图：若图中既有无向边又有无向边则图为混合图； 多重图：还有平行边的任何一个图称为多重图 简单图：不含平行边和环的图称为简单图 平凡图：仅由一个孤立节点构成的图为平凡图； 零图：仅由孤立节点组成的图为零图； 完全图：图中每一对节点之间都有边相连则称为完全图 补图：给定一个图G，由图中所有节点和所有能使G称为完全图的添加边组成的图称为G相当于完全图的补图，简称G的补图。 子图 ：G=<V,E>，G’=<V’, E’>， 其中V’,E’分别是V，E的子集，则G’是G的子图 ***注意！***图G’ = <V’, E’>是图G=<V,E>的子图，若另一子图G’’=<V’’, E’’>使得E’’=E-E’，且V’‘中仅包含E’‘的边所关联的结点。则称 G’'是子图G’的相对于图G的补图。 生成子图：G的子图包含G的所有结点则该子图为G的生成子图 同构图：图G=<V,E>及G’=<V’,E’>，若存在一一对应关系g，使得v->v’，e=(vi, vj) -> e’ = (g(vi), g(vj))，则称G于G’同构记作G\simeqG’.两个图同构的充要条件是两个图的结点和边分别存在一一对应，且保持关联关系 孤立节点：图中不与任何节点邻接的节点 邻接节点：两个节点之间有边相连则这两个节点称为邻接点 邻接边：连接同一节点的两条边称为邻接边 环(回路)：邻接同一节点的一条边 度：节点连接的边数记为节点的度 出度：指出节点的边数量 入度：指向节点的边数量 定理 节点度数总和等于边数的二倍 度数为奇数的节点必定是偶数 所有节点入度和等于 ...

五、web开发 1、SpringMVC自动配置概览 Spring Boot provides auto-configuration for Spring MVC that works well with most applications.(大多场景我们都无需自定义配置) The auto-configuration adds the following features on top of Spring’s defaults: Inclusion of ContentNegotiatingViewResolver and BeanNameViewResolver beans. 内容协商视图解析器和BeanName视图解析器 Support for serving static resources, including support for WebJars (covered later in this document)). 静态资源（包括webjars） Automatic registration of Converter, GenericConverter, and Formatter beans. 自动注册 Converter，GenericConverter，Formatter Support for HttpMessageConverters (covered later in this document). 支持 HttpMessageConverters （后来我们配合内容协商理解原理） Automatic registration of MessageCodesResolver (covered later in this document). 自动注册 MessageCodesResolver （国际化用） Static index.html support. 静态index.html 页支持 Custom Favicon support (covered later in this document). 自定义 Favicon Automatic use of a ConfigurableWebBindingInitializer bean (covered later in th ...