LeetCode-1
|
|
402
|
0
|
LeetCode

LeetCode-1

今天是研究生生涯中第一次刷算法，算法真的很头疼我直接说，但是问题不大，刷就行了。

但是我不知道几道题水一篇比较合适，可能一两周一篇，或者达到五六道题就能水一篇了。

482 密钥格式化

特例

"---"
3
返回""

解法

因为是道简单题，也是第一次用GO写，所以既简单又困难。

我的想法简单，用go的库替换“-”为空字符串，然后再用自带的库把字符串变成大写的。

计算字符串余是多少。如果余为0，那么情况比较特殊，相当于第一部分为K大小，否则第一部分就是余的数量。然后去除第一部分，看看剩下的商是多少，即被分为几部分。

然后就是正常的字符串拼接，用了buffer.WriteString()这个函数，说是会快一点，用内存换时间吧。时间吊锤100%的人，当然是因为GO语言没人用的原因了。

func licenseKeyFormatting(s string, k int) string {
	s1 := strings.Replace(s, "-", "", -1)
	s1 = strings.ToUpper(s1)
	length := len(s1)
	if length <= k {
		return s1
	}
	var buffer bytes.Buffer
	first := length % k
	if first == 0 {
		length -= 1
		buffer.WriteString(s1[0:k])
		first += k
	} else {
		buffer.WriteString(s1[0:first])
	}
	var num int = length / k

	start := first
	for i := 0; i < num; i++ {
		buffer.WriteString("-")
		buffer.WriteString(s1[start : start+k])
		start += k
	}
	return buffer.String()
}

官方1

官方的解法是倒置的，从后面去字符，然后转大写，添加到数组里面，如果是破折号跳过，计算余是不是0，如果是，加入破折号。

然后检查数组是不是为空，并且最后一个是不是破折号

最后字符串进行反转。

这个方法也挺好的，不错，空间利用率比我的高。

func licenseKeyFormatting(s string, k int) string {
    ans := []byte{}
    for i, cnt := len(s)-1, 0; i >= 0; i-- {
        if s[i] != '-' {
            ans = append(ans, byte(unicode.ToUpper(rune(s[i]))))
            cnt++
            if cnt%k == 0 {
                ans = append(ans, '-')
            }
        }
    }
    if len(ans) > 0 && ans[len(ans)-1] == '-' {
        ans = ans[:len(ans)-1]
    }
    for i, n := 0, len(ans); i < n/2; i++ {
        ans[i], ans[n-1-i] = ans[n-1-i], ans[i]
    }
    return string(ans)
}

441 排列硬币

解法

两年前也做过一遍，思路一模一样，没有一点点改变，就是求根，我写了两行，多了一行，直接套用官方的解法

func arrangeCoins(n int) int {
	return int((math.Sqrt(float64(8*n+1)) - 1) / 2)
}

官方1

官方第二种解法是求根，第一种解法是二分法，我反正不太会二分法，虽然是比较基础的，没办法，谁叫我基础不牢呢。

k行硬币数量为total=2k×(k+1)，可以通过二分查找计算 nn 枚硬币可形成的完整阶梯行的总行数。

就是不断尝试k，如果比total大，就去左边区间的中心，如果比total小，就取右边区间的中心，一直分下去就能找到k了。

int arrangeCoins(int n) {
    int left = 1, right = n;
    while (left < right) {
        int mid = (right - left + 1) / 2 + left;
        if ((long long) mid * (mid + 1) <= (long long) 2 * n) {
            left = mid;
        } else {
            right = mid - 1;
        }
    }
    return left;
}

Go语言的居然直接有二分查找的函数，牛了

func arrangeCoins(n int) int {
    return sort.Search(n, func(k int) bool { k++; return k*(k+1) > 2*n })
}

search使用二分法进行查找，Search()方法回使用“二分查找”算法来搜索某指定切片[0:n]，并返回能够使f(i)=true的最小的i（0<=i<n）值，并且会假定，如果f(i)=true，则f(i+1)=true，即对于切片[0:n]，i之前的切片元素会使f()函数返回false，i及i之后的元素会使f()函数返回true。但是，当在切片中无法找到时f(i)=true的i时（此时切片元素都不能使f()函数返回true），Search()方法会返回n（而不是返回-1）。

  1. 访问的下标范围： [0,n)
  2. 如果不存在满足调节，函数返回n
  3. 二分位是false，则向后查询，是true，向前查询
  4. 通常用来在有序列表中进行过滤，也可以判断某个元素是否存在

852 山脉数组的峰顶索引

解法1

O(n)的做法，很简单，直接找到开始下坡的时候

func peakIndexInMountainArray(arr []int) int {
	for i := 1; ; i++ {
		if arr[i] > arr[i+1] {
			return i
		}
	}
}

解法2

一提示是O(logn)，我就知道铁用二分法，这种方法最适合用二分法，正好用上上面学的sort函数

func peakIndexInMountainArray(arr []int) int {
	return sort.Search(len(arr)-1, func(k int) bool { return arr[k+1] < arr[k] })
}

那么这个函数怎么用呢，我的理解就是返回条件为右边为true的情况。

那么这个情况就是，右边就是下坡，所以就是返回下坡arr[i] > arr[i+1]。当是下坡的时候，返回左区间，当不是下坡的时候，返回右区间。

38 外观数列

解法

就按题目的来就行了，我是递归的写法

func countAndSay(n int) string {
	if n == 1 { //我的方法精简法
		return "1"
	}
	var str strings.Builder
	var forward string = countAndSay(n - 1)
	index := 0
	for index < len(forward) {
		cur := index
		for cur < len(forward) && forward[index] == forward[cur] {
			cur++
		}
		str.WriteString(strconv.Itoa(cur - index))
		str.WriteByte(forward[index])
		index = cur
	}
	return str.String()
}

官方给的是迭代方法，两个都差不多

func countAndSay(n int) string {
	prev := "1"
	for i := 2; i <= n; i++ {
		cur := &strings.Builder{}
		for j, start := 0, 0; j < len(prev); start = j {
			for j < len(prev) && prev[j] == prev[start] {
				j++
			}
			cur.WriteString(strconv.Itoa(j - start))
			cur.WriteByte(prev[start])
		}
		prev = cur.String()
	}
	return prev
}

230 二叉搜索树中第K小的元素

当然无脑暴力解就是化为数组了，但是又慢空间又长了，没办法，二叉树的知识我都忘光了，而且我没注意到时搜索二叉树

func kthSmallest(root *TreeNode, k int) int {
	var numArr []int
	var nodeArr []*TreeNode = []*TreeNode{root}
	i := 0
	for len(nodeArr) > i {
		fmt.Println(nodeArr[i].Val)
		numArr = append(numArr, nodeArr[i].Val)
		if nodeArr[i].Left != nil {
			nodeArr = append(nodeArr, nodeArr[i].Left)
		}
		if nodeArr[i].Right != nil {
			nodeArr = append(nodeArr, nodeArr[i].Right)
		}
		i++
	}
	sort.Ints(numArr)
	return numArr[k-1]
}

然后我注意到了是搜索二叉树，我一开始想到的确实是中序遍历，但我没写，直接看我以前的解法，所以这里也放一下中序遍历的写法好了，这也是必须掌握的

中序递归法

func kthSmallest(root *TreeNode, k int) int {
	res := 0
	var middleOrder func(root *TreeNode)
	middleOrder = func(root *TreeNode) {
		if root == nil {
			return
		}
		middleOrder(root.Left)
		k--
		if k == 0 {
			res = root.Val
			return
		}
		middleOrder(root.Right)
	}
	middleOrder(root)
	return res
}

中序迭代法

func kthSmallest(root *TreeNode, k int) int {
	stack := []*TreeNode{}
	for {
		for root != nil {
			stack = append(stack, root)
			root = root.Left
		}
		stack, root = stack[:len(stack)-1], stack[len(stack)-1]
		k--
		if k == 0 {
			return root.Val
		}
		root = root.Right
	}
}

还是递归法香啊

记录子树的结点数

之前C++写过一遍，估计也是看过来的，总的思想就是计算每个节点子树的节点数，然后查找比k小的值，如果比k小，那么去左边，如果比k大，那么去右边。官方的多一个map记录，我感觉没啥用，还是就这样子吧。

func kthSmallest(root *TreeNode, k int) int {
	if root == nil {
		return 0
	}
	cnt := count(root.Left)
	if cnt >= k {
		return kthSmallest(root.Left, k)
	} else if k > cnt+1 {
		return kthSmallest(root.Right, k-cnt-1)
	}
	return root.Val
}

func count(node *TreeNode) int {
	if node == nil {
		return 0
	}
	return 1 + count(node.Left) + count(node.Right)
}

476 数字的补数

刷题时间：2021-10-18

和 1009是同一道题，就是多了个0的区别

思路就是int类型的，然后int32位的，就31位是有效的。找到有1的最大的那个位置，然后算得2^（highBit+1），再减去1，就是获得所有的1，然后再异或一下就行了

func findComplement(num int) int {
	highBit := 0
	for i := 1; i < 31; i++ {
		if num < 1<<i {
			break
		}
		highBit = i
	}
	mask := 1<<(highBit+1) - 1
	return num ^ mask
}

1009那题多了一个0，需要单独讨论，然后直接用go的一个函数库，直接获得bit位的长度

func bitwiseComplement(n int) int {
    if n==0 {
        return 1
    }
    return n ^ (1<<bits.Len(uint(n)) - 1)   
}

208 实现Trie

刷题时间：2021-10-19

本来写211的，因为有一种方法用的是字典树，所以先写这道题。就是实现字典树，就这。

// 实现字典树
type Trie struct {
	children [26]*Trie
	isEnd    bool
}

func Constructor() Trie {
	return Trie{}
}

func (this *Trie) Insert(word string) {
	node := this
	for _, ch := range word {
		ch -= 'a'
		if node.children[ch] == nil {
			node.children[ch] = &Trie{}
		}
		node = node.children[ch]
	}
	node.isEnd = true
}

func (this *Trie) Search(word string) bool {
	node := this
	for _, ch := range word {
		ch -= 'a'
		if node.children[ch] == nil {
			return false
		} else {
			node = node.children[ch]
		}
	}
	if node.isEnd == true {
		return true
	}
	return false
}

func (this *Trie) StartsWith(prefix string) bool {
	node := this
	for _, ch := range prefix {
		ch -= 'a'
		if node.children[ch] == nil {
			return false
		} else {
			node = node.children[ch]
		}
	}
	return true
}

211 添加与搜索单词

刷题时间：2021-10-19

法一

暴力解法，不是很提倡，有点拉

type WordDictionary struct {
	data []string
}

func Constructor() WordDictionary {
	return WordDictionary{data: make([]string, 0)}
}

func (this *WordDictionary) AddWord(word string) {
	this.data = append(this.data, word)
}

func (this *WordDictionary) Search(word string) bool {
	for _, d := range this.data {
		if len(d) != len(word) {
			continue
		}
		flag := true
		for i, w := range word {
			if w == '.' {
				continue
			}
			if string(d[i]) != string(w) {
				flag = false
				break
			}
		}
		if flag {
			return true
		}
	}
	return false
}

法二

暴力升级版，使用map，根据字符串的长度进行分类，大大加快了速度

type WordDictionary struct {
	data map[int][]string
}

func Constructor() WordDictionary {
	return WordDictionary{make(map[int][]string)}
}

func (this *WordDictionary) AddWord(word string) {
	l := len(word)
	if list, ok := this.data[l]; ok {
		this.data[l] = append(list, word)
	} else {
		this.data[l] = []string{word}
	}
}

func (this *WordDictionary) Search(word string) bool {
	l := len(word)
	if list, ok := this.data[l]; ok {
		for _, d := range list {
			flag := true
			for i, w := range word {
				if w == '.' {
					continue
				}
				if string(d[i]) != string(w) {
					flag = false
					break
				}
			}
			if flag {
				return true
			}
		}
	}
	return false
}

法三

字典树的方法，有点小难。

还会用上深度优先算法，当字符串中含有’ .’ 的时候，需要检查所有满足条件的字典，如果不存在，不一定返回false，因为还没检查完，所以要注意这点。

type TrieNode struct {
	children [26]*TrieNode
	isEnd    bool
}

func (t *TrieNode) Insert(word string) {
	node := t
	for _, ch := range word {
		ch -= 'a'
		if node.children[ch] == nil {
			node.children[ch] = &TrieNode{}
		}
		node = node.children[ch]
	}
	node.isEnd = true
}

type WordDictionary struct {
	trieRoot *TrieNode
}

func Constructor() WordDictionary {
	return WordDictionary{&TrieNode{}}
}

func (d *WordDictionary) AddWord(word string) {
	d.trieRoot.Insert(word)
}

// 这里需要用到深度优先搜索，因为有前缀*
func (d *WordDictionary) Search(word string) bool {
	var dfs func(index int, node *TrieNode) bool
	dfs = func(index int, node *TrieNode) bool {
		if index == len(word) {
			return node.isEnd
		}
		w := word[index]
		if w != '.' {
			child := node.children[w-'a']
			return child != nil && dfs(index+1, child)
		} else {
			for i := range node.children {
				child := node.children[i]
				if child != nil && dfs(index+1, child) {
					return true
				}
			}
		}
		return false
	}
	return dfs(0, d.trieRoot)
}

453 最小操作次数使数组元素相等

刷题时间：2021-10-20

直接错误，以为是最大值减去每个值就是了，后来发现不对，以为是次大值减去每个值。唉居然是反向思维，最小值减去每个值，因为n-1个数+1就是1个数减一，确实没想到，拉了拉了

func minMoves(nums []int) int {
	min := nums[0]
	for _, num := range nums[1:] {
		if num < min {
			min = num
		}
	}
	ans := 0
	for _, num := range nums {
		ans += num - min
	}
	return ans
}

66 加一

刷题时间：2021-10-21

就加法呗，逆向数组，最小的加一，然后查看是不是超过了10，要不然就减去10，进位，唯一特殊的情况就是需要首位也进位了，那么数组就需要加上一个1。

func plusOne(digits []int) []int {
	flag := true
	for i := len(digits) - 1; i >= 0; i-- {
		if !flag {
			return digits
		}
		digits[i]++
		if digits[i]/10 == 1 {
			digits[i] %= 10
		} else {
			flag = false
		}
	}
	if flag {
		return append([]int{1}, digits...)
	}
	return digits
}

官解是判断末尾第一个不出现9的数字，+1，然后9的全部置零，特殊情况也是一样考虑。

func plusOne(digits []int) []int {
    n := len(digits)
    for i := n - 1; i >= 0; i-- {
        if digits[i] != 9 {
            digits[i]++
            for j := i + 1; j < n; j++ {
                digits[j] = 0
            }
            return digits
        }
    }
    // digits 中所有的元素均为 9

    digits = make([]int, n+1)
    digits[0] = 1
    return digits
}

169 多数元素

刷题时间：2021-10-22

因为有一题是这个的拓展，所以先刷这道题。

法一

哈希表，在遍历的时候采用打擂台的方法，不需要再遍历一遍了

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        unordered_map<int, int> counts;
        int majority = 0, cnt = 0;
        for (int num: nums) {
            ++counts[num];
            if (counts[num] > cnt) {
                majority = num;
                cnt = counts[num];
            }
        }
        return majority;
    }
};

法二

排序，这个没啥好讲的。

法三

随机法，就随机一个数组，然后看看是不是众数，感觉有、扯，不是很推荐吧

法四

分治法，越变越麻烦了，也不推荐

法五

摩尔投票算法，具体细节不讲了，看一下这篇文章，还有演示。

func majorityElement(nums []int) int {
	res, cnt := 0, 0
	for _, num := range nums {
		if cnt == 0 {
			res = num
			cnt++
		} else {
			if num == res {
				cnt++
			} else {
				cnt--
			}
		}
	}
	return res
}

229 求众数 II

刷题时间：2021-10-22

法一

也是哈希值的做法，然后再遍历一遍哈希表，时间复杂度是O(n)，空间是O(n)

class Solution {
   public:
    vector<int> majorityElement(vector<int>& nums) {
        int n = nums.size();
        vector<int> ans;
        unordered_map<int, int> cnt;

        for (auto & v : nums) {
            cnt[v]++;
        }
        for (auto & v : cnt) {
            if (v.second > n / 3) {
                ans.push_back(v.first);
            }
        }
        return ans;
    }
};

法二

摩尔投票法。

先给出完整版本的摩尔投票法，算是上面的加强版本，因为上一题的条件是一定有满足条件的大于n/2，所以不需要计票。而正统的算法需要计票，来判断是不是满足条件。

int majorityElement(vector<int>& nums) {
	int k = 0, cand = 0;
	//成对抵销阶阶段
	for(auto num:nums){
		if(k == 0){
			cand = num;
			k = 1;
		}
		else{
			if(num == cand){
				++k;
			}
			else{
				--k;
			}
		}
	}
	//计数阶段 判断cand的个数是否超过一半
	k = 0;
	for(auto num:nums){
		if(num == cand){
			++k;
		}
	}
	if(k <= nums.size() / 2){
		cand = -1;//表示未超过一半 
	}
	return cand;
}

那么对应这题，就需要做一个加强版本的摩尔投票法。

因为大于n/3的情况，可能会有两个候选人，所以需要两个元素和两个计数器。抵消的时候，也要两个人同时抵消。

func majorityElement(nums []int) (ans []int) {
    element1, element2 := 0, 0
    vote1, vote2 := 0, 0

    for _, num := range nums {
        if vote1 > 0 && num == element1 { // 如果该元素为第一个元素，则计数加1
            vote1++
        } else if vote2 > 0 && num == element2 { // 如果该元素为第二个元素，则计数加1
            vote2++
        } else if vote1 == 0 { // 选择第一个元素
            element1 = num
            vote1++
        } else if vote2 == 0 { // 选择第二个元素
            element2 = num
            vote2++
        } else { // 如果三个元素均不相同，则相互抵消1次
            vote1--
            vote2--
        }
    }

    // 计票
    cnt1, cnt2 := 0, 0
    for _, num := range nums {
        if vote1 > 0 && num == element1 {
            cnt1++
        }
        if vote2 > 0 && num == element2 {
            cnt2++
        }
    }

    // 检测元素出现的次数是否满足要求
    if vote1 > 0 && cnt1 > len(nums)/3 {
        ans = append(ans, element1)
    }
    if vote2 > 0 && cnt2 > len(nums)/3 {
        ans = append(ans, element2)
    }
    return
}
暂无评论

发送评论 编辑评论 


				

			

						

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
							
													

					

				

			

			
			

				

					
				



			

				

											

							
							
						

																					

							
							
						

										
					
											
						

	

		


|´・ω・)ノ


ヾ(≧∇≦*)ゝ


(☆ω☆)


（╯‵□′）╯︵┴─┴


￣﹃￣


(/ω＼)


∠( ᐛ 」∠)＿


(๑•̀ㅁ•́ฅ)


→_→


୧(๑•̀⌄•́๑)૭


٩(ˊᗜˋ*)و


(ノ°ο°)ノ


(´இ皿இ｀)


⌇●﹏●⌇


(ฅ´ω`ฅ)


(╯°A°)╯︵○○○


φ(￣∇￣o)


ヾ(´･ ･｀｡)ノ"


( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃


(ó﹏ò｡)


Σ(っ °Д °;)っ


( ,,´･ω･)ﾉ"(´っω･｀｡)


╮(╯▽╰)╭


o(*////▽////*)q


＞﹏＜


( ๑´•ω•) "(ㆆᴗㆆ)






😂


😀


😅


😊


🙂


🙃


😌


😍


😘


😜


😝


😏


😒


🙄


😳


😡


😔


😫


😱


😭


💩


👻


🙌


🖕


👍


👫


👬


👭


🌚


🌝


🙈


💊


😶


🙏


🍦


🍉


😣






































































Source: github.com/k4yt3x/flowerhd


	

	

		
颜文字


Emoji


小恐龙


花!
	


									

			

			
			
		

	









上一篇




下一篇 






                    

                    
			        推荐文章
		            

		            



							
LeetCode-24

							
							



							
LeetCode-23

							
							



							
LeetCode-22

							
							



							
LeetCode-21

							
							



							
LeetCode-20