Lavender-csdn的博客

并查集作用：1、合并两个集合2、判断两个点是否在同一个集合中模板：// 找到父节点public static int find(int x) { if(p[x]!=x) p[x] = find(x); return p[x];}1、547. 省份数量以下为java代码：class Solution { static int[] p; public int findCircleNum(int[][] isConnected) { in

前缀和的基本概念题目：560. 和为 K 的子数组考察S[R]-S[L-1]是否等于k，哈希表的作用可以快速插入一个数、可以快速找到一个数、可以统计数出现的次数。以下为Java代码：class Solution { public int subarraySum(int[] nums, int k) { int result = 0; int sum = 0; //表示前缀和 Map<Integer,Integer> map = new H.

1、49. 字母异位词分组思路：定义一个map，key值为每个排好序的字符串，value为字符串本身，key的类型为String，value的类型为ArrayList<String>。所以以上例子的map为map={ "aet":{"ate","eat","tea"}, "abt":{bat}, "ant":{"nat","tan"}}以下为java代码class Solution { public L...

算法思想：1、在字符串 S 中使用双指针中的左右指针技巧，初始化 left = right = 0，把索引闭区间 [left, right] 称为一个「窗口」。2、先不断地增加 right 指针扩大窗口 [left, right]，直到窗口中的字符串符合要求。3、此时，停止增加 right，转而不断增加 left 指针缩小窗口 [left, right]，直到窗口中的字符串不再符合要求。同时，每次增加 left，都要更新一轮结果。4、重复第 2 和第 3 步，直到 right 到达字符串 S

问题来历据说著名犹太历史学家 Josephus有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从。首先从一个人开始，越过k...

leetcode377. 组合总和 Ⅳ题目描述：给定一个由正整数组成且不存在重复数字的数组，找出和为给定目标正整数的组合的个数。根据前几道组合总和的做题轨迹，直接使用回溯：class Solution { public int count=0; //记录满足组合的个数 public int combinationSum4(int[] nums, int target) { int cursum = 0; backtrack(nums,ta

回溯算法的模板：List<Object> list = new ArrayList<>();public void backtrack(路径，选择列表){ //设置结束条件 if 满足结束条件{ lista.dd(路径); return; } //候选节点的选择 for(int i=start;i<选择列表的长度;i++){ //做选择 是否要将当前节点添加到list中

leetcode674. 最长连续递增序列题目描述：给定一个未经排序的整数数组，找到最长且 连续递增的子序列，并返回该序列的长度。连续递增的子序列 可以由两个下标 l 和 r（l < r）确定，如果对于每个 l <= i < r，都有 nums[i] < nums[i + 1] ，那么子序列 [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] 就是连续递增子序列。class Solution { publ.

首先说明：子串是在原始字符串中连续的，子序列在原始字符串中可连续可不连续leetcode5. 最长回文子串题目描述：给你一个字符串s，找到s中最长的回文子串。此题有两种经典的解法，一种是动态规划，一种是中心扩展法，个人更喜欢中心扩展法，两种方法都放一下代码。中心扩展法以当前字符为中心，向左右两边扩展，寻找以当前字符为中心的回文串，以下是返回最长回文串的长度import java.util.*;/**以下做法是返回长度**/public class Solut...

leetcode 84、柱状图中最大的矩形题目描述：给定n个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。求在该柱状图中，能够勾勒出来的矩形的最大面积。思想：以当前的柱子为中心，向两边扩展，找出界限，计算以当前柱子为中心的矩形面积。class Solution { public int largestRectangleArea(int[] heights) { //三指针法，left，curr，right i..

题目描述：假设链表中每一个节点的值都在 0 - 9之间，那么链表整体就可以代表一个整数。给定两个这种链表，请生成代表两个整数相加值的结果链表。例如：链表 1为 9->3->7，链表 2为 6->3，最后生成新的结果链表为 1->0->0->0。这道题没啥技巧，思路清晰，就是代码有点多。import java.util.*;/* * public class ListNode { * int val; * ListNode ...

题目描述：输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。/** * Definition for binary tree * public class TreeNode { * int val; * TreeNode left; * TreeNode right; *

算法思想：1、在字符串 S 中使用双指针中的左右指针技巧，初始化 left = right = 0，把索引闭区间 [left, right] 称为一个「窗口」。2、先不断地增加 right 指针扩大窗口 [left, right]，直到窗口中的字符串符合要求。3、此时，停止增加 right，转而不断增加 left 指针缩小窗口 [left, right]，直到窗口中的字符串不再符合要求。同时，每次增加 left，都要更新一轮结果。4、重复第 2 和第 3 步，直到 right 到达字符串 S

题目描述：import java.util.*;/* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * public TreeNode(int val) { * this.val = val; * } * } */public class Solution { /** * 代码中的类名、方法名、

题目描述：给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。进阶：你可以实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案吗？个人第一下想法就是先给这个数组排序class Solution { public int firstMissingPositive(int[] nums) { Arrays.sort(nums); boolean flag = false; int index=0;

题目描述编写一个高效的算法来判断m x n矩阵中，是否存在一个目标值。该矩阵具有如下特性：每行中的整数从左到右按升序排列。 每行的第一个整数大于前一行的最后一个整数。class Solution { public boolean searchMatrix(int[][] matrix, int target) { int row=0; int col=matrix[0].length-1; while(row<matrix...

题目描述：给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。你应当 保留 两个分区中每个节点的初始相对位置。/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int va

题目描述：给定一个包含非负整数的mxn网格grid，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。说明：每次只能向下或者向右移动一步。典型的动态规划问题class Solution { public int minPathSum(int[][] grid) { //动态规划 int m = grid.length; //行数 int n = grid[0].length; //列数 ...

题目描述：给你一个正整数n，生成一个包含1到n^2所有元素，且元素按顺时针顺序螺旋排列的n x n正方形矩阵matrix。class Solution { public int[][] generateMatrix(int n) { int row = n; //行数 int col = n; //列数 int[][] matrix = new int[row][col]; int count=1; ...

题目描述：给定一个排序数组，你需要在 原地 删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。class Solution { public int removeDuplicates(int[] nums) { int len = nums.length-1; int i=0; while(i<len){ .

题目：shopee的办公室非常大，小虾同学的位置坐落在右上角，而大门却在左下角，可以把所有位置抽象为一个网格（门口的坐标为0，0），小虾同学很聪明，每次只向上，或者向右走，因为这样最容易接近目的地，但是小虾同学不想让自己的boss们看到自己经常在他们面前出没，或者迟到被发现。他决定研究一下如果他不通过boss们的位置，他可以有多少种走法？这道题典型的动态规划。import java.util.ArrayList;import java.util.List;import java..

1. Leetcode-206:反转链表这道题的经典做法：断链+头插法，以下为java实现的代码：/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */class Solution { public ListNode reverseList

对刷题过程中的牵扯到树的层次遍历的代码总结。1. 基础版，树的层次遍历java代码的实现(利用的是队列)：/** * Definition for binary tree with next pointer. * public class TreeLinkNode { * int val; * TreeLinkNode left, right, next; * ...

输入一个正整数数组，把数组里面所有的数字拼接起来排成一个数，打印能拼接出所有数字中最小的一个，例如输入数组{3,32,321}，则打印出这三个数字能排成的最小数字为321323。这个就是排列组合算法中的基础版。以下为上述问题的java代码实现：package niukewang;import java.util.Scanner;public class Minnumber { ...

def check(temp): flag = False #设置一个标记 如果出现掉落的情况 标记设为True drop = 0 pre = temp[1] for i in range(2,len(temp)): if(temp[i]>0): currenttotal = temp[i] ...

N,M = map(int,input().split())total = []dictionary = {}for i in range(N): temp = list(map(int,input().split())) total.append(sum(temp)) dictionary[i+1] =abs(sum(temp[1:]))maxval = 0i...

n = int(input())result = []for i in range(n): temp = str(input()) if("x" in temp): temp = temp.replace("x","*") if("/" in temp): temp = temp.replace("/","//") if(eva...

import java.util.Scanner;public class Linear { static Scanner sc; static long[] a; static String temp; static String[] cmd; static int m,l,r; static long[] k; static long Q=998244353; pub...

问题描述　　目前在一个很大的平面房间里有 n 个无线路由器,每个无线路由器都固定在某个点上。任何两个无线路由器只要距离不超过 r 就能互相建立网络连接。　　除此以外,另有 m 个可以摆放无线路由器的位置。你可以在这些位置中选择至多 k 个增设新的路由器。　　你的目标是使得第 1 个路由器和第 2 个路由器之间的网络连接经过尽量少的中转路由器。请问在最优方案下中转路由器的最少个数是多少?输入...

这个提交上去不是满分，希望各位大佬们给出建议，谢谢了。问题描述　　授权 (authorization) 是各类业务系统不可缺少的组成部分，系统用户通过授权机制获得系统中各个模块的操作权限。　　本题中的授权机制是这样设计的：每位用户具有若干角色，每种角色具有若干权限。例如，用户 david 具有 manager 角色，manager 角色有 crm:2 权限，则用户 david 具有 cr...

import java.util.Scanner;/** 问题描述　　消除类游戏是深受大众欢迎的一种游戏，游戏在一个包含有n行m列的游戏棋盘上进行，棋盘的每一行每一列的方格上放着一个有颜色的棋子，当一行或一列上有连续三个或更多的相同颜色的棋子时，这些棋子都被消除。当有多处可以被消除时，这些地方的棋子将同时被消除。　　现在给你一个n行m列的棋盘，棋盘中的每一个方格上有一个棋子，请给出经...

问题描述　　给定一个年份y和一个整数d，问这一年的第d天是几月几日？　　注意闰年的2月有29天。满足下面条件之一的是闰年：　　1） 年份是4的整数倍，而且不是100的整数倍；　　2） 年份是400的整数倍。输入格式　　输入的第一行包含一个整数y，表示年份，年份在1900到2015之间（包含1900和2015）。　　输入的第二行包含一个整数d，d在1至365之间。输出格式　　输出...

import java.util.ArrayList;import java.util.Iterator;import java.util.List;import java.util.Scanner;/** * 问题描述　　给出一个字符串和多行文字，在这些文字中找到字符串出现的那些行。你的程序还需支持大小写敏感选项：当选项打开时，表示同一个字母的大写和小写看作不同的字符；当选项关闭...

import java.util.Scanner;/** * 问题描述　　数轴上有一条长度为L（L为偶数)的线段，左端点在原点，右端点在坐标L处。有n个不计体积的小球在线段上，开始时所有的小球都处在偶数坐标上，速度方向向右，速度大小为1单位长度每秒。　　当小球到达线段的端点（左端点或右端点）的时候，会立即向相反的方向移动，速度大小仍然为原来大小。　　当两个小球撞到一起的时候，两个小球会...

import java.util.Scanner;/** * 问题描述　　旋转是图像处理的基本操作，在这个问题中，你需要将一个图像逆时针旋转90度。　　计算机中的图像表示可以用一个矩阵来表示，为了旋转一个图像，只需要将对应的矩阵旋转即可。 输入格式　　输入的第一行包含两个整数n, m，分别表示图像矩阵的行数和列数。　　接下来n行每行包含m个整数，表示输入的图像。 输出格式　　...

改了几次，经过测试100分。问题描述　　有一个学校的老师共用N个教室，按照规定，所有的钥匙都必须放在公共钥匙盒里，老师不能带钥匙回家。每次老师上课前，都从公共钥匙盒里找到自己上课的教室的钥匙去开门，上完课后，再将钥匙放回到钥匙盒中。　　钥匙盒一共有N个挂钩，从左到右排成一排，用来挂N个教室的钥匙。一串钥匙没有固定的悬挂位置，但钥匙上有标识，所以老师们不会弄混钥匙。　　每次取钥匙的时候，...

import java.util.Scanner;/** * 问题描述　　小明带着N元钱去买酱油。酱油10块钱一瓶，商家进行促销，每买3瓶送1瓶，或者每买5瓶送2瓶。请问小明最多可以得到多少瓶酱油。 输入格式　　输入的第一行包含一个整数N，表示小明可用于买酱油的钱数。N是10的整数倍，N不超过300。 输出格式　　输出一个整数，表示小明最多可以得到多少瓶酱油。 样例输入 40...

import java.util.ArrayList;import java.util.Collections;import java.util.Comparator;import java.util.List;import java.util.Scanner;/** * 问题描述　　给定n个整数，请统计出每个整数出现的次数，按出现次数从多到少的顺序输出。 输入格式　　...

import java.util.Scanner;/** * 问题描述　　给定n个整数表示一个商店连续n天的销售量。如果某天之前销售量在增长，而后一天销售量减少，则称这一天为折点，反过来如果之前销售量减少而后一天销售量增长，也称这一天为折点。其他的天都不是折点。如下图中，第3天和第6天是折点。　　给定n个整数a1, a2, …, an表示销售量，请计算出这些天总共有多少个折点。　...

import java.util.Scanner;/** * 问题描述　　给定一个十进制整数n，输出n的各位数字之和。 输入格式　　输入一个整数n。 输出格式　　输出一个整数，表示答案。 样例输入 20151220 样例输出 13 样例说明　　20151220的各位数字之和为2+0+1+5+1+2+2+0=13。 评测用例规模与约定　　所有评测用例满足：0 ≤ n ...