66. Plus One
description:
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.
Train of thought:
Sum and overflow operations are carried out from low to high to find the last number. If the last bit overflows, special processing will be carried out, otherwise, direct copy will be returned.
/**
* Return an array of size *returnSize.
* Note: The returned array must be malloced, assume caller calls free().
*/
int* plusOne(int* digits, int digitsSize, int* returnSize) {
int i;
int pre = 1;
int temp;
int *p = NULL;
for(i = digitsSize -1; i >= 0; i--){
temp = (digits[i]+pre)%10;
pre = (digits[i] + pre) / 10;
digits[i] = temp;
}
if(pre){
*returnSize = digitsSize+1;
p = malloc(sizeof(int) * (*returnSize));
if(p){
memset(p, 0, *returnSize);
p[0] = 1;
return p;
}
}
p = malloc(sizeof(int) * digitsSize);
if(p){
memcpy(p, digits, sizeof(int) * digitsSize);
}
*returnSize = digitsSize;
return p;
}
441. Arranging Coins
description:
You have a total of n coins that you want to form in a staircase shape, where every k-th row must have exactly k coins.
Given n, find the total number of full staircase rows that can be formed.
n is a non-negative integer and fits within the range of a 32-bit signed integer.
Idea: equal difference series, pay attention to multiplication overflow.
int arrangeCoins(int n) {
long long i = 0;
while(((i*i + i)>>1) <= n){
i++;
}
return i-1;
}
414. Third Maximum Number
description:
Given a non-empty array of integers, return the third maximum number in this array. If it does not exist, return the maximum number. The time complexity must be in O(n).
Train of thought:
Insertion method, classified discussion.
int thirdMax(int* nums, int numsSize) {
int max_num[3] = {};
int num = 0;
int i;
for(i = 0; i < numsSize; i++){
if(0 == num){
max_num[0] = nums[i];
num++;
}else if(1 == num){
if(nums[i] > max_num[0]){
max_num[1] = nums[i];
num++;
}else if(nums[i] < max_num[0]){
max_num[1] = max_num[0];
max_num[0] = nums[i];
num++;
}
}else if(2 == num){
if(nums[i] > max_num[1]){
max_num[2] = nums[i];
num++;
}else if(nums[i] > max_num[0] && nums[i] != max_num[1]){
max_num[2] = max_num[1];
max_num[1] = nums[i];
num++;
}else if(nums[i] < max_num[0]){
max_num[2] = max_num[1];
max_num[1] = max_num[0];
max_num[0] = nums[i];
num++;
}
}else{
if(max_num[2] < nums[i]){
max_num[0] = max_num[1];
max_num[1] = max_num[2];
max_num[2] = nums[i];
}else if(nums[i] > max_num[1] && nums[i] != max_num[2]){
max_num[0] = max_num[1];
max_num[1] = nums[i];
}else if(nums[i] > max_num[0] && nums[i] != max_num[1] && nums[i] != max_num[2]){
max_num[0] = nums[i];
}
}
}
return (num == 3) ? max_num[0] : max_num[num-1];
}
349. Intersection of Two Arrays
description:
Given two arrays, write a function to compute their intersection.
Train of thought:
Quick sort, then compare. Only the minimum value is optimized.
Best ideas:
It is still a quick sort, but it is a dynamic comparison. Skip the parts that do not need to be compared and directly apply for memory.
/**
* Return an array of size *returnSize.
* Note: The returned array must be malloced, assume caller calls free().
*/
/**
int compare(const void * a, const void * b) {
return ( *(int*)a - *(int*)b );
}
int *mem_set(int *p, int val, int *num){
int *p_temp;
if(NULL == p){
p = malloc(sizeof(int));
if(p){
*p = val;
*num = 1;
}else{
return NULL;
}
return p;
}else{
p_temp = malloc(sizeof(int) * (*num+1));
if(p_temp){
memcpy(p_temp, p, sizeof(int) * (*num));
p_temp[*num] = val;
(*num)++;
}else{
free(p);
return NULL;
}
return p_temp;
}
}
int* intersection(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize) {
if(NULL == nums1 || 0 == nums1Size || NULL == nums2 || 0 == nums2Size){
goto label;
}
int pre;
int i, j;
int *p = NULL;
qsort(nums1, nums1Size, sizeof(int), compare);
qsort(nums2, nums2Size, sizeof(int), compare);
pre = nums1[0] - 1;
*returnSize = 0;
for(i = 0; i < nums1Size; i++){
if(nums1[i] < nums2[0]){
pre = nums1[i];
continue;
}
if(pre == nums1[i]){
continue;
}
for(j = 0; j < nums2Size; j++){
if(nums1[i] == nums2[j]){
p = mem_set(p, nums1[i], returnSize);
if(NULL == p){
goto label;
}
break;
}
}
pre = nums1[i];
}
return p;
label:
*returnSize = 0;
return NULL;
}
*/
int compare(const void *a,const void *b){
return *(int *)a-*(int *)b;
}
int* intersection(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize) {
int i,j,size,*Rarray;
size = nums1Size < nums2Size? nums1Size: nums2Size;
Rarray=(int *)malloc(size*sizeof(int));
*returnSize=0;
qsort(nums1,nums1Size,sizeof(int),compare);
qsort(nums2,nums2Size,sizeof(int),compare);
for(i=0,j=0;i<nums1Size&&j<nums2Size; ){
while(i<nums1Size&&nums1[i]<nums2[j])
i++;
if(nums1[i] == nums2[j]){
Rarray[*returnSize]=nums1[i];
while(i<nums1Size&&nums1[i]==Rarray[*returnSize])
i++;
while(j<nums2Size&&nums2[j]==Rarray[*returnSize])
j++;
(*returnSize)++;
}
while(j<nums2Size&&nums1[i]>nums2[j])
j++;
}
return Rarray;}
674. Longest Continuous Increasing Subsequence
description:
Given an unsorted array of integers, find the length of longest continuous increasing subsequence (subarray).
Train of thought:
Before and after comparison, update the maximum value.
int findLengthOfLCIS(int* nums, int numsSize) {
if(NULL == nums || 0 == numsSize){
return 0;
}
int cur_subsequence = 1;
int max_subsequence = 1;
int i;
for(i = 0; i < numsSize-1; i++){
if(nums[i] < nums[i+1]){
cur_subsequence++;
}else{
if(cur_subsequence > max_subsequence){
max_subsequence = cur_subsequence;
}
cur_subsequence = 1;
}
}
if(cur_subsequence > max_subsequence){
max_subsequence = cur_subsequence;
}
return max_subsequence;
}
459. Repeated Substring Pattern
description:
Given a non-empty string check if it can be constructed by taking a substring of it and appending multiple copies of the substring together. You may assume the given string consists of lowercase English letters only and its length will not exceed 10000.
Train of thought:
If it is repeated, first find out the largest repeated string, compare it from the back to the front, the longest is no more than half of the string, then find the largest substring, and compare whether the middle part is consistent.
Best ideas:
Suppose it's repeated, one by one. For example, if the string length is 6, test whether its integer divisor meets the repetition condition, i.e. 1, 2, 3
/*bool repeatedSubstringPattern(char* s) {
int i, k;
char substr[10000] = {};
int substr_len_cur = 0;
int substr_len_max = 0;
int str_len = strlen(s);
int j = str_len / 2;
for(k = 0; k < j; k++){
for(i = 0; i < k+1; i++){
if(s[i] == s[str_len-1-k+i]){
substr[i] = s[i];
substr_len_cur++;
}else{
substr_len_cur = substr_len_max;
break;
}
}
substr_len_max = substr_len_cur;
substr_len_cur = 0;
}
for(i = substr_len_max, k = 0; i < str_len-substr_len_max; i++, k++){
if(substr[k] != s[i]){
return false;
}
}
return true;
}*/
bool repeatedSubstringPattern(char* s) {
int size = strlen(s);
int found = true, start = 0;
int i = 0;
if(size <= 1)
return false;
for(i=1; i <= size / 2; i++)
{
if(size % i == 0)
{
found = true;
for(start = i; start + i <= size; start += i)
{
if(memcmp(s, s + start, i) != 0)
{
found = false;
break;
}
}
if(found)
{
return true;
}
}
}
return false;
}
231. Power of Two
description:
Given an integer, write a function to determine if it is a power of two.
Train of thought:
Determine whether a bit is set, and then verify that other bits are not set. Basic operation of bit.
#define TEST_THE_BIT(x, n) x & (1 << n)
#define TEST_OTHER_BIT(x, n) x & ~(1 << n)
bool isPowerOfTwo(int n) {
if(n < 1){
return false;
}
int i;
for(i = 0; i< 31; i++){
if(TEST_THE_BIT(n, i)){
if(TEST_OTHER_BIT(n, i)){
return false;
}else{
return true;
}
}
}
return false;
}