leetcode 242. 有效的字母异位词

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。


示例 1:
输入: s = "anagram", t = "nagaram"
输出: true

示例 2:

输入: s = "rat", t = "car"
输出: false
说明:
你可以假设字符串只包含小写字母。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/valid-anagram
思路：简单水题咋做都行，直接将出现过的字母统计出现次数最后对比出现的次数是否相等就行。
时间复杂度：$O(n+m)$
空间复杂度：$O(1)$

class Solution {
public:
    bool isAnagram(string s, string t) {
        vector<int>h1(26),h2(26);
        for(auto &c:s) h1[c-'a']++;
        for(auto &c:t) h2[c-'a']++;
        for(int i=0;i<26;i++){
            if(h1[i] != h2[i]) return false;
        }
        return true;
    }
};

leetcode 79. 单词搜索

给定一个二维网格和一个单词，找出该单词是否存在于网格中。单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例:
board =
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

给定 word = "ABCCED", 返回 true
给定 word = "SEE", 返回 true
给定 word = "ABCB", 返回 false

提示：

board 和 word 中只包含大写和小写英文字母。
1 <= board.length <= 200
1 <= board[i].length <= 200
1 <= word.length <= 10^3

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

思路：根据当前指向的字母去找即可，简单回溯。

class Solution {
public:
    int n,m,len;
    bool vis[201][201];
    int dir[4][2] = {{-1,0},{0,1},{1,0},{0,-1}};
    bool exist(vector<vector<char>>& board, string word) {
        n = board.size(), m = board[0].size(), len = word.size();
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(board[i][j] == word[0]){
                    if(dfs(board,word,0,i,j)) return true;
                }
            }
        }
        return false;
    }
    bool dfs(vector<vector<char>>& board, string &word,int pos,int x,int y){
        if(pos == len-1) return true;
        vis[x][y] = 1;
        for(int i=0;i<4;i++){
            int newx = x + dir[i][0];
            int newy = y + dir[i][1];
            if(newx<0 || newx>=n || newy<0 || newy>=m) continue;
            if(vis[newx][newy]) continue;
            if(pos<len-1 && word[pos+1] == board[newx][newy]){
                if(dfs(board,word,pos+1,newx,newy)) return true;
            }
        }
        vis[x][y] = 0;
        return false;
    }
};

leetcode 842. 将数组拆分成斐波那契序列

给定一个数字字符串 S，比如 S = “123456579”，我们可以将它分成斐波那契式的序列 [123, 456, 579]。形式上，斐波那契式序列是一个非负整数列表 F，且满足：

0 <= F[i] <= 2^31 - 1，（也就是说，每个整数都符合 32 位有符号整数类型）；
F.length >= 3；
对于所有的0 <= i < F.length - 2，都有 F[i] + F[i+1] = F[i+2] 成立。

另外，请注意，将字符串拆分成小块时，每个块的数字一定不要以零开头，除非这个块是数字 0 本身。返回从 S 拆分出来的任意一组斐波那契式的序列块，如果不能拆分则返回 []。

1
2
3

示例 1：
输入："123456579"
输出：[123,456,579]

1
2
3

示例 2：
输入: "11235813"
输出: [1,1,2,3,5,8,13]

示例 3：
输入: "112358130"
输出: []
解释: 这项任务无法完成。

示例 4：
输入："0123"
输出：[]
解释：每个块的数字不能以零开头，因此 "01"，"2"，"3" 不是有效答案。

示例 5：
输入: "1101111"
输出: [110, 1, 111]
解释: 输出 [11,0,11,11] 也同样被接受。

提示：

1 <= S.length <= 200
字符串 S 中只含有数字。

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/split-array-into-fibonacci-sequence
思路：简单回溯，按照每一个要添加的数字有多少位递归即可，当前答案中没有两个数则直接加入，否则要添加的数要等于前两项之和，因为每个数不能超过int所以每个数最多10位,要注意一下0开头的数长度只能为1，即0本身。

class Solution {
public:
    int n,cursize=0;
    vector<int> splitIntoFibonacci(string s) {
        vector<int> cur;
        n = s.size();
        if(dfs(s,cur,0)) return cur;
        return {};
    }
    bool dfs(string &s,vector<int> &cur,int pos){
        if(pos == n && cursize >= 3) return true;
        long num = 0;
        for(int len = 1;len <= 10 && pos+len <= n;len++){
            string t = s.substr(pos,len);
            num = num*10 + s[pos+len-1] - '0';
            if(num <= INT_MAX && (cursize < 2 || (long)cur[cursize-1] + (long)cur[cursize-2] == num)){
                cur.push_back(num), cursize++;
                if(dfs(s,cur,pos+len)) return true;
                cur.pop_back(), cursize--;
            }
            if(s[pos] == '0') break;
        }
        return false;
    }
};