leetcode–807: 保持城市天际线

在二维数组grid中,grid[i][j]代表位于某处的建筑物的高度。 我们被允许增加任何数量(不同建筑物的数量可能不同)的建筑物的高度。 高度 0 也被认为是建筑物。 最后,从新数组的所有四个方向(即顶部,底部,左侧和右侧)观看的“天际线”必须与原始数组的天际线相同。 城市的天际线是从远处观看时,由所有建筑物形成的矩形的外部轮廓。 请看下面的例子。 建筑物高度可以增加的最大总和是多少? 例子: 输入: grid = [[3,0,8,4],[2,4,5,7],[9,2,6,3],[0,3,1,0]] 输出: 35 解释: The grid is: [ [3, 0, 8, 4], [2, 4, 5, 7], [9, 2, 6, 3], [0, 3, 1, 0] ] 从数组竖直方向(即顶部,底部)看“天际线”是:[9, 4,…

Leetcode –771: 宝石与石头

给定字符串J 代表石头中宝石的类型,和字符串 S代表你拥有的石头。 S 中每个字符代表了一种你拥有的石头的类型,你想知道你拥有的石头中有多少是宝石。 J 中的字母不重复,J 和 S中的所有字符都是字母。字母区分大小写,因此”a”和”A”是不同类型的石头。 示例 1: 输入: J = “aA”, S = “aAAbbbb” 输出: 3 示例 2: 输入: J = “z”, S = “ZZ” 输出: 0 注意: S 和 J 最多含有50个字母。 J 中的字符不重复。 解题思路: –…

字符串处理

字符串相关概念: 回文 子串 子序列 前缀树 后缀树和后缀数组 匹配 字典序 字符串操作: 1.与数组相关的操作 增删改查 2.字符的替换 3.字符串的旋转 字符串题目的常见类型 1.规则判断 判断字符串是否符合整数规则 判断字符串是否符合浮点数规则 判断字符串是否符合会问字符串规则 2.数字运算 int 和long 类型表达整数范围有限所以经常用字符串实现大整数 与大整数相关的加减乘除操作,需要模拟笔算的过程 3.与数组操作相关的类型 数组相关的调整、排序等操作需要掌握 快速排序的划分过程需要掌握和改写 4.字符计数 hash表 固定长度的数组 滑动串口问题、寻找无重复字符子串问题、计算变位词问题 5.动态规划类型 最长公共子串 最长公共子串序列 最长回文子串 最长回文子序列 6.搜索类型 宽度优先搜索 深度优先搜索 7.高级算法与数据结构 manacher算法解决最长回文子串问题…

排序算法复习与总结

排序算法比较 冒泡排序 时间复杂度O(N^2) 工作原理: 1.比较相邻两个元素,如果前者比后者大就交换 2.对第0个到第n-1个数重复步骤1,使得最大的数到达数组的末尾 3.重复以上步骤,直到比较完 c++版: “`c++ class BubbleSort { public: int* bubbleSort(int* A, int n) { <pre><code> for(int i=0;i <= n;i++) for(int j = n-1;j > i;j–){ if(A[j-1]>A[j]) { swap(A[j],A[j-1]); } } return A; // write code…

字符串高频面试题目

确定字符互异 请实现一个算法,确定一个字符串的所有字符是否全都不同。这里我们要求不允许使用额外的存储结构。 给定一个string iniString,请返回一个bool值,True代表所有字符全都不同,False代表存在相同的字符。保证字符串中的字符为ASCII字符。字符串的长度小于等于3000。 测试样例: “aeiou” 返回:True BarackObama” 返回:False 解题思路 使用集合能自动去重,然后判断set()前和set()后长度是否一样,如果一样,则没有重复的字符。 # -*- coding:utf-8 -*- class Different: def checkDifferent(self, iniString): if len(iniString) == len(set(iniString)): return True else: return False 原串翻转 请实现一个算法,在不使用额外数据结构和储存空间的情况下,翻转一个给定的字符串(可以使用单个过程变量)。 给定一个string iniString,请返回一个string,为翻转后的字符串。保证字符串的长度小于等于5000。 测试样例: “This is nowcoder” 返回:”redocwon si sihT”…