第一题

268. 缺失数字

2.png

3.png

Image.png

解法一：数字求和

然后和1到n项得数列和对比，相差的数就是缺的数。为减小数据溢出风险，采用边加边减【首先想到的一种方法】

//C++
class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int size = nums.size();
        int sum = 0;
        for(int i = 1; i <= size; i++){
            sum += i;
            sum -= nums[i-1];
        }
        return sum;
    }
};

class Solution {
public:
    int missingNumber(vector<int>& nums) {
    int sum = 0, n = nums.size();
    for(int n : nums)   sum += n;  //枚举这个参数传进的数组
    return (n * (n+1)) / 2 - sum;
    }
};

解法二：位运算-异或

将0到n异或，并且同时异或nums[0]到nums[n-1]，共2n+1个数，相同的数异或结果为0，0^a = a，最后的结果就是缺失的数字

C++
class Solution {
public:
    int missingNumber(vector<int>& nums) {
    int res = nums.size();
    for(int i = 0; i < nums.size(); ++i)
        res = res ^ i ^ nums[i];            // a^b^b = a;
    return res ;
    }
};

JAVA
class Solution {
    public int missingNumber(int[] nums) {
        int missing = nums.length;
        for(int i = 0; i < nums.length; i++){
            missing ^= i ^ nums[i];
        }
        return missing;
    }
}

解法三：排序

class Solution {
public:
    int missingNumber(vector<int>& nums) {
    sort(nums.begin(),nums.end());
    for(int i = 0; i < nums.size(); ++i)
        if(i != nums[i])    return i;
    return nums.size();   //为什么这里必须是返回序列的大小
    }
};

解法四：二分

class Solution {
public:
    int missingNumber(vector<int>& nums) {
    sort(nums.begin(),nums.end());
    int left = 0, right = nums.size(), mid= (left + right)/2;
    while(left < right)
    {
        mid = (left + right)/2;
        if(nums[mid] > mid) right = mid;
        else left = mid+1;
    }
    return left;
    }
};

解法五：排序

首先我们对数组进行排序，随后我们可以在常数时间内判断两种特殊情况：0 没有出现在数组的首位，以及 n 没有出现在数组的末位。如果这两种特殊情况都不满足，那么缺失的数字一定在 0 和 n 之间（不包括两者）。此时我们可以在线性时间内扫描这个数组，如果某一个数比它前面的那个数大了超过 1，那么这两个数之间的那个数即为缺失的数字。

class Solution {
    public int missingNumber(int[] nums) {
        Arrays.sort(nums);


        // 判断 n 是否出现在末位
        if (nums[nums.length-1] != nums.length) {
            return nums.length;
        }
        // 判断 0 是否出现在首位
        else if (nums[0] != 0) {
            return 0;
        }


        // 此时缺失的数字一定在 (0, n) 中
        for (int i = 1; i < nums.length; i++) {
            int expectedNum = nums[i-1] + 1;
            if (nums[i] != expectedNum) {
                return expectedNum;
            }
        }


        // 未缺失任何数字（保证函数有返回值）
        return -1;
    }
}

4.png

解法六：哈希表

直接查询每个数是否在数组中出现，找出缺失的数字，使用哈希表

class Solution {
    public int missingNumber(int[] nums) {
        Set<Integer> numSet = new HashSet<Integer>();  //定义一个哈希Set集合。存放int及int对象
        for (int num : nums) numSet.add(num);  //遍历nums的值

        int expectedNumCount = nums.length + 1;
        for (int number = 0; number < expectedNumCount; number++) {
            if (!numSet.contains(number)) {
                return number;
            }
        }
        return -1;
    }
}

5.png

第二题

49.字母异位词分组

6.png

7.png

解法一：遍历strs

对每个string进行排序，异位词的排序结构是一样的，在map中的key值也一样，在map中添加对应的vector，再将vector逐个添加到res中【常规方法】

#Python3
class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        if not strs:
            return []
        res, dics = [],{}
        for s in strs:
            key = "".join(sorted(s))
            index = dics.setdefault(key,len(res))
            if index == len(res):
                res.append([s])
            else:
                res[index].append(s)
        return res

#C++
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> res;
        unordered_map <string,vector<string> > m;
        for(string& s : strs)
        {
            string t = s;
            sort(t.begin(),t.end());
            m[t].push_back(s);   //t为单词的按顺序排列，作为key值，m[t]则为该单词的异位词构成的vector，作为value值
        }
        for(auto& n : m)                //n为键和值组成的pair
            res.push_back(n.second);
        return res;
    }
};

解法二：每个字符对应一个ASCII码，使用质数作为乘法因子【参考题解，方法易理解】

#JAVA
class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        int[] primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29,
                31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
                73, 79, 83, 89, 97, 101};


        // key 是字符串自定义规则下的哈希值
        Map<Integer, List<String>> hashMap = new HashMap<>();
        for (String s : strs) {
            int hashValue = 1;


            char[] charArray = s.toCharArray();
            for (char c : charArray) {
                hashValue *= primes[c - 'a'];
            }


            // 把单词添加到哈希值相同的分组
            if (hashMap.containsKey(hashValue)) {
                List<String> curList = hashMap.get(hashValue);
                curList.add(s);
            } else {
                List<String> newList = new ArrayList<>();
                newList.add(s);
                hashMap.put(hashValue, newList);
            }
        }
        return new ArrayList<>(hashMap.values());
    }
}

#C++
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> res;
        unordered_map <double,vector<string> > m;
        double a[26]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101};
        for(string& s : strs)
        {
            double t = 1;
            for(char c : s)
            t *= a[c - 'a'];


            m[t].push_back(s);          //t为单词对应的质数乘积，m[t]则为该单词的异位词构成的vector
        }
        for(auto& n : m)                //n为键和值组成的pair
            res.push_back(n.second);
        return res;
    }
};

for(char c : s)//定义一个遍历字符c，让它分别等于字符串数组s里面的各个字符，然后执行下面的语句，当c被赋值为s里面所有字符各一次后，就会退出这个循环

第三题

756.金字塔转换矩阵

8.png

9.png

10.png

解法：深度优先遍历

1.找到当前bottom层的上一层解，如果解均存在，则继续将bottom的上一层解作为当前bottom进行再一次求解，否则退回到前一次递归直至上一层解均存在；退回到前一次递归并不是直接结束，而是存在着对当前位置的可能元素集合的遍历，例如，一个位置可能有3个不同元素存在的可能，则在此位置最多会触发3次遍历。
2.根据递归的大致轮廓，可知递归完全结束的终点在于，如果金字塔存在，那么递归一定能遍历到塔尖然后返回true；否则递归会一直进行，直到当前bottom的所有位置上的所有元素的可能全部遍历完成，最终得到金字塔不存在的解。
3.递归包含在遍历中，每次遍历都出发一次递归，符合深度优先的思想。用HashMap存储三元组

class Solution {
    public boolean pyramidTransition(String bottom, List<String> allowed) {
        HashMap<String, ArrayList<Character>> map = new HashMap<>();
        for (String word : allowed) {
            String key = word.substring(0, 2);
            char value = word.charAt(2);
            if (!map.containsKey(key)) {
                map.put(key, new ArrayList<>());
            }
            map.get(key).add(value);
        }
        return helper(bottom, map);
    }


    public boolean helper(String bottom, HashMap<String, ArrayList<Character>> map) {
        if (bottom.length() == 1) {
            return true;
        }
        int n = bottom.length();
        //上一层的长度为 n - 1
        List<Character>[] lists = new List[n - 1];
        for (int i = 1; i < n; i++) {
            lists[i - 1] = map.getOrDefault(bottom.substring(i - 1, i + 1), new ArrayList<>());
        }
        return dfs(lists, 0, new StringBuilder(), map);
    }


    //用 sb 记录着一层被构建的情况
    public boolean dfs(List<Character>[] lists, int cur, StringBuilder sb, HashMap<String, ArrayList<Character>> map) {
        if (cur == lists.length) {
            return helper(sb.toString(), map);
        }
        for (char c : lists[cur]) {
            sb.append(c);
            if (dfs(lists, cur + 1, sb, map)) {
                return true;
            }
            sb.deleteCharAt(sb.length() - 1);
        }
        return false;
    }

}

charAt（）方法的使用

1.作用：返回指定索引处的char值。索引范围是从0-length（）-1。
2.声明方法：public char charAt(int index)
3.参数：index——该数的char值
4.异常：IndexOutOfBoundsException——当index参数为负或不小于该字符串的长度
5.实例：

public class Test{
    public static void main(String[] args){
        String s = "abc";
        System.out.println(s.charAt(1));
    }
}

运行结果
b

substring（）方法的使用

1.作用：用于提取字符串中介于两个指定下标之间的字符
2.语法：public String substring(int beginIndex, int endInxdex)
3.返回值：返回的子串包括beginIndex处的字符，但不包括endInxdex处的字符
4.实例：

public class Test{
    public static void main(String args[]){
        String Str = new String("Hello World");
        System.put.println(Str.substring(4，7));
    }
}

运行结果
o W

Map.getOrDefault(Object key, V defaultValue)方法

1.作用：当Map集合中存在这个key时，就使用这个key值，如果没有就是用默认值defaultValue

第四题

130.被围绕的区域

11.png

12.png

13.png

解法：深度优先搜索。

将边界的O特殊处理，剩下的O替换成X。可以将边界O换成#作为占位符，待搜索结束之后，遇到O替换成X；遇到#，替换成O
寻找边界相关O：从边界出发，对图进行dfs实现标记操作。

C++
class solution{
public:
    int n, m;

    void dfs(vector<vector<char>>&board, int x, int y){
        if(x < 0 || x >= n || y < 0 || y >= m || board[x][y] != 'O') {
            return;
        }
        board[x][y] = '#';
        dfs(board, x + 1, y);
        dfs(board, x - 1, y);
        dfs(board, x, y + 1);
        dfs(board, x, y - 1);
    }

    void solve(vector<vector<char>>& board) {
        n = board.size();
        if (n == 0) {
            return;
        }
        m = board[0].size();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                //从边缘O开始搜索
                boolean isEdge = i == 0 || j == 0 || i == m - 1 || j == n - 1;
                if (isEdge && board[i][j] == 'O'){
                    dfs(board, i, j);
                }
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (board[i][j] == '#') {
                    board[i][j] = 'O';
                }
                else if (board[i][j] == 'O'){
                    board[i][j] = 'X';
                }
            }
        }
    }
};

JAVA
class Solution {
    int n, m;

    public void solve (char[][] board) {
        n = board.length;
        if (n == 0 || board == null) {
            return;
        }
        m = board[0].length;

        for (int i = 0; i < n; i++) {
            dfs(board, i, 0);
            dfs(board, i, m - 1);
        }
        for (int i = 0; i < m - 1; i++) {
            dfs(board, 0, i);
            dfs(board, n - 1, i);
        }

        //下几行等于上面两个for循环
        for ( int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                //从边缘第一个是o的开始搜索
                boolean isEdge = i == 0 || j == 0 || i == m - 1 || j == n - 1;
                if (isEdge && board[i][j] == 'O') {
                    dfs(board, i, j);
                }
            }
        }
        //

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (board[i][j] == '#') {
                    board[i][j] = 'O';
                }
                else if (board[i][j] == 'O'){
                    board[i][j] = 'X';
                }
            }
        }
    }

    public void dfs(char[][] board, int x, int y) {
        if (x < 0 || x >= n || y < 0 || y >= m || board[x][y] != 'O') {
            return;
        }
        board[x][y] = '#';
        dfs(board, x - 1, y);  //上
        dfs(board, x + 1, y);  //下
        dfs(board, x, y - 1);  //左
        dfs(board, x, y + 1);  //右
    }
}

Python3
class Solution:
    def solve(self, board: List[List[str]]) -> None:
        if not board:
            return
        
        n, m = len(board), len(board[0])


        def dfs(x, y):
            if not 0 <= x < n or not 0 <= y < m or board[x][y] != 'O':
                return
            
            board[x][y] = "#"
            dfs(x + 1, y)
            dfs(x - 1, y)
            dfs(x, y + 1)
            dfs(x, y - 1)
        
        for i in range(n):
            dfs(i, 0)
            dfs(i, m - 1)
        
        for i in range(m - 1):
            dfs(0, i)
            dfs(n - 1, i)
        
        for i in range(n):
            for j in range(m):
                if board[i][j] == "#":
                    board[i][j] = "O"
                elif board[i][j] == "O":
                    board[i][j] = "X"

第五题

64.最小路径和

14.png

15.png

解法：动态规划

每个元素对应的最小路径和和与其相邻元素对应的最小路径和有关。创建二维数组dp，与原始网格大小相同，dp[i][j]表示从左上角出发到（i，j）位置的最小路径和。
显然dp[0][0] =grid[0][0]。
dp[i][0] = dp [i - 1][0] + grid[i][0]
dp[0][j] = dp [0][j - 1] + grid[0][j]
dp[i][j] = min(dp[i - 1][j] , dp[i][j - 1]) + grid[i][j]

JAVA
class Solution {
    public int minPathSum(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return 0;
        }
        int rows = grid.length, columns = grid[0].length;
        int[][] dp = new int[rows][columns];
        dp[0][0] = grid[0][0];
        for (int i = 1; i < rows; i++) {
            dp[i][0] = dp[i - 1][0] + grid[i][0];
        }
        for (int j = 1; j < columns; j++) {
            dp[0][j] = dp[0][j - 1] + grid[0][j];
        }
        for (int i = 1; i < rows; i++) {
            for (int j = 1; j < columns; j++) {
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
            }
        }
        return dp[rows - 1][columns - 1];
    }
}

不建立dp矩阵，直接遍历grid[i][j]修改。

class Solution {
    public int minPathSum(int[][] grid) {
        for(int i = 0; i < grid.length; i++) {
            for(int j = 0; j < grid[0].length; j++) {
                if(i == 0 && j == 0) continue;
                else if(i == 0)  grid[i][j] = grid[i][j - 1] + grid[i][j];
                else if(j == 0)  grid[i][j] = grid[i - 1][j] + grid[i][j];
                else grid[i][j] = Math.min(grid[i - 1][j], grid[i][j - 1]) + grid[i][j];
            }
        }
        return grid[grid.length - 1][grid[0].length - 1];
    }
}

C++
class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        if (grid.size() == 0 || grid[0].size() == 0) {
            return 0;
        }
        int rows = grid.size(), columns = grid[0].size();
        auto dp = vector < vector <int> > (rows, vector <int> (columns));
        dp[0][0] = grid[0][0];
        for (int i = 1; i < rows; i++) {
            dp[i][0] = dp[i - 1][0] + grid[i][0];
        }
        for (int j = 1; j < columns; j++) {
            dp[0][j] = dp[0][j - 1] + grid[0][j];
        }
        for (int i = 1; i < rows; i++) {
            for (int j = 1; j < columns; j++) {
                dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
            }
        }
        return dp[rows - 1][columns - 1];
    }
};

Python3
class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        if not grid or not grid[0]:
            return 0
        
        rows, columns = len(grid), len(grid[0])
        dp = [[0] * columns for _ in range(rows)]
        dp[0][0] = grid[0][0]
        for i in range(1, rows):
            dp[i][0] = dp[i - 1][0] + grid[i][0]
        for j in range(1, columns):
            dp[0][j] = dp[0][j - 1] + grid[0][j]
        for i in range(1, rows):
            for j in range(1, columns):
                dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]
        
        return dp[rows - 1][columns - 1]

算法题总结

算法题总结

第一题

268. 缺失数字

解法一：数字求和

解法二：位运算-异或

解法三：排序

解法四：二分

解法五：排序

解法六：哈希表

第二题

49.字母异位词分组

解法一：遍历strs

解法二：每个字符对应一个ASCII码，使用质数作为乘法因子【参考题解，方法易理解】

第三题

756.金字塔转换矩阵

解法：深度优先遍历

charAt（）方法的使用

substring（）方法的使用

Map.getOrDefault(Object key, V defaultValue)方法

第四题

130.被围绕的区域

解法：深度优先搜索。

第五题

64.最小路径和

解法：动态规划

不建立dp矩阵，直接遍历grid[i][j]修改。

算法题总结

第一题

268. 缺失数字

解法一：数字求和

解法二：位运算-异或

解法三：排序

解法四：二分

解法五：排序

解法六：哈希表

第二题

49.字母异位词分组

解法一：遍历strs

解法二：每个字符对应一个ASCII码，使用质数作为乘法因子 【参考题解，方法易理解】

第三题

756.金字塔转换矩阵

解法：深度优先遍历

charAt（）方法的使用

substring（）方法的使用

Map.getOrDefault(Object key, V defaultValue)方法

第四题

130.被围绕的区域

解法：深度优先搜索。

第五题

64.最小路径和

解法：动态规划

不建立dp矩阵，直接遍历grid[i][j]修改。

解法二：每个字符对应一个ASCII码，使用质数作为乘法因子【参考题解，方法易理解】