菜鸡15 - 个人主页动态 - 牛客网

2022-03-27 12:19

门头沟学院 Java

最长公共子序列(二)

public String LCS (String s1, String s2) { // write code here int m=s1.length(); int n=s2.length(); String[][] dp=new String[m+1][n+1]; for (int i=0;i<=m;i++){ dp[i][0]=""; } for (int i=0;i<=n;i++){ dp[0][i]=""; } for (int i=1;i<=m;i++){ for (int j=1;j<=n;j++){ if(s1.charAt(i-1)==s2.char...

0 点赞评论收藏

分享

2022-03-27 11:50

门头沟学院 Java

最小花费爬楼梯

step 1：可以用一个数组记录每次爬到第i阶楼梯的最小花费，然后每增加一级台阶就转移一次状态，最终得到结果。 step 2：（初始状态） 因为可以直接从第0级或是第1级台阶开始，因此这两级的花费都直接为0. step 3：（状态转移） 每次到一个台阶，只有两种情况，要么是它前一级台阶向上一步，要么是它前两级的台阶向上两步，因为在前面的台阶花费我们都得到了，因此每次更新最小值即可，转移方程为：dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])。 public int minCostClimbingStairs (int[]...

0 点赞评论收藏

分享

2022-03-27 09:44

门头沟学院 Java

斐波那契数列

public int Fibonacci(int n) { if(n==1||n==0) return n; else return Fibonacci(n-1)+Fibonacci(n-2); }

0 点赞评论收藏

分享

2022-03-26 21:58

门头沟学院 Java

矩阵最长递增路径

深搜+dp即可。  private int[][] dirs=new int[][]{{-1,0},{1,0},{0,-1},{0,1}}; private int m,n; public int solve (int[][] matrix) { // write code here if(matrix.length==0||matrix[0].length==0) return 0; m=matrix.length; n=matrix[0].length; int res=0; int[][] dp=new int[m+1][n+1]; for (int i=0;i<m;i++){ f...

0 点赞评论收藏

分享

2022-03-26 21:07

门头沟学院 Java

字符串的排列

与重复数字写法基本相同。  public ArrayList<String> Permutation(String str) { ArrayList<String> list=new ArrayList<String>(); if(str==null||str.length()==0) return list; char[] strnum=str.toCharArray(); boolean[] vis=new boolean[str.length()]; Arrays.fill(vis,false); StringBuilder sr=new String...

0 点赞评论收藏

分享

2022-03-26 20:10

门头沟学院 Java

深度优先搜索即可。  public ArrayList<String> generateParenthesis (int n) { // write code here ArrayList<String> list=new ArrayList<String>(); String sr=""; dfs(list,0,0,sr,0,n); return list; } public void dfs(ArrayList<String> list,int l,int r,String sr,int k,int n){ if(k==n*2) list.a...

0 点赞评论收藏

分享

2022-03-26 20:09

门头沟学院 Java

矩阵中多处聚集着1，要想统计1聚集的堆数而不重复统计，那我们可以考虑每次找到一堆相邻的1，就将其全部改成0，而将所有相邻的1改成0的步骤又可以使用深度优先搜索（dfs），因此具体做法如下： step 1：优先判断空矩阵等情况。 step 2：从上到下从左到右遍历矩阵每一个位置的元素，如果该元素值为1，统计岛屿数量。 step 3：使用dfs将遍历矩阵遇到的1以及相邻的1全部置为0。 至于dfs具体怎么操作，我们接着看。当我们遇到矩阵的某个元素为1时，首先将其置为了0，然后查看与它相邻的上下左右四个方向，如果这四个方向相邻元素为1，则进入该元素，进入该元素之后我们发现又回到了刚刚的子问题，又是把...

0 点赞评论收藏

分享

2022-03-26 18:23

门头沟学院 Java

在牛客打卡9天，今天学习：刷题 5 道/代码提交 29 次

每日监督打卡

0 点赞评论收藏

分享

2022-03-26 17:24

门头沟学院 Java

有重复项数字的全排列

因为交换位置可能会出现重复交换的情况，出现的结果需要去重，因此不便于使用交换位置的方法。 step 1：我们就使用临时变量去组装一个排列的情况：每当我们选取一个数组元素以后，就确定了其位置，相当于对数组中剩下的元素进行全排列添加在该元素后面，给剩余部分进行全排列就是一个子问题，因此可以使用递归。 终止条件：临时数组中选取了n个元素，已经形成了一种排列情况了，可以将其加入输出数组中。 返回值：每一层给上一层返回的就是本层级在临时数组中添加的元素，递归到末尾的时候就能添加全部元素。 本级任务：每一级都需要选择一个元素加入到临时数组末尾（遍历数组选择）。首先已经加入的元素不能再次加入了，因此我们需要...

0 点赞评论收藏

分享

2022-03-26 15:41

门头沟学院 Java

没有重复项数字的全排列

使用一个list,对数组进行排序。 在函数中首先就是终止条件判断，之后用一个for数组进行遍历，交换，递归调用，在回溯即可。 public void swap(ArrayList<Integer> list,int i,int index){ int temp=list.get(i); list.set(i,list.get(index)); list.set(index,temp); } public void recure(ArrayList<ArrayList<Integer>> lists,ArrayList<Integer> list,...

0 点赞评论收藏

分享

2022-03-26 14:39

已编辑

门头沟学院 Java

step 1：排除边界特殊情况。 step 2：既然三元组内部要求非降序排列，那我们先得把这个无序的数组搞有序了，使用sort函数优先对其排序。 step 3：得到有序数组后，遍历该数组，对于每个遍历到的元素假设它是三元组中最小的一个，那么另外两个一定在后面。 step 4：需要三个数相加为0，则另外两个数相加应该为上述第一个数的相反数，我们可以利用双指针在剩余的子数组中找有没有这样的数对。双指针指向剩余子数组的首尾，如果二者相加为目标值，那么可以记录，而且二者中间的数字相加可能还会有。 step 5：如果二者相加大于目标值，说明右指针太大了，那就将其左移缩小，相反如果二者相加小于目标值，说明...

0 点赞评论收藏

分享

2022-03-26 10:53

已编辑

门头沟学院 Java

缺失的第一个正整数

Hashmap好东西啊  public int minNumberDisappeared (int[] nums) { // write code here if(nums==null||nums.length==0){ return -1; } HashMap<Integer,Integer> hashmap = new HashMap<Integer,Integer>(); for(int i=0;i<nums.length;i++){ hashmap.put(nums[i],1); } for(int i=1;i<=nums.length;i++){ ...

0 点赞评论收藏

分享

2022-03-25 20:32

门头沟学院 Java

在牛客打卡8天，今天学习：刷题 8 道/代码提交 40 次

每日监督打卡

0 点赞评论收藏

分享

2022-03-25 19:44

门头沟学院 Java

数组中出现次数超过一半的数字

依旧使用Hashmap  public int MoreThanHalfNum_Solution(int [] array) { Map<Integer,Integer> map=new HashMap<Integer,Integer>(); for (int i=0;i<array.length;i++){ if(!map.containsKey(array[i])){ map.put(array[i],1); }else { map.put(array[i],map.get(array[i])+1); if(map.get(array[i])>array...

0 点赞评论收藏

分享

2022-03-25 19:19

门头沟学院 Java

使用Hashmap即可  public int[] twoSum (int[] numbers, int target) { Map<Integer,Integer> map=new HashMap<Integer,Integer>(); for (int i=0;i<numbers.length;i++){ if(map.containsKey(target-numbers[i])){ return new int[]{map.get(target-numbers[i])+1,i+1}; }else { map.put(numbers[i],i); } } re...

0 点赞评论收藏

分享

创作者周榜

更多

关注他的用户也关注了：

牛客网
牛客网在线编程
牛客网题解
牛客企业服务