大廠算法面試之leetcode精講24.其他類型題
視頻講解（高效學習）:點擊學習
目錄：
65. 有效數(shù)字 （hard）
圖是網(wǎng)絡結構的抽象模型刁岸，是一組由邊連接的節(jié)點
圖可以辨識任何二元關系 比如路脏里、航班
圖的表示方法
- 鄰接矩陣
- 鄰接表
ds_190
ds_189
- 思路:有限狀態(tài)機，遍歷字符串虹曙，不斷轉(zhuǎn)換狀態(tài)迫横，看最后的狀態(tài)是是否是有效狀態(tài)
- 復雜度：時間復雜度
O(n)番舆，n是字符串的長度，遍歷n次矾踱，每次狀態(tài)轉(zhuǎn)移是O(1)〗榉担空間復雜度O(1)
js：
//1.2 2e10
//--6 2e
var isNumber = function(s) {
const graph = {//點和邊構成的臨接表
0:{ 'blank': 0, 'sign': 1, '.': 2, 'digit': 6 },
1:{ 'digit': 6, '.': 2 },
2:{ 'digit': 3 },
3:{ 'digit': 3, 'e': 4 },
4:{ 'digit': 5, 'sign': 7 },
5:{ 'digit': 5 },
6:{ 'digit': 6, '.': 3, 'e': 4 },
7:{ 'digit': 5 },
}
let state = 0;//初始狀態(tài)
for (let c of s.trim()) {//循環(huán)字符串
if (c >= '0' && c <= '9') {
c = 'digit';
} else if (c === ' ') {
c = 'blank';
} else if(c === '+' || c === '-') {
c = 'sign'
}
state = graph[state][c];//返回下一個狀態(tài)
if (state === undefined) {//狀態(tài)轉(zhuǎn)移之后不在臨接表中 返回false
return false;
}
}
if (state == 3 || state == 5 || state == 6) {//狀態(tài)是3圣蝎、5刃宵、6中的一個說明是有效數(shù)字
return true;
}
return false;
};
836. 矩形重疊 （easy）
ds_183
- 復雜度：時間復雜度
O(1)徘公，空間復雜度O(1)
js：
var isRectangleOverlap = function(rec1, rec2) {
const [x1, y1, x2, y2] = rec1;
const [x3, y3, x4, y4] = rec2;
return !(x1 >= x4 || x3 >= x2 || y3 >= y2 || y1 >= y4);
};
java：
class Solution {
public boolean isRectangleOverlap(int[] rec1, int[] rec2) {
return !(rec1[2] <= rec2[0] || rec2[2] <= rec1[0] || rec1[3] <= rec2[1] || rec2[3] <= rec1[1]);
}
}
417. 太平洋大西洋水流問題（ medium）
- 思路：準備兩個表示是否能流向某個海岸線的矩陣，沿著海岸線‘’逆流而上‘’关面，最后統(tǒng)計兩個大洋都能流向的坐標
- 復雜度：時間復雜度
O(m*n),m坦袍、n分別是坐標矩陣的長寬捂齐∷趼眨空間復雜度O(m * n)
太平洋 ~ ~ ~ ~ ~
~ 1 2 2 3 (5) *
~ 3 2 3 (4) (4) *
~ 2 4 (5) 3 1 *
~ (6) (7) 1 4 5 *
~ (5) 1 1 2 4 *
* * * * * 大西洋
js：
var pacificAtlantic = function(matrix) {
if(!matrix || !matrix[0]) { return []; }
const m = matrix.length;
const n = matrix[0].length;
//從太平洋或大西洋逆流而上是否能到達某個坐標的數(shù)組 ture表示能流向某一個大洋
const flow1 = Array.from({ length: m }, () => new Array(n).fill(false));
const flow2 = Array.from({ length: m }, () => new Array(n).fill(false));
const dfs = (r, c, flow) => {
flow[r][c] = true;
[[r-1, c], [r+1, c], [r, c-1], [r, c+1]].forEach(([nr, nc]) => {
if(
//防止越界
nr >= 0 && nr < m &&
nc >= 0 && nc < n &&
//只有未標記的坐標才能繼續(xù)遞歸 防止死循環(huán)
!flow[nr][nc] &&
//確保是逆流而上
matrix[nr][nc] >= matrix[r][c]
) {
dfs(nr, nc, flow)
}
})
}
//逆流而上
for(let r = 0; r<m; r+=1) {
dfs(r, 0, flow1);
dfs(r, n-1, flow2)
}
for(let c = 0; c <n; c += 1) {
dfs(0, c, flow1);
dfs(m-1, c, flow2)
}
//統(tǒng)計兩個大洋都能流向的坐標
const res = []
for(let r = 0; r < m; r += 1) {
for(let c = 0; c < n; c += 1) {
if(flow1[r][c] && flow2[r][c]) {
res.push([r, c])
}
}
}
return res;
};
java：
public class pacificAtlantic {
private static int[][] dires = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
private int m, n;
private int[][] matrix;
public List<List<Integer>> pacificAtlantic(int[][] matrix) {
List<List<Integer>> res = new ArrayList<>();
m = matrix.length;
if (m == 0)
return res;
n = matrix[0].length;
if (n == 0)
return res;
this.matrix = matrix;
boolean[][] canReachP = new boolean[m][n];
boolean[][] canReachA = new boolean[m][n];
for (int i = 0; i < n; i++) {
dfs(0, i, canReachP);
dfs(m - 1, i, canReachA);
}
for (int i = 0; i < m; i++) {
dfs(i, 0, canReachP);
dfs(i, n - 1, canReachA);
}
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
if(canReachA[i][j] && canReachP[i][j]){
List<Integer> temp = new ArrayList<>();
temp.add(i);
temp.add(j);
res.add(temp);
}
}
}
return res;
}
private void dfs(int x, int y, boolean[][] canReach) {
canReach[x][y] = true;
for (int i = 0; i < 4; i++) {
int newX = x + dires[i][0];
int newY = y + dires[i][1];
if (isIn(newX, newY) && matrix[x][y] <= matrix[newX][newY] && !canReach[newX][newY]) {
dfs(newX, newY, canReach);
}
}
}
private boolean isIn(int x, int y) {
return x >= 0 && x < m && y >= 0 && y < n;
}
}
133. 克隆圖 （medium）
方法1:dfs
- 思路：深度優(yōu)先遍歷，遞歸新建每個節(jié)點和相鄰節(jié)點的關系
- 復雜度：時間復雜度
O(n)滴肿，n表示節(jié)點的數(shù)量佃迄『乔危空間復雜度O(n)柴信，遞歸的深度
js：
var cloneGraph = function(node) {
if(!node) return;
const visited = new Map();//存放遍歷過的節(jié)點
const dfs = (n) => {
const nCopy = new Node(n.val);//拷貝節(jié)點
visited.set(n, nCopy);//節(jié)點值和新建節(jié)點以鍵值對存入visited
(n.neighbors || []).forEach(ne => {
if(!visited.has(ne)) {
dfs(ne);//遞歸遍歷相鄰節(jié)點
}
nCopy.neighbors.push(visited.get(ne));//復制相鄰節(jié)點
})
}
dfs(node);//深度優(yōu)先遍歷
return visited.get(node);//返回visited中的新創(chuàng)建的節(jié)點
};
java:
class Solution {
private HashMap <Node, Node> visited = new HashMap <> ();
public Node cloneGraph(Node node) {
if (node == null) {
return node;
}
if (visited.containsKey(node)) {
return visited.get(node);
}
Node cloneNode = new Node(node.val, new ArrayList());
visited.put(node, cloneNode);
for (Node neighbor: node.neighbors) {
cloneNode.neighbors.add(cloneGraph(neighbor));
}
return cloneNode;
}
}
方法1:bfs
- 思路：廣度優(yōu)先遍歷每個節(jié)點随常，復制節(jié)點和節(jié)點間的關系
- 復雜度：時間復雜度
O(n)，n表示節(jié)點的數(shù)量唆鸡≌迹空間復雜度O(n)臂痕，隊列的空間
js：
var cloneGraph = function(node) {
if(!node) return;
const visited = new Map();
visited.set(node, new Node(node.val));//節(jié)點值和新建節(jié)點以鍵值對存入visited
const q = [node];
while(q.length) {
const n = q.shift()//出隊
(n.neighbors || []).forEach(ne => {//循環(huán)相鄰節(jié)點
if(!visited.has(ne)) {//沒有訪問過就加入隊列
q.push(ne);
visited.set(ne, new Node(ne.val));
}
visited.get(n).neighbors.push(visited.get(ne));//復制相鄰節(jié)點
})
}
return visited.get(node);
};
java:
class Solution {
public Node cloneGraph(Node node) {
if (node == null) {
return node;
}
HashMap<Node, Node> visited = new HashMap();
LinkedList<Node> queue = new LinkedList<Node> ();
queue.add(node);
visited.put(node, new Node(node.val, new ArrayList()));
while (!queue.isEmpty()) {
Node n = queue.remove();
for (Node neighbor: n.neighbors) {
if (!visited.containsKey(neighbor)) {
visited.put(neighbor, new Node(neighbor.val, new ArrayList()));
queue.add(neighbor);
}
visited.get(n).neighbors.add(visited.get(neighbor));
}
}
return visited.get(node);
}
}
605. 種花問題 （easy）
- 思路：遍歷握童，能種花的情況是該位置為0澡绩，前后位置不為1
- 復雜度：時間復雜度
O(n)俺附，空間復雜度O(1)
js：
var canPlaceFlowers = function (flowerbed, n) {
let count = 0
for (let i = 0, length = flowerbed.length; i < length; i++) {
//當前位置是0事镣，并且前后都不是1蛮浑，考慮在最前和最后的特殊情況
if (flowerbed[i] === 0 && flowerbed[i - 1] !== 1 && flowerbed[i + 1] !== 1) {
count++
i++
}
}
return count >= n
};
java：
class Solution {
public boolean canPlaceFlowers(int[] flowerbed, int n) {
int m = flowerbed.length;
int count = 0;
for (int i=0;i<m;i++) {
if (flowerbed[i] == 0 && (i == m - 1 || flowerbed[i + 1] == 0) && (i == 0 || flowerbed[i - 1] == 0)) {
flowerbed[i] = 1;
count++;
}
}
return count >= n;
}
}
89. 格雷編碼 （medium）
ds_197
- 思路：變量pre初始為1沮稚，不斷左移蕴掏，ans存放結果盛杰，每次循環(huán)之前數(shù)即供，在前面加上pre
- 復雜度：時間復雜度
O(n^2)∏嘧裕空間復雜度O(1)
js：
var grayCode = function(n) {
let ans = [0];
let pre = 1;
for(let i = 0;i<n;i++){
for(let j = ans.length - 1;j>=0;j--){
ans.push(pre + ans[j]);
}
pre <<= 1;
}
return ans;
};
java：
class Solution {
public List<Integer> grayCode(int n) {
List<Integer> res = new ArrayList<Integer>() {{ add(0); }};
int head = 1;
for (int i = 0; i < n; i++) {
for (int j = res.size() - 1; j >= 0; j--)
res.add(head + res.get(j));
head <<= 1;
}
return res;
}
}
914. 卡牌分組（ easy）
- 思路：統(tǒng)計各個數(shù)字的頻次延窜，求最大公約數(shù)是否大于1
- 復雜度：時間復雜度
O(n)逆瑞，空間復雜度O(n)
js：
var hasGroupsSizeX = function(deck) {
let map = new Map()
for(let n of deck){//統(tǒng)計頻次
map.set(n,map.has(n)?map.get(n)+1:1)
}
let arr = [...map.values()]
let res = arr[0]
return arr.every(i => (res = gcd(res, i)) > 1)//求最大公約數(shù)是否大于1
};
//輾轉(zhuǎn)相除法 4,2
let gcd = (a, b) => (b === 0 ? a : gcd(b, a % b))
java：
class Solution {
public boolean hasGroupsSizeX(int[] deck) {
if(deck.length == 0 || deck.length == 1) return false;
int[] count = new int[10000];
for (int num: deck) count[num]++;
return Arrays.stream(count).reduce(this::gcd).getAsInt() > 1;
}
private int gcd(int a, int b) {
return b == 0? a: gcd(b, a % b);
}
}
41. 缺失的第一個正數(shù) （hard）
ds_198
- 思路:循環(huán)nums哈肖，當前元素在
(0,nums.lenght]之間谋减，并且nums[nums[i]-1] != nums[i]出爹，則交換位置严就，然后循環(huán)交換位置之后的數(shù)組，判斷第一個缺失的正數(shù) - 復雜度：時間復雜度
O(n)渐行，空間復雜度O(1)
js：
var firstMissingPositive = function(nums) {
for(let i = 0; i < nums.length; i++){
//循環(huán)nums祟印，當前元素在(0,nums.lenght]之間蕴忆，并且nums[nums[i]-1] != nums[i]悲幅，則交換位置
while(nums[i] > 0 && nums[i] <= nums.length && nums[nums[i]-1] != nums[i] ){
const temp = nums[nums[i]-1];
nums[nums[i]-1] = nums[i];
nums[i] = temp;
}
}
for(let i = 0; i < nums.length; i++){//循環(huán)交換位置之后的數(shù)組汰具，判斷第一個缺失的正數(shù)
if(nums[i] != i+1){
return i+1;
}
}
// [1,2,3]
return nums.length + 1;
};
java：
class Solution {
public int firstMissingPositive(int[] nums) {
int n = nums.length;
for (int i = 0; i < n; ++i) {
while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
int temp = nums[nums[i] - 1];
nums[nums[i] - 1] = nums[i];
nums[i] = temp;
}
}
for (int i = 0; i < n; ++i) {
if (nums[i] != i + 1) {
return i + 1;
}
}
return n + 1;
}
}
48. 旋轉(zhuǎn)圖像 （medium）
ds_201
- 思路：先沿水平中軸線翻轉(zhuǎn)吟孙，然后在沿主對角線翻轉(zhuǎn).
- 復雜度：時間復雜度
O(n^2)杰妓，空間復雜度O(1)
js：
var rotate = function(matrix) {
const n = matrix.length;
//水平中軸線翻轉(zhuǎn)
for (let i = 0; i < Math.floor(n / 2); i++) {
for (let j = 0; j < n; j++) {
[matrix[i][j], matrix[n - i - 1][j]] = [matrix[n - i - 1][j], matrix[i][j]];
}
}
//主對角線翻轉(zhuǎn)
for (let i = 0; i < n; i++) {
for (let j = 0; j < i; j++) {
[matrix[i][j], matrix[j][i]] = [matrix[j][i], matrix[i][j]];
}
}
};
java：
class Solution {
public void rotate(int[][] matrix) {
int n = matrix.length;
//水平中軸線翻轉(zhuǎn)
for (int i = 0; i < n / 2; ++i) {
for (int j = 0; j < n; ++j) {
int temp = matrix[i][j];
matrix[i][j] = matrix[n - i - 1][j];
matrix[n - i - 1][j] = temp;
}
}
//主對角線翻轉(zhuǎn)
for (int i = 0; i < n; ++i) {
for (int j = 0; j < i; ++j) {
int temp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = temp;
}
}
}
}
54. 螺旋矩陣 （medium）
ds_169
- 思路：模擬旋轉(zhuǎn)的順序
- 復雜度：時間復雜度
O(mn)稚失，空間復雜度O(1)
js：
var spiralOrder = function (matrix) {
if (matrix.length == 0) return []
const res = []
let top = 0, bottom = matrix.length - 1, left = 0, right = matrix[0].length - 1
while (top <= bottom && left <= right) {//循環(huán)條件
for (let i = left; i <= right; i++) res.push(matrix[top][i])//循環(huán)完上面一行 top++
top++
for (let i = top; i <= bottom; i++) res.push(matrix[i][right])//循環(huán)右邊一行 right--
right--
if (top > bottom || left > right) break
for (let i = right; i >= left; i--) res.push(matrix[bottom][i])
bottom--
for (let i = bottom; i >= top; i--) res.push(matrix[i][left])
left++
}
return res
};
java
class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> ans = new ArrayList<>();
int top = 0, bottom = matrix.length - 1;
int left = 0, right = matrix[0].length - 1;
while(true){
for(int i = left ; i <= right ; ++i) ans.add(matrix[top][i]);
if(++top > bottom) break;
for(int i = top ; i <= bottom ; ++i) ans.add(matrix[i][right]);
if(--right < left) break;
for(int i = right ; i >= left ; --i) ans.add(matrix[bottom][i]);
if(--bottom < top) break;
for(int i = bottom ; i >= top ; --i) ans.add(matrix[i][left]);
if(++left > right) break;
}
return ans;
}
}
56. 合并區(qū)間 (medium)
- 思路：區(qū)間按照起始位置排序，當
curr[1] >= interval[0]說明重疊凿宾，更新當前curr的右邊界初厚，如果不重孙技，則加入result并更新區(qū)間 - 復雜度：時間復雜度
O(nlogn)牵啦，排序復雜度哈雏。空間復雜度O(logn)土浸，排序額外的空間
js：
// curr: [1,3]
// interval: [2,6]
// curr: ---
// interval: -----
var merge = function (intervals) {
if (intervals.length < 2) {
return intervals;
}
intervals.sort((a, b) => a[0] - b[0]);//按照起始位置排序
let curr = intervals[0];//當前區(qū)間curr初始化為intervals[0]
let result = [];
for (let interval of intervals) {//遍歷intervals
if (curr[1] >= interval[0]) {//當curr[1] >= interval[0]說明重疊
curr[1] = Math.max(curr[1], interval[1]);//更新當前curr的右邊界
} else {
result.push(curr);//不重疊 加入result
curr = interval;//更新區(qū)間
}
}
result.push(curr);
return result;
};
java：
class Solution {
public int[][] merge(int[][] intervals) {
List<int[]> res = new LinkedList<>();
Arrays.sort(intervals, (o1, o2) -> Integer.compare(o1[0], o2[0]));
int start = intervals[0][0];
for (int i = 1; i < intervals.length; i++) {
if (intervals[i][0] > intervals[i - 1][1]) {
res.add(new int[]{start, intervals[i - 1][1]});
start = intervals[i][0];
} else {
intervals[i][1] = Math.max(intervals[i][1], intervals[i - 1][1]);
}
}
res.add(new int[]{start, intervals[intervals.length - 1][1]});
return res.toArray(new int[res.size()][]);
}
}
66. 加一 （easy)
- 思路：如果
digits[i] %= 10不為0，則直接返回digits毅舆，循環(huán)過程中沒有reutrn掉說明一直進位到最大位置愈腾。 - 復雜度：時間復雜度
O(n)虱黄，空間復雜度O(1)
js：
//例子：12，19粱甫， 99
var plusOne = function(digits) {
const len = digits.length;
for(let i = len - 1; i >= 0; i--) {
digits[i]++;
digits[i] %= 10;//求余10作瞄，覆蓋當前位置
if(digits[i]!=0)//沒有進位就直接返回這個數(shù)
return digits;
}
digits = [...Array(len + 1)].map(_=>0);//循環(huán)沒有return掉 處理一直進位到最大位置
//[1,0,0]
digits[0] = 1;
return digits;
};
java：
class Solution {
public int[] plusOne(int[] digits) {
int len = digits.length;
for(int i = len - 1; i >= 0; i--) {
digits[i]++;
digits[i] %= 10;
if(digits[i]!=0)
return digits;
}
digits = new int[len + 1];
digits[0] = 1;
return digits;
}
}
73. 矩陣置零（ medium）
ds_170
- 思路:用兩個變量標記第一行和第一列是否有0乌庶，接著循環(huán)一遍矩陣契耿，如果遇見0搪桂，將和這個網(wǎng)格相同的第一行和第一列的元素標記成0踢械，在循環(huán)矩陣裸燎，如果當前網(wǎng)格對應的第一行和第一列是0，則將這個單元格置為0荷荤。最后如果第一列有0 蕴纳，則將這第一列全部置為0,如果第一行有0 个粱，則將這第一行全部置為0
- 復雜度：時間復雜度
O(mn)都许，m胶征、n為矩陣的行和列“负荩空間復雜度O(1)
js:
var setZeroes = function(matrix) {
const m = matrix.length, n = matrix[0].length;
let flagCol0 = false, flagRow0 = false;//表示第一行和第一列有沒有0
for (let i = 0; i < m; i++) {//尋找第一列是否存在0
if (matrix[i][0] === 0) {
flagCol0 = true;
}
}
for (let j = 0; j < n; j++) {
if (matrix[0][j] === 0) {
flagRow0 = true;
}
}
for (let i = 1; i < m; i++) {//循環(huán)矩陣骂铁，如果遇見0拉庵，將和這個網(wǎng)格相同的第一行和第一列的元素標記成0
for (let j = 1; j < n; j++) {
if (matrix[i][j] === 0) {
matrix[i][0] = matrix[0][j] = 0;
}
}
}
for (let i = 1; i < m; i++) {//循環(huán)矩陣钞支，如果當前網(wǎng)格對應的第一行和第一列是0伸辟，則將這個單元格置為0
for (let j = 1; j < n; j++) {
if (matrix[i][0] === 0 || matrix[0][j] === 0) {
matrix[i][j] = 0;
}
}
}
if (flagCol0) {//如果第一列有0 馍刮，則將這第一列全部置為0
for (let i = 0; i < m; i++) {
matrix[i][0] = 0;
}
}
if (flagRow0) {//如果第一行有0 卡啰，則將這第一行全部置為0
for (let j = 0; j < n; j++) {
matrix[0][j] = 0;
}
}
};
java
class Solution {
public void setZeroes(int[][] matrix) {
int m = matrix.length, n = matrix[0].length;
boolean flagCol0 = false, flagRow0 = false;
for (int i = 0; i < m; i++) {
if (matrix[i][0] == 0) {
flagCol0 = true;
}
}
for (int j = 0; j < n; j++) {
if (matrix[0][j] == 0) {
flagRow0 = true;
}
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
if (matrix[i][j] == 0) {
matrix[i][0] = matrix[0][j] = 0;
}
}
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
if (matrix[i][0] == 0 || matrix[0][j] == 0) {
matrix[i][j] = 0;
}
}
}
if (flagCol0) {
for (int i = 0; i < m; i++) {
matrix[i][0] = 0;
}
}
if (flagRow0) {
for (int j = 0; j < n; j++) {
matrix[0][j] = 0;
}
}
}
}
419. 甲板上的戰(zhàn)艦 （medium）
- 思路：尋找船頭的個數(shù)
- 復雜度：時間復雜度
O(n^2)振湾，空間復雜度O(1)
X..X
...X
...X
js:
function countBattleships(board) {
const lenX = board.length, lenY = board[0].length
let count = 0
for (let i = 0; i < lenX; i++) {
for (let j = 0; j < lenY; j++) {
//左邊和上面不是X 則是船頭
if ((board[i][j] == 'X') && (i == 0 || board[i - 1][j] == '.') && (j == 0 || board[i][j - 1] == '.')) {
++count;
}
}
}
return count
};
java：
class Solution {
public int countBattleships(char[][] board) {
int count=0,i,j;
for(i=0;i<board.length;++i) {
for(j=0;j<board[0].length;++j){
if((board[i][j]=='X')&&(i==0||board[i-1][j]=='.')&&(j==0||board[i][j-1]=='.')) {
++count;
}
}
}
return count;
}
}
