首页 > 编程语言 >面试最常见算法3—数组

面试最常见算法3—数组

时间:2024-09-03 18:25:27浏览次数:12  
标签:nums int ++ 面试 算法 数组 length array

1.二维数组螺旋打印

给定一个二维数组 array,请返回「螺旋遍历」该数组的结果。

螺旋遍历:从左上角开始,按照 向右向下向左向上 的顺序 依次 提取元素,然后再进入内部一层重复相同的步骤,直到提取完所有元素。

面试最常见算法3—数组_矩阵

示例 1:

输入:array = [[1,2,3],[8,9,4],[7,6,5]]
输出:[1,2,3,4,5,6,7,8,9]
class Solution {
    public int[] spiralArray(int[][] array) {
        if(array.length==0) {
            return new int[0];
        }
        int[] res = new int[array.length*array[0].length];
        int idx=0;
        int up=0,down=array.length-1,left=0,right=array[0].length-1;
        while(true) {
            for(int i=left;i<=right;i++) {
                res[idx++]=array[up][i];
            }
            if(++up>down) {
                break;
            }
            for(int i=up;i<=down;i++) {
                res[idx++]=array[i][right];
            }
            if(--right<left) {
                break;
            }
            for(int i=right;i>=left;i--) {
                res[idx++]=array[down][i];
            }
            if(--down<up) {
                break;
            }
            for(int i=down;i>=up;i--) {
                res[idx++]=array[i][left];
            }
            if(++left>right) {
                break;
            }
        }
        return res;
    } 
}

https://leetcode.cn/problems/shun-shi-zhen-da-yin-ju-zhen-lcof/comments/

https://leetcode.cn/problems/spiral-matrix/comments/

2.求数组中最大乘积

public static int maxProduct(int[] nums) { 
        if (nums == null || nums.length  == 0) { 
            return 0; 
        } 
         
        int maxProduct = nums[0]; // 最终的最大乘积结果 
        int maxCurrent = nums[0]; // 当前的最大乘积 
        int minCurrent = nums[0]; // 当前的最小乘积 
         
        for (int i = 1; i < nums.length;  i++) { 
            // 如果当前元素是负数,交换maxCurrent和minCurrent 
            if (nums[i] < 0) { 
                int temp = maxCurrent; 
                maxCurrent = minCurrent; 
                minCurrent = temp; 
            } 
             
            // 更新当前的最大乘积和最小乘积 
            maxCurrent = Math.max(nums[i],  maxCurrent * nums[i]); 
            minCurrent = Math.min(nums[i],  minCurrent * nums[i]); 
             
            // 更新最终的最大乘积结果 
            maxProduct = Math.max(maxProduct,  maxCurrent); 
        } 
         
        return maxProduct; 
    }

3.求数组中连续最大和

描述

一个数组有 N 个元素,求连续子数组的最大和。 例如:[-1,2,1],和最大的连续子数组为[2,1],其和为 3

public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int sums=0, maxsums=Integer.MIN_VALUE; //考虑全为负数的情况

            sums+=sc.nextInt();
            maxsums=Math.max(maxsums,sums);
            sums= sums<0?0:sums; //代码核心了,如果当前求和为负,则抛弃之前的连续数组,重新开始求和

        }
        System.out.println(maxsums);
    }

https://www.nowcoder.com/practice/5a304c109a544aef9b583dce23f5f5db?tpId=182&ru=%2Fexam%2Foj&difficulty=&judgeStatus=&tags=&title=&sourceUrl=&gioEnter=menu

4.和为 S 的连续正数序列

示例1

输入:9
输出:[[2,3,4],[4,5]]
public ArrayList > FindContinuousSequence(int sum) {
       ArrayList<ArrayList<Integer>> ret = new ArrayList<>();
       int start=1,end=2;
       int currSum = 3;
       while(end < sum) {
           if(currSum > sum) {
               currSum-=start;
               start++;
           } else if (currSum < sum) {
               end++;
               currSum+=end;
           } else{
              temp = new ArrayList<>();
               for(int i=start; i<=end; i++) {
                   temp.add(i);
               }
               ret.add(temp);
               currSum-=start;
               start++;
               end++;
               currSum+=end;
           }
       }
       return ret;
    }

https://www.nowcoder.com/practice/c451a3fd84b64cb19485dad758a55ebe?tpId=13&tqId=11194&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking&from=cyc_github

5.合并有序数组

两个有序数组合并成新的有序数组

示例 1:

输入:nums1 = [1,2,5], nums2 = [3,4,6]
输出:[1,2,3,4,5,6]
public int[] mergeArray(int[] a,int[] b){
		int[] result = new int[a.length+b.length];
		int i = 0,j =0,k = 0;

			if(a[i] < b[j]){
				result[k++] = a[i++];
				}
			else{
				result[k++] = b[j++];
			}
		}
		/* 后面连个while循环是用来保证两个数组比较完之后剩下的一个数组里的元素能顺利传入 *
         * 此时较短数组已经全部放入新数组,较长数组还有部分剩余,最后将剩下的部分元素放入新数组,大功告成*/
        while(i < a.length) 
            result[k++] = a[i++];
        while(j < b.length)
            result[k++] = b[j++];
		return result;
	}

6.数组排序

排序可以使用冒泡+插入+快速+希尔+归并+桶+基数等方式实现

最基础的四个算法:冒泡、选择、插入、快排中,快排的时间复杂度最小O(n*log2n),其他都是O(n2)

排序法

平均时间

最差情形

稳定度

额外空间

备注

冒泡

O(n2)

    O(n2)

稳定

O(1)

n小时较好

选择

O(n2)

O(n2)

不稳定

O(1)

n小时较好

插入

O(n2)

O(n2)

稳定

O(1)

大部分已排序时较好

基数

O(logRB)

O(logRB)

稳定

O(n)

B是真数(0-9),

R是基数(个十百)

Shell

O(nlogn)

O(ns) 1

不稳定

O(1)

s是所选分组

快速

O(nlogn)

O(n2)

不稳定

O(nlogn)

n大时较好

归并

O(nlogn)

O(nlogn)

稳定

O(1)

n大时较好

O(nlogn)

O(nlogn)

不稳定

O(1)

n大时较好

public static void quickSort(int[] arr, int low, int high){
    int i,j,temp,t;
    if(low>high){
        return;
    }
    i=low;
    j=high;
    //temp就是基准位
    temp = arr[low];

    while (i<j) {
        //先看右边,依次往左递减
        while (temp<=arr[j]&&i<j) {
            j--;
        }
        //再看左边,依次往右递增
        while (temp>=arr[i]&&i<j) {
            i++;
        }
        //如果满足条件则交换
        if (i<j) {
            t = arr[j];
            arr[j] = arr[i];
            arr[i] = t;
        }

    }
    //最后将基准为与i和j相等位置的数字交换
    arr[low] = arr[i];
    arr[i] = temp;
    //递归调用左半数组
    quickSort(arr, low, j-1);
    //递归调用右半数组
    quickSort(arr, j+1, high);
}

标签:nums,int,++,面试,算法,数组,length,array
From: https://blog.51cto.com/u_13222507/11909635

相关文章

  • 工厂模式、工厂方法面试常备
    1、定义汽车#include<iostream>usingnamespacestd;classCar{public:Car(stringname_):name(name_){}~Car(){}public:stringname;virtualvoidshow(){cout<<"thisisnomore:"<<name<<endl;......
  • 【花雕学编程】Arduino FOC 之并联五连杆算法
    Arduino是一个开放源码的电子原型平台,它可以让你用简单的硬件和软件来创建各种互动的项目。Arduino的核心是一个微控制器板,它可以通过一系列的引脚来连接各种传感器、执行器、显示器等外部设备。Arduino的编程是基于C/C++语言的,你可以使用ArduinoIDE(集成开发环境)来编写、......
  • 多目标应用:基于自组织多模态多目标鸽群优化算法MMOPIO的移动机器人路径规划研究(提供MA
      一、机器人路径规划介绍移动机器人(Mobilerobot,MR)的路径规划是移动机器人研究的重要分支之,是对其进行控制的基础。根据环境信息的已知程度不同,路径规划分为基于环境信息已知的全局路径规划和基于环境信息未知或局部已知的局部路径规划。随着科技的快速发展以及机器人的大......
  • 最近(2024.08.14-2024.08.25 )面试感悟
    简历最近(2024.08.14-2024.08.25)除了周末,都在面试的路上,平均每天3、4场面试,边面试边回顾知识点边完善简历,在哀鸿遍野的招聘市场里,简历做了调整,突出自己的优势,比如读过spring源码要能清楚的说出来、比如对jvm内存模型的了解,及为什么采用对应的垃圾回收算法;比如遇到的jvm内存及解决......
  • JVM面试(二)内存区域划分
    内存区划分Java虚拟机在执行Java程序的过程中会把它锁管理的内存划分为若干个不同的数据区域。这些区域有各自不同的用途,以及创建和销毁的时间。有的区域随着虚拟机的进程一直存在,有的区域依赖用户线程的启动和结束而建立和销毁。根据《Java虚拟机规范》的规定,Java虚拟......
  • 文心一言 VS 讯飞星火 VS chatgpt (339)-- 算法导论23.1 8题
    八、设TTT为图GGG的一棵最小生成树,设......
  • 决策树算法 0基础小白也能懂(附代码)
    决策树算法原文链接啥是决策树决策树(Decisiontree)是基于已知各种情况(特征取值)的基础上,通过构建树型决策结构来进行分析的一种方式,是常用的有监督的分类算法(也就是带有标签的训练数据集训练的,比如后文中使用到的训练集中的好瓜坏瓜就是标签,形容瓜的就是特征)决策树模型(Decision......
  • LeetCode_0028. 找出字符串第一个匹配项的下标,KMP算法的实现
    题目描述  给你两个字符串haystack和needle,请你在haystack字符串中找出needle字符串的第一个匹配项的下标(下标从0开始)。如果needle不是haystack的一部分,则返回-1。示例1:输入:haystack="sadbutsad",needle="sad"输出:0解释:"sad"在下标0和6处匹......
  • 召回策略算法-粗排算法-精排算法
     召回策略算法召回策略算法用于在海量文档中快速识别和选择与用户查询相关的文档,以满足用户的检索需求:提高检索效率:召回策略算法能够快速过滤出与用户查询相关的文档,减少了后续排序和排除不相关文档的计算量,从而提高了检索效率。提高搜索结果的相关性:通过选择与用户查询......
  • 过滤策略算法
    过滤策略算法过滤策略算法是指根据特定的规则或条件,从一组数据中筛选出符合要求的数据集合的方法。在信息检索和搜索引擎领域,过滤策略算法常用于对搜索结果或推荐结果进行过滤,以提供更符合用户需求的结果集合。比如针对过滤用户拉黑的内容和不感兴趣的内容,可以采用基于用户行......