算法

左边升序右边降序的数组o1时间内计算不重复元素个数

问题 左边升序右边降序的数组o1时间内计算不重复元素个数 比如:[1,2,3,4,4,5,10,9,5,3,1,0], 返回8 要求:空间复杂度o(1), 时间复杂度o(n) 分析 讲真,从来没思考过o1空间复杂度下,要怎么破解这个问题。今天恰好遇到了,就思考下。太菜了,想了好久 下面讲讲思路吧 既然是有规律的升序降序数组,重复的元素都是连在一起的。那么我们顺序筛一遍就可以知道左半部分有多少重复,右半部分有多少重复。时间复杂度O(n),空间复杂度O(1) 左右两头比对,相等就计数器-1。不相等就看大小,右边大则右边下标-1,否则左边下标-1,继续比对。时间复杂度O(n),空间复杂度O(1) 实现代码 。。。。等我去测试下。。。 蛮高兴,自己测试了下,没啥问题 function process($array){ $len = count($array); $total = $len; $left = 0; $right = count($array)-1; // 空数组返回0 if($len < 2){ return $len; } // 去掉升序部分的重复,去掉降序部分的重复,O(n) // 两头开始检查,如果右边当前元素出现在左边,total-1 $pos = 0;...

合并两个升序数组A和B到数组A

题目 给出两个有序的整数数组A(长度m)和B(长度n) ,请将AB数组合并到数组A中,变成一个有序的数组。 算法思路 合并后数据总长度m+n,最后一个元素的位置为A[m+n-1] 从前(下标0)向后(下标m-1,n-1)合并需要挪动后续元素,复杂度高。因此,我们从后向前合并。 如何合并?初始化当前合并下标lastPos = m+n-1, 当前A数组下标posA = m-1, 当前B数组下标posB = n-1 逐个比大小,A[posA]和B[posB]取较大元素,放入A[lastPos]。取A数组,则posA--; 取B数组则posB--。同时lastPos-- 最后如果B数组有剩余,填入A数组即可 关于4和5,如果想问为什么这样就可以达到目的。注意观察,原始A数组中特定位置的数据,要么保持原位不变,要么会向后移动。因此,我们只需要取最大元素,放入lastPos即可 代码实现 public class Solution { public void merge(int A[], int m, int B[], int n) { int posA = m-1; int posB = n-1; int lastPos = m + n - 1; while(posA >= 0 && p...

整数数组中寻找第K大元素

算法思想 使用最大堆结构,最大堆的顶部总是最大元素。因此我们只需要构建一个最大堆,然后循环取K次堆顶就可以拿到目标元素。 堆是什么,怎么使用堆,这里不做讨论。 算法复杂度分析 构建堆:O(N) 取出K个元素,K常数,算法复杂度O(N) 上代码 import java.util.*; public class Finder { PriorityQueue<Integer> maxHeap; public int findKth(int[] a, int n, int K) { // write code here createHeap(a, n); int val = 0; for(int i=0; i<K; i++){ val = maxHeap.poll(); } return val; } public void createHeap(int[] a, int n){ maxHeap = new PriorityQueue<Integer>(new Comparator<Integer>() { @Override ...

反转链表

算法思想 初始条件,头结点不能为null,否则直接返回null 对于第i个节点,我们只要得到第i+1到last节点的逆序链表。假设第i+1到last节点的逆序链表的最后一个元素叫prev,那我们只要把prev.next设置为当前节点,并返回当前节点即可 对于最后一个节点last,last.next是null,我们直接返回last即可 以上三步可以逆序,但我们好像没保存新的头结点(原来的尾节点),第三部保存一下即可 上代码 /* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } }*/ public class Solution { protected ListNode newHead; public ListNode ReverseList(ListNode head) { if(head == null){ return null; } ListNode last = ReverseListRecursive(head); last.next = null; retur...

判断单链表中是否有环

算法核心思想 设置两只小狗,一个速度为1,另一只速度为2。小学相遇问题,很简单对吧。如果有环,第二只狗出发之后会追上第一只狗 退出条件 到达链表尾部 避免空指针 实现代码 public class Solution { public boolean hasCycle(ListNode head) { ListNode dog1 = head; // 狗1 ListNode dog2 = head; // 狗2 // 空指针判断 if(dog1 == null || dog2 == null){ return false; } // 退出条件: 空指针 while(dog1.next != null && dog2.next != null && dog2.next.next != null){ dog1 = dog1.next; dog2 = dog2.next.next; // 相遇,有环 if(dog1 == dog2){ return true; ...

用两个栈来实现队列

用两个栈来实现队列 算法思想 什么是栈,后进先出 什么是队列,先进先出 如果有两个栈,如何模拟队列先进先出?假设有三个元素ABC进入栈1,我们按照队列的要求,pop操作应该弹出A。但此时栈1的数据弹出顺序是CBA。解决方法:需要出栈的时候,先把栈1所有数据逐个pop,并push到栈2。最后从栈2出栈,那么我们就可以得到A了 我们把栈1数据全部弹到栈2,那么要入栈如何破?自然是把栈2数据逐个pop,并push进入栈1。最后在把当前数据push进栈1,就好了不是么 上代码 import java.util.Stack; public class Solution { Stack<Integer> stack1 = new Stack<Integer>(); Stack<Integer> stack2 = new Stack<Integer>(); public void push(int node) { int val; // stack2 => stacl1 while(!stack2.empty()){ val = stack2.pop(); stack1.push(val); }...

lintcode-4 丑数算法

题目 设计一个算法求出第n个只包含因子2,3,5的数。认为1也是丑数 比如输入9,则返回10;输入1,返回1 分析 只包含因子2,3,5,则这个数的形式就是F = (2^x) (3^y) (5^z), 限制条件x,y,z>=0 求出对应x,y,z即可 1th:x=y=z=0, F1 = (2^0) (3^0) (5^0) = 1 2th:x=1,y=z=0, F2 = 2 F1 = 2 3th:x=0,y=1,z=0, F3 = 3 F1 = 3 4th:x=2,y=0,z=0, F4 = 2 F2 = 4 5TH: x=0,y-0,z-1, F5 = 5 F1 = 5 对于第N个丑数,它的x+y+z < N-1 因子2,3,5的数量。 两个2相乘会大于3,因此增加一个2,就要对应增加一个3 一个2,一个3相乘,会大于5,。因此,增加一个2,3就需要替换成5 F1 = 1 迭代1:基底F1=1 F2 = F1 2 = 2(乘以2最小) F3 = F1 3 = 3(乘以3最小) F4 = F1 2 2 = 4(乘以2^2最小) F5 = F1 5 = 5(乘以5最小) F6 = F1 2 3 = 6(乘以23最小) F7 = F1 3 3 = 9(乘以3*3最小) 迭代2:基底 = F5=5 F8 = F5 2 = 10(乘以...

鸡兔同笼问题的一种解法

问题 假设有鸡和兔子总共80只,总共280只脚,问有多少只鸡,多少只兔子 解答 让所有的鸡和兔子抬起一只脚,那么还有280-80=200,还有200只脚在地上 让所有的鸡和兔子再抬起一只脚,那么地上还有200-80=120只脚。 这时候,所有的鸡已经坐在地上了。剩下的兔子还有两只脚着地,对应省的120只脚。 所以,笼子里120/2=60兔子 有80-60 = 20只鸡 公式化 假设有A和B两种动物。每只动物A有m只脚,每只动物B有n只脚,有m>n。假设A和B总共有S只,总共有脚P只。 那只要让所有动物抬起n只脚,剩下的酒都是动物A的脚。 剩下脚的数量为:P - Sn = 280 - 802 = 120 只脚 剩下的都是动物A,每只有m只脚,还有m-n只脚在地上 所以A动物有 x = (P - S*n)/(m-n) 只 = 120/(4-2) = 60 只 B动物有 y = S - x 只 = 80 - 60 = 20 只 x = (P - S*n)/(m-n) y = S - x

背包九讲1之01背包

九个问题 01背包 完全背包 多重背包 混合背包 二维混合背包 分组背包 背包问题求方案熟 求背包问题的方案 有依赖的背包 感谢: https://www.youtube.com/watch?v=nleY0-eexps 01背包 问题描述 问题描述 有N件物品和一个容量V的背包,第i件物品体积vi,价值是wi. 求解将那些物品装入背包,可是这些物品总体积不超过背包容量,且总价值最大 输入格式 第一行两个整数, N和V, 用空格隔开, 分别表示物品数量和背包容积 接下来有N行, 每行有两个整数vi, wi, 分别表示第i件物品的体积和价值 输出格式 一个整数, 表示最大价值 数据范围 0 < N, V <1000 0 < vi, wi < 1000 输入样例 4 5 1 2 2 4 3 4 4 5 输出样例 8 算法分析 我们用一个二维数组f[n][m]存储所有状态,n表示商品总数,m表示背包容量。m,n > 0 f[i][j]表示只考虑前i个物品,总体积是j的情况下,总价值最大是多少 i,j取值范围 0<i<=n, 至少一个商品,之多n个商品; 0<=j<=m,重量最小可以是0(刚好用完),最大可以是m 如何求解f[i][j]? 对于每一个f[i][j], 我们哟两种选择, 不选择它或者选泽它。 不选第i个商品...

袋鼠从起点开始跳,问到终点有多少种不同的跳跃方式

题目 有一只袋鼠,它跳跃一次的方式只有两种:①一次跳1米 ②一次跳3米,现在有一段10米长的路,袋鼠从起点开始跳,问到终点有多少种不同的跳跃方式? 方法1:生成二叉树生成 每一步有两种选择:1米或者3米,所以解集是一棵二叉树,每一个节点代表一种选择。 假设当前运动位置是S,则S = sum(根节点 + ... +当前节点)。(我不知道markdown如何打数学公式,google出来的都没成功,凑合着看吧) 当前运动位置 > 10m,说明路走完了。结束当前路径搜索。 遍历二叉树,找到所有sum <?php const TOTAL_STEP = 10; const OPTION_STEP1 = 1; const OPTION_STEP3 = 3; $table = []; $count = 0; // 生成遍历二叉树 function gene1($path, $dist){ global $table; global $count; $path1 = 0; $path2 = 0; $count += 1; if($dist < TOTAL_STEP){ $path1 = $path . OPTION_STEP1; $set1 = gene1($path1, $dist +...
执行时间: 41.836977005005 毫秒