🤞目录🤞
【大家好，我是爱干饭的猿，如果喜欢这篇文章，点个赞👍，关注一下吧，后续会一直分享题目与算法思路】
🚀1. 和为S的连续正数序列
描述
小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列?
例
编辑
返回值描述
输出所有和为S的连续正数序列。序列内按照从小至大的顺序，序列间按照开始数字从小到大的顺序
解题思路：
根据题意我们知道一个数sum，我们需要找到sum是由哪些连续的整数所组成的。
🎈思路一：
1. 我们可以遍历1到sum，从第一个数开始令total = 这个数;
2. 当total < sum 时，total += （i++）；
3. 当total == sum 时，组成 total 的数就是组成sum的数;
4. 当total > sum 时，total 遍历到下一个数；
🎈思路二：（用到滑动窗口）
1. 定义开始数字start，结束数字end，当start < end 时一直循环；
2. 当start加到end的和 == sum 时，start到end 之间的数就是组成sum的数；
3. 当start加到end的和 < sum 时，说明该序列区间中的数据和小于sum，应该扩大区间,以包含更多数据 end++；
4. 当start加到end的和 > sum 时，说明该序列区间中的数据和大于sum，应该缩小区间,以包含较少数据 start++;
🚡思路一：代码如下：
// 方法一： public static ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) { ArrayList<ArrayList<Integer>> result = new ArrayList<>(); //1. 我们可以遍历1到sum，从第一个数开始令total = 这个数 for (int i = 1; i < sum; i++) { ArrayList<Integer> list = new ArrayList<>(); int total = 0; int j = i; // 2. 当total < sum 时，total += （i++） while (total < sum){ total += j; list.add(j); j++; } // 3. 当total == sum 时，组成 total 的数就是组成sum的数 if(total == sum){ System.out.println(); result.add(list); } // 4. 当total > sum 时，total 遍历到下一个数 } return result; }
🚡思路二：代码如下：
// 方法二：滑动窗口 // 通项公式为：an=a1+(n-1)*d。首项a1=1，公差d=2。 // 前n项和公式为：Sn=a1*n+[n*(n-1)*d]/2或Sn=[n*(a1+an)]/2。 // 注意：以上n均属于正整数 public static ArrayList<ArrayList<Integer> > FindContinuousSequence2(int sum) { ArrayList<ArrayList<Integer>> result = new ArrayList<>(); // 1. 定义开始数字start，结束数字end int start = 1; int end = 2; // 当start < end 时一直循环 while (start < end){ int total = (start + end)*(end-start+1)/2; // 2. 当start加到end的和 == sum 时，start到end 之间的数就是组成sum的数； if(total == sum){ ArrayList<Integer> list = new ArrayList<>(); for (int i = start; i <= end; i++) { list.add(i); } result.add(list); start++; }else if(total > sum){ // 3. 当start加到end的和 < sum 时，说明该序列区间中的数据和小于sum， // 应该扩大区间,以包含更多数据 end++； start++; }else { // 4. 当start加到end的和 >sum 时，说明该序列区间中的数据和大于sum， // 应该缩小区间,以包含较少数据 start++; end++; } } return result; }
🚀2. 左旋转字符串
描述
汇编语言中有一种移位指令叫做循环左移（ROL），现在有个简单的任务，就是用字符串模拟这个指令的运算结果。对于一个给定的字符序列 S ，请你把其循环左移 K 位后的序列输出。例如，字符序列 S = ”abcXYZdef” , 要求输出循环左移 3 位后的结果，即 “XYZdefabc”
例
编辑
编辑
解题思路：
🎈思路一：根据题意循环左移，拆解一下：
1. 向左移动一次，需要保存第一个，剩下的整体前移一个，第一个放在最后，完成一次移动；
2. 左移k次即可，（需要注意的是，若k > 元素个数，k = k % str.length() 即可，减少不必要的重复）；
🎈思路二：局部逆置，在整体逆置；
我们发现一件很神奇的事，如果字符串要左移k位，我们可以将0-k位逆置，将(k+1)-末位逆置，整体逆置，（三次逆置不分先后）结果正是我们循环左移的结果。
🚡思路一：代码如下：
// 方法一 data[j] = data[j+1] public static String LeftRotateString(String str,int n) { if(str == null || str.length() == 0){ return new String(""); } char[] data = str.toCharArray(); // 2. 左移k次即可 for(int i = 0;i < n;i++){ // 1. 向左移动一次，需要保存第一个，剩下的整体前移一个，第一个放在最后，完成一次移动 char temp = data[0]; for(int j = 0;j < data.length-1;j++){ data[j] = data[j+1]; } data[data.length -1] = temp; } String result = ""; for(char a:data){ result += a; } return result; }
🚡思路二：代码如下：
// 方法二 三遍数组逆置 public static String LeftRotateString2(String str,int n) { if(str == null || str.length() == 0){ return new String(""); } n = n % str.length(); char[] data = str.toCharArray(); // 整体逆置 inversion(data,0,data.length-1); // 将0-k位逆置 inversion(data,0,data.length-1 - n); // 将(k+1)-末位逆置 inversion(data,data.length - n,data.length-1); String result = ""; for(char a:data){ result += a; } //System.out.println(result.toString()); return result; } private static void inversion(char[] data, int start, int end) { while (start < end){ char temp = data[start]; data[start] = data[end]; data[end] = temp; start++; end--; } }
🚀3. 翻转单词序列
描述
牛客最近来了一个新员工Fish，每天早晨总是会拿着一本英文杂志，写些句子在本子上。同事Cat对Fish写的内容颇感兴趣，有一天他向Fish借来翻看，但却读不懂它的意思。例如，“nowcoder. a am I”。后来才意识到，这家伙原来把句子单词的顺序翻转了，正确的句子应该是“I am a nowcoder.”。Cat对一一的翻转这些单词顺序可不在行，你能帮助他么？
例
编辑
解题思路：
🎈思路一：
1. 将字符串转为String 数组，定义一个String类型的result；
2. 倒着遍历数组，使result+=data[i]，result即为翻转后的结果；
🎈思路二：局部逆置，在整体逆置；
我们发现这道题和上道题有相似之处，我们只需将每个单词逆置，然后整体逆置，结果就是翻转后的结果。
🚡思路一：代码如下：
// 方法一 字符串逆置 + 拼接 public String ReverseSentence(String str) { // 1. 将字符串转为String 数组 String[] data = str.split(" "); // 定义一个String类型的result String result = ""; // 2. 倒着遍历数组，使result+=data[i]，result即为翻转后的结果。 for(int i = data.length-1;i >= 0 ;i--){ if(i == 0){ result += data[i]; }else{ result += data[i] += " "; } } return result; }
🚡思路二：代码如下：
// 方法二 单个字符串逆置 + 总体逆置 public static String ReverseSentence2(String str) { if(str == null || str.length() == 0){ return str; } char[] data = str.toCharArray(); int i = 0; int j = i; while (i < data.length){ while (i < data.length && str.charAt(i) != ' ') i++; reverse(data,j,i-1); while (i < data.length && str.charAt(i) == ' ') i++; j = i; } reverse(data,j,i-1); reverse(data,0,i-1); return new String(data); } private static void reverse(char[] data, int start, int end) { while (start < end){ char temp = data[start]; data[start] = data[end]; data[end] = temp; start++; end--; } }
