LeetCode 67二进制求和&68文本左右对齐&69x的平方根

华为云博客 技术博客 19554 48

原创公众号：bigsai 专注于Java、数据结构与算法，一起进大厂不迷路！
关注后回复进群即可加入力扣打卡群，欢迎划水。近期打卡：
LeetCode 55跳跃游戏&56合并区间&57插入区间
跟我打卡LeetCode 58最后一个单词长度&59螺旋矩阵Ⅱ&60排列序列
跟我打卡LeetCode 61旋转链表&62不同路径&63不同路径 II
打卡LeetCode 65有效数字&66加一 &67二进制求和

二进制求和

给你两个二进制字符串，返回它们的和（用二进制表示）。

输入为 非空 字符串且只包含数字 1 和 0。

示例 1:

输入: a = “11”, b = “1”
输出: “100”

示例 2:

输入: a = “1010”, b = “1011”
输出: “10101”

提示：

每个字符串仅由字符 ‘0’ 或 ‘1’ 组成。
1 <= a.length, b.length <= 10^4
字符串如果不是 “0” ，就都不含前导零。

分析：
思路也很简单，如果不等长找到短的，从右往左遍历叠加进位。然后再处理常得尾遍历地方，具体实现上。先通过交换是的ab字符串其中一个较小，可以用StringBuilder去实现数字叠加。

实现代码：

class Solution { public String addBinary(String a, String b) { StringBuilder stringBuilder=new StringBuilder(); if(a.length()<b.length()) { String team=a; a=b; b=team; } char ach[]=a.toCharArray(); char bch[]=b.toCharArray(); int alen=a.length(),blen=b.length(); int minLen=b.length(); int jinwei=0;//进位 for(int i=0;i<minLen;i++) { char ch1=ach[alen-1-i]; char ch2=bch[blen-1-i]; int va=(ch1-'0')+(ch2-'0')+jinwei; jinwei=va/2; va=va%2; stringBuilder.insert(0,va); } for(int i=0;i<alen-minLen;i++) { char ch1=ach[alen-1-minLen-i]; int va=ch1-'0'+jinwei; jinwei=va/2; va=va%2; stringBuilder.insert(0,va); } if(jinwei==1) stringBuilder.insert(0,1); return stringBuilder.toString(); }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37

在这里插入图片描述

文本左右对齐

描述

给定一个单词数组和一个长度 maxWidth，重新排版单词，使其成为每行恰好有 maxWidth 个字符，且左右两端对齐的文本。
你应该使用“贪心算法”来放置给定的单词；也就是说，尽可能多地往每行中放置单词。必要时可用空格 ’ ’ 填充，使得每行恰好有 maxWidth 个字符。
要求尽可能均匀分配单词间的空格数量。如果某一行单词间的空格不能均匀分配，则左侧放置的空格数要多于右侧的空格数。
文本的最后一行应为左对齐，且单词之间不插入额外的空格。

说明:

单词是指由非空格字符组成的字符序列。
每个单词的长度大于 0，小于等于 maxWidth。
输入单词数组 words 至少包含一个单词。
示例:

输入:
words = ["This", "is", "an", "example", "of", "text", "justification."]
maxWidth = 16
输出:
[ "This is an", "example  of text", "justification.  "
]
示例 2:

输入:
words = ["What","must","be","acknowledgment","shall","be"]
maxWidth = 16
输出:
[
  "What   must   be",
  "acknowledgment  ",
  "shall be "
]
解释: 注意最后一行的格式应为 "shall be " 而不是 "shall be", 因为最后一行应为左对齐，而不是左右两端对齐。 第二行同样为左对齐，这是因为这行只包含一个单词。
示例 3:

输入:
words = ["Science","is","what","we","understand","well","enough","to","explain", "to","a","computer.","Art","is","everything","else","we","do"]
maxWidth = 20
输出:
[
  "Science  is  what we",
  "understand well",
  "enough to explain to",
  "a  computer.  Art is",
  "everything  else  we",
  "do "
]
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38

分析
字符串处理的贪心题，首先要知道以下几点要求：

  • 如果不是一个单词，不是最后一行，每一行最左侧和最右侧都有单词。
  • 每一行尽量长，能够包容够多的单词，但每两个单词之间至少有一个空格
  • 空格要匀称，如果无法绝对相等那么偏左的要多一点

在这里插入图片描述

在具体处理上也很容易，可以用一个数字统计当前List已存字符长度。如果可以存下就加进来，存不下那就处理当前集合然后初始话添加进来。在处理当前集合的时候需要注意空格情况，首先空格要均匀，其次如果不能绝对均匀左侧要比右侧多。

实现代码为：

public static List<String> fullJustify(String[] words, int maxWidth) { List<String>vaList=new ArrayList<String>(); List<String>teamList=new ArrayList<String>(); int strlen=0; for(int i=0;i<words.length;i++) { String str=words[i]; //System.out.println(teamlen+teamList.toString()); if(strlen+str.length()+teamList.size()<=maxWidth) { teamList.add(str); } else { String team=addstr(teamList,words,maxWidth,strlen,false); vaList.add(team); teamList.clear(); teamList.add(str); strlen=0; } strlen+=str.length(); } String team=addstr(teamList,words,maxWidth,strlen,true); vaList.add(team); return vaList; } private static  String addstr(List<String> teamList,String words[], int maxWidth,int strlen,boolean isLast) {//组合成一个字符串返回 //System.out.println(teamList.toString()); StringBuilder sb=new StringBuilder(); if(isLast) { for(String str:teamList) { sb.append(str); sb.append(' '); } if(sb.length()>maxWidth) { return sb.deleteCharAt(maxWidth).toString(); } for(int i=sb.length();i<maxWidth;i++) { sb.append(' '); } } else { //计算空格总数量 int spaceNum=maxWidth-strlen; int aveNum; if(teamList.size()==1) aveNum=1; else  aveNum=spaceNum/(teamList.size()-1); int more=spaceNum-aveNum*(teamList.size()-1);//不能平均分 多出来的空格 sb.append(teamList.get(0)); for(int i=1;i<teamList.size();i++) { int spaceAdd=aveNum; if(more-->0) spaceAdd++; for(int j=0;j<spaceAdd;j++) {sb.append(' ');} sb.append(teamList.get(i)); } for(int i=sb.length();i<maxWidth;i++) { sb.append(' '); } } return sb.toString(); }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74

x的平方根实现 int sqrt(int x) 函数。

计算并返回 x 的平方根，其中 x 是非负整数。
由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

示例 1:

输入: 4
输出: 2

示例 2:

输入: 8
输出: 2
说明: 8 的平方根是 2.82842…,
由于返回类型是整数，小数部分将被舍去。

分析
本题有三个方法求解分别为：

  • 暴力求解(不推荐）
  • 二分查找(推荐)
  • 牛顿迭代法

对于本题，笔者就实现一个二分查找找到这个数字，而牛顿迭代法有空可以自行学习(也不是很难原理可以找专门文章看一看)。

  public int mySqrt(int x) { //二分 int l=0,r=x/2+1; while (l<r) {
	 long mid=(l+r)/2;
	 if(mid*mid<=x)
	 { if((mid+1)*(mid+1)<=x) { l=(int) (mid+1); } else { return (int) mid;
		}
	 }
	 else {
		r=(int) mid;
	}
} return l; 
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21

爬楼梯

在这里插入图片描述
分析：
入门dp，状态转移方程为：初始赋值好后，dp[i]=dp[i-1]+dp[i-2];

 public int climbStairs(int n) { if(n<3)return n;
	 int dp[]=new int[n+1];
	 dp[1]=1;
	 dp[2]=2;
	 for(int i=3;i<n+1;i++)
	 { dp[i]=dp[i-1]+dp[i-2];
	 }
	 return dp[n];
 }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11

结语

原创不易，bigsai请你帮两件事帮忙一下:

  1. star支持一下， 您的肯定是我在平台创作的源源动力。

  2. 微信搜索「bigsai」，关注我的公众号，不仅免费送你电子书，我还会第一时间在公众号分享知识技术。加我还可拉你进力扣打卡群一起打卡LeetCode。

记得关注、咱们下次再见！

image-20201114211553660

文章来源: bigsai.blog.csdn.net，作者：Big sai，版权归原作者所有，如需转载，请联系作者。

原文链接：bigsai.blog.csdn.net/article/details/109922645

（完）