初始数据结构与算法(例题篇)
以下都是本人在刷题时觉得比较有价值的例题和笔记和比较有意思的题解，如有不好见谅，还有比赛前仔细看比赛文档..........
动态规划
个人理解:记住求解的方式有两种：①自顶向下的备忘录法 ②自底向上。
(1)给定三个字符串 s1、s2、s3，请你帮忙验证 s3 是否是由 s1 和 s2 交错 组成的。
两个字符串 s 和 t 交错 的定义与过程如下，其中每个字符串都会被分割成若干 非空 子字符串：
s = s1 + s2 + ... + sn
t = t1 + t2 + ... + tm
|n - m| <= 1
交错 是 s1 + t1 + s2 + t2 + s3 + t3 + ... 或者 t1 + s1 + t2 + s2 + t3 + s3 + ...
注意：a + b 意味着字符串 a 和 b 连接。
输入: s1 = "aabcc",s2 = "dbbca", s3 = "aadbbcbcac"输出:true
class Solution {public boolean isInterleave(String s1, String s2, String s3) {int n = s1.length();int m = s2.length();int p = s3.length();if(n + m != p)return false;//f[i][j]表示用s1的前i个字符和用s2的前i个字符是否能符合s3的前(i + j - 1)个字符boolean[][] f = new boolean[n + 1][m + 1];f[0][0] = true;for(int i = 0;i <= n;i++) {for(int j = 0;j <= m;j++) {int q = i + j - 1;if(i > 0) {//f[i][j] = f[i][j] || (f[i - 1][j] && s3.charAt(q) == s1.charAt(i - 1));//原题是以上的形式，速度慢了一半//这里的f[i][j] = f[i][j]只是因为j要从0开始，告诉j我i能满足，已经不需要你了f[i][j] = (f[i - 1][j] && s3.charAt(q) == s1.charAt(i - 1));}if(j > 0) {f[i][j] = f[i][j] || (f[i][j - 1] && s2.charAt(j - 1) == s3.charAt(q));}}}return f[n][m];}}
可以用滚动数组优化
class Solution {public boolean isInterleave(String s1, String s2, String s3) {int n = s1.length(), m = s2.length(), t = s3.length();if (n + m != t) {return false;}boolean[] f = new boolean[m + 1];f[0] = true;for (int i = 0; i <= n; ++i) {for (int j = 0; j <= m; ++j) {int p = i + j - 1;if (i > 0) {f[j] = f[j] && s1.charAt(i - 1) == s3.charAt(p);}if (j > 0) {f[j] = f[j] || (f[j - 1] && s2.charAt(j - 1) == s3.charAt(p));}}}return f[m];}}
(2)
观察下面的数字金字塔。
写一个程序来查找从最高点到底部任意处结束的路径，使路径经过数字的和最大。每一步可以走到左下方的点也可以到达右下方的点。
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
在上面的样例中,从 7 \to 3 \to 8 \to 7 \to 57→3→8→7→5 的路径产生了最大
输入输出样例
输入 #1
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
输出 #1
30
一开始的思想是从上往下走 其实从后往前走会更快
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();// 数组的行列数int[][] num = new int[n][n];for (int i = 0; i < n; i++) {// 输入数组for (int j = 0; j < i + 1; j++) {num[i][j] = sc.nextInt();}}System.out.println(dpd(num));}public static int dpd(int[][] num) {int row = num.length;// 定义行数int line = num[row - 1].length;// 定义列数int[][] dp = new int[row][line];// 定义dp数组for (int i = 0; i < line; i++) {// 初始化最后一行dp[row - 1][i] = num[row - 1][i];}for (int i = row - 2; i >= 0; i--) {// 从最后一行向前走 所以i从倒数第二行开始for (int j = 0; j <= i; j++) {dp[i][j] = num[i][j] + Math.max(dp[i + 1][j], dp[i + 1][j + 1]);}}return dp[0][0];}}
(3)
某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。
输入导弹依次飞来的高度（雷达给出的高度数据是\le 50000≤50000的正整数），计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。
输入 #1
389 207 155 300 299 170 158 65
输出 #1
6
2
import java.util.Scanner;public class Main {//动态规划，创建特殊数组static int[] len, height, count;static int max1, max2;public static void dio(int k){for (int i = 0; i < k; i++) {len[i] = 1;count[i] = 1;//每一次都与前面的数遍历，只取最大值for (int j = 0; j < i; j++) {if(height[i] <= height[j]){len[i] = Math.max(len[i], len[j]+1);}else{count[i] = Math.max(count[i], count[j]+1);}}//389 207 155 300 299 170 158 65max1 = Math.max(max1, len[i]);max2 = Math.max(max2, count[i]);}}public static void main(String[] args) {Scanner sc = new Scanner(System.in);String arr = sc.nextLine();String[] a = arr.split(" ");int n = a.length;len = new int[n];count = new int[n];height = new int[n];for (int i = 0; i < n; i++) {height[i] = Integer.parseInt(a[i]);}dio(n);System.out.println(max1);System.out.println(max2);}}
(4)
在一个由’0’和1’组成的二维矩阵内，找到只包含’1’的最大正方形，并返回其面积
这题可以用dfs，但是时间复杂度有点高，这里就直接用dp吧
class Solution {public int maximalSquare(char[][] matrix) {int n = matrix.length,m = matrix[0].length;int max = 0;if(matrix == null || n == 0 || m == 0)return 0;//dp[i][j]记录的是以i，j为正方形的右下方坐标int[][] dp = new int[n][m];for(int i = 0;i < n;i++) {for(int j = 0;j < m;j++) {if(matrix[i][j] == '1') {if(i == 0 || j == 0) {dp[i][j] = 1;}else {//这里取最小值是因为比如i，j的左边有一个一，上面也有一个一，但是斜上是0，这样是不能构成正方形的，所以应该取最小值dp[i][j] = Math.min(Math.min(dp[i - 1][j],dp[i][j - 1]),dp[i - 1][j - 1]) + 1;}max = Math.max(max,dp[i][j]);}}}return max * max;}}
(5)
你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。
示例 1：
输入：nums = [2,3,2]
输出：3
解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。
示例 2：
输入：nums = [1,2,3,1]
输出：4
解释：你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
偷窃到的最高金额 = 1 + 3 = 4 。
示例 3：
输入：nums = [1,2,3]
输出：3
思路:
假设数组nums 的长度为n。如果不愉窃最后一间房屋，则偷窃房屋的下标范围是[0, n一2;如果不偷窃第一间房屋，则愉窃房屋的下标范围是[1,n-1]。在确定偷窃房屋的下标范围之后，即可用第198 题的方法解决。对于两段下标范围分别计算可以偷窃到的最高总金额，其中的最大值即为在n间房屋中可以偷窃到的最高总金额。
class Solution {//其实就是分成两种情况，每种情况的起始与结束的下标不同public int rob(int[] nums) {int len = nums.length;if(len == 1)return nums[0];else if(len == 2) {return Math.max(nums[0],nums[1]);}int[] dp1 = new int[len];int[] dp2 = new int[len];dp1[0] = nums[0];dp1[1] = Math.max(nums[0],nums[1]);for(int i = 2;i < len - 1;i++) {dp1[i] = Math.max(dp1[i - 2] + nums[i],dp1[i - 1]);}dp2[1] = nums[1];dp2[2] = Math.max(nums[2],nums[1]);for(int i = 3;i < len;i++) {dp2[i] = Math.max(dp2[i - 2] + nums[i],dp2[i - 1]);}return Math.max(dp1[len - 1-1],dp2[len - 1]);}}
2.搜索+图
搜索也分广度与深度，都会有一定的模板
(1)
你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。
在选修某些课程之前需要一些先修课程。先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。
例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。
请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。
示例 1：
输入：numCourses = 2, prerequisites = [[1,0]]
输出：true
解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。
示例 2：
输入：numCourses = 2, prerequisites = [[1,0],[0,1]]
输出：false
解释：总共有 2 门课程。学习课程 1 之前，你需要先完成课程 0 ；并且学习课程 0 之前，你还应先完成课程 1 。这是不可能的
深度优先搜索
class Solution {public boolean canFinish(int numCourses, int[][] prerequisites) {List<List<Integer>> aj = new ArrayList<>();for(int i = 0;i < numCourses;i++) {aj.add(new ArrayList<>());}int[] isVisit = new int[numCourses];for(int[] cp : prerequisites) {aj.get(cp[1]).add(cp[0]);}for(int i = 0;i < numCourses;i++) {if(!dfs(aj,isVisit,i))return false;}return true;}public boolean dfs(List<List<Integer>> aj,int[] isVisit,int i) {//如果后面的元素为一，说明已经被赋值过了，也就是已经被学过了，这是不符合题意的if(isVisit[i] == 1)return false;//表示后面的课程已经被前面判断过没有问题，剪枝if(isVisit[i] == -1)return true;isVisit[i] = 1;for(int j : aj.get(i)) {if(!dfs(aj,isVisit,j))return false;}isVisit[i] = -1;return true;}}
广度优先搜索
class Solution {public boolean canFinish(int numCourses, int[][] prerequisites) {List<List<Integer>> res = new ArrayList<>();int[] arr = new int[numCourses];for(int i = 0;i < numCourses;i++) {res.add(new ArrayList<Integer>());}for(int[] p : prerequisites) {res.get(p[1]).add(p[0]);//只要arr[p[0]]不等于0，则表示它前面还有arr[p[0]]的课程要学arr[p[0]]++;}Queue<Integer> q = new LinkedList<>();for(int i = 0;i < numCourses;i++) {//先将先学的课程推入if(arr[i] == 0)q.offer(i);}int isVist = 0;while(!q.isEmpty()) {isVist++;int u = q.poll();for(int e : res.get(u)) {arr[e]--;//如果它前面没有课程需要学了，就将该课程推入if(arr[e] == 0)q.offer(e);}}return isVist == numCourses;}}
(2)记忆化搜索
给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
你可以认为每种硬币的数量是无限的。
示例 1：
输入：coins = [1, 2, 5], amount = 11
输出：3
解释：11 = 5 + 5 + 1
示例 2：
输入：coins = [2], amount = 3
输出：-1
示例 3：
输入：coins = [1], amount = 0
输出：0
class Solution {public int coinChange(int[] coins, int amount) {if(amount < 1)return 0;return dfs(coins,amount,new int[amount]);}public int dfs(int[] coins,int res,int[] count) {if(res < 0)return -1;if(res == 0)return 0;//记忆化搜索关键if(count[res - 1] != 0)return count[res - 1];int min = Integer.MAX_VALUE;for(int val : coins) {int a = dfs(coins,res - val,count);if(a >= 0 && a < min) {//加一是为了前面的那一步加上的金币数min = a + 1;}}count[res - 1] = (min == Integer.MAX_VALUE ? -1 : min);//count[]是下标从0开始的，count[res - 1]表示的是res钱需要的最少金币数return count[res - 1];}}
(3)
树是一个无向图，其中任何两个顶点只通过一条路径连接。换句话说，一个任何没有简单环路的连通图都是一棵树。
给你一棵包含 n 个节点的树，标记为 0 到 n - 1 。给定数字 n 和一个有 n - 1 条无向边的 edges 列表（每一个边都是一对标签），其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间存在一条无向边。
可选择树中任何一个节点作为根。当选择节点 x 作为根节点时，设结果树的高度为 h 。在所有可能的树中，具有最小高度的树（即，min(h)）被称为 最小高度树 。
请你找到所有的 最小高度树 并按 任意顺序 返回它们的根节点标签列表。
树的 高度 是指根节点和叶子节点之间最长向下路径上边的数量。
输入:n= 4, edges = [[1,o].[1,2].[1,3]]输出:[1]
解释:如图所示，当根是标签为1的节点时，树的高度是1，这是唯一的最小高度树。
class Solution {public List<Integer> findMinHeightTrees(int n, int[][] edges) {List<Integer> res = new ArrayList<>();/*如果只有一个节点，那么他就是最小高度树*/if (n == 1) {res.add(0);return res;}/*建立各个节点的出度表*/int[] degree = new int[n];/*建立图关系，在每个节点的list中存储相连节点*/List<List<Integer>> map = new ArrayList<>();for (int i = 0; i < n; i++) {map.add(new ArrayList<>());}for (int[] edge : edges) {degree[edge[0]]++;degree[edge[1]]++;/*出度++*/map.get(edge[0]).add(edge[1]);/*添加相邻节点*/map.get(edge[1]).add(edge[0]);}/*建立队列*/Queue<Integer> queue = new LinkedList<>();/*把所有出度为1的节点，也就是叶子节点入队*/for (int i = 0; i < n; i++) {if (degree[i] == 1) queue.offer(i);}/*循环条件当然是经典的不空判断*/while (!queue.isEmpty()) {res = new ArrayList<>();/*这个地方注意，我们每层循环都要new一个新的结果集合，这样最后保存的就是最终的最小高度树了*/int size = queue.size();/*这是每一层的节点的数量*/for (int i = 0; i < size; i++) {int cur = queue.poll();res.add(cur);/*把当前节点加入结果集，不要有疑问，为什么当前只是叶子节点为什么要加入结果集呢?因为我们每次循环都会新建一个list，所以最后保存的就是最后一个状态下的叶子节点，这也是很多题解里面所说的剪掉叶子节点的部分，你可以想象一下图，每层遍历完，都会把该层（也就是叶子节点层）这一层从队列中移除掉，不就相当于把原来的图给剪掉一圈叶子节点，形成一个缩小的新的图吗*/List<Integer> neighbors = map.get(cur);/*这里就是经典的bfs了，把当前节点的相邻接点都拿出来，* 把它们的出度都减1，因为当前节点已经不存在了，所以，* 它的相邻节点们就有可能变成叶子节点*/for (int neighbor : neighbors) {degree[neighbor]--;if (degree[neighbor] == 1) {/*如果是叶子节点我们就入队*/queue.offer(neighbor);}}}}return res;/*返回最后一次保存的list*/}}
3.Floyd(模板模板)
有 n 个城市，按从 0 到 n-1 编号。给你一个边数组 edges，其中 edges[i] = [fromi, toi, weighti] 代表 fromi 和 toi 两个城市之间的双向加权边，距离阈值是一个整数 distanceThreshold。
返回能通过某些路径到达其他城市数目最少、且路径距离 最大 为 distanceThreshold 的城市。如果有多个这样的城市，则返回编号最大的城市。
注意，连接城市 i 和 j 的路径的距离等于沿该路径的所有边的权重之和。
示例 1：
输入：n = 4, edges = [[0,1,3],[1,2,1],[1,3,4],[2,3,1]], distanceThreshold = 4
输出：3
解释：城市分布图如上。
每个城市阈值距离 distanceThreshold = 4 内的邻居城市分别是：
城市 0 -> [城市 1, 城市 2]
城市 1 -> [城市 0, 城市 2, 城市 3]
城市 2 -> [城市 0, 城市 1, 城市 3]
城市 3 -> [城市 1, 城市 2]
城市 0 和 3 在阈值距离 4 以内都有 2 个邻居城市，但是我们必须返回城市 3，因为它的编号最大。
class Solution {public int findTheCity(int n, int[][] edges, int distanceThreshold) {int[][] arr = new int[n][n];for(int i = 0;i < n;i++) {for(int j = 0;j < n;j++) {if(i == j) {arr[i][j] = 0;}else {arr[i][j] = Integer.MAX_VALUE;}}}for(int[] p : edges) {arr[p[0]][p[1]] = arr[p[1]][p[0]] = p[2];}for (int k = 0; k < n; k++) {for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {if (i != k && j != k && i != j && arr[i][k] != Integer.MAX_VALUE && arr[k][j] != Integer.MAX_VALUE) {arr[i][j] = Math.min(arr[i][j], arr[i][k] + arr[k][j]);}}}}int min = n + 1;int res = -1;for(int i = 0;i < n;i++) {int count = 0;for(int j = 0;j < n;j++) {if(i != j && arr[i][j] <= distanceThreshold) {count++;}}if(min >= count) {min = count;res = i;}}return res;}}
4.贪心
(1)
给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证 返回结果的字典序最小（要求不能打乱其他字符的相对位置）。
示例 1：
输入：s = "bcabc"
输出："abc"
示例 2：
输入：s = "cbacdcbc"
输出："acdb"
1.贪心+单调栈方法
class Solution {public String removeDuplicateLetters(String s) {//判断这个字符是否已经遇到过boolean[] isV = new boolean[26];//每个字符出现的个数int[] num = new int[26];for(int i = 0;i < s.length();i++) {num[s.charAt(i) - 'a']++;}StringBuffer res = new StringBuffer();for(int i = 0;i < s.length();i++) {char a = s.charAt(i);//没遇到过的字符if(!isV[a - 'a']) {//如果res的长度大于0，并且他的最后一个字符要比现在的字符大while(res.length() > 0 && res.charAt(res.length() - 1) > a) {//如果最后一个字符还有，才能将他在前面的去掉if(num[res.charAt(res.length() - 1) - 'a'] > 0) {//设为未访问，要后面的该字符isV[res.charAt(res.length() - 1) - 'a'] = false;res.deleteCharAt(res.length()-1);}else//如果没有，那没办法了break;}//设为已经访问过了isV[a - 'a'] = true;//添加res.append(a);}num[a - 'a']--;}return res.toString();}}
2.Stack（）方法
class Solution {public String removeDuplicateLetters(String s) {Stack<Character> w = new Stack<>();for(int i = 0;i < s.length();i++) {Character c = s.charAt(i);//已经存在就不再添加if(w.contains(c))continue;//当w不为空，并且w最后一个元素比c要大，并且后面还能找到这个元素，则删除他while(!w.isEmpty() && w.peek() > c && s.indexOf(w.peek(),i) != -1) {w.pop();}//添加cw.push(c);}char[] arr = new char[w.size()];for(int i = 0;i < w.size();i++) {arr[i] = w.get(i);}return new String(arr);}}
(2)
在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。
你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。
给定两个整数数组 gas 和 cost ，如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则 保证 它是 唯一 的。
示例 1:
输入: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
输出: 3
解释:
从 3 号加油站(索引为 3 处)出发，可获得 4 升汽油。此时油箱有 = 0 + 4 = 4 升汽油
开往 4 号加油站，此时油箱有 4 - 1 + 5 = 8 升汽油
开往 0 号加油站，此时油箱有 8 - 2 + 1 = 7 升汽油
开往 1 号加油站，此时油箱有 7 - 3 + 2 = 6 升汽油
开往 2 号加油站，此时油箱有 6 - 4 + 3 = 5 升汽油
开往 3 号加油站，你需要消耗 5 升汽油，正好足够你返回到 3 号加油站。
因此，3 可为起始索引。
示例 2:
输入: gas = [2,3,4], cost = [3,4,3]
输出: -1
解释:
你不能从 0 号或 1 号加油站出发，因为没有足够的汽油可以让你行驶到下一个加油站。
我们从 2 号加油站出发，可以获得 4 升汽油。此时油箱有 = 0 + 4 = 4 升汽油
开往 0 号加油站，此时油箱有 4 - 3 + 2 = 3 升汽油
开往 1 号加油站，此时油箱有 3 - 3 + 3 = 3 升汽油
你无法返回 2 号加油站，因为返程需要消耗 4 升汽油，但是你的油箱只有 3 升汽油。
因此，无论怎样，你都不可能绕环路行驶一周。
class Solution {public int canCompleteCircuit(int[] gas, int[] cost) {int i = 0;int len = cost.length;while(i < len) {int cut = 0;int sumcost = 0,sumgas = 0;while(cut < len) {int j = (i + cut) % len;sumcost += cost[j];sumgas += gas[j];if(sumgas < sumcost)break;cut++;}if(cut == len)return i;else {i = i + cut + 1;}}return -1;}}
更多请前往我的个人博客:
https://blog.csdn.net/fffff9999?spm=1000.2115.3001.5343
本人能力有限 多多指教
结束!