阿伟很威猛 - 个人主页动态

2024-07-22 21:59

方法：倒置矩阵 通过以下三个图发现，顺时针旋转90度的矩阵按行翻转后和原矩阵是转置关系即关于主对角线对称，所以为了得到旋转90度后的结果，可以先将原矩阵做对角线对称，再做行对称即可。 import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param mat int整型二维数组 * @param n int整型 * @return int整型二维数组 */ public int[][] rotateMatrix (int[][] mat, int n) { int...

0 点赞评论收藏

2024-07-22 17:56

太原理工大学 Java

题解 | #旋转数组#

方法：翻转代平移 数组的循环移动的结果可以由三次翻转得到，第一次整个翻转实现目标的左右分离，只是为倒序，所以第二次和第三次是为了使之为正序，第二次是前m个数，即从0到m-1，第二次是后n-m个数，即从m到n-1的位置。其中，翻转函数挨个从两边向中间左右交换得到的，实现如下： import java.util.*; public class Solution { public void swap(int[] nums,int a,int b){ int temp = nums[a]; nums[a] = nums[b]; nums[b] = temp; } public void reverse...

0 点赞评论收藏

2024-07-19 20:21

太原理工大学 Java

题解 | #矩阵最长递增路径#

方法：深度优先搜索+动态规划 由于不知道以哪个位置作为起点能得到最长递增路径长度，所以需要遍历每个位置，找出每个位置为起点的最长路径长度，最后比较就可以得到整个矩阵的最大递增的长度了。而每个起点的下一位置可以是上下左右四个方向，又需要挨个遍历，选好一个点后又成了子问题，所以采用深度优先搜索方法，并且设置一个动态规划数组dp来记录每个位置的最大长度。步骤：1、排除空矩阵情况。2、创建dp数组，遍历每个位置，通过调用深度优先搜索算法得到当前最大长度，维护最大长度。3、由于需要遍历四个方向，所以可以设置一个数组来表示方向移动情况。4、对于每个起点，使用dfs查找最长的递增路径：只要下一个位置比当前的...

0 点赞评论收藏

2024-07-18 22:46

太原理工大学 Java

题解 | #括号生成#

方法：递归+回溯 n对括号的生成就是n个左括号和n个右括号组成的合法排列，在使用了一个左括号后，还剩n-1个左括号和n个右括号进入子问题递归。但是要保证序列合法，使用的右括号数不能大于左括号，因此需要每次都检查使用的括号数量。具体做法：step 1：将空串与左右括号各自使用了0个送入递归。step 2：若是左右括号都使用了n个，此时就是一种结果，添加后返回。step 3：若是左括号数没有到达n个，可以考虑增加左括号进入递归，或者右括号数没有到达n个且左括号的使用次数多于右括号就可以增加右括号进入递归。 import java.util.*; public class Solution { pu...

0 点赞评论收藏

2024-07-18 22:14

太原理工大学 Java

题解 | #字符串的排列#

方法：递归+回溯 和前面有重复项数字的全排列方法一样，即使这里是字符串但是排序后还是方便将相同的字母放在一块便于判断去重。其他都和前面一样，就是排序需要将字符串转为字符数组，还有字符串不能直接增删所以采用StringBuffer作为临时数组，可以增删字符。 import java.util.*; public class Solution { public void dfs(ArrayList<String> res,char[] str,StringBuffer temp,boolean[] vis){ if(temp.length()==str.length){ res.add...

0 点赞评论收藏

2024-07-17 18:56

太原理工大学 Java

题解 | #岛屿数量#

方法一：dfs深度优先遍历 题中岛屿是相互连接的1组成的，而要判断岛屿个数就需要挨个遍历，为防止多个1重复判断，就要把与当前1相邻的所有1都设为0，在判断某个方向是否为1时，又要再往下判断其相邻的情况，在遍历完所有相邻的情况后，再回溯，因此用到深度遍历递归调用的方法。步骤：首先，判断矩阵是否为空。然后，遍历矩阵，判断是否为1，是则计数加一，再调用dfs函数。dfs函数中，先将i，j位置设为0，再判断相邻的位置是否为1，是则递归调用dfs。 import java.util.*; public class Solution { public void dfs(char[][] grid,int ...

0 点赞评论收藏

2024-07-17 12:30

太原理工大学 Java

题解 | #有重复项数字的全排列#

方法：递归+回溯 因为有重复的元素，所以需要去重，前面用到的交换的方法不适用了。这里我们采用一个临时数组记录当前添加的结果，用一个标记数组判断哪些元素已经加入，再每次添加时都需要判断是否和前一个元素相等，相等则不添加。步骤：step 1：先对数组按照字典序排序，获取第一个排列情况。step 2：准备一个数组暂存递归过程中组装的排列情况。使用额外的visited数组用于记录哪些位置的数字被加入了。step 3：每次递归先判断，若临时数组长度到达原数组长度就是一种排列情况。step 4：从头遍历数组，获取数字加入：首先根据vis数组，已经加入的元素不能再次加入了；同时，如果当前的元素num[i]与...

0 点赞评论收藏

2024-07-15 18:47

已编辑

太原理工大学 Java

题解 | #主持人调度（二）#

方法一：贪心思想->排序+遍历比较 利用贪心的思想，当上个活动和下个活动之间没有时间交集则不需要新增主持人，因此，要对有交集的主持人做判断，需增加多少主持人。步骤：1、将所有活动的开始时间和结束时间取出并分别排序。2、遍历，比较本次活动的开始时间和上个活动的结束时间的大小，若本次活动开始时间晚则可以延用上个活动的主持人，无需新增主持人活动结束的数组下标后移一个，相反则需要新增主持人。3、最后返回主持人个数即可。 import java.util.*; public class Solution { /** * 计算成功举办活动需要多少名主持人 * @param n int整型 有n个活动...

0 点赞评论收藏

2024-07-09 11:26

太原理工大学 Java

题解 | #没有重复项数字的全排列#

方法一：递归+回溯 全排列就是要交换数组中元素位置所能得到的全部解，题目要求按字典序从小到大排列，则排序后的数组是字典序最小的，此后就保持前面的元素不变交换后面的元素，这个时候就用到了递归。递归终止条件是：遍历到最后一个位置，则添加当前顺序到结果数列。本级递归任务是：向后遍历，交换当前index位置与本次循环下标，然后递归。 只用递归不够，应该加上回溯，使回到上一个子问题，使考虑到在此问题的基础上的所有情况。综上，步骤如下：1、数组排序，得到字典序最小的情况2、交换位置的值，向下递归3、交换，回溯，进入下一分支4、数组结尾，添加结果，返回继续遍历，直到所有情况遍历结束 import java....

0 点赞评论收藏

2024-07-09 09:27

已编辑

太原理工大学 Java

题解 | #数组中只出现一次的两个数字#

方法一：哈希表1、利用哈希表进行统计数字出现的频率2、再次遍历，找到只出现一次的数字，加入创建的ArrayList数组中3、要求非降序输出，则先比较二者的大小后输出，注意要求返回的是int【】数组，要创建此数组将得到的值作为其元素 import java.util.*; public class Solution { public int[] FindNumsAppearOnce (int[] nums) { HashMap<Integer,Integer> mp = new HashMap<Integer,Integer>(); //遍历数组，统计频率 for(int...

0 点赞评论收藏

2024-07-08 20:14

太原理工大学 Java

题解 | #数组中出现次数超过一半的数字#

方法：哈希表 哈希表是一个按键值对存储的数据结构，其中键key唯一，用其可以找到唯一的值value，访问时间是O（1），一般用于计数统计频率和判断某个元素是否出现过的问题。 本题就是典型的统计频率的问题，通过哈希表记录每个元素出现的次数，当某个元素的出现次数超过一半就返回。步骤：1、创建哈希表，key为数组的元素，value为出现的次数。2、遍历一次数组，每次先判断该数是否出现过，若没出现过就将出现次数设为1，若出现过就将查询到的次数加一存入。3、判断当前数字出现次数是否大于数组一半的长度，是则返回该数，否则继续步骤2的遍历。4、若最后遍历完东都没找到，返回0哈希表的常用方法：1、mp.set...

0 点赞评论收藏

2024-06-16 15:42

太原理工大学 Java

题解 | #表达式求值#

方法：栈+递归 利用栈存储数字和部分计算结果，用递归解决括号内的计算，递归出口是右括号，递归主体是遍历括号内进行计算，返回值是其结果。减法可以看作是 加上一个负数，所以就转化为都是加的问题了。具体步骤：1、建立一个递归函数用于计算表达式，类型为一个数组列表，参数为字符串和下标。2、函数内先声明一个栈和符号标识符默认为加号。3、遇到数字字符则将连续的数字字符都转化为数字。4、遇到左括号，则递归解决子问题，返回为一个数组列表，里面存储的是计算的结果和子问题解决后的下标位置。5、判断符号，加号则数字入栈，减号则数字的相反数入栈，乘号则将数字与栈顶相乘再入栈。6、数字归零，方便下次遇见数字字符好计算，...

0 点赞评论收藏

2024-06-15 17:37

太原理工大学 Java

题解 | #数据流中的中位数#

import java.util.*; public class Solution { //较大值构成小顶堆 PriorityQueue<Integer> max = new PriorityQueue<>((o1,o2)->o1.compareTo(o2)); //较小值构成大顶堆 PriorityQueue<Integer> min = new PriorityQueue<>((o1,o2)->o2.compareTo(o1)); public void Insert(Integer num) { min.offer(num); ...

0 点赞评论收藏

2024-06-15 15:46

太原理工大学 Java

题解 | #寻找第K大#

import java.util.*; public class Solution { public int findKth (int[] a, int n, int K) { //小顶堆 PriorityQueue<Integer> q = new PriorityQueue<>((o1,o2)->o1.compareTo(o2)); for(int i=0;i<K;++i){ q.offer(a[i]); } for(int i=K;i<n;++i){ if(q.peek()<a[i]){ q.poll(); q.offer(a[i]); }...

0 点赞评论收藏

2024-06-15 11:34

太原理工大学 Java

题解 | #最小的K个数#

import java.util.*; public class Solution { public ArrayList<Integer> GetLeastNumbers_Solution (int[] input, int k) { if(k==0||input.length==0){ return new ArrayList<Integer>(); } int[] temp = new int[k]; Arrays.sort(input); ArrayList<Integer> res = new ArrayList<Integer>(); ...

0 点赞评论收藏

创作者周榜

关注他的用户也关注了：