LeetCode 刷题基础 -- 模板原型Ⅰ

学习网站

晴问算法训练营

一、进制转换

十进制数 n 转 q 进制

    int n,a[1000],len=0;
    cin>>n;
    do{
   
        a[len++] = n % q;
        n /= q;
    }while(n>0);
    for(int i= len-1;i>=0;i--){
   
        cout<<a[i];
    }

p进制数 n 转 Q进制

int y = 0,product = 1;   //product 不断乘以p
while( n != 0){
   
    y += (n%10) * product;
    n /= 10;
    product *= p
}

二、二分查找

① 查找指定元素

//  查找指定元素
int findX(int a[],int l,int r,int x){
   
    int mid;
    while( l<= r){
      //注意<= 号
        mid = (l + r) / 2;
        if(a[mid]==x){
   
            return mid;
        }else if(a[mid] < x){
   
            l = mid + 1;
        }else{
   
            r = mid - 1;
        }
    }
    return -1;
}
int main(){
   
    cout<<findX(a,0,n-1,x); //n为数组长度
}

② 查找第一个大于等于 x 值的序列下标

// 查找第一个大于等于 x 值的序列下标
int findX(int a[],int l,int r,int x){
   
    int mid;
    while(l < r){
      // 注意< 号
        mid = (l+r)/2;
        if(a[mid] >= x){
     //
            r = mid;
        }else{
   
            l = mid + 1;
        }
    }
    return l;  // 注意return l
}

③ 查找第一个大于 x 值的序列下标

int findX(int a[],int l,int r,int x){
   
    int mid;
    while(l<=r){
   
        mid = (l+r)/2;
        if(a[mid]<=x){
   
            l = mid + 1;
        }else{
   
            r = mid - 1;
        }
    }
    return l;
}

④ 单峰序列

单峰序列是指,在这个序列中存在一个位置,满足这个位置的左侧(含该位置)是严格递增的、右侧(含该位置)是严格递减的,这个位置被称作峰顶位置。现在给定一个单峰序列,求峰顶位置的下标。

image-20240924133000287

int maxIn = 0;
int mx = 0;
void findX(int a[],int l,int r){
   
    if(l>r)
        return ;
    int mid = (l+r)/2;
    if(a[mid]>mx){
   
        mx = a[mid];
        maxIn = mid;
    }
    findX(a,mid+1,r);
    findX(a,l,mid-1);
}

三、双指针

① 两数之和

给定一个严格递增序列A和一个正整数k,在序列A中寻找不同的下标i、j,使得Ai+Aj=k。问有多少对(i,j)同时i<j满足条件。

image-20240924133243742

int i=0,j=n-1,cnt=0;
    while(i<j){
   
        if(a[i]+a[j]==k){
   
            cnt++;
            i++;
            j--;
        }else if(a[i]+a[j]<k){
   
            i++;
        }else{
   
            j--;
        }
    }

② 序列合并

给定两个升序的正整数序列A和B,将它们合并成一个新的升序序列并输出。

int merge() {
   
    int i = 0, j = 0, counter = 0;
    while (i < n && j < m) {
   
        if (a[i] < b[j]) {
   
            mergedNums[counter++] = a[i++];
        } else {
   
            mergedNums[counter++] = b[j++];
        }
    }
    while (i < n) {
   
        mergedNums[counter++] = a[i++];
    }
    while (j < m) {
   
        mergedNums[counter++] = b[j++];
    }
    return counter;
}

③ 集合求交

给定一个包含 n 个正整数的集合 S1,再给定一个包含 m 个正整数的集合 S2,求两个集合的交集。

image-20240924133626143

void getIntersection() {
   
    int i = 0, j = 0;
    while (i < n && j < m) {
   
        if (a[i] == b[j]) {
   
            intersection.push_back(a[i]);
            i++, j++;
        } else if (a[i] < b[j]) {
   
            i++;
        } else {
   
            j++;
        }
    }
}

④ 集合求并

给定一个包含 n 个正整数的集合S1,再给定一个包含 m 个正整数的集合S2,求两个集合的并集。

image-20240924133722056

void getUnionSet() {
   
    int i = 0, j = 0;
    while (i < n && j < m) {
   
        if (a[i] == b[j]) {
   
            unionSet.push_back(a[i]);
            i++, j++;
        } else if (a[i] < b[j]) {
   
            unionSet.push_back(a[i++]);
        } else {
   
            unionSet.push_back(b[j++]);
        }
    }
    while (i < n) {
   
        unionSet.push_back(a[i++]);
    }
    while (j < m) {
   
        unionSet.push_back(b[j++]);
    }
}

四、其他高效技巧与算法

① 区间和

给定由n个正整数组成的序列A,接下来给出k个查询,每个查询指定两个正整数l、r,计算序列从第l个整数至第r个整数之和,即Al+Al+1+…+Ar。

int main() {
   
    int n;
    cin >> n;
    vector<int> A(n + 1);
    vector<int> prefixSum(n + 1, 0);
    
    // 读取原数组并构建前缀和数组
    for (int i = 1; i <= n; ++i) {
   
        cin >> A[i];
        prefixSum[i] = prefixSum[i - 1] + A[i];
    }
    
    int k;
    cin >> k;
    for (int i = 0; i < k; ++i) {
   
        int l, r;
        cin >> l >> r;
        // 计算区间和并输出结果
        cout << prefixSum[r] - prefixSum[l - 1] 
1. 二分法 5 1.1. 什么是二分查找 5 1.2. 如何识别二分法 5 1.3. 二分法模板 6 1.3.1. 模板一 6 1.3.1.1. 模板代码 6 1.3.1.2. 关键属性 7 1.3.1.3. 语法说明 7 1.3.1.4. Lc69:x的平方根 8 1.3.1.5. Lc374:猜数大小 9 1.3.1.6. Lc33:搜索旋转数组 11 1.3.2. 模板二 13 1.3.2.1. 模板代码 13 1.3.2.2. 关键属性 14 1.3.2.3. 语法说明 14 1.3.2.4. Lc278:第一个错误版本 14 1.3.2.5. Lc162:寻找峰值 16 1.3.2.6. Lc153:寻找旋转排序数组最小值 19 1.3.2.7. Lc154:寻找旋转排序数组最小值II 20 1.3.3. 模板三 22 1.3.3.1. 模板代码 22 1.3.3.2. 关键属性 23 1.3.3.3. 语法说明 23 1.3.3.4. LC-34:在排序数组中查找元素的第一个和最后一个 23 1.3.3.5. LC-658:找到K个最接近的元素 25 1.3.4. 小结 28 1.4. LeetCode中二分查找目 29 2. 双指针 30 2.1. 快慢指针 31 2.1.1. 什么是快慢指针 31 2.1.2. 快慢指针模板 31 2.1.3. 快慢指针相关目 32 2.1.3.1. LC-141:链表是否有环 32 2.1.3.2. LC-142:环形链表入口 34 2.1.3.3. LC-876:链表的中间节点 37 2.1.3.4. LC-287:寻找重复数 40 2.2. 滑动窗口 43 2.2.1. 什么是滑动窗口 43 2.1.4. 常见型 44 2.1.5. 注意事项 45 2.1.6. 滑动窗口模板 45 2.1.7. 滑动窗口相关目 46 2.1.7.1. LC-3:无重复字符的最长子串 47 2.1.7.2. LC-76:最小覆盖子串 49 2.1.7.3. LC-209:长度最小的子数组 54 2.1.7.4. LC-239:滑动窗口最大值 57 2.1.7.5. LC-395:至少有K个重复字符的最长子串 60 2.1.7.6. LC-567:字符串排列 62 2.1.7.7. LC-904:水果成篮 64 2.1.7.8. LC-424:替换后的最长重复字符 66 2.1.7.9. LC-713:乘积小于K的子数组 67 2.1.7.10. LC-992:K个不同整数的子数组 70 2.3. 左右指针 73 2.3.1. 模板 73 2.3.2. 相关目 73 2.3.2.1. LC-76:删除倒数第N个节点 74 2.3.2.2. LC-61:旋转链表 76 2.3.2.3. LC-80:删除有序数组中的重复项 79 2.3.2.4. LC-86:分割链表 80 2.3.2.5. LC-438:找到字符串中所有字母的异位词 82 3. 模板 85 2.3.2.6. LC-76:删除倒数第N个节点 85
### LeetCode 基础语法入门教程 LeetCode 是程序员提升算法能力的重要平台之一,掌握其基础语法对于高效解至关重要。以下是关于 C++ 和 Java 的基础语法要点以及如何应用这些知识来解决 LeetCode 上的。 #### 1. 数据类型与变量 C++ 提供了多种基本数据类型,包括但不限于 `int`、`long` 和 `double` 等[^2]。在编写程序时,应根据具体需求选择合适的数据类型以优化内存使用和计算效率。例如,在处理大规模数值运算时,推荐优先考虑浮点数或长整型以避免溢出。 #### 2. 控制流语句 控制流是编程的核心部分,它决定了代码执行路径的选择逻辑。常用的条件分支结构如 `if...else` 或者更复杂的多路判断工具——`switch case` 可帮助开发者根据不同输入情况采取相应操作。此外还有循环机制(for/while),它们允许重复执行某段特定指令直到满足终止条件为止。 #### 3. 容器类简介及其应用场景分析 为了更好地管理和存储大量动态变化的信息单元组群对象集合体概念模型抽象表示形式即我们常说的各种标准模板库(STL)组件实例化后的实体形态表现出来的东西叫做容器(Container),其中最常用的一些包括: - **Vector**: 动态数组,支持随机访并能在尾部快速增删元素。 - **Set & Unordered_Set**: 分别代表有序集合并具备查找功能的哈希表版本;前者按升序排列后者则不关心顺序只关注唯一性检验速度更快些时候会用到find()方法来进行成员存在性的检测工作流程简化很多哦~ - **Map & Multimap**: 键值映射关系管理利器,能够轻松实现一对一或多对一关联查询任务目标达成效果显著提高工作效率的同时也减少了错误发生的可能性几率大大降低啦!另外还有一种叫Unorderd_Map变种形式同样适用于某些特殊场合条件下呢😊 #### 4. 特殊用途的数据结构介绍 - Deque (双端队列) Deque是一种可以在两端都进行插入删除操作非常灵活方便的一种线性序列结构形式表达方式呈现出来的样子感觉特别棒👍🏻通过下面这个例子我们可以看到它是怎么被创建出来的:`Deque<Integer> deque = new LinkedList<>();` 这样我们就得到了一个基于链接列表实现原理构建而成的新对象实例可供后续进一步开发拓展之用了呀😄[^3] #### 5. 关于栈(Stacks)的知识补充说明 最后值得一提的是有关Stack方面的内容知识点分享给大家知道一下吧~原来啊,在Standard Template Library里面啊,我们的老朋友Stack其实背后隐藏着秘密武器呢🧐那就是它可以由三种不同的底层支撑技术方案任选其中之一作为实际运行环境下的物理载体介质哟😎分别是向量(Vector),双向队列(Deque)或者是简单的单链表(List)...怎么样是不是很神奇呢😉[^4] ```java // 示例:Java 中 Stack 的简单使用 import java.util.Stack; public class Main { public static void main(String[] args) { Stack<Integer> stack = new Stack<>(); // 添加元素 stack.push(10); stack.push(20); System.out.println("Top element is: " + stack.peek()); // 输出顶部元素 // 删除顶部元素 stack.pop(); System.out.println("After popping, top element is: " + stack.peek()); } } ``` ---
评论
添加红包

请填写红包祝福语或标题

红包个数最小为10个

红包金额最低5元

当前余额3.43前往充值 >
需支付:10.00
成就一亿技术人!
领取后你会自动成为博主和红包主的粉丝 规则
hope_wisdom
发出的红包
实付
使用余额支付
点击重新获取
扫码支付
钱包余额 0

抵扣说明:

1.余额是钱包充值的虚拟货币,按照1:1的比例进行支付金额的抵扣。
2.余额无法直接购买下载,可以购买VIP、付费专栏及课程。

余额充值