作者: 康凯森
日期: 2016-11-19
分类: 算法
原题 给出2*n + 1 个的数字,除其中一个数字之外其他每个数字均出现两次,找到这个数字。
一个数与自身异或的结果为0
public class Solution {
/**
*@param A : an integer array
*return : a integer
*/
public int singleNumber(int[] A) {
if (A.length == 0) {
return 0;
}
int n = A[0];
for(int i = 1; i < A.length; i++) {
n = n ^ A[i];
}
return n;
}
}
原题 给出3*n + 1 个的数字,除其中一个数字之外其他每个数字均出现三次,找到这个数字。
若一个数字出现3次,则该数字的二进制表示中每个位置的数值为1的出现次数为3次,如:5的二进制表示为101,若5出现3次,则其二进制表示中的第一个位置和第二个位置出现1的次数和均为3。那么对该位1出现的次数对3取余,最终的结果所对应的就是所要求的Sing Number。
对int的32bit的各个位中1出现的次数,对数组中所有元素逐个进行统计,然后每个bit对3取余,最终的结果就是只出现一次的数字。
public class Solution {
/**
* @param A : An integer array
* @return : An integer
*/
public int singleNumberII(int[] A) {
if (A == null || A.length == 0) {
return -1;
}
int result = 0;
int[] bits = new int[32];
for (int i = 0;i < 32;i++) {
for(int j = 0;j < A.length;j++){
bits[i] += A[j] >> i & 1;
bits[i] = bits[i] % 3;
}
result = result | (bits[i] << i);
}
return result;
}
}
原题 给出2*n + 2个的数字,除其中两个数字之外其他每个数字均出现两次,找到这两个数字。
一个数与自身异或的结果为0。
如果对所有元素进行异或操作,最后剩余的结果是出现次数为1次的两个数的异或结果,此时无法直接得到这两个数具体的值。但是,因为这两个数一定是不同的,所以最终异或的值至少有一个位为1。我们可以找出异或结果中第一个值为1的位,然后根据该位的值是否为1,将数组中的每一个数,分成两个部分。这样每个部分,就可以采用Singal numberI中的方法得到只出现一次的数。
public class Solution {
/**
* @param A : An integer array
* @return : Two integers
*/
int findFirstBit1(int num) {
int index = 0;
while((num & 1) == 0) {
++index;
num >>= 1;
}
return index;
}
boolean isBit1(int num, int index) {
num = num >> index;
if ((num & 1) == 1)
return true;
else
return false;
}
public List<Integer> singleNumberIII(int[] A) {
ArrayList<Integer> res = new ArrayList<Integer> ();
if (A ==null || A.length == 0){
return res;
}
int n = A.length;
int result = 0;
for (int i = 0;i < n;i ++){
result ^= A[i];
}
int indexOfBit1 = findFirstBit1(result);
int num1 = 0, num2 = 0;
for(int i = 0; i < n; ++i) {
if(isBit1(A[i], indexOfBit1)) {
num1 ^= A[i];
}
else
num2 ^= A[i];
}
res.add(num1);
res.add(num2);
return res;
}
}
原题 给定一个整型数组,找出主元素,它在数组中的出现次数严格大于数组元素个数的二分之一
public class Solution {
/**
* @param nums: a list of integers
* @return: find a majority number
*/
public int majorityNumber(ArrayList<Integer> nums) {
if (nums.size() == 0){
return -1;
}
int result = nums.get(0);
int count = 1;
for (int i = 1;i < nums.size();i++){
if (result == nums.get(i)){
count ++;
}
else {
count --;
if (count == 0){
result = nums.get(i);
count = 1;
}
}
}
return result;
}
}
原题 给定一个整型数组,找到主元素,它在数组中的出现次数严格大于数组元素个数的三分之一。
1.选择两个candidate
2.scan数组,如果和两个candidate相等,则相应的candidate count+1;如果不相等,两个candidate的counter都减1(前提是counter都大于0);如果某一个counter已经等于0,那么替换candidate为当前数
3.我们最后得到两个candidate,但是不知道谁更majority,因为一个例子就是1,1,1,1,3,3,3,2,2,2,5,5,5,最后candidate1=1, counter=1,candidate2=5,counter2=3,原因就是candidate1在之前被错误的抵消了很多。所以要再扫一遍。
public class Solution {
/**
* @param nums: A list of integers
* @return: The majority number that occurs more than 1/3
*/
public int majorityNumber(ArrayList<Integer> nums) {
int candidate1 = 0, candidate2 = 0;
int count1, count2;
count1 = count2 = 0;
for (int i = 0; i < nums.size(); i++) {
if (candidate1 == nums.get(i)) {
count1 ++;
} else if (candidate2 == nums.get(i)) {
count2 ++;
} else if (count1 == 0) {
candidate1 = nums.get(i);
count1 = 1;
} else if (count2 == 0) {
candidate2 = nums.get(i);
count2 = 1;
} else {
count1--;
count2--;
}
}
count1 = count2 = 0;
for (int i = 0; i < nums.size(); i++) {
if (nums.get(i) == candidate1) {
count1++;
} else if (nums.get(i) == candidate2) {
count2++;
}
}
return count1 > count2 ? candidate1 : candidate2;
}
}
原题 给定一个整型数组,找到主元素,它在数组中的出现次数严格大于数组元素个数的1/k。
使用HashMap,存k个值,key为数组中的元素值,value为该值出现的次数。若同时有k个不同的元素在map中,则抵销一次,即所有value减一,并删除value为零的key,遍历一遍后,map中value最大的key为答案。
public class Solution {
/**
* @param nums: A list of integers
* @param k: As described
* @return: The majority number
*/
public int majorityNumber(ArrayList<Integer> nums, int k) {
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for (Integer i : nums) {
if (!map.containsKey(i)) {
map.put(i, 1);
} else {
map.put(i, map.get(i) + 1);
}
if (map.size() >= k) {
removeKey(map);
}
}
if (map.size() == 0) {
return Integer.MIN_VALUE;
}
int maxKey = 0;
int max = 0;
Set<Integer> keySet = map.keySet();
for (Integer i : keySet) {
int count = 0;
for (Integer j : nums) {
if (i.equals(j)) {
count++;
}
}
if (count > max) {
max = count;
maxKey = i;
}
}
return maxKey;
}
private void removeKey(Map<Integer, Integer> map) {
Set<Integer> keySet = map.keySet();
List<Integer> removeList = new ArrayList<>();
for (Integer key : keySet) {
if (map.get(key) == 1) {
removeList.add(key);
}
else {
map.put(key, map.get(key) - 1);
}
}
for (Integer key : removeList) {
map.remove(key);
}
}
}
原题 假设有一个数组,它的第i个元素是一支给定的股票在第i天的价格。如果你最多只允许完成一次交易(例如,一次买卖股票),设计一个算法来找出最大利润。
扫描一遍,找出后一项-前一项的最大值即可
public class Solution {
/**
* @param prices: Given an integer array
* @return: Maximum profit
*/
public int maxProfit(int[] prices) {
if (prices == null || prices.length == 0) {
return 0;
}
int min = Integer.MAX_VALUE; //just remember the smallest price
int profit = 0;
for (int i : prices) {
min = i < min ? i : min;
profit = (i - min) > profit ? i - min : profit;
}
return profit;
}
}
原题 假设有一个数组,它的第i个元素是一个给定的股票在第i天的价格。设计一个算法来找到最大的利润。你可以完成尽可能多的交易(多次买卖股票)。然而,你不能同时参与多个交易(你必须在再次购买前出售股票)。
best-time-to-buy-and-sell-stock的基础累加即可
class Solution {
/**
* @param prices: Given an integer array
* @return: Maximum profit
*/
public int maxProfit(int[] prices) {
if ( prices == null || prices.length == 0){
return 0;
}
int profit = 0;
for (int i = 1; i < prices.length; i++){
if (prices[i] > prices[i-1]){
profit += prices[i] - prices[i-1];
}
}
return profit;
}
}
原题 假设你有一个数组,它的第i个元素是一支给定的股票在第i天的价格。设计一个算法来找到最大的利润。你最多可以完成两笔交易。
给出一个样例数组 [4,4,6,1,1,4,2,5], 返回 6
基本思想是分成两个时间段,然后对于某一天,计算之前的最大值和之后的最大值
class Solution {
/**
* @param prices: Given an integer array
* @return: Maximum profit
*/
public int maxProfit(int[] prices) {
if (prices == null || prices.length <= 1) {
return 0;
}
int[] left = new int[prices.length];
int[] right = new int[prices.length];
// DP from left to right;
left[0] = 0;
int min = prices[0];
for (int i = 1; i < prices.length; i++) {
min = Math.min(prices[i], min);
left[i] = Math.max(left[i - 1], prices[i] - min);
}
//DP from right to left;
right[prices.length - 1] = 0;
int max = prices[prices.length - 1];
for (int i = prices.length - 2; i >= 0; i--) {
max = Math.max(prices[i], max);
right[i] = Math.max(right[i + 1], max - prices[i]);
}
int profit = 0;
for (int i = 0; i < prices.length; i++){
profit = Math.max(left[i] + right[i], profit);
}
return profit;
}
};
原题 假设你有一个数组,它的第i个元素是一支给定的股票在第i天的价格。
设计一个算法来找到最大的利润。你最多可以完成 k 笔交易
我们维护两种量,一个是当前到达第i天可以最多进行j次交易,最好的利润是多少(global[i][j]),另一个是当前到达第i天,最多可进行j次交易,并且最后一次交易在当天卖出的最好的利润是多少(local[i][j])
同时注意当K很大时的情况,变为买卖股票的最佳时机ii。
class Solution {
/**
* @param k: An integer
* @param prices: Given an integer array
* @return: Maximum profit
*/
public int maxProfit(int k, int[] prices) {
if (k == 0) {
return 0;
}
if(prices==null || prices.length==0)
return 0;
if (k >= prices.length / 2) {
int profit = 0;
for (int i = 1; i < prices.length; i++) {
if (prices[i] > prices[i - 1]) {
profit += prices[i] - prices[i - 1];
}
}
return profit;
}
int len = prices.length;
int[][] local = new int[len][k+1];
int[][] global = new int[len][k+1];
for(int i=1; i<len; i++) {
int diff = prices[i] - prices[i-1];
for(int j=1; j<=k; j++) {
local[i][j] = Math.max(global[i-1][j-1]+Math.max(diff,0), local[i-1][j]+diff);
global[i][j] = Math.max(global[i-1][j], local[i][j]);
}
}
return global[len-1][k];
}
};
原题 给定一个整数数组,找到一个具有最大和的子数组,返回其最大和。
扫描一遍,遇到负数则重新累加求和。
public class Solution {
/**
* @param nums: A list of integers
* @return: A integer indicate the sum of max subarray
*/
public int maxSubArray(ArrayList<Integer> nums) {
if(nums == null || nums.size() == 0){
return 0;
}
int thissum = 0;
int maxsum = nums.get(0);
for (int i : nums){
thissum += i;
if (thissum > maxsum){
maxsum = thissum;
}
else if (thissum < 0){
thissum = 0;
}
}
return maxsum;
}
}
原题 给定一个整数数组,找出两个不重叠子数组使得它们的和最大。
每个子数组的数字在数组中的位置应该是连续的。
返回最大的和。
和买卖股票的最佳时机 III 思路一样。用俩个数组,一个从左往右扫,一个从右往左扫。
public class Solution {
/**
* @param nums: A list of integers
* @return: An integer denotes the sum of max two non-overlapping subarrays
*/
public int maxTwoSubArrays(ArrayList<Integer> nums) {
// write your code
int size = nums.size();
int[] left = new int[size];
int[] right = new int[size];
int sum = 0;
int minSum = 0;
int max = Integer.MIN_VALUE;
for(int i = 0; i < size; i++){
sum += nums.get(i);
max = Math.max(max,sum);
sum = Math.max(sum,0);
left[i] = max;
}
sum = 0;
minSum = 0;
max = Integer.MIN_VALUE;
for(int i = size - 1; i >= 0; i--){
sum += nums.get(i);
max = Math.max(max, sum );
sum = Math.max(sum,0);
right[i] = max;
}
max = Integer.MIN_VALUE;
for(int i = 0; i < size - 1; i++){
max = Math.max(max, left[i] + right[i + 1]);
}
return max;
}
}
原题 给定一个整数数组和一个整数k,找出k个不重叠子数组使得它们的和最大。
每个子数组的数字在数组中的位置应该是连续的。
返回最大的和。
思路类似买卖股票的最佳时机 IV,用DP解。
public class Solution {
/**
* @param nums: A list of integers
* @param k: An integer denote to find k non-overlapping subarrays
* @return: An integer denote the sum of max k non-overlapping subarrays
*/
public int maxSubArray(ArrayList<Integer> nums, int k) {
if (nums == null)
return 0;
int len = nums.size();
if (len < k)
return 0;
int[][] globalMax = new int[k + 1][len + 1];
for (int i = 1; i <= k; i++) {
int localMax = Integer.MIN_VALUE;
for (int j = i - 1; j < len; j++) {
localMax = Math.max(localMax, globalMax[i - 1][j]) + nums.get(j);
if (j == i - 1)
globalMax[i][j + 1] = localMax;
else
globalMax[i][j + 1] = Math.max(globalMax[i][j], localMax);
}
}
return globalMax[k][len];
}
}
同最大子数组
public class Solution {
/**
* @param nums: a list of integers
* @return: A integer indicate the sum of minimum subarray
*/
public int minSubArray(ArrayList<Integer> nums) {
if (nums == null || nums.size() == 0) {
return 0;
}
int tempSum = 0;
int minSum = nums.get(0);
for (int i = 0; i < nums.size(); i++){
tempSum += nums.get(i);
minSum = Math.min(tempSum , minSum);
tempSum = Math.min(tempSum , 0);
}
return minSum;
}
}
给定一个整数数组,找出两个不重叠的子数组A和B,使两个子数组和的差的绝对值|SUM(A) - SUM(B)|最大。
返回这个最大的差值。
左右各扫描一遍。建立俩个数组,每个数组存放对应的从左,从右的最大,最小值。
public class Solution {
/**
* @param nums: A list of integers
* @return: An integer indicate the value of maximum difference between two
* Subarrays
*/
public int maxDiffSubArrays(ArrayList<Integer> nums) {
if (nums == null || nums.size() == 0) {
return 0;
}
int len = nums.size();
int[] leftMin = new int[len];
int[] leftMax = new int[len];
int endMin = nums.get(0), endMax = nums.get(0);
leftMin[0] = endMin;
leftMax[0] = endMax;
for (int i=1;i<len;i++){
//Calculate max subarray.
endMax = Math.max(nums.get(i), nums.get(i)+endMax);
leftMax[i] = Math.max(leftMax[i-1],endMax);
//Calculate min subarray.
endMin = Math.min(nums.get(i),nums.get(i)+endMin);
leftMin[i] = Math.min(leftMin[i-1],endMin);
}
int[] rightMin = new int[len];
int[] rightMax = new int[len];
endMin = nums.get(len-1);
endMax = nums.get(len-1);
rightMin[len-1] = endMin;
rightMax[len-1] = endMax;
for (int i=len-2;i>=0;i--){
endMax = Math.max(nums.get(i),nums.get(i)+endMax);
rightMax[i] = Math.max(rightMax[i+1],endMax);
endMin = Math.min(nums.get(i),nums.get(i)+endMin);
rightMin[i] = Math.min(rightMin[i+1],endMin);
}
int maxDiff= 0;
for (int i=0;i<len-1;i++){
if (maxDiff<Math.abs(leftMin[i]-rightMax[i+1]))
maxDiff = Math.abs(leftMin[i]-rightMax[i+1]);
if (maxDiff<Math.abs(leftMax[i]-rightMin[i+1]))
maxDiff = Math.abs(leftMax[i]-rightMin[i+1]);
}
return maxDiff;
}
}
原题 给定一个整数数组,找到和为零的子数组。你的代码应该返回满足要求的子数组的起始位置和结束位置
使用Map 来记录index,sum的值。当遇到两个index的sum相同时,表示从index1+1到index2是一个解。 注意:添加一个index = -1作为虚拟节点。这样我们才可以记录index1 = 0的解。
public class Solution {
/**
* @param nums: A list of integers
* @return: A list of integers includes the index of the first number
* and the index of the last number
*/
public ArrayList<Integer> subarraySum(int[] nums) {
ArrayList<Integer> res = new ArrayList<Integer>();
if (nums==null || nums.length==0) return res;
int len = nums.length;
Map<Integer,Integer> map = new HashMap<Integer , Integer>();
map.put(0,-1);
int sum =0;
for (int i=0;i<len;i++){
sum += nums[i];
//check the exists of current sum.
if (map.containsKey(sum)){
int start = map.get(sum)+1;
res.add(start);
res.add(i);
return res;
} else {
map.put(sum,i);
}
}
return res;
}
}
原题 给定一个整数数组,找到一个和最接近于零的子数组。返回第一个和最有一个指数。你的代码应该返回满足要求的子数组的起始位置和结束位置。
连续数组的和其实就是前缀和之间的差,而要求和最接近于零,也就是说,两个前缀和要最接近,那么直接前缀和排序,相邻两项比较即。 由O(nlogn)的时间复杂度我们也可以想到排序。
class CustomComparator implements Comparator<int[]> {
public int compare(int[] a, int[] b) {
return Integer.compare(a[0], b[0]);
}
}
public class Solution {
/**
* @param nums: A list of integers
* @return: A list of integers includes the index of the first number
* and the index of the last number
*/
public ArrayList<Integer> subarraySumClosest(int[] nums) {
ArrayList<Integer> rst = new ArrayList<Integer>();
if(nums == null || nums.length == 0) {
return rst;
}
if (nums.length == 1) {
rst.add(0); rst.add(0);
return rst;
}
int[][] culmulate = new int[nums.length][2];
culmulate[0][0] = nums[0];
culmulate[0][1] = 0;
for (int i = 1; i < nums.length; i++) {
culmulate[i][0] = culmulate[i - 1][0] + nums[i];
culmulate[i][1] = i;
}
Arrays.sort(culmulate, new CustomComparator());
int min = Integer.MAX_VALUE;
int start = 0;
int end = 0;
for (int i = 0; i < nums.length - 1; i++) {
int temp = culmulate[i + 1][0] - culmulate[i][0];
if (temp <= min) {
min = temp;
start = culmulate[i][1];
end = culmulate[i + 1][1];
}
}
if (start < end) {
rst.add(start + 1);
rst.add(end);
} else {
rst.add(end + 1);
rst.add(start);
}
return rst;
}
}
原题 给一个整数数组,找到两个数使得他们的和等于一个给定的数target。
你需要实现的函数twoSum需要返回这两个数的下标, 并且第一个下标小于第二个下标。注意这里下标的范围是1到n,不是以0开头。
和 subarray-sum 子数组之和 问题一样
public class Solution {
/*
* @param numbers : An array of Integer
* @param target : target = numbers[index1] + numbers[index2]
* @return : [index1 + 1, index2 + 1] (index1 < index2)
*/
public int[] twoSum(int[] numbers, int target) {
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
int[] result = new int[2];
for (int i = 0; i < numbers.length; i++) {
if (map.containsKey(numbers[i])) {
int index = map.get(numbers[i]);
result[0] = index+1 ;
result[1] = i+1;
break;
} else {
map.put(target - numbers[i], i);
}
}
return result;
}
}
原题 给出一个有n个整数的数组S,在S中找到三个整数a, b, c,找到所有使得a + b + c = 0的三元组。
a + b + c = 0 => a + b = -c; 我们很自然的想到排序,再从俩头扫。设置最小的c,第2小和最大的为a 和 b. 固定c,让a++或者b--.对整个数组循环这个过程。
public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
if (num.length < 3)
return result;
// sort array
Arrays.sort(num);
for (int i = 0; i < num.length - 2; i++) {
// //avoid duplicate solutions
if (i == 0 || num[i] > num[i - 1]) {
int negate = -num[i];
int start = i + 1;
int end = num.length - 1;
while (start < end) {
//case 1
if (num[start] + num[end] == negate) {
ArrayList<Integer> temp = new ArrayList<Integer>();
temp.add(num[i]);
temp.add(num[start]);
temp.add(num[end]);
result.add(temp);
start++;
end--;
//避免重复
while (start < end && num[end] == num[end + 1])
end--;
while (start < end && num[start] == num[start - 1])
start++;
//case 2
} else if (num[start] + num[end] < negate) {
start++;
//case 3
} else {
end--;
}
}
}
}
return result;
给一个包含n个整数的数组S, 找到和与给定整数target最接近的三元组,返回这三个数的和。
思路
和上题一样,排序后,俩头扫。只是每次保留和target的差的最小值
public int threeSumClosest(int[] nums ,int target) {
int min = Integer.MAX_VALUE;
int result = 0;
Arrays.sort(nums);
for (int i = 0; i < nums.length; i++) {
int j = i + 1;
int k = nums.length - 1;
while (j < k) {
int sum = nums[i] + nums[j] + nums[k];
int diff = Math.abs(sum - target);
if(diff == 0) return sum;
if (diff < min) {
min = diff;
result = sum;
}
if (sum <= target) {
j++;
} else {
k--;
}
}
}
return result;
}
给一个包含n个数的整数数组S,在S中找到所有使得和为给定整数target的四元组(a, b, c, d)。
思路
和前俩题思路一样,只不过排序后要固定前俩个数字,俩头扫。需要俩重循环。
public class Solution {
public ArrayList<ArrayList<Integer>> fourSum(int[] num, int target) {
ArrayList<ArrayList<Integer>> rst = new ArrayList<ArrayList<Integer>>();
Arrays.sort(num);
for (int i = 0; i < num.length - 3; i++) {
if (i != 0 && num[i] == num[i - 1]) {
continue;
}
for (int j = i + 1; j < num.length - 2; j++) {
if (j != i + 1 && num[j] == num[j - 1])
continue;
int left = j + 1;
int right = num.length - 1;
while (left < right) {
int sum = num[i] + num[j] + num[left] + num[right];
if (sum < target) {
left++;
} else if (sum > target) {
right--;
} else {
ArrayList<Integer> tmp = new ArrayList<Integer>();
tmp.add(num[i]);
tmp.add(num[j]);
tmp.add(num[left]);
tmp.add(num[right]);
rst.add(tmp);
left++;
right--;
while (left < right && num[left] == num[left - 1]) {
left++;
}
while (left < right && num[right] == num[right + 1]) {
right--;
}
}
}
}
}
return rst;
}
}
给定n个不同的正整数,整数k(k < = n)以及一个目标数字。 在这n个数里面找出K个数,使得这K个数的和等于目标数字,求问有多少种方案?
思路
经过前面几道和K相关的问题,我们意识到应该用动态规划(DP)了。 建立递推方程如下:
if (t <= A[i - 1]) {
f[i][j][t] = f[i - 1][j - 1][t - A[i - 1]];
}
f[i][j][t] += f[i - 1][j][t];
我们用f[i][j][t] 代表前i个数,挑j个数,组成和为t的方案总数。 (1)我们可以把当前A[i - 1]这个值包括进来,所以需要加上D[i - 1][j - 1][t - A[i - 1]](前提是t – A[i - 1]要大于0)
(2)我们可以不选择A[i - 1]这个值,这种情况就是D[i - 1][j][t],也就是说直接在前i-1个值里选择一些值加到target.
public class Solution {
/**
* @param A: an integer array.
* @param k: a positive integer (k <= length(A))
* @param target: a integer
* @return an integer
*/
public int kSum(int A[], int k, int target) {
int n = A.length;
int[][][] f = new int[n + 1][k + 1][target + 1];
for (int i = 0; i < n + 1; i++) {
f[i][0][0] = 1;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= k && j <= i; j++) {
for (int t = 1; t <= target; t++) {
f[i][j][t] = 0;
if (t >= A[i - 1]) {
f[i][j][t] = f[i - 1][j - 1][t - A[i - 1]];
}
f[i][j][t] += f[i - 1][j][t];
} // for t
} // for j
} // for i
return f[n][k][target];
}
}
计算an % b,其中a,b和n都是32位的整数。
思路
a的n次方等于a的n/2次方乘以a的n/2次方。注意奇偶。
class Solution {
/*
* @param a, b, n: 32bit integers
* @return: An integer
*/
public int fastPower(int a, int b, int n) {
if (n == 1) {
return a % b;
}
if (n == 0) {
return 1 % b;
}
long product = fastPower(a, b, n / 2);
product = (product * product) % b;
if (n % 2 == 1) {
product = (product * a) % b;
}
return (int) product;
}
};
Implement int sqrt(int x).Compute and return the square root of x
二分查找。由时间复杂度logn以及相关数学知识我们应该想到
public class Solution {
public int sqrt(int x) {
long lo = 0;
long hi = x;
while (hi >= lo) {
long mid = lo+(hi-lo)/2;
if (x < mid * mid) {
hi = mid-1; // not hi = mid
} else {
lo = mid+1;
}
}
return (int) hi;
}
}
Write an algorithm which computes the number of trailing zeros in n factorial.
思路
由数学知识我们知道,n!中尾部0的个数取决于5的个数,但是还有5的n次方我们不要忘记统计,因为2的个数总是多于5的。
class Solution {
/*
* param n: As desciption
* return: An integer, denote the number of trailing zeros in n!
*/
public long trailingZeros(long n) {
long x = 5;
long result = 0;
while (n >= x){
result += n / x;
x *= 5;
}
return result;
}
};
Using O(1) time to check whether an integer n is a power of 2.
思路
如果是n是2的幂,则有n&(n-1) == 0. 位运算中小技巧还是蛮多的。
class Solution {
/*
* @param n: An integer
* @return: True or false
*/
public boolean checkPowerOf2(int n) {
if (n == 0 || n == Integer.MIN_VALUE){
return false;
}
boolean flag = false;
if ((n & n - 1) == 0){
flag = true;
}
return flag;
}
};