番禺网站建设外包,龙游网站建设,在线教育网站设计,学院网站建设管理办法1.整数除法 思想#xff1a;不能用除法、乘法、取余#xff0c;那么可以用减法完成除法的操作#xff0c;但是在减去被除数的时候#xff0c;可以考虑被除数1扩大一倍在进行减少#xff0c;加快减的速率。 2.二进制加法 思想#xff1a;从末尾向前遍历#xff0…1.整数除法 思想不能用除法、乘法、取余那么可以用减法完成除法的操作但是在减去被除数的时候可以考虑被除数1扩大一倍在进行减少加快减的速率。 2.二进制加法 思想从末尾向前遍历类似这种有长短不一的需要累计的时候可以采用for i0 || j 0 {内部在进行判断该值是否有贡献} 3.前n个数二进制1的个数 这里隐藏着2的倍数和之间二进制1的个数的关系2和4的二进制个数相等。 4.出现1次的数字其余都是三次 原版本是找出出现一次的数字其余都是出现两次这个只需要全部异或就能得出答案但是出现三次的要进行过滤的话需要从二进制的角度去考虑某一位数组中累积和事3的倍数的话这一位置肯定是出现三次的否则是一位中的。注意go语言中int是变化的在这个题目中需要指定int32否则会出现溢出的情况。 5.单词长度最大的乘积 题目要求两个字符串之间没有字符交集 暴力做法在单词数组中找出两个互补包含相同字符的串的乘积的最大值思路是采用暴力双层遍历先对数组按照字符串的长度进行降序排序关键是如何快速判断两个字符串包含相同的字符超时做法是用一个map记录a然后在判断b取巧的方式是采用strings.indexByte内置的api。 二进制做法(位运算)因为字符串只包含小写的英文字母那么判断两个字符串是否有相同的字符可以考虑将字符串转换成数字通过ab 0 表示字符串没有共同字符。 6.排序数组中找出两个数之和等于target 方法一直接采用二分查找去做方法二可以采用变循环边加入map通过map[tar-val]判断是否存在一遍就能找出答案。 7.找出数组中三数之和为零的数 先排序然后可以用两层遍历去重复判断i ! 0 nums[i] ! nums[i-1最后一维可以采用二分查找来做。 8.找出最短的字数组的和大于等于target的长度 暴力法先计算前缀和然后通过暴力从短到长的进行判断。 滑动窗口由小窗口在逐渐变大达到目的值的时候在逐渐减少数组都是正数。 func numSubarrayProductLessThanK(nums []int, k int) int {res : 0left : 0right : 0cv : 1for right len(nums){cv * nums[right]for left right cv k { // 如果当前的滑动窗口需要进行变化cv / nums[left]left}res res (right - left 1) // 含义以right结尾的所有满足条件字数组的情况right}return res
} 前缀和二分查找由于本题目的前缀和是递增的因此也可以考虑用二分查找需要的值 9.找出子数组中积少的target的个数 滑动窗口(数组中都为正数) func numSubarrayProductLessThanK(nums []int, k int) int {res : 0left : 0right : 0cv : 1for right len(nums){cv * nums[right]for left right cv k { // 如果当前的滑动窗口需要进行变化cv / nums[left]left}res res (right - left 1) // 含义以right结尾的所有满足条件字数组的情况right}return res
}
10.和为k的子数组 很容易根据上面题目联想到使用滑动窗口但是这题目nums中包含非正数这导致了滑动窗口不知道往哪边滑因此不能采取。 暴力法枚举出所有的情况最后几个用例超时了(暴力写法纠正)纠正暴力写法之后通过。 动态规划法让我想到了01背包问题01背包包括是否重复选但是这里又和01重复选背包不同这里要求是连续数组。 可以采用前缀和加map一层遍历解决思想和找出数组中两数之和为tar的方法一样。 遍历map写法只要target确定可以考虑这种写法 func subarraySum(nums []int, k int) int {count, pre : 0, 0m : map[int]int{}m[0] 1for i : 0; i len(nums); i {pre nums[i]if _, ok : m[pre - k]; ok {count m[pre - k]}m[pre] 1}return count
} 暴力写法的纠正 // 通过写法
func subarraySum(nums []int, k int) int {preSum : make([]int , len(nums))cv : 0res : 0for i : 0 ; i len(nums); i{cv nums[i]preSum[i] cv}// fmt.Println(preSum)for i : 0 ; i len(nums); i{for j : i ; j len(nums); j{cv : preSum[j]if i ! 0{cv - preSum[i-1]}if cv k{res }}}return res
}
// 超时写法很好理解代码的思路但是超时
func subarraySum(nums []int, k int) int {preSum : make([]int , len(nums))cv : 0res : 0for i : 0 ; i len(nums); i{cv nums[i]preSum[i] cv}// fmt.Println(preSum)for clen: 1; clen len(nums); clen{for i : 0 ; i len(nums) - clen; i{j : i clen - 1if j len(nums){break}cv : preSum[j]if i ! 0{cv - preSum[i-1]}if cv k{res}// fmt.Println(cv)}}return res
}
