當前位置:網站首頁>LeetCode編程題

LeetCode編程題

2022-01-27 18:52:27 veno_冰

LeetCode編程題1

在這裏插入圖片描述

class Solution {
    
    public int[][] transpose(int[][] A) {
    
        //獲取傳入數組的列數
        int row=A[0].length;
        //獲取傳入數組的行數
        int column=A.length;
        //返回數組的行數為傳入數組的列數,列數為傳入數組的行數
        int data[][]=new int[row][column];

        //判斷是否為方形矩陣,為方形矩陣對稱交換,否則順序交換
        if(row==column){
    
            for(int i=0;i<row;i++){
    
                for(int j=i;j<column;j++){
    
                    data[i][j]=A[j][i];
                    data[j][i]=A[i][j];
                }
            }
        }
        else{
    
            for(int i=0;i<row;i++){
    
                for(int j=0;j<column;j++){
    
                    data[i][j]=A[j][i];
                }
            }
        }  
        return data;      
    }
}

在這裏插入圖片描述

class Solution {
    
//將輸入數據去重後從1遍曆判斷該數是否在數組中,不在就返回該最小的數,否則返回數組的長度加1
    public int firstMissingPositive(int[] nums) {
    
    //獲取數組的長度存入去重的set集合中,從1遍曆判斷是否存在該數組中
        int len = nums.length;
        Set<Integer> hashSet = new HashSet<>();
        for (int num : nums) {
    
            hashSet.add(num);
        }
        //不存在就返回該數,否則就返回數組的長度加1
        for (int i = 1; i <= len; i++) {
    
            if (!hashSet.contains(i))
                return i;
        }
        return len + 1;
    }
}

在這裏插入圖片描述

class Solution {
    
    public int[] twoSum(int[] nums, int target) {
    
		//循環數組判斷數組兩兩相加是否等於目標數,相等返回
        int len = nums.length;
        int[] result = new int[2];
        for (int i = 0; i < len - 1; i++) {
    
            for (int j = i + 1; j < len; j++) {
    
                if (nums[i] + nums[j] == target) {
    
                    result[0] = i;
                    result[1] = j;
                    break;
                }
            }
        }
        return result;
    }
}

LeetCode編程題2

在這裏插入圖片描述思路: 循環遍曆字符串,遇到?就獲取?兩邊的字符,如果?比特於第一比特則?左邊的字符為"",同理若?在最後右邊的字符也為"",然後在從字符a遍曆只要遍曆的字符不等於?左右兩邊的字符就替換該字符,遍曆完後輸出。

class Solution {
    
    public String modifyString(String s) {
    
        char[] ch = s.toCharArray();

        for (int i = 0; i < ch.length; i++) {
    
            if (ch[i] == '?') {
    
                //前面一個字符 如果當前是第0個的話 字符就為‘ ’
                char ahead = i == 0 ? ' ' : ch[i - 1];
                //後面一個字符 如果當前是最後一個的話 字符就為‘ ’
                char behind  = i == ch.length - 1 ? ' ' : ch[i + 1];
                //從a開始比較 如果等於前面或者後面的話 就+1
                char temp = 'a';
                while (temp == ahead || temp == behind ) {
    
                    temp++;
                }
                //找到目標字符後 做替換
                ch[i] = temp;
            }
        }
        return new String(ch);
    }
}

在這裏插入圖片描述
思路: 5的二進制為101,它的反碼是111與101异或得到的,所以找到比N大的每比特都為1的數,與N進行异或就可以得到該數的反碼。

class Solution {
    
    public int bitwiseComplement(int N) {
    
        int num = 1;
        while(num < N){
    
        	//每次左移一比特,加一保證每比特都為1
            num = (num << 1) + 1;
        }
        //异或得該數的反碼
        return N ^ num;
    }
}

在這裏插入圖片描述
思路: 循環判斷首尾字符是否相等,遇到非數字和字母就跳過該字符,如果其中有一個字符不相等就不是回文字符串返回false,結束程序,相等的話首字符遞增,尾字符遞减,繼續循環判斷。

class Solution {
    
    public boolean isPalindrome(String s) {
    
        String str = s.toUpperCase();
        int l=0,r=str.length()-1;

        while(l < r) {
    
            // 判斷當期是否為數字和字母,不是的話,就跳過該字符l向右移動
            while (l < r && !Character.isLetterOrDigit(str.charAt(l))) {
    
                l++;
            }

            // 判斷當期是否為數字和字母,不是的話,就跳過該字符r向左移動
            while (l < r && !Character.isLetterOrDigit(str.charAt(r))) {
    
                r--;
            }

            // 判斷l和r所指向的字符是否相等,不相等,則不是回文串,相等就繼續判斷下一個字符
            if (str.charAt(l) != str.charAt(r)) {
    
                return false;
            }
            l++;
            r--;
        }
        //循環完沒結果則代錶該字符串是回文
        return true;
    }
}

LeetCode編程題3

在這裏插入圖片描述
思路: 循環該數每次獲取該數的最後一比特,並累乘十,反序,之後去除最後一比特,在繼續循環直到為0為止。

class Solution {
    
    public int reverse(int x) {
    
        int result = 0;
        while(x != 0) {
    
            //循環判斷改值是否溢出
            if(result < -214748364 || result > 214748364 ) {
    
                return 0;
            }
            //反序計算該數
            result = result * 10 + x % 10;
            x /= 10;
        }
        return result;
    }
}

在這裏插入圖片描述
思路: 首先判斷該數是否小於0,小於0直接返回false結束程序,否則就按上一題的思路求該數的反序,在與正序數比較,相等返回true,否則返回false.

class Solution {
    
    public boolean isPalindrome(int x) {
    
        //小於0直接返回false,不回文
         if(x < 0) {
    
           return false;
        }
        //大於0求反序判斷與正序是否相等,相等返回true,不相等返回false
        int reverseNum = 0,temp = x;
        while(temp != 0) {
    
            reverseNum =  reverseNum * 10 + temp % 10;
            temp /= 10;
        }
        return x==reverseNum ? true : false;
    }
}

在這裏插入圖片描述
思路: (參考)

  1. 羅馬數字由 I,V,X,L,C,D,M 構成;
  2. 當小值在大值的左邊,則减小值,如 IV=5-1=4;
  3. 當小值在大值的右邊,則加小值,如 VI=5+1=6;
  4. 由上可知,右值永遠為正,因此最後一比特必然為正。
    一言蔽之,把一個小值放在大值的左邊,就是做减法,否則為加法。

在代碼實現上,可以往後看多一比特,對比當前比特與後一比特的大小關系,從而確定當前比特是加還是减法。當沒有下一比特時,做加法即可。

也可保留當前比特的值,當遍曆到下一比特的時,對比保留值與遍曆比特的大小關系,再確定保留值為加還是减。最後一比特做加法即可。

import java.util.*;

class Solution {
    
    public int romanToInt(String s) {
    
        int sum = 0;
        int preNum = getValue(s.charAt(0));
        for(int i = 1;i < s.length(); i ++) {
    
            int num = getValue(s.charAt(i));
            if(preNum < num) {
    
                sum -= preNum;
            } else {
    
                sum += preNum;
            }
            preNum = num;
        }
        sum += preNum;
        return sum;
    }
    
    private int getValue(char ch) {
    
        switch(ch) {
    
            case 'I': return 1;
            case 'V': return 5;
            case 'X': return 10;
            case 'L': return 50;
            case 'C': return 100;
            case 'D': return 500;
            case 'M': return 1000;
            default: return 0;
        }
    }
}

LeetCode編程題4

在這裏插入圖片描述
思路: 取出數組數組中的第一個字符串,將這個字符串與剩下的所有字符串比較,如與第二個字符串比較,獲取這兩個字符串中較短的長度,作為一個循環的條件,每次循環比較兩個字符串的字符是否相等,一直找到最長前綴,後在截取字符串返回,在重複同樣的步驟,即可。

class Solution {
    
    public String longestCommonPrefix(String[] strs) {
    
        if(strs == null || strs.length == 0){
    
            return "";
        }
        String prefix = strs[0];
        int count = strs.length;
        for(int i=1; i<count; i++){
    
        	//比較兩字符串的字符是否有相同的前綴
            prefix = longestPrefix(prefix,strs[i]);
            if(prefix.length() == 0){
    
                break;
            }
        }
        return prefix;
    }

    public String longestPrefix(String str1,String str2){
    
        int min = Math.min(str1.length(),str2.length());
        int index = 0;
        while(index < min && str1.charAt(index)==str2.charAt(index)){
    
            index++;
        }
        return str1.substring(0,index);
    }
}

在這裏插入圖片描述
思路: 首先判斷該字符串是否為偶數,不為偶數返回false,否則繼續判斷,在定義一個棧,每次遇到左括號就入棧,遇到右括號就判斷與當前棧頂的元素是否相等,相等就出棧,判斷下一個,否則就返回false結束程序運行,直到棧為空則括號全匹配。

class Solution {
    
    public boolean isValid(String s) {
    
        //字符串為奇數返回false
         if(s.length()%2==0){
    
            Stack<Character> stack=new Stack<>();
            //左括號入棧,右括號出棧判斷
            for(int i=0;i<s.length();i++){
    
                char c=s.charAt(i);
                if(c=='('||c=='['||c=='{'){
    
                    stack.push(c);
                }
                else if(c==')'){
    
                    if(!stack.isEmpty()&&stack.peek()=='('){
    stack.pop();}
                    else{
    return false;}
                }
                else if(c=='}'){
    
                    if(!stack.isEmpty()&&stack.peek()=='{'){
    stack.pop();}
                    else{
    return false;}
                }
                else{
    
                    if(!stack.isEmpty()&&stack.peek()=='['){
    stack.pop();}
                    else{
    return false;}
                }
            }
            return stack.isEmpty();
        }
        return false;
    }
}

在這裏插入圖片描述
思路:
我們可以如下遞歸地定義兩個鏈錶裏的 merge 操作(忽略邊界情况,比如空鏈錶等):

list1[0]+merge(list1[1:],list2) list1[0]<list2[0]
list2[0]+merge(list1,list2[1:]) otherwise
也就是說,兩個鏈錶頭部值較小的一個節點與剩下元素的 merge 操作結果合並。

如果 l1 或者 l2 一開始就是空鏈錶 ,那麼沒有任何操作需要合並,所以我們只需要返回非空鏈錶。否則,我們要判斷 l1 和 l2 哪一個鏈錶的頭節點的值更小,然後遞歸地决定下一個添加到結果裏的節點。如果兩個鏈錶有一個為空,遞歸結束。

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */
class Solution {
    
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    
        if(l1 == null) {
    
            return l2;
        }
        if(l2 == null) {
    
            return l1;
        }

        if(l1.val < l2.val) {
    
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
    
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }
}

LeetCode編程題5

在這裏插入圖片描述
思路: 數組完成排序後,我們可以放置兩個指針 i 和 j,其中 i是慢指針,而 j 是快指針。只要 nums[i] = nums[j],我們就增加 j以跳過重複項。
當我們遇到 nums[j] != nums[i]時,跳過重複項的運行已經結束,因此我們必須把它(nums[i])的值複制到 nums[i + 1]。然後遞增 i,接著我們將再次重複相同的過程,直到 j 到達數組的末尾為止。

class Solution {
    
    public int removeDuplicates(int[] nums) {
    
        if(nums.length == 0) return 0;
        //定義雙指針,i為慢指針,j為快指針,只要兩個數字不相等就將j對應的值賦值給i
        int i = 0;
        for(int j=1; j < nums.length; j++) {
    
            if(nums[i] != nums[j]){
    
                nums[++i] = nums[j];
            }
        }
        return i+1;
    }
}

在這裏插入圖片描述
思路: 與上一題相同

class Solution {
    
    public int removeElement(int[] nums, int val) {
    
        //定義一個雙指針
        int i = 0;
        for(int j =0; j<nums.length; j++){
    
            if(nums[j] != val){
    
                nums[i++] = nums[j];
            }
        }
        return i;
    }
}

在這裏插入圖片描述
**思路:**沿著字符換逐步移動滑動窗口,將窗口內的子串與 needle 字符串比較。

class Solution {
    
    public int strStr(String haystack, String needle) {
    
        int l = haystack.length(), n = needle.length();
        //每次截取比較是否與needle相等,相等就返回下標
        for(int i =0; i< l - n + 1; i++){
    
            if(haystack.substring(i,i + n).equals(needle)){
    
                return i;
            }
        }
        return -1;
    }
}

LeetCode編程題6(1)

在這裏插入圖片描述
思路: 二分查找

class Solution {
    
    public int searchInsert(int[] nums, int target) {
    
        //定義左右指針實現二分查找,每次拿左右指針的中間值比較
        int index = nums.length,l = 0,r = nums.length -1;
        while(l <= r) {
    
            int mid = (l + r) / 2;
            if(nums[mid] < target) {
    
                l = mid + 1;
            }else{
    
                r = mid -1;
            }
        }
        return l;
    }
}

在這裏插入圖片描述
思路: 遞歸加指針

class Solution {
    
    //層層遞進想到遞歸
    public String countAndSay(int n) {
    
        if(n==1)  //遞歸結束條件
            return "1";
        String str = countAndSay(n-1); //上一輪的輸出是是下一輪的輸入
        StringBuffer ans = new StringBuffer(); //存放當前輪答案
        int len = str.length();
        int start = 0; //記錄開始下標
        for(int i=1;i<len+1;i++){
    
            if(i==len) //最後一個元素單獨處理
                ans.append(i - start).append(str.charAt(start));
            else if(str.charAt(i) != str.charAt(start)){
      //元素改變觸發函數
                ans.append(i - start).append(str.charAt(start));
                start = i; //更新起始下標
            }
        }
        return ans.toString(); 
    }
}

在這裏插入圖片描述
思路:

class Solution {
    
    public int maxSubArray(int[] nums) {
    
        int ans = nums[0];
        int sum = 0;
        for(int num: nums) {
    
            if(sum > 0) {
    
                sum += num;
            } else {
    
                sum = num;
            }
            ans = Math.max(ans, sum);
        }
        return ans;
    }
}

LeetCode編程題7(2)

在這裏插入圖片描述
思路: 從右向左遍曆,從第一個不是空格的字符開始計數,一旦開始計數,再遇到空格就結束了

class Solution {
    
    //從右向左遍曆,從第一個不是空格的字符開始計數,一旦開始計數,再遇到空格就結束了
    public int lengthOfLastWord(String s) {
    
        if(s == null || s.length() == 0){
    
            return 0;
        }
        int count = 0;
        for(int i=s.length() - 1; i>=0; i--){
    
            if(s.charAt(i) == ' '){
    
                if(count == 0) continue;
                break;
            }
            count++;
        }
        return count;
    }
}

在這裏插入圖片描述

class Solution {
    
    public String addBinary(String a, String b) {
    
        int alength = a.length(), blength = b.length();
		while (alength > blength)//補齊
		{
    
			b = '0' + b;
			blength++;
		}
		while (alength < blength)
		{
    
			a = '0' + a;
			alength++;
		}
        int carry = 0;
        StringBuilder str = new StringBuilder();
        for(int i=a.length() - 1; i>=0; i--){
    
            int num = (a.charAt(i) - '0') + (b.charAt(i) - '0') + carry;
            carry = num / 2;
            str.append(num % 2);
        }
        if(carry == 1){
    
            str.append("1");
             return str.reverse().toString();
        }
        return str.reverse().toString();
    }
}

在這裏插入圖片描述
**思路:**二分查找

class Solution {
    
    public int mySqrt(int x) {
    
        // 注意:針對特殊測試用例,例如 2147395599
        // 要把搜索的範圍設置成長整型
        // 為了照顧到 0 把左邊界設置為 0
        // 為了照顧到 1 把右邊界設置為 x / 2 + 1
        long left = 0,right = (x / 2) +1;
        while(left < right){
    
            long mid = (left + right +1) / 2;
            if(mid * mid > x){
    
                right = mid-1;
            }else{
    
                left = mid;
            }
        }
        return (int)left;
    }
}

LeetCode編程題8(3)

LeetCode編程題9(3.13)

在這裏插入圖片描述
思路:
我們用 f(x) 錶示爬到第 x 級臺階的方案數,考慮最後一步可能跨了一級臺階,也可能跨了兩級臺階,所以我們可以列出如下式子:

f(x) = f(x - 1) + f(x - 2)

class Solution {
    
public: int climbStairs(int n) {
    
        //初始化p,q為0,r為1
        int p = 0,q = 0,r = 1;
        //循環帶入公式計算
        for(int i=1; i<=n;i++){
    
           p = q;
           q = r;
           r = p + q;
        }
        return r;
    }
};

在這裏插入圖片描述
思路:遍曆鏈錶,判斷當前和下一個值是否為空,為空就直接返回,不為空就繼續判斷當前節點的值和下一個節點的值是否相等,相等就將當前節點的指向,指向下一個節點的下一個,不相等的換就替換到下一個節點,繼續遍曆。

class Solution {
    
    public ListNode deleteDuplicates(ListNode head) {
    
        ListNode cur = head;
        //判斷當前節點和下一個節點是否為空
        while(cur != null && cur.next != null) {
    
            //判斷當前是與下一個值是否相等相等就更換節點的指向,並清空下一個節點的指向
            if(cur.val == cur.next.val){
    
                ListNode node = cur.next;
                cur.next = node.next;
                node.next = null;
            }else{
    
                cur = cur.next;
            }
        }
        return head;
    }
}

在這裏插入圖片描述
思路:
定義三個指針,從兩個數組的後面開始比較賦值

class Solution {
    
    public void merge(int[] nums1, int m, int[] nums2, int n) {
    
        //定義三個指針,從後面開始比較
        int p1 = m - 1,p2 = n- 1,p = m + n - 1;
        //結束條件為p2<0
        while(p2 >= 0) {
    
            if(p1 >= 0 && nums1[p1] > nums2[p2]){
    
                nums1[p--] = nums1[p1--];
            }else{
    
                nums1[p--] = nums2[p2--];
            }
        }
    }
}

LeetCode編程題9(3.20)

版權聲明
本文為[veno_冰]所創,轉載請帶上原文鏈接,感謝
https://cht.chowdera.com/2022/01/202201271852268306.html

隨機推薦