【迎战蓝桥】 算法·每日一题(详解+多解)-- day10

简介: 💖1. 和为S的连续正数序列💖2. 左旋转字符串💖3. 翻转单词序列

 

🤞目录🤞

💖1. 和为S的连续正数序列

💖2. 左旋转字符串

💖3. 翻转单词序列


【大家好,我是爱干饭的猿,如果喜欢这篇文章,点个赞👍,关注一下吧,后续会一直分享题目与算法思路


🚀1. 和为S的连续正数序列

描述

小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列?

image.gif编辑

返回值描述

输出所有和为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;
    }

image.gif

🚡思路二:代码如下:  

// 方法二:滑动窗口
    // 通项公式为: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;
    }

image.gif


🚀2. 左旋转字符串

描述

汇编语言中有一种移位指令叫做循环左移(ROL),现在有个简单的任务,就是用字符串模拟这个指令的运算结果。对于一个给定的字符序列  S ,请你把其循环左移 K 位后的序列输出。例如,字符序列 S = ”abcXYZdef” , 要求输出循环左移 3 位后的结果,即 “XYZdefabc”

image.gif编辑

image.gif编辑

解题思路:

🎈思路一:根据题意循环左移,拆解一下:

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;
    }

image.gif

🚡思路二:代码如下:

// 方法二 三遍数组逆置
    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--;
        }
    }

image.gif


🚀3. 翻转单词序列

描述

牛客最近来了一个新员工Fish,每天早晨总是会拿着一本英文杂志,写些句子在本子上。同事Cat对Fish写的内容颇感兴趣,有一天他向Fish借来翻看,但却读不懂它的意思。例如,“nowcoder. a am I”。后来才意识到,这家伙原来把句子单词的顺序翻转了,正确的句子应该是“I am a nowcoder.”。Cat对一一的翻转这些单词顺序可不在行,你能帮助他么?

image.gif编辑

解题思路:

🎈思路一:

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;
    }

image.gif

🚡思路二:代码如下:

// 方法二 单个字符串逆置 + 总体逆置
    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--;
        }
    }

image.gif

相关文章
|
算法
单链表(算法面试题2)---单链表进阶2 一题多解,逐步优化
单链表(算法面试题2)---单链表进阶2 一题多解,逐步优化
56 0
|
6月前
|
存储 人工智能 算法
【算法——动态规划】蓝桥ALGO-1007 印章(C/C++)
【算法——动态规划】蓝桥ALGO-1007 印章(C/C++)
【算法——动态规划】蓝桥ALGO-1007 印章(C/C++)
|
6月前
|
算法 C++
蓝桥 算法训练 共线(C++)
蓝桥 算法训练 共线(C++)
|
11月前
|
存储 算法 安全
【数据结构与算法初学者指南】【冲击蓝桥篇】String与StringBuilder的区别和用法
【数据结构与算法初学者指南】【冲击蓝桥篇】String与StringBuilder的区别和用法
|
算法 机器人
|
算法 测试技术
蓝桥算法_单词分析-wordAnalysis
蓝桥算法_单词分析-wordAnalysis
123 1
|
存储 算法
【备战蓝桥,冲击省一】高精度算法实现加减乘除
【备战蓝桥,冲击省一】高精度算法实现加减乘除
198 0
|
算法
【迎战蓝桥】 算法·每日一题(详解+多解)-- day11
💖1. 按之字形顺序打印二叉树 💖2. 二叉搜索树的第k个节点 💖3. 二叉搜索树的第k大节点
|
13天前
|
存储 算法 调度
基于和声搜索优化算法的机器工作调度matlab仿真,输出甘特图
本程序基于和声搜索优化算法(Harmony Search, HS),实现机器工作调度的MATLAB仿真,输出甘特图展示调度结果。算法通过模拟音乐家即兴演奏寻找最佳和声的过程,优化任务在不同机器上的执行顺序,以最小化完成时间和最大化资源利用率为目标。程序适用于MATLAB 2022A版本,运行后无水印。核心参数包括和声记忆大小(HMS)等,适应度函数用于建模优化目标。附带完整代码与运行结果展示。

热门文章

最新文章