leetcode

Documentation

Index

• func FindComplement(num int) int
• func FindInMountainArray(target int, m *MountainArray) int
• func FindTheDifference(s, t string) byte
• func Fraction(cont []int) []int
• func FractionX(cont []int) []int
• func GcdOfStrings(a, b string) string
• func IsMatch(s string, p string) bool
• func IsPalindrome(s string) bool
• func IsPalindromeX(s string) bool
• func IsPowerOfTwo(n int) bool
• func IsSubsequence(s, t string) bool
• func IsValidPalindrome(s string, k int) bool
• func Lcs(text1 string, text2 string) int
• func LongestPalindrome(s string) string
• func LongestPalindromeX(s string) string
• func LongestSubsequence(arr []int, difference int) int
• func MaxProduct(words []string) int
• func MinCostToMoveChips(chips []int) int
• func ShortestPalindrome(s string) string
• func ShortestPalindromeX(s string) string
• func SingleNumber(nums []int) int
• func SingleNumber2(nums []int) int
• func SingleNumber2x(nums []int) int
• func SingleNumber3(nums []int) []int
• func StrLcs(text1 string, text2 string) string
• func String2int(str string) (res int)
• func ValidMountingArray(m []int) bool
• func ValidPalindrome(s string) bool
• func ValidPalindromeX(s string) bool
• type LFUCache
  • func ConstructorLFU(capacity int) LFUCache
  • func (lfu *LFUCache) Get(key int) int
  • func (lfu *LFUCache) Put(key int, value int)
• type LRUCache
  • func NewLRU(capacity int) LRUCache
  • func (lru *LRUCache) Get(key int) int
  • func (lru *LRUCache) Put(key, value int)
• type MountainArray
• type Node
  • func (n *Node) Append(c byte, child *Node)
  • func (n *Node) String() string
  • func (n *Node) StringLevel(level int, finishNodes map[*Node]bool) string

Functions

func FindComplement

func FindComplement(num int) int

FindComplement 生成某数的补数 `110(6) ==> 001(1)` 从右边开始,对第i位的处理,num已经右移了i次,此时对num的个位数位进行异或;将生成的异或位也左移i位. 然后将所有生成的异或位相加即可得到改数的`补数`.

func FindInMountainArray

func FindInMountainArray(target int, m *MountainArray) int

FindInMountainArray 在山脉数组中找某数. 定义左右边界l和r，mid=(l+r)>>1，判断arr[mid]>arr[mid+1]是不是成立，如果成立，那么山峰在[0,mid]这个区间中，我们在这个区间中继续查找； 如果不成立，那么山峰在[mid+1,len(arr))这个区间中，我们在这个区间中查找。 最后山峰左边查找目标和山峰右边查找目标使用的就是二分查找，不过山峰左边是递增，山峰右边是递减.

func FindTheDifference

func FindTheDifference(s, t string) byte

FindTheDifference Given two strings s and t which consist of only lowercase letters. String t is generated by random shuffling string s and then add one more letter at a random position. Find the letter that was added in t.

func Fraction

func Fraction(cont []int) []int

func FractionX

func FractionX(cont []int) []int

func GcdOfStrings

func GcdOfStrings(a, b string) string

func IsMatch

func IsMatch(s string, p string) bool

func IsPalindrome

func IsPalindrome(s string) bool

func IsPalindromeX

func IsPalindromeX(s string) bool

func IsPowerOfTwo

func IsPowerOfTwo(n int) bool

IsPowerOfTwo n为2的幂，二进制表示时：一定为 某位是1，其它位都是0，例如4：00000100 n-1,二进制表示时，n的二进制为1的位右边全是1，例如3：00000011 所以 & 运算后，结果是 00000000, 则必定为 true

func IsSubsequence

func IsSubsequence(s, t string) bool

func IsValidPalindrome

func IsValidPalindrome(s string, k int) bool

IsValidPalindrome 给出一个字符串 s 和一个整数 k，请你帮忙判断这个字符串是不是一个「K 回文」。 所谓「K 回文」：如果可以通过从字符串中删去最多 k 个字符将其转换为回文，那么这个字符串就是一个「K 回文」。

func Lcs

func Lcs(text1 string, text2 string) int

Lcs 获取string的最长公共子序列

- 思路

```cgo 输入两个串s1,s2,

设MaxLen(i,j)表示:  s1的左边i个字符形成的子串，与s2左边的j个字符形成的子串的最长公共子序列的长度(i,j从0开始算）
MaxLen(i,j) 就是本题的“状态”
假定len1 = strlen(s1),len2 = strlen(s2）
那么题目就是要求MaxLen(len1,len2)
显然：
MaxLen(n,0)  = 0  ( n= 0...len1）
MaxLen(0,n)  = 0  ( n=0...len2）递推公式：
if ( s1[i-1] == s2[j-1] ) //s1的最左边字符是s1[0]
    MaxLen(i,j) = MaxLen(i-1,j-1) + 1
else
    MaxLen(i,j) = Max(MaxLen(i,j-1),MaxLen(i-1,j) )

```

- 证明

```cgo S1,S2表示表示长度为i,j的序列 S1[:i-1]表示长度为i-1的序列 S2[:j-1]表示长度为j-1的序列 S1[i-1]表示S1的第i-1个字符 S2[j-1]表示S2的第j-1个字符

在S1[i-1] != S2[j-1]情况下: MaxLen(S1,S2)不会比MaxLen(S1,S2[:j-1])和MaxLen(S1[:i-1],S2)两者之中任意一个小,也不会比两者都大.

证明:

采用反证法:

若MaxLen(S1,S2) 比 MaxLen(S1,S2[:j-1])和MaxLen(S1[:i-1],S2) 都大,
情况1: MaxLen(S1,S2) > MaxLen(S1,S2[:j-1]
则,S1[i-1] 必定是 MaxLen(S1,S2)的子序列的关键元素,且为最后一个元素.
同理:S2[j-1] 必定是 MaxLen(S1,S2)的子序列的关键元素,且为最后一个元素.
故而S1[i-1]==S2[j-1],
与假设矛盾,从而假设不成立. 证毕~

```

func LongestPalindrome

func LongestPalindrome(s string) string

func LongestPalindromeX

func LongestPalindromeX(s string) string

func LongestSubsequence

func LongestSubsequence(arr []int, difference int) int

LongestSubsequence 最长等差子序列 这道题思路比较简单，跟经典问题`最长递增（减）子序列`有点相似，而这道题称为`最长等差子序列`, 并且公差还是固定的，相对还更简单一点。 可以用`dp[i]`来记录以数字`i`为结尾的`最长等差子序列`的长度，那么它应该只有两种情况：

- `dp[i] = 1 // 表示在 i 之前没有出现等差子序列`;

- `dp[i] = dp[i - difference] + 1 // 表示在 i 之前出现了等差子序列，长度为 dp[i-difference], 而 i 也是满足这个等差序列的，所以等差序列的长度在此基础上加 1 就可以了`

考虑元素值会出现负数，所以用数组存放是不行的，那么可以用一个 `map`来维护以 `i` 结尾的最长等差序列的长度，所以也就不难得出如下代码

设m[i]表示当前序列最后一个数是i的最大子序列长度 递推式: m[i]=max(m[i],m[i-difference]+1);

func MaxProduct

func MaxProduct(words []string) int

func MinCostToMoveChips

func MinCostToMoveChips(chips []int) int

func ShortestPalindrome

func ShortestPalindrome(s string) string

func ShortestPalindromeX

func ShortestPalindromeX(s string) string

func SingleNumber

func SingleNumber(nums []int) int

SingleNumber

| a | b | ⊕ | | ---- | ---- | ---- | | 1 | 0 | 1 | | 1 | 1 | 0 | | 0 | 0 | 0 | | 0 | 1 | 1 |

交换律：`a ^ b ^ c <=> a ^ c ^ b`

任何数于0异或为任何数: `0 ^ n => n`

相同的数异或为0: `n ^ n => 0`

func SingleNumber2

func SingleNumber2(nums []int) int

SingleNumber2 已知: 0 ^ x = x, x ^ x = 0; x & ^x = 0, x & ^0 = x; 则有: x出现一次:

a = (a ^ x) & ^b ==>  a = x
b = (b ^ x) & ^a ==> (因为a=x,所有b=0)

x出现两次:

a = (a ^ x) & ^b ==>  a = (x ^ x) & ^0 ==> a = 0
b = (b ^ x) & ^a ==>  b = (0 ^ x) & ^0 ==> b = x

x出现三次:

a = (a ^ x) & ^b ==>  a = (0 ^ x) & ^x ==> a = 0
b = (b ^ x) & ^a ==>  b = (x ^ x) & ^0 ==> b = 0

func SingleNumber2x

func SingleNumber2x(nums []int) int

func SingleNumber3

func SingleNumber3(nums []int) []int

SingleNumber3 位运算，异或运算。对于一个数组`nums = [1, 1 , 2, 2, 3, 4, 4, 5]`。 其一，如果，进行一次全部异或运算，将会得到`3 xor 5`。 其二， `3 ^ 5 = 110b`。那么在出现`1`的位置，必然一个为`1`一个为`0`，这样就可以根据特征区分出两个数字。 其三，于是将问题转化为了“一个数字出现1次，其他数字出现两次”。

func StrLcs

func StrLcs(text1 string, text2 string) string

func String2int

func String2int(str string) (res int)

String2int 思路: 用二进制的一位表示某一个字母是否出现过，0表示没出现，1表示出现。 "abcd"二进制表示00000000 00000000 00000000 00001111, "bc"二进制表示00000000 00000000 00000000 00000110。 当两个字符串没有相同的字母时，二进制数与的结果为0。

func ValidMountingArray

func ValidMountingArray(m []int) bool

ValidMountingArray 判断是否是山脉数组.

思路: 找到递增数列的下标i,找到递减数列的下标j; i==j时说明为山脉数组. i=0 || j=len(arr)-1不符合山脉数组的要求.

func ValidPalindrome

func ValidPalindrome(s string) bool

ValidPalindrome 判断一个str是否为

func ValidPalindromeX

func ValidPalindromeX(s string) bool

Types

type LFUCache

type LFUCache struct {
	Cap int
	// contains filtered or unexported fields
}

用2个hash-map，CntM的key为访问次数，value为缓存元素组成的链表； KMap的key为缓存元素的key，value为CntM的链表的节点指针。 关键还有一个int型的Min，记录当前访问次数最小值

func ConstructorLFU

func ConstructorLFU(capacity int) LFUCache

func (*LFUCache) Get

func (lfu *LFUCache) Get(key int) int

func (*LFUCache) Put

func (lfu *LFUCache) Put(key int, value int)

type LRUCache

type LRUCache struct {
	// contains filtered or unexported fields
}

func NewLRU

func NewLRU(capacity int) LRUCache

func (*LRUCache) Get

func (lru *LRUCache) Get(key int) int

如果key存在缓存中, 则获取key的value 每次数据项被查询到时，都将此数据项移动到链表头部（O(1)的时间复杂度） 这样，在进行过多次查找操作后，最近被使用过的内容就向链表的头移动，而没有被使用的内容就向链表的后面移动 当需要替换时，链表最后的位置就是最近最少被使用的数据项，我们只需要将最新的数据项放在链表头部， 当Cache满时，淘汰链表最后的位置就是了。

func (*LRUCache) Put

func (lru *LRUCache) Put(key, value int)

写入数据, 如果key不存在, 则写入其数据值, 当缓存容量达到上限时, 它应该在写入新数据之前删除最近最少使用的value.

type MountainArray

type MountainArray struct {
	// contains filtered or unexported fields
}

type Node

type Node struct {
	C        byte
	Parent   *Node
	Children map[byte][]*Node
	End      bool
	Size     int
}

func (*Node) Append

func (n *Node) Append(c byte, child *Node)

func (*Node) String

func (n *Node) String() string

func (*Node) StringLevel

func (n *Node) StringLevel(level int, finishNodes map[*Node]bool) string