【算法】LeetCode刷题记录 Part.01

在这里记录下我的LeetCode刷题记录

1.两数之和

给定一个整数数列,找出其中和为特定值的那两个数。
你可以假设每个输入都只会有一种答案,同样的元素不能被重用。

示例

给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

解题思路

每个数都在其后面寻找一遍有没有合适的,有则确定答案。

代码

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] arr = new int[2];
        for(int i=0;i<nums.length;i++){
            for (int j=i+1;j<nums.length;j++){
                if ( nums[i]+nums[j] ==target){
                    arr[0]=i;
                    arr[1]=j;
                }
            }
        }
        return arr;
    }
}

7.颠倒整数

给定一个范围为 32 位 int 的整数,将其颠倒。

示例

例 1:

输入: 123
输出: 321

例 2:

输入: -123
输出: -321

例 3:

输入: 120
输出: 21

注意:
假设我们的环境只能处理 32 位 int 范围内的整数。根据这个假设,如果颠倒后的结果超过这个范围,则返回 0。

解题思路

本体难点在于超过32位int的范围时,返回0

解决方法 如果当前的tmp/10与tmp不等,则说明已经超过int范围,于是直接返回0 (超过取值范围从负从新开始)

代码

class Solution {
    public int reverse(int x) {
        int result = 0;
        while (x != 0) {

            int tmp = result * 10 + x % 10;

            if (tmp / 10 != result) {
                return 0;
            }

            result = tmp;

            x = x / 10;
        }

        return result;
    }
}

292.Nim游戏

您和您的朋友,两个人一起玩 Nim游戏:桌子上有一堆石头,每次你们轮流拿掉 1 到 3 块石头。 拿掉最后一块石头的人就是胜利者。由您来开局。

你们两个都是聪明人,相信都有最佳的游戏策略。 请编写一个函数,来判断您是否可以在给定的石头数量的情况下赢得游戏。

比方说,如果堆中有4块石头,那么你永远不会赢得比赛:无论你拿走的是 1块,2块 还是 3块 石头,最后一块石头总是会被你的朋友拿走。

解题思路

本题看上去难,实际上是数学问题,观察可以发现,由于双方都很聪明,若1 2 3三种情况,则我必赢, 4 的情况下,不管怎样拿,都是输,5 6 7 三种情况,必赢。8 时则我必输…

通过这样可以发现,只有为4的倍数时我会输,其他情况必赢

所以只用判断n是否是4的倍数

代码

class Solution {
    public boolean canWinNim(int n) {
        return n % 4 != 0;
    }
}

344.反转字符串

请编写一个函数,其功能是将输入的字符串反转过来。

示例

输入:s = "hello"
返回:"olleh"

解题思路

只用把得到的字符串从后往前,每次在StringBuffer后接上当前字符就好

不过有个比较坑的地方是,如果不用StringBuffer或StringBuilder,直接用String+=这种形式的话,会超时

因为StringBuffer耗时最少,所以选择StringBuffer

代码

class Solution {
     public String reverseString(String s) {
        StringBuffer result = new StringBuffer();
        for (int i=s.length()-1;i>=0;i--){
            result.append(s.charAt(i));
        }
        return result.toString();
    }
}

461.汉明距离

两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。

给出两个整数 x 和 y,计算它们之间的汉明距离。

示例

输入: x = 1, y = 4

输出: 2

解释:
1   (0 0 0 1)
4   (0 1 0 0)
       ↑   ↑

上面的箭头指出了对应二进制位不同的位置。

解题思路

每次把一个数%2,即可得到它的当前二进制的最低位,每次比较两个数的最低位,然后两个数/2到下一位,即可得出结果

代码

class Solution {
    public int hammingDistance(int x, int y) {
        int result = 0;
        while(x!=0 || y!=0){
            if (x%2 != y%2){
                result++;
            }
            x/=2; y/=2;
        }
        return result;
    }
}

728.自除数

自除数 是指可以被它包含的每一位数除尽的数。

例如,128 是一个自除数,因为 128 % 1 == 0,128 % 2 == 0,128 % 8 == 0。

还有,自除数不允许包含 0 。

给定上边界和下边界数字,输出一个列表,列表的元素是边界(含边界)内所有的自除数。

示例

输入: 
上边界left = 1, 下边界right = 22
输出: [1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 15, 22]

注意:
每个输入参数的边界满足 1 <= left <= right <= 10000。

解题思路

用了一个比较蠢的办法,就不解释了

代码

class Solution {
   public List<Integer> selfDividingNumbers(int left, int right) {
        List<Integer> result = new ArrayList<>();
        for (int n=left;n<=right;n++){
            boolean flag = true;
            int num = n;
            while (num>0){
                if (num%10 == 0){
                    flag = false;
                    break;
                }
                if(n % (num%10) != 0) flag = false;
                num /= 10;
            }
            if (flag == true)
                result.add(n);
        }
        return result;
    }
}

557.反转字符串中的单词 III

给定一个字符串,你需要反转字符串中每个单词的字符顺序,同时仍保留空格和单词的初始顺序。

示例

输入: "Let's take LeetCode contest"
输出: "s'teL ekat edoCteeL tsetnoc" 

解题思路

把字符串按空格分成几个字符串,然后挨个倒序,最后把每个后面加空格加到最后一个中

一个比较坑的地方,输出样例最后一个字母后是没有空格的,所以代码中手动删去了这个空格。

代码

class Solution {
    public String reverseWords(String s) {
        StringBuffer result = new StringBuffer();
        String [] arr = s.split("\\s+");
        for (String str:arr){
            StringBuffer stringBuffer = new StringBuffer();
            for (int i=str.length()-1;i>=0;i--){
                stringBuffer.append(str.charAt(i));
            }
            stringBuffer.append(" ");
            result.append(stringBuffer);
        }
        result.deleteCharAt(result.length()-1);
        return result.toString();
    }
}

561.数组拆分 I

给定长度为 2n 的数组, 你的任务是将这些数分成 n 对, 例如 (a1, b1), (a2, b2), …, (an, bn) ,使得从1 到 n 的 min(ai, bi) 总和最大。

示例

输入: [1,4,3,2]

输出: 4
解释: n 等于 2, 最大总和为 4 = min(1, 2) + min(3, 4).

解题思路

看起来比较复杂,观察规律后可发现只用把这些数排序一次后把奇数个的数加起来就好
如 1 2 3 4 的结果是 1+3=4

代码

class Solution {
    public int arrayPairSum(int[] nums) {
        int sum = 0;
        Arrays.sort(nums);
        for (int i=0;i<nums.length;i+=2){
            sum += nums[i];
        }
        return sum;
    }
}

657.判断路线成圈

初始位置 (0, 0) 处有一个机器人。给出它的一系列动作,判断这个机器人的移动路线是否形成一个圆圈,换言之就是判断它是否会移回到原来的位置。

移动顺序由一个字符串表示。每一个动作都是由一个字符来表示的。机器人有效的动作有 R(右),L(左),U(上)和 D(下)。输出应为 true 或 false,表示机器人移动路线是否成圈。

示例

输入: "UD"
输出: true

输入: "LL"
输出: false

解题思路

用x y两个变量来记录当前坐标
每次向北则是y+1 向南则是y-1 向东是x+1 向西是x-1
这样,遍历字符串,最后得到了它最后的位置,如果是0,0 说明成了圈

代码

class Solution {
    public boolean judgeCircle(String moves) {
        int x = 0,y = 0;
        for (int i=0;i<moves.length();i++){
            if (moves.charAt(i) == 'U') y++;
            if (moves.charAt(i) == 'D') y--;
            if (moves.charAt(i) == 'R') x++;
            if (moves.charAt(i) == 'L') x--;
        }
        if (x == 0 && y == 0){
            return true;
        }else{
            return false;
        }
    }

}

771.宝石与石头

给定字符串J 代表石头中宝石的类型,和字符串 S代表你拥有的石头。 S 中每个字符代表了一种你拥有的石头的类型,你想知道你拥有的石头中有多少是宝石。

J 中的字母不重复,J 和 S中的所有字符都是字母。字母区分大小写,因此”a”和”A”是不同类型的石头。

示例

输入: J = "aA", S = "aAAbbbb"
输出: 3

输入: J = "z", S = "ZZ"
输出: 0

解题思路

两层循环,外层遍历前面的字符串,每次获取到宝石的字符都在后面的字符串寻找,找到则结果加一

代码

class Solution {
     public int numJewelsInStones(String J, String S) {
        int num = 0;
        for (int i=0;i<J.length();i++){
            char ch = J.charAt(i);
            for (int j=0;j<S.length();j++){
                if (ch == S.charAt(j)){
                    num++;
                }
            }
        }
        return num;
    }
}

500.键盘行

给定一个单词列表,只返回可以使用在键盘同一行的字母打印出来的单词。键盘如下图所示。
Keyboard

示例

输入: ["Hello", "Alaska", "Dad", "Peace"]
输出: ["Alaska", "Dad"]

解题思路

遍历字符串,每次个字符串先找到第一个字母所在行,若后面的字母都在该行,则结果List中加入该行

代码

class Solution {
    public String[] findWords(String[] words) {
        String[] lines ={ "QWERTYUIOPqwertyuiop",
         "ASDFGHJKLasdfghjkl",
         "ZXCVBNMzxcvbnm"};
        List<String> result = new ArrayList<>();
        for (String str:words){
            int index=0;
            boolean flag = true;
            for (int i=0;i<lines.length;i++){
                if (lines[i].indexOf(str.charAt(0))!=-1) index=i;
            }
            for (int i=1;i<str.length();i++){
                char ch = str.charAt(i);
                for (int j=0;j<lines.length;j++){
                    if (lines[j].indexOf(ch)!=-1){
                        if (j!=index){
                            flag = false;
                        }
                    }
                }
            }
            if (flag) result.add(str);
        }
        String[] str = new String[result.size()];
        for (int i=0;i<result.size();i++){
            str[i] = (String)result.get(i);
        }
        return str;
    }
}

806.写字符串需要的行数

我们要把给定的字符串 S 从左到右写到每一行上,每一行的最大宽度为100个单位,如果我们在写某个字母的时候会使这行超过了100 个单位,那么我们应该把这个字母写到下一行。我们给定了一个数组 widths ,这个数组 widths[0] 代表 ‘a’ 需要的单位, widths[1] 代表 ‘b’ 需要的单位,…, widths[25] 代表 ‘z’ 需要的单位。

现在回答两个问题:至少多少行能放下S,以及最后一行使用的宽度是多少个单位?将你的答案作为长度为2的整数列表返回。

示例

输入: 
widths = [10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10]
S = "abcdefghijklmnopqrstuvwxyz"
输出: [3, 60]
解释: 
所有的字符拥有相同的占用单位10。所以书写所有的26个字母,
我们需要2个整行和占用60个单位的一行。


输入: 
widths = [4,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10]
S = "bbbcccdddaaa"
输出: [2, 4]
解释: 
除去字母'a'所有的字符都是相同的单位10,并且字符串 "bbbcccdddaa"     将会覆盖 9 * 10 + 2 * 4 = 98 个单位.
最后一个字母 'a' 将会被写到第二行,因为第一行只剩下2个单位了。
所以,这个答案是2行,第二行有4个单位宽度。

解题思路

只用遍历字符串,则当前的字符在widths数组中的索引即为该字符减去’a’字符所得的值

用索引获取该字符宽度,若宽度能放入,则该行宽度加上该字符宽度,不能则换行,行数++,行宽度清零并加上该字符宽度。

代码

class Solution {
    public int[] numberOfLines(int[] widths, String S) {
        int line = 1,weightNum = 0;
        for (int i=0;i<S.length();i++){
            int index = S.charAt(i)-'a';
            int weight = widths[index];
            if (weightNum + weight<=100){
                weightNum+=weight;
            }else{
                line++;
                weightNum = weight;
            }
        }
        int[] result = new int[2];
        result[0] = line;
        result[1] = weightNum;
        return result;
    }
}

171.Excel表列序号

给定一个Excel表格中的列名称,返回其相应的列序号。

示例

A -> 1
B -> 2
C -> 3
...
Z -> 26
AA -> 27
AB -> 28 

解题思路

遍历字符串,每找到一个字符,sum都相当于它乘以26再加上当前字母的序列

代码

class Solution {
    public int titleToNumber(String s) {
        int sum = 0;  
        int tmp = 0;  
        for (int i = 0; i < s.length(); ++i) {  
            tmp = s.charAt(i)- 'A' + 1;  
            sum = 26 * sum + tmp;  
        }  
        return sum;  
    }
}

766.托普利茨矩阵

如果一个矩阵的每一方向由左上到右下的对角线上具有相同元素,那么这个矩阵是托普利茨矩阵。

给定一个 M x N 的矩阵,当且仅当它是托普利茨矩阵时返回 True。

示例

输入: matrix = [[1,2,3,4],[5,1,2,3],[9,5,1,2]]
输出: True
解释:
1234
5123
9512

在上面这个矩阵中, 对角线分别是 "[9]", "[5, 5]", "[1, 1, 1]", "[2, 2, 2]", "[3, 3]", "[4]", 各条对角线上的所有元素都相同, 因此答案是True。

输入: matrix = [[1,2],[2,2]]
输出: False
解释: 
对角线, 比如: "[1, 2]" 上有不同的元素。

解题思路

遍历每个元素,判断与右下角的是否相同,不同直接return false

代码

class Solution {
    public boolean isToeplitzMatrix(int[][] matrix) {
        for (int i=0;i<matrix.length-1;i++){
            for (int j=0;j<matrix[0].length-1;j++){
                if (matrix[i][j] != matrix[i+1][j+1]) return false;
            }
        }
        return true;
    }
}

566.重塑矩阵

在MATLAB中,有一个非常有用的函数 reshape,它可以将一个矩阵重塑为另一个大小不同的新矩阵,但保留其原始数据。

给出一个由二维数组表示的矩阵,以及两个正整数r和c,分别表示想要的重构的矩阵的行数和列数。

重构后的矩阵需要将原始矩阵的所有元素以相同的行遍历顺序填充。

如果具有给定参数的reshape操作是可行且合理的,则输出新的重塑矩阵;否则,输出原始矩阵。

示例

输入: 
nums = 
[[1,2],
 [3,4]]
r = 1, c = 4
输出: 
[[1,2,3,4]]
解释:

行遍历nums的结果是 [1,2,3,4]。新的矩阵是 1 * 4 矩阵, 用之前的元素值一行一行填充新矩阵。


输入: 
nums = 
[[1,2],
 [3,4]]
r = 2, c = 4
输出: 
[[1,2],
[3,4]]
解释:
没有办法将 2 * 2 矩阵转化为 2 * 4 矩阵。 所以输出原矩阵。

解题思路

无法转化的是由于要转化的矩阵的元素个数比原来更多(如2 * 4>2 * 2)

所以如果元素个数比原来多的直接return原来的矩阵。

可以转化的就把原来的矩阵转化为一维,然后依次赋值到新的矩阵。

代码

class Solution {
    public int[][] matrixReshape(int[][] nums, int r, int c) {
        if (nums.length*nums[0].length < r*c){
            return nums;
        }
        int[] arr = new int[nums.length*nums[0].length];
        int temp = 0;
        for (int i=0;i<nums.length;i++){
            for (int j=0;j<nums[0].length;j++){
                arr[temp] = nums[i][j];
                temp++;
            }
        }
        int[][] result = new int[r][c];
        temp = 0;
        for (int i = 0 ;i<r;i++){
            for (int j = 0;j<c;j++){
                result[i][j] = arr[temp];
                temp++;
            }
        }
        return result;
    }
}

575.分糖果

给定一个偶数长度的数组,其中不同的数字代表着不同种类的糖果,每一个数字代表一个糖果。你需要把这些糖果平均分给一个弟弟和一个妹妹。返回妹妹可以获得的最大糖果的种类数。

示例

输入: candies = [1,1,2,2,3,3]
输出: 3
解析: 一共有三种种类的糖果,每一种都有两个。
最优分配方案:妹妹获得[1,2,3],弟弟也获得[1,2,3]。这样使妹妹获得糖果的种类数最多。

输入: candies = [1,1,2,3]
输出: 2
解析: 妹妹获得糖果[2,3],弟弟获得糖果[1,1],妹妹有两种不同的糖果,弟弟只有一种。这样使得妹妹可以获得的糖果种类数最多。

解题思路

可以发现,如果妹妹可以拿的糖果数量比糖果种类数量多,则可以把每种糖果都拿完,如果少的话,只能拿走她能拿的个数种糖果
所以,只用找出糖果的种类数,并与糖果个数的一半(妹妹能拿的糖果数比较即可)

代码

class Solution {
    public int distributeCandies(int[] candies) {
        int num = candies.length/2;
        Map<Integer,Boolean> map = new HashMap<>();
        for (int i=0;i<candies.length;i++){
            if (!map.containsKey(candies[i])){
                map.put(candies[i],true);
            }
        }
        return map.size()>num?num:map.size();
    }
}

476.数字的补数

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

注意:

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

示例

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


输入: 1
输出: 0
解释: 1的二进制表示为1(没有前导零位),其补数为0。所以你需要输出0。

解题思想

异或可以用于取反,只用获得该数的二进制位数,弄出一个二进制和这个位数相同的全是1的数,与原数异或,便可得到答案

代码

class Solution {
    public int findComplement(int num) {
        int bitsNum = 0;
        int n = num;
        while (n != 0) {
            ++bitsNum ;
            n >>= 1 ;
        }
        n = (1<<bitsNum)-1;
        return num ^ n;
    }
}

463.岛屿的周长

给定一个包含 0 和 1 的二维网格地图,其中 1 表示陆地 0 表示水域。网格中的格子水平和垂直方向相连(对角线方向不相连)。整个网格被水完全包围,但其中恰好有一个岛屿(或者说,一个或多个表示陆地的格子相连组成的岛屿)。岛屿中没有“湖”(“湖” 指水域在岛屿内部且不和岛屿周围的水相连)。格子是边长为 1 的正方形。网格为长方形,且宽度和高度均不超过 100 。计算这个岛屿的周长。

示例
[[0,1,0,0],
[1,1,1,0],
[0,1,0,0],
[1,1,0,0]]

答案: 16
解释: 它的周长是下面图片中的 16 个黄色的边:

image

解题思路

遍历地图,从第一个方块开始一层层向下搜索,每个1的方块都向四个方向判断,四个方向有几个1,它的周长就减去几,这些方块的周长的和即为岛屿的周长

代码

class Solution {
   public int islandPerimeter(int[][] grid) {

        int C = 0;
        for (int i=0;i<grid.length;i++){
            for (int j=0;j<grid[0].length;j++){
                if (grid[i][j] == 1){
                    int n = 4;
                    if (j-1>=0&&grid[i][j-1] == 1) n--;
                    if (j+1<grid[0].length&&grid[i][j+1] == 1) n--;
                    if (i-1>=0&&grid[i-1][j] == 1) n--;
                    if (i+1<grid.length&&grid[i+1][j] == 1) n--;
                    C += n;
                }
            }
        }
        return C;
    }
}

412.Fizz Buzz

写一个程序,输出从 1 到 n 数字的字符串表示。

  1. 如果 n 是3的倍数,输出“Fizz”;

  2. 如果 n 是5的倍数,输出“Buzz”;

  3. 如果 n 同时是3和5的倍数,输出 “FizzBuzz”。

示例

n = 15,

返回:
[
    "1",
    "2",
    "Fizz",
    "4",
    "Buzz",
    "Fizz",
    "7",
    "8",
    "Fizz",
    "Buzz",
    "11",
    "Fizz",
    "13",
    "14",
    "FizzBuzz"
]

解题思路

过于简单,不解释了

代码

class Solution {
    public List<String> fizzBuzz(int n) {
        List<String> result = new ArrayList<>();
        for (int i=1;i<=n;i++){
            if (i%3 == 0 && i%5 != 0) result.add("Fizz");
            else if (i%3 != 0 && i%5 == 0) result.add("Buzz");
            else if (i%3 == 0 && i%5 == 0) result.add("FizzBuzz");
            else result.add(String.valueOf(i));
        }
        return result;
    }
}

485.最大连续1的个数

给定一个二进制数组, 计算其中最大连续1的个数。

示例

输入: [1,1,0,1,1,1]
输出: 3
解释: 开头的两位和最后的三位都是连续1,所以最大连续1的个数是 3.

解题思路

把每段1的长度都弄进List中,最后在这个List中找最大值

代码

class Solution {
    public int findMaxConsecutiveOnes(int[] nums) {
        List<Integer> arr = new ArrayList<>();
        int temp = 0;
        for (int i=0;i<nums.length;i++){
            if (nums[i] == 0){
                arr.add(temp);
                temp = 0;
            }else temp++;
        }
        arr.add(temp);
        return Collections.max(arr);
    }
}

283.移动零

给定一个数组 nums, 编写一个函数将所有 0 移动到它的末尾,同时保持非零元素的相对顺序。

例如, 定义 nums = [0, 1, 0, 3, 12],调用函数之后, nums 应为 [1, 3, 12, 0, 0]。

注意事项:

  1. 必须在原数组上操作,不要为一个新数组分配额外空间。
  2. 尽量减少操作总数。

示例

解题思路

遍历数组,将非0的全部放到前面,再把剩下的位置填上0

代码

class Solution {
    public void moveZeroes(int[] nums) {
        int n = 0;
        for (int i=0;i<nums.length;i++){
            if (nums[i] != 0)   nums[n++] = nums[i];
        }
        for (int j=n;j<nums.length;j++){
            nums[j] = 0;
        }
    }
}

258.各位数

给一个非负整数 num,反复添加所有的数字,直到结果只有一个数字。

例如:

设定 num = 38,过程就像: 3 + 8 = 11, 1 + 1 = 2。 由于 2 只有1个数字,所以返回它。

示例

解题思路

用递归的方式,直到只有一位
遇到特殊值0则直接返回0

代码

public int addDigits(int num) {
        int sum=0,bit=0,n=num;
        if (num == 0) return 0;
        while (n != 0){
            sum += n%10;
            n/=10;
            bit++;
        }
        if (bit == 1) return num;
        else return addDigits(sum);
    }

520.检测大写字母

给定一个单词,你需要判断单词的大写使用是否正确。

我们定义,在以下情况时,单词的大写用法是正确的:

全部字母都是大写,比如”USA”。
单词中所有字母都不是大写,比如”leetcode”。
如果单词不只含有一个字母,只有首字母大写, 比如 “Google”。
否则,我们定义这个单词没有正确使用大写字母。

示例

输入: "USA"
输出: True

输入: "FlaG"
输出: False

解题思路

通过前两个字母判断它是哪种情况,并进行相应的判断

需要注意的是比较坑的数据

单个字母。直接返回true

如果第一个是小写,第二个是大写,就直接返回false

代码

class Solution {
    public boolean detectCapitalUse(String word) {
        int status = 0; //0:全小写 1:全大写 2:首字母大写
        if (word.length() == 1) return true;

        if (word.charAt(0)>= 'A' && word.charAt(0) <='Z')
            if (word.charAt(1)>= 'A' && word.charAt(1) <='Z') status = 1;
            else status = 2;
        else {
            if (word.charAt(1)>= 'A' && word.charAt(1) <='Z') return false;
            status = 2;
        }

        boolean result = true;

        for (int i=2;i<word.length();i++){
            switch (status){
                case 0:
                    if (word.charAt(i)>= 'A' && word.charAt(i) <='Z') result = false;
                    break;
                case 1:
                    if (word.charAt(i)>= 'a' && word.charAt(i) <='z') result = false;
                    break;
                case 2:
                    if (word.charAt(i)>= 'A' && word.charAt(i) <='Z') result = false;
            }
        }
        return result;
    }
}

本部分完结

N0tExpectErr0r

N0tExpectErr0r

一名热爱代码的 Android 开发者

留下你的评论

*评论支持代码高亮<pre class="prettyprint linenums">代码</pre>

相关推荐

暂无内容!