Java基础算法每日5道详解

拼搏现实的明天。 2023-09-23 18:26 80阅读 0赞

# 58. Length of Last Word 最后一个字的长度 #

> Given a string `s` consisting of words and spaces, return *the length of the **last** word in the string.*  
> A **word** is a maximal substring consisting of non-space characters only.  
> 给定一个由单词和空格组成的字符串 s，返回字符串中最后一个单词的长度。  
> 单词是仅由非空格字符组成的最大子串。

**Example 1:**

Input: s = "Hello World"
    Output: 5
    Explanation: The last word is "World" with length 5.

**Example 2:**

Input: s = "   fly me   to   the moon  "
    Output: 4
    Explanation: The last word is "moon" with length 4.

**Example 3:**

Input: s = "luffy is still joyboy"
    Output: 6
    Explanation: The last word is "joyboy" with length 6.

## 代码运行 ##

public class lengthOfLastWord {
        
        public static void main(String[] args) {
        
            String s = "luffy is still joyboy";
           int result = lengthOfLastWord(s);
            System.out.println(result);
        }
        public static int lengthOfLastWord(String s) {
        
            String[] words = s.split(" "); // 拆分字符串为单词数组
            if (words.length == 0) {
        
                return 0; // 如果单词数组为空，返回0
            }
            return words[words.length - 1].length(); // 返回最后一个单词的长度
        }
    
    }

## 运行结果 ##

## leetcode代码 ##

public int lengthOfLastWord(String s) {
        
        if (s == null || s.length() == 0) return 0;
        int result = 0, i = s.length() - 1;
        while (i >= 0 && s.charAt(i) == ' ') i--;   // Skip all whitespaces at the end of s.
        while (i >= 0 && s.charAt(i) != ' ') {
              // Count the number of consecutive non-whitespace characters.
            result++;
            i--;
        }
        return result;
    }

# 66. Plus One 加一 #

> You are given a **large integer** represented as an integer array `digits`, where each `digits[i]` is the `ith` digit of the integer. The digits are ordered from most significant to least significant in left-to-right order. The large integer does not contain any leading `0`’s.  
> 给定一个表示为整数数组digits 的大整数，其中每个digits\[i\] 是整数的第i 个数字。 数字按从左到右的顺序从最高有效到最低有效排序。 大整数不包含任何前导 0。

**Example 1:**

Input: digits = [1,2,3]
    Output: [1,2,4]
    Explanation: The array represents the integer 123.
    Incrementing by one gives 123 + 1 = 124.
    Thus, the result should be [1,2,4].

**Example 2:**

Input: digits = [4,3,2,1]
    Output: [4,3,2,2]
    Explanation: The array represents the integer 4321.
    Incrementing by one gives 4321 + 1 = 4322.
    Thus, the result should be [4,3,2,2].

**Example 3:**

Input: digits = [9]
    Output: [1,0]
    Explanation: The array represents the integer 9.
    Incrementing by one gives 9 + 1 = 10.
    Thus, the result should be [1,0].

## leetcode代码 ##

public int[] plusOne(int[] digits) {
        
        for (int i = digits.length - 1; i >=0; i--) {
        
            if (digits[i] != 9) {
        
                digits[i]++;
                break;
            } else {
        
                digits[i] = 0;
            }
        }
        if (digits[0] == 0) {
        
            int[] res = new int[digits.length+1];
            res[0] = 1;
            return res;
        }
        return digits;
    }
    
    
    class Solution {
        
        public int[] plusOne(int[] digits) {
        
            
        int n = digits.length;
        for(int i=n-1; i>=0; i--) {
        
            if(digits[i] < 9) {
        
                digits[i]++;
                return digits;
            }
            
            digits[i] = 0;
        }
        
        int[] newNumber = new int [n+1];
        newNumber[0] = 1;
        
        return newNumber;
            
        }
    }

# 67. Add Binary 添加二进制 #

> Given two binary strings a and b, return their sum as a binary string.

**Example 1:**

Input: a = "11", b = "1"
    Output: "100"

**Example 2:**

Input: a = "1010", b = "1011"
    Output: "10101"

## leetcode代码 ##

public String addBinary(String a, String b) {
        
            StringBuilder sb = new StringBuilder(); 
            //Google immutability or string vs stringbuilder if you don't know why we use this instead of regular string
            
            int i = a.length() - 1, j = b.length() -1, carry = 0; 
            //two pointers starting from the back, just think of adding two regular ints from you add from back
            
            while (i >= 0 || j >= 0) {
        
                int sum = carry; 
                //if there is a carry from the last addition, add it to carry 
                
                if (j >= 0) sum += b.charAt(j--) - '0'; 
                //we subtract '0' to get the int value of the char from the ascii
                
                if (i >= 0) sum += a.charAt(i--) - '0';
                sb.append(sum % 2); 
                //if sum==2 or sum==0 append 0 cause 1+1=0 in this case as this is base 2 (just like 1+9 is 0 if adding ints in columns)
                
                carry = sum / 2; 
                //if sum==2 we have a carry, else no carry 1/2 rounds down to 0 in integer arithematic
                
            }
            if (carry != 0) sb.append(carry); //leftover carry, add it
            return sb.reverse().toString();
        }

# 69. Sqrt(x) 平方（x） #

> Given a non-negative integer `x`, compute and return *the square root of* `x`.  
> Since the return type is an integer, the decimal digits are **truncated**, and only **the integer part** of the result is returned.  
> **Note:** You are not allowed to use any built-in exponent function or operator, such as `pow(x, 0.5)` or `x ** 0.5`.  
> 给定一个非负整数 x，计算并返回 x 的平方根。  
> 由于返回类型是整数，所以十进制数字被截断，只返回结果的整数部分。  
> 注意：您不能使用任何内置的指数函数或运算符，例如 pow(x, 0.5) 或 x \*\* 0.5。

**Example 1:**

Input: x = 4
    Output: 2

**Example 2:**

Input: x = 8
    Output: 2
    Explanation: The square root of 8 is 2.82842..., and since the decimal part is truncated, 2 is returned.

## leetcode代码 ##

public int mySqrt(int x) {
        
    	if (x == 0) return 0;
    	for (int i = 1; i <= x / i; i++)
    		if (i <= x / i && (i + 1) > x / (i + 1))// Look for the critical point: i*i <= x && (i+1)(i+1) > x
    			return i;
    	return -1;
    }
    
    
    Solution1 - Binary Search Solution: Time complexity = O(lg(x)) = O(32)=O(1)
    
    public int mySqrt(int x) {
        
    	if (x == 0) return 0;
    	int start = 1, end = x;
    	while (start < end) {
         
    		int mid = start + (end - start) / 2;
    		if (mid <= x / mid && (mid + 1) > x / (mid + 1))// Found the result
    			return mid; 
    		else if (mid > x / mid)// Keep checking the left part
    			end = mid;
    		else
    			start = mid + 1;// Keep checking the right part
    	}
    	return start;
    }

# 70. Climbing Stairs 爬楼梯 #

> You are climbing a staircase. It takes `n` steps to reach the top.  
> Each time you can either climb `1` or `2` steps. In how many distinct ways can you climb to the top?  
> 你正在爬楼梯。 到达顶峰需要 n 步。  
> 每次您可以爬 1 或 2 级台阶。 你可以通过多少种不同的方式爬上顶峰？

**Example 1:**

Input: n = 2
    Output: 2
    Explanation: There are two ways to climb to the top.
    1. 1 step + 1 step
    2. 2 steps

**Example 2:**

Input: n = 3
    Output: 3
    Explanation: There are three ways to climb to the top.
    1. 1 step + 1 step + 1 step
    2. 1 step + 2 steps
    3. 2 steps + 1 step

## leetcode代码 ##

class Solution {
        
        public int climbStairs(int n) {
        
            if (n <= 1) {
        
                return 1;
            }
            
            int[] dp = new int[n + 1];
            dp[1] = 1;
            dp[2] = 2;
    
            for (int i = 3; i <= n; i++) {
        
                dp[i] = dp[i - 1] + dp[i - 2];
            }
    
            return dp[n];
        }
    }