初级算法之数组

「爱情、让人受尽委屈。」 2024-03-31 13:14 99阅读 0赞

## 数组 ##

[删除有序数组中的重复项][Link 1]

给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。

由于在某些语言中不能改变数组的长度，所以必须将结果放在数组nums的第一部分。更规范地说，如果在删除重复项之后有 k 个元素，那么 nums 的前 k 个元素应该保存最终结果。

将最终结果插入 nums 的前 k 个位置后返回 k 。

不要使用额外的空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

**思路及代码**

遍历数组的每一个数,如果当前元素和下一个元素不一样,那么就加一.

>     class Solution {
>         public int removeDuplicates(int[] nums) {
>             int index=0;
>             for(int i=0;i<nums.length;i++){
>                 if(nums[i]!=nums[index]){
>                     if(nums[index+1]=nums[i];
>                     index++;
>                 }
>                 return index+1;
>             }
>         }
>     }

[买卖股票的最佳时机][Link 2]

给定一个数组 prices ，它的第 i 个元素 prices\[i\] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

**思路及代码**

默认第一天买是价格最低的时候,最大利润为零.遍历数组,如果当前的价格低于初始的价格,就把当前加个赋值给最低价,否则就判断当前价格减去买入的最低价的差值和最大利润比较.

>     public class Solution {
>         public int maxProfit(int prices[]) {
>             int minprice = Integer.MAX_VALUE;
>             int maxprofit = 0;
>             for (int i = 0; i < prices.length; i++) {
>                 if (prices[i] < minprice) {
>                     minprice = prices[i];
>                 } else if (prices[i] - minprice > maxprofit) {
>                     maxprofit = prices[i] - minprice;
>                 }
>             }
>             return maxprofit;
>         }
>     }

[买卖股票的最佳时机 II][II]

给你一个整数数组 prices ，其中 prices\[i\] 表示某支股票第 i 天的价格。

在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。

返回 你能获得的 最大 利润 。

**思路及代码**

有一个讨巧的方法,只要后面的数字比前面的数字大就把两者的差值加起来

>     class Solution {
>         public int maxProfit(int[] prices) {
>             int ans=0;
>             for(int i=1;i<=prices.length-1;i++){
>                 if(prices[i]>prices[i-1]){
>                     ans+=prices[i]-prices[i-1];
>                 }
>             }
>             return ans;
>         }
>     }
> 
>     class Solution { // 动态规划
>         public int maxProfit(int[] prices) {
>             // [天数][是否持有股票]
>             int[][] dp = new int[prices.length][2];
>     
>             // bad case
>             dp[0][0] = 0;
>             dp[0][1] = -prices[0];
>     
>             for (int i = 1; i < prices.length; i++) {
>                 // dp公式
>                 dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
>                 dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
>             }
>     
>             return dp[prices.length - 1][0];
>         }
>     }

[力扣][Link 3]

给你一个数组，将数组中的元素向右轮转 k个位置，其中 k是非负数。

**思路及代码**

创建一个临时数组,赋值,然后统一对原数组进行取余赋值

>     //方法一  
>     //一次交换
>     class Solution {
>         public void rotate(int nums[], int k) {
>             int length = nums.length;
>             int temp[] = new int[length];
>             //把原数组值放到一个临时数组中，
>             for (int i = 0; i < length; i++) {
>                 temp[i] = nums[i];
>             }
>             //然后在把临时数组的值重新放到原数组，并且往右移动k位
>             for (int i = 0; i < length; i++) {
>                 nums[(i + k) % length] = temp[i];
>             }
>         }
>     }
>     
>     //方法二  
>     //多次交换
>     class Solution {
>     	public void rotate(int[] nums, int k) {
>             int length = nums.length;
>             k %= length;
>             reverse(nums, 0, length - 1);//先反转全部的元素
>             reverse(nums, 0, k - 1);//在反转前k个元素
>             reverse(nums, k, length - 1);//接着反转剩余的
>         }
>     
>         //把数组中从[start，end]之间的元素两两交换,也就是反转
>         public void reverse(int[] nums, int start, int end) {
>             while (start < end) {
>                 int temp = nums[start];
>                 nums[start++] = nums[end];
>                 nums[end--] = temp;
>             }
>         }
>     }

[217. 存在重复元素][217.]

给你一个整数数组 nums 。如果任一值在数组中出现 **至少两次** ，返回 true ；如果数组中每个元素互不相同，返回 false 。

>     class Solution {
>         public boolean containsDuplicate(int[] nums) {
>             Arrays.sort(nums);
>             int n = nums.length;
>             for (int i = 0; i < n - 1; i++) {
>                 if (nums[i] == nums[i + 1]) {
>                     return true;
>                 }
>             }
>             return false;
>         }
>     }
>     
>     
>     
>     //set去重
>     public boolean containsDuplicate(int[] nums) {
>             Set<Integer> res = new HashSet<Integer>();
>             for(int i:nums)
>                 res.add(i);
>             return res.size()<nums.length?true:false;
>         }

[219. 存在重复元素 II][219. _ II]

给你一个整数数组 nums 和一个整数 k ，判断数组中是否存在两个 不同的索引 i 和 j ，满足 nums\[i\] == nums\[j\] 且 abs(i - j) <= k 。如果存在，返回 true ；否则，返回 false

>     class Solution {
>         public boolean containsNearbyDuplicate(int[] nums, int k) {
>             Map<Integer, Integer> map = new HashMap<Integer, Integer>();
>             int length = nums.length;
>             for (int i = 0; i < length; i++) {
>                 int num = nums[i];
>                 if (map.containsKey(num) && i - map.get(num) <= k) {
>                     return true;
>                 }
>                 map.put(num, i);
>             }
>             return false;
>         }
>     }

[220. 存在重复元素 III][220. _ III]

给你一个整数数组 nums 和两个整数 k 和 t 。请你判断是否存在 两个不同下标 i 和 j，使得 abs(nums\[i\] - nums\[j\]) <= t ，同时又满足 abs(i - j) <= k 。

如果存在则返回 true，不存在返回 false。

>     class Solution {
>         public boolean containsNearbyAlmostDuplicate(int[] nums, int indexDiff, int valueDiff) {
>             int len = nums.length;
>             for(int i=len-1;i>0;i--){
>                 int a = i-indexDiff;
>                 // a减少数据进入循环的数量,a表示满足在k范围内的数据
>                 if(a>=0 && i>=indexDiff){
>                     for(int j=i-1;j>=a;j--){
>                     if(Math.abs(nums[i]-nums[j])<=valueDiff){
>                          return true;
>                         }
>                     }
>                 }
>                 // 处理a<0,a小于0,由于i的下标小于indexDiff
>                 else{
>                     for(int j=i-1;j>=0;j--){
>                     if(Math.abs(nums[i]-nums[j])<=valueDiff){
>                          return true;
>                         }
>                     }
>                 }
>             }
>             return false;
>         }
>     }
> 
> [136. 只出现一次的数字][136.]
> 
> 给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。
> 
>     //异或
>     //交换律：a ^ b ^ c <=> a ^ c ^ b
>     
>     //任何数于0异或为任何数 0 ^ n => n
>     
>     //相同的数异或为0: n ^ n => 0
>     class Solution {
>         public int singleNumber(int[] nums) {
>             int len=nums.length;
>             int sum=0;
>             for(int i=0;i<len;i++){
>                 sum=sum^nums[i];
>             }
>             return sum;
>         }
>     }
>     
>     
>     
>     //二分法
>     class Solution {
>         public int singleNonDuplicate(int[] nums) {
>             int l=0,r = nums.length-1,m;
>             while(l<r){
>                 m=l+(r-l)/2;
>                 if(m%2==1){
>                     m--;
>                 }
>                 if(nums[m]==nums[m+1]){
>                     l=m+2;
>                 }else{
>                     r=m;
>                 }
>             }
>             return nums[l];
>         }
>     }
>     
>     //普通
>     class Solution {
>         public int singleNumber(int[] nums) {
>             Arrays.sort(nums);
>             int n=nums.length;
>             for(int i=0;i<n;i+=2){
>                 if(i==n-1)
>                 return nums[n-1];
>                 if(nums[i]!=nums[i+1])
>                 return nums[i];
>             }
>             return -1;
>     
>         }
>     }

[137. 只出现一次的数字 II][137. _ II]

给你一个整数数组 nums ，除某个元素仅出现 **一次** 外，其余每个元素都恰出现 **三次 。**请你找出并返回那个只出现了一次的元素。

>     //1
>     class Solution {
>         public int singleNumber(int[] nums) {
>             int one = 0, two = 0, three;
>             for (int num : nums) {
>                 // two的相应的位等于1，表示该位出现2次
>                 two |= (one & num);
>                 // one的相应的位等于1，表示该位出现1次
>                 one ^= num;
>                 // three的相应的位等于1，表示该位出现3次
>                 three = (one & two);
>                 // 如果相应的位出现3次，则该位重置为0
>                 two &= ~three;
>                 one &= ~three;
>             }
>             return one;
>         }
>     }
>     
>     //2.mpa
>     class Solution {
>         public int singleNumber(int[] nums) {
>     		Map<Integer , Integer> map = new LinkedHashMap<>();
>             for(Integer num : nums){
>                 if(!map.containsKey(num)){
>                     map.put(num, 1);
>                 }else{
>                     map.put(num, map.get(num) + 1);
>                 }
>             }
>             for(Integer key : map.keySet()){
>                 if(map.get(key) == 1){
>                     return key;
>                 }
>             }
>             return 0;
>         }
>     }
>     
>     
>     
>     
>     //3排序后遍历
>     class Solution {
>         public int singleNumber(int[] nums) {
>             // 首先排序
>             Arrays.sort(nums);
>             // 预定义返回变量
>             int ans = -1;
>             // 计算nums长度
>             int len = nums.length;
>             // 如果nums长度为1
>             if (len == 1){
>                 return nums[0];
>             }
>             // 以长度3为间隔，遍历nums
>             for(int i = 0; i< len;){
>                 if (nums[i] != nums[i+2]){
>                     ans = nums[i];
>                     break;
>                 }
>                  i = i+3;
>                  // 如果i 越界
>                  if (i >= len-1){
>                       ans = nums[i];
>                       break;
>                  }
>             }
>         // 返回结果
>         return ans;
>         }
>     }

[260. 只出现一次的数字 III][260. _ III]

给你一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 **任意顺序** 返回答案。

>     //位运算
>     class Solution {
>         public int[] singleNumber(int[] nums) {
>             int xorsum = 0;
>             for (int num : nums) {
>                 xorsum ^= num;
>             }
>             // 防止溢出
>             int lsb = (xorsum == Integer.MIN_VALUE ? xorsum : xorsum & (-xorsum));
>             int type1 = 0, type2 = 0;
>             for (int num : nums) {
>                 if ((num & lsb) != 0) {
>                     type1 ^= num;
>                 } else {
>                     type2 ^= num;
>                 }
>             }
>             return new int[]{type1, type2};
>         }
>     }
>     
>     
>     //map运算
>     class Solution {
>         public int[] singleNumber(int[] nums) {
>             Map<Integer, Integer> freq = new HashMap<Integer, Integer>();
>             for (int num : nums) {
>                 freq.put(num, freq.getOrDefault(num, 0) + 1);
>             }
>             int[] ans = new int[2];
>             int index = 0;
>             for (Map.Entry<Integer, Integer> entry : freq.entrySet()) {
>                 if (entry.getValue() == 1) {
>                     ans[index++] = entry.getKey();
>                 }
>             }
>             return ans;
>         }
>     }
>     
>     
>     
>     class Solution {
>         public int[] singleNumber(int[] nums) {
>             Map<Integer , Integer> map = new LinkedHashMap<>();
>             int[] res=new int[2];
>             for(Integer num : nums){
>                 if(!map.containsKey(num)){
>                     map.put(num, 1);
>                 }else{
>                     map.put(num, map.get(num) + 1);
>                 }
>             }
>             int i=0;
>             for(Integer key : map.keySet()){
>                 if(map.get(key) == 1){
>                     res[i++]=key;
>                 }
>             }
>             return res;
>             
>         }
>     }

[349. 两个数组的交集][349.]

给定两个数组 nums1 和 nums2 ，返回 *它们的交集* 。输出结果中的每个元素一定是 **唯一** 的。我们可以 **不考虑输出结果的顺序**

>     class Solution {
>         public int[] intersection(int[] nums1, int[] nums2) {
>          
>             if (nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0) {
>                 return new int[0];
>             }
>             Set<Integer> set1 = new HashSet<>();
>             Set<Integer> resSet = new HashSet<>();
>             //遍历数组1
>             for (int i : nums1) {
>                 set1.add(i);
>             }
>             //遍历数组2的过程中判断哈希表中是否存在该元素
>             for (int i : nums2) {
>                 if (set1.contains(i)) {
>                     resSet.add(i);
>                 }
>             }
>             int[] resArr = new int[resSet.size()];
>             int index = 0;
>             //将结果几何转为数组
>             for (int i : resSet) {
>                 resArr[index++] = i;
>             }
>             return resArr;
>         }
>     }
>     
>     
>     
>     
>     
>     
>     class Solution {
>         public int[] intersection(int[] nums1, int[] nums2) {
>             Arrays.sort(nums1);
>             Arrays.sort(nums2);
>             int length1 = nums1.length, length2 = nums2.length;
>             int[] intersection = new int[length1 + length2];
>             int index = 0, index1 = 0, index2 = 0;
>             while (index1 < length1 && index2 < length2) {
>                 int num1 = nums1[index1], num2 = nums2[index2];
>                 if (num1 == num2) {
>                     // 保证加入元素的唯一性
>                     if (index == 0 || num1 != intersection[index - 1]) {
>                         intersection[index++] = num1;
>                     }
>                     index1++;
>                     index2++;
>                 } else if (num1 < num2) {
>                     index1++;
>                 } else {
>                     index2++;
>                 }
>             }
>             return Arrays.copyOfRange(intersection, 0, index);
>         }
>     }

[350. 两个数组的交集 II][350. _ II]

给你两个整数数组 nums1 和 nums2 ，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。

>     class Solution {
>         public int[] intersect(int[] nums1, int[] nums2) {
>       // 使用Map集合
>             Map<Integer, Integer> map = new HashMap<>();
>             // 记录nums1中每个数出现的次数
>             for(int num : nums1){
>                 Integer value = map.get(num) == null ? 1 : map.get(num) + 1;
>                 map.put(num, value);
>             }
>             // 存放交集结果
>             List<Integer> list = new ArrayList<>();
>             for(int num : nums2){
>                 // 查询map中是否包含该数，如果是，表示是交集
>                 Integer value = map.get(num);
>                 if(value != null && value != 0){
>                     list.add(num);
>                     // 将map中对应数字出现的次数-1
>                     map.put(num, value-1);
>                 }
>             }
>             int[] result = new int[list.size()];
>             int i = 0;
>             for(Integer num : list){
>                 result[i] = num;
>                 i++;
>             }
>             return result;
>         }
>     }

[66. 加一][66.]  
给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一。

最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。

**你可以假设除了整数 0 之外，这个整数不会以零开头**

分析题意:

无非就是一个首位非零的数组,转换成数字加一,现在考虑的情况有两种

*   *  加一不进位 比如123
     *  加一进位但是数组不需要扩容 比如789
     *  加一进位数字需要扩容 比如999

>     class Solution {
>         public int[] plusOne(int[] digits) {
>             //倒着获取数组,先加1,然后和10取余,如果需要不需要进一直接跳出循环,结束程序
>             for (int i = digits.length - 1; i >= 0; i--) {
>                 digits[i]++;
>                 digits[i] = digits[i] % 10;
>                 if (digits[i] != 0) return digits;
>             }
>             digits = new int[digits.length + 1];
>             digits[0] = 1;
>             return digits;
>         }
>     }

[283. 移动零][283.]

**给定一个数组** **nums****，编写一个函数将所有** **0** **移动到数组的末尾，同时保持非零元素的相对顺序。**

**思路:**

**定义一个指针,开始遍历该数组,如果遇到不为零的就把该值赋给当前数组,同时把指针+1,直到遍历完整个数组,最后从该指针开始遍历直到结束,依次赋值0**

>     class Solution {
>         public void moveZeroes(int[] nums) {
>            if (nums == null || nums.length <= 1) {
>                 return;
>             }
>             int index=0;
>             for(int i=0;i<nums.length;i++){
>                 if(nums[i]!=0){
>                     nums[index]=nums[i];
>                     index++;
>                 }
>             }
>             // int index=0;
>             // for(int i=0;i<nums.length;i++){
>             //     if(nums[i]!=0){
>             //         nums[index]=nums[i];
>             //         index++;
>     
>             //     }
>                 
>             // }
>             for(int i=index;i<nums.length;i++){
>                 nums[i]=0;
>             }
>     
>         }
>     }

[1. 两数之和][1.]

**给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。**

**你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。**

**思路:**

**使用map建立数组和下表的哈希值,通过判断差值是否存在来判断,如果存在就直接赋值,不存在的话就把其存进map里面**

>     class Solution {
>         public int[] twoSum(int[] nums, int target) {
>         int[] res = new int[2];
>         if(nums == null || nums.length == 0){
>             return res;
>         }
>         Map<Integer, Integer> map = new HashMap<>();
>         for(int i = 0; i < nums.length; i++){
>             int temp = target - nums[i];
>             if(map.containsKey(temp)){
>                 res[1] = i;
>                 res[0] = map.get(temp);
>             }
>             map.put(nums[i], i);
>         }
>         return res;
>         }
>     }

[36. 有效的数独][36.]

**请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。**

**数字 1-9 在每一行只能出现一次。**

**数字 1-9 在每一列只能出现一次。**

**数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次**

>     class Solution {
>         public boolean isValidSudoku(char[][] board) {
>             // 记录某行，某位数字是否已经被摆放
>             boolean[][] row = new boolean[9][9];
>             // 记录某列，某位数字是否已经被摆放
>             boolean[][] col = new boolean[9][9];
>             // 记录某 3x3 宫格内，某位数字是否已经被摆放
>             boolean[][] block = new boolean[9][9];
>     
>             for (int i = 0; i < 9; i++) {
>                 for (int j = 0; j < 9; j++) {
>                     if (board[i][j] != '.') {
>                         int num = board[i][j] - '1';
>                         int blockIndex = i / 3 * 3 + j / 3;
>                         if (row[i][num] || col[j][num] || block[blockIndex][num]) {
>                             return false;
>                         } else {
>                             row[i][num] = true;
>                             col[j][num] = true;
>                             block[blockIndex][num] = true;
>                         }
>                     }
>                 }
>             }
>             return true;
>         }
>     }

[48. 旋转图像][48.]

**给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。**

**你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。**

思路:

旋转90度可以先转置,然后进行对称操作

>     class Solution {
>         public void rotate(int[][] matrix) {
>     
>             //先转置
>             for(int i=0;i<matrix.length;i++){
>                 for(int j=0;j<i;j++){
>                     int tem=matrix[j][i];
>                     matrix[j][i]=matrix[i][j];
>                     matrix[i][j]=tem;
>                     
>                 }
>             }
>             //在对称
>             for(int i=0;i<matrix.length;i++){
>                 for(int j=0;j<matrix.length/2;j++){
>                     int tem=matrix[i][matrix.length-1-j];
>                     matrix[i][matrix.length-1-j]=matrix[i][j];
>                     matrix[i][j]=tem;
>                     
>                     
>                 }
>             }
>         }
>     }

[Link 1]: https://leetcode.cn/problems/remove-duplicates-from-sorted-array/
[Link 2]: https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/
[II]: https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/
[Link 3]: https://leetcode.cn/leetbook/read/top-interview-questions-easy/x2skh7/
[217.]: https://leetcode.cn/problems/contains-duplicate/
[219. _ II]: https://leetcode.cn/problems/contains-duplicate-ii/
[220. _ III]: https://leetcode.cn/problems/contains-duplicate-iii/
[136.]: https://leetcode.cn/problems/single-number/
[137. _ II]: https://leetcode.cn/problems/single-number-ii/
[260. _ III]: https://leetcode.cn/problems/single-number-iii/
[349.]: https://leetcode.cn/problems/intersection-of-two-arrays/
[350. _ II]: https://leetcode.cn/problems/intersection-of-two-arrays-ii/
[66.]: https://leetcode.cn/problems/plus-one/
[283.]: https://leetcode.cn/problems/move-zeroes/
[1.]: https://leetcode.cn/problems/two-sum/
[36.]: https://leetcode.cn/problems/valid-sudoku/
[48.]: https://leetcode.cn/problems/rotate-image/