leetcode-78-79

leetcode78题79题:

leetcode78题(子集):

给定一组不含重复元素的整数数组 nums,返回该数组所有可能的子集(幂集)。

说明:解集不能包含重复的子集。

示例:
1
2
3
4
5
6
7
8
9
10
11
12
输入: nums = [1,2,3]
输出:
[
[3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]
解答(回溯法):
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
var subsets = function(nums) {
var result = [];
var path = [];
nums.sort(compare);//先将数组排序,方便后面进行处理
dfs(nums,path,0,result);
return result;
};
function compare(a,b){
return a-b;
}
function dfs(nums,path,cur,result){//表示此轮将给path数组中位置为cur的数组元素赋值
result.push(path.slice(0,cur));//将上一轮设置好的数组放在结果数组里面
if(cur==nums.length){//cur已经到了数组的最后一个元素
return;
}
for(var i=0;i<nums.length;i++){
//当cur不为0且path的cur-1位置的元素大于等于即将添加的元素,那么开始下一轮循环
if(cur&&path[cur-1]>=nums[i]){
continue;
}
path[cur] = nums[i];
dfs(nums,path,cur+1,result);
}
}

leetcode79题(单词搜索):

给定一个二维网格和一个单词,找出该单词是否存在于网格中。

单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例:
1
2
3
4
5
6
7
8
9
10
board =
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]

给定 word = "ABCCED", 返回 true.
给定 word = "SEE", 返回 true.
给定 word = "ABCB", 返回 false.
解答:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
var exist = function(board, word) {
if(board.length==0||word.length==0){
return false;
}
var d = [[-1,0],[0,1],[1,0],[0,-1]];//四周数组
var x = board.length;
var y = board[0].length;
var visited = [];//该数组用来标记某个位置的字母是否被遍历了
for(var i=0;i<x;i++){
visited[i] = [];
for(var j=0;j<y;j++){
visited[i][j] = false;
}
}
for(var i=0;i<x;i++){
for(var j=0;j<y;j++){
if(process(board,i,j,word,0,x,y,visited,d)){//判断单词的首字母以i,j位置上的字母开头,是否可以遍历到字符串
return true;
}
}
}
return false;//以所有的位置开始,都遍历不到,说明找不到,那么返回false
};

function process(board,row,column,word,index,x,y,visited,d){
if(index == word.length-1){//说明找到单词的最后一个字符了
return board[row][column]==word[index];
}
if(board[row][column]==word[index]){
visited[row][column] = true;//表示这个位置的元素被遍历过了
for(var h=0;h<d.length;h++){//遍历四周数组,得到新行新列
var newRow = row+d[h][0];
var newColumn = column+d[h][1];
//如果新的行值和新的列值是合法的,并且该位置字符没有被遍历过,同时其process方法返回true,那么返回true
if(judgeLegal(newRow,newColumn,x,y)&&!visited[newRow][newColumn]&&process(board,newRow,newColumn,word,index+1,x,y,visited,d)){
return true;
}
}
//执行到这里,说明从该位置开始到后面,没有找到完全匹配的方式
visited[row][column] = false;//要回溯到其它方位
}
return false;
}

function judgeLegal(row,column,x,y){//判断得到的坐标值是否合法
return row>=0 && column>=0 && row<x && column<y;
}

小k

分享到