字母异位词分组

问题描述

给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。

示例:
输入: ["eat", "tea", "tan", "ate", "nat", "bat"],
输出:
[
["ate","eat","tea"],
["nat","tan"],
["bat"]
]

说明：
所有输入均为小写字母。
不考虑答案输出的顺序。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/group-anagrams

思路

使用map映射

• 如果单词是异位词，那么他们本身对sort排序后，应该相同的。
• 所以，异位词会在同一个k的映射下（不知道这种表述对不对，大概是这个意思...）
  map<string, vector<string>> table
  比如，eat排序后为aet，tea排序后也为aet，所以，aet对应eat，aet也对应tea。

• 将结果存到vector<vector<string>> ret即可。

  题解

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string> &strs) {
        vector<vector<string>> ret;
        map<string, vector<string>> table;
        for (const string &str : strs) {
            string buf = str;
            sort(buf.begin(), buf.end());
            table[buf].push_back(str);
        }
        for (const auto &each : table) {
            ret.push_back(each.second);
        }
        return ret;
    }
};

给单链表加一

问题描述

你可以假设这个整数除了 0 本身，没有任何前导的 0。
这个整数的各个数位按照 高位在链表头部、低位在链表尾部 的顺序排列。

示例:
输入: [1,2,3]
输出: [1,2,4]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/plus-one-linked-list

思路

从链表的最后一个节点开始，找到第一个不为9的位置

• 如果整个链表都为9，那么将原链表的节点的值都置为0，并在链表前加一个值为1的节点。
• 如果链表存在不为9的节点，该节点前边的节点值不变，该节点的值+1，该节点后边的值置为0。

题解

class Solution {
public:
    ListNode *plusOne(ListNode *head) {
        if (head == nullptr) return nullptr;
        ListNode *p = head;
        vector<int> vec;
        while (p != nullptr) {
            vec.push_back(p->val);
            p = p->next;
        }
        int location = -1;
        for (int i = vec.size() - 1; i >= 0; i--) {
            if (vec[i] != 9) {
                location = i;
                break;
            }
        }
        if (location == -1) {
            ListNode *tmphead = new ListNode(1);
            ListNode *tmp = head;
            while (tmp != nullptr) {
                tmp->val = 0;
                tmp = tmp->next;
            }
            tmphead->next = head;
            head = tmphead;
        } else {
            ListNode *tmp = head;
            int count = 0;
            while (count <location) {
                tmp = tmp->next;
                count++;
            }
            tmp->val = tmp->val + 1;
            tmp = tmp->next;
            while (tmp != nullptr) {
                tmp->val = 0;
                tmp = tmp->next;
            }
        }

        return head;
    }
};

水壶问题

问题描述

有两个容量分别为 x升 和 y升 的水壶以及无限多的水。请判断能否通过使用这两个水壶，从而可以得到恰好 z升 的水？
如果可以，最后请用以上水壶中的一或两个来盛放取得的z升水。

你允许：
装满任意一个水壶
清空任意一个水壶
从一个水壶向另外一个水壶倒水，直到装满或者倒空

示例 1: (From the famous "Die Hard" example)
输入: x = 3, y = 5, z = 4
输出: True

示例 2:
输入: x = 2, y = 6, z = 5
输出: False

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/water-and-jug-problem

思路

满足题意需要有z=x+y;
如果z=ax+by（a，b均整），x与y最大公约数为g，那么z一定是g的整数倍，即z%g=0;
需要注意的是，g不能为0，所以，x==0&&y==0这一种情况需要特判。

题解

class Solution {
public:
    bool canMeasureWater(int x, int y, int z) {
        if(x==0&&y==0) return z==x;
        return z%gcd(x,y)==0&&(x+y>=z);
    }
    int gcd(int x,int y){
        return y?gcd(y,x%y):x;
    }
};

数字范围按位与

问题描述

给定范围 [m, n]，其中 0 <= m <= n <= 2147483647，返回此范围内所有数字的按位与（包含 m, n 两端点）。

示例 1: 
输入: [5,7]
输出: 4

示例 2:
输入: [0,1]
输出: 0

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/bitwise-and-of-numbers-range

思路

当一个数+1时，总会有这么一个规律“某一位后的数字，全部被置为相反数”。举个例子：

• 010111 + 1 = 011000，则010111 & 011000 = 010000。那么，x & (x+1) 后几位相反数的“与操作”，结果总为0。
• 所以，当(m,m+1,...n-1,n)进行连续“与操作”时，会按照上述规律被抵消很大一部分，而只剩下n的前缀部分，最后只需将n归位。举个例子：
  m = 5(0101), n = 7 (0111)。不停右移，得到n前缀部分为01，最后归位前缀得res=0100=4

来源：李一一
链接：https://blog.csdn.net/smile_watermelon/article/details/47320381

题解

class Solution {
public:
    int rangeBitwiseAnd(int m, int n) {
        int count=0;
        for(;m!=n;count++){
            m>>=1;
            n>>=1;
        }
        int ret;
        ret=n<<count;
        return ret;
    }
};

二叉树的右视图

问题描述

给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

示例:
输入: [1,2,3,null,5,null,4]
输出: [1, 3, 4]
解释:

   1            <---
 /   \
2     3         <---
 \     \
  5     4       <---

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-right-side-view

思路

和层次遍历的思路是一样的

• 按层将二叉树存到vector<vector<int>> vec中，此处和二叉树的层次遍历不同的是，本题从每层的右侧开始存。
  当然也可以从每层的左边开始遍历，用reverse反转一下就可以了。
• 将veci存到vector<int> ret中。
• 最后return ret即可。

题解

/**
 * 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:
    vector<vector<int>> vec;
    vector<int> ret;

    vector<int> rightSideView(TreeNode *root) {
        dfs(root, 0);
        int n = vec.size();
        if (n == 0) return ret;
        for(int i=0;i<n;i++){
            ret.push_back(vec[i][0]);
        }
        return  ret;
    }

    void dfs(TreeNode *node, int level) {
        if (node == nullptr) return;
        if (level + 1 > vec.size()) vec.push_back(vector<int>());
        vec[level].push_back(node->val);
        dfs(node->right, level + 1);
        dfs(node->left, level + 1);
    }
};