原創公衆号：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();
}
} 
文本左右對齊
描述
給定一個單詞數組和一個長度 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 "
] 分析
字元串處理的貪心題，首先要知道以下幾點要求：
- 如果不是一個單詞，不是最後一行，每一行最左側和最右側都有單詞。
- 每一行盡量長，能夠包容夠多的單詞，但每兩個單詞之間至少有一個空格
- 空格要勻稱，如果無法絕對相等那麼偏左的要多一點
在具體處理上也很容易，可以用一個數字統計目前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();
} 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;
} 爬樓梯
分析：
入門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];
} 結語
原創不易，bigsai請你幫兩件事幫忙一下:
- star支援一下， 您的肯定是我在平台創作的源源動力。
- 微信搜尋「bigsai」，關注我的公衆号，不僅免費送你電子書