给定一个字符串str,str表示一个公式,公式里可能有整数、加减乘除符号和左右括号。返回公式的计算结果,难点在于括号可能嵌套很多层。str=“48((70-65)-43)+81",返回-1816。str="3+14”,返回7。str=“3+(14)",返回7。【说明】1.可以认为给定的字符串一定是正确的公式,即不需要对str做公式有效性检查。2.如果是负数,就需要用括号括起来,比如“4(-3)”但如果负数作为公式的开头或括号部分的开头,则可以没有括号,比如”-34"和"(-34)"都是合法的。3.不用考虑计算过程中会发生溢出的情况。 栈。对于递归函数。遇到左括号,递归调用;遇到右括号或者终止...
四数相加II。给你四个整数数组nums1、nums2、nums3和nums4,数组长度都是n,请你计算有多少个元组(i,j,k,l)能满足:0<=i,j,k,l<n;nums1[i]+nums2[j]+nums3[k]+nums4[l]0。力扣454。 nums1+nums2存map。然后求nums3+nums4,在map里找到相反数,就添加到结果里。时间复杂度:O(N2)。额外空间复杂度:O(N2)。 代码用golang编写。代码如下: packagemain import"fmt" funcmain(){ nums1:=[]int{1,2} nums2:=[]int{-...
考虑到只要有5,或者因子为5的数,就可以产生0的尾部。假如1234...250,那么250/5=50可以知道,有50个为5的倍数,但是里面有多少个为25的倍数,125的倍数..., 50/5=10,可知25的倍数有10个,10/5=2,可知125的倍数有两个,以此类推,代码如下: class Solution { public: // param n : description of n // re...
include<stdio.h> include<stdlib.h> include<math.h> defineINPUT_SIZE2 defineHIDDEN_SIZE3 defineOUTPUT_SIZE1 /定义神经元结构体/ typedefstruct_neuron{ doubleweights;//权重数组 doublebias;//偏置值 doubleoutput;//输出 }neuron; /定义隐藏层和输出层结构体/ typedefstruct_layer{ intsize;//层数 neuronneurons;//...
计算一个数组的子集 原题参照:Subset/子集 给你一个整数数组nums,数组中的元素互不相同。返回该数组所有可能的子集(幂集)。 解集不能包含重复的子集。你可以按任意顺序返回解集。 示例1: 输入:nums=[1,2,3] 输出:[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]] 示例2: 输入:nums=[0] 输出:[[],[0]] 解题思路 回溯法:确定子集是由长度为0size个数字组成,所以就分别求对应长度所有的子集的交集,就是最终的子集。重点是一个判断条件temp.size()0||(temp.size()>0&&...
打乱数组。给你一个整数数组nums,设计算法来打乱一个没有重复元素的数组。实现Solutionclass:Solutio(int[]nums)使用整数数组nums初始化对象;int[]reset()重设数组到它的初始状态并返回;int[]shuffle()返回数组随机打乱后的结果。力扣384。 第1次,1到N-1取随机数i1,[i1]与[N-1]交换。第2次,1到N-2取随机数i2,[i2]与[N-2]交换。遍历下去,就是打乱的数组了。时间复杂度:O(N)。额外空间复杂度:O(N)。因为有重置功能。 代码用golang编写。代码如下: packagemain import( "fmt" ...
我们之前讲的二阶段提交协议和Raft算法,它们都需要全部节点或者大多数节点正常运行,才能稳定运行。假如我们希望自己的系统能在极端情况下(比如集群中只有一个节点在运行)也能运行.我们要怎么办呢? 我们可以通过Gossip协议实现这个目标。 Gossip协议,顾名思义,就像流言蜚语一样,利用一种随机、带有传染性的方式,将信息传播到整个网络中,并在一定时间内,使得系统内的所有节点数据一致。对你来说,掌握这个协议不仅能很好地理解这种最常用的,实现最终一致性的算法,也能在后续工作中得心应手地实现数据的最终一致性。 我们先来了解Gossip三板斧,因为这是Gossip协议的核心内容,也是实现最终一致性...
经过上篇文章的学习,你应该知道,BasicPaxos只能就单个值(Value)达成共识,一旦遇到为一系列的值实现共识的时候,它就不管用了 兰伯特并没有把Multi-Paxos讲清楚,只是介绍了大概的思想,缺少算法过程的细节和编程所必须的细节(比如缺少选举领导者的细节)。这也就导致每个人实现的Multi-Paxos都不一样。不过从本质上看,大家都是在兰伯特提到的Multi-Paxos思想上补充细节,设计自己的Multi-Paxos算法,然后实现它(比如Chubby的Multi-Paxos实现、Raft算法、ZAB协议等)。 兰伯特提到的Multi-Paxos是一种思想,不是算法。而...
前言 提到分布式算法,就不得不提Paxos算法,在过去几十年里,它基本上是分布式共识的代名词,因为当前最常用的一批共识算法都是基于它改进的。比如,FastPaxos算法、CheapPaxos算法、Raft算法、ZAB协议等等。 兰伯特提出的Paxos算法包含2个部分: 一个是BasicPaxos算法,描述的是多节点之间如何就某个值(提案Value)达成共识; 另一个是Multi-Paxos思想,描述的是执行多个BasicPaxos实例,就一系列值达成共识 可因为兰伯特提到的Multi-Paxos思想,缺少代码实现的必要细节(比如怎么选举领导者),所以在理解上比较难。 BasicPaxo...
Example008 题目 构造串的链表结点数据结构(每个结点内存储一个字符),编写一个函数,找出串str1中第一个不在串str2中出现的字符。 分析 所谓串的链表结点数据结构,就是单链表,只不过存储的数据类型变成了char类型。 而本题的算法思想是:从头到尾扫描串str1,对于str1中的每一个结点判断是否在str2中出现,若出现,则继续扫描str1中的下一个字符;若没有出现,则返回当前检测的字符。如果str1中的所有字符都在str2中出现,则返回'\0'。 即双层for循环,算法思想是很简单,无非就是双层遍历。 图解 C实现 核心代码: /找出串str1中第一个不在串str2中出现的...
给你一个链表的头节点head,旋转链表,将链表每个节点向右移动k个位置。输入:head=1→2→3→4→5,k=2,输出:4→5→1→2→3。 1.找尾节点并且计算链表节点个数。2.如果k大于等链表节点个数,需要取模,k一定在[0,节点个数)范围之内。如果k=0,直接返回头节点。3.求倒数k+1的节点。4.缓存倒数第k节点ans。5.尾节点连头节点。6.倒数k+1节点的Next指针为空。7.返回ans。 代码用golang编写,代码如下: packagemain import"fmt" funcmain(){ head:=&ListNode{Val:1} head.Next=&...
按公因数计算最大组件大小。给定一个由不同正整数的组成的非空数组A,考虑下面的图:有A.length个节点,按从A[0]到A[A.length1]标记;只有当A[i]和A[j]共用一个大于1的公因数时,A[i]和A[j]之间才有一条边。返回图中最大连通组件的大小。 算出每个的公因数,然后并查集。时间复杂度:O(Nsqrt(V))。空间复杂度:O(N)。 代码用golang编写。代码如下: packagemain import( "fmt" "math" ) funcmain(){ arr:=[]int{2,3,6,7,4,12,21,39} ret:=largestComponentSi...
接雨水。给定n个非负整数表示每个宽度为1的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。 左右指针向中间移动。左指针是左边柱子最大高度,右指针是右边柱子最大高度。当左指针小于右指针时,左指针右移;当左指针大于等于右指针时,右指针左移。时间复杂度:O(N)。空间复杂度:O(1)。 代码用golang编写。代码如下: packagemain import"fmt" funcmain(){ height:=[]int{2,0,1,2} ret:=trap(height) fmt.Println(ret) } functrap(height[]int)int{ N:=len(he...
中心对称数III。中心对称数是指一个数字在旋转了180度之后看起来依旧相同的数字(或者上下颠倒地看)。写一个函数来计算范围在[low,high]之间中心对称数的个数。示例:输入:low=“50”,high=“100”,输出:3。解释:69,88和96是三个在该范围内的中心对称数。注意:由于范围可能很大,所以low和high都用字符串表示。来自力扣248。 假设low=264,high=3422。264到999的个数x,1000到9999的个数y,3422到9999的个数z。sum=x+y-z。如果high本身是有效数,sum=x+y-z+1。 代码用golang编写。代码如下: packa...