缺失的第一个正数 问题陈述 给你一个未排序的整数数组，请你找出其中没有出现的最小的正整数。 思路分析 将数组存入一个hashset，然后从i=1开始遍历，判断hashset中是否存在i元素，不存在则返回这个i，若一直到nums.length都存在，则返回nums.length+1。 代码实现 123456789101112131415class Solution{ public int getFirstPositive(int[] nums){ int len=nums.length; Set<Integer> set=new HashSet<>(); for(int c:nums){ set.add(c); } for(int i=1;i<=len;i++){ if(!set.contains(i)){ return i; ...

旋转图像 问题陈述 给定一个 n × n 的二维矩阵表示一个图像。 将图像顺时针旋转 90 度。 示例： 12345678910111213给定 matrix = [ [1,2,3], [4,5,6], [7,8,9]],原地旋转输入矩阵，使其变为:[ [7,4,1], [8,5,2], [9,6,3]] 思路分析 根据n×n矩阵旋转的特性，可知其能由原矩阵进行置换，然后对每行颠倒一下首尾得到。 代码实现 123456789101112131415161718192021class Solution{ public void rotate(int[][] matrix){ int n=matrix.length; //转置(i,j对换) for(int i=0;i<n;i++){ for(int j=i;j<n;j++){ int temp=matrix[i][j]; matrix[i] ...

合并k个排序链表 问题陈述 合并 k 个排序链表，返回合并后的排序链表。 示例： 1234567输入:[ 1->4->5, 1->3->4, 2->6]输出: 1->1->2->3->4->4->5->6 思路分析 两个排序链表合并会吧？然后k个链表就两两合并啦。 代码实现 123456789101112131415161718class Solution{ public ListNode mergeKLinkedlist(ListNode[] lists){ ListNode res=null; for(ListNode list:lists) res=mergeTwoLists(res,list); return res; } public ListNode mergeTwoLists(ListNode l1,ListNode l2){ if(l1==null) ...

两数相除 问题陈述 给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。 返回被除数 dividend 除以除数 divisor 得到的商。 问题解决 1234567891011121314151617181920212223242526272829303132333435/** * 我们可以以100/3为例 * * 2^n是1，2，4，8...2^31这种数，当n为31时，这个数特别大，100/2^n是一个很小的数，肯定是小于3的，所以循环下来， * * 当n=5时，100/32=3, 刚好是大于等于3的，这时我们将100-32*3=4，也就是减去了32个3，接下来我们再处理4，同样手法可以再减去一个3 * * 所以一共是减去了33个3，所以商就是33 * * 这其中得处理一些特殊的数，比如divisor是不能为0的，Integer.MIN_VALUE和Integer.MAX_VALUE * */ public int d ...

搜索旋转排序数组 问题陈述 假设按照升序排序的数组在预先未知的某个点上进行了旋转。 ( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。 搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。 你可以假设数组中不存在重复的元素。 你的算法时间复杂度必须是 O(log n) 级别。 示例： 12输入: nums = [4,5,6,7,0,1,2], target = 6输出: 2 思路分析 根据旋转数组的特性将其分为左右两段，二分查找。 代码实现 12345678910111213141516171819202122232425262728class Solution{ public int search(int[] nums,int target){ int lo=0,hi=nums.length-1,mid=0; while(lo<=hi){ mid=lo+(hi-lo)/2; if(nums[ ...

删除排序数组中的重复项 问题陈述 给定一个排序数组，你需要在 原地 删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。 不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。 思路分析 定义两个指针p，q。p=0,q=1,若nums[q]！=nums[p]，则将nums[q]赋给nums[p+1]。如此，实现了一次遍历，原地删除。原地理解为只操作nums。 代码实现 1234567891011121314class Solution{ public int removeDuplicate(int[] nums){ if(nums==null||nums.length==0) return 0; int p=0,q=1; while(q<nums.length){ if(nums[p]!=nums[q]){ nums[p+1]=nums[q]; p ...

在排序数组中查找元素的第一个和最后一个位置 问题陈述 给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。 你的算法时间复杂度必须是 O(log n) 级别。 如果数组中不存在目标值，返回 [-1, -1]。 示例： 12输入: nums = [5,7,7,8,8,10], target = 8输出: [3,4] 思路分析 定义一个存储该元素起始索引和终止索引两个元素的数组。初始化为{-1，-1}，从头开始遍历到第一个元素，赋给数组的第一个元素。如果第一个匹配索引找不到，直接返回{-1，-1}。如果第一个索引找到，则继续从数组尾开始遍历找到第二个匹配索引，赋给数组第二个元素。 代码实现 1234567891011121314151617181920212223242526272829303132public class SearchRange { public int[] getRange(int[] nums,int target){ int[] range={-1 ...

括号生成 问题陈述 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。 示例： 12345678输入：n = 3输出：[ "((()))", "(()())", "(())()", "()(())", "()()()" ] 思路分析 使用深度优先遍历算法，定义左右括号的数目和当前字符串。如果左括号和右括号数目都为0，返回当前这个res。 否则，左括号还有剩余，拼接一个左括号；右括号还有剩余，拼接一个右括号。 代码实现 12345678910111213141516171819202122class Solution { List<String> res = new ArrayList<>(); public List<String> generateParenthesis(int n) { ...

罗马数字转整数 问题产生 罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。 12345678字符 数值I 1V 5X 10L 50C 100D 500M 1000 通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。 示例： 123输入: "MCMXCIV"输出: 1994解释: M = 1000, CM = 900, XC = 90, IV = 4. 问题分析 按照题目的描述，可以总结如下规则： 罗马数字由 I,V,X,L,C,D,M 构成； 当小值在大值的左边，则减小值，如 IV=5-1=4； 当小值在大值的右边，则加小值，如 VI=5+1=6； 由上可知，右值永远为正，因此最后一位必然为正。 一言蔽之，把一个小值放在大值的 ...

电话号码的字母组合 问题陈述 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。 示例： 12输入："23"输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]. 代码实现 12345678910111213141516171819202122232425262728293031323334353637class Solution{ public List<String> letterCombinations(String digits){ List<String> list=new ArrayList<>(); if(digits==null| ...