202012leetcode刷题记录

技术文章 11个月前 完美者
1,515 0

标签:哈希   false   nta   leetcode   字符型   flag   turn   lan   idm   

73. 矩阵置零

题目要求:
给定一个m x n的矩阵,如果一个元素为 0,则将其所在行和列的所有元素都设为 0。请使用原地算法。

思路:
由于需要用到原地的算法,因此需要想办法对含0的行列进行标记。当矩阵中的某个元素为0时,则将其所在行和列的第一个元素置零作为标记。而matrix[0][0]同时成为了第一行和第一列的标记,因此需要另开一个布尔变量用于标记第一列是否含有0。

class Solution {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        boolean flag = false;
        for (int i = 0; i < m; i++) {
            if (matrix[i][0] == 0){
                flag = true;
            }
            for (int j = 1; j < n; j++) {
                if (matrix[i][j] == 0){
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }
        
        // 把标记的行和列都置零
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0;
                }
            }
        }
        
        // 如果matrix[0][0]为零,则需要将第一行置零
        // 再判断是否需要将第一列置零
        if(matrix[0][0] == 0){
            for (int i = 0; i < n; i++) {
                matrix[0][i] = 0;
            }
        }
        
        if (flag){
            for (int i = 0; i < m; i++) {
                matrix[i][0] = 0;
            }
        }
    }
}

150. 逆波兰表达式求值

题目要求:
根据 逆波兰表示法,求表达式的值。有效的运算符包括+, -, *, /。每个运算对象可以是整数,也可以是另一个逆波兰表达式。

思路:
用栈。

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        stack = []
        for x in tokens:
            if x not in "+-*/":
                stack.append(int(x))
            else:
                tmp = stack.pop()
                if x == ‘+‘:
                    stack[-1] += tmp
                elif x == ‘-‘:
                    stack[-1] -= tmp
                elif x == ‘*‘:
                    stack[-1] *= tmp
                else:
                    stack[-1] = int(stack[-1]/tmp)
        
        return stack[0]

290. 单词规律

题目要求:
给定一种规律 pattern 和一个字符串 str ,判断 str 是否遵循相同的规律。

这里的 遵循 指完全匹配,例如, pattern 里的每个字母和字符串 str 中的每个非空单词之间存在着双向连接的对应规律。

思路:
本题要求pattern中的字母与str中的单词要一一对应,因此用两个哈希表来表示它们之间的一一对应关系。每次对比字母和单词是否对应后就更新这两个哈希表,以免出现aaaadog cat cat dog相匹配的情况。

class Solution {
    public boolean wordPattern(String pattern, String s) {
        Map<String, Character> word2ch = new HashMap<String, Character>();
        Map<Character, String> ch2word = new HashMap<Character, String>();
        String[] strArr = s.split(" ");
        int n = pattern.length();
        if(n != strArr.length){
            return false;
        }

        for (int i = 0; i < n; i++){
            char ch = pattern.charAt(i);
            String word = strArr[i];
            if (word2ch.containsKey(word) && !word2ch.get(word).equals(ch)){
                return false;
            }
            if (ch2word.containsKey(ch) && !ch2word.get(ch).equals(word)){
                return false;
            }
            word2ch.put(word, ch);
            ch2word.put(ch, word);
        }
        return true;
    }
}
class Solution:
    def wordPattern(self, pattern: str, s: str) -> bool:
        strArr = s.split(" ")
        if len(pattern) != len(strArr):
            return False
        word2ch = {}
        ch2word = {}

        for ch, word in zip(pattern, strArr):
            if (word in word2ch and word2ch[word] != ch) or (ch in ch2word and ch2word[ch] != word):
                return False
            word2ch[word] = ch
            ch2word[ch] = word

        return True

389. 找不同

题目要求:
给定两个字符串 s 和 t,它们只包含小写字母。

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

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

思路一:
由于t中的字符只比s多一个小写字母,因此只要给字符计数就可以找到多出的那个小写字母。用一个数组cnt来给字符串s中出现的字符计数,接着遍历字符串t,没出现一次就把cnt对应位置的计数减一,知道某个位置的计数变为-1,说明就是这个字符多出来一个。

class Solution {
    public char findTheDifference(String s, String t) {
        int[] cnt = new int[26];
        int n = s.length();
        for (int i = 0; i < n; i++) {
            cnt[s.charAt(i) - ‘a‘] ++;
        }
        for (int i = 0; i < n + 1; i++) {
            char ch = t.charAt(i);
            cnt[ch - ‘a‘] --;
            if(cnt[ch - ‘a‘] < 0){
                return ch;
            }
        }
        return ‘ ‘;
    }
}

思路二:
Java中,字符型是可以根据ASCII码进行加减的。因此分别对两个字符串求和,最后相减就是想要的结果。

class Solution {
    public char findTheDifference(String s, String t) {
        int sums = 0, sumt = 0;
        int n = s.length();
        for (int i = 0; i < n; i++) {
            sums += s.charAt(i);
        }
        for (int i = 0; i < n + 1; i++) {
            sumt += t.charAt(i);
        }
        return (char)(sumt - sums);
    }
}

738. 单调递增的数字

题目要求:
给定一个非负整数 N,找出小于或等于 N 的最大的整数,同时这个整数需要满足其各个位数上的数字是单调递增。

(当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时,我们称这个整数是单调递增的。)

思路:
首先将整型转为字符型数组,遍历这个数组,如果某一位数字比其后一位数字要大,则将其减一,且之后的数字都变为9。然后按照这个流程再检查一遍这个数组。

class Solution {
    public int monotoneIncreasingDigits(int N) {
        if(N < 10){
            return N;
        }
        char[] numbers = Integer.toString(N).toCharArray();
        int i = 0;
        while(i < numbers.length - 1){
            if (numbers[i] <= numbers[i + 1]){
                i ++;
                continue;
            }
            numbers[i]--;
            for (int j = i + 1; j < numbers.length; j ++){
                numbers[j] = ‘9‘;
            }
            // 从头开始再来一遍
            i = 0;
        }
        return Integer.valueOf(new String(numbers));
    }
}

941. 有效的山脉数组

题目要求:
给定一个整数数组A,如果它是有效的山脉数组就返回true,否则返回false

让我们回顾一下,如果A满足下述条件,那么它是一个山脉数组:

  • A.length >= 3
  • 0 < i < A.length - 1条件下,存在i使得:
  • A[0] < A[1] < ... A[i-1] < A[i]
  • A[i] > A[i+1] > ... > A[A.length - 1]

思路:
用双指针分别从头和尾开始查找。

class Solution {
    public boolean validMountainArray(int[] A) {
        int n = A.length;
        if (n < 3){
            return false;
        }
        int left = 0, right = A.length - 1;
        while (left < n - 1 && A[left] < A[left + 1]){
            left++;
        }
        while (right > 1 && A[right] < A[right - 1]){
            right--;
        }
        if(left == 0 || right == n - 1){
            return false;
        }
        return left == right;
    }
}

1365. 有多少小于当前数字的数字

题目要求:
给你一个数组nums,对于其中每个元素nums[i],请你统计数组中比它小的所有数字的数目。换而言之,对于每个nums[i]你必须计算出有效的j的数量,其中j满足j != inums[j] < nums[i]。以数组形式返回答案。

提示:

  • 2 <= nums.length <= 500
  • 0 <= nums[i] <= 100

思路:
暴力求解。对于数组中的每一个元素,都去数组中找到比它小的元素的个数。

class Solution {
    public int[] smallerNumbersThanCurrent(int[] nums) {
        int n = nums.length;
        int[] ans = new int[n];
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                if(nums[j] < nums[i]){
                    ans[i]++;
                }
            }
        }
        return ans;
    }
}

202012leetcode刷题记录

标签:哈希   false   nta   leetcode   字符型   flag   turn   lan   idm   

原文地址:https://www.cnblogs.com/beeblog72/p/14236982.html

版权声明:完美者 发表于 2021-01-07 12:31:31。
转载请注明:202012leetcode刷题记录 | 完美导航

暂无评论

暂无评论...