LeetCode 67二進制求和&68文本左右對齊&69x的平方根

原創公眾號：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請你幫兩件事幫忙一下:

1. star支持一下， 您的肯定是我在平臺創作的源源動力，

2. 微信搜索「bigsai」，關注我的公眾號，不僅免費送你電子書，我還會第一時間在公眾號分享知識技術，加我還可拉你進力扣打卡群一起打卡LeetCode，

記得關注、咱們下次再見！