C++实现LeetCode数组练习题

1、存在重复元素

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

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去重,判断长度

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、最大子序和

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

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就重新赋值为下一个

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,来存储数组值和当前位置,来判断

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、合并两个有序数组

定义变量,遍历比较

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.排序,定义指针来判断

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

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,其他的都上面的值加上面左边的值,定义二维数组进行帮助

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、重塑矩阵

找到其规律进行赋值即可

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.

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即可

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;

}

}

}

}

总结

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

以上是 C++实现LeetCode数组练习题 的全部内容, 来源链接: www.h5w3.com/246820.html

回到顶部