当前位置：首页 > news >正文

华为od面试手撕代码真题题型6——传统双指针

news 2024/10/22 16:45:49

传统双指针

1 三数之和

15. 三数之和 - 力扣（LeetCode）

public List<List<Integer>> threeSum(int[] nums) {//对数组nums排序Arrays.sort(nums);//lists保存结果List<List<Integer>> lists = new ArrayList<>();int n = nums.length;for (int i = 0;i < n; i ++){int cur = nums[i];//如果cur大于0，则直接退出循环 if (cur > 0) break;//如果cur与之前一个元素相同，则跳过if (i > 0 && cur == nums[i - 1]) continue;//转成在[i+1,n-1]中求两数之和为target的问题int target = -nums[i];//定义左右指针int left = i + 1, right = n - 1;while (left < right){int lNum = nums[left];int rNum = nums[right];if (lNum + rNum == target){List<Integer> list = new ArrayList<>();list.add(cur);list.add(lNum);list.add(rNum);lists.add(list);//接着左指针右移 右指针左移 同时要跳过相同的数while(left + 1 < right && nums[left + 1] == lNum) left ++;while(left < right - 1 && nums[right - 1] == rNum) right --;left ++;right --;}else if (lNum + rNum > target){right --;}else{left ++;}}}return lists;
}

2 最长回文字符串

5. 最长回文子串 - 力扣（LeetCode）

思路**:两重for**循环拿到所有可能长度的子串根据下标判断子串是否回文串若是判断是否需要更新最长回文子串的[begin,end)

暴力解，用到了双指针

public String longestPalindrome(String s) {int n = s.length();char[] chars = s.toCharArray();//记录最长回文子串的长度int max = 0;//记录最长回文子串的起始下标int begin = 0;int end = 0;//i遍历所有起始位置   [i,j]for(int i = 0; i < n; i ++) {//j遍历所有结束位置for (int j = i; j < n; j ++){//若s下标[i,j]是回文串 if (isHW(chars,i,j)){//判断是否需要更新if (j - i + 1 > max){max = j - i + 1;begin = i;end = j + 1;}}}}return s.substring(begin, end);
}public boolean isHW(char[] chars,int left,int right){while(left <= right){if (chars[left] != chars[right]) return false;left ++;right --;}return true;
}

3 判断回文串

125. 验证回文串 - 力扣（LeetCode）

public boolean isPalindrome(String s) {//将所有大写字母转为小写字母s = s.toLowerCase();//将所有非小写字母 数字字符替换成空字符（移除所有非小写字母 数字字符）s = s.replaceAll("[^0-9a-z]","");int n = s.length();int left = 0, right = n - 1;while(left < right){char lc = s.charAt(left);char rc = s.charAt(right);if (lc != rc) return false;left ++;right --;}return true; }

4 回文子串

本人二面手撕代码原题，最优解要用到动态规划思想，我没有想出来，本人最后写出暴力解如下，暴力解思路就是拿到所有子串，判断子串是否是回文串，是数量就+1

647. 回文子串 - 力扣（LeetCode）

    public int getSumHw(String s){int n = s.length();char[] chars = s.toCharArray();int cnt = 0; //记录回文子串的数量for(int start = 0; start < n; start ++){for (int end = start + 1; end <= n; end++) {//判断s中[start,end) 是否是回文串if (isHW(chars, start, end)){cnt ++;}}}return cnt;}//判断chars数组中[start,end-1]下标组成的字符串是否是回文串private boolean isHW(char[] chars, int start, int end) { int left = start, right = end - 1;while (left < right){if (chars[left] != chars[right]) {return false;}left ++;right --;}return true;}