第六周 - 《leetcode》

周一
https://leetcode-cn.com/problems/range-sum-query-immutable/
周二
https://leetcode-cn.com/problems/power-of-three/
周三
https://leetcode-cn.com/problems/counting-bits/
周四
https://leetcode-cn.com/problems/power-of-four/
周五
https://leetcode-cn.com/problems/reverse-string/
周六
https://leetcode-cn.com/problems/reverse-vowels-of-a-string/

周三
比特位计数
给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数，返回一个长度为 n + 1 的数组 ans 作为答案。
tips:题目要计算从0到 N 的每个元素的1 比特位有多少,看进阶要求你需要注意每一次计算之后的信息积累;也就是前一次计算的结果和后一次计算的结果是否有关系,我们需要构建一个动态方程

进阶要求
很容易就能实现时间复杂度为 O(n log n) 的解决方案，你可以在线性时间复杂度 O(n) 内用一趟扫描解决此问题吗？
你能不使用任何内置函数解决此问题吗？（如，C++ 中的 __builtin_popcount ）

/**
@param  {number} n 
@return  {number[]} 
*/
// 0 --> 0  ---0
// 1 --> 1  ---2^0
// 2 --> 10 ---2^1
// 3 --> 11 ---最高位2^1
// 4 --> 100---2^2
// 5 --> 101---最高位2^2
// 15 = 8+7  --> 最高位 8(防止看不懂)
// 每一个数都是由最高比特位 + 其他值构成的在二进制中为
//                1      0 0 0 0
//            最高比特位  其他位自由填充
//所以存在一个数x 它的最高比特位是 highBit,存在一个数小于x z<=x,那他们之间的关系应该是
// bits[x] = 1(最高比特位固定为1)+bits[z] 其中 x = highbits +z
//所以我们就找到dp方程
//dp[x] = dp[x-heighbits] +1
var countBits = function(n) {
//最高有效位
//初始化数组
const result = new Array(n+1).fill(0)
let heighbits = 0
for(let i =1;i<=n;++i){
if((i&(i-1)) ===0 ){
heighbits=i
}
result[i] = result[i-heighbits]+1
}
return result
};

/**
@param  {number} n 
@return  {number[]} 
*/
//  Brian Kernighan 算法的原理是：对于任意整数 xx，令 x=x&(x-1)x=x & (x−1)，
// 该运算将 xx 的二进制表示的最后一个 11 变成 00。因此，对 xx 重复该操作，直到 xx 变成 00，
// 则操作次数即为 xx 的「一比特数」。

var countBits = function(n) {
//暴力法
function getBits(num){
let bits = 0
while(num !==0){
bits++
num = num &(num-1)
}
return bits
}
const result = new Array(n+1).fill(0)
for(let i = 1;i<=n;i++){
result[i]= getBits(i)
}
return result
};

/**
@param  {number} n 
@return  {number[]} 
*/
var countBits = function(n) {
//最低位,我是这么理解的
//做位运算,每次都往左侧移动一位,如果是偶数就不加1,奇数
const result = new Array(n+1).fill(0)//初始化
for(let i=1;i<=n;++i){
//dp方程
//  111111 缩小一位,但是你并不知道这一位有没有1 ,所以你要先判定最小位置上是不是有1 通过和 ...0000001与运算
//[i] 你直接把这个看成一个二进制标志,而不是十进制可能会更好的去理解
//[i 10] [i 2]其实都是标志一个位置,你用[i (10) -1]表示位置的运动
//[i (2) >>1]也是表示位置的移动
//dp[i] = dp[i>>1]+ (i&(1))
result[i] = result[i>>1] + (i&1)
}
return result
};

/**

/**
@param  {number} n 
@return  {number[]} 
*/
//第四种解法叫做最小设置
//首先我想说你怎么去理解 (i &(i-1))这个操作
//10 & 9 =8
// 1010
// 1001 这种比较好像把低位 给打乱然后得出最高位置

//9&8
// 1001
// 1000  ->8

//12&11  ->8
// 1100
// 1011

// 15&14 14
// 1111
// 1110
//从与运算的结果来看,并没有固定规律
//  官方的意思是这样会得到一个方程
// y = x&(x-1)
// dp[x] = dp[x&(x-1)]+1
//也就是与运算会导致有一位从1变成0  这也对应了暴力解法,
//每次执行这样一个操作就会有一个位从1变成0

var countBits = function(n) {
const result = new Array(n+1).fill(0)
for(let i=1;i<=n;++i){
result[i]= result[(i&(i-1))]+1
}
return result

};

从这里你可以发现,动态规划本质需要两个:1 初始值 2 dp方程
tips:

周一
区域和检索 - 数组不可变
给定一个整数数组 nums，求出数组从索引 i 到 j（i ≤ j）范围内元素的总和，包含 i、j 两点。
实现 NumArray 类：
NumArray(int[] nums) 使用数组 nums 初始化对象
int sumRange(int i, int j) 返回数组 nums 从索引 i 到 j（i ≤ j）范围内元素的总和，包含 i、j 两点（也就是 sum(nums[i], nums[i + 1], … , nums[j])）

/**

@param  {number[]} nums 
*/
var NumArray = function(nums) {
this.localNumArray = [...nums]
this.sumArray = []
if(this.localNumArray.length>0) this.sumArray.push(this.localNumArray[0])
for(let i=1;i<this.localNumArray.length;++i){
this.sumArray[i] = this.sumArray[i-1]+this.localNumArray[i]
}

};

/**
@param  {number} left 
@param  {number} right 
@return  {number} 
*/
NumArray.prototype.sumRange = function(left, right) {
if(left<right){
return this.sumArray[right]-this.sumArray[left]+this.localNumArray[left]
}else if(left===right){
return this.localNumArray[left]
}

};

Your NumArray object will be instantiated and called as such:
var obj = new NumArray(nums)
var param_1 = obj.sumRange(left,right)
*/

周二
3的幂
两种解法

/**

@param  {number} n 
@return  {boolean} 
*/
var isPowerOfThree = function(n) {
//暴力法
//通过列举一系列数字我发现一个规律
//3^0 =1
//3^1 = 3
//3^2 =9
//3^3=27
//3^4 =81
//你会发现 结尾是一个循环 1-3-9-7
// 建立一个对象
const reflection = {
3:3,
9:9,
7:27,
1:81
}
while(n!1){//n1就说明是幂次方
if((n%10)===3){
n = n/reflection[3]
}else if((n%10)===9){
n=n/reflection[9]
}else if((n%10)===7){
n=n/reflection[7]
}else if((n%10)===1){
n=n/reflection[1]
}else{
return false
}
}
return true
};
/**
@param  {number} n 
@return  {boolean} 
*/
var isPowerOfThree = function(n) {
//3 的三进制是 ......01
//9 的三进制是 ......10
//也就是转化成三进制之后只会有一个3
const test = new RegExp('^10*'
console.log(n.toString(3))
return test.test(n.toString(3))
};

周四
给定一个整数，写一个函数来判断它是否是 4 的幂次方。如果是，返回 true ；否则，返回 false 。
整数 n 是 4 的幂次方需满足：存在整数 x 使得 n == 4x

/**
@param  {number} n 
@return  {boolean} 
*/
var isPowerOfFour = function(n) {
//不让使用循环,我可以使用3的幂次方的套路
const test = new RegExp('^10*$')
return test.test(n.toString(4))
};

数论中的重要概念,给定一个正整数 m,如果两个整数 a 和 b 满足 (a-b)能够被 m 整除,即
(a-b)/m得到一个整数,那么就称整数 a 对 b 对模同余
a=4,b=1 m=3

/**

@param  {number} n 
@return  {boolean} 
*/
var isPowerOfFour = function(n) {
return (n%3 ===1)&&((n&(n-1))===0)
};

tips 有没有更好的办法?
周五
反转字符串
编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。

不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。

/**

@param  {character[]} s 
@return  {void} Do not return anything, modify s in-place instead. 
*/
var reverseString = function(s) {
//s是一个数组
let left = 0
let right = s.length-1
while(left<right){
[s[left],s[right]] = [s[right],s[left]]
left++
right--
}
return s
};

周六
反转字符串中的元音字母

给你一个字符串 s ，仅反转字符串中的所有元音字母，并返回结果字符串。

元音字母包括 ‘a’、’e’、’i’、’o’、’u’，且可能以大小写两种形式出现。

/**

 @param  {string} s  
 @return  {string} 
*/
var reverseVowels = function(s) {
let sArray = s.split('')
let left = 0
let right = sArray.length-1
let oArray = 'aeiouAEIOU'.split('')
// console.log(sArray)
while(left<right){
let leftChar = sArray[left]
let rightChar = sArray[right]
let leftIndex = oArray.indexOf(leftChar)
let rightIndex = oArray.indexOf(rightChar)
if(leftIndex>-1 && rightIndex>-1){
[sArray[left],sArray[right]] = [sArray[right],sArray[left]]
left++
right--
// console.log(rightChar)
}
if(leftIndex===-1){
left++
}
if(rightIndex===-1){
right--
} 

}
return sArray.join('')
};

//不知道为啥这个题做了这么久