LeetCode(Easy)-17/1/11

476. Number Complement

  • 题意：二进制翻转
  • 思路：
  1. 暴力将每一位为0的对应的2的乘方加起来
  2. ~num & ((Integer.highestOneBit(num) << 1) - 1);highestOneBit(num)：获取长整数二进制最高位1的索引

代码

1
2
3
public int findComplement(int num) {
        return ~num & ((Integer.highestOneBit(num) << 1) - 1);
}

283. Move Zeroes

  • 题意：在不开新数组的情况下将一个数组的0移到最后
  • 思路：没什么好说的( ⊙ o ⊙ )

代码

1
2
3
4
5
6
7
8
9
public void moveZeroes(int[] nums) {
        int index = 0;
        for(int i = 0;i<nums.length;i++){
            if(nums[i] != 0)
                nums[index++]=nums[i];
        }
        for(;index<nums.length;index++)
            nums[index] = 0;
}

392. Is Subsequence

  • 题意：判断一个字符串是不是另一个字符串的子序列
  • 思路：暴力判断字符串的每个字符

代码

1
2
3
4
5
6
7
8
9
10
11
public boolean isSubsequence(String s, String t) {
        int i = 0;
        for(int j = 0;i<s.length() && j<t.length();j++){
            if(s.charAt(i)==t.charAt(j))
                i++;
        }
        if(i!=s.length())
            return false;
        else
            return true;
}

383. Ransom Note

  • 题意：判断一个字符串中的字符能不能构成另一个字符串的部分字符
  • 思路：判断字符串出现次数

代码

1
2
3
4
5
6
7
8
9
public boolean canConstruct(String ransomNote, String magazine) {
        int[] vis = new int[26];
        for(int i = 0;i < magazine.length();i++)
            vis[magazine.charAt(i)-'a']++;
        for(int i = 0;i < ransomNote.length();i++)
            if(--vis[ransomNote.charAt(i)-'a'] < 0)
                return false;
        return true;
 }

404. Sum of Left Leaves

  • 题意：求一棵二叉树的所有左叶子的和
  • 思路：递归左右子树，当一个点有左节点且左节点是叶子节点时返回该左节点的值

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
public int sumOfLeftLeaves(TreeNode root) {
        if(root==null)
            return 0;
        int ans = 0;
        if(root.left!=null){//有左孩子
            if(root.left.left == null && root.left.right == null)//该节点是叶子节点
                ans += root.left.val;
            else//递归下去
                ans += sumOfLeftLeaves(root.left);
        }
        ans+=sumOfLeftLeaves(root.right);//递归右孩子
        return ans;
}

237. Delete Node in a Linked List

  • 题意：删除链表指定的一个节点
  • 思路：将该节点的val指向下一个，next指向下一个的下一个

代码

1
2
3
4
public void deleteNode(ListNode node) {
        node.val = node.next.val;
        node.next = node.next.next;
}

349. Intersection of Two Arrays

  • 题意：计算两个数组的交集，所求集合中的元素唯一
  • 思路：将第一个数组放入Set1，第二个数组放入Set2时，判断数组中的每个数字是否在Set1中，是的话就放入Set2

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int[] intersection(int[] nums1, int[] nums2) {
        Set<Integer> set1 = new HashSet<Integer>();
        Set<Integer> set2 = new HashSet<Integer>();
        for(int i = 0;i <nums1.length;i++)
            set1.add(nums1[i]);
        for(int i = 0;i < nums2.length;i++){
            if(set1.contains(nums2[i]))
                set2.add(nums2[i]);
        }
        int[] ans = new int[set2.size()];
        int i = 0;
        for(Integer num : set2)
            ans[i++] = num;
        return ans;
}

387. First Unique Character in a String

  • 题意：从左到右找出一个字符串中第一个不重复的字符的下标，不存在返回-1
  • 思路：遍历字符串，判断s.indexOf(str[i])==s.lastIndexOf(str[i])

代码

1
2
3
4
5
6
7
public int firstUniqChar(String s) {
        char[] str = s.toCharArray();
        for(int i = 0; i < str.length;i++)
            if(s.indexOf(str[i])==s.lastIndexOf(str[i]))
                return i;
        return -1;
}

171. Excel Sheet Column Number

  • 题意：将excel sheet的列转出十进制，A->1,AA->27,AB->28
  • 思路：就是将26进制转成十进制

代码

1
2
3
4
5
6
public int titleToNumber(String s) {
        int ans = 0;
        for(int i = 0;i < s.length();i++)
            ans = ans*26 + (s.charAt(i)-'A'+1);
        return ans;
}

100. Same Tree

  • 题意：判断两个二叉树是否一样（节点一致，节点值一致）
  • 思路：递归判断左右子树

代码

1
2
3
4
5
6
7
public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p==null && q==null) return true;//左或右结构一致，都为空
        if(p==null || q==null) return false;//左右结构不一致，一个为空一个不为空
        if(p.val==q.val)
            return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
        return false;
    }

242. Valid Anagram

  • 题意：判断构成两个字符串的字符是否一样
  • 思路：一个数组记录第一个字符串的字符出现的次数，遍历第二个字符串，将字符对应的数组的值-1，如果数组中的值有不为0的情况，则说明不一样

代码

1
2
3
4
5
6
7
public boolean isAnagram(String s, String t) {
        int[] alphabet = new int[26];
        for (int i = 0; i < s.length(); i++) alphabet[s.charAt(i) - 'a']++;
        for (int i = 0; i < t.length(); i++) alphabet[t.charAt(i) - 'a']--;
        for (int i : alphabet) if (i != 0) return false;
        return true;
}

169. Majority Element

  • 题意：有一个数组，其中某个数字至少出现了n/2次，找出这个数字
  • 思路：将数组排序，则这个数字一定出现在n/2+1的位置

代码

1
2
3
4
public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length/2];
}

留言

2017-01-12
⬆︎TOP