数组和字符串
寻找数组的中心索引.
本来使用暴力破解方法， 但是实在是，看不下去了，想了半个小时终于想出来一个，我觉得还算好的办法。请参看注释。
func pivotIndex(nums []int) int {
length := len(nums)
sumRight := 0
sumLeft := 0
sum := 0
//count all the values to one
for i := 0 ; i < length ; i ++ {
sum += nums[i]
}
//we have a sum for all the values counts, and then we use {right = (all-currentPos-left)}
//if right == left , then we retrun the position.
for pos := 0 ; pos < length ; pos++ {
if pos != 0 {
sumLeft += nums[pos-1]
}
sumRight = sum - nums[pos] - sumLeft
if sumRight == sumLeft {
return pos
}
}
return -1
}
至少是其他数字两倍的最大数
func dominantIndex(nums []int) int {
first , second := -1 , -1
pos := -1
//Find the first and second bigger number in the array , if the first > 2*second, then we can return the position.
for i := 0 ; i < len(nums) ; i++ {
if first < nums[i] {
second = first
first = nums[i]
pos = i
} else if second < nums[i] {
second = nums[i]
}
}
if first >= second * 2{
return pos
}
return -1
}
加一
func plusOne(digits []int) []int {
length := len(digits)
//do this just like we do the plus when we are young
for i:= length -1 ; i >= 0 ; i-- {
//if digits[i]<9 then we could just do digits[i]++
if digits[i] < 9 {
digits[i]++
return digits
}
digits[i] = 0
}
res := []int{1}
res = append(res , digits...)
return res
}
对角线遍历
func findDiagonalOrder(matrix [][]int) []int {
//if the array is empty just return empty one.
if len(matrix) == 0 {
return []int{}
}
/*
at the first , it will goes up right , then (row - 1) and (column + 1) ,if we meet the border then (row + 1) (column - 1)
How to handle border.
if go up right , when get the up but not right border , then go right (row + 0) and (cloumn + 1), if not then go down (row + 1)(column + 0)
if go down left , when get the left but not down border , then go down (row + 1)(cloumn + 0) , if not then go right (row + 0)(cloumn + 1)
*/
row , column := 0, 0
m, n := len(matrix), len(matrix[0])
ret := make([]int, m*n)
for i := 0; i < m*n; i++ {
ret[i] = matrix[row][column]
if (row + column)%2 == 0 {
if column == n-1 {
row++
} else if row == 0 {
column++
} else {
row--
column++
}
} else {
if row == m-1 {
column++
} else if column == 0 {
row++
} else {
row++
column--
}
}
}
return ret
}
实现strStr()
func strStr(haystack string, needle string) int {
//regarding the problem tips , we know when needle is nil we return 0; and if haystck == needle also return 0
if len(needle) == 0 || haystack == needle {
return 0
}
length := len(needle)
//becareful array out of range. so we need len(haystack) - length
for i := 0 ; i <= (len(haystack) - length) ;i++ {
if haystack[i:i+length] == needle {
return i
}
}
return -1
}
最长公前缀
func longestCommonPrefix(strs []string) string {
if len(strs) == 0{
return ""
}
prefix := strs[0]
length := len(strs)
for i := 1; i < length; i++ {
str := strs[i]
for !strings.HasPrefix(str, prefix){
if len(prefix) == 1 {
prefix = ""
break
}
prefix = prefix[0:len(prefix)-1]
}
}
return prefix
}
字符串翻转
func reverseString(s []byte) {
for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
s[i], s[j] = s[j], s[i]
}
}
数组拆分I
func arrayPairSum(nums []int) int {
sort.Ints(nums)
ret := 0
//sort the array first then we put all odds togother.
for i := 0; i < len(nums); i += 2 {
ret += nums[i]
}
return ret
}
两数之和II
func twoSum(numbers []int, target int) []int {
//start from left and right.
left, right := 0, len(numbers)-1
for left < right {
if numbers[left]+numbers[right] < target {
left++
} else if numbers[left]+numbers[right] > target {
right--
} else {
return []int{left + 1, right + 1}
}
}
return nil
}
移除元素
func removeElement(nums []int, val int) int {
if nums == nil {
return 0
}
for i := 0; i < len(nums); {
if nums[i] == val {
nums = append(nums[:i], nums[i+1:]...)
i--
}
i++
}
return len(nums)
}
最大连续1的个数
func findMaxConsecutiveOnes(nums []int) int {
if (nums == nil) {
return 0
}
max := 0
temp := 0
for i := 0 ;i < len(nums) ;i++ {
if nums[i] == 1 {
temp++
} else {
if temp > max {
max = temp
}
temp = 0
}
}
//this part was stuck for more than 30 mins.
//this part controls test case like [1] , [0,1] this two are so special
if temp > max {
max = temp
}
return max
}
杨辉三角形II
func getRow(rowIndex int) []int {
ret := make([]int, rowIndex+1)
for k := range ret {
ret[k] = 1
}
for i := 0; i < rowIndex-1; i++ {
for j := i + 1; j >= 1; j-- {
ret[j] = ret[j] + ret[j-1]
}
}
return ret
}
翻转字符串里的单词
func reverseWords(s string) string {
arr := strings.Split(s, " ")
res := []string{}
for i := 0; i < len(arr); i++ {
if arr[i] != "" {
res = append(res, arr[i])
}
}
for i, j := 0, len(res)-1; i < j; i, j = i+1, j-1 {
res[i], res[j] = res[j], res[i]
}
return strings.Replace(strings.Trim(fmt.Sprint(res), "[]"), " ", " ", -1)
}
翻转单词III
func reverseWords(s string) string {
sp := strings.Split(s, " ")
ret := ""
for i := 0; i < len(sp); i++ {
t := make([]byte, len(sp[i]))
for left, right := 0, len(sp[i])-1; left <= right; left, right = left+1, right-1 {
t[left], t[right] = sp[i][right], sp[i][left]
}
ret += string(t)
if i != len(sp)-1 {
ret += " "
}
}
return ret
}
移动零
func moveZeroes(nums []int) {
index := 0
for i:= 0 ; i < len(nums) ; i++ {
if(nums[i] != 0) {
nums[index] = nums[i]
index++
}
}
for index < len(nums) {
//diffrent from c/c++ you can't use nums[index++] here
nums[index] = 0
index++
}
}
网友评论