题目一览图
零、模拟/设计题概述
【模拟/设计题】都是根据题目设计的场景进行编码。
一、模拟题
题目概述
【模拟题】倾向于按照规矩办事，一般的方法是通过枚举几种情况，看看能不能找到规律，或者判断有几种情况。
题型一 | 找规律
题型串联
1 Z 字形变换
【概述】模拟题
【题目描述**】**
将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。比如输入字符串为 “PAYPALISHIRING” 行数为 3 时，排列如下：
P A H NA P L S I I GY I R
之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如：”PAHNAPLSIIGYIR”
【题目示例**】**
输入：s = "PAYPALISHIRING", numRows = 3
输出："PAHNAPLSIIGYIR"
【枚举**】**
1 7 13 19
2 6 8 12 14 1820
3 5 9 11 15 17 21
4 10 16 22
- 可以发现【Z字型】变换分为两个部分：
- 【Z】的横杠部分，每个横杠数字相差
2*(numRow-1)。 - 【Z】的拐弯部分，与前一个横杆的距离是
2*(numRow-所在行数)。
- 【Z】的横杠部分，每个横杠数字相差
- 字符串输出的时候，是按照行输出的。由于第一行和最后一行没有拐弯处，需要单独考虑。剩余行用两个指针
j和k分别定位【横杠】处和【拐弯】处，移动间隔都是2*(numRow-1)。var convert = function(s, numRows) { if( numRows <= 1 ) return s; const len = s.length; let res = ''; for( let i = 0 ; i < len ; i+=2*(numRows-1)) res += s[i]; for( let i = 1 ; i < numRows-1 ; i++ ){ for( let j = i , k = 2*(numRows-1) - i ; j < len || k < len ; j+=2*(numRows-1),k+=2*(numRows-1)){ if(j < s.length ) res += s[j]; if(k < s.length ) res += s[k]; } } for( let i = numRows-1 ; i < len ; i+=2*(numRows-1)) res += s[i]; return res; };2 格雷编码
【概述】模拟题
【题目描述**】
格雷编码是一个二进制数字系统，在该系统中，两个连续的数值仅有一个位数的差异。给定一个代表编码总位数的非负整数 n，打印其格雷编码序列。即使有多个不同答案，你也只需要返回其中一种。格雷编码序列必须以 0 开头。
【题目示例**】 ``` 输入: 2 输出: [0,1,3,2] 解释: 00 - 0 01 - 1 11 - 3 10 - 2
对于给定的 n，其格雷编码序列并不唯一。 例如，[0,2,3,1] 也是一个有效的格雷编码序列。
00 - 0 10 - 2 11 - 3 01 - 1
**【枚举****】**<br />本题考查格雷码相关知识，没有学过的话，难以找到规律（此时可以选择回溯算法）。但不影响我们枚举：
当n = 0 —— 0 当n = 1 —— 0 | 1 当n = 2 —— 00 01 | 11 10 当n = 3 —— 000 001 011 010 | 110 111 101 100
可以发现以下两点：
- `n` 每上升一位，相当于上一层所有数最高位加个 `0` ，但这不影响其在十进制的表示。
- 竖线左边的数和右边的数，只是最高位由 `0` 转 `1` 。
所以我们可以总结成以下步骤：
- 设置答案集合 `res` ，最高位权重 `w` 。
- 每到下一层 `n+1`
- 把上一层每个数最高位加 `0` （相当于不变）。
- 把这些数复制下，最高位改成 `1` ，即 `w + res[i]` 。
```javascript
var grayCode = function(n) {
const res = [0];
let w = 1;
while(n--){
for(let i = res.length - 1;i >= 0; i--) res.push(w + res[j]);
w *= 2;
}
return res;
};
题型二 | 分类讨论
题型串联
1 字符串转换整数 (atoi)
【概述】模拟题
【题目描述**】
请你来实现一个 atoi 函数，使其能将字符串转换成整数。
首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。接下来的转化规则如下：
如果第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字字符组合起来，形成一个有符号整数。
假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成一个整数。
该字符串在有效的整数部分之后也可能会存在多余的字符，那么这些字符可以被忽略，它们对函数不应该造成影响。
假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换，即无法进行有效转换。
在任何情况下，若函数不能进行有效的转换时，请返回 0 。
【题目示例**】
输入: " -42"
输出: -42
解释: 第一个非空白字符为 '-', 它是一个负号。
我们尽可能将负号与后面所有连续出现的数字组合起来，最后得到 -42 。
【分类讨论**】**
- 【删除空格】用指针快速定位第一个非空节点。
- 【正负号判定】判断第一个非空元素是否为 ‘-‘ ，并进行标记。
- 【十进制加和】根据读取到的各位，进行十进制加和。
【越位判定】判定数字是否在正负
2^31之间。var myAtoi = function(s) { const intMax = Math.pow(2, 31); let k = 0; while( k < s.length && s[k] === ' ') k++; if( k === s.length ) return 0; let sign = 1; if( s[k] === '-' ) sign = -1, k++; else if( s[k] === '+') k++; let res = 0; while( k < s.length && s[k] <= '9' && s[k] >= '0'){ res = res * 10 + (s[k] - '0'); k++; if(res > intMax ) break; } res *= sign; if (res < -intMax || res > intMax - 1) { return res < intMax ? -intMax : intMax - 1; } else { return res; } };2 有效数字
【概述】模拟题
【题目描述**】**
验证给定的字符串是否可以解释为十进制数字。
例如:"0" => true" 0.1 " => true"abc" => false"1 a" => false"2e10" => true" -90e3 " => true" 1e" => false"e3" => false" 6e-1" => true" 99e2.5 " => false"53.5e93" => true" --6 " => false"-+3" => false"95a54e53" => false
说明: 我们有意将问题陈述地比较模糊。在实现代码之前，你应当事先思考所有可能的情况。这里给出一份可能存在于有效十进制数字中的字符列表：
- 数字 0-9
- 指数 - “e”
- 正/负号 - “+”/“-“
- 小数点 - “.”
当然，在输入中，这些字符的上下文也很重要。
【分类讨论**】**
- 【删除左右空格】用指针快速定位第一个非空节点。
- 【正负号判定】判断第一个非空元素是否为 ‘-‘ ，并进行标记。
- 【小数缩写形式判定】直接以
.开头的数字，可能是小数的缩写形式，需要额外判定。 - 【小数和指数判定】用变量
dot和e标记是否出现小数或者指数的标记.或e。.不能出现【小数】和【指数】已经出现的时候。e不能出现【指数】已经出现的时候，并且后面必须跟着【数字】或者【正负号】。
【数字判定】判定完以上的，只要是数字就有效的。
var isNumber = function(s) { let l = 0 , r = s.length - 1; while(l<=r&&s[l]===' ') l++; while(l<=r&&s[r]===' ') r--; if( l > r ) return false; s = s.substr(l,r-l+1); if(s[0]==='+'||s[0]==='-') s = s.substr(1); if(s.length===0) return false; if(s[0]==='.' && (s.length===1||s[1]==='e'||s[1]==='E')) return false; let dot = 0 , e = 0; for(let i = 0 ; i < s.length ; i++){ if(s[i]==='.'){ if(dot>0||e>0) return false; dot++; }else if(s[i]==='e'||s[i]==='E'){ if (!i || i + 1 == s.length || e > 0) return false; if (s[i + 1] == '+' || s[i + 1] == '-') { if (i + 2 == s.length) return false; i ++ ; } e ++ ; } else if (s[i] < '0' || s[i] > '9') return false; } return true; };var isNumber = function(s) { let l = 0 , r = s.length - 1; while(l<=r&&s[l]===' ') l++; while(l<=r&&s[r]===' ') r--; if( l > r ) return false; s = s.substr(l,r-l+1); if(s[0]==='+'||s[0]==='-') s = s.substr(1); if(s.length===0) return false; if(s[0]==='.' && (s.length===1||s[1]==='e'||s[1]==='E')) return false; let dot = 0 , e = 0; for(let i = 0 ; i < s.length ; i++){ if(s[i]==='.'){ if(dot>0||e>0) return false; dot++; }else if(s[i]==='e'||s[i]==='E'){ if (!i || i + 1 == s.length || e > 0) return false; if (s[i + 1] == '+' || s[i + 1] == '-') { if (i + 2 == s.length) return false; i ++ ; } e ++ ; } else if (s[i] < '0' || s[i] > '9') return false; } return true; };3 文本左右对齐
【概述】模拟题
【题目描述**】
给定一个单词数组和一个长度 maxWidth，重新排版单词，使其成为每行恰好有 maxWidth 个字符，且左右两端对齐的文本。你应该使用“贪心算法”来放置给定的单词；也就是说，尽可能多地往每行中放置单词。必要时可用空格 ‘ ‘ 填充，使得每行恰好有 maxWidth 个字符。要求尽可能均匀分配单词间的空格数量。如果某一行单词间的空格不能均匀分配，则左侧放置的空格数要多于右侧的空格数。文本的最后一行应为左对齐，且单词之间不插入额外的空格。
【题目示例**】输入: words = ["This", "is", "an", "example", "of", "text", "justification."] maxWidth = 16 输出: [ "This is an", "example of text", "justification. " ]【分类讨论**】**
【正常情况】放
wordCount个单词，剩余空间rs放空格。为了均匀放空格，可以根据剩余空间树rs除以（单词数减一wordCount-1）得到，但是有余数的情况，如果余数大于0就多加一个空格。- 【最后一行】单词之间空格长度固定为
1。 - 【只有一个单词】右面用空格补齐。 ```javascript const space = ( num ) => new Array(num).fill(‘ ‘).join(‘’);
var fullJustify = function(words, maxWidth) { const res = [];
for( let i = 0 ; i < words.length ;){
let j = i + 1 , s = rs = words[i].length;
while( j < words.length && s + 1 + words[j].length <= maxWidth){
s+=1+words[j].length , rs += words[j].length;
j++;
}
rs = maxWidth - rs ;
let line = words[i];
if( j === words.length ) {
for( i += 1 ; i < j ; i++) line += ' ' + words[i];
while( line.length < maxWidth ) line += ' ';
}else if( j - i === 1) line += space(rs);
else{
let sAvg = rs / ( j - i - 1 ) | 0 , sEx = rs % (j-i-1);
i++;
for( let k = 0 ; i < j ; i++ , k++) line += space(sAvg+(k<sEx)) + words[i];
}
i = j , res.push(line);
}
return res;
};
<a name="wenN3"></a>
## 二、设计题
---
<a name="IMaNA"></a>
### 题目概述
【**设计题**】倾向于考察基本数据结构的掌握情况，经常将需要各数据结构配合。
<a name="7axtY"></a>
#### 题型串联
<a name="89M7P"></a>
#### 1 [LRU 缓存机制](https://leetcode-cn.com/problems/lru-cache/)
**【概述】设计题**<br />**【题目描述****】**<br />运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制 。<br />实现 LRUCache 类：
- LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
- int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
- void put(int key, int value) 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字-值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。
** 进阶：你是否可以在 O(1) 时间复杂度内完成这两种操作？**
**【题目示例****】**
输入 [“LRUCache”, “put”, “put”, “get”, “put”, “get”, “put”, “get”, “get”, “get”] [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]] 输出 [null, null, null, 1, null, -1, null, -1, 3, 4]
解释 LRUCache lRUCache = new LRUCache(2); lRUCache.put(1, 1); // 缓存是 {1=1} lRUCache.put(2, 2); // 缓存是 {1=1, 2=2} lRUCache.get(1); // 返回 1 lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3} lRUCache.get(2); // 返回 -1 (未找到) lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3} lRUCache.get(1); // 返回 -1 (未找到) lRUCache.get(3); // 返回 3 lRUCache.get(4); // 返回 4
**【数据结构选取****】**
- 题目要求 `get` 和 `put` 方法时间复杂度都是 `O(1)` ，对应了插入和查找。而且存在自动删除的【旧数据】的机制，也要求在`get` 方法时能快速删除元素。
- 查找时间复杂度为`O(1)` 对应的是哈希表。
- 插入和删除时间复杂度为`O(1)` 对应的是链表。
- 所以本题要设计【哈希链表】。
```javascript
function DoubleLinkListNode(key,val){
this.key = key;
this.val = val;
this.next = null;
this.pre = null;
}
class DoubleLinkList{
constructor(){
this.size = 0;
this.head = new DoubleLinkListNode(0,0);
this.tail = new DoubleLinkListNode(0,0);
this.head.next = this.tail;
this.tail.pre = this.head;
}
addLast(x){
x.next = this.tail;
x.pre = this.tail.pre;
this.tail.pre.next = x;
this.tail.pre = x;
this.size ++;
}
remove(x){
x.pre.next = x.next;
x.next.pre = x.pre;
this.size--;
}
removeFirst(){
if( this.head.next === this.tail ) return null;
const first = this.head.next;
this.remove(first);
return first;
}
size(){
return this.size;
}
}
var LRUCache = function(capacity) {
this.capacity = capacity;
this.map = new Map();
this.doubleLinkList = new DoubleLinkList();
};
LRUCache.prototype._addRecently = function(key,val) {
const node = new DoubleLinkListNode(key,val);
this.map.set(key,node);
this.doubleLinkList.addLast(node);
};
LRUCache.prototype._getRecently = function(key) {
const node = this.map.get(key);
this.doubleLinkList.remove(node);
this.doubleLinkList.addLast(node);
};
LRUCache.prototype._deleteNode = function(key) {
const node = this.map.get(key);
this.map.delete(key);
this.doubleLinkList.remove(node);
};
LRUCache.prototype._deleteLeastNode = function() {
const node = this.doubleLinkList.removeFirst();
this.map.delete(node.key)
};
/**
* @param {number} key
* @return {number}
*/
LRUCache.prototype.get = function(key) {
if(!this.map.has(key)) return -1;
this._getRecently(key);
return this.map.get(key).val;
};
/**
* @param {number} key
* @param {number} value
* @return {void}
*/
LRUCache.prototype.put = function(key, value) {
if(this.map.has(key)){
this._deleteNode(key);
this._addRecently(key,value);
return ;
}
if(this.doubleLinkList.size === this.capacity ) this._deleteLeastNode();
this._addRecently(key,value);
};
若有收获，就点个赞吧
0 人点赞
