服务器之家

服务器之家 > 正文

C++实现LeetCode数组练习题

时间:2021-12-16 13:40     来源/作者:caiyec

1、存在重复元素

排序数组,之后遍历是否有重复的元素

?
1
2
3
4
5
6
7
8
9
public boolean containsDuplicate(int[] nums) {
        Arrays.sort(nums);
        for(int i=1;i<nums.length;i++){
            if(nums[i-1]==nums[i]){
                return true;
            }
        }
        return false;
    }

不排序,利用set去重,判断长度

?
1
2
3
4
5
6
7
8
9
10
public boolean containsDuplicate(int[] nums) {
        HashSet <Integer> set=new HashSet<>();
        for(int i=0;i<nums.length;i++){
            set.add(nums[i]);
        }
        if(set.size()==nums.length){
            return false;
        }
        return true;
    }

2、最大子序和

这道题最经典的思路就是动态规划,取当前数组值和当前数组值加上前一个数组值中取最大值

?
1
2
3
4
5
6
7
8
public int maxSubArray(int[] nums) {
       int res=nums[0];
       for(int i=1;i<nums.length;i++){
           nums[i]=Math.max(nums[i]+nums[i-1],nums[i]);
           res=Math.max(nums[i],res);
       }
       return res;
   }

还有一种就是记录前i项子序列和小于0就重新赋值为下一个

?
1
2
3
4
5
6
7
8
9
10
11
12
13
public int maxSubArray(int[] nums) {
       int count=nums[0];
       int res=nums[0];
       for(int i=1;i<nums.length;i++){
           if(count<=0){
               count=nums[i];
           }else{
               count+=nums[i];
           }
           res=Math.max(res,count);
       }
       return res;
   }

3、两数之和

利用map,来存储数组值和当前位置,来判断

?
1
2
3
4
5
6
7
8
9
10
11
12
13
public int[] twoSum(int[] nums, int target) {
       HashMap<Integer,Integer> map=new HashMap<>();
       for(int i=0;i<nums.length;i++){
           map.put(nums[i],i);
       }
       for(int i=0;i<nums.length;i++){
           int num=target-nums[i];
           if(map.containsKey(num)&&i!=map.get(num)){
               return new int[]{i,map.get(num)};
           }
       }
       return null;
   }

4、合并两个有序数组

定义变量,遍历比较

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public void merge(int[] nums1, int m, int[] nums2, int n) {
     int i=m-1;
     int j=n-1;
     int k=m+n-1;
     while(i>=0&&j>=0){
         if(nums1[i]>nums2[j]){
             nums1[k--]=nums1[i--];
         }else{
             nums1[k--]=nums2[j--];
         }
     }
     while(j>=0){//即nums2元素还没放完
     nums1[k--]=nums2[j--];
       }
    }

5、两个数组的交集II

1.排序,定义指针来判断

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public int[] intersect(int[] nums1, int[] nums2) {
       Arrays.sort(nums1);
       Arrays.sort(nums2);
       int left=0;
       int right=0;
       List<Integer> list=new ArrayList<>();
       while(left<nums1.length&&right<nums2.length){
           if(nums1[left]==nums2[right]){
               list.add(nums1[left]);
               left++;
               right++;
           }else if(nums1[left]<nums2[right]){
               left++;
           }else{
               right++;
           }
       }
       int []arr=new int[list.size()];
       for(int i=0;i<list.size();i++){
           arr[i]=list.get(i);
       }
       return arr;
   }

6、买卖股票的最佳时机

股票问题就是保存数组中最小值,之后用当前数组值减去最小值保留最大的,如果max是负数,就返回0

?
1
2
3
4
5
6
7
8
9
10
11
12
public int maxProfit(int[] prices) {
   int max=Integer.MIN_VALUE;
   int min=prices[0];
   for(int i=1;i<prices.length;i++){
        max=Math.max(max,prices[i]-min);
        min=Math.min(prices[i],min);
   }
   if(max<0){
       return 0;
   }
   return max;
   }

7、杨辉三角

判断特殊情况,第一列和i=j列都是1,其他的都上面的值加上面左边的值,定义二维数组进行帮助

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public List<List<Integer>> generate(int numRows) {
      List<List<Integer>> list=new ArrayList<>();
       int [][]array=new int[numRows][numRows];
       for(int i=0;i<numRows;i++){
           List<Integer> res=new ArrayList<>();
           for(int j=0;j<=i;j++){
               if(j==0||i==j){
                   array[i][j]=1;
               }else{
                   array[i][j]=array[i-1][j-1]+array[i-1][j];
               }
               res.add(array[i][j]);
           }
           list.add(res);
       }
       return list;
   }

8、重塑矩阵

找到其规律进行赋值即可

?
1
2
3
4
5
6
7
8
9
10
11
12
public int[][] matrixReshape(int[][] mat, int r, int c) {
        int n=mat.length;//行数
        int m=mat[0].length;//列数
        if(m*n!=r*c){
            return mat;
        }
        int [][]arr=new int[r][c];
        for(int i=0;i<r*c;i++){
        arr[i/c][i%c]=mat[i/m][i%m];
        }
       return arr;
    }

9、有效的数独

定义二维数组来判断,将存在的数字置为true,判断是否该位置为true,返回false.

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public boolean isValidSudoku(char[][] board) {
       boolean [][] row=new boolean[9][9];//行数
       boolean [][] col=new boolean[9][9];//列数
       boolean [][] box=new boolean[9][9];//格子内
       for(int i=0;i<9;i++){
           for(int j=0;j<9;j++){
               char ch=board[i][j];
               if(ch=='.') continue;
               int curIndex=ch-'1';//计算在哪个位置
               int boxIndex=i/3*3+j/3;// 计算在哪个格子里面
    if(row[i][curIndex]||col[j][curIndex]||box[boxIndex][curIndex]) return false;
               row[i][curIndex]=true;
               col[j][curIndex]=true;
               box[boxIndex][curIndex]=true;
           }
       }
       return true;
   }

10、矩阵置零

先检查第一行和第一列是否有0,定义boolean 变量标记
再利用第一行和第一列作为标记列,遍历整个数组,将中间元素为0的第一行和第一列置为0,
之后遍历整个数组将第一行和第一列的为0的元素的中间元素置为0,之后判断第一行和第一列是否含0,改为0即可

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class Solution {
    public void setZeroes(int[][] matrix) {
        boolean row=false;//标记第一行
        boolean col=false;//标记第一列
        int m=matrix.length;//行数
        int n=matrix[0].length;//列数
       //检查第一行是否有0 标记
       for(int i=0;i<n;i++){
           if(matrix[0][i]==0){
               row=true;
               break ;
           }
       }
       //检查第一列是否有0 标记
        for(int i=0;i<m;i++){
            if(matrix[i][0]==0){
                col=true;
                break ;
            }
        }
        //遍历中间元素 把第一行和第一列置为0
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                if(matrix[i][j]==0){
                    matrix[i][0]=0;
                    matrix[0][j]=0;
                }
            }
        }
        //根据第一行第一列的结果 把中间元素置为0
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                if(matrix[i][0]==0||matrix[0][j]==0){
                    matrix[i][j]=0;
                }
            }
        }
        //检查第一行是否有最开始为0的
        if(row){
            for(int i=0;i<n;i++){
                matrix[0][i]=0;
            }
        }
        //检查第一列是否有最开始为0的
        if(col){
            for(int i=0;i<m;i++){
                matrix[i][0]=0;
            }
        }
    }
}

总结

本篇文章就到这里了,希望能给你带来帮助,也希望您能够多多关注服务器之家的更多内容!

原文链接:https://blog.csdn.net/weixin_51601437/article/details/119086163

标签:

相关文章

热门资讯

yue是什么意思 网络流行语yue了是什么梗
yue是什么意思 网络流行语yue了是什么梗 2020-10-11
背刺什么意思 网络词语背刺是什么梗
背刺什么意思 网络词语背刺是什么梗 2020-05-22
2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全
2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全 2019-12-26
2021年耽改剧名单 2021要播出的59部耽改剧列表
2021年耽改剧名单 2021要播出的59部耽改剧列表 2021-03-05
苹果12mini价格表官网报价 iPhone12mini全版本价格汇总
苹果12mini价格表官网报价 iPhone12mini全版本价格汇总 2020-11-13
返回顶部