Commit78b9574

authored

Merge pull request6boris#86 from kylesliu/develop

add the 74 problem solution

2 parents50f187c +2295eaa commit78b9574Copy full SHA for 78b9574

File tree

+57

-19

lines changed

+57

-19

lines changed

Lines changed: 23 additions & 8 deletions

Original file line number	Diff line number	Diff line change
`@@ -23,21 +23,36 @@ Output: "10101"`
`23`	`23`	`Tags: Math, String`
`24`	`24`
`25`	`25`	`##题意`
`26`		`->给你两个二进制串，求其和的二进制串。`
	`26`	`+>写一个高效算法，在矩阵中查找一个数是否存在。矩阵有如下特点：`
	`27`	`+- 矩阵中每行的数，从左到右单调递增；`
	`28`	`+- 每行行首的数大于上一行行尾的数；`
`27`	`29`
`28`	`30`	`##题解`
`29`	`31`
`30`	`32`	`###思路1`
`31`		->按照小学算数那么来做，用`carry` 表示进位，从后往前算，依次往前，每算出一位就插入到最前面即可，直到把两个二进制串都遍历完即可。
	`33`	`+>我们可以想象把整个矩阵，按行展开成一个一维数组，那么这个一维数组单调递增，然后直接二分即可。`
	`34`	`+ 二分时可以通过整除和取模运算得到二维数组的坐标。`
	`35`	`+ 时间复杂度分析：二分的时间复杂度是 O(logn2)=O(logn)O(logn2)=O(logn)。`
`32`	`36`
`33`		-```go
`34`		`-`
`35`		-```
`36`	`37`
`37`		`-###思路2`
`38`		`->思路2`
`39`	`38`	```go
`40`		`-`
	`39`	`+funcsearchMatrix(matrix [][]int,targetint)bool {`
	`40`	`+iflen(matrix) ==0 {`
	`41`	`+returnfalse`
	`42`	`+}`
	`43`	`+n,m:=len(matrix),len(matrix[0])`
	`44`	`+l,r:=0, n*m-1`
	`45`	`+`
	`46`	`+for l < r {`
	`47`	`+mid:= (l + r) /2`
	`48`	`+if matrix[mid/m][mid%m] >= target {`
	`49`	`+r = mid`
	`50`	`+}else {`
	`51`	`+l = mid +1`
	`52`	`+}`
	`53`	`+}`
	`54`	`+return matrix[r/m][r%m] == target`
	`55`	`+}`
`41`	`56`	```
`42`	`57`
`43`	`58`	`##结语`

Lines changed: 16 additions & 2 deletions

Original file line number	Diff line number	Diff line change
`@@ -1,5 +1,19 @@`
`1`	`1`	`package Solution`
`2`	`2`
`3`		`-funcSolution(xbool)bool {`
`4`		`-returnx`
	`3`	`+funcsearchMatrix(matrix [][]int,targetint)bool {`
	`4`	`+iflen(matrix)==0 {`
	`5`	`+returnfalse`
	`6`	`+}`
	`7`	`+n,m:=len(matrix),len(matrix[0])`
	`8`	`+l,r:=0,n*m-1`
	`9`	`+`
	`10`	`+forl<r {`
	`11`	`+mid:= (l+r)/2`
	`12`	`+ifmatrix[mid/m][mid%m]>=target {`
	`13`	`+r=mid`
	`14`	`+}else {`
	`15`	`+l=mid+1`
	`16`	`+}`
	`17`	`+}`
	`18`	`+returnmatrix[r/m][r%m]==target`
`5`	`19`	`}`

Lines changed: 18 additions & 9 deletions

Original file line number	Diff line number	Diff line change
`@@ -2,28 +2,37 @@ package Solution`
`2`	`2`
`3`	`3`	`import (`
`4`	`4`	`"reflect"`
	`5`	`+"strconv"`
`5`	`6`	`"testing"`
`6`	`7`	`)`
`7`	`8`
`8`	`9`	`funcTestSolution(t*testing.T) {`
`9`	`10`	`//测试用例`
`10`	`11`	`cases:= []struct {`
`11`	`12`	`namestring`
`12`		`-inputsbool`
	`13`	`+matrix [][]int`
	`14`	`+targetint`
`13`	`15`	`expectbool`
`14`	`16`	`}{`
`15`		`-{"TestCacse 1",true,true},`
`16`		`-{"TestCacse 1",true,true},`
`17`		`-{"TestCacse 1",false,false},`
	`17`	`+{"TestCase", [][]int{`
	`18`	`+{1,3,5,7},`
	`19`	`+{10,11,16,20},`
	`20`	`+{23,30,34,50},`
	`21`	`+},3,true},`
	`22`	`+{"TestCase", [][]int{`
	`23`	`+{1,3,5,7},`
	`24`	`+{10,13,16,20},`
	`25`	`+{23,30,34,50},`
	`26`	`+},13,true},`
`18`	`27`	`}`
`19`	`28`
`20`	`29`	`//开始测试`
`21`		`-for_,c:=rangecases {`
`22`		`-t.Run(c.name,func(t*testing.T) {`
`23`		`-ret:=Solution(c.inputs)`
`24`		`-if!reflect.DeepEqual(ret,c.expect) {`
	`30`	`+fori,c:=rangecases {`
	`31`	`+t.Run(c.name+" "+strconv.Itoa(i),func(t*testing.T) {`
	`32`	`+got:=searchMatrix(c.matrix,c.target)`
	`33`	`+if!reflect.DeepEqual(got,c.expect) {`
`25`	`34`	`t.Fatalf("expected: %v, but got: %v, with inputs: %v",`
`26`		`-c.expect,ret,c.inputs)`
	`35`	`+c.expect,got,c.matrix)`
`27`	`36`	`}`
`28`	`37`	`})`
`29`	`38`	`}`

Comments

(0)