当前位置: 首页> 健康> 母婴 > 个人网站内容如何填写_上海美术设计公司_营销策划方案怎么做_北京最新疫情

个人网站内容如何填写_上海美术设计公司_营销策划方案怎么做_北京最新疫情

时间:2025/7/11 7:55:00来源:https://blog.csdn.net/ylfhpy/article/details/146693019 浏览次数:0次
个人网站内容如何填写_上海美术设计公司_营销策划方案怎么做_北京最新疫情

1. 手写栈实现队列

  • 定义

队列遵循先进先出(FIFO)原则,即最先进入队列的元素最先出队;而栈遵循后进先出(LIFO)原则,即最后进入栈的元素最先出栈。使用两个栈来模拟队列,一个栈用于入队操作(pushStack),另一个栈用于出队操作(popStack),借助栈的特性实现队列的功能。

  • 要点
  1. 入队操作:直接将元素压入 pushStack
  2. 出队操作:若 popStack 为空,把 pushStack 中的所有元素依次弹出并压入 popStack,然后从 popStack 弹出元素;若 popStack 不为空,直接从 popStack 弹出元素。
  3. 时间复杂度:入队操作的时间复杂度为 O(1),出队操作的平均时间复杂度也为 O(1)。

  • 应用
  1. 在多线程环境中,当需要对任务进行排队处理,且任务的入队和出队操作频率不同时,可以使用栈实现队列来平衡性能。
  2. 在某些算法中,如广度优先搜索(BFS),需要使用队列来存储待处理的节点,若队列操作较为复杂,可采用栈实现的队列。

java

import java.util.Stack;class MyQueue {private Stack<Integer> pushStack;private Stack<Integer> popStack;public MyQueue() {pushStack = new Stack<>();popStack = new Stack<>();}public void enqueue(int x) {pushStack.push(x);}public int dequeue() {if (popStack.isEmpty()) {while (!pushStack.isEmpty()) {popStack.push(pushStack.pop());}}if (popStack.isEmpty()) {throw new RuntimeException("Queue is empty");}return popStack.pop();}public boolean isEmpty() {return pushStack.isEmpty() && popStack.isEmpty();}
}

2. 给定一个二叉树,打印每一层最右边的结点

  • 定义

广度优先搜索(BFS)是一种用于遍历或搜索树或图的算法,它从根节点开始,逐层地访问节点。对于二叉树,使用 BFS 遍历每一层节点,在遍历过程中记录每一层的最后一个节点,最终打印出这些节点。

  • 要点
  1. 使用队列:借助队列来实现 BFS 遍历,将根节点入队,然后不断从队列中取出节点进行处理,并将其左右子节点入队。
  2. 记录层信息:在遍历每一层时,记录该层的节点数,通过节点数来确定该层的最后一个节点。
  3. 时间复杂度:O(n),其中 n 是二叉树的节点数。

  • 应用
  1. 在图像处理中,对于一些树形结构的图像数据,如四叉树,可使用该方法获取每一层的边界信息。
  2. 在网络爬虫中,对于网页的树形结构,可通过该方法获取每一层的关键页面信息。

java

import java.util.LinkedList;
import java.util.Queue;class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int x) { val = x; }
}public class RightViewOfBinaryTree {public void printRightView(TreeNode root) {if (root == null) {return;}Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);while (!queue.isEmpty()) {int levelSize = queue.size();for (int i = 0; i < levelSize; i++) {TreeNode node = queue.poll();if (i == levelSize - 1) {System.out.print(node.val + " ");}if (node.left != null) {queue.offer(node.left);}if (node.right != null) {queue.offer(node.right);}}}}
}

3. 给定一个数组,里面只有一个数出现了一次,其他都出现了两次。怎么得到这个出现了一次的数

  • 定义

异或运算是一种二进制位运算,相同的二进制位异或结果为 0,不同的二进制位异或结果为 1。根据异或运算的交换律和结合律,对数组中的所有元素进行异或运算,相同的元素异或结果为 0,最终剩下的就是只出现一次的数。

  • 要点
  1. 异或运算特性:利用异或运算的交换律 a ^ b = b ^ a 和结合律 (a ^ b) ^ c = a ^ (b ^ c),以及 a ^ 0 = aa ^ a = 0 的特性。
  2. 时间复杂度:O(n),其中 n 是数组的长度。

  • 应用
  1. 在数据校验中,可通过异或运算来检测数据是否被篡改。例如,对一组数据进行异或运算得到一个校验值,在传输或存储后再次进行异或运算,若结果与原校验值相同,则数据可能未被篡改。
  2. 在密码学中,异或运算可用于简单的加密和解密操作。

java

public class SingleNumber {public int singleNumber(int[] nums) {int result = 0;for (int num : nums) {result ^= num;}return result;}
}

4. 如果有两个不同数的出现了一次,其他出现了两次,怎么得到这两个数

  • 定义

同样基于异或运算的特性,先将数组中的所有元素进行异或运算,得到的结果是这两个只出现一次的数的异或结果。然后找到这个异或结果中任意一位为 1 的位,根据这一位是否为 1 将数组中的元素分为两组,这样这两个只出现一次的数就会被分到不同的组中,最后分别对这两组元素进行异或运算,得到这两个只出现一次的数。

  • 要点
  1. 分组依据:通过异或结果中某一位为 1 的位来分组,保证两个只出现一次的数被分到不同组。
  2. 时间复杂度:O(n),其中 n 是数组的长度。

  • 应用
  1. 在数据加密中,可用于将加密数据中的两个关键信息分离出来。
  2. 在故障诊断中,若系统中有两个独立的故障源,且故障信息以某种方式存储在数组中,可使用该方法找出这两个故障源。

java

public class SingleNumbers {public int[] singleNumbers(int[] nums) {int xorResult = 0;for (int num : nums) {xorResult ^= num;}int mask = 1;while ((xorResult & mask) == 0) {mask <<= 1;}int num1 = 0, num2 = 0;for (int num : nums) {if ((num & mask) == 0) {num1 ^= num;} else {num2 ^= num;}}return new int[]{num1, num2};}
}

5. 查找有序数组和为 S 的数

  • 定义

双指针法是一种常用的算法技巧,对于有序数组,使用两个指针,一个指针指向数组的开头(left),另一个指针指向数组的末尾(right)。通过计算两个指针所指元素的和,并与目标值 S 进行比较,根据比较结果移动指针,缩小查找范围。

  • 要点
  1. 指针移动规则:若和等于 S,则找到这两个数;若和小于 S,则将 left 指针右移;若和大于 S,则将 right 指针左移。
  2. 时间复杂度:O(n),其中 n 是数组的长度。

  • 应用
  1. 在数据库查询优化中,对于有序的索引数据,可使用双指针法快速查找满足条件的记录。
  2. 在数据分析中,对于有序的数据集,可使用该方法查找满足特定和条件的数据对。

java

public class TwoSumInSortedArray {public int[] twoSum(int[] nums, int target) {int left = 0, right = nums.length - 1;while (left < right) {int sum = nums[left] + nums[right];if (sum == target) {return new int[]{nums[left], nums[right]};} else if (sum < target) {left++;} else {right--;}}return new int[]{};}
}

6. 公司有 10000 名员工,要求按照年龄来排序要求时间复杂度 O (N)

  • 定义

计数排序是一种非比较排序算法,适用于数据范围较小的情况。对于员工年龄排序问题,由于年龄的范围通常是有限的(例如 0 - 120 岁),可以使用一个数组来记录每个年龄出现的次数,然后根据这个数组重新构建排序后的数组。

  • 要点
  1. 计数数组:创建一个长度为年龄范围的数组,用于记录每个年龄出现的次数。
  2. 时间复杂度:O(N+k),其中 N 是员工的数量,k 是年龄的范围。

  • 应用
  1. 在学生成绩排序中,若成绩范围较小,可使用计数排序快速完成排序。
  2. 在统计某一地区居民的年龄分布时,可使用计数排序对居民年龄进行排序和统计。

java

public class AgeSorting {public void sortByAge(int[] ages) {int[] count = new int[121];for (int age : ages) {count[age]++;}int index = 0;for (int i = 0; i <= 120; i++) {while (count[i] > 0) {ages[index++] = i;count[i]--;}}}
}

7. 两个 int32 整数 m 和 n 的二进制表达有多少位不同

  • 定义

异或运算可以找出两个数二进制表达中不同的位,因为相同的位异或结果为 0,不同的位异或结果为 1。然后使用 Brian Kernighan 算法来统计异或结果中 1 的个数,该算法的核心是通过 n &= (n - 1) 操作不断清除 n 中最右边的 1。

  • 要点
  1. 异或运算:通过 m ^ n 得到两个数二进制表达中不同位组成的数。
  2. Brian Kernighan 算法:通过不断清除最右边的 1 来统计 1 的个数。
  3. 时间复杂度:O(k),其中 k 是异或结果中 1 的个数。

  • 应用
  1. 在数据压缩中,可通过计算两个数据的二进制差异位来评估数据的相似度,进而选择合适的压缩算法。
  2. 在图像处理中,可用于比较两幅图像的像素值的二进制差异,检测图像的变化。

java

public class HammingDistance {public int hammingDistance(int m, int n) {int xorResult = m ^ n;int count = 0;while (xorResult != 0) {xorResult &= (xorResult - 1);count++;}return count;}
}

8. 全排列的算法思路

  • 定义

回溯法是一种通过尝试所有可能的解来找到问题的解的算法。对于一个数组,从第一个位置开始,依次将每个元素放到该位置,然后递归地对剩余的元素进行全排列,在递归过程中,若发现当前的选择无法得到有效的解,则回溯到上一步,尝试其他选择。

  • 要点
  1. 递归与回溯:通过递归不断尝试不同的元素排列,当排列完成后回溯,尝试其他排列。
  2. 时间复杂度:O(n!),其中 n 是数组的长度。

  • 应用
  1. 在旅行商问题(TSP)中,可通过全排列算法找出所有可能的旅行路线,然后选择最短的路线。
  2. 在密码破解中,对于已知长度和字符集的密码,可使用全排列算法生成所有可能的密码组合进行尝试。

java

import java.util.ArrayList;
import java.util.List;public class Permutations {public List<List<Integer>> permute(int[] nums) {List<List<Integer>> result = new ArrayList<>();backtrack(result, new ArrayList<>(), nums);return result;}private void backtrack(List<List<Integer>> result, List<Integer> tempList, int[] nums) {if (tempList.size() == nums.length) {result.add(new ArrayList<>(tempList));} else {for (int i = 0; i < nums.length; i++) {if (tempList.contains(nums[i])) continue;tempList.add(nums[i]);backtrack(result, tempList, nums);tempList.remove(tempList.size() - 1);}}}
}

9. 字符串反转

  • 定义

字符串反转是将字符串中的字符顺序颠倒。双指针法是一种简单有效的实现方法,通过一个指针指向字符串的开头,另一个指针指向字符串的末尾,交换两个指针所指的字符,然后将两个指针向中间移动,直到两个指针相遇。

  • 要点
  1. 双指针移动:不断交换首尾指针所指的字符,并向中间移动指针。
  2. 时间复杂度:O(n/2),可近似看作 O(n),其中 n 是字符串的长度。

  • 应用
  1. 在文本处理中,如处理回文字符串时,可先将字符串反转,然后与原字符串比较。
  2. 在数据加密中,可将字符串反转作为一种简单的加密手段。

java

public class ReverseString {public String reverseString(String s) {char[] charArray = s.toCharArray();int left = 0, right = charArray.length - 1;while (left < right) {char temp = charArray[left];charArray[left] = charArray[right];charArray[right] = temp;left++;right--;}return new String(charArray);}
}

10. 拓扑排序

  • 定义

拓扑排序是对有向无环图(DAG)的顶点进行排序的一种算法,使得对于图中的任意一条有向边 (u,v),顶点 u 在排序结果中都出现在顶点 v 之前。可以使用 Kahn 算法或深度优先搜索(DFS)来实现拓扑排序。

  • 要点
  1. Kahn 算法:不断选择入度为 0 的顶点,并将其从图中移除,直到图中没有顶点为止。
  2. DFS 算法:对图进行深度优先搜索,在回溯时将顶点加入到结果列表中,最后将结果列表反转。
  3. 时间复杂度:O(V+E),其中 V 是图的顶点数,E 是图的边数。

  • 应用
  1. 在项目管理中,可将项目的各个任务看作图的顶点,任务之间的依赖关系看作有向边,通过拓扑排序确定任务的执行顺序。
  2. 在编译器的依赖分析中,可使用拓扑排序来确定编译单元的编译顺序。

java

import java.util.*;public class TopologicalSort {public List<Integer> topologicalSort(int numCourses, int[][] prerequisites) {List<List<Integer>> adjList = new ArrayList<>();for (int i = 0; i < numCourses; i++) {adjList.add(new ArrayList<>());}int[] inDegree = new int[numCourses];for (int[] prerequisite : prerequisites) {int u = prerequisite[1];int v = prerequisite[0];adjList.get(u).add(v);inDegree[v]++;}Queue<Integer> queue = new LinkedList<>();for (int i = 0; i < numCourses; i++) {if (inDegree[i] == 0) {queue.offer(i);}}List<Integer> result = new ArrayList<>();while (!queue.isEmpty()) {int u = queue.poll();result.add(u);for (int v : adjList.get(u)) {inDegree[v]--;if (inDegree[v] == 0) {queue.offer(v);}}}if (result.size() == numCourses) {return result;} else {return new ArrayList<>();}}
}

友情提示:本文已经整理成文档,可以到如下链接免积分下载阅读

https://download.csdn.net/download/ylfhpy/90546438

关键字:个人网站内容如何填写_上海美术设计公司_营销策划方案怎么做_北京最新疫情

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: