Welcome to BeckoninGshy's Bolg

LeetCode-59-螺旋矩-II

59. 螺旋矩阵 II

给定一个正整数 n，生成一个包含 1 到 n² 所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。

与54. 螺旋矩阵类似。

只需要依次给新数组中的相应元素赋值即可。

Solution：

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
class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int> > res(n, vector<int>(n));;
        if(n <= 0) return res;
        int k = 1;
        int left = 0, right = n-1, up = 0, down = n-1;
        while(left < right && up < down){

            int i = left, j = up;
            while(i < right){
                res[j][i] = k++;
                i++;
            } 
            while(j < down){
                res[j][i] = k++;
                j++;
            }
            while(i > left){
                res[j][i] = k++;
                i--;
            }
            while(j > up){
                res[j][i] = k++;
                j--;
            }
            left++;
            right--;
            up++;
            down--;
        }
        
        //形不成圈（单列或者单行）
        if(up == down){
            while(left <= right){
                res[up][left++] = k++;
            }
        }else if(left == right){
            while(up <= down){
                res[up++][left] = k++;
            }
        }
        return res;
        
    }
};
阅读更多
LeetCode-693-交替位二进制数

693. 交替位二进制数

给定一个正整数，检查他是否为交替位二进制数：换句话说，就是他的二进制数相邻的两个位数永不相等。

示例 1:

输入: 5

输出: True

解释:
5的二进制数是: 101

Solution：

1
2
3
4
5
6
7
8
9
class Solution {
public:
    bool hasAlternatingBits(int n) {
        //如果是奇偶交替，则n ^ (n >> 1) 会使有效位全为1，
        int temp = n ^ (n >> 1);
        //有效位全为1 再加1， 得到有效位前面为1，后面全为0，再与该数与，则全部清零。
        return (temp & (temp+1)) == 0;
    }
};
阅读更多
LeetCode-476-数字的补数

476. 数字的补数

给定一个正整数，输出它的补数。补数是对该数的二进制表示取反。

注意:

  • 给定的整数保证在32位带符号整数的范围内。
  • 你可以假定二进制数不包含前导零位。
    示例 1:

输入: 5

输出: 2

解释: 5的二进制表示为101（没有前导零位），其补数为010。所以你需要输出2。

Solution：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int findComplement(int num) {
        int cot = 0;
        int temp = num;
        while(1){
            if(num == 0) break;
            num = num >> 1;
            cot++;
        } 
        int mark = 0xffffffff;
        return ~temp ^ (mark << cot);
    }
};

首先找到该数是从哪一位开始才算有效（即不包含前面零的位置。）
再将该数所有位取反，
然后用全位置的1左移cot次，与值异或即可。

异或：不同为一，相同为零，所以当前面的零取反后成为一后，相应位置与1异或，会恢复成为0，之后的有效位还保持不变。

阅读更多
LeetCode-51-N皇后

51. N皇后

该题为著名的n皇后问题。

Solution：

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
48
49
50
51
52
53
54
55
56
class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<string> mark;
        vector<string> queenposition;
        vector<vector<string> > map;
        //初始化。
        string a = "";
        for(int i = 0; i < n;i++){
            a = a + ".";
        }
        for(int i = 0; i < n; i++){
            queenposition.push_back(a);
            mark.push_back(a);
        }
        
        dfs(mark,queenposition,map,0,n);
        return map;
    }
    void putOneQueen(vector<string> &mark,int x,int y,int n){
        static const int dx[8] = {-1,-1,-1,0,0,1,1,1};
        static const int dy[8] = {-1,0,1,-1,1,-1,0,1};
        
        mark[x][y] = '1';

        for(int i = 0; i < 8; i++){
            int nx = x + dx[i],ny = y+dy[i]; 
            while(0 <= nx && nx < n && 0 <= ny && ny < n){
                mark[nx][ny] = '1';
                nx += dx[i];
                ny += dy[i];	
            }
        }
	}
    
    void dfs(vector<string> &mark,vector<string> &queenposition,vector<vector<string> > &map,int col,int n){
        //出口
        if(col == n){
            map.push_back(queenposition);
            return;
        }
        for(int i = 0; i < n;i++){
            if(mark[col][i] == '.'){//可以放皇后 
                vector<string> temp_mark = mark;//记录回溯前的镜像。
                //放皇后。 
                queenposition[col][i] = 'Q';
                putOneQueen(mark,col,i,n);
                //递归调用。 
                dfs(mark,queenposition,map,col+1,n);
                //回溯 
                mark = temp_mark;
                queenposition[col][i] = '.';
            }
        }
    }
};

该题考查对递归与回溯算法的掌握。

使用一个矩阵来存储是否可以放皇后的状态。
每当一行放置了一个皇后后，更新其状态，并在下一行中挑选合适的位置来放置该行的皇后。

直到每一行都放置了皇后，保存状态，返回上一个递归过程。

回溯主要针对矩阵的状态和皇后放置的位置，以便利于递归返回过程中的再次使用。

阅读更多
LeetCode-45-跳跃游-II

45. 跳跃游戏 II

此题55. 跳跃游戏的进阶版

给定一个非负整数数组，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

你的目标是使用最少的跳跃次数到达数组的最后一个位置。

按照前面题的思路，依然是从后往前搜索。每次搜索能跳到当前位置的最远位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int jump(vector<int>& nums) {
        // 选择当前能跳到当前点的最远的距离。
        int max_index = nums.size()-1;
        int current_max_index = max_index;
        int step = 0;
        //当没有到达开头位置，进行循环。
        while(max_index > 0){
            //记录能跳到当前数组的最前面的点。
            for(int i = max_index-1; i >= 0; i--){
                if(i + nums[i] >= max_index){
                    current_max_index = i;
                }
            }
             //更新能跳的最远的点。
            max_index = current_max_index;
            //步数更新
            step++;
        }
        return step;
    }
    
};

用了两层循环，发现能ac，但是又排在了末名。

看了大神的代码，写出了下面的代码：

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
class Solution {
public:
    int jump(vector<int>& nums) {
        if(nums.size() < 2){
            return 0;
        }
        //当前可到达的最远距离。
        int current_max_index = nums[0];
        //遍历各个位置中，可到达的最远距离。
        int pre_max_max_index = nums[0];
        int jump = 1;
        
        for(int i = 1; i < nums.size(); i++){
            //更新当前可达到的最远距离。
            if(i > current_max_index){
                jump++;
                current_max_index = pre_max_max_index;
            }
            if(pre_max_max_index < nums[i] + i){
                //更新
                pre_max_max_index = nums[i] + i;
            }
        }
        return jump;
    }
    
};

跳到当前所能跳到的最远的位置所在的位置中。

记录当前位置所能到达的最远的位置。

如果做到了该最远位置，更新一下。继续走。

阅读更多
LeetCode-40-组合总-II

40. 组合总和 II

给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用一次。

示例 1:

输入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]

示例 2:

输入: candidates = [2,5,2,1,2], target = 5,
所求解集为:
[
[1,2,2],
[5]
]

该题为90. 子集 II的升级版

与上题相同的是，都要保证元素的非重复性，所以与上题使用set部分的代码是一致的。

区别在于在进行递归的过程中，需要随时对条件进行判断，只有满足等于target，才往result中添加。

并且在剪枝的时候，如果元素之和已经比target大，就没有必要进行下去了，直接退出即可。

Solution：

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
class Solution {
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        vector<vector<int> > result;
        vector<int> item;
        //去重所使用的集合
        set<vector<int>> item_set;
        //对nums进行排序。
        sort(candidates.begin(),candidates.end());
        putitem(0, candidates, result, item, item_set,target, 0);
        return result;
        
    }
    void putitem(int i, vector<int>& nums,vector<vector<int> > &result, vector<int> &item, set<vector<int>> &item_set,int target, int sum){
        if(i >= nums.size() || sum > target) return;
        
        sum += nums[i];
        item.push_back(nums[i]);
        //如果没有重复，就加入到最终的集合里。
        if(sum == target && item_set.find(item) == item_set.end()){
            result.push_back(item);
            //加入去重集合中。
            item_set.insert(item);
        }
        putitem(i+1, nums, result, item, item_set, target, sum);
        sum -= nums[i];
        item.pop_back();
        putitem(i+1, nums, result, item, item_set, target, sum);
    } 
};
阅读更多
LeetCode-389-找不同

389. 找不同

给定两个字符串 s 和 t，它们只包含小写字母。

字符串 t 由字符串 s 随机重排，然后在随机位置添加一个字母。

请找出在 t 中被添加的字母。

示例:

输入：
s = “abcd”
t = “abcde”

输出：
e

解释：
‘e’ 是那个被添加的字母。

Solution:

1
2
3
4
5
6
7
8
9
class Solution {
public:
    char findTheDifference(string s, string t) {
        char e = 0;
        for(int i = 0; i < s.size(); i++) e ^= s[i];
        for(int i = 0; i < t.size(); i++) e ^= t[i];
        return e;
    }
};

与136. 只出现一次的数字一样的思路，考察异或的使用。

阅读更多
LeetCode-240-搜索二维矩-II

240. 搜索二维矩阵 II

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性：

  • 每行的元素从左到右升序排列。
  • 每列的元素从上到下升序排列。

Solution：

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if(matrix.size() <= 0) return false;
        int i = 0, j = matrix[0].size()-1;
        while(i < matrix.size() && j >= 0){
            if(target == matrix[i][j]) return true;
            else if(target > matrix[i][j]) i++;
            else if(target < matrix[i][j]) j--;
        }
        return false;
    }
};

思路：

从矩阵的左上角出发，如果比目标值大，向左移，如果比目标值小，向下移。出界或找到则结束。

对于一列，如果比当前值小，说明不在当前列中，列减一（缩小搜索范围）。
对于一行，如果比当前值小，则往前移动一个位置。

经过不断缩小范围（以经过的点划矩形），就可以得知目标值是否存在矩阵中。

阅读更多
LeetCode-234.回文链表

234.回文链表

请判断一个链表是否为回文链表。

Solution1：
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
//获得链表长度
int getListLength(ListNode* head){
    int len = 0;
    while(head){
        head = head->next;
        len++;
    }
    return len;
}
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        ListNode* head1 = head;
        int listlen = getListLength(head1);
        if(listlen <= 1) return true;
        int mid = listlen/2;
        std::stack<int> s;
        while(mid && head){
            s.push(head->val);
            head = head->next;
            mid--;
        }
        if(listlen%2 != 0){
            head = head->next;
        }
        while(head){
            if(head->val != s.top()){
               return false; 
            }
            s.pop();
            head = head->next;
        }
        return true;
    }
};
思路:

借助stack。

将mid之前的元素值都push进stack中，然后到mid之后，将每个元素与栈顶值比较。不相等退出，相等继续下一轮。

Solution2：
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
48
49
50
51
52
53
//获得链表长度
int getListLength(ListNode* head){
    int len = 0;
    while(head){
        head = head->next;
        len++;
    }
    return len;
}

//根据位置与所给链表，向后移动position步。
ListNode* getNodeByPosition(ListNode* head,int position){
    while(position>0){
        head = head->next;
        position--;
    }
    return head;
}

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        //存储头结点。
        ListNode* first = head;
        ListNode* head1 = head;
        int listlen = getListLength(head);
        int midposition = listlen/2;
        //如果链表长度<=1，直接返回true;
        if(listlen <= 1) return true;
        //到达需要翻转的长度，对于偶数，为（listlen/2）+1，对于奇数，为listlen/2;
        ListNode* mid = getNodeByPosition(head1,midposition);
        //翻转mid之后的指针。
        ListNode * newHead = NULL;
        int position = listlen-midposition;
        while(mid && position){
            ListNode* next = mid->next;
            mid->next = newHead;
            newHead = mid;
            mid = next;
            position--;
        }
        //将翻转之后的链表与开头的链表的内容比较，向后比较listlen/2;
        //如果是偶数，则元素都会比较到，如果是奇数，最后一个元素不会比较到。他在原来的链表中就处于中心位置，不必比较。
        while(first && newHead && midposition){
            //只要不相等，就为false;
            if(first->val != newHead->val) return false;
            first = first->next;
            newHead = newHead->next;
            midposition--;
        }
        return true;
    }
};
思路：

将链表的后半段翻转，从翻转位置开始与从头结点开始，依次比较（listlen/2次）。

阅读更多
LeetCode-235-二叉搜索树的最近公共祖先

235. 二叉搜索树的最近公共祖先

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

Solution1（递归版）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root->val < p->val && root->val < q->val){
            return lowestCommonAncestor(root->right,p,q);
        }else if(root->val > p->val && root->val > q->val){
            return lowestCommonAncestor(root->left,p,q);
        }
        return root;
    }
};

ONELINE版：

1
2
3
4
5
6
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        return ((root->val - p->val) * (root->val - q->val) < 1) ? root: lowestCommonAncestor(root->val < p->val ? root->right : root->left, p, q ) ;
    }
};

1
(root->val - p->val) * (root->val - q->val) < 1

这段代码表示给定的两个结点是否在当前节点的两个不同的子树上，或者两个节点中有节点与当前所在节点相同。如果是，则该节点就是最近公共祖先。如果不是，说明在同一棵子树上，转移到该子树上继续递归调用。

Solution2（迭代版）：

1
2
3
4
5
6
7
8
9
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        while((root->val - p->val) * (root->val - q->val) > 0){
            root = root->val > p->val ? root->left : root->right;
        }
        return root;
    }
};

与上面思路类似。

阅读更多
首页 归档 标签 关于 搜索