0%

Bitwise And Array LEETCODE-100-DAY3

Posted on Valine:

66. Plus One

Given a non-empty array of digits representing a non-negative integer, plus one to the integer.

The digits are stored such that the most significant digit is at the head of the list, and each element in the array contain a single digit.

You may assume the integer does not contain any leading zero, except the number 0 itself.

Example 1:

1
2
3
Input: [1,2,3]
Output: [1,2,4]
Explanation: The array represents the integer 123.

Example 2:

1
2
3
Input: [4,3,2,1]
Output: [4,3,2,2]
Explanation: The array represents the integer 4321.
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
//case1 1011 1012
//case2 1099 1100
//case3 9999 10000

//time : O(n)
//space : O(n)在最后开辟了一个新的数组
class Solution {
    public int[] plusOne(int[] digits) {
        if (digits == null || digits.length == 0) return digits;
        for (int i = digits.length - 1; i >= 0; i--) {
            //case 1
            if(digits[i] < 9) {
                digits[i]++;
                return digits;
            } else {
                //case2
                digits[i] = 0;
            }
        }
        //case 3
        int[] res = new int[digits.length + 1];
        res[0] = 1;
        return res;
    }
}

136. Single Number

Given a non-empty array of integers, every element appears twice except for one. Find that single one.

Note:

Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Example 1:

1
2
Input: [2,2,1]
Output: 1

Example 2:

1
2
Input: [4,1,2,1,2]
Output: 4
1
2
3
4
5
6
7
8
9
class Solution {
    public int singleNumber(int[] nums) {
        int res = 0;
        for (int i = 0; i < nums.length; i++) {
            res ^= nums[i];
        }
        return res;
    }
}

🐘异或:相同为0,不同为1

389. Find The Difference

Given two strings s\ and t\ which consist of only lowercase letters.

String t\ is generated by random shuffling string s\ and then add one more letter at a random position.

Find the letter that was added in t\.

Example:

1
2
3
4
5
6
7
8
9
Input:
s = "abcd"
t = "abcde"

Output:
e

Explanation:
'e' is the letter that was added.
1
2
3
4
5
6
7
8
9
10
11
12
//性质：4与6进行异或的结果,再与4进行异或,得到了6.
class Solution {
    public char findTheDifference(String s, String t) {
        //t的长度比s长，所以直接取t的最后一位
        char c = t.charAt(t.length() - 1);
        for (int i = 0; i < s.length(); i++) {
            c ^= s.charAt(i);
            c ^= t.charAt(i);
        }
        return c;
    }
}

性质（1）：4与6进行异或的结果,再与4进行异或,得到了6.

191. Number of 1 Bits

Write a function that takes an unsigned integer and return the number of ‘1’ bits it has (also known as the Hamming weight).

Example 1:

1
2
3
Input: 00000000000000000000000000001011
Output: 3
Explanation: The input binary string 00000000000000000000000000001011 has a total of three '1' bits.

Example 2:

1
2
3
Input: 00000000000000000000000010000000
Output: 1
Explanation: The input binary string 00000000000000000000000010000000 has a total of one '1' bit.

Example 3:

1
2
3
Input: 11111111111111111111111111111101
Output: 31
Explanation: The input binary string 11111111111111111111111111111101 has a total of thirty one '1' bits.

Note:

  • Note that in some languages such as Java, there is no unsigned integer type. In this case, the input will be given as signed integer type and should not affect your implementation, as the internal binary representation of the integer is the same whether it is signed or unsigned.
  • In Java, the compiler represents the signed integers using 2’s complement notation. Therefore, in Example 3 above the input represents the signed integer -3.

Follow up:

If this function is called many times, how would you optimize it?

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
26
27
28
class Solution {
    //dp,前N个数的和就是它的DP值
    public int maxSubArray(int[] nums) {
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        int res = nums[0];
        for(int i = 1; i < nums.length; i++) {
             dp[i] = nums[i] + (dp[i - 1] < 0 ? 0 : dp[i - 1]);
             res = Math.max(res, dp[i]);
        }
        return res;
    }
}
// @lc code=end

// class Solution {
//     //dp,前N个数的和就是它的DP值
//     public int maxSubArray(int[] nums) {
//         int[] dp = new int[nums.length];
//         dp[0] = nums[0];
//         int res = nums[0];
//         for(int i = 1; i < nums.length; i++) {
//              dp[i] = nums[i] + (dp[i - 1] < 0 ? 0 : dp[i - 1]);
//              res = Math.max(res, dp[i]);
//         }
//         return res;
//     }
// }

性质（2）n&(n-1):将n的二进制表示中的最低位为1的改成0（在这里注意重复操作）

231. Power of Two

Given an integer, write a function to determine if it is a power of two.

Example 1:

1
2
3
Input: 1
Output: true 
Explanation: 20 = 1

Example 2:

1
2
3
Input: 16
Output: true
Explanation: 24 = 16

Example 3:

1
2
Input: 218
Output: false
1
2
3
4
5
6
7
8
9
10
11
12
13
// 2 : 10
// 4 : 100
// 8 : 1000
// 16: 10000

// n : 16 10000
// n - 1 : 01111
//如果与的结果都为0,那么就是2的次方倍
class Solution {
    public boolean isPowerOfTwo(int n) {
        return n > 0 && ((n & (n - 1)) == 0);
    }
}

190. Reverse Bits

Reverse bits of a given 32 bits unsigned integer.

Example 1:

1
2
3
Input: 00000010100101000001111010011100
Output: 00111001011110000010100101000000
Explanation: The input binary string 00000010100101000001111010011100 represents the unsigned integer 43261596, so return 964176192 which its binary representation is 00111001011110000010100101000000.

Example 2:

1
2
3
Input: 11111111111111111111111111111101
Output: 10111111111111111111111111111111
Explanation: The input binary string 11111111111111111111111111111101 represents the unsigned integer 4294967293, so return 3221225471 which its binary representation is 10111111111111111111111111111111.

Note:

  • Note that in some languages such as Java, there is no unsigned integer type. In this case, both input and output will be given as signed integer type and should not affect your implementation, as the internal binary representation of the integer is the same whether it is signed or unsigned.
  • In Java, the compiler represents the signed integers using 2’s complement notation. Therefore, in Example 2 above the input represents the signed integer -3 and the output represents the signed integer -1073741825.

Follow up:

If this function is called many times, how would you optimize it?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 1011 右移变成0101
// 0001
//    1
// res = 1

public class Solution {
    // you need treat n as an unsigned value
    public int reverseBits(int n) {
        if (n == 0) return 0;
        int res = 0;
        for (int i = 0; i < 32; i++) {
            res <<= 1;
            //如果是偶数，为0，并且判断最低位是不是1
            if ((n & 1) == 1) res++;
            // 1011 右移变成0101
            n >>= 1;
        }
        return res;
    }
}

27. Remove Element

Given an array nums and a value val, remove all instances of that value in-place and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

The order of elements can be changed. It doesn’t matter what you leave beyond the new length.

Example 1:

1
2
3
4
5
Given nums = [3,2,2,3], val = 3,

Your function should return length = 2, with the first two elements of nums being 2.

It doesn't matter what you leave beyond the returned length.

Example 2:

1
2
3
4
5
6
7
Given nums = [0,1,2,2,3,0,4,2], val = 2,

Your function should return length = 5, with the first five elements of nums containing 0, 1, 3, 0, and 4.

Note that the order of those five elements can be arbitrary.

It doesn't matter what values are set beyond the returned length.

Clarification:

Confused why the returned value is an integer but your answer is an array?

Note that the input array is passed in by reference, which means modification to the input array will be known to the caller as well.

Internally you can think of this:

1
2
3
4
5
6
7
8
// nums is passed in by reference. (i.e., without making a copy)
int len = removeElement(nums, val);

// any modification to nums in your function would be known by the caller.
// using the length returned by your function, it prints the first len elements.
for (int i = 0; i < len; i++) {
    print(nums[i]);
}
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
//在List中是相等，在Array中是不等
//双指针法：一个从前向后扫，一个记录结果，
class Solution {
    public int removeElement(int[] nums, int val) {
        if (nums == null || nums.length == 0) return 0;
        int res = 0;
        for (int i = 0; i < nums.length; i++) {
            //如果和val相等，i向前走，r不变
            if(nums[i] != val) {
                nums[res++] = nums[i];
            }
        }
        return res;    
    }
}
// @lc code=end


// class Solution {
//     public int removeElement(int[] nums, int val) {
//         int ans = 0;
//         for(int num: nums) {
//             if(num != val) {
//                 nums[ans] = num;
//                 ans++;
//             }
//         }
//         return ans;
//     }
// }

// class Solution {
//     public int removeElement(int[] nums, int val) {
//         int i  = 0;
//         for (int j = 0; j < nums.length; ++j) {
//             if (nums[j] != val) {
//                 nums[i] = nums[j];
//                 i++;
//             }
//         }
//         return i;
//     }
// }

26. Remove Duplicates from Sorted Array

Given a sorted array nums, remove the duplicates in-place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

Example 1:

1
2
3
4
5
Given nums = [1,1,2],

Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively.

It doesn't matter what you leave beyond the returned length.

Example 2:

1
2
3
4
5
Given nums = [0,0,1,1,1,2,2,3,3,4],

Your function should return length = 5, with the first five elements of nums being modified to 0, 1, 2, 3, and 4 respectively.

It doesn't matter what values are set beyond the returned length.

Clarification:

Confused why the returned value is an integer but your answer is an array?

Note that the input array is passed in by reference, which means modification to the input array will be known to the caller as well.

Internally you can think of this:

1
2
3
4
5
6
7
8
// nums is passed in by reference. (i.e., without making a copy)
int len = removeDuplicates(nums);

// any modification to nums in your function would be known by the caller.
// using the length returned by your function, it prints the first len elements.
for (int i = 0; i < len; i++) {
    print(nums[i]);
}
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
26
27
28
29
30
class Solution {
    public int removeDuplicates(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        //第一个数一定被保持，
        int count = 1;
        for (int i = 1; i < nums.length; i++) {
            if(nums[i - 1] != nums[i]) {
                //如果相同,那么count不变,i++
                nums[count++] = nums[i];
            }
        }
        return count;
    }
}



// class Solution {
//     public int removeDuplicates(int[] nums) {
//         if (nums == null || nums.length == 0) return 0;
//         int i = 0;
//         for (int j = 1; j < nums.length; ++j) {
//             if (nums[j] != nums[i]) {
//                 i++;
//                 nums[i] = nums[j];
//             }
//         }
//         return i + 1;
//     }
// }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 * [80] 删除排序数组中的重复项 II
 */

// @lc code=start
class Solution {
    public int removeDuplicates(int[] nums) {
        if (nums.length <= 2) return nums.length;
        int count = 2;
        for(int i = 2; i < nums.length; i++) {
            if(nums[i] != nums[count - 2]){
                nums[count++] = nums[i];
            }
        }
        return count;
    }
}
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
26
 * [83] 删除排序链表中的重复元素
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode cur = head;
        while (cur.next != null) {
            if(cur.next.val == cur.val) {
                cur.next = cur.next.next;
            } else {
                cur = cur.next;// movre forward when do not have replcaited item;
            }
        }
        return head;
    }
}

53. Maximum Subarray

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

1
2
3
Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

Follow up:

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    //dp,前N个数的和就是它的DP值
    public int maxSubArray(int[] nums) {
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        int res = nums[0];
        for(int i = 1; i < nums.length; i++) {
             dp[i] = nums[i] + (dp[i - 1] < 0 ? 0 : dp[i - 1]);
             res = Math.max(res, dp[i]);
        }
        return res;
    }
}