秋招突击——算法练习——8/30、9/4——技巧题练习——复习{}——新作{只出现一次的数字、多数元素、颜色分类、下一个排列、寻找重复数}

2024-09-05 10:28
文章标签 算法 技巧 元素 分类 练习 重复 秋招 复习 30 一次 数字 颜色 排列 多数 寻找 突击 新作

本文主要是介绍秋招突击——算法练习——8/30、9/4——技巧题练习——复习{}——新作{只出现一次的数字、多数元素、颜色分类、下一个排列、寻找重复数}，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

    • 引言
    • 复习
    • 新作
      • 136、只出现一次的数字
        • 个人实现
      • 169、多数元素
        • 个人实现
      • 75、颜色分类
        • 个人实现
        • 参考实现
      • 31、下一个排列
        • 个人实现
        • 参考实现
      • 287寻找重复数
        • 个人实现
        • 参考实现
    • 总结

引言

  • 手撕的代码大部分都是出自于这里，还是要继续加强，把剩下一些零碎的题目再过一遍，然后再把hot100再刷一遍，这次重在于思想，而不是代码和答案。

复习

新作

136、只出现一次的数字

  • 题目链接
    在这里插入图片描述
    注意
  • 输入的是数组，并且不会越界，使用int就能够存储
  • 元素中出了一个元素只出现一次，其余元素都出现了两次
  • 输出仅仅出现一次的元素
个人实现
  • 这个题目就是使用异或运算，异或运算，满足交换性，自反性和结合性。
class Solution {public int singleNumber(int[] nums) {int  res = nums[0];for(int i = 1;i < nums.length;i ++)res ^= nums[i];return res;}
}

在这里插入图片描述

169、多数元素

题目链接
在这里插入图片描述
注意

  • 给的是一个有重复元素的数组，一定存在一个元素出现的次数是超过了总数量的一半
  • 数组不为空，一定会有一个答案
个人实现
  • 直白的就是遍历整个数组，然后统计一下次数，然后返回最大的结果。
class Solution {public int majorityElement(int[] nums) {Map<Integer,Integer> map = new HashMap<>();int[] res = {0,0};for(int x:nums){map.put(x,map.getOrDefault(x,0) + 1);int count = map.get(x);if( count >= res[1]){res[0] = x;res[1] = count; }}return res[0];}
}

在这里插入图片描述
总结

  • 如果这个题目是一个场景题，现在有10亿个数字，你应该怎么做？
  • 没有办法全部加载到内存中，只能一部分一部分加载到内存中，然后统计次数，保存到hashmap中吗？不对，感觉这个方法不对！

摩尔投票算法

class Solution {public int majorityElement(int[] nums) {int count = 0;int num = 0;for(int x:nums){if(count == 0){count = 1;num = x;}else{if(x == num) count ++;else count --;}}return num;}
}

在这里插入图片描述

75、颜色分类

题目链接
在这里插入图片描述
注意

  • 总共只有三种数字，分别是0、1、2，然后相同的数字放在一起，然后按照0、1、2进行排序
  • 只能使用常数空间实现！
个人实现
  • 如果常数空间，直白的话就是使用交换排序，因为元素是知道的，然后相对顺序也是知道的，直接双指针交换就行了！

在这里插入图片描述
这里有一个思路，这个右侧肯定是2，然后左侧肯定是0，所以逐个进行遍历，出现2往右移动，出现0往左移动就行了！

class Solution {public void sortColors(int[] nums) {int m = nums.length - 1;int l = 0,r = m;int cur = l ;// 使用三指针，中间的指针用来遍历，左右指针用来保存while(cur <= r){// 往右加换2，保证r指针右侧都是2// if(nums[cur] == 2){while(r > cur && nums[r] == 2) r--;int temp = nums[r];nums[r] = nums[cur];nums[cur] = temp;r--;}// 往左交换0，保证l左侧的指针都是0if(nums[cur] == 0){while(l < cur && nums[l] == 0) l ++;int temp = nums[l];nums[l] = nums[cur];nums[cur] = temp;l ++;}        // 然后在移动对应的cur指针cur ++;    }return;}
}

在这里插入图片描述
总结

  • 这道题感觉做的还是有点久的，因为一开始用了双指针进行交换，但是有一些问题解决不了，就想着用三指针，因为知道2就往右，0就往左，是固定的！
  • 然后重新写了一下！
参考实现
  • 单指针就需要遍历两次，然后双指针就是需要遍历一次，这里用的方法和我的差不多，不过代码上更简洁一点，具体实现如下

流程图直接看这里

class Solution {public void sortColors(int[] nums) {int m = nums.length - 1;int p0 = 0, p1 = 0;// 使用三指针，中间的指针用来遍历，左右指针用来保存for (int i = 0; i <= m; i++) {if (nums[i] == 1) {int temp = nums[i];nums[i] = nums[p1];nums[p1] = temp;p1++;} else if (nums[i] == 0) {int temp = nums[i];nums[i] = nums[p0];nums[p0] = temp;if (p0 < p1) {temp = nums[i];nums[i] = nums[p1];nums[p1] = temp;}p0++;p1++;}}return;}
}

31、下一个排列

题目链接
在这里插入图片描述
注意

  • 当前序列会有若干序列，需要找出下一个字典序中的序列是什么
  • 只能原地修改，只允许使用额外的常数空间
个人实现
  • 这个没什么好的方法，然后直接看参考实现吧！
参考实现

在这里插入图片描述

class Solution {public void nextPermutation(int[] nums) {// 主要分为两部，先是找到较小的，然后再找比较小的大的// 然后进行交换，然后在排序// 这里需要遍历对应的元素int n = nums.length;if(n == 1)  {return;}if(n == 2){swap(nums,0,1);return;}// 超过两个元素的情况int i = nums.length - 2;while(i >= 0 && nums[i] >= nums[i + 1]){i --;}if(i >= 0){int j = nums.length - 1;while(j >= 0 && nums[i] >= nums[j]){j --;}swap(nums,i ,j);}reverse(nums,i + 1 ,nums.length - 1);}// 交换元素public void swap(int[] nums,int i,int j){int temp = nums[i];nums[i] = nums[j];nums[j] = temp;}public void reverse(int[] nums ,int i ,int j){// 将从i到j 的序列进行反转while(i <= j){swap(nums,i , j);i ++;j --;}}
}

在这里插入图片描述

287寻找重复数

题目链接
在这里插入图片描述
注意

  • 有一个数字树出现了多次，然后其他的数字仅仅出现了一次
  • 找出这个出现多次的数字
个人实现

个人思路

  • 不能修改原来的数组，所以不能进行排序了，如果能够排序，那就好做了！
  • 然后只能使用常数的存储空间，就不能创建一个类似hash表的结构进行处理的
  • 针对这类题目，常规的会使用bitmap，操作位图，然后需要遍历的，但是这样就不是常数的存储空间了，而且就算申请了固定的存储存储空间也是取巧！
  • 抓住两个点，所有的数组都是在1到n之间的，而且只有一个数字是重复的，其他的数字都是唯一的
    • 求和感觉看不出来什么，其他的也看不出来啥，为什么求和，是因为他是一个顺序不一样的操作，所以不得行！，那想想看，能不能对每一个元素做差，然后再求绝对值，然后在求和，最小的时候，就是最大的！

在这里插入图片描述

  • 平均减一，做差求和的思路去试试看
  • 通过下述的方式，可以看出来重复多少次，以及具体是什么值
    在这里插入图片描述
class Solution {public int findDuplicate(int[] nums) {int n = nums.length;int preSum = 0;int res = 0;for(int j = 0;j < n;j ++){preSum += nums[j];}for(int i = 1;i <= n;i ++){int sum = 0;for(int j = 0;j < n;j ++){sum += Math.abs(nums[j] - i);}// 判定是否相等System.out.println(sum + "  " + preSum);if(preSum > sum){res ++;}preSum = sum;}return res;}
}

总结

  • 这个不会，属实整不会了，不知道怎么弄！因为如果是单单最小的和话，1这种情况无解！
参考实现

  • 这里使用了快慢指针来实现，因为所有数字都是在1到n的，所以可以转成图论来看这个问题，具体如下
    在这里插入图片描述

  • 使用快慢指针的话，快慢相遇表示会成环

  • 然后在确定环的切入点就行

class Solution {public int findDuplicate(int[] nums) {int a = 0, b = 0;while (true) {a = nums[a]; // a走一步b = nums[nums[b]]; // b走两步if (a == b) {a = 0;while (a != b) {a = nums[a];b = nums[b];}return a;}}}
}

切入点的疑惑

  • 找到相遇点了，为什么a直接从零开始遍历，再次相遇，然后同时运行，再次相遇就是相遇点了！

在这里插入图片描述

总结

  • 继续加油，秋招还有机会！
  • 感觉要做一个自己的博客网站了，CSDN不是很好用，首先搜索我自己的博文的时候，居然没有办法进行模糊匹配，我搜环形链表，居然搜出来为空，然后只能自己一个一个找，这个效率太低了！
    • 搞一个自己的博客，至少以后面试也有的讲！
  • 秋招还是比较难得，好不容易面过了美团，结果没有HC，直接回到了人才池，然后重新开始面试吧！

这篇关于秋招突击——算法练习——8/30、9/4——技巧题练习——复习{}——新作{只出现一次的数字、多数元素、颜色分类、下一个排列、寻找重复数}的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1138695。

相关文章

Ilya-AI分享的他在OpenAI学习到的15个提示工程技巧

Ilya-AI分享的他在OpenAI学习到的15个提示工程技巧

Ilya（不是本人，claude AI）在社交媒体上分享了他在OpenAI学习到的15个Prompt撰写技巧。 以下是详细的内容： 提示精确化:在编写提示时,力求表达清晰准确。清楚地阐述任务需求和概念定义至关重要。例:不用"分析文本",而用"判断这段话的情感倾向:积极、消极还是中性"。 快速迭代:善于快速连续调整提示。熟练的提示工程师能够灵活地进行多轮优化。例:从"总结文章"到"用
阅读更多...
不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
基于人工智能的图像分类系统

基于人工智能的图像分类系统

目录 引言项目背景环境准备 硬件要求软件安装与配置系统设计 系统架构关键技术代码示例 数据预处理模型训练模型预测应用场景结论 1. 引言 图像分类是计算机视觉中的一个重要任务，目标是自动识别图像中的对象类别。通过卷积神经网络（CNN）等深度学习技术，我们可以构建高效的图像分类系统，广泛应用于自动驾驶、医疗影像诊断、监控分析等领域。本文将介绍如何构建一个基于人工智能的图像分类系统，包括环境
阅读更多...
从去中心化到智能化：Web3如何与AI共同塑造数字生态

从去中心化到智能化：Web3如何与AI共同塑造数字生态

在数字时代的演进中，Web3和人工智能（AI）正成为塑造未来互联网的两大核心力量。Web3的去中心化理念与AI的智能化技术，正相互交织，共同推动数字生态的变革。本文将探讨Web3与AI的融合如何改变数字世界，并展望这一新兴组合如何重塑我们的在线体验。 Web3的去中心化愿景 Web3代表了互联网的第三代发展，它基于去中心化的区块链技术，旨在创建一个开放、透明且用户主导的数字生态。不同于传统
阅读更多...
康拓展开（hash算法中会用到）

康拓展开（hash算法中会用到）

康拓展开是一个全排列到一个自然数的双射（也就是某个全排列与某个自然数一一对应） 公式： X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。（a[i]在不同应用中的含义不同）； 典型应用： 计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第
阅读更多...
认识、理解、分类——acm之搜索

认识、理解、分类——acm之搜索

普通搜索方法有两种：1、广度优先搜索；2、深度优先搜索； 更多搜索方法： 3、双向广度优先搜索； 4、启发式搜索（包括A*算法等）； 搜索通常会用到的知识点：状态压缩（位压缩，利用hash思想压缩）。
阅读更多...
csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

这是一道扩展欧几里得算法的简单应用题，这题是在湖南多校训练赛中队友ac的一道题，在比赛之后请教了队友，然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意：把题意转变下就变成了：求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点：求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个
阅读更多...
综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动，这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升：减少抖动，提高图像的清晰度和细节表现力，使得监控画面更加真实可信。 - 细节增强：在低光条件下，抖
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
poj2406（连续重复子串）

poj2406（连续重复子串）

题意:判断串s是不是str^n，求str的最大长度。 解题思路：kmp可解，后缀数组的倍增算法超时。next[i]表示在第i位匹配失败后，自动跳转到next[i]，所以1到next[n]这个串 等于 n-next[n]+1到n这个串。 代码如下； #include<iostream>#include<algorithm>#include<stdio.h>#include<math.
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2