【华为面试手撕代码】

这篇具有很好参考价值的文章主要介绍了【华为面试手撕代码】。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。


先说思路,然后写代码

常用的排序算法

1.冒泡排序

1.设置循环次数。
2.设置开始比较的位数,和结束的位数。
3.两两比较,将最小的放到前面去。
重复2、3步,直到循环次数完毕。

int temp;//定义一个临时变量
for(int i=0;i<arr.length-1;i++){
   //冒泡趟数
    for(int j=0;j<arr.length-i-1;j++){
   //从第一个比到n-1-i
        if(arr[j+1]<arr[j]){
   //若前面比后面大,则交换
            temp = arr[j];
            arr[j] = arr[j+1];
            arr[j+1] = temp;
         }
     }
}

2.选择排序

1.首先在未排序序列中找到最小元素,存放到排序序列的起始位置。
2.再从剩余未排序元素中继续寻找最小元素,然后放到已排序序列的末尾。
3.重复第二步,直到所有元素均排序完毕。

/* 选择排序 */
void SelectionSort(int arr[], int length)
{
   
    int index, temp;
	for (int i = 0; i < length; i++)
	{
   
        index = i;//未排序序列中最小元素
		for (int j = i + 1; j < length; j++)
		{
   
			if (arr[j] < arr[index])
				index = j;
		}
		if (index != i)
		{
   
			temp = arr[i];
			arr[i] = arr[index];
			arr[index] = temp;
		}
	}
}

3.插入排序

将数组R划分成两个子区间R[1..i-1](已排好序的有序区)和R[i..n](当前未排序的部分,可称无序区)。插入排序的基本操作是将当前无序区的第1个记录R[i]插人到有序区R[1..i-1]中适当的位置上,使R[1..i]变为新的有序区

public voidInsertSort () {
   
	int i,j,temp;
	for(i=1;i<array.length;i++) {
   // R[i..n](当前未排序的部分,可称无序区)
		temp=array[i];
		for(j=i-1;j>=0;j--) {
   // R[1..i-1](已排好序的有序区)
			if(temp>array[j]) {
   
				break;
			}else {
   
				array[j+1]=array[j];//往后挪,腾位置
			}
		}
		array[j+1]=temp;//插入数据
	}
}

4.快排排序

先从右往左找到一个小于基准数的数,再从左往右找到一个大于基准数的数,交换他们.重复,当ij相遇时把此时这个数和基准数交换,再分别处理左右两边的数字.
== 先从右往左找,再从左往右找==

public static void quickSort(int[] arr,int low,int high){
   
    int i,j,temp,t;
    if(low>high) return;
    i=low;
    j=high;
    temp = arr[low];//temp就是基准位
    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;
        }
    }
    arr[low] = arr[i];//最后将基准为与i和j相等位置的数字交换
    arr[i] = temp;
    quickSort(arr, low, j-1);//递归调用左半数组
    quickSort(arr, j+1, high);//递归调用右半数组
}    

5.归并排序

假设初始序列含有n个记录,则可以看成是n个有序的子序列,每个子序列的长度为1,然后两两归并,得到n/2个长度为2(或者是1)的有序子序列,再两两归并。如此重复,直到得到一个长度为n的有序序列为止。

private static void sort(int[] array, int left, int right) {
   
	if (left == right) {
   
		return;
	}
	int mid = left + ((right - left)/2);
	sort(array, left, mid); // 对左侧子序列进行递归排序
	sort(array, mid + 1, right); // 对右侧子序列进行递归排序
	merge(array, left, mid, right); // 合并
}

private static void merge(int[] array, int left, int mid, int right) {
   
	int[] temp = new int[right - left + 1];
	int i = 0;
	int p1 = left;
	int p2 = mid + 1;
	// 比较左右两部分的元素,哪个小,把那个元素填入temp中
	while (p1 <= mid && p2 <= right) {
   
		temp[i++] = array[p1] < array[p2] ? array[p1++] : array[p2++];
	}
	// 上面的循环退出后,把剩余元素依次填入temp(以下两个while只有一个会执行)
	while (p1 <= mid) {
   
		temp[i++] = array[p1++];
	}
	while (p2 <= right) {
   
		temp[i++] = array[p2++];
	}
	// 把最终的排序的结果复制给原数组
	for (i = 0; i < temp.length; i++) {
   
		array[left + i] = temp[i];
	}
}

6.堆排序

可以将堆看做是一个完全二叉树。并且,每个结点的值都大于等于其左右孩子结点的值,称为大顶堆;或者每个结点的值都小于等于其左右孩子结点的值,称为小顶堆。

堆排序(Heap Sort)是利用堆进行排序的方法。其基本思想为:将待排序列构造成一个大顶堆(或小顶堆),整个序列的最大值(或最小值)就是堆顶的根结点,将根节点的值和堆数组的末尾元素交换,此时末尾元素就是最大值(或最小值),然后将剩余的n-1个序列重新构造成一个堆,这样就会得到n个元素中的次大值(或次小值),如此反复执行,最终得到一个有序序列。

【华为面试手撕代码】
图解

a.将无需序列构建成一个堆,根据升序降序需求选择大顶堆或小顶堆;
b.将堆顶元素与末尾元素交换,将最大元素"沉"到数组末端;
c.重新调整结构,使其满足堆定义,然后继续交换堆顶元素与当前末尾元素,反复执行调整+交换步骤,直到整个序列有序。

作者:尼小摩
链接:https://www.jianshu.com/p/a161b991fa82
来源:简书
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。文章来源地址https://www.toymoban.com/news/detail-472234.html

public class HeapSort {
   
    public static void main(String []args){
   
        int []arr = {
   7,6,7,11,5,12,3,0,1};
        System.out.println("排序前:"+Arrays.toString(arr));
        sort(arr);
        System.out.println("排序前:"+Arrays.toString(arr));
    }
    public static void sort(int []arr){
   
        //1.构建大顶堆
        for(int i=arr.length/2-1;i>=0;i--){
   
            //从第一个非叶子结点从下至上,从右至左调整结构
            adjustHeap(arr,i,arr.length);
        }
        //2.调整堆结构+交换堆顶元素与末尾元素
        for(int j=arr.length-1;j>0;j--){
   
            swap(arr,0,j);//将堆顶元素与末尾元素进行交换
            adjustHeap(arr,0,j);//重新对堆进行调整
        }
    }
    //调整大顶堆(仅是调整过程,建立在大顶堆已构建的基础上)
    public static void adjustHeap(int []arr,int i,int length){
   
        int temp = arr[i];//先取出当前元素i
        for(int k=i*2+1;k<length;k=k*2+1){
   //从i结点的左子结点开始,也就是2i+1处开始
            if(k+1<length && arr[k]<arr[k+1]){
   //如果左子结点小于右子结点,k指向右子结点
                k++;
            }
            if(arr[k] >temp){
   //如果子节点大于父节点,将子节点值赋给父节点(不用进行交换)
                arr[i] = arr[k];
                i = k;
            }else{
   
                break;
            }
        }
        arr[i] = temp;//将temp值放到最终的位置
    }
    public static void swap(int []arr,int a ,int b){
   
        int temp=arr[a];
        arr[a] = arr[b

到了这里,关于【华为面试手撕代码】的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 华为面试手撕真题【旋转矩阵】

    有一个NxN整数矩阵,请编写一个算法,将矩阵顺时针旋转90度。 给定一个NxN的矩阵,和矩阵的阶数N,请返回旋转后的NxN矩阵。 要求:空间复杂度 O(1) 也是非常经典,很老的一个题目了,可见其实面试官并没有非常难为人。 常规思路下旋转,肯定要用到额外的空间,想要O(1)空

    2024年02月07日
    浏览(41)
  • 华为od 面试手撕真题【长度最小的子数组】

    给定一个含有 n 个正整数的数组和一个正整数 target 。 找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ,并返回其长度。如果不存在符合条件的子数组,返回 0 。 示例 1: 输入:target = 7, nums = [2,3,1,2,4,3] 输出:2 解释:子数组 [4,3] 是

    2024年02月14日
    浏览(36)
  • Java【手撕滑动窗口】LeetCode 209. “长度最小子数组“, 图文详解思路分析 + 代码

    各位读者好, 我是小陈, 这是我的个人主页, 希望我的专栏能够帮助到你: 📕 JavaSE基础: 基础语法, 类和对象, 封装继承多态, 接口, 综合小练习图书管理系统等 📗 Java数据结构: 顺序表, 链表, 堆, 二叉树, 二叉搜索树, 哈希表等 📘 JavaEE初阶: 多线程, 网络编程, TCP/IP协议, HTTP协议

    2024年02月11日
    浏览(43)
  • Java【手撕滑动窗口】LeetCode 438. “字符串中所有异位词“, 图文详解思路分析 + 代码

    各位读者好, 我是小陈, 这是我的个人主页, 希望我的专栏能够帮助到你: 📕 JavaSE基础: 基础语法, 类和对象, 封装继承多态, 接口, 综合小练习图书管理系统等 📗 Java数据结构: 顺序表, 链表, 堆, 二叉树, 二叉搜索树, 哈希表等 📘 JavaEE初阶: 多线程, 网络编程, TCP/IP协议, HTTP协议

    2024年02月10日
    浏览(39)
  • Java【手撕滑动窗口】LeetCode 3. “无重复字符的最长子串“, 图文详解思路分析 + 代码

    各位读者好, 我是小陈, 这是我的个人主页, 希望我的专栏能够帮助到你: 📕 JavaSE基础: 基础语法, 类和对象, 封装继承多态, 接口, 综合小练习图书管理系统等 📗 Java数据结构: 顺序表, 链表, 堆, 二叉树, 二叉搜索树, 哈希表等 📘 JavaEE初阶: 多线程, 网络编程, TCP/IP协议, HTTP协议

    2024年02月11日
    浏览(39)
  • 华为OD机试 - 去除多余空格(Python)| 真题+思路+代码

    去除文本多余空格,但不去除配对单引号之间的多余空格。给出的起始和结束下标,去除多余空格后刷新的起始和结束下标。 条件约束: 不考虑起始和结束位置为空格的场景; 单词的的开始和结束下标保证涵盖一个完整的单词,即一个坐标对开始和结束

    2024年02月16日
    浏览(41)
  • 【华为OD】C卷真题100分:最大矩阵和 python代码实现[思路+代码]

    C++、Java、JS、C代码: 【华为OD】C卷真题100分:最大矩阵和 C/C++代码实现[思路+代码]-CSDN博客 【华为OD】C卷真题100分:最大矩阵和 Java代码实现[思路+代码]-CSDN博客 【华为OD】C卷真题100分:最大矩阵和 JavaScript代码实现[思路+代码]-CSDN博客 【华为OD】C卷真题100分:最大矩阵和

    2024年04月16日
    浏览(33)
  • 【华为OD】C卷真题100分:最大矩阵和 Java代码实现[思路+代码]

     C++、python、C、JS代码: 【华为OD】C卷真题100分:最大矩阵和 C/C++代码实现[思路+代码]-CSDN博客 【华为OD】C卷真题100分:最大矩阵和 python代码实现[思路+代码]-CSDN博客 【华为OD】C卷真题100分:最大矩阵和 C语言代码实现[思路+代码]-CSDN博客  【华为OD】C卷真题100分:最大矩阵

    2024年04月17日
    浏览(47)
  • 【华为OD】C卷真题 200分:最小矩阵宽度 python代码实现[思路+代码]

    C++、java、JS代码: 【华为OD】C卷真题 200分:最小矩阵宽度 C/C++代码实现[思路+代码]-CSDN博客 【华为OD】C卷真题 200分:最小矩阵宽度 Java代码实现[思路+代码]-CSDN博客 【华为OD】C卷真题 200分:最小矩阵宽度 JavaScript代码实现[思路+代码]-CSDN博客  给定一个矩阵,包含N*M个整数,

    2024年04月17日
    浏览(61)
  • 【华为OD】C卷真题200分:服务器广播 JavaScript代码实现[思路+代码]

      C++、java、python、C代码:  【华为OD】C卷真题200分:服务器广播 C/C++代码实现[思路+代码]-CSDN博客 【华为OD】C卷真题200分:服务器广播 Java代码实现[思路+代码]-CSDN博客 【华为OD】C卷真题200分:服务器广播 python代码实现[思路+代码]-CSDN博客 【华为OD】C卷真题200分:服务器广

    2024年03月25日
    浏览(54)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包