Leetcode Journey
数组按出现频次从大到小排序
http://www.geeksforgeeks.org/amazon-interview-set-21/
#include <stdio.h>
typedef struct
{
int id;
int count;
}item;
void sort(int a[], int n)
{
item temp[n];
memset(temp,0,sizeof(temp));
int index=0;
for(int i=0;i<n;i++)
{
int count=1;
temp[index].id=a[i];
while(temp[index].id==a[i+count])
{
count++;
}
temp[index].count=count;
printf("id:%d,count:%d\n",temp[index].id,temp[index].count);
index++;
i+=count-1;
}
int j=0;
int k=0;
while(temp[j].count!=0) //should usd stable sort
{
int k=j+1;
while(temp[k].count!=0)
{
if(temp[k].count>temp[j].count)
{
item var=temp[j];
temp[j]=temp[k];
temp[k]=var;
}
k+=1;
}
printf("id:%d,count:%d\n",temp[j].id,temp[j].count);
j+=1;
}
printf("ddddd\n");
int m=0;
while(temp[m].count!=0)
{
while(temp[m].count--)
{
printf("%d",temp[m].id);
}
m+=1;
}
}
int main(void) {
// your code goes here
int a[]={65,65,1,1,1,2,2,0,9,9,9,9};
sort(a,12);
return 0;
}
344. Reverse String
Write a function that takes a string as input and returns the string reversed.
Example: Given s = “hello”, return “olleh”.
void inverse(int start, int end, char *p)
{
char temp;
if(p)
{
temp=p[start];
p[start]=p[end];
p[end]=temp;
return;
}
else
{
return;
}
}
char* reverseString(char* s)
{
int length=strlen(s);
printf("%d\n",length);
if(!s)
{
return NULL;
}
int start;
int end;
start=0;
end=length-1;
while(start<end)
{
//char *p=s+start;
inverse(start,end,s); //这边犯了个错误，将 p作为参数传入，p地址偏移后，end的计数就应该也要减1，正确应该直接将S传入
//printf("%c",s[start]);
start++;
end--;
//printf("%s\n",s);
}
return s;
}
136. Single Number
Given an 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?
int singleNumber(int* nums, int numsSize)
{
//a^a=0,a^b=b^a, 0^a=a;
//利用异或操作的特性 int a=0;
for(int i=0;i<numsSize;i++)
{
a=a^nums[i];
}
return a;
}
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.
void fast_sort(int start, int end, char *array)
{
if(start>=end)
return;
int pivot=array[start];
int i=start;
int j=end;
while(i<j)
{
while(i<j && array[j]>=pivot)
{
j--;
}
array[i]=array[j];
while(i<j && array[i]<=pivot)
{
i++;
}
array[j]=array[i];
}
array[i]=pivot;
fast_sort(start,i-1, array);
fast_sort(i+1,end,array);
}
char findTheDifference(char* s, char* t)
{
int len1=strlen(s);
int len2=strlen(t);
char *comp1=(char *)malloc(sizeof(char)*strlen(t));
//char *comp2=(char *)malloc(sizeof(char)*strlen(t));
memcpy(comp1,t,len2);
printf("len t:%d,len s:%d\n",strlen(t),strlen(s));
printf("%s\n",s);
printf("%s\n",t);
fast_sort(0,len1-1,s);
fast_sort(0,len2-1,t);
printf("%s\n",s);
printf("%s\n",t);
for(int i=0;i<len1;i++)
{
if(s[i]!=t[i])
{
if(t[i]==comp1[len2-1]);
return s[i];
}
}
char ret=t[len2-1];
//free(comp1);
//free(comp2);
printf("%c",ret);
return ret;
}
Ransom note
看成了KMP 匹配算法，这边实现了下
void get_next(char *key,int *next)
{ next[0]=0;
int i=0;
int j=-1;
while(i<strlen(key))
{
if(j==-1 || key[i]==key[j])
{
++i;
++j;
next[i]=j;
}
else
{
j=next[j]-1;
}
}
}
bool canConstruct(char* ransomNote, char* magazine)
{
int len=strlen(ransomNote);
int len_mag=strlen(magazine);
int *next=(int *)malloc(sizeof(int)*len);
get_next(ransomNote, next);
for(int i=0;i<len;i++)
{ printf("%d\t",next[i]); }
printf("\n len:%d,len_mag:%d\n",len,len_mag);
int i=0;
int j=0;
while(i<len_mag && j<len)
{
printf("i:%d,j:%d\n",i,j);
if(magazine[i]==ransomNote[j] )
{ i++; j++; }
else
{
if(j==0)
{ i++; }
else
{ j=next[j]; }
}
if(j==len)
{ printf("true\n"); return true; }
}
printf("false\n");
return false;
}真正的解法：
349 Intersection of Two ArraysHash 表的解法
#define HASHSIZE 1000
/**
* Return an array of size *returnSize.
* Note: The returned array must be malloced, assume caller calls free().
*/
int* intersection(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize)
{
int *ret;
int hash[HASHSIZE] = { 0 };
if (!nums1 || !nums2)
return NULL;
*returnSize = 0;
ret = calloc(MAX(nums1Size, nums2Size), sizeof(*nums1));
for (int i = 0; i < nums1Size; ++i)
hash[nums1[i]] = 1;
for (int i = 0; i < nums2Size; ++i)
if (hash[nums2[i]] == 1)
hash[nums2[i]] = 2;
for (int i = 0; i < HASHSIZE; ++i)
if (hash[i] == 2)
ret[(*returnSize)++] = i;
return ret;
}`
169 Majority ElementAll
Solutions :https://discuss.leetcode.com/topic/17446/6-suggested-solutions-in-c-with-explanations- Hash table:- Moore voting algorithm** introduce to moore voting algorithm**<http://www.cs.utexas.edu/~moore/best
ideas/mjrty/index.html>
int majorityElement(int* nums, int numsSize)
{
int count=0;
int retval=0;
for(int i=0;i<numsSize;i++)
{
if(count==0)
{
retval=nums[i];
count++;
}
else
{
if(retval==nums[i])
{
count++;
}
else
{
count--;
}
}
}
return retval;
}
Bit manipulationint majorityElement(int* nums, int numsSize)
{
int mask=0x00000001;
int retval;
for(int i=0;i<32;i++)
{
int count=0;
for(int j=0;j<numsSize;j++)
{
if(mask&nums[j])
{
count++;
}
}
if(count>numsSize/2)
{
retval|=mask;
}
mask<<=1;
}
}
350. Intersection of Two Arrays IIelegant
solution of python:
def intersect(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: List[int]
"""
dict1 = dict()
for i in nums1:
if i not in dict1:
dict1[i] = 1
else:
dict1[i] += 1
ret = []
for i in nums2:
if i in dict1 and dict1[i]>0:
ret.append(i)
dict1[i] -= 1
return ret
401. Binary Watch
from collections import defaultdict
class Solution(object):
def readBinaryWatch(self, num):
"""
:type num: int
:rtype: List[str]
"""
minute=defaultdict(lambda:list())
hour=defaultdict(lambda:list())
for i in range(60):
binary='{0:b}'.format(i)
minute[binary.count('1')].append(i)
for j in range(12):
binary='{0:b}'.format(j)
hour[binary.count('1')].append(j)
ret=list()
for i in range(num+1):
for j in hour[i]:
for k in minute[num-i]:
if len(str(k))<2:
ret.append(str(j)+':0'+str(k))
else:
ret.append(str(j)+':'+str(k))
return ret
566. Reshape the Matrix
class Solution(object):
def matrixReshape(self, nums, r, c):
flat = sum(nums, [])
if len(flat) != r * c:
return nums
print [iter(flat)]
print flat
#print *([iter(flat)]*c)
tuples = zip(*([iter(flat)] * c))
return map(list, tuples)
557 Reverse Words in a String III
my solution:
class Solution(object):
def reverseWords(self, s):
"""
:type s: str
:rtype: str
"""
lista=list()
s1=""
ret=""
for x in s:
if x!=' ':
s1+=x
else:
lista.append(s1)
s1=""
lista.append(s1) // append last string
print lista
for x in lista:
x=x[::-1]
ret+=x+' '
ret=ret[:-1] //delete last space, attention, last index is -1,and not included
return ret
better solution: use python split function:
class Solution(object):
def reverseWords(self, s):
"""
:type s: str
:rtype: str
"""
return " ".join(map(lamada x: x[ : :-1], s.split()))
// note: " ".join will insert a space into join list element
538. Convert BST to Greater Tree
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def convertBST(self, root):
"""
:type root: TreeNode
:rtype: TreeNode
"""
def sumall(isleft,node,noder):
if node==None and isleft:
return noder.val
if node==None and isleft==False:
return 0
if isleft:
node.val+=noder.val+sumall(False,node.right,node)
sumall(True,node.left,node)
return node.val
else:
node.val+=sumall(False,node.right,node)
return sumall(True,node.left,node)
if root==None:
return root
root.val+=sumall(False,root.right,root)
sumall(True,root.left,root)
return root
two sum
Given an array of integers, return indices of the two numbers such that they add up to a specific target. You may assume that each input would have exactly one solution, and you may not use the same element twice. Example: Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1].
public class Solution
{
public int[] twoSum(int[] nums, int target)
{
int[] index=new int[2];
if(nums==null||nums.length<2)
{
return null;
}
HashMap<Integer,Integer> map=new HashMap<Integer,Integer>();
for(int i=0;i<nums.length;i++)
{
if(map.containsKey(target-nums[i]))
{
index[0]=map.get(target-nums[i])+1;
index[1]=i+1;
break;
}
map.put(nums[i],i);
}
return index;
}
}
tag: hashmap, dict, index
Add Two Numbers
You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list. You may assume the two numbers do not contain any leading zero, except the number 0 itself. Input: (2 -> 4 -> 3) + (5 -> 6 -> 4) Output: 7 -> 0 -> 8
//this is from discussion solution
public class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode c1 = l1;
ListNode c2 = l2;
ListNode sentinel = new ListNode(0);
ListNode d = sentinel;
int sum = 0;
while (c1 != null || c2 != null) {
sum /= 10;
if (c1 != null) {
sum += c1.val;
c1 = c1.next;
}
if (c2 != null) {
sum += c2.val;
c2 = c2.next;
}
d.next = new ListNode(sum % 10);
d = d.next;
}
if (sum / 10 == 1)
d.next = new ListNode(1);
return sentinel.next;
}
}
c solution: just reuse the original list, not create a new list:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2)
{
int over_count=0;
struct ListNode *temp1=l1;
struct ListNode *temp2=l2;
struct ListNode *pre=l1;
//struct ListNode *head=l1;
int sum=0;
while(temp1 || temp2)
{
int val1=0;
int val2=0;
if(temp1==NULL)
{
pre->next=temp2; //shift from l1
while(temp2)
{
pre=temp2;
val2=temp2->val;
sum=val2+over_count;
pre->val=sum%10;
over_count=sum/10;
temp2=temp2->next;
}
break;//return l2 directly
}
else
{
//temp1!=NULL, l1
val1=temp1->val;
pre=temp1;
temp1=temp1->next;
if(temp2)
{
val2=temp2->val;
temp2=temp2->next;
}
}
sum=(val1+val2+over_count);
pre->val=sum%10;
over_count=sum/10;
sum=0;
printf("%d",over_count);
}
if(over_count)
{
struct ListNode *new_node=(struct ListNode*)malloc(sizeof(struct ListNode));
new_node->val=over_count;
new_node->next=NULL;
pre->next=new_node;
}
return l1;
}
tag: math, list
#3 Longest Substring Without Repeating Characters
Given a string, find the length of the longest substring without repeating characters. Examples: Given ”abcabcbb”, the answer is ”abc”, which the length is 3. Given ”bbbbb”, the answer is ”b”, with the length of 1. Given ”pwwkew”, the answer is ”wke”, with the length of 3. Note that the answer must be a substring, ”pwke” is a subsequenceand not a substring.
class Solution(object):
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
dic={}
start=0
maxlength=0
for i in range(len(s)):
if s[i] in dic:
start=dic[s[i]]+1
else:
maxlength=max(maxlength,i-start+1)
dic[s[i]]=i
return maxlength
tag: dict, string, substring
8. String to Integer (atoi)
Implement atoi to convert a string to an integer. Hint: Carefully consider all possible input cases. If you want a challenge, please do not see below and ask yourself what are the possible input cases. Notes: It is intended for this problem to be specified vaguely (ie, no given input specs). You are responsible to gather all the input requirements up front.
class Solution(object):
def myAtoi(self, str):
"""
:type str: str
:rtype: int
"""
resstr=''
flag=0
for c in str:
if c not in ' -+0123456789':
break
if c in '-+ ' :
if c in '-+ ' and flag==1 :
break;
if c in '-+':
resstr+=c
flag=1
if c in '0123456789':
flag=1
resstr+=c
if resstr =='' or resstr=='-' or resstr=='+':
return 0
res_int=int(resstr)
if res_int>=2147483647:
return 2147483647
if res_int<=-2147483648:
return -2147483648
return res_int
Note: 2147483647=2^32 - 1 tag: math, string
15. 3sum
Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero. Note: The solution set must not contain duplicate triplets. For example, given array S = [-1, 0, 1, 2, -1, -4],
A solution set is: [ [-1, 0, 1], [-1, -1, 2] ]
class Solution:
# @return a list of lists of length 3, [[val1,val2,val3]]
def threeSum(self, num):
num.sort()
ans = []
target = 0
for i in range(0, len(num)):
if (i > 0 and num[i] == num[i-1]): continue # only reserve first of all same values
l, r = i + 1, len(num) - 1
while l < r:
sum = num[i] + num[l] + num[r]
if sum == target:
ans.append([num[i], num[l], num[r]])
while l < r and num[l] == num[l + 1]: l = l + 1 # remove duplicate
while l < r and num[r] == num[r - 1]: r = r - 1 # remove duplicate
l, r = l + 1, r - 1
elif sum < target:
l = l + 1
else:
r = r - 1
return ans
Tag: list, math, sort
20. Valid Parentheses
Given a string containing just the characters ’(‘, ’)’, ’{‘, ’}’, ’[‘ and ’]’, determine if the input string is valid. The brackets must close in the correct order, ”()” and ”()[]{}” are all valid but ”(]” and ”([)]” are not.
Python solution:
class Solution:
# @return a boolean
def isValid(self, s):
stack = []
dict = {"]":"[", "}":"{", ")":"("}
for char in s:
if char in dict.values():
stack.append(char)
elif char in dict.keys():
if stack == [] or dict[char] != stack.pop():
return False
else:
return False
return stack == []
C solution: #define STACK_DEPTH 1000 typedef struct{ char a[STACK_DEPTH]; int top; }stack_t;
bool isValid(char* s)
{
stack_t st;
st.top=0;
for(int i=0;i<strlen(s);i++)
{
if((s[i]=='(')||(s[i]=='{')||(s[i]=='['))
{
st.a[st.top]=s[i];
st.top=st.top+1;
}
else if(s[i]==')')
{
if(st.a[st.top-1]=='(')
{
st.a[st.top]=' ';
st.top=st.top-1;
}
else
{
return false;
}
}
else if(s[i]=='}')
{
if(st.a[st.top-1]=='{')
{
st.a[st.top]=' ';
st.top=st.top-1;
}
else
{
return false;
}
}
else if(s[i]==']')
{
if(st.a[st.top-1]=='[')
{
st.a[st.top]=' ';
st.top=st.top-1;
}
else
{
return false;
}
}
else
return false;
}
if(st.top==0)
return true;
else
return false;
} Tag: stack, dict
22. Generate Parentheses
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses. For example, given n = 3, a solution set is: [ “((()))”, “(()())”, “(())()”, “()(())”, “()()()” ]
class Solution
{
private:
void dfs(vector<string>& s,string p,int n,int m)
{
///已经构造好的字符串为p，还剩n个'('可用，并且必须要用m个')'。
if(n==0&&m==0)
{
s.push_back(p);
return ;
}
if(m>0) dfs(s,p+')',n,m-1);
if(n>0) dfs(s,p+'(',n-1,m+1);
}
public:
vector<string> generateParenthesis(int n)
{
vector<string>s;
dfs(s,"",n,0);
return s;
}
};
Tag: dfs, recursion