首页 > 其他分享 >0_刷题中的基础

0_刷题中的基础

时间：2024-05-15 20:21:55浏览次数：21  
标签：return int res 基础 vector low root 刷题

目录

基础练习题

如下为基础练习题，基础练习题涉及基础知识，其他大部分的练习题都可以或多或少找到基础联系题目的影子。其具体分为如下两块：

  • 二叉树的深度优先遍历和广度优先遍历
    • 深度优先遍历的三种方式（递归、非递归写法）
    • 广度优先遍历 （递归、非递归写法）
  • 排序（几种基本的排序算法、链表排序）
  • 二分搜索

具体题目

二叉树

树的遍历递归、非递归写法。默写+练习

排序

双指针法

类型1：一个头指针，一个尾指针，不断缩小搜索空间

  1. 偶数排列在奇数之前
    1. https://leetcode.com/problems/sort-array-by-parity/
  2. 3sum 基础问题
    1. https://leetcode.com/problems/3sum/
  3. 3Sum Closest
    1. https://leetcode.com/problems/3sum-closest/
  4. 4 sum
    1. https://leetcode.com/problems/4sum/submissions/
  5. Container With Most Water
    1. https://leetcode.com/problems/container-with-most-water/
  6. Two Sum II - Input Array Is Sorted
    1. https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/

类型2：快慢指针法

链表

  1. 链表反转 （双向链表反转）基础中的基础 核心思想：两个指针反转，一个指针指向保存之前的记忆(共三个指针)
    1. https://leetcode.com/problems/reverse-linked-list/
  2. 链表合并
    1. 两个链表合并
      1. https://leetcode.com/problems/merge-two-sorted-lists/submissions/
    2. k个链表合并
      1. https://leetcode.com/problems/merge-k-sorted-lists/submissions/
        1. 堆做法
          1. 复杂度 n*log(k)
            1. 创建堆的复杂度是k，取数的复杂度是log(k), 假设有n个数，构建堆的复杂度是n，每一次取数的复杂度是log(k)
        2. 使用队列，不断的合并两个list，直到最后只剩一个list为止
          1. 时间复杂度
            1. 总共n个节点，一共合并了log(k)次，总的时间复杂度是O(nlog(k))
        3. 递归做法
        4. mergesrot
          1. 总共合并了logk次，一共n个节点进行了合并，复杂度还是O(nlog(k))
    3. 链表模拟加减法
      1. Add Two Numbers 考察细心
        1. https://leetcode.com/problems/add-two-numbers/
    4. 删除链表中第N个节点，如果N是第一个节点要注意
      1. https://leetcode.com/problems/remove-nth-node-from-end-of-list/submissions/
    5. 链表排序
      1. https://leetcode.com/problems/sort-list/
        1. 使用mergeSort
          1. 核心思想：找到中间节点，而后将一个链表分裂成两个链表，而后进行merge
    6. JZ86 在二叉树中找到两个节点的最近公共祖先
      1. 基本思路：
        1. 找到从根节点到目标阶段的一条路径，二叉树，所以只有一条路径
        2. 找到两条路径第一个相同的点

动态规划

  1. 最长递增子序列 一维动态规划

二分搜索

  1. 旋转数组的最小数字
    1. 牛客
  2. 二维数组中的查找
    1. 牛客
    2. 方法很多：
      1. 线性查找（一次减少一列）
      2. 一个二分查找
      3. 两个二分查找

排序

数组排序

数组排序分为如下几种：

  • 基于交换的排序
    • 冒泡排序
    • 快速排序
  • 基于插入的排序
    • 插入排序
  • 基于选择的排序
    • 选择排序
    • 堆排序(对选择排序的改进）
  • 二分排序、基数排序等

基于交换的排序

冒泡排序

基本知识：像冒泡一样，慢慢从最后面基于交换替换到第一个，以此类推

void bubbleSort(vector<int>&vec, int low, int high) {
    if (low >= high) return;
    int size = high - low + 1;
    for(int i=0; i < size; ++i) {
    	for(int j = size-1; j > i;--j) {
    		if (vec[j]<vec[j-1]) {
    			swap(vec[j], vec[j-1]);
			}
		}
	}
}
快速排序

基本思想：选定基准元素x，找到x的排序之后的位置，使得 左边的元素都比x小，右边的元素都比x大

基本的方法：双指针方法，左边指针为left，右边指针为right

  • left指向的都是比x小的
  • right指向的都比x大的

实现方式1：我自己实现的，也许是对的

int partition1(vector<int>&vec, int low, int high) {
	int target = vec[low];
	int i = low+1;
	int j = high;
	// i如果不是<=j 则出错了, ex:[2,2,1]  如果此时是i<j, 那么 swap之后，则数组不会改变，其输出还是 [2,2,1] 
	while(i<=j) {
		if(vec[i] > target && vec[j] <= target) {
			swap(vec[i], vec[j]);
			i = i + 1;
			j = j - 1;
		} else if (vec[i] <= target){
			i = i + 1;
		} else if (vec[j] > target) {
			j = j - 1;
		}
	}
	swap(vec[low], vec[i-1]);
	return i - 1;
}

int partition2(vector<int>&vec, int low, int high) {
    int target = vec[low];
	int i = low;
	int j = low + 1;
	while(j<=high) {
		if (vec[j]<=target){
			i = i + 1;
			if (i != j) {
				swap(vec[i], vec[j]);
			}
		}
		++j;
	}
	swap(vec[low], vec[i]);
	return i;
}

void quickSort(vector<int>&vec, int low, int high) {
	if (low >= high) {
		return;
	}
	int i = partition(vec, low, high);
	quickSort(vec, low, i-1);
	quickSort(vec, i+1, high);
}

注意其他写法：

int partitionAnother(vector<int>&vec, int low, int high) {
    int target = vec[low];
	int i = low-1;
	int j = low;
	while(j<=high) {
		if (vec[j]<=target){
			i = i + 1;
			if (i != j) {
				swap(vec[i], vec[j]);
			}
		}
		++j;
	}
	if (i>low) { // 如果i从low-1开始，则一定要加上这一步
		swap(vec[low], vec[i]);
	}
	
	return i; // 如果i从low-1开始，返回值i有等于low-1的可能性
}

基于插入的排序

插入排序

基本思想：整体思路自底向上，从一个元素开始，不断的加入元素，找到元素最适合的位置

void insertSort(vector<int>&vec, int low, int high) {
	if (low >= high) return;
	int i = low + 1;
	int size = high - low + 1;
	while (i<size) {
		int j = i - 1;
		int temp = vec[i];
		while (j>= 0 && temp <= vec[j]) {
			vec[j+1] = vec[j];
			j = j - 1;
		}
		vec[j+1] = temp;
		printVec(vec);
		i = i + 1;
	}
}

基于选择的排序

选择排序

基本思想：从剩余选择中选择出一个最小的元素，放在第一个位置，以此类推

void chooseSort(vector<int>&vec, int low, int high) {
	if (low >= high) return;
	int size = high - low + 1;
	for(int i = 0; i < size; ++i) {
		int temp = vec[i];
		int index = i;
		for (int j = i + 1; j < size; ++j) {
			if (vec[j]<= temp) {
				temp = vec[j];
				index = j;
			}
		}
		swap(vec[i], vec[index]);
	}
}

二路归并排序

方法：典型的分支方法。自底向上。不断的合并两个有序的数组

递归方法

// 2-merge sort
void merge(vector<int>& vec, int leftA, int rightA, int leftB, int rightB) {
	if (rightA < leftA || rightB < leftB) {
		return;
	}
	int i = leftA;
	int j = leftB;
	int k = 0;
	vector<int> temp(rightA - leftA + 1 + rightB - leftB + 1);
	
    while(i <= rightA && j <= rightB) {
    	if (vec[i] <= vec[j]) {
    		temp[k++] = vec[i++];
		} else {
			temp[k++] = vec[j++];
		}
	}
	
	while(i<=rightA) {
		temp[k++] = vec[i++];
	}
	while(j<=rightB) {
		temp[k++] = vec[j++];
	}
	k=0;
	for(i=leftA; i <= rightA; ++i) {
		vec[i] = temp[k++];
	}
	for(j=leftB; j <= rightB; ++j) {
		vec[j] = temp[k++];
	}
}
//递归方法
void mergeSort(vector<int>& vec, int low , int high) {
	if (low >= high) return;
	int middle = (high + low) / 2;
	mergeSort(vec, low, middle);
	mergeSort(vec, middle + 1, high);
	merge(vec, low, middle, middle + 1, high);
}
// 非递归方法
void mergeSortNotRecursive(vector<int>& vec, int low , int high) {
	if (low >= high) return;
	int step = 2;
	int size = high - low + 1;
	while(step <= size) {
		int  i = 0;
		while ((i+step) <= size) {
			merge(vec, i, i + step/2 - 1, i + step/2, i + step-1);
			i = i + step;
		}
		merge(vec,i, i+step/2-1, i+step/2, high);
		step = step * 2;
	}
	merge(vec, low, low+step/2-1, low + step/2, high);
}

链表排序

搜索

二分搜索

基本思想：不断的缩小左右空间，直到找到元素或者找不到元素

/*  1. binary search */
int binarySearchResursive(vector<int>&vec, int lower, int high, int target) {
	if (high < lower) return -1;
	int middle = lower + (high - lower) / 2;
	if (vec[middle] > target) {
		return binarySearchResursive(vec, lower, middle-1, target);
	} else if (vec[middle] < target) {
		return binarySearchResursive(vec, middle+1, high, target);
	} 
    return middle;
}

/* 2. */
int binarySearch(vector<int>&vec, int lower, int high, int target) {
	if (high < lower) return -1;
	int left = lower;
	int right = high;
	int res = -1;
	while (left <= right) {
		int middle = right + (left - right) / 2;
		if (vec[middle] > target) {
			right = middle - 1;
		} else if (vec[middle] < target) {
			left = middle + 1;
		} else {
			res = middle;
			break;
		}
	}
	return res;
}

二叉树的遍历

深度优先遍历

先序遍历

1. 先序非递归写法
vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        if (root==nullptr) {
            return res;
        }
        stack<TreeNode*> s;
        TreeNode *p = root; 
        while(p!=nullptr || !s.empty()) {
            while(p!=nullptr) {
                s.push(p);
                res.push_back(p->val);
                p=p->left;
            }
            p = s.top();
            s.pop();
            p = p->right;
        }
        return res;
    }
 2. 递归做法
     void preorder(TreeNode *root, vector<int>& res) {
        if (root==nullptr) return;
        res.push_back(root->val);
        preorder(root->left, res);
        preorder(root->right, res);
    }
    
    
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        if (root==nullptr) {
            return res;
        }
        preorder(root, res);
        return res;
    }

中序遍历

1. 非递归做法 
   vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        if (root==nullptr) return res;
        stack<TreeNode*> s;
        TreeNode *p = root;
        while(p != nullptr || !s.empty()) {
            while(p!=nullptr) {
                s.push(p);
                p = p->left;
            }
            p = s.top();
            s.pop();
            res.push_back(p->val);
            p=p->right;
        }
        return res;
    }
 2. 递归做法
     void inorder(TreeNode *root, vector<int>&res) {
        if (root==nullptr) return;
        inorder(root->left, res);
        res.push_back(root->val);
        inorder(root->right, res);
    }
    
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        if (root==nullptr) return res;
        inorder(root, res);
        return res;
    }

后序遍历

   1. 非递归写法
   vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        if (root==nullptr) return res;
        stack<TreeNode*> s;
        TreeNode *pre = nullptr;
        TreeNode *p = root;
        while(!s.empty() || p != nullptr) {
            while(p!=nullptr) {
                s.push(p);
                p = p->left;
            }
            p = s.top();
            if (p->right == nullptr || p->right == pre) {
                s.pop();
                res.push_back(p->val);
                pre = p;
                p = nullptr;  // 这里一定要置空
            } else {
                p = p->right;
            }
            
        }
        return res;
    }
  2. 递归写法
      void postorder(TreeNode *root, vector<int>&res) {
        if (root==nullptr) return;
        postorder(root->left, res);
        postorder(root->right, res);
        res.push_back(root->val);
    }
    
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        if (root==nullptr) return res;
        postorder(root, res);
        return res;
    }

广度优先遍历

层次遍历

1、层次输出:[[1],[2,3],[4,5,6,7]]

实现1：代码数较少

    vector<vector<int>> levelOrder(TreeNode* root) {
       vector<vector<int>> res;
       if (root==nullptr) return res;
       queue<TreeNode*> q1;
       queue<TreeNode*> q2;
       q1.push(root);
       while(!q1.empty() || !q2.empty()) {
           vector<int> temp;
           while(!q1.empty()) {
               TreeNode *p = q1.front();
               q1.pop();
               temp.push_back(p->val);
               if (p->left) q2.push(p->left);
               if (p->right) q2.push(p->right);
           }
           if (temp.size()) {
               res.push_back(temp);
           }
           q1.swap(q2);
       }
       return res;
    }

实现2：代码数较多

    vector<vector<int>> levelOrder(TreeNode* root) {
       vector<vector<int>> res;
       if (root==nullptr) return res;
       queue<TreeNode*> q1;
       queue<TreeNode*> q2;
       q1.push(root);
       vector<int> temp_res;
       while(!q1.empty() || !q2.empty()) {
           TreeNode *temp;
           while(!q1.empty()) {
               temp = q1.front();
               q1.pop();
               temp_res.push_back(temp->val);
               if (temp->left) q2.push(temp->left);
               if (temp->right) q2.push(temp->right);
               if (q1.empty()) {
                  res.push_back(temp_res);
                  vector<int>().swap(temp_res);    
               }
           } 
           while(!q2.empty()) {
               temp = q2.front();
               q2.pop();
               temp_res.push_back(temp->val);
               if (temp->left) q1.push(temp->left);
               if (temp->right) q1.push(temp->right);
               if (q2.empty()) {
                 res.push_back(temp_res);
                 vector<int>().swap(temp_res);
               }
           }
       }
       return res;
    }

也是层次遍历，但是不是按照层次输出

vector<int> bfs(TreeNode *head) {
    vector<int> res;
    if (head == nullptr) return res;
    TreeNode *p = head;
    queue<TreeNode*> Q;
    Q.push(p);
    while(Q.size()) {
        p = Q.front();
        Q.top();
        res.push_back(p->val);
        if (p->left) Q.push(p->left);
        if (p->right) Q.push(p->right);
    }
}

标签：return,int,res,基础,vector,low,root,刷题
From： https://www.cnblogs.com/douniwanli/p/18192466

相关文章

  • 云原生基础架构介绍
    什么是云原生基础架构？基础架构是指支持应用程序的所有软件和硬件，包括数据中心、操作系统、部署流水线、配置管理以及支持应用程序生命周期所需的任何系统或软件。高效运行的基础架构可以使得迭代更快，缩短投向市场的时间，从而加速业务发展。使用云原生基础架构是有效运行云原生应......
  • Python基础篇（流程控制）
    流程控制是程序运行的基础，流程控制决定了程序按照什么样的方式执行。条件语句条件语句一般用来判断给定的条件是否成立，根据结果来执行不同的代码，也就是说，有了条件语句，才可以根据不同的情况做不同的事，从而控制程序的流程。ifelseif条件成立，执行if内的命令；否则条件不成立，则......
  • serverless基础应用
    架构的演进物理机时代：单机版的单体架构-数据库，应用代码，HTTP服务器等服务都在一台服务器上虚拟机时代：将一台物体机通过虚拟化技术分割为多台虚拟机，对于硬件设备的管理统一由云厂商负责，开发者不需买硬件，直接在云平台买虚拟机，例如阿里云的ECS为了降低服务器负载，数据库迁移到云厂商......
  • Git基础操作
    #1.安装git请参考之前的步骤#2.配置gitgitconfig--globaluser.name"yourname"gitconfig--globaluser.email"[email protected]"#注册时用的邮箱#创建新仓库gitinit#初始化仓库gitclonehttps://github.com/user/repo#克隆远......
  • 软件设计师基础学习 十二
    十二、项目管理12.1范围管理范围管理确定在项目内包括什么工作和不包括什么工作，由此界定的项目范围在项目的全生命周期内可能因种种原因而变化，项目管理范围也要管理项目范围的这种变化。项目范围的变化也叫变更对项目范围的管理，是通过5个管理过程来实现的：规划范围管理(编制......
  • PLC的一些基础介绍
    1、W点和D点D点信号（DataPoints）：数据存储：D点通常指的是PLC中的“数据”存储区域，用于存储各种类型的数据，如整数、浮点数、字符串等。变量使用：在PLC程序中，D点可以作为变量使用，用于存储中间结果、计数器值、定时器值等。寻址方式：D点通常有连续的地址编号，如D0、D1、D2...，或者按照数......
  • Java的基础语法
    Java的基础语法1、注释、标识符、关键字Java中的注释有三种，注释并不会被执行，是给人看的。单行注释//注释文字只能够注释一行。多行注释/*多行注释文字*/能够注释一段文字。文档注释/***abcd*aaaa*/和JavaDoc结合使用标识符Java所有的组成部分都需要名字......
  • 面试题-JAVA基础
    JAVA有几种基本数据类型，各种类型占用字节大小？64位JVM中，int的长度是多数？Java的Integer缓存池大小是多少？Java中应该使用什么数据类型来描述价格？什么是装箱和拆箱？Java中的值传递和引用传递有什么区别？java8和java9的String类型的区别String，StringBuilder，StringBuffer区别......
  • 动态规划基础
    动态规划基础某一问题有很多重叠子问题，使用动态规划是最有效的。动态规划中每一个状态是从上一个状态推导出来的。与贪心不同，贪心没有状态推导，从局部中直接选取最优解。动态规划五部曲：确定dp数组以及下标的含义确定递推公式dp数组的初始化确定遍历顺序举例推导dp数组exa......
  • 统计力学中的概率论基础（二）
    技术背景接上一篇文章，我们继续记录统计力学中的一些基础的概率论知识。这一篇文章主要介绍的是一些常用的概率密度函数的对应参数计算，如期望值、方差等。伯努利分布在离散分布中，最简单的分布为伯努利（Bernoulli）分布，也叫0-1分布。伯努利分布的随机变量就跟抛硬币一样只有两种：0（失......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99