918. 环形子数组的最大和 - 力扣（LeetCode）
分类讨论：
前提：环形子数组可以通过将2个数组拼接得到
- 如果子数组没有跨越边界：答案就是子数组的最大和
- 如果子数组跨越了边界：答案就是整个数组的和减去中间部分的和，中间部分和越小，答案越大，所以这部分需要求出子数组的最小和
- 特殊情况：如果sum == minSum，应当返回maxSum，因为题目要保证非空子数组
func maxSubarraySumCircular(nums []int) int {
maxSum := math.MinInt //子数组的最大和
minSum := 0 //子数组的最小和 可以为0
sum := 0 //全部元素的和
tmpMax,tmpMin := 0,0
for _,num := range nums {
//以num为结尾的最大子数组和 最小子数组和 ，因为没有乘法 肯定是只从tmpMax或tmpMin转移过来
tmpMax = max(tmpMax + num,num)
tmpMin = min(tmpMin + num, num)
//更新答案 不能用一个变量
maxSum = max(maxSum,tmpMax)
minSum = min(minSum,tmpMin)
sum += num
}
if sum == minSum {//必须非空
return maxSum
}
return max(maxSum,sum - minSum)
}9. 回文数 - 力扣（LeetCode）
很多种做法，转为数组，转为字符串，本质上判断回文数的方法就是双指针，分别放在开始和结束，相互靠近
func isPalindrome(x int) bool {
if x < 0 {
return false
}
s := strconv.Itoa(x)
l,r := 0,len(s)-1
for l < r {
if s[l] != s[r] {
return false
}
l++
r--
}
return true
}66. 加一 - 力扣（LeetCode）
使用digit存储进位，从低位依次累加即可
注意最后的时候如果digit不为0，要加到第一位
初始化设置为1，因为要对个位数+1
func plusOne(digits []int) []int {
digit := 1
for i := len(digits) - 1; i >= 0; i -- {
tmp := digit + digits[i]
digits[i] = tmp % 10
digit = tmp / 10
}
if digit > 0 {
digits = append([]int{digit},digits...)
}
return digits
}172. 阶乘后的零 - 力扣（LeetCode）
求因子里2和5的数量，两者最小值就是答案，因为10=2*5
因为5出现的次数一定比2少 只需要求5出现的次数即可
func trailingZeroes(n int) int {
ans := 0
for i := 2; i <= n; i ++ {
tmp := i
for tmp % 5 == 0 {
tmp /= 5
ans ++
}
}
return ans
}69. x 的平方根 - 力扣（LeetCode）
具有单调性 可以用二分
只需要求整数部分，等价于找到最大的mid使得mid*mid<=x
func mySqrt(x int) int {
l,r,ans := 1,x,0
for l <= r {
mid := (l+r) / 2
if mid * mid <= x {
ans = mid
l = mid + 1
}else{
r = mid - 1
}
}
return ans
}50. Pow(x, n) - 力扣（LeetCode）
快速幂，时间复杂度O(logn) 原理是借助二进制，如果该位为1的话，说明要乘上x
x要累计乘
func myPow(x float64, n int) float64 {
if n < 0 {
n = - n
x = 1 / x
}
var ans float64 = 1
//二进制
for n > 0 {
if n % 2 == 1 {
ans = ans * x
}
x = x * x
n /= 2
}
return ans
}149. 直线上最多的点数 - 力扣（LeetCode）
n只有300，n^3的做法，前两层枚举直线的2个点，第三层计算有多少个点在该直线上
关键在于如何判断
斜率公式 (y1-y2) / (x1-x2)
func maxPoints(points [][]int) int {
n := len(points)
ans := 1
for i := 0; i < n; i ++ {
for j := i + 1; j < n ; j ++ {
cnt := 2
k1 := float64(points[i][1] - points[j][1]) / float64(points[i][0] - points[j][0])
for k := 0; k < n; k ++ {
if i == k || j == k {
continue
}
k2 := float64(points[i][1] - points[k][1]) / float64(points[i][0] - points[k][0])
if k1 == k2 {
cnt ++
}
}
ans = max(ans,cnt)
}
}
return ans
}136. 只出现一次的数字 - 力扣（LeetCode）
异或的性质
func singleNumber(nums []int) int {
ans := 0
for _,num := range nums {
ans = ans ^ num
}
return ans
}169. 多数元素 - 力扣（LeetCode）
众数的话肯定出现次数比其他元素多，众数对cnt的贡献是1，非众数的贡献是-1，先假设当前数为众数，然后依次遍历
func majorityElement(nums []int) int {
ans,cnt := nums[0],1
for i := 1; i < len(nums); i ++ {
if ans == nums[i] {
cnt++
continue
}
cnt --
if cnt == 0 {
cnt = 1
ans = nums[i]
}
}
return ans
}75. 颜色分类 - 力扣（LeetCode）
两个指针，p0表示下一个要放0的位置，p1表示下一个要放1的位置
如果当前数是1的话，直接和前面的nums[p1]交换
如果当前数是0的话，和前面的nums[p0]交换，但是因为0后面是1，如果p0<p1的话，说明刚刚的操作把1换到了后面，需要再换回来
func sortColors(nums []int) {
p0,p1 := 0,0
for idx,num := range nums {
if num == 0 {
nums[p0],nums[idx] = nums[idx],nums[p0]
if p0 < p1 {
//上一行会把1换到后面，再换回来
nums[p1],nums[idx] = nums[idx],nums[p1]
}
p1++
p0++
}else if num == 1 {
nums[p1],nums[idx] = nums[idx],nums[p1]
p1++
}
}
}31. 下一个排列 - 力扣（LeetCode）
例如 2, 6, 3, 5, 4, 1 这个排列， 我们想要找到下一个刚好比他大的排列，于是可以从后往前看 我们先看后两位 4, 1 能否组成更大的排列，答案是不可以，同理 5, 4, 1也不可以 直到3, 5, 4, 1这个排列，因为 3 < 5， 我们可以通过重新排列这一段数字，来得到下一个排列 因为我们需要使得新的排列尽量小，所以我们从后往前找第一个比3更大的数字，发现是4 然后，我们调换3和4的位置，得到4, 5, 3, 1这个数列 因为我们需要使得新生成的数列尽量小，于是我们可以对5, 3, 1进行排序，可以发现在这个算法中，我们得到的末尾数字一定是倒序排列的，于是我们只需要把它反转即可 最终，我们得到了4, 1, 3, 5这个数列 完整的数列则是2, 6, 4, 1, 3, 5。
func nextPermutation(nums []int) {
n := len(nums)
if n == 1 {
return
}
//2 6 3 5 4 1
pos := -1 //找到3
for i := n-2; i >=0 ; i -- {
if nums[i] < nums[i+1] {
pos = i
break
}
}
if pos == -1 {
//已经是降序的了
sort.Ints(nums)
return
}
firstPos := 0 //找到4
for i := n-1; i > pos; i -- {
if nums[i] > nums[pos] {
firstPos = i
break
}
}
//交换3和4 ==> 2 6 4 | 5 3 1
nums[pos],nums[firstPos] = nums[firstPos],nums[pos]
//要尽可能小 所以对 5 3 1 排序
for i := pos+1; i < n; i ++ {
for j := i + 1; j < n; j ++ {
if nums[i] > nums[j] {
nums[i],nums[j] = nums[j],nums[i]
}
}
}
}287. 寻找重复数 - 力扣（LeetCode）
建图，i->nums[i]为边，转化为环形链表找环
func findDuplicate(nums []int) int {
slow,fast := 0,0
for slow,fast = nums[slow],nums[nums[fast]]; slow != fast; slow,fast = nums[slow],nums[nums[fast]] {
}
head := 0
for slow != head {
slow = nums[slow]
head = nums[head]
}
return head
}67. 二进制求和 - 力扣（LeetCode）
func addBinary(a string, b string) string {
i,j := len(a)-1,len(b)-1
var ans []byte
last := 0
for i >= 0 || j >= 0 || last > 0 {
tmpa,tmpb := 0,0
if i >= 0 {
tmpa = int(a[i]-'0')
i--
}
if j >= 0 {
tmpb = int(b[j]-'0')
j--
}
now := tmpa + tmpb + last
if now % 2 == 0 {
ans = append(ans,'0')
}else{
ans = append(ans,'1')
}
last = now / 2
}
tmp := make([]byte,0,len(ans))
for i := len(ans)-1;i>=0;i-- {
tmp = append(tmp,ans[i])
}
return string(tmp)
}190. 颠倒二进制位 - 力扣（LeetCode）
for循环32位，如果当前位为1，那么让31-i位也为1
func reverseBits(num uint32) uint32 {
var res uint32
for i := 0; i < 32; i ++ {
if num % 2 == 1 {
res |= 1 << (31 - i)
}
num /= 2
}
return res
}191. 位1的个数 - 力扣（LeetCode）
func hammingWeight(n int) int {
ans := 0
for n > 0 {
if n % 2 == 1 {
ans ++
}
n /= 2
}
return ans
}137. 只出现一次的数字 II - 力扣（LeetCode）
如果出现的次数%3不为0的话，说明是只出现了一次的数字
func singleNumber(nums []int) int {
var ans int32
for i := 0; i < 32; i ++ {
var total int32
for _,num := range nums {
if (num >> i) & 1 == 1 {
total ++
}
}
if total % 3 != 0 {
ans |= (1<<i)
}
}
//力扣上的 int 是 int64，符号位在 i=63 位中
return int(ans)
}201. 数字范围按位与 - 力扣（LeetCode）
func rangeBitwiseAnd(left int, right int) int {
//所有对应二进制字符串的公共前缀再用零补上后面的剩余位
cnt := 0
for left < right {
left /= 2
right /= 2
cnt ++
}
return left << cnt
}评论 (0)
