1.删除排序数组的重复项
题目：
解题思路：
代码：
public int removeDuplicates(int[] nums) { //当数组长度为0时，直接返回零即可 if (nums.length == 0) { return 0; } //如果数组长度大于0，则返回的数组长度至少为1，记录数先保存所存入的第一个元素 int record = nums[0]; int num = 1; //直接从数组的第二个元素开始判断 for (int i = 1; i < nums.length; i++) { //如果所遍历到的新元素不等于记录数所保存的值，说明出现的是新元素，则更新记录数，并将该数存储到所给数组前面，num即当前找到的第几个不重复的数 if (nums[i] != record) { nums[num]=nums[i]; num++; record=nums[i]; } } return num; }
//官方做法 public int removeDuplicates(int[] nums) { int n = nums.length; if (n == 0) { return 0; } //slow用于记录当前找到的不重复数的数量，当数组长度大于0时，最起码有一个或以上的不重复的数 int fast = 1, slow = 1; while (fast < n) { //找到不重复的数，存储到数组的第slow个元素中 if (nums[fast] != nums[fast - 1]) { nums[slow] = nums[fast]; ++slow; } ++fast; } return slow; }
2.买卖股票的最佳时机II
题目：
解题思路：允许多次买卖，意味着所有的差价都可以赚到，所以题目就相当于求解可以转到的最大总差价
代码：
public class Solution { public int maxProfit(int[] prices) { if(prices.length==1){ return 0; } int reslut = 0; int i = 0; int j = 1; while (j<prices.length){ int p1 = prices[i]; int p2 = prices[j]; if(p2>=p1){ reslut += (p2-p1); } i++; j++; } return reslut; } }
class Solution { public int maxProfit(int[] prices) { int sum=0; //无论数组长度为0还是1，都无法赚钱 if(prices.length<=1){ return 0; } for(int i=1;i<prices.length;i++){ if(prices[i]>prices[i-1]){ sum+=prices[i]-prices[i-1]; } } return sum; } }
3.旋转数组
解题思路：由于旋转数组具有周期性，所以可以采用取余法获取旋转次数，而后进行模拟，这样可以大量减少模拟次数
代码：
public voidpublic void rotate(int[] nums, int k) { int length = nums.length; k = k%length; if(k!=0){ int firstIndex = k; int[] arr = nums.clone(); for (int i = 0; i < arr.length ; i++) { if(firstIndex>=nums.length){ firstIndex = 0; } nums[firstIndex] = arr[i]; firstIndex++; } } }
4.存在重复元素
代码：
/** * 解题思路：我们知道set集合中的元素是不能有重复的，在添加的时候如果有重复的，会把之前的值给覆盖，并且返回false。 * 我们遍历数组中的所有值，一个个添加到集合set中，在添加的时候如果返回false，就表示有重复的，直接返回true。 */ public class Solution { public boolean containsDuplicate(int[] nums) { Set<Integer> set = new HashSet<>(); for (int num : nums) { //因为集合set中不能有重复的元素，如果有重复的 //元素添加，就会添加失败 if (!set.add(num)) return true; } return false; } }
5.只出现一次的数字
代码：
/** * 解题思路：位运算解决 * 这题说的是只有一个数出现了一次，其他数字都出现了2次，让我们求这个只出现一次的数字。这题使用位运算是最容易解决的，关于位运算有下面几个规律 * 1^1=0; * 1^0=1; * 0^1=1; * 0^0=0; * 也就说0和1异或的时候相同的异或结果为0，不同的异或结果为1，根据上面的规律我们得到 * a^a=0；自己和自己异或等于0 * a^0=a；任何数字和0异或还等于他自己 * a^b^c=a^c^b；异或运算具有交换律 * 有了这3个规律，这题就很容易解了，我们只需要把所有的数字都异或一遍，最终的结果就是我们要求的那个数字。来看下代码 */ public class Solution { public int singleNumber(int[] nums) { int reduce = 0; for (int num : nums) { reduce = reduce ^ num; } return reduce; } }
6.两个数组的交集 II
代码：
public int[] intersect(int[] nums1, int[] nums2) { HashMap<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < nums1.length; i++) { if (!map.containsKey(nums1[i])) { map.put(nums1[i], 1); } else { map.replace(nums1[i], map.get(nums1[i]) + 1); } //或者使用以下方式 //map.put(nums1[i], map.getOrDefault(nums1[i], 0) + 1); } List<Integer> numList = new ArrayList<>(); for (int num2 : nums2) { //当Map集合中存在这个key时，就使用这个key值,(若是数值型可以在此基础上进行运算) //如果没有就使用默认值defaultValue,即所设置的0 if (map.getOrDefault(num2,0)>0){ numList.add(num2); map.put(num2, map.get(num2) - 1); } } int[] arr = new int[numList.size()]; for (int i = 0; i < numList.size(); i++) { arr[i]=numList.get(i); } return arr; }
7.加一
代码：
public int[] plusOne(int[] digits) { //用来记录一个位数是否要执行加1操作，比如个位数是9，则十位数需要执行加一操作 int count = 1; for (int i = digits.length - 1; i >= 0; i--) { //大于9，下一位数还需要加一 if (digits[i] + count > 9) { digits[i] = 0; count = 1; } else { //小于等于9，下一位数无须再加一，count=0 digits[i] = digits[i] + count; count = 0; } } //当最后count==1时，说明数组长度不够，如999>1000 if (count == 1) { int[] arr = new int[digits.length + 1]; //只有首位是1 arr[0] = 1; return arr; } else { return digits; } }
8.移动零
代码：
public void moveZeroes(int[] nums) { int length = nums.length; if (length <= 1) { return; } int fast = 0; int slow = 0; while (fast < length) { //不为零地数往前移动 if (nums[fast] != 0) { nums[slow] = nums[fast]; slow++; } fast++; } //后面的数置为0 while (slow<length){ nums[slow++]=0; } }
9.两数之和
代码：
//暴力搜索 public int[] twoSum(int[] nums, int target) { int[] answer=new int[2]; int length=nums.length; for(int i=0;i<length-1;i++){ for(int j=i+1;j<length;j++){ if(nums[i]+nums[j]==target){ answer[0]=i; answer[1]=j; return answer; } } } return answer; }
//优化之后的方法 public int[] twoSum(int[] nums, int target) { //存放元素及其index HashMap<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < nums.length; i++) { if (map.getOrDefault(target - nums[i], -1) > -1) { return new int[]{map.get(target - nums[i]), i}; } map.put(nums[i],i); } return null; }
总结
提示：这里对文章进行总结：
数组是数据结构的入门，虽然看似简单，但也存在很多操作技巧，感兴趣的同学可以上初级算法 - LeetBook - 力扣（LeetCode）全球极客挚爱的技术成长平台 (leetcode-cn.com)进行进一步的学习。
