LeetCode(Easy)-17/1/10

461. Hamming Distance

  • 题意：两个数字的二进制有多少位不同
  • 思路：判断x^y的二进制结果有多少个1
1
2
3
4
5
6
7
public int hammingDistance(int x, int y) {
        int xor = x ^ y;
        int sum = 0;
        for(int i = 0;i<=31;i++)
            sum +=(xor >> i) & 1;
        return sum;
    }

412. Fizz Buzz

  • 题意：3的倍数输出Fizz，5的倍数输出Buzz，既是3的倍数也是5的倍数输出FizzBuzz
  • 思路：先判断既是3和5的倍数的情况

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public List<String> fizzBuzz(int n) {
	List<String> ans = new ArrayList<String>();
		for(Integer i = 1;i <= n;i++){
			if(i%3==0 && i%5==0)
				ans.add("FizzBuzz");
			else if(i%3==0)
				ans.add("Fizz");
			else if(i%5==0)
				ans.add("Buzz");
			else
				ans.add(i.toString());
			}
		return ans;
}

344. Reverse String

  • 题意：反转一个字符串
  • 思路：递归翻转，每次将字符串分半

代码

1
2
3
4
5
public String reverseString(String s){
		if(s.length()<=1)
			return s;
		return reverseString(s.substring(s.length()/2,s.length())) + reverseString(s.substring(0,s.length()/2));
}

463. Island Perimeter

  • 题意：给一个01矩阵，1代表陆地，0代表海，问需要多少围栏将陆地围成一块
  • 思路：遍历矩阵，假设一个1需要4个围栏，判断每个1四周是否为1，为1则减去一个围栏

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public class Solution {
    public int islandPerimeter(int[][] grid) {
        int ans = 0;
        int x;
        int y;
        int[][] dir= new int[][]{{1,0},{0,1},{-1,0},{0,-1}};
        for(int i = 0;i<grid.length;i++){
            for(int j =0;j<grid[0].length;j++){
                if(grid[i][j]==1) {
                    int cnt = 4;
                    for (int k = 0; k < 4; k++) {
                        x = i + dir[k][0];
                        y = j + dir[k][1];
                        if (x >= 0 && x < grid.length && y >= 0 && y < grid[0].length) {
                            if (grid[x][y] == 1)
                                cnt--;
                        }
                    }
                    ans+=cnt;
                }
            }
        }
        return ans;
    }
}

448. Find All Numbers Disappeared in an Array

  • 题意：找出数组（1≤a[i]≤n，n = size of array）中没出现的数字
  • 思路：
    1. 开一个数组记录哪些数字出现过
    2. 对每个元素nums[nums[i] -1] = -nums[nums[i]-1]，最后哪个位置的值大于则该下标对应的数字就是没出现过的

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
public List<Integer> findDisappearedNumbers(int[] nums) {
       List<Integer> ret = new ArrayList<Integer>();
       for(int i = 0; i < nums.length; i++) {
           int val = Math.abs(nums[i]) - 1;
           if(nums[val] > 0)
               nums[val] = -nums[val];
       }  
       for(int i = 0; i < nums.length; i++) {
           if(nums[i] > 0)
               ret.add(i+1);
       }
       return ret;
   }

136. Single Number

  • 题意：给定一个整数数组，每个数字都出现两次但有个数字只出现一次，找出这个数字
  • 思路：将数组所有的元素异或一遍，因为两个相同的数字异或的结果为0，0与一个数字异或结果不变

代码

1
2
3
4
5
6
public int singleNumber(int[] nums) {
        int ans = nums[0];
        for(int i = 1;i < nums.length;i++)
            ans^=nums[i];
        return ans;
}

371. Sum of Two Integers

  • 题意：不使用四则运算符实现两个数相加
  • 思路：相同位相加时会进位
  • 例子：7+2
    =0111+0010
    =0101+0100
    =1000+0001
    =1001（9）

代码

1
2
3
4
5
6
7
8
9
10
public int getSum(int a, int b) {
        if(a==0)return b;
        if(b==0)return a;
        while(b!=0){
            int carry = a & b;//找相同位
            a = a ^ b;//找不同位
            b = carry<<1;//进位
        }
        return a;
 }

104. Maximum Depth of Binary Tree

  • 题意：求一棵二叉树的最大深度
  • 思路：递归左右子树的深度，返回最大值

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int maxDepth(TreeNode root) {
        if(root == null)
            return 0;
        int depthLeft = maxDepth(root.left);
        int depthRight = maxDepth(root.right);
        return 1+(depthLeft > depthRight ? depthLeft : depthRight);
    }
}

389. Find the Difference

  • 题意：给两个只包含小写的字符串，第二个字符串是在第一字符串随机洗乱后再随机插入一个字符，找出这个字符
  • 思路：
  1. 两个数组记录每个字符串中小写字母出现的次数
  2. 通过异或运算

代码

1
2
3
4
5
6
7
8
9
public char findTheDifference(String s, String t) {
	int n = t.length();
	char c = t.charAt(n - 1);
	for (int i = 0; i < n - 1; ++i) {
		c ^= s.charAt(i);
		c ^= t.charAt(i);
	}
	return c;
}

258. Add Digits

  • 题意：给一个数反复的将每位数相加，直到结果为一位数（38->3+8=11->1+1=2）
  • 思路：
  1. 递归求解
  2. （100a+10b+c）%9 = (a+99a+b+9b+c)%9=(a+b+c)%9

代码

1
2
3
public int addDigits(int num) {
        return num==0?0:(num%9==0?9:(num%9));
}

留言

2017-01-10
⬆︎TOP