深圳建工集团,seo网站关键词优化费用,Wordpress首页制作代码,网站代理工具#x1f3a5; 个人主页#xff1a;Dikz12#x1f525;个人专栏#xff1a;Java算法#x1f4d5;格言#xff1a;那些在暗处执拗生长的花#xff0c;终有一日会馥郁传香欢迎大家#x1f44d;点赞✍评论⭐收藏
目录
1. 移动零
1.1 题目描述
1.2 讲解算法原理 1.3 编… 个人主页Dikz12个人专栏Java算法格言那些在暗处执拗生长的花终有一日会馥郁传香欢迎大家点赞✍评论⭐收藏
目录
1. 移动零
1.1 题目描述
1.2 讲解算法原理 1.3 编写代码 2. 复写零
2.1 题目描述
2.2 讲解算法原理
2.3代码实现
3. 盛最多水的容器
3.1 题目描述
3.2 讲解算法原理
3.3 代码实现
4.有效三角形的个数
4.1 题目描述
4.2 讲解算法原理
4.3代码实现 1. 移动零
1.1 题目描述 1.2 讲解算法原理 这种题型可以划分到数组划分、数组分块. 解决这类题就有最经典的算法双指针算法. 定义两个指针作用
cur从左到右扫描数组遍历数组.dest在已处理区间内非0元素的最后一个位置.
如图数组被划分成了三个区间[0,dest]非0 [dest1cur-1]0[curn-1]待处理.
做到代码按照上面思路走即可.
cur从前往后遍历的过程中
遇到0元素cur遇到非0元素交换dest1和cur的值 1.3 编写代码 public void moveZeroes(int[] nums) {int dest -1;for(int cur 0;cur nums.length; cur) {if(nums[cur] ! 0) {dest;int tmp nums[cur];nums[cur] nums[dest];nums[dest] tmp; }}} 2. 复写零
2.1 题目描述 2.2 讲解算法原理 思路 如果「从前向后」进⾏原地复写操作的话由于 0 的出现会复写两次导致没有复写的数「被覆 盖掉」。 因此我们选择「从后往前」的复写策略。 但是「从后向前」复写的时候我们需要找到「最后⼀个复写的数」因此我们的⼤体流程分两 步 先找到最后⼀个复写的数然后从后向前进⾏复写操作 整体流程
初始化两个指针 cur 0dest -1;找到最后一个复写的数当cur n时,判断cur位置的元素是0的话dest,往后移动两步不为0移动一位当dest走到最后一个位置或者等于数组长度就breadk结束循环,否则cur判断dest是否越界.越界让最后一个位置的元素改成0cur向前移动一位dest 移动两位从cur的位置开始往前遍历数组cur 为0把dest 和 dest -1位置的元素都改成0移动两位cur 不为0dest位置的元素改为cur的dest - -cur--
2.3代码实现 public void duplicateZeros(int[] arr) {int cur 0, dest -1, n arr.length;//1.找到复写之后数组的最后一个数while(cur n) {if(arr[cur] 0) {dest 2;}else{dest 1;}if(dest n-1) {break;}cur;}//处理dest越界问题if(dest n) {arr[n-1] 0;dest - 2;cur --;}//2.从后往前完成复写操作while(cur 0){if(arr[cur] ! 0){arr[dest--] arr[cur--];}else{arr[dest--] 0;arr[dest--] 0;cur--;}}}
3. 盛最多水的容器
3.1 题目描述 数组放的是高度第0条线的高度是1第1条线的高度是8........(对应的数组下标)。 如图容器的height是由较低的的那条线决定的而宽度这好等于右边下标减去左边下标. 3.2 讲解算法原理
解方法一 暴力枚举.O(n^2)
先固定最左边的线1依次枚举右边的线所有容器都算一遍记录最大值在固定8重复上诉过程. 解法二 利用单调性使用双指针解决.
取一部分区间进行模拟[625,4]刚开始直接拿4和6进行计算V h 高* w (宽) 假设4在向内枚举2和5时不难发现宽始终在减少高会有两种情况遇见小的数h 减少w 减少v一定减少遇到大的数h 不变w减少v减少那较小的数向内枚举v 始终是减少的.所以可以直接把4干掉. 整体过程 定义两个指针left 指向最左边right 指向最右边,初始容积为ret 0高度取min(left,right),并记录目前的容积v在max(v,ret)记录最大容积左边高度小于右边left--; 否则right (相同移动哪边都一样). 3.3 代码实现 public int maxArea(int[] height) {int left 0,right height.length - 1,ret 0;while(left right) {int v Math.min(height[left],height[right]) * (right - left);ret Math.max(ret,v);if(height[left] height[right]) {left;}else {right--;}}return ret;}
4.有效三角形的个数
4.1 题目描述 4.2 讲解算法原理
解法一暴力解法.O(n^3)
三层for循环一层固定一个数 .
伪代码
for(i 0; i n; i)for(j i 1; j n; j)for(int k j 1; k n; k)check(i,j,k)
解法二 利用单调性使用双指针来解决问题. 如图假设选取的三个数是有序的就会发现第二种情况和第三种情况下C已经是最大值了无论加谁都是大于第三个数的. 对数组进行排序开始count 统计个数 固定一个最大的数最右边left指向最左边 right 指向最大数减一的位置.在最大数区间内使用双指针算法快速统计符合要求的个数. (循环上图过程
4.3代码实现 public int triangleNumber(int[] nums) {//排序Arrays.sort(nums);int count 0,n nums.length;//利⽤双指针快速统计出符合要求的个数for(int i n - 1; i 2; i--) {int left 0,right i - 1;while(left right) {if(nums[left] nums[right] nums[i]) {count right - left;right--;}else{left;}}}return count;}
