K取反后最大化数组和
题目：给定一个整数数组 A，我们只能用以下方法修改该数组：我们选择某个个索引 i 并将 A[i] 替换为 -A[i]，然后总共重复这个过程 K 次。（我们可以多次选择同一个索引 i。）以这种方式修改数组后，返回数组可能的最大和。
示例 1：
输入：A = [4,2,3], K = 1
输出：5
解释：选择索引 (1,) ，然后 A 变为 [4,-2,3]。
示例 2：
输入：A = [3,-1,0,2], K = 3
输出：6
解释：选择索引 (1, 2, 2) ，然后 A 变为 [3,1,0,2]。
示例 3：
输入：A = [2,-3,-1,5,-4], K = 2
输出：13
解释：选择索引 (1, 4) ，然后 A 变为 [2,3,-1,5,4]。
提示：
1 <= A.length <= 10000
1 <= K <= 10000
-100 <= A[i] <= 100
思路：这道题感觉不是很复杂。分几种情况：有负数的情况下，从小到大能都取反就取反，不能挑小的取。如果k还有剩余挑最小的来回来去返来返去。就是酱。同样如果没负数直接最小的数返来返去，我去尝试代码实现了。
做是做出来了，2ms执行速度，只超过了百分之六十多，先把代码贴上：
class Solution {
public int largestSumAfterKNegations(int[] A, int K) {
Arrays.sort(A);
int s = 0;
for(int i : A){
if(i<0) s++;
}
int sum = 0;
if(s>K){
for(int i = 0;i<K;i++){
sum += Math.abs(A[i]);
}
for(int i = K;i<A.length;i++){
sum += A[i];
}
return sum;
}
if(s<=K){
int min = Integer.MAX_VALUE;
for(int i : A){
int n = Math.abs(i);
min = min>n?n:min;
sum += n;
}
//偶数
if(((K-s)&1)==0) return sum;
return sum-2*min;
}
return -1;
}
}
想来想去看来看去我觉得我这个性能可能是浪费在了sort上？好的，我看了性能排行第一的代码，我的问题就是出现在sort上。。。
其实这个题依然就是数组下标代替值的标准做法，只不过我当时没想到或者没打算这么麻烦的做，果然怕麻烦就得牺牲性能~~我先贴代码了：
class Solution {
public int largestSumAfterKNegations(int[] A, int K) {
//相当于捅排序，下标为A的元素。A[i]范围是-100 100
int[] nums = new int[201];
for (int a : A) {
// 转为0-200
nums[a + 100]++;
}
int i = 0;
while (K > 0) {
while (nums[i] == 0) {
i++;
}
// 反转A[i]，假设 i 100 j，那么有100-i=j-100,即j=200-i
nums[i]--;
nums[200 - i]++;
// i>100那么反转后小于100
if (i > 100) {
i = 200 - i;
}
K--;
}
int ans = 0;
for (int j = i; j < nums.length; j++) {
ans += nums[j] * (j - 100);
}
return ans;
}
}
就是如上代码，其实很容易理解，排序是为了知道哪些是更小的数值。而这里用了数组也使得知道了哪些的更小的数值（0-100之间是负数，越往后绝对值越小）。反正这个题就这样吧， 下一题了。
十进制整数的反码
题目：每个非负整数 N 都有其二进制表示。例如， 5 可以被表示为二进制 "101"，11 可以用二进制 "1011" 表示，依此类推。注意，除 N = 0 外，任何二进制表示中都不含前导零。二进制的反码表示是将每个 1 改为 0 且每个 0 变为 1。例如，二进制数 "101" 的二进制反码为 "010"。给定十进制数 N，返回其二进制表示的反码所对应的十进制整数。
示例 1：
输入：5
输出：2
解释：5 的二进制表示为 "101"，其二进制反码为 "010"，也就是十进制中的 2 。
示例 2：
输入：7
输出：0
解释：7 的二进制表示为 "111"，其二进制反码为 "000"，也就是十进制中的 0 。
示例 3：
输入：10
输出：5
解释：10 的二进制表示为 "1010"，其二进制反码为 "0101"，也就是十进制中的 5 。
提示：
0 <= N < 10^9
思路：讲真，这样的题我感觉不仅做过一遍了。0变1，1变0的最好办法就是与一堆1进行异或运算。但是因为前面没有位数，所以要先知道这个二进制的长度，想想就麻烦。。。都不如直接拼了。这道题怎么说呢，做过N次类似的，实现办法很多，但是真下手还有点不知道选择哪种方法好，正好闲着，一会儿把所有能想到的方法都写一遍。我去写代码了。
第一种方式：无脑调用，各种api
class Solution {
public int bitwiseComplement(int N) {
if(N==0) return 1;
StringBuilder sb = new StringBuilder();
while(N>0){
sb.append(N%2==1?0:1);
N = N/2;
}
sb.reverse();
return Integer.valueOf(sb.toString(), 2);
}
}
第二种方式：和1异或。1的位数取决于原数的二进制位数
class Solution {
public int bitwiseComplement(int N) {
if(N==0) return 1;
int x = N;
int y = 0 ;
while(x>0) {
y = y*2+1;
x =x/2;
}
return y^N;
}
}
剩下实现的办法多种多样，但是本质上要么字符串拼接，要么二进制操作。我看了性能排行第一的代码（上面两个都是2ms。第一的1ms），我以为二进制操作就是&，^之类的。但是人家用的更多，各种位移，好吧，又涉及到知识盲区了，单纯的看是能看懂的，但是让我自己设计就发懵，仅仅停留在知道位移是啥，给我一个我能扣扣搜搜的位移出结果，但是让我张口就来做不到。所以我这现在就先这样了，二进制以后有空专门补补位移的知识。顺便附上第一的代码然后下一题 了。
class Solution {
public int bitwiseComplement(int N) {
if(N==0){
return 1;
}
int res=0;
int i=0;
while(N!=0){
if((N&1)==0){
res|=1<<i;
}
i++;
N>>=1;
}
return res;
}
}
总持续时间可被60整除的歌曲
题目：在歌曲列表中，第 i 首歌曲的持续时间为 time[i] 秒。返回其总持续时间（以秒为单位）可被 60 整除的歌曲对的数量。形式上，我们希望索引的数字 i < j 且有 (time[i] + time[j]) % 60 == 0。
示例 1：
输入：[30,20,150,100,40]
输出：3
解释：这三对的总持续时间可被 60 整数：
(time[0] = 30, time[2] = 150): 总持续时间 180
(time[1] = 20, time[3] = 100): 总持续时间 120
(time[1] = 20, time[4] = 40): 总持续时间 60
示例 2：
输入：[60,60,60]
输出：3
解释：所有三对的总持续时间都是 120，可以被 60 整数。
提示：
1 <= time.length <= 60000
1 <= time[i] <= 500
思路：感觉这个题应该叫做可被60整除的歌曲对啊。反正思路就是从第一个开始算，挨个和后面相加能不能被60整除，能则res+1.不能继续往后，然后一个双循环解决问题，这里前面和后面的组成对了，后面就不能和前面再组对。所以第一个循环起始i=0，第二个循环起始应该是j=i+1，感觉思路挺明确的，我去实现看看。
很好，无脑暴力法超时了，但是思路逻辑是没问题了，我还是要贴上来以供参考：
class Solution {
public int numPairsDivisibleBy60(int[] time) {
int res = 0;
for(int i = 0;i<time.length-1;i++){
for(int j = i+1;j<time.length;j++){
if((time[i]+time[j])>=60 && (time[i]+time[j])%60==0) res++;
}
}
return res;
}
}
剩下的就是怎么把暴力法更加优雅的实现，我重新申了下题目，发现这个数值的范围是1-500。而数组长度6万。所以很明显这道题可以相同秒数的一起判断。这个时间和其他所有能组成60倍数的次数*这个时间本身的次数。但是有一点要注意，就是如果这个时间可以和她自己组成60则要单独算，因为不能双向算。比如60 60 60 只是三次而不是6次。
刚在草稿上找半天这个规律（好不好看都对付看吧）：
剩下的其实和暴力法差别不大了，都是从头开始算，只与后面的比较。我去实现了。
emmmmmm....首先做出来了可喜可贺，其次性能只超过百分之四十。。先贴上代码吧：
class Solution {
public int numPairsDivisibleBy60(int[] time) {
int res = 0;
int[] a = new int[501];
for(int i :time){
a[i]++;
}
for(int i = 0;i<500;i++){
if(a[i]==0) continue;
if(a[i]>1 && i>=30 && i*2%60==0) res += a[i]*(a[i]-1)/2;
int s = 0;
for(int j = i+1;j<501;j++){
if(a[j]==0) continue;
if((i+j)>=60 && (i+j)%60==0) s += a[j] ;
}
res += s*a[i];
}
return res;
}
}
优化一下又一下，从6ms到4ms，排名一名没进，我怀疑我思路错了？做复杂了？正常应该0ms或1ms完成的？
class Solution {
public int numPairsDivisibleBy60(int[] time) {
int res = 0;
int[] a = new int[501];
for(int i :time){
a[i]++;
}
for(int i = 0;i<500;i++){
if(a[i]>0){
if(i>=30 && i*2%60==0) res += a[i]*(a[i]-1)/2;
int s = 0;
for(int j = i+1;j<501;j++){
if(a[j]>0 && (i+j)>=60 && (i+j)%60==0) s += a[j] ;
}
if(s>0) res += s*a[i];
}
}
return res;
}
}
我再好好理理思路。
好的吧，我直接看了性能第一的代码：我是500以内的计算。其实60的倍数直接计算余数就好了，所以人家是60以内的计算，而且这个的好出就是只有余数是0和30的时候有可能自身相加是60倍数。不用做那么多无用的判断了。整体来说如下代码：
class Solution {
public int numPairsDivisibleBy60(int[] time) {
int res = 0;
int[] a = new int[60];
for(int i :time){
a[i%60]++;
}
res += a[0]*(a[0]-1)/2;
res += a[30]*(a[30]-1)/2;
for(int i = 0;i<59;i++){
if(a[i]>0){
int s = 0;
for(int j = i+1;j<60;j++){
if(a[j]>0 && i+j==60) s += a[j] ;
}
if(s>0) res += s*a[i];
}
}
return res;
}
}
这道题确实是思路上的不到位，其实不难想到，只不过没这个意识。下次会记得这个方法。
将数组分成和相等的三个部分
题目：给定一个整数数组 A，只有我们可以将其划分为三个和相等的非空部分时才返回 true，否则返回 false。形式上，如果我们可以找出索引 i+1 < j 且满足 (A[0] + A[1] + ... + A[i] == A[i+1] + A[i+2] + ... + A[j-1] == A[j] + A[j-1] + ... + A[A.length - 1]) 就可以将数组三等分。
示例 1：
输出：[0,2,1,-6,6,-7,9,1,2,0,1]
输出：true
解释：0 + 2 + 1 = -6 + 6 - 7 + 9 + 1 = 2 + 0 + 1
示例 2：
输入：[0,2,1,-6,6,7,9,-1,2,0,1]
输出：false
示例 3：
输入：[3,3,6,5,-2,2,5,1,-9,4]
输出：true
解释：3 + 3 = 6 = 5 - 2 + 2 + 5 + 1 - 9 + 4
提示：
3 <= A.length <= 50000
-10000 <= A[i] <= 10000
思路：这道题怎么说呢，送分题？反正最笨的思路就是整体相加，除3.再用这个值取数组套。反正就是两次循环而已，我去实现了。
想法不错，实现了，性能不行还得优化，贴上第一版代码：
class Solution {
public boolean canThreePartsEqualSum(int[] A) {
int sum = 0;
for(int i : A){
sum += i;
}
if(sum%3!=0) return false;
int s = sum/3;
int temp = 0;
for(int i : A){
s -= i;
if(s==0){
s=sum/3;
temp++;
if(temp==2) return true;
}
}
return false;
}
}
因为比较简单不知道从哪里优化，所以直接看了排行第一的代码，只能说我仍然选择我这种性能不是那么好的写法：
class Solution {
public boolean canThreePartsEqualSum(int[] A) {
int count=0;
for(int i=0;i<A.length;i++) {
count+=A[i];
}
double sum=(double)count/3;
if(sum%1!=0) {
return false;
}
int arr=(int)sum;
int left=0;
int right=A.length-1;
int arr1=0;
int arr2=0;
while(left<=right) {
if(arr1!=arr) {
arr1+=A[left];
left++;
}else {
break;
}
}
while(right>=0) {
if(arr2!=arr) {
arr2+=A[right];
right--;
}else {
break;
}
}
if(left<=right) {
return true;
}
return false;
}
}
ps：一样的代码我又重复提交了几次，果然从百分之四十到了百分之九十九。只能说这个效率比较接近，所以差1ms天壤之别。下一题吧。
可被5整除的二进制前缀
题目：给定由若干 0 和 1 组成的数组 A。我们定义 N_i：从 A[0] 到 A[i] 的第 i 个子数组被解释为一个二进制数（从最高有效位到最低有效位）。返回布尔值列表 answer，只有当 N_i 可以被 5 整除时，答案 answer[i] 为 true，否则为 false。
示例 1：
输入：[0,1,1]
输出：[true,false,false]
解释：
输入数字为 0, 01, 011；也就是十进制中的 0, 1, 3 。只有第一个数可以被 5 除，因此 answer[0] 为真。
示例 2：
输入：[1,1,1]
输出：[false,false,false]
示例 3：
输入：[0,1,1,1,1,1]
输出：[true,false,false,false,true,false]
示例 4：
输入：[1,1,1,0,1]
输出：[false,false,false,false,false]
提示：
1 <= A.length <= 30000
A[i] 为 0 或 1
思路：这个题对我而言比较复杂，审题就复杂，主要是一开始思路错了。不应该考虑什么二进制转化成数字之类的，应该直接只取十进制尾数。 每次有新的二进制尾数追加，原来的尾数进1则2，然后加上新的尾数。如果能被0/5整除说明是5的倍数，不能则不是。（ps：这个思路是在做之前群里大佬指点的思路。）我去实现了。*
很好，因为思路很清晰所以做着也很方便，一次通过：
class Solution {
public List<Boolean> prefixesDivBy5(int[] A) {
List<Boolean> res = new ArrayList<Boolean>();
int temp = 0;
for(int i : A){
temp = temp*2+i;
temp = temp%10;
if(temp==0 || temp==5){
res.add(true);
}else{
res.add(false);
}
}
return res;
}
}
性能超过百分之九十五。其实感觉优化的地方就是这些计算了。比如这里的*2可以用左移1来代替。不过到底用不习惯所以我这里还是用的乘法。就当加强自己对二进制运算的使用吧。下一题。
删除最外层的括号
题目：有效括号字符串为空 ("")、"(" + A + ")" 或 A + B，其中 A 和 B 都是有效的括号字符串，+ 代表字符串的连接。例如，""，"()"，"(())()" 和 "(()(()))" 都是有效的括号字符串。如果有效字符串 S 非空，且不存在将其拆分为 S = A+B 的方法，我们称其为原语（primitive），其中 A 和 B 都是非空有效括号字符串。给出一个非空有效字符串 S，考虑将其进行原语化分解，使得：S = P_1 + P_2 + ... + P_k，其中 P_i 是有效括号字符串原语。对 S 进行原语化分解，删除分解中每个原语字符串的最外层括号，返回 S 。
示例 1：
输入："(()())(())"
输出："()()()"
解释：
输入字符串为 "(()())(())"，原语化分解得到 "(()())" + "(())"，
删除每个部分中的最外层括号后得到 "()()" + "()" = "()()()"。
示例 2：
输入："(()())(())(()(()))"
输出："()()()()(())"
解释：
输入字符串为 "(()())(())(()(()))"，原语化分解得到 "(()())" + "(())" + "(()(()))"，
删除每隔部分中的最外层括号后得到 "()()" + "()" + "()(())" = "()()()()(())"。
示例 3：
输入："()()"
输出：""
解释：
输入字符串为 "()()"，原语化分解得到 "()" + "()"，
删除每个部分中的最外层括号后得到 "" + "" = ""。
提示：
S.length <= 10000
S[i] 为 "(" 或 ")"
S 是一个有效括号字符串
思路：这道题怎么说呢，说难不难，说简单不简单，以前做过类似的就是判断括号是否合法。其实我觉得这道题的思路就是删除整除串中最外围的所有括号。感觉就是看括号外面有没有括号了，没有就是外层的，直接删除。不出意外应该是一次遍历就可以了。我去代码实现看看。
思路没啥问题，就是查看最外层有没有括号。有的话不要动，追加到新串，没有的话就不追加，相当于另类的删除。
class Solution {
public String removeOuterParentheses(String S) {
StringBuilder sb = new StringBuilder();
int level = -1;
for (char c : S.toCharArray()) {
if (c == ')') level--;
if (level >= 0) sb.append(c);
if (c == '(') level++;
}
return sb.toString();
}
}
如图所示，当level等于-1的时候说明是最外层的括号，所以不追加。
然后这道题其实代码不难，只要思路理清楚了就很容易做。
今天的笔记就做到这里，今天遇到的都是不是很难实现的代码题，而是单纯的思路题，刷的很舒服。哈哈，如果这篇笔记稍微帮到你了记得点个喜欢点个关注，也祝大家工作顺顺利利~~！
