力扣第 119 場雙周賽(Java)

文章目錄

    • T1 找到兩個數組中的公共元素
      • 代碼解釋
    • T2 消除相鄰近似相等字符
      • 代碼解釋
    • T3 最多 K 個重復元素的最長子數組
      • 代碼解釋
    • T4 關閉分部的可行集合數目
      • 代碼解釋

鏈接:第 119 場雙周賽 - 力扣(LeetCode)

T1 找到兩個數組中的公共元素

給你兩個下標從 0 開始的整數數組 nums1nums2 ,它們分別含有 nm 個元素。

請你計算以下兩個數值:

統計 0 <= i < n 中的下標 i ,滿足 nums1[i]nums2 中 至少 出現了一次。
統計 0 <= i < m 中的下標 i ,滿足 nums2[i]nums1 中 至少 出現了一次。
請你返回一個長度為 2 的整數數組 answer ,按順序 分別為以上兩個數值。

示例 :

輸入:nums1 = [4,3,2,3,1], nums2 = [2,2,5,2,3,6]
輸出:[3,4]
解釋:分別計算兩個數值:

  • nums1 中下標為 1 ,2 和 3 的元素在 nums2 中至少出現了一次,所以第一個值為 3 。
  • nums2 中下標為 0 ,1 ,3 和 4 的元素在 nums1 中至少出現了一次,所以第二個值為 4 。

提示:

  • n == nums1.length
  • m == nums2.length
  • 1 <= n, m <= 100
  • 1 <= nums1[i], nums2[i] <= 100

代碼解釋

暴力 O(n^2)

class Solution {public int[] findIntersectionValues(int[] nums1, int[] nums2) {int[] ans = new int[]{0, 0};for (int k : nums1) {for (int i : nums2) {if (k == i) {ans[0]++;break;}}}for (int k : nums2) {for (int i : nums1) {if (k == i) {ans[1]++;break;}}}return ans;}
}

T2 消除相鄰近似相等字符

給你一個下標從 0 開始的字符串 word

一次操作中,你可以選擇 word 中任意一個下標 i ,將 word[i] 修改成任意一個小寫英文字母。

請你返回消除 word 中所有相鄰 近似相等 字符的 最少 操作次數。

兩個字符 ab 如果滿足 a == b 或者 ab 在字母表中是相鄰的,那么我們稱它們是 近似相等 字符。

示例 1:

輸入:word = “aaaaa”
輸出:2
解釋:我們將 word 變為 “acaca” ,該字符串沒有相鄰近似相等字符。 消除 word 中所有相鄰近似相等字符最少需要 2 次操作。

示例 2:

輸入:word = “abddez”
輸出:2
解釋:我們將 word 變為 “ybdoez” ,該字符串沒有相鄰近似相等字符。 消除 word 中所有相鄰近似相等字符最少需要 2 次操作。

示例 3:

輸入:word = “zyxyxyz”
輸出:3
解釋:我們將 word 變為 “zaxaxaz” ,該字符串沒有相鄰近似相等字符。 消除 word 中所有相鄰近似相等字符最少需要 3 次操作

提示:

  • 1 <= word.length <= 100
  • word 只包含小寫英文字母。

代碼解釋

一次遍歷,相鄰近似相等字符換一次右邊的就是操作次數最少的

class Solution {public int removeAlmostEqualCharacters(String word) {int ans = 0;for (int i = 1; i < word.length(); i++) {if (Math.abs(word.charAt(i) - word.charAt(i-1)) < 2) {ans++;i++;}}return ans;}
}

T3 最多 K 個重復元素的最長子數組

給你一個整數數組 nums 和一個整數 k

一個元素 x 在數組中的 頻率 指的是它在數組中的出現次數。

如果一個數組中所有元素的頻率都 小于等于 k ,那么我們稱這個數組是 數組。

請你返回 nums最長好 子數組的長度。

子數組 指的是一個數組中一段連續非空的元素序列。

示例 1:

輸入:nums = [1,2,3,1,2,3,1,2], k = 2
輸出:6
解釋:最長好子數組是 [1,2,3,1,2,3] ,值 1,2 和 3 在子數組中的頻率都沒有超過 k = 2 。[2,3,1,2,3,1] 和 [3,1,2,3,1,2] 也是好子數組。最長好子數組的長度為 6 。

示例 2:

輸入:nums = [1,2,1,2,1,2,1,2], k = 1
輸出:2
解釋:最長好子數組是 [1,2] ,值 1 和 2 在子數組中的頻率都沒有超過 k = 1 。[2,1] 也是好子數組。 最長好子數組的長度為 2 。

示例 3:

輸入:nums = [5,5,5,5,5,5,5], k = 4
輸出:4
解釋:最長好子數組是 [5,5,5,5] ,值 5 在子數組中的頻率沒有超過 k = 4 。 最長好子數組的長度為 4 。

提示:

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^9
  • 1 <= k <= nums.length

代碼解釋

滑動窗口,哈希表記次數大于 K 時左邊界右移,時間復雜度 O(n)

class Solution {public int maxSubarrayLength(int[] nums, int k) {int ans = 0, l = 0, r = 0, n = nums.length;Map<Integer, Integer> map = new HashMap<>();while (r < n) {map.put(nums[r], map.getOrDefault(nums[r], 0) + 1);while (map.get(nums[r]) > k) {map.put(nums[l], map.get(nums[l]) - 1);l++;}ans = Math.max(ans, ++r - l);}return ans;}
}

T4 關閉分部的可行集合數目

一個公司在全國有 n 個分部,它們之間有的有道路連接。一開始,所有分部通過這些道路兩兩之間互相可以到達。

公司意識到在分部之間旅行花費了太多時間,所以它們決定關閉一些分部(也可能不關閉任何分部),同時保證剩下的分部之間兩兩互相可以到達且最遠距離不超過 maxDistance

兩個分部之間的 距離 是通過道路長度之和的 最小值

給你整數 nmaxDistance 和下標從 0 開始的二維整數數組 roads ,其中 roads[i] = [ui, vi, wi] 表示一條從 uivi 長度為 wi無向 道路。

請你返回關閉分部的可行方案數目,滿足每個方案里剩余分部之間的最遠距離不超過 maxDistance

注意,關閉一個分部后,與之相連的所有道路不可通行。

注意,兩個分部之間可能會有多條道路。

提示:

  • 1 <= n <= 10
  • 1 <= maxDistance <= 105
  • 0 <= roads.length <= 1000
  • roads[i].length == 3
  • 0 <= ui, vi <= n - 1
  • ui != vi
  • 1 <= wi <= 1000
  • 一開始所有分部之間通過道路互相可以到達。

代碼解釋

這次最后一題比較簡單,就是 位運算 可以將每個節點選就是 1 不選就是 0,使用 弗洛伊德算法(Floyd) 求最短路,時間復雜度最壞為 O ( 2 n n 3 ) O(2^nn^3) O(2nn3)

class Solution {public int numberOfSets(int n, int maxDistance, int[][] roads) {int ans = 0;int[][] g = new int[n][n];for (int s = (1 << n) - 1; s >= 0; s--) {for (int i = 0; i < n; i++) {Arrays.fill(g[i], Integer.MAX_VALUE / 2);g[i][i] = 0;}for (int[] r : roads) {int u = r[0], v = r[1], w = r[2];if ((s >> u & 1) != 0 && (s >> v & 1) != 0) {g[u][v] = Math.min(g[u][v], w);g[v][u] = Math.min(g[v][u], w);}}for (int k = 0; k < n; k++) {for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {g[i][j] = Math.min(g[i][j], g[i][k] + g[k][j]);}}}int max = 0;for (int u = 0; u < n; u++) {for (int v = 0; v < n; v++) {if ((s >> u & 1) != 0 && (s >> v & 1) != 0) {max = Math.max(max, g[u][v]);}}}if (max <= maxDistance) ans++;}return ans;}
}

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/news/211787.shtml
繁體地址,請注明出處:http://hk.pswp.cn/news/211787.shtml
英文地址,請注明出處:http://en.pswp.cn/news/211787.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

Xcode doesn’t support iOS 16.6

xocde版本低&#xff0c;手動放入16.6的依賴文件 https://gitee.com/qiu1993/iOSDeviceSupport/blob/master/iOS16/16.6.zip 路徑 /Applications/Xcode.app/Contents/Developer/Platforms/iPhoneOS.platform/DeviceSupport

JAVA全棧開發 day21_JDBC與反射結合、設計模式

一、總結 一階段 day01 java 發展&#xff0c;java 環境( path, java_home, class_path)&#xff0c;java 原理&#xff0c; java 執行 &#xff0c; jvm , jre , jdk day02 變量 標識符命名規則 數據類型 數據類型的轉換 運算符 day03 選擇結構 if , switch day04 循環結…

分割回文串

分割回文串 描述 : 給你一個字符串 s&#xff0c;請你將 s 分割成一些子串&#xff0c;使每個子串都是 回文串 。返回 s 所有可能的分割方案。 回文串 是正著讀和反著讀都一樣的字符串。 題目 : LeetCode 131.分割回文串 : 131. 分割回文串 分析 : 字符串如何判斷回文本…

20 Redis進階 - 運維監控

1、理解Redis監控 Redis運維和監控的意義不言而喻&#xff0c;可以以下三個方面入手 1.首先是Redis自身提供了哪些狀態信息&#xff0c;以及有哪些常見的命令可以獲取Redis的監控信息; 2.一些常見的UI工具可以可視化的監控Redis; 3.理解Redis的監控體系;2、Redis自身狀態及命…

Vue3-02-ref() 響應式詳解

ref() 是什么 ref() 是一個函數&#xff1b; ref() 函數用來聲明響應式的狀態&#xff08;就是來聲明變量的&#xff09; ref() 函數聲明的變量&#xff0c;是響應式的&#xff0c;變量的值改變之后&#xff0c;頁面中會自動重新渲染。ref() 有什么特點 1.ref() 可以聲明基礎…

VUE語法--toRefs與toRef用法

1、功能概述 ref和reactive能夠定義響應式的數據&#xff0c;當我們通過reactive定義了一個對象或者數組數據的時候&#xff0c;如果我們只希望這個對象或者數組中指定的數據響應&#xff0c;其他的不響應。這個時候我們就可以使用toRefs和toRef實現局部數據的響應。 toRefs是…

算一算并輸出2到正整數n中每個數的質因子(for循環)

計算并輸出2到正整數n之間每個數的質因子&#xff0c;并以乘法形式輸出。 輸入格式: 輸入只有1個正整數即n。 輸出格式: 把2到正整數n間的每一個數分解成它的質因子&#xff0c;并以乘法的形式輸出。例如&#xff0c;輸入的正整數n值為10&#xff0c;則應輸出如下&#xff…

MIT線性代數筆記-第28講-正定矩陣,最小值

目錄 28.正定矩陣&#xff0c;最小值打賞 28.正定矩陣&#xff0c;最小值 首先正定矩陣是一個實對稱矩陣 由第 26 26 26講的末尾可知正定矩陣有以下四種判定條件&#xff1a; 所有特征值都為正左上角所有 k k k階子矩陣行列式都為正&#xff08; 1 ≤ k ≤ n 1 \le k \le n …

DDD系列 - 第6講 倉庫Repository及Mybatis、JPA的取舍(一)

目錄 一、領域層定義倉庫接口1.1 設計聚合1.2 定義倉庫Repository接口二 、基礎設施層實現倉庫接口2.1 設計數據庫2.2 集成Mybatis2.3 引入Convetor2.4 實現倉庫三、回顧一、領域層定義倉庫接口 書接上回,之前通過一個關于拆解、微服務、面向對象的故事,向大家介紹了如何從微…

簡單的WEB服務器

優質博文&#xff1a;IT-BLOG-CN 目的&#xff1a; 了解Java Web服務器是如何運行的。Web服務器使用HTTP與其客戶端&#xff0c;也就是Web瀏覽器進行通信。基于Java的Web服務器會使用兩個重要類&#xff1a;java.net.Socket類和java.net.ServerSocket類&#xff0c;并通過發送…

詳解Keras3.0 Models API: Model class

1、語法 keras.Model() 將不同層組為具有訓練/推理特征的對象的模型 2、示例一 inputs keras.Input(shape(37,)) x keras.layers.Dense(32, activation"relu")(inputs) outputs keras.layers.Dense(5, activation"softmax")(x) model keras.Model…

58.Nacos源碼分析2

三、服務心跳。 3.服務心跳 Nacos的實例分為臨時實例和永久實例兩種&#xff0c;可以通過在yaml 文件配置&#xff1a; spring:application:name: order-servicecloud:nacos:discovery:ephemeral: false # 設置實例為永久實例。true&#xff1a;臨時; false&#xff1a;永久ser…

MySQL-備份+日志:介質故障與數據庫恢復

目錄 第1關&#xff1a;備份與恢復 第2關&#xff1a;備份日志&#xff1a;介質故障的發生與數據庫的恢復 第1關&#xff1a;備份與恢復 任務描述 本關任務: 備份數據庫&#xff0c;然后再恢復它。 test1_1.sh # 你寫的命令將在linux的命令行運行 # 對數據庫residents作海…

【C/C++筆試練習】多態的概念、虛函數的概念、虛表地址、派生類的虛函數、虛函數的訪問、指針引用、動態多態、完全數計算、撲克牌大小

文章目錄 C/C筆試練習選擇部分&#xff08;1&#xff09;多態的概念&#xff08;2&#xff09;虛函數的概念&#xff08;3&#xff09;虛表地址&#xff08;4&#xff09;派生類的虛函數&#xff08;5&#xff09;虛函數的訪問&#xff08;6&#xff09;分析程序&#xff08;7&…

C# WPF上位機開發(會員管理軟件)

【 聲明&#xff1a;版權所有&#xff0c;歡迎轉載&#xff0c;請勿用于商業用途。 聯系信箱&#xff1a;feixiaoxing 163.com】 好多同學都認為上位機只是純軟件開發&#xff0c;不涉及到硬件設備&#xff0c;比如聽聽音樂、看看電影、寫寫小的應用等等。如果是消費電子&#…

HibernateJPA快速搭建

1. 先創建一個普通Maven工程&#xff0c;導入依賴 <dependencies><dependency><groupId>junit</groupId><artifactId>junit</artifactId><version>4.12</version><scope>test</scope></dependency><depe…

Java 匿名內部類使用的外部變量,為什么一定要加 final?

問題描述 Effectively final Java 1.8 新特性&#xff0c;對于一個局部變量或方法參數&#xff0c;如果他的值在初始化后就從未更改&#xff0c;那么該變量就是 effectively final&#xff08;事實 final&#xff09;。 這種情況下&#xff0c;可以不用加 final 關鍵字修飾。 …

報錯:Parsed mapper file: ‘file mapper.xml 導致無法啟動

報錯 &#xff1a; Logging initialized using class org.apache.ibatis.logging.stdout.StdOutImpl adapter. Registered plugin: com.github.yulichang.interceptor.MPJInterceptor3b2c8bda Parsed mapper file: file [/Mapper.xml] application無法啟動 我這邊產生原因是項…

K8S學習指南(4)-minikube的使用

文章目錄 簡介安裝 Minikube啟動 Minikube 集群基本概念創建和管理資源1. 創建 Pod2. 創建 Deployment3. 創建 Service 監視和調試1. 查看集群狀態2. 查看集群信息3. 訪問 Kubernetes Dashboard4. 使用 kubectl 命令 清理資源1. 刪除 Pod2. 刪除 Deployment3. 刪除 Service4. 停…

! [remote rejected] master -> master (pre-receive hook declined)

! [remote rejected] master -> master (pre-receive hook declined) 如圖&#xff1a; 出錯解決方法 首先輸入命令 git branch xindefenzhi然后&#xff0c;進入這個新創建的分支 git checkout branch然后重新git push就可以了