最后一块石头的重量
题目：有一堆石头，每块石头的重量都是正整数。每一回合，从中选出两块最重的石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：
如果 x == y，那么两块石头都会被完全粉碎；
如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。
最后，最多只会剩下一块石头。返回此石头的重量。如果没有石头剩下，就返回 0。
提示：
1 <= stones.length <= 30
1 <= stones[i] <= 1000
思路：这道题的思路怎么说呢，就是最大值两两相减，然后差值不是0就存数组重排序，继续找两个最大值。感觉应该比较麻烦但是不难。
emmmmm.....确实是不难，但是我一度在做的时候怀疑自己做错了，毕竟真的很麻烦，不断在新建数组什么的，但是运行性能超过百分之九十八，，所以贴代码下一题：
class Solution {
public int lastStoneWeight(int[] stones) {
if(stones.length==1) return stones[0];
int[] res = getWeight(stones);
while(res.length>1){
res = getWeight(res);
}
return res.length==0?0:res[0];
}
public int[] getWeight(int[] stones){
int index = -1;
int index1 = -1;
int max = 0;
int max1 = 0;
for(int i = 0;i<stones.length;i++){
if(stones[i]>=max){
max1 = max;
max = stones[i];
index1 = index;
index = i;
}else if(stones[i]>max1){
max1 = stones[i];
index1 = i;
}
}
boolean flag = max1==max;
int[] res = new int[flag?stones.length-2:stones.length-1];
int x = 0;
for(int i = 0;i<stones.length;i++){
if(i!=index && i!=index1){
res[x] = stones[i];
x++;
}
}
if(!flag) res[res.length-1] = max-max1;
return res;
}
}
删除字符串中所有相邻重复项
题目：给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。在 S 上反复执行重复项删除操作，直到无法继续删除。在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
示例：
输入："abbaca"
输出："ca"
解释：
例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca"，其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。
提示：
1 <= S.length <= 20000
S 仅由小写英文字母组成。
思路：这道题第一反应递归，直到遍历一次长度不变是递归出口。然后怎么判断就很多样了，刚刚用测试案例测了一下，三个连在一起也只删除两个。这个题做出来很容易，做的优雅很难。我先去实现了。
好的吧，我选择了最不优雅的一种方式：
class Solution {
String s;
public String removeDuplicates(String S) {
s = S;
int res = removeD();
while(removeD() != res){
res = removeD();
}
return s;
}
public int removeD(){
char[] c = s.toCharArray();
for(int i = 0;i<c.length-1;i++){
if(c[i]==c[i+1]){
c[i] = ' ';
c[i+1] = ' ';
i++;
}
}
s = new String(c).replace(" ","");
return s.length();
}
}
但是我决定用更不优雅的一种方式实现：
class Solution {
String s;
public String removeDuplicates(String S) {
s = S;
int res = removeD();
while(removeD() != res){
res = removeD();
}
return s;
}
public int removeD(){
s = s.replace("aa","");
s = s.replace("bb","");
s = s.replace("cc","");
s = s.replace("dd","");
s = s.replace("ee","");
s = s.replace("ff","");
s = s.replace("gg","");
s = s.replace("hh","");
s = s.replace("ii","");
s = s.replace("jj","");
s = s.replace("kk","");
s = s.replace("ll","");
s = s.replace("mm","");
s = s.replace("nn","");
s = s.replace("oo","");
s = s.replace("pp","");
s = s.replace("qq","");
s = s.replace("rr","");
s = s.replace("ss","");
s = s.replace("tt","");
s = s.replace("uu","");
s = s.replace("vv","");
s = s.replace("ww","");
s = s.replace("xx","");
s = s.replace("yy","");
s = s.replace("zz","");
return s.length();
}
}
对的，就这么简单粗暴也没超时。好了好了，心态平和一点了，之前我以为拆分成char肯定性能不错，但是没想到只超过了百分之七十的人，现在看看还是哪里没做好，非要说的话我觉得败笔就是replace那块了，我尝试改进一下。
emmm...好了，性能百分百了，这个string的valueOf一个char，然后确定起始下标和结束下标是刚刚看源码看的，学到一个api而且性能到了百分百，开心，贴最终版的代码：
class Solution {
String s;
public String removeDuplicates(String S) {
s = S;
int res = removeD();
while(removeD() != res){
res = removeD();
}
return s;
}
public int removeD(){
char[] c = s.toCharArray();
char[] res = new char[c.length];
int index = 0;
for(int i = 0;i<c.length;i++){
if(i<c.length-1 && c[i]==c[i+1]){
i++;
continue;
}
res[index] = c[i];
index++;
}
s = String.valueOf(res,0,index);
return s.length();
}
}
高度检查器
题目：学校在拍年度纪念照时，一般要求学生按照 非递减 的高度顺序排列。请你返回至少有多少个学生没有站在正确位置数量。该人数指的是：能让所有学生以 非递减 高度排列的必要移动人数。
示例：
输入：[1,1,4,2,1,3]
输出：3
解释：
高度为 4、3 和最后一个 1 的学生，没有站在正确的位置。
提示：
1 <= heights.length <= 100
1 <= heights[i] <= 100
思路:这道题感觉是以位置主导的。比如除了第一个剩下的都是升序排列，但是因为第一个位置不对，则第一个元素前面的所有人都是错了的。比如 712345、这个错误的就是所有人，因为7站的靠前了，所有人位置都往后了。感觉一个方法就是升序排序，所以下标不是规定值的就res++。我先去实现下，再说自己实现排序的事。
好的，思路没问题，性能也ok，超过百分之九十八的人，一次及格。
class Solution {
public int heightChecker(int[] heights) {
int res = 0;
int[] h1 = new int[heights.length];
int idx = 0;
for(int i :heights){
h1[idx] = i;
idx++;
}
Arrays.sort(heights);
for(int i = 0;i<h1.length;i++){
if(h1[i]!=heights[i]) res++;
}
return res;
}
}
既然这道题这么简单，那就不多浪费时间了，继续下一题。。
字符串的最大公因子
题目：对于字符串 S 和 T，只有在 S = T + ... + T（T 与自身连接 1 次或多次）时，我们才认定 “T 能除尽 S”。返回字符串 X，要求满足 X 能除尽 str1 且 X 能除尽 str2。
示例 1：
输入：str1 = "ABCABC", str2 = "ABC"
输出："ABC"
示例 2：
输入：str1 = "ABABAB", str2 = "ABAB"
输出："AB"
示例 3：
输入：str1 = "LEET", str2 = "CODE"
输出：""
提示：
1 <= str1.length <= 1000
1 <= str2.length <= 1000
str1[i] 和 str2[i] 为大写英文字母
思路：这种题做过类似的，首先要判断的是str1和str2是不是包含关系（短的是长的中的子串），不是的话没办法同时满足两个都除尽。其次就是判重了，我目前的想法反正就是26个英文字母。用数组代替下标查看能构成一组子串的长度，然后判断这个是不是子串。就是这样，可能我表达的不是很清楚，但是思路我觉得还是很靠谱的，我去实现了。
好的吧，做了半天也就这样了，一共写了两个版本，都是1ms，超过百分之九十五的性能。都贴出来分享下：
class Solution {
public String gcdOfStrings(String str1, String str2) {
int l1 = str1.length();
int l2 = str2.length();
if(str1.indexOf(str2)==-1 && str2.indexOf(str1)==-1) return "";
if(str1.equals(str2)) return str1;
int end = maxGcd(Math.abs(l1-l2),l1>l2?l2:l1);
StringBuffer sb = new StringBuffer();
String temp = str1.substring(0,end);
for(int i = 0; i<l1/end;i++){
sb.append(temp);
}
if(!sb.toString().equals(str1)) return "";
StringBuffer sb1 = new StringBuffer();
for(int i = 0; i<l2/end;i++){
sb1.append(temp);
}
if(!sb1.toString().equals(str2)) return "";
return temp;
}
public int maxGcd(int x ,int y){
for(int i=(x>y?y:x);i>=1;i--){
if(x%i==0 && y%i==0) return i;
}
return -1;
}
}
其实这个有个思路，就是因为两个串都要是重叠子串组成的。所以肯定两个串从0开始要一样。直到短的那个没了。然后短的那个从头比较还是要一样，不断重叠，直到长的也没了。
我可能说的不清楚，我画个图、反正就是什么时候比较元素不一样了说明不是重叠字符串，直接返回空串就行了。
首先要确定是不是重叠子串，其次判断最小公因子。这个数应该是较短数组的长度（最大公因子）和长度差的最大公因数。
说下原理，首先这个最大公因子最大也就是较短数组的长度，因为再长点这个较短字符串都不包含了。所以不可能。其次就是长度差，这个如果长度差是1，则说明这个1也是满足重叠子串的，所以这个重叠子串只能是1.
再之后如果长度差是3，而较短串长4.我们这么想：如果重叠串是3，那么较短串不可能满足，同样重叠串4余数不满足。所以只能选择两个数的最大公因数。
最后一步就是根据最大公因数再把这个串拼起来，看是不是之前的str1和str2，不是说明没满足这个规律，直接空串返回。
两个都是说明没找错，可以返回了。
这个题就是表述起来比较墨迹，其实做起来没那么难，直接贴代码：
class Solution {
public String gcdOfStrings(String str1, String str2) {
int l1 = str1.length();
int l2 = str2.length();
if(str1.indexOf(str2)==-1 && str2.indexOf(str1)==-1) return "";
if(str1.equals(str2)) return str1;
int end = maxGcd(Math.abs(l1-l2),l1>l2?l2:l1);
StringBuffer sb = new StringBuffer();
String temp = str1.substring(0,end);
for(int i = 0; i<l1/end;i++){
sb.append(temp);
}
if(!sb.toString().equals(str1)) return "";
StringBuffer sb1 = new StringBuffer();
for(int i = 0; i<l2/end;i++){
sb1.append(temp);
}
if(!sb1.toString().equals(str2)) return "";
return temp;
}
public int maxGcd(int x ,int y){
for(int i=(x>y?y:x);i>=1;i--){
if(x%i==0 && y%i==0) return i;
}
return -1;
}
}
如上代码，这个没我写的那么墨迹，因为判断是不是重叠串组成的部分我给割了。第一遍提交性能没到百分百我觉得是不是来回来去比较耗性能，所以改成就现在这个版本，事实证明还是没到百分百。所以。。我又懒得改回来。
算了，我直接去看排行第一的代码吧：
这个代码处理的很优雅啊~~豁然开朗恍然大悟，我直接贴出来：
class Solution {
public static String gcdOfStrings(String str1, String str2) {
int lenStr1 = str1.length();
int lenStr2 = str2.length();
int rem = gcb(lenStr1, lenStr2);
String str11 = str1.concat(str2);
String str22 = str2.concat(str1);
if (!str11.equals(str22)) {
return "";
} else {
return str1.substring(0, rem);
}
}
//最大公因数
public static int gcb(int a, int b) {
int rem = 0;
while (b != 0) {
rem = a % b;
a = b;
b = rem;
}
return a;
}
}
这里用到的concat是追加的意思（我反正这么理解的）。str1 + str2 == str2+str1 说明这两个字符串是重叠子串组成的，只不过重叠次数不一样相同而已。
然后确定这点就找两个数的最大公因数。而不是我想的那个余数和短数的最大公因数，这块是我想复杂的。最后返回就ok了。简直是。。。别人家的脑子怎么长的呢？
Bigram 分词
题目：给出第一个词 first 和第二个词 second，考虑在某些文本 text 中可能以 "first second third" 形式出现的情况，其中 second 紧随 first 出现，third 紧随 second 出现。对于每种这样的情况，将第三个词 "third" 添加到答案中，并返回答案。
示例 1：
输入：text = "alice is a good girl she is a good student", first = "a", second = "good"
输出：["girl","student"]
示例 2：
输入：text = "we will we will rock you", first = "we", second = "will"
输出：["we","rock"]
提示：
1 <= text.length <= 1000
text 由一些用空格分隔的单词组成，每个单词都由小写英文字母组成
1 <= first.length, second.length <= 10
first 和 second 由小写英文字母组成
思路：这个题我不知道是不是我有点没理解。是不是可以说用空格分隔单词数组，当遇到first的单词以后，选择下下一个单词，遇到second单词以后选择下一个单词就ok了？我去实现下看看。
很好，我理解错了，并且还没明白题意。。。怎么就两个数能有三个结果呢？什么鬼？我再去审题吧。
好的吧，看了N此题终于看懂了，我果然是整个都理解偏了，这个题是第一个单词是first第二个单词是second才会输出第三个单词。。。更简单了有没有。。。我去实现了。
class Solution {
public String[] findOcurrences(String text, String first, String second) {
String[] a = text.split(" ");
String[] b = new String[a.length];
int n = 0;
for(int i = 0;i<a.length-2;i++){
if(a[i].equals(first)&& a[i+1].equals(second)){
b[n] = a[i+2];
n++;
}
}
String[] res = new String[n];
for(int i = 0;i<n;i++){
res[i] = b[i];
}
return res;
}
}
这道题其实真的很简单，就怪我第一次审题没审明白。好了，不多说了，直接过了。
复写0
题目:给你一个长度固定的整数数组 arr，请你将该数组中出现的每个零都复写一遍，并将其余的元素向右平移。
注意：请不要在超过该数组长度的位置写入元素。要求：请对输入的数组 就地 进行上述修改，不要从函数返回任何东西。
示例 1：
输入：[1,0,2,3,0,4,5,0]
输出：null
解释：调用函数后，输入的数组将被修改为：[1,0,0,2,3,0,0,4]
示例 2：
输入：[1,2,3]
输出：null
解释：调用函数后，输入的数组将被修改为：[1,2,3]
提示：
1 <= arr.length <= 10000
0 <= arr[i] <= 9
思路：虽然因为上一题的审题不清让我自己多废了点事，但是这道题我还是很自信的把思路理出来了。我这里的想法就是第一遍遍历数组。判断有几个0.第二遍则是根据0数相应的从后往前填充元素值。我先去实现试试。
好了，实现了，中间各种debug还有修修改改，终于是完事了。这道题不难，但是可能我现在思路比较乱，居然硬生生推翻重做好几次！！
就是思路是有的，但是因为细节没过，我室友还在打王者，真真的日了狗了。。。
好了，直接贴代码：
class Solution {
public void duplicateZeros(int[] arr) {
int n = 0;
int idx = -1;
boolean flag = false;
for(int i = 0;i<arr.length;i++){
if(arr[i]==0) n++;
if(i+n==arr.length-1){
idx = i;
flag = true;
break;
}else if(i+n>arr.length-1){
idx = i;
break;
}
}
int j = arr.length-1;
arr[j] = arr[idx];
j--;
if(arr[idx]==0 && flag) {
arr[j] = 0;
j--;
}
for(int k = j;k>=0;k--){
idx--;
arr[k] = arr[idx];
if(arr[idx]==0){
k--;
if(k>0) arr[k] = 0;
}
}
}
}
首先思路是我之前的思路，就是先看在范围内有几个0 .找到最后一个存储坐标的点。但是有种情况 就是最后一个是0，而且不复制因为没位置，所以要单独提出来处理。
剩下的就没啥了。
一个idx是复制后存在的元素的下标。最后循环的k是当前元素的下标， 我一开始做这两个还弄混了。反正做的乱七八糟的。还是我心不静吧。
分糖果2
题目：排排坐，分糖果。我们买了一些糖果 candies，打算把它们分给排好队的 n = num_people 个小朋友。给第一个小朋友 1 颗糖果，第二个小朋友 2 颗，依此类推，直到给最后一个小朋友 n 颗糖果。然后，我们再回到队伍的起点，给第一个小朋友 n + 1 颗糖果，第二个小朋友 n + 2 颗，依此类推，直到给最后一个小朋友 2 * n 颗糖果。重复上述过程（每次都比上一次多给出一颗糖果，当到达队伍终点后再次从队伍起点开始），直到我们分完所有的糖果。注意，就算我们手中的剩下糖果数不够（不比前一次发出的糖果多），这些糖果也会全部发给当前的小朋友。返回一个长度为 num_people、元素之和为 candies 的数组，以表示糖果的最终分发情况（即 ans[i] 表示第 i 个小朋友分到的糖果数）。
示例 1：
输入：candies = 7, num_people = 4
输出：[1,2,3,1]
解释：
第一次，ans[0] += 1，数组变为 [1,0,0,0]。
第二次，ans[1] += 2，数组变为 [1,2,0,0]。
第三次，ans[2] += 3，数组变为 [1,2,3,0]。
第四次，ans[3] += 1（因为此时只剩下 1 颗糖果），最终数组变为 [1,2,3,1]。
示例 2：
输入：candies = 10, num_people = 3
输出：[5,2,3]
解释：
第一次，ans[0] += 1，数组变为 [1,0,0]。
第二次，ans[1] += 2，数组变为 [1,2,0]。
第三次，ans[2] += 3，数组变为 [1,2,3]。
第四次，ans[0] += 4，最终数组变为 [5,2,3]。
提示：
1 <= candies <= 10^9
1 <= num_people <= 1000
思路：这道题比较简单，就是一圈一圈的分被，直到糖果不够就是出口。感觉比较简单，我直接去写代码。
一次搞定，而且性能超过百分之九十三，也算是及格了，因为题目简单也不多说什么了，直接贴上代码：
class Solution {
public int[] distributeCandies(int candies, int num_people) {
int[] res = new int[num_people];
int n = 1;
while (candies>0){
for(int i = 0;i<res.length;i++){
if(candies>n){
res[i] +=n;
candies -= n;
n++;
}else{
res[i] += candies;
return res;
}
}
}
return res;
}
}
今天的笔记就记到这里，如果稍微帮到你了记得点个喜欢点个关注~~~也祝大家工作顺顺利利，周末愉快！
