每日刷题记录 (十二)

转x33g5p2x  于2022-07-04 转载在 其他  
字(4.1k)|赞(0)|评价(0)|浏览(484)

第一题: 剑指 Offer II 012. 左右两边子数组的和相等

LeetCode: 剑指 Offer II 012. 左右两边子数组的和相等

描述:
给你一个整数数组 nums ，请计算数组的 中心下标 。

数组 中心下标 是数组的一个下标，其左侧所有元素相加的和等于右侧所有元素相加的和。

如果中心下标位于数组最左端，那么左侧数之和视为 0 ，因为在下标的左侧不存在元素。这一点对于中心下标位于数组最右端同样适用。

如果数组有多个中心下标，应该返回 最靠近左边 的那一个。如果数组不存在中心下标，返回 -1 。

解题思路:

  1. 这里直接记录所有的总和, 给 rightTotal
  2. 遍历数组.
  3. 让leftTotal记录左侧的所有元素的和, rightTotal 记录右侧所有元素的和.
  4. 如果当前 leftTotal 和 rightTotal 值相等. 返回当前下标.

代码实现:

  1. class Solution {
  2.     public int pivotIndex(int[] nums) {
  3.         int rightTotal = 0;
  4.         int leftTotal = 0;
  5.         for(int num : nums) {
  6.             rightTotal += num;
  7.         }
  8.         for(int i = 0; i < nums.length; i++) {
  9.         	// 注意这里先右边减了 再判断了 然后左边加.
  10.             rightTotal -= nums[i];
  11.             if (leftTotal == rightTotal) return i;
  12.             leftTotal += nums[i];
  13.         }
  14.         return -1;
  15.     }
  16. }

第二题: 剑指 Offer II 014. 字符串中的变位词

LeetCode: 剑指 Offer II 014. 字符串中的变位词

描述:
给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的某个变位词。

换句话说，第一个字符串的排列之一是第二个字符串的 子串 。

解题思路:

  1. 使用滑动窗口来解决.
  2. 首先使用一个数组记录s1中 字符串出现的次数
  3. 然后将所有的没出现的字符变成-1
  4. 建立一个范围为 [left,right] 的滑动窗口.

  • 如果当前right下标的元素在数组中存在

  • 如果当前次数大于0, 则让该元素对应的数组下标减1, 窗口变大一个(right++).

  • 如果当前次数等于0, 如果当前left和right下标元素不相同, 就需要左边窗口变小(left++). 如果相同了, 就让窗口往右滑动一个(left++,right++)

  • 如果当前right下标的元素在数组中不存在.如果当前left和right不在同以下标,则表示当前已经进行窗口变化,且当前元素又不存在,就需要重新初始化窗口,

代码实现:

  1. class Solution {
  2.     public boolean checkInclusion(String s1, String s2) {
  3.         int[] arr = new int[26];
  4.         for(char ch : s1.toCharArray()) {
  5.             arr[ch-'a']++;
  6.         }
  7.         for (int i = 0; i < 26; i++) {
  8.             if (arr[i] == 0) arr[i] = -1;
  9.         }
  10.         int left = 0;
  11.         int right = 0;
  12.         int total = s1.length();
  13.         while (total > 0 && right < s2.length()) {
  14.             int tmp = arr[s2.charAt(right)-'a'];
  15.             if (tmp == -1) {
  16.                 while (left < right) {
  17.                     arr[s2.charAt(left) - 'a']++;
  18.                     total++;
  19.                     left++;
  20.                 }
  21.                 left = right + 1;
  22.                 right = left;
  23.             } else {
  24.                 if (tmp > 0) {
  25.                     total--;
  26.                     arr[s2.charAt(right)-'a']--;
  27.                     right++;
  28.                 }else {
  29.                     while(s2.charAt(left) != s2.charAt(right)) {
  30.                         total++;
  31.                         arr[s2.charAt(left) - 'a']++;
  32.                         left++;
  33.                     }
  34.                     left++;
  35.                     right++;
  36.                 }
  37.             }
  38.         }
  39.         return total == 0;
  40.     }
  41. }

第三题: 剑指 Offer II 016. 不含重复字符的最长子字符串

LeetCode: 剑指 Offer II 016. 不含重复字符的最长子字符串

描述:
给定一个字符串 s ，请你找出其中不含有重复字符的 最长连续子字符串 的长度。

解题思路:

  1. 这里是使用滑动窗口解题.
  2. 范围为 [left,right]的滑动窗口. 将字符串加入list记录
  3. 如果当前right下标的元素存在, 就删除list中首元素, 让left++, 直到right下标元素在list中不存在.
  4. 将right下标的元素加入list中, 记录下当前滑动窗口的大小(right-left+1)
  5. 遍历结束,返回最大的滑动窗口大小.

代码实现:

  1. class Solution {
  2.     public int lengthOfLongestSubstring(String s) {
  3.         int left = 0;
  4.         int right = 0;
  5.         int ans = 0;
  6.         List<Character> list = new ArrayList<>();
  7.         while (right < s.length()) {
  8.             while(left < right && list.contains(s.charAt(right))) {
  9.                 list.remove(0);
  10.                 left++;
  11.             }
  12.             list.add(s.charAt(right));
  13.             ans = Math.max(ans,right-left+1);
  14.             right++;
  15.         }
  16.         return ans;
  17.     }
  18. }

第四题: 剑指 Offer II 018. 有效的回文

LeetCode: 剑指 Offer II 018. 有效的回文

描述:
给定一个字符串 s ，验证 s 是否是 回文串 ，只考虑字母和数字字符，可以忽略字母的大小写。

本题中，将空字符串定义为有效的 回文串 。

解题思路:

  1. 遍历字符串, 只要字符串是数字和字符就把他变成一个新的字符串.
  2. 使用双指针遍历字符串.
  3. 如果 left下标和 right 下标的字的内容一样, 就 left++. right--;
  4. 如果不一样,直接返回 false ;
  5. 遍历结束返回 true ;

代码实现:

  1. class Solution {
  2.     public boolean isPalindrome(String s) {
  3.         String ret = "1234567890abcdefghijklmnopqlstuvwxyz";
  4.         StringBuilder sb = new StringBuilder();
  5.         s = s.toLowerCase();
  6.         for (int i = 0; i < s.length(); i++) {
  7.             if(ret.contains(s.charAt(i)+"")){
  8.                 sb.append(s.charAt(i));
  9.             }
  10.         }
  11.         int left = 0;
  12.         int right = sb.length()-1;
  13.         while(left <= right) {
  14.             if(sb.charAt(left) == sb.charAt(right)) {
  15.                 left++;
  16.                 right--;
  17.             }else{
  18.                 return false;
  19.             }
  20.         }
  21.         return true;
  22.     }
  23. }

第五题: 剑指 Offer II 019. 最多删除一个字符得到回文

LeetCode: 剑指 Offer II 019. 最多删除一个字符得到回文

描述:
给定一个非空字符串 s，请判断如果 最多 从字符串中删除一个字符能否得到一个回文字符串。

解题思路:

  1. 这里首先进行判断, 当前是否是回文字符串
  2. 如果是就返回true;
  3. 如果不是就去判断当前[left,right-1] 或 [left+1,right]是否是回文字符串.只要有一个是就是true;

代码实现:

  1. class Solution {
  2.     public boolean validPalindrome(String s) {
  3.         int left = 0;
  4.         int right = s.length()-1;
  5.         while(left <= right) {
  6.             if(s.charAt(left) == s.charAt(right)){
  7.                 left++;
  8.                 right--;
  9.             }else{
  10.                 return isHui(s,left,right-1) || isHui(s,left+1,right);
  11.             }
  12.         }
  13.         return true;
  14.     }
  15.     public boolean isHui(String s, int left, int right) {
  16.         while(left <= right) {
  17.             if(s.charAt(left) == s.charAt(right)) {
  18.                 left++;
  19.                 right--;
  20.             }else{
  21.                 return false;
  22.             }
  23.         }
  24.         return true;
  25.     }
  26. }

第六题: 剑指 Offer II 020. 回文子字符串的个数

LeetCode: 剑指 Offer II 020. 回文子字符串的个数

描述:
给定一个字符串 s ，请计算这个字符串中有多少个回文子字符串。

具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

解题思路:

  1. 这里使用动态规划解题.
  2. 状态 F(i,j) : 表示 i~j是否是回文串
  3. 状态转移方程: 当前 j == i 时, F(i,j) = true; 当 j - i == 1时,F(i,j)=s.charAt(i) == s.charAt(j);当 j-i > 1时, F(i,j) = s.charAt(i) == s.charAt(j) && dp[i+1][j-1] (dp[i+1][j-1] ,就是[i+1,j-1]是否是回文串)
  4. 初始状态: 单个字符是 true;
  5. 返回结果: dp[i][j] 为true的个数

代码实现:

  1. class Solution {
  2.     public int countSubstrings(String s) {
  3.         boolean[][] dp = new boolean[s.length()][s.length()];
  4.         int count = 0;
  5.         for(int i = s.length()-1; i >= 0; i--) {
  6.             for(int j = s.length()-1; j>=i; j--){
  7.                 if(j == i) dp[i][j] = true;
  8.                 else if(j - i == 1) {
  9.                     dp[i][j] = s.charAt(i) == s.charAt(j);
  10.                 }else{
  11.                     dp[i][j] = s.charAt(i) == s.charAt(j) && dp[i+1][j-1];
  12.                 }
  13.                 if(dp[i][j]) count++;
  14.             }
  15.         }
  16.         return count;
  17.     }
  18. }

版权说明 : 本文为转载文章, 版权归原作者所有 版权申明

原文链接 : https://wangzhi430.blog.csdn.net/article/details/125589698

内容来源于网络，如有侵权，请联系作者删除！

leetcode算法二叉树深度优先宽度优先

相关文章

    查看更多

    热门标签

    更多
    JavaquerypythonNode开发语言requestUtil数据库Table后端算法LoggerMessageElementParser

    最新文章

    更多
    • 蜀ICP备13028337号-1 大数据知识库 https://www.saoniuhuo.com © All rights reserved
    • 本站内容来源互联网,如果侵犯您的权益请联系我们删除, 联系方式：448109455@qq.com