前言
Leetcode里面的20天演算法刷題計劃中的演算法入門部分的31道題，使用Go語言，
704. 二分查找
package question704
func Search(nums []int, target int) int {
start,end := 0,len(nums)-1
for start <= end {
mid := (start+end)/2
if nums[mid] == target {
return mid
}else if nums[mid] < target {
start = mid+1
}else {
end = mid-1
}
}
return -1
}
278. 第一個錯誤的版本
package question278
/**
* Forward declaration of isBadVersion API.
* @param version your guess about first bad version
* @return true if current version is bad
* false if current version is good
* func isBadVersion(version int) bool;
*/
func firstBadVersion(n int) int {
start,end := 1,n
for start <= end {
mid := start + (end-start)/2
if isBadVersion(mid) {
end = mid-1
}else {
start = mid + 1
}
}
return start
}
35. 搜索插入位置
package question35
func searchInsert(nums []int, target int) int {
start,end := 0,len(nums)-1
for start <= end {
mid := (start+end)/2
if nums[mid] == target {
return mid
}else if nums[mid] < target {
start = mid+1
}else {
end = mid-1
}
}
return -1
}
977. 有序陣列的平方
package question977
func sortedSquares(nums []int) []int {
var index int = len(nums)-1
res := make([]int,len(nums))
left,right := 0,len(nums)-1
for left<=right {
if nums[left]*nums[left] >= nums[right]*nums[right] {
res[index] = nums[left]*nums[left]
left++
}else{
res[index] = nums[right]*nums[right]
right--
}
index--
}
return res
}
189. 輪轉陣列
package question189
func rotate(nums []int, k int) {
n := len(nums)
k = k%n
reverse(nums)
reverse(nums[:k])
reverse(nums[k:])
}
func reverse(nums []int){
n := len(nums)
for i:=0;i<n/2;i++{
temp := nums[i]
nums[i]=nums[n-i-1]
nums[n-i-1] = temp
}
}
283. 移動零
package question283
func moveZeroes(nums []int) {
left,right,n := 0,0,len(nums)
for right < n {
if nums[right] != 0 {
nums[left],nums[right] = nums[right],nums[left]
left++
}
right++
}
}
167. 兩數之和 II - 輸入有序陣列
package question167
func twoSum(numbers []int, target int) []int {
n := len(numbers)
left,right := 0,n-1
for left<right {
sum := numbers[left]+numbers[right]
if sum==target {
return []int{left+1,right+1}
}else if sum<target {
left++
}else {
right--
}
}
return []int{}
}
344. 反轉字串
package question344
func reverseString(s []byte) {
n := len(s)
for i:=0;i<(n>>1);i++{
s[i],s[n-i-1] = s[n-i-1],s[i]
}
}
557. 反轉字串中的單詞 III
package question557
import "strings"
func reverseString(s []byte) string{
n := len(s)
for i:=0;i<(n>>1);i++{
s[i],s[n-i-1] = s[n-i-1],s[i]
}
return string(s)
}
func reverseWords(s string) string {
ss := strings.Split(s," ")
for i:=0;i<len(ss);i++ {
ss[i] = reverseString([]byte(ss[i]))
}
return strings.Join(ss," ")
}
876. 鏈表的中間結點
package question876
type ListNode struct {
Val int
Next *ListNode
}
func middleNode(head *ListNode) *ListNode {
var leftNode,rightNode *ListNode = head,head
for {
if rightNode.Next==nil {
return leftNode
}else{
rightNode = rightNode.Next.Next
leftNode = leftNode.Next
}
if rightNode==nil {
return leftNode
}
}
}
19. 洗掉鏈表的倒數第 N 個結點
package question19
type ListNode struct {
Val int
Next *ListNode
}
func removeNthFromEnd(head *ListNode, n int) *ListNode {
hhead := &ListNode{0,head}
left,right := hhead,head
for i:=0;i<n;i++ {
right = right.Next
}
for ;right!=nil;left=left.Next {
right = right.Next
}
left.Next = left.Next.Next
return hhead.Next
}
/*func removeNthFromEnd(head *ListNode, n int) *ListNode {
left,right := head,head
for i:=0;i<n;i++ {
right = right.Next
}
if right==nil {
return head.Next
}
for ;right.Next!=nil;left=left.Next {
right = right.Next
}
left.Next = left.Next.Next
return head
}*/
3. 無重復字符的最長子串
package question3
func max(x,y int) int{
if x>y{
return x
}else{
return y
}
}
/*func lengthOfLongestSubstring(s string) int {
n := len(s)
mmax := max(n,128)
maxLength := 0
left,right := 0,0
for ;left<n;left++ {
myMap := make(map[byte]int)
for right=left;right<n&&right-left<mmax;right++ {
if myMap[s[right]]>0 {
break
}
myMap[s[right]]++
}
maxLength = max(maxLength,right-left)
if right==n {
return maxLength
}
left += strings.Index(string([]byte(s)[left:right]), string(s[right]))
fmt.Println(left)
}
return maxLength
}*/
func lengthOfLongestSubstring(s string) int {
n := len(s)
mmax := max(n,128)
maxLength := 0
myMap := make(map[byte]int)
left,right := 0,0
for ;left<n;left++ {
if left != 0 {
myMap[s[left-1]]--
}
for ;right<n&&right-left<mmax;right++ {
if myMap[s[right]]>0 {
break
}
myMap[s[right]]++
}
maxLength = max(maxLength,right-left)
}
return maxLength
}
567. 字串的排列
package question567
import "fmt"
func checkInclusion(s1 string, s2 string) bool {
n1, n2 := len(s1), len(s2)
if n1>n2 {
return false
}
myMap := make(map[byte]int)
for i := 0; i < n1; i++ {
myMap[s1[i]]++
myMap[s2[i]]--
}
var diff int = 0
for _,k :=range myMap{
if k!=0 {
diff++
}
}
if diff==0 {
return true
}
for i := n1; i < n2; i++ {
if myMap[s2[i-n1]]==0 {
diff++
}
myMap[s2[i-n1]]++
if myMap[s2[i-n1]]==0 {
diff--
}
if myMap[s2[i]]==0 {
diff++
}
myMap[s2[i]]--
if myMap[s2[i]]==0 {
diff--
}
fmt.Println(diff)
if diff == 0 {
return true
}
}
return false
}
/*func checkInclusion(s1 string, s2 string) bool {
n1, n2 := len(s1), len(s2)
if n1>n2 {
return false
}
map1 := make(map[byte]int)
map2 := make(map[byte]int)
for i := 0; i < n1; i++ {
map1[s1[i]]++
map2[s2[i]]++
}
var fflag bool = true
for k, v := range map1 {
if map2[k]!=v {
fflag = false
}
}
if fflag==true {
return true
}
fmt.Println(map1)
for i := 1; i < n2-n1+1; i++ {
map2[s2[i-1]]--
map2[s2[i+n1-1]]++
fmt.Println(map1)
var flag bool = true
for k, v := range map1 {
if map2[k]!=v {
flag = false
}
}
if flag==true {
return true
}
}
return false
}
*/
733. 影像渲染
package question733
//BFS
func floodFill(image [][]int, sr int, sc int, newColor int) [][]int {
target := image[sr][sc]
if target == newColor {
return image
}
image[sr][sc] = newColor
queue := [][]int{}
xx := []int{-1, 0, 0, 1}
yy := []int{0, -1, 1, 0}
queue = append(queue, []int{sr, sc})
for i := 0; i < len(queue); i++ {
nowEle := queue[i]
for j := 0; j < 4; j++ {
mx, my := nowEle[0]+xx[j], nowEle[1]+yy[j]
if mx >= 0 && my >= 0 && mx < len(image) && my < len(image[0]) && image[mx][my] == target {
image[mx][my] = newColor
queue = append(queue, []int{mx, my})
}
}
}
return image
}
695. 島嶼的最大面積
package question695
func maxAreaOfIsland(grid [][]int) int {
res := 0
xx := []int{-1, 0, 0, 1}
yy := []int{0, -1, 1, 0}
for i := 0;i<len(grid);i++ {
for j := 0;j<len(grid[i]);j++ {
if grid[i][j]==0 {
continue
}
nowArea := 1
queue := [][]int{}
queue = append(queue,[]int{i,j})
grid[i][j] = 0
for k := 0; k < len(queue);k++ {
nowEle := queue[k]
for p := 0; p < 4; p++ {
mx, my := nowEle[0]+xx[p], nowEle[1]+yy[p]
if mx >= 0 && my >= 0 && mx < len(grid) && my < len(grid[0]) && grid[mx][my] != 0 {
grid[mx][my] = 0
nowArea++
queue = append(queue, []int{mx, my})
}
}
}
if nowArea>res {
res = nowArea
}
}
}
return res
}
617. 合并二叉樹
package question617
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
//深度優先搜索
func mergeTrees(root1 *TreeNode, root2 *TreeNode) *TreeNode {
if root1==nil {
return root2
}else if root2==nil {
return root1
}
root1.Val = root1.Val+root2.Val
root1.Left = mergeTrees(root1.Left,root2.Left)
root1.Right = mergeTrees(root1.Right,root2.Right)
return root1
}
116. 填充每個節點的下一個右側節點指標
package question116
type Node struct {
Val int
Left *Node
Right *Node
Next *Node
}
func connect(root *Node) *Node {
if root == nil {
return root
}
if root.Left != nil {
root.Left.Next = root
root.Right.Next = root
}
if root.Next != nil {
if root.Next.Right != root {
root.Next = root.Next.Right
} else if root.Next.Next == nil {
root.Next = nil
} else {
root.Next = root.Next.Next.Left
}
}
connect(root.Left)
connect(root.Right)
return root
}
542. 01 矩陣
package question542
func updateMatrix(mat [][]int) [][]int {
n,m := len(mat),len(mat[0])
queue := [][]int{}
hasDeal := make([][]int,n)
for k,_ := range hasDeal{
hasDeal[k] = make([]int,m)
}
for i:=0;i<n;i++ {
for j:=0;j<m;j++ {
if mat[i][j]==0 {
queue = append(queue, []int{i,j})
hasDeal[i][j] = 1
}
}
}
xx := []int{-1,1,0,0}
yy := []int{0,0,-1,1}
for i:=0;i<len(queue);i++ {
nowElem := queue[i]
for j:=0;j<4;j++ {
mx,my := nowElem[0]+xx[j],nowElem[1]+yy[j]
if mx>=0&&my>=0&&mx<n&&my<m&&hasDeal[mx][my]==0 {
hasDeal[mx][my] = hasDeal[nowElem[0]][nowElem[1]]+1
mat[mx][my] = hasDeal[mx][my]-1
queue = append(queue, []int{mx,my})
}
}
}
return mat
}
994. 腐爛的橘子
package question994
func orangesRotting(grid [][]int) int {
n,m := len(grid),len(grid[0])
queue := [][]int{}
hasDeal := make([][]int,n)
for k,_ := range hasDeal{
hasDeal[k] = make([]int,m)
}
freshNum := 0
for i:=0;i<n;i++ {
for j:=0;j<m;j++ {
if grid[i][j]==2 {
queue = append(queue, []int{i,j})
hasDeal[i][j] = 1
}else if grid[i][j]==1 {
freshNum++
}
}
}
if freshNum==0 {
return 0
}
xx := []int{-1,1,0,0}
yy := []int{0,0,-1,1}
var res int
for i:=0;i<len(queue);i++ {
nowElem := queue[i]
for j:=0;j<4;j++ {
mx,my := nowElem[0]+xx[j],nowElem[1]+yy[j]
if mx>=0&&my>=0&&mx<n&&my<m&&hasDeal[mx][my]==0&&grid[mx][my]==1 {
hasDeal[mx][my] = hasDeal[nowElem[0]][nowElem[1]]+1
res = hasDeal[mx][my]-1
grid[mx][my] = 2
freshNum--
queue = append(queue, []int{mx,my})
}
}
}
if freshNum!=0 {
return -1
}
return res
}
21. 合并兩個有序鏈表
package question21
type ListNode struct {
Val int
Next *ListNode
}
func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
if list1==nil {
return list2
}else if list2==nil {
return list1
}
if list1.Val<list2.Val {
list1.Next = mergeTwoLists(list1.Next,list2)
return list1
}else{
list2.Next = mergeTwoLists(list1,list2.Next)
return list2
}
}
206. 反轉鏈表
package question206
type ListNode struct {
Val int
Next *ListNode
}
//迭代
func reverseList(head *ListNode) *ListNode {
var prev *ListNode
curr := head
for curr!=nil {
next := curr.Next
curr.Next = prev
prev = curr
curr = next
}
return prev
}
//迭代
/*func reverseList(head *ListNode) *ListNode {
if head==nil||head.Next==nil {
return head
}
var mid,right *ListNode
mid = head.Next
right = mid.Next
head.Next = nil
for right!=nil{
mid.Next = head
head = mid
mid = right
right = right.Next
}
mid.Next = head
return mid
}*/
//遞回
/*func reverseList(head *ListNode) *ListNode {
if head==nil||head.Next==nil {
return head
}
res := reverseList(head.Next)
head.Next.Next = head
//很重要，為了防止鏈表回圈，在處理第一個節點的時候 防止回圈
head.Next = nil
return res
}*/
77. 組合
package question77
var res [][]int
func combine(n int, k int) [][]int {
var path []int
res = [][]int{}
backtrace(path, n, k, 1)
return res
}
func backtrace(path []int, n int, k int, start int) {
if len(path) == k {
//后續修改path，會影響到res中的內容，
temp := make([]int, k)
copy(temp, path)
res = append(res, temp)
return
}
for i := start; i <= n; i++ {
//剪枝
if i<=1+n-k+len(path) {
path = append(path, i)
backtrace(path, n, k, i+1)
path = path[:len(path)-1]
}
}
}
46. 全排列
package question46
import "fmt"
var res [][]int
func permute(nums []int) [][]int {
path := []int{}
res = [][]int{}
backtrace(path,nums)
return res
}
func isInSlice(path []int,value int) bool{
for _,v:=range path{
if v == value {
return true
}
}
return false
}
func backtrace(path []int,nums []int) {
if len(path) == len(nums) {
fmt.Println(len(nums))
//后續修改path，會影響到res中的內容，
temp := make([]int, len(nums))
copy(temp, path)
res = append(res, temp)
return
}
for i := 0; i <len(nums); i++ {
if !isInSlice(path,nums[i]) {
fmt.Println(nums[i])
path = append(path, nums[i])
backtrace(path,nums)
path = path[:len(path)-1]
}
}
}
784. 字母大小寫全排列
package question784
import "strings"
var res []string
func letterCasePermutation(s string) []string {
res = []string{}
path := ""
backtrace(path, s, 0)
return res
}
func backtrace(path string, s string, start int) {
if len(path) == len(s) {
res = append(res, path)
return
}
ch := s[start]
if ch >= 'a' && ch <= 'z' ||ch>='A'&&ch<='Z'{
path += strings.ToUpper(string(ch))
backtrace(path, s, start+1)
path = path[:len(path)-1]
path += strings.ToLower(string(ch))
backtrace(path, s, start+1)
path = path[:len(path)-1]
} else {
path += string(ch)
backtrace(path, s, start+1)
}
}
70. 爬樓梯
package question70
/*var cache []int = make([]int,100)
func climbStairs(n int) int {
if cache[n-1]!=0 {
return cache[n-1]
}
if n==1||n==2 {
cache[n-1] = n
return n
}
cache[n-1] = climbStairs(n-1)+climbStairs(n-2)
return cache[n-1]
}*/
func climbStairs(n int) int {
x,y,z :=0,0,1
for i:=1;i<=n;i++ {
x = y
y = z
z = x+y
}
return z
}
198. 打家劫舍
package question198
func max(x,y int) int {
if x>y {
return x
}
return y
}
func rob(nums []int) int {
n := len(nums)
if n==1 {
return nums[0]
}
first,second := nums[0],max(nums[0],nums[1])
for i:=3;i<=n;i++ {
first,second = second,max(second,nums[i-1]+first)
}
return second
}
/*func rob(nums []int) int {
n := len(nums)
res := make([]int,n)
for i:=1;i<=n;i++ {
if i==1 {
res[i-1] = nums[i-1]
}else if i==2 {
res[i-1] = max(nums[i-1],nums[i-2])
}else{
res[i-1] = max(res[i-2],res[i-3]+nums[i-1])
}
}
return res[n-1]
}
*/
120. 三角形最小路徑和
package question120
func min(x,y int)int {
if x>y {
return y
}
return x
}
func minimumTotal(triangle [][]int) int {
n := len(triangle)
res := make([][]int, n)
for i := 0; i < n; i++ {
res[i] = make([]int, i+1)
}
for i := 0; i < n; i++ {
for j := 0; j < i+1; j++ {
if i==0 {
res[i][j] = triangle[i][j]
}else if j==0 {
res[i][j] = res[i-1][j]+triangle[i][j]
}else if j==i{
res[i][j] = res[i-1][j-1]+triangle[i][j]
}else{
res[i][j] = min(res[i-1][j],res[i-1][j-1])+triangle[i][j]
}
}
}
minElem := res[n-1][0]
for i := 1; i <n ; i++ {
if res[n-1][i]<minElem {
minElem = res[n-1][i]
}
}
return minElem
}
231. 2 的冪
package question231
func isPowerOfTwo(n int) bool {
return (n>0)&&(n&(n-1)==0)
}
/*func isPowerOfTwo(n int) bool {
if n==1 {
return true
}
num := 1
for num<=n {
num = num<<1
}
if num==n {
return true
}
return false
}*/
191. 位1的個數
package question191
func hammingWeight(num uint32) int {
res := 0
for ;num>0;num&=num-1 {
res++
}
return res
}
/*func hammingWeight(num uint32) int {
return strings.Count(strconv.FormatInt(int64(num),2),"1")
}*/
190. 顛倒二進制位
package question190
func reverseBits(n uint32) uint32 {
n = (n>>16)|(n<<16)
n = ((n&0xff00ff00)>>8)|((n&0x00ff00ff)<<8)
n = ((n&0xf0f0f0f0)>>4)|((n&0x0f0f0f0f)<<4)
n = ((n&0xcccccccc)>>2)|((n&0x33333333)<<2)
n = ((n&0xaaaaaaaa)>>1)|((n&0x55555555)<<1)
return n
}
/*func reverseBits(num uint32) uint32 {
var res uint32 = 0
for i:=0;i<32;i++ {
res = res<<1|num&1
num=num>>1
}
return res
}*/
136. 只出現一次的數字
package question136
func singleNumber(nums []int) int {
var res int
for _,v := range nums{
res^=v
}
return res
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/403904.html
標籤：其他