LeetCode算法 IntegertoEnglishWords的解题方法

说明：本人能力有限，部分算法效率较差，各位如有好的思路，请留言回复。

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/



版权声明：本文为博主原创文章，未经博主允许不得转载。