Leetcode刷題第六周

来源:https://www.cnblogs.com/noviceprogrammeroo/archive/2022/12/13/16954874.html
-Advertisement-
Play Games

哈嘍兄弟們 在大家的日常python程式的編寫過程中，都會有自己解決某個問題的解決辦法，或者是在程式的調試過程中，用來幫助調試的程式公式。 小編通過幾十萬行代碼的總結處理，總結出了22個python萬用公式，可以幫助大家解決在日常的python編程中遇到的大多數問題，一起來看看吧。 1、一次性進行多 ...


77、組合

class Solution {
    public List<List<Integer>> result = new ArrayList<List<Integer>>();
    public List<Integer> temp = new LinkedList<>();
    public List<List<Integer>> combine(int n, int k) {
        int index = 1;
        travesal(n,k,index);
        return result;
    }
    public void travesal(int n, int k, int index){
        // 終止條件，得到k個數的組合
        if(temp.size() == k){
            result.add(new ArrayList<>(temp));
            return;
        }
        for (int i = index; i <= n - (k - temp.size()) + 1; i++) {
            temp.add(i);
            travesal(n,k,i+1);//遞歸
            temp.remove(temp.size() - 1);//回溯
        }
    }
}

216、組合總和 III

class Solution {
    public List<List<Integer>> result = new ArrayList<List<Integer>>();
    public List<Integer> temp = new LinkedList<Integer>();
    public List<List<Integer>> combinationSum3(int k, int n) {
        // 邊界條件，不存在有效的組合
        int sum = 0;
        for(int i = 1; i <= k; i++){
            sum += i;
        }
        if(sum > n){
            return result;
        }
        int index = 1;
        combinationSumHelper(k,n,index);
        return result;
    }
    public void combinationSumHelper(int k, int n,int index){
        if(temp.size() == k){
            // 判斷找出的組合是否滿足相加之和為n的條件
            int sum = 0;
            for(Integer i : temp){
                sum += i;
            }
            if(sum == n){
                result.add(new ArrayList<>(temp));
            }
            return;
        }
        for(int i = index; i <= 9 - (k - temp.size()) + 1; i++){
            temp.add(i);
            combinationSumHelper(k,n,i+1);//遞歸
            temp.remove(temp.size() - 1);//回溯
        }
    }
}

17、電話號碼的字母組合

class Solution {
    public List<String> result = new ArrayList<String>();
    public StringBuffer str = new StringBuffer();
    public List<String> letterCombinations(String digits) {
        // 邊界條件
        if(digits == null || digits.length() == 0){
            return result;
        }
        char[] digitsArr = digits.toCharArray();
        // 映射關係
        String[] find = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
        int index = 0;
        letterCombinationsHelper(digitsArr, find, index);
        return result;
    }
    public void letterCombinationsHelper(char[] digitsArr, String[] find, int index){
        if(index == digitsArr.length){
            result.add(new String(str));
            return;
        }
        // 第index個數字對應的字母
        String strTemp = find[digitsArr[index] - '0'];
        for(int i = 0; i < strTemp.length(); i++){
            str.append(strTemp.charAt(i));//加入第Index個數字對應的字母的第i個
            letterCombinationsHelper(digitsArr,find,index+1);
            str.deleteCharAt(str.length() - 1);
        }
    }
}

39、組合總和

class Solution {
    public List<List<Integer>> result = new ArrayList<List<Integer>>();
    public List<Integer> temp = new ArrayList<Integer>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        int sum = 0;
        int index = 0;
        Arrays.sort(candidates);
        combinationSumHelper(candidates,index,sum,target);
        return result;
    }
    public void combinationSumHelper(int[] candidates, int index, int sum,int target){
        if(sum >= target){
            if(sum == target){
                result.add(new ArrayList<Integer>(temp));
            }
            return;
        }
        for(int i = index; i < candidates.length; i++){
            sum += candidates[i];
            temp.add(candidates[i]);
            combinationSumHelper(candidates,i,sum,target);
            temp.remove(temp.size() - 1);
            sum -= candidates[i];
        }
    }
}

40、 組合總和 II

class Solution {
    public List<List<Integer>> result = new ArrayList<List<Integer>>();
    public List<Integer> temp = new ArrayList<Integer>();
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        int sum = 0;
        int index = 0;
        Arrays.sort(candidates);
        combinationSumHelper(candidates, target, index, sum);
        return result;
    }
    public void combinationSumHelper(int[] candidates, int target, int index, int sum){
        if(sum >= target){
            if(sum == target){
                result.add(new ArrayList<>(temp));
            }
            return;
        }
        // 每個數字在每個組合中只能使用一次 
        for(int i = index; i < candidates.length; i++){
            // 去重邏輯，同層剪枝，同枝可取
            if(i > 0 &&i > index && candidates[i] == candidates[i - 1]){
                continue;
            }
            temp.add(candidates[i]);
            sum += candidates[i];
            combinationSumHelper(candidates, target, i + 1, sum);
            temp.remove(temp.size() - 1);
            sum -= candidates[i];
        }
    }
}

131、分割迴文串

class Solution {
    public List<List<String>> result = new ArrayList<List<String>>();
    public List<String> temp = new ArrayList<String>();
    public List<List<String>> partition(String s) {
        int index = 0;
        partitionHelper(s, index);
        return result;
    }
    public void partitionHelper(String s, int index){
        if(index == s.length()){
            result.add(new ArrayList<>(temp));
            return;
        }
        for(int i = index; i < s.length(); i++){
            String s1 = s.substring(index, i + 1);
            if(!check(s1,0,s1.length() - 1)){
                continue;//字元子串不迴文的話直接跳過該次分割方案
            }
            temp.add(s1);
            partitionHelper(s,i+1);
            temp.remove(temp.size() - 1);

        }
    }
    // 判斷是否迴文
    public boolean check(String s1, int left, int right){
        while(left < right){
            if(s1.charAt(left) == s1.charAt(right)){
                left++;
                right--;
            }else{
                return false;
            }
        }
        return true;
    }
}

93、複原 IP 地址

class Solution {
    public List<String> result = new ArrayList<String>();
    public StringBuilder stringBuilder = new StringBuilder();
    public List<String> restoreIpAddresses(String s) {
        restoreIpAddressesHelper(s,0,0);
        return result;
    }
    public void restoreIpAddressesHelper(String s, int index,int count){
        if (index == s.length() && count == 4) {
			result.add(stringBuilder.toString());
			return;
		}
		if (index == s.length() || count == 4) {
			return;
		}
        for (int i = index; i < s.length() && i - index < 3 && Integer.parseInt(s.substring(index, i + 1)) >= 0
				&& Integer.parseInt(s.substring(index, i + 1)) <= 255; i++) {
            if (i + 1 - index > 1 && s.charAt(index) - '0' == 0) {
				continue;
			}
			stringBuilder.append(s.substring(index, i + 1));
			if (count < 3) {
				stringBuilder.append(".");
			}
            count++;
            restoreIpAddressesHelper(s,i+1,count);
            count--;
            stringBuilder.delete(index + count, i + count + 2);
            
        }
    }
}

78、子集

class Solution {
    public List<List<Integer>> result = new ArrayList<List<Integer>>();
    public List<Integer> temp = new ArrayList<Integer>();
    public List<List<Integer>> subsets(int[] nums) {
        subsetsHandler(nums, 0);
        return result;
    }
    public void subsetsHandler(int[] nums, int index){
        if(index == nums.length){
            result.add(new ArrayList<>(temp));
            return;
        }
        result.add(new ArrayList<>(temp));
        for(int i = index; i < nums.length; i++){
            temp.add(nums[i]);
            subsetsHandler(nums,i+1);
            temp.remove(temp.size() - 1);
        }
    }
}

90、子集 II

class Solution {
    public List<List<Integer>> result = new ArrayList<List<Integer>>();
    public List<Integer> temp = new ArrayList<Integer>();
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        subsetsWithDupHandler(nums, 0);
        return result;
    }
    public void subsetsWithDupHandler(int[] nums, int index){
        if(index == nums.length){
            result.add(new ArrayList<>(temp));
            return;
        }
        result.add(new ArrayList<>(temp));
        for(int i = index; i < nums.length; i++){
            //  不能 包含重覆的子集
            if(i > 0 &&i > index && nums[i] == nums[i - 1]){
                continue;
            }
            temp.add(nums[i]);
            subsetsWithDupHandler(nums, i + 1);
            temp.remove(temp.size() - 1);
        }
    }
}

491、遞增子序列

class Solution {
    public List<List<Integer>> result = new ArrayList<List<Integer>>();
    public List<Integer> temp = new ArrayList<Integer>();
    public List<List<Integer>> findSubsequences(int[] nums) {
    // 遞增子序列中 至少有兩個元素
        findSubsequencesHandler(nums, 0);
        return result;
    }
    
    public void findSubsequencesHandler(int[] nums, int index){
        if(temp.size() > 1){
            result.add(new ArrayList<>(temp));
        }
        int[] used = new int[201];
        for(int i = index; i < nums.length; i++){
            if(temp.size() != 0 && nums[i] < temp.get(temp.size() - 1) || (used[nums[i] + 100] == 1)){
                continue;
            }
            used[nums[i] + 100] = 1;
            temp.add(nums[i]);
            findSubsequencesHandler(nums, i + 1);
            temp.remove(temp.size() - 1);
        }
    }
}

46、全排列

class Solution {
    public List<List<Integer>> result = new ArrayList<List<Integer>>();
    public List<Integer> temp = new ArrayList<Integer>();
    public List<List<Integer>> permute(int[] nums) {
// 有序
        int[] used = new int[30];
        permuteHandler(nums, used);
        return result;
    }
    public void permuteHandler(int[] nums, int[] used){
        if(temp.size() == nums.length){
            result.add(new ArrayList<>(temp));
            return;
        }
        for(int i = 0; i < nums.length; i++){
            if(used[nums[i]+10] == 1){
                continue;
            }
            used[nums[i]+10] = 1;
            temp.add(nums[i]);
            permuteHandler(nums,used);
            used[temp.get(temp.size() - 1)+10] = 0;
            temp.remove(temp.size() - 1);

        }
    }
}

47、全排列 II

class Solution {
    public List<List<Integer>> result = new ArrayList<List<Integer>>();
    public List<Integer> temp = new ArrayList<Integer>();
    public List<List<Integer>> permuteUnique(int[] nums) {
        boolean[] used = new boolean[nums.length];
        Arrays.fill(used, false);
        Arrays.sort(nums);
        permuteHandler(nums, used);
        return result;
    }
    public void permuteHandler(int[] nums, boolean[] used){
        if(temp.size() == nums.length){
            result.add(new ArrayList<>(temp));
            return;
        }
        for(int i = 0; i < nums.length; i++){
            if(i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false){
                continue;
            }
            if(used[i] == false){
                used[i] = true;
                temp.add(nums[i]);
                permuteHandler(nums,used);
                used[i] = false;
                temp.remove(temp.size() - 1);
                }
        }
    }
}

332、重新安排行程

//基本參考代碼隨想錄
class Solution {
    public LinkedList<String> result;
    public LinkedList<String> path = new LinkedList<String>();
    public List<String> findItinerary(List<List<String>> tickets) {
        Collections.sort(tickets,(a,b)->a.get(1).compareTo(b.get(1)));
        path.add("JFK");
        int[] used = new int[tickets.size()];
        findItineraryHanlder(tickets, used);
        return result;
    }
    public boolean findItineraryHanlder(List<List<String>> tickets, int[] used){
        if(path.size() == tickets.size() + 1){
            result = new LinkedList<String>(path);
            return true;
        }
        for(int i = 0; i < tickets.size(); i++){
            if(used[i] != 1 && tickets.get(i).get(0).equals(path.getLast())){
                path.add(tickets.get(i).get(1));
                used[i] = 1;
                if(findItineraryHanlder(tickets,used)){
                    return true;
                }
                path.removeLast();
                used[i] = 0;
            }
        }
        return false;
    }
}

51、N 皇後

class Solution {
    public List<List<String>> result = new ArrayList<>();
    public List<String> temp = new ArrayList<>();
    public List<List<String>> solveNQueens(int n) {
        int[] arr = new int[n];
        Arrays.fill(arr, -1); 
        find(arr, 0, n);
        return result;
    }
    public void find(int[] arr, int index,int n){
        if(index == n){
            result.add(new ArrayList<>(temp));
            return;
        }
        for(int i = 0; i < n; i++){
            arr[index] = i;
            if(judge(arr,index)){
                temp.add(setString(n,i));
                find(arr, index+1,n);
                arr[index]=-1;
                temp.remove(temp.size() - 1);
            }
        }
    }
    public boolean judge(int[] arr, int index){
        for(int i = 0; i < index; i++){
            if(arr[i] == arr[index] || Math.abs(index - i)==Math.abs(arr[index]-arr[i])){
                return false;
            }
        }
        return true;
    }
    public String setString(int n, int m){
        StringBuffer str1 = new StringBuffer();
        for(int i = 0; i < n; i++){
            if(i == m){
                str1.append("Q");
            }else{
                str1.append(".");
            }
        }
        return new String(str1);
    }
}

37、解數獨

class Solution {
    public void solveSudoku(char[][] board) {
        solveSudokuHander(board);
    }
    public boolean solveSudokuHander(char[][] board){
        for(int i = 0; i < 9; i++){
            for(int j = 0; j < 9; j++){
                if(board[i][j] != '.'){
                    continue;
                }
                for(char k = '1'; k <= '9'; k++){
                    if(judge(board,i,j,k)){
                        board[i][j] = k;
                        if(solveSudokuHander(board)){
                            return true;
                        }
                        board[i][j] = '.';
                    }
                    
                }
                return false;
            }
        }
        return true;
    }
    public boolean judge(char[][] board, int i, int j, char k){
        for(int m = 0; m < 9; m++){
            if(board[i][m]==k){
                return false;
            }
        }
        for(int n = 0; n < 9; n++){
            if(board[n][j]==k){
                return false;
            }
        }
        int startRow = (i/3)*3;
        int startCol = (j/3)*3;
        for(int m = startRow; m < startRow+3; m++){
            for(int n = startCol; n < startCol+3; n++){
                if(board[m][n]==k){
                    return false;
                }
            }
        }
        return true;
    }
}

您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • Elasticsearch Head插件使用小結
    作者：崔雄華 1 Elasticsearch Head是什麼 ElasticSearch head就是一款能連接ElasticSearch搜索引擎，並提供可視化的操作頁面對ElasticSearch搜索引擎進行各種設置和數據檢索功能的管理插件，如在head插件頁面編寫RESTful介面風格的請求，就 ...
  • 汽車行業：充分借力數據價值，推動數字化營銷鏈路閉環
    當下，汽車行業已慢慢由曾經的增量市場逐步轉變為存量市場。更年輕的消費群體偏好、更精準智能的營銷投放策略和強勢入局的新能源汽車等因素都在推動著汽車行業的不斷發展。對於汽車廠商和垂域媒體來說，進行豐富的人群洞察與用戶分層，能挖掘更多用戶生命周期內的價值。 聯合建模，精準拉新 隨著電商與短視頻的快速發展， ...
  • 用Flutter寫了個博客園APP
    最近在摸魚時看到了一些博客園API文章，就想著摸魚時寫個APP練練手。 現階段實現了以下功能模塊： 博客瀏覽、評論 新聞瀏覽 快閃記憶體瀏覽、發佈、評論 博問瀏覽 用戶登錄 博問暫時只支持瀏覽，不支持回答提問等操作。 支持iOS、Android平臺。 截圖 淺色模式： 深色模式： API 開發前需要先到h ...
  • 教你用JavaScript實現實時字元計數器
    案例介紹 歡迎來到我的小院，我是霍大俠，恭喜你今天又要進步一點點了！我們來用JavaScript編程實戰案例，做一個實時字元計數器。用戶在指定位置打字，程式實時顯示字元數量。 案例演示 在編輯框內輸入字元，下方實時記錄數字，且輸入有數量限制，輸入超出限制的字元後就無法再繼續輸入。 源碼學習 進入核心 ...
  • 微服務洞察，讓微服務更透明
    微服務作為雲原生時代下一種開發軟體的架構和組織方法，通過將明確定義的功能分成更小的服務，並讓每個服務獨立迭代，增加了應用程式的靈活性，允許開發者根據需要更輕鬆地更改部分應用程式。同時每個微服務可以由單獨的團隊進行管理，使用適當的語言編寫，並根據需要進行獨立擴縮容。但微服務同樣也並非“銀彈”，在帶來如... ...
  • keepalived + nginx 實現高可用
    keepalived + nginx 實現高可用 本篇主要介紹一下 keepalived + nginx 來實現 對於nginx的高可用, 還是簡單的主備模式 1.概述 前面有瞭解keepalived 的主備的基本使用, 但是那種是針對宕機等情況 停止了keepalived 的進程實現的 vip的漂 ...
  • 用狀態機實現串口多位元組數據發送
    這次設計一個多位元組(8-256位)且波特率可更改(通過修改例化模塊的參數)的串口發送模塊。 1、狀態機的設定 狀態機的設定有空閑、發送、和數據移位三個狀態，其中空閑狀態為等待多位元組發送的信號； 發送狀態為給8位串口發送模塊傳輸待發送8位的數據同時判斷是否發送完數據回到空閑狀態； 數據移位狀態為等到前 ...
  • day01-傢具網購項目說明
    傢具網購項目說明 1.項目前置技術 Java基礎 正則表達式 Mysql JDBC 資料庫連接池技術 滿漢樓項目(包括框架圖) JavaWeb 2.相關說明 這裡先使用原生的servlet/過濾器，後臺是經典的分層結構WEB-Service-DAO-Entity 在學習SSM時，我們使用SSM框架（ ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發（一）：使用.NET MAUI開發第一個安卓APP
    移動開發（一）：使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說，近來想嘗試開發一款安卓APP，考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP，畢竟是使用Visual Studio開發工具，使用起來也比較的順手，結合微軟官方的教程進行了安卓 ...
  • wpf ToggleButton選中效果和一個登錄界面
    前言 QuestPDF 是一個開源 .NET 庫，用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫，它徹底改變了我們生成 PDF 文檔的方 ...
  • 彈幕樹洞項目功能新增篇
    項目地址 項目後端地址： https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址： ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址： http://tree ...
  • 第27篇 sqlserver2022詳細安裝步驟
    話不多說，直接開乾 一.下載 1.官方鏈接下載： https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe，運行開始下載SQL server； 二. ...
  • .NET 開源高性能 MQTT 類庫
    前言 隨著物聯網（IoT）技術的迅猛發展，MQTT（消息隊列遙測傳輸）協議憑藉其輕量級和高效性，已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫，為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog文檔翻譯系列（六） - 可用的接收器、增強器、格式化輸出
    Serilog支持多種接收器用於日誌存儲，增強器用於添加屬性，LogContext管理動態屬性，支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項，適用於不同需求。 ...
  • 警惕 Visual Studio 屬性求值副作用導致邏輯不符合預期
    目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據，爬取信息時需要模擬瀏覽器行為，否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下： 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • [使用目前最新版]HybridCLR6.9.0+YooAsset2.2.4實現純C# Unity熱更新方案 (一)
    1.前言 什麼是熱更新 游戲或者軟體更新時，無需重新下載客戶端進行安裝，而是在應用程式啟動的情況下，在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR，Xlua，ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles，Addressable， ...
  • 在 ASP.NET Core Web API 中使用操作篩選器統一處理通用操作
    本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺，其實像阿裡雲，騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後，它會送 ...
  • 第28篇 如何.net中實現高效可靠數據同步api
    通過以下方式可以高效，並保證數據同步的可靠性 1.API設計 使用RESTful設計，確保API端點明確，並使用適當的HTTP方法（如POST用於創建，PUT用於更新）。 設計清晰的請求和響應模型，以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證，確保接收到的數據符合預期格 ...
所有分類