前言
新的一年，好好学习。
正文
问题来源
本问题来自leetcode上的240题。
问题描述
编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性：
每行的元素从左到右升序排列。
每列的元素从上到下升序排列。
示例 1：
[
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]
给定 target = 5，返回 true。
给定 target = 20，返回 false。
分析：
每一行二分
func binary_search(array []int,target int) bool {
l := len(array)
left, right := 0, l-1
mid := (left+right) / 2
if 0 == l {
return false
}
for ;left <= right ; mid = (left+right)/2 {
cur := array[mid]
if cur == target {
return true
} else if cur > target {
right = mid - 1
} else {
left = mid + 1
}
}
return false
}
func searchMatrix(matrix [][]int, target int) bool {
l := len(matrix)
if 0 == l {
return false
}
for i := 0; i < l; i++ {
if binary_search(matrix[i], target) {
return true
}
}
return false
}
从matrix的右上角向左向右查找
func countSubstrings(s string) int {
ans := 0
for i := 0; i < len(s); i++ {
for j := 0; (i-j>=0)&&(i+j<len(s))&&(s[i-j]==s[i+j]); j++ {
ans++
}
for j := 0; (i-j-1>=0)&&(i+j<len(s))&&(s[i-j-1]==s[i+j]); j++ {
ans++
}
}
return ans
}
将矩阵分成四份，二分查找
func searchMatrix(matrix [][]int, target int) bool {
return (len(matrix) > 0) && binarySearch2D(matrix, target, 0, 0, len(matrix)-1, len(matrix[0])-1)
}
func binarySearch2D(M [][]int, T int, top, left, bottom, right int) bool {
m, c := (top+bottom)/2, (left+right)/2
switch {
case top > bottom || left > right:
case M[m][c] == T:
return true
case M[m][c] < T:
return binarySearch2D(M, T, m+1, left, bottom, c) ||
binarySearch2D(M, T, top, c+1, bottom, right)
case M[m][c] > T:
return binarySearch2D(M, T, top, left, bottom, c-1) ||
binarySearch2D(M, T, top, c, m-1, right)
default:
}
return false
}
总结：
勤思考。
结语
不管怎么样好好加油。
