打家劫舍Ⅱ 问题陈述 你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。 123输入: [2,3,2]输出: 3解释: 你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。 思路实现 1234567891011121314151617181920212223class Solution { public int rob(int[] nums) { if (nums == null || nums.length == 0) { return 0; } int n = nums.length; if (n == 1) { return nums[0]; ...

打印从1到最大的n位数 问题陈述 输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数 999。 简易解法 12345678910class Solution { public int[] printNumbers(int n) { int len=(int)Math.pow(10,n)-1; int[] nums=new int[len]; for(int i=0;i<len;i++){ nums[i]=i+1; } return nums; }} 考虑大数越界 当 n 较大时，结果会超出 int32 整型的取值范围，超出取值范围的数字无法正常存储。应该存储为字符串进行输出。 123456789101112131415161718192021222324class Solution { StringBuilder res; i ...

平方数之和 问题陈述 题目描述：判断一个非负整数是否为两个整数的平方和。 思路分析 123456789101112131415/*双指针遍历法*设两个整数为a，b，非负整数c。显然a，b在区间[0,sqrt(c)]内，因此可用双指针逼近进行判断*/public boolean getSquareSum(int c){ if(c<0) return false; int i=0,j=(int)Math.sqrt(c); while(i<=j){ int sum=i*i+j*j; if(sum==c) return true; else if(sum>c) j--; else i++; } return false;} 12345678910/*解法二*/public boolean getSquareSum(int c){ for(long a=0;a*a<=c;a++){ double b=M ...

岛屿的最大面积 问题陈述 给定一个包含了一些 0 和 1 的非空二维数组 grid 。 一个 岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在水平或者竖直方向上相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。 找到给定的二维数组中最大的岛屿面积。(如果没有岛屿，则返回面积为 0 。) 问题分析 DFS 12345678910111213141516171819202122232425public class Solution{ public int maxArea(int[][] grid){ int res=0; for(int i=0;i<grid.length;i++){ for(int j=0;j<grid[0].length;j++){ if(grid[i][j]==1){ res=Math.max(res,dfs(grid,i,j) ...

寻找重复数 问题陈述 找出数组中重复的数字。 在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。 常规思路 123456789publiic int findDuplicate(int[] nums){ Arrays.sort(nums); for(int i=0;i<nums.length-1;i++){ if(nums[i]==nums[i+1]){ return nums[i]; } } return -1;} 原地寻找 123456789101112131415161718//以数组元素的值作为索引，若出现相同索引，则必定是重复值。class Solution { public int findRepeatNumber(int[] nums) { int i ...

寻找数组中第k大的元素 问题陈述 寻找数组中第k大的元素。 算法实现 思路一：先排序，然后直接获取。 1234public int getKLargeElements(int[] nums,int k){ Arrays.sort(nums); return nums[nums.length-k];} 思路二：通过维持一个大堆顶，堆顶元素就是第k大的元素。 123456789public int getKLargeElements(int[] nums,int k){ PriorityQueue<Integer> pq=new PriorityQueue<>();//默认实现一个小顶堆。 for(int num:nums){ pq.add(num); if(pq.size()>k){ pq.poll(); } }} 思路三：快速选择排序 1234567891011121314151 ...

完全平方数 问题陈述 给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。 123输入: n = 12输出: 3 解释: 12 = 4 + 4 + 4. 常规思路 12345678910111213141516171819public int numSquares(int n) { return numSquaresHelper(n, new HashMap<Integer, Integer>());}private int numSquaresHelper(int n, HashMap<Integer, Integer> map) { if (map.containsKey(n)) { return map.get(n); } if (n == 0) { return 0; } int count = Integer.MAX_VALUE; ...

字符串的排列 问题陈述 给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。 换句话说，第一个字符串的排列之一是第二个字符串的子串。 示例： 123输入: s1 = "ab" s2 = "eidbaooo"输出: True解释: s2 包含 s1 的排列之一 ("ba"). 算法思路 12345678910111213141516public class Solution{ public boolean checkInclusion(String s1,String s2){ s1=sort(s1); for(int i=0;i<=s2.length()-s1.length();i++){ if(s1.equals(sort(s2.substring(i,i+s1.length())))){ return true; } ...

太平洋大西洋水流 问题陈述 给定一个 m x n 的非负整数矩阵来表示一片大陆上各个单元格的高度。“太平洋”处于大陆的左边界和上边界，而“大西洋”处于大陆的右边界和下边界。 规定水流只能按照上、下、左、右四个方向流动，且只能从高到低或者在同等高度上流动。 请找出那些水流既可以流动到“太平洋”，又能流动到“大西洋”的陆地单元的坐标。 123456789101112131415给定下面的 5x5 矩阵: 太平洋 ~ ~ ~ ~ ~ ~ 1 2 2 3 (5) * ~ 3 2 3 (4) (4) * ~ 2 4 (5) 3 1 * ~ (6) (7) 1 4 5 * ~ (5) 1 1 2 4 * * * * * * 大西洋返回:[[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]] (上图中带括号的单元). 思路分析 思路是从海洋开始逆流 如果 ...

在线笔试输入输出处理 1、简单字符串及数组输入 1、输入字符串 12345678910import java.util.*;public class Main{ public static void main(String[] args){ Scanner in=new Scanner(System.in); //next()方法在读取内容时，会过滤掉有效字符前面的无效字符，对输入有效字符之前遇到的空格键、Tab键或Enter键等结束符，next()方法会自动将其过滤掉；只有在读取到有效字符之后，next()方法才将其后的空格键、Tab键或Enter键等视为结束符；所以next()方法不能得到带空格的字符串。 String str=in.next(); // nextLine()方法字面上有扫描一整行的意思，它的结束符只能是Enter键，即nextLine()方法返回的是Enter键之前没有被读取的所有字符，它是可以得到带空格的字符串的。 String str1=in.nextLine( ...