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

0_刷题中的基础

时间:2024-05-15 20:21:55浏览次数:22  
标签: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(失......