说明:本人能力有限,部分算法效率较差,各位如有好的思路,请留言回复。
(相关资料图)
Integer to English Words:
解题思路:由于最大输入值不可能大于231- 1.即2147483647,第十位:Billion;第七位:Million;第四位:Thousand;第一位:个位。由此可能观察到,将输入值分成四个小组,每三个一组,从低到高依次输入四个小组中。然分别对每个小组中处理,分别百位,十位,个位。
Java实现:
publicclass Solution {
public String numberToWords(int num) {
if(num==0) return "Zero";
int[] grp=new int[4];
String[] strNum=new String[4];
strNum[0]="";
strNum[1]="";
strNum[2]="";
strNum[3]="";
int i=0;
while(num!=0){
int mod=num%1000;
grp[i++]=mod;
num=num/1000;
}
for(int j=i;j<GRP.LENGTH;J++)< strong="">
grp[j]=0;
for(int k=0;k<GRP.LENGTH;K++){
int third=grp[k]/100;
if(third!=0){
switch(third){
case1:strNum[k]+="One ";break;
case 2:strNum[k]+="Two";break;
case 3:strNum[k]+="Three";break;
case 4:strNum[k]+="Four";break;
case 5:strNum[k]+="Five";break;
case 6:strNum[k]+="Six";break;
case 7:strNum[k]+="Seven";break;
case 8:strNum[k]+="Eight";break;
case 9:strNum[k]+="Nine";break;
}
strNum[k]+="Hundred ";
}
grp[k]=grp[k]%100;
int second=grp[k]/10;
if(second!=0){
switch(second){
case 1:
switch(grp[k]){
case10:strNum[k]+="Ten ";break;
case11:strNum[k]+="Eleven ";break;
case12:strNum[k]+="Twelve ";break;
case13:strNum[k]+="Thirteen ";break;
case14:strNum[k]+="Fourteen ";break;
case15:strNum[k]+="Fifteen ";break;
case16:strNum[k]+="Sixteen ";break;
case17:strNum[k]+="Seventeen ";break;
case18:strNum[k]+="Eighteen ";break;
case19:strNum[k]+="Nineteen ";break;
}
break;
case 2:strNum[k]+="Twenty ";break;
case 3:strNum[k]+="Thirty ";break;
case 4:strNum[k]+="Forty ";break;
case 5:strNum[k]+="Fifty ";break;
case 6:strNum[k]+="Sixty ";break;
case 7:strNum[k]+="Seventy ";break;
case 8:strNum[k]+="Eighty ";break;
case 9:strNum[k]+="Ninety ";break;
}
}
if(second!=1){
grp[k]=grp[k]%10;
int first=grp[k];
if(first!=0){
switch(first){
case1:strNum[k]+="One ";break;
case 2:strNum[k]+="Two";break;
case 3:strNum[k]+="Three";break;
case 4:strNum[k]+="Four";break;
case 5:strNum[k]+="Five";break;
case 6:strNum[k]+="Six";break;
case 7:strNum[k]+="Seven";break;
case 8:strNum[k]+="Eight";break;
case 9:strNum[k]+="Nine";break;
}
}
}
if(strNum[k].length()>0){
switch(k){
case 1:strNum[k]+="Thousand";break;
case 2:strNum[k]+="Million";break;
case 3:strNum[k]+="Billion";break;
}
}
}
String res=strNum[3]+strNum[2]+strNum[1]+strNum[0];
return res.substring(0,res.length()-1);
}
}
url:https://leetcode.com/problems/integer-to-english-words/
2、Missing Number
解题思路:利用输入漏掉数字的数组所有数字之和和完全数组之和,做减法,即差值即是所要的。
Java代码实现:
public class Solution {
public intmissingNumber(int[] nums) {
int sum1=0;
int sum=0;
for(inti=0;i<NUMS.LENGTH+1;I++)< h3="">
sum1=sum1+i;
for(inti=0;i<NUMS.LENGTH;I++)< h3="">
sum=sum+nums[i];
return sum1-sum;
}
}
url:https://leetcode.com/problems/missing-number/
3,Ugly Number
解题思路:分别让输入值给2、3、5做除法,直至不存在上述数字的倍数为止。
Java代码实现:
public class Solution {
public booleanisUgly(int num) {
if(num==0) returnfalse;
while(num%2==0)num=num/2;
while(num%3==0)num=num/3;
while(num%5==0)num=num/5;
if(num==1) returntrue;
else return false;
}
}
url:https://leetcode.com/problems/ugly-number/
4、SingleNumber III
解题思路:该题利用一个集合存储遍历的数字,如何初始该集合中没有则加入,有的话则删除,最后集合里面的数字,即是所要求的。
Java代码实现:
public class Solution {
public int[]singleNumber(int[] nums) {
Set set=newHashSet();
for(inti=0;i<NUMS.LENGTH;I++){
if(!set.contains(nums[i])) set.add(nums[i]);
else set.remove(nums[i]);
}
int [] re=newint[set.size()];
Iteratorit=set.iterator();
int i=0;
while(it.hasNext()){
re[i++]=it.next();
}
//System.out.print(re);
return re;
}
}
url:https://leetcode.com/problems/single-number-iii/
5、AddDigits
解题思路:传统方法,按位相加,循环,直至只有一位为止。
Java代码实现:
public class Solution {
public intaddDigits(int num) {
int sum=0;
//System.out.println(num);
while(num/10>0){
StringstrNum=String.valueOf(num);
//System.out.println(strNum.length());
for(inti=0;i<STRNUM.LENGTH();I++){
sum+=Integer.valueOf(strNum.charAt(i))-48;
//System.out.println(sum);
}
System.out.println(sum);
num=sum;
sum=0;
}
sum=num;
return sum;
}
}
url:https://leetcode.com/submissions/detail/37775675/
6、ValidAnagram
解题思路:该题意思即是两个字符串是否具有相同的字符组成的串,首先记录第一个字符串出现的字符及其个数,然后与第二个字符串想比较。(另一个思路:将两个字符串分别排序,不过耗时。)
Java代码实现:
public class Solution {
public booleanisAnagram(String s, String t) {
if(s.length()!=t.length()) return false;
Mapmap =new HashMap();
for(inti=0;i<S.LENGTH();I++){
String str=String.valueOf(s.charAt(i));
if(map.containsKey(str)) map.put(str,map.get(str)+1);
else map.put(str, 1);
}
for(int i=0;i<T.LENGTH();I++){
String str=String.valueOf(t.charAt(i));
if(map.containsKey(str)) {
map.put(str, map.get(str)-1);
if(map.get(str)==0)map.remove(str);
}
else map.put(str, 1);
}
if(map.isEmpty())return true;
else return false;
}
}
url:https://leetcode.com/problems/valid-anagram/
7、DeleteNode in a Linked List
解题思路:指定删除任一节点,因无头节点指针,实际删除节点即是删除节点的值,所以可以将要删除节点和后继节点的值替换,删除后继节点即可。
Java代码实现:
/**
* Definition forsingly-linked list.
* struct ListNode {
*int val;
*struct ListNode *next;
* };
*/
void deleteNode(struct ListNode* node) {
struct ListNode *p,*q;
p=q=node;
q=p->next;
p->val=q->val;
p->next=q->next;
free(q);
}
url:https://leetcode.com/submissions/detail/37866400/
8、Numberof Digit One
解题思路:0-9中1的个数为1个,而X99..9的1的个数可以通过公式计算:即Math.pow(10, digit-1)+(10-(9-highestDigit))*Math.pow(10,digit-2)*(digit-1);比如8999:10^3+9*10^2*3。由此可以将输入数字分解,比如9548=9000+548=9000+500+48=9000+500+40+8,如此分布计算即可。
Java代码:
public class Solution {
public intcountDigitOne(int n) {
int count=0;
while(n>0){
if(n/10==0) {
count++;
return count;//大于1的个位数只有一个1,返回
}
intdigit=0;//存储数字位数
int num=n;
while(num/10>0){
digit++;
num=num/10; //num最高位数字
}
digit++;
int highestDigit=num;//最高位数字
num=(int) (num*(Math.pow(10, digit-1)))-1;
if(highestDigit==1) {//1为最高位时,-1数字位数将会发生改变
count++;
count+=n-(num+1);
highestDigit=9;
digit--;
}
else{
highestDigit--;
}
count+=Math.pow(10,digit-1)+(10-(9-highestDigit))*Math.pow(10, digit-2)*(digit-1);//如8999计算1的公式
n=n-(num+1);
}
return count;
}
}
url:https://leetcode.com/submissions/detail/37894024/
9、ImplementQueue using Stacks
解题思路:采用两个栈,实现队列,一个用于进栈S1,一个用于出栈和取头元素S2。进栈时必须将S2中元素全部加入S1中,出栈时必须将S1中的元素加入S2中,才可以保证先进先出。判断为空时,S1,S2均为空。
Java代码实现:
class MyQueue {
private Stack stack1;
private Stack stack2;
MyQueue(){
stack1=newStack();
stack2=newStack();
}
// Push element x tothe back of queue.
public void push(intx) {
if(stack2.isEmpty()) stack1.push(x);
else {
while(!stack2.isEmpty()){
stack1.push(stack2.peek());
stack2.pop();
}
stack1.push(x);
}
}
// Removes the elementfrom in front of queue.
public void pop() {
if(stack1.isEmpty()) {
if(!stack2.isEmpty())
stack2.pop();
}
else {
while(!stack1.isEmpty()){
stack2.push(stack1.peek());
stack1.pop();
}
stack2.pop();
}
}
// Get the frontelement.
public int peek() {
if(stack1.isEmpty()) {
if(!stack2.isEmpty())
return (int) stack2.peek();
return -1;
}
else {
while(!stack1.isEmpty()){
stack2.push(stack1.peek());
stack1.pop();
}
return (int) stack2.peek();
}
}
// Return whether thequeue is empty.
public boolean empty(){
if(stack1.isEmpty()&&stack2.isEmpty())return true;
else return false;
}
}
url:https://leetcode.com/submissions/detail/37897765/
10、Power of Two
解题思路:如果一个数是否是2的次方,即如果其对应的二进制数1的个数如果超过1,不是的2的次方,反之才是。
Java代码实现:
public class Solution {
public booleanisPowerOfTwo(int n) {
int count=0;
if(n==1) return true;
if(n<=0) return false;
while(n>0){
int mod=n%2;
if(mod==1) count++;
if(count>1) return false;
n=n/2;
}
return true;
}
}
url:https://leetcode.com/problems/power-of-two/
11、Kth Smallest Element in aBST
解题思路:按树的中序遍历的方式,利用栈实现,第k个出栈的节点即是所求的。
Java代码实现:
/**
* Definition for a binarytree node.
* public class TreeNode {
*int val;
*TreeNode left;
*TreeNode right;
*TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public intkthSmallest(TreeNode root, int k) {
TreeNode p=newTreeNode(0);
p=root;
Stack sk=newStack();
sk.push(p);
while(p.left!=null){
sk.push(p.left);
p=p.left;
}
int i=0;
while(!sk.isEmpty()){
TreeNode q=newTreeNode(0);
q=(TreeNode)sk.pop();
i++;
if(i==k)return q.val;
if(q.right!=null) {
p=q.right;
sk.push(p);
while(p.left!=null){
sk.push(p.left);
p=p.left;
}
}
}
return 0;
}
}
url:https://leetcode.com/submissions/detail/38221838/
12、Invert Binary Tree
解题思路:利用中序遍历的方式,依次交换所遍历节点的左右子树。
Java代码实现:
/**
* Definition for a binarytree node.
* public class TreeNode {
*int val;
*TreeNode left;
*TreeNode right;
*TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public TreeNodeinvertTree(TreeNode root) {
if(root==null)return root;
Stack stack=newStack();
TreeNode p=newTreeNode(0);
stack.push(root);
p=root;
while(p.left!=null){
p=p.left;
stack.push(p);
}
while(!stack.isEmpty()){
TreeNodeq=(TreeNode)stack.pop();
TreeNodetemp=new TreeNode(0);;
temp=q.left;
q.left=q.right;
q.right=temp;
while(q.left!=null){
stack.push(q.left);
q=q.left;
}
}
return root;
}
}
url:https://leetcode.com/problems/invert-binary-tree/
13、Number of 1 Bits
解题思路:32位有符号整数的表示范围:-2147483648—2147483647。32位无符号整数的表示范围:0—2147483647+2147483648。如果输入的无符号数大于2147483647,则会显示成负数,所以当输入数字小于0时,只需加上2147483647+1,之后按照整数求1的个数,此时需要将1的个数加1.
Java代码实现:
public class Solution {
// you need to treat nas an unsigned value
public inthammingWeight(int n) {
int count=0;
if(n==0) return 0;
if(n<0) {
System.out.print(n);
n+=2147483647+1;
System.out.print(n);
count++;
}
while(n!=0){
int mod=n%2;
if(mod==1)count++;
n=n/2;
}
return count;
}
}
url:https://leetcode.com/problems/number-of-1-bits/
14、Reverse Bits
解题思路:该题与上题类似,如果是负数首先转化成正数(+ 2147483647+1),再处理,然后变成2进制数(如果是负数最高位是1),翻转2进制数,变成十进制数,翻转后如果最后位是1,在十进制数基础上加上2147483647+1。
Java代码实现:
public class Solution {
// you need treat n as an unsigned value
public int reverseBits(int n) {
String str="";
if(n==0) return 0;
if(n==-2147483648) return 1;
System.out.println(n);
int m=n;
if(n<0) {
n+=2147483647+1;
//str+="1";
}System.out.println(n);
while(n!=0){
int mod=n%2;
if(mod==1) str="1"+str;
else str="0"+str;
n=n/2;
}
String revString="";
for(int j=str.length();j<32;j++){
str="0"+str;
}
if(m<0)str="1"+str.substring(1,str.length());
for(int i=0;i<STR.LENGTH();I++){
revString=str.charAt(i)+revString;
}
int num=0;
for(inti=revString.length()-1;i>0;i--){
num+=(Integer.valueOf(revString.charAt(i))-48)*(int)Math.pow(2,revString.length()-1-i);
}
if(revString.charAt(0)=="1") {
return2147483647+1+num;
}
return num;
}
}
url:https://leetcode.com/problems/reverse-bits/
版权声明:本文为博主原创文章,未经博主允许不得转载。