本文主要是介绍左程云算法 - 公开课笔记,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
第五节
题目:原地交换,不允许额外的空间
方法1:复杂度O(N/2)
1、左侧逆序
2、右侧逆序
3、整体逆序
方法2:循环右移
复杂度O(N^2)
方法3:
直到左右等长的时候,就不再交换了
第六节
方法一:暴力
方法二:一种不是最优解的解法:先对绝对值进行排序,再比较前后数字是否相同
方法三:最优解,双指针原理
两头指针,谁的绝对值大,谁动
首尾指针:划过的数字,可以保证以后再也不会出现这个结果
如果只关注所有波峰波谷的话,可能会出现波峰波谷失效的状态。
变换思路:求某一个位置i上方有多少水
暴力解法O(n^2)
怎么找左边和右边最大值?
生成某前缀数组最大值,作为预处理结构:
因为left辅助结构本身就是从左往右遍历的,所以在计算水量遍历时,可以用一个变量维持左侧已经遍历过部分的最大值,就没有必要另外维护一个left数组了,相当于在线计算left数组
彻底不用辅助结构,用双指针,时间复杂度仍为O(n)的解法:
leftmax、rightmax两个最大值,哪边最大值小,结算哪一边的水量。
移动的时候,更新自己一侧的最大值
当左侧最大值小于右侧最大值的时候,结算左侧水量,往右移动;
…
直到最后,两个指针相遇,停止。
对数器验证
这篇关于左程云算法 - 公开课笔记的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!