import java.util.Scanner; import java.util.*; public class Main{ public static void main(String[] args){ Scanner in = new Scanner(System.in); int N = in.nextInt(); int[] nums = new int[N]; for(int i =0; i<N; i++){ nums[i] = in.nextInt(); } long[] res = new long[N]; for(int i = 0; i< N ; i++){ ...

动态规划相当于dp[i][j]代表从i到j的最短路径这时候的最短路径 仅仅是初始化的时候 点与点之间的直接相连。每次向其中 增加一个中间节点所有节点指点的dp状态都会随之改变，即每增加一个节点 所有的dp[i][j]都有可能更新但是不论增加的节点的顺序是什么，最终的结果都是一样的即增加 k1,k2 和 增加 k2,k1 最终结果一样 因此一共N个点 依次进行添加其中 每次增加一个点都需要更新整个dp所以是O（n^3） 我们从动态规划的角度考虑，解动态规划题目的重点就是合理的定义状态，划分阶段，我们定义 f[k][i][j] 为经过前k的节点，从i到j所能得到的最短路径，f[k][i][j]可以...

import java.util.Scanner; import java.util.ArrayList; public class Main{ public static void main(String[] args){ //读取数据 Scanner in = new Scanner(System.in); int M = in.nextInt(); ArrayList<Integer> items = new ArrayList<Integer>(); while(in.hasNext()){ items.add(in.nextInt()); } Integer[...

对不起 我直接暴力了 O(n^3) 如果用滑动窗口感觉可以到 O(n^2) import java.util.Scanner; import java.util.ArrayList; public class Main{ public static void main(String[] args){ Scanner in = new Scanner(System.in); ArrayList<Integer> items = new ArrayList<Integer>(); while(in.hasNext()){ items.add(in.nextInt()); }...

首先排序 左右指针这两种情况可以合并array[r] == length || array[r]+array[l] > length array[r]+array[l] <= length  关键 每个最多放两个 因此不用考虑太多 不用考虑 再放第三个 import java.util.ArrayList; import java.util.Collections; import java.util.Comparator; import java.util.Scanner; public class Main{ public static void main(String[] ar...

1.最开始用递归做的答案比解多 不知道有没有大佬知道为什么。可能是递归过程中 对于同一个可能进行了重复计算？ import java.util.Scanner; public class Main{ public static void main(String[] args){ Scanner in = new Scanner(System.in); String mos = in.nextLine(); int res = recur(mos); System.out.println(res); } public static int recur(String mos){ if(mos.eq...

2021年9月14日23:27:35 JZ46 孩子们的游戏(圆圈中最后剩下的数)牛客题目描述有问题 直接看力扣已知f(1) = 0 然后可以递推 public class Solution { public int LastRemaining_Solution(int n, int m) { if(n == 0) return -1; int ans = 0; for(int i =2; i<= n ; i++){ ans = (ans+m) % i; } return ans; } }

2021年9月14日23:04:13数学方法双指针 import java.util.ArrayList; public class Solution { public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) { ArrayList<ArrayList<Integer>> res = new ArrayList<>(); int i= 1, j=2, s = 3; while(i<j){ if(s == sum){ ArrayList<I...

2021年9月14日22:31:52动态规划res代表 i时 的 最大值i为1,2,3 时 不分割 最大值 为1,2,3为什么是 j<= i/2 因为 大于时 重复算了一遍 2,8 -> 8,2 public class Solution { public int cutRope(int n) { if(n<4) return n-1; int[] res = new int [n+1]; res[1] = 1; res[2] = 2; res[3] = 3; for(int i = 4;i<=n;i++){ for(int j = 2;j<= i/2 ;j++)...

2021年9月14日22:17:30状态机 牛逼 class Solution { public int singleNumber(int[] nums) { int ones = 0, twos = 0; for(int num : nums){ ones = ones ^ num & ~twos; twos = twos ^ num & ~ones; } return ones; } } 作者：jyd 链接：https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-ii-lcof/solu...

class Solution { public int[] singleNumbers(int[] nums) { int x = 0, y = 0, n = 0, m = 1; for(int num : nums){ n = n^num; } while( (n & m) == 0) m = m<<1; for(int num: nums){ if( (num & m) ==0) x = x^num; else y = y^num; } return new int[]{x,y}; } }

哈希表统计法： 遍历数组 nums ，用 HashMap 统计各数字的数量，即可找出 众数 。此方法时间和空间复杂度均为 O(N)O(N) 。数组排序法： 将数组 nums 排序，数组中点的元素 一定为众数。摩尔投票法： 核心理念为 票数正负抵消 。此方法时间和空间复杂度分别为 O(N)O(N) 和 O(1)O(1) ，为本题的最佳解法。 1. import java.util.*; public class Solution { public int MoreThanHalfNum_Solution(int [] array) { int x = array[0]; int votes = ...

2021年9月14日21:20:25 /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { //如果pq都在左子树 那么返回左子树返回的值 if( recur(r...

2021年9月14日21:06:53递归 public class Solution { public double Power(double base, int exponent) { if(exponent == 0) return 1; else if(exponent>0) return base * Power(base,exponent-1); else return 1/base*Power(base,exponent+1); } }快速幂 k神  class Solution { public double myPow(double x, int n) { if(x ==...