Teknik Pemotretan Dua Titik – beragampengetahuan – Beragampengetahuan

Aloha, teman-teman. Hari ini, kita akan menangani masalah yang lebih umum dan memperbaikinya menggunakan teknik dua poin.

Pendekatan ini banyak digunakan dalam tugas-tugas wawancara. Sangat penting untuk membaca pola dalam kondisi masalah dan menggunakannya saat memecahkan masalah. Metode ini bertujuan untuk membuat dua pointer, biasanya pointer cepat dan pointer lambat. Setelah itu, tergantung pada situasi masalahnya, kami akan memindahkan penunjuk cepat/lambat.

Pendekatan ini akan lebih jelas dengan sebuah contoh. Prioritas utama kami:

palindrom yang valid

menggambarkan

kalimat adalah a palindrom Jika, setelah mengonversi semua huruf besar menjadi huruf kecil dan menghapus semua karakter non-alfanumerik, bacaannya sama maju dan mundur. Karakter alfanumerik meliputi huruf dan angka.

diberi tali skembali true jika memang palindromatau false jika tidak.

Contoh 1:

Input: s = "A man, a plan, a canal: Panama"
Output: true
Explanation: "amanaplanacanalpanama" is a palindrome.

Contoh 2:

Input: s = "race a car"
Output: false
Explanation: "raceacar" is not a palindrome.

Contoh 3:

Input: s = " "
Output: true
Explanation: s is an empty string "" after removing non-alphanumeric characters.
Since an empty string reads the same forward and backward, it is a palindrome.

larutan

Mari kita mulai dengan contoh sederhana, abaMenurut deskripsi, kita harus memeriksa awal dan akhir. Jika sama, kita harus memeriksa pasangan berikutnya. Apakah itu jelas?

Untuk ini kita dapat menambahkan dua petunjuk, awal dan akhir.Untuk berpindah ke pasangan lain, kita dapat menaikkan penunjuk awal dan mengurangi penunjuk akhir (start++, end--).

Tetapi dalam string kami, kami dapat memiliki beberapa karakter tertentu seperti : atau *. Apa yang harus kita lakukan tentang ini? Kita dapat melewati karakter ini dan bergerak maju atau mundur. Untuk pemahaman yang lebih baik, jika karakter saat ini pada penunjuk awal bukan huruf atau angka, kita harus menambahkannya (atau mengurangi penunjuk akhir).

Mari selami bagian kode:

Kode

public boolean isPalindrome(String s) {
    if (s == null || s.isEmpty()) {
      return false;
    }
    if (s.length() == 1) {
      return true;
    }

    int start = 0;
    int end = s.length() - 1;
    s = s.toLowerCase();
    while (start < end) {
      char a = s.charAt(start);
      char b = s.charAt(end);
      if (!Character.isLetterOrDigit(a)) {
        start++;
        continue;
      }
      if (!Character.isLetterOrDigit(b)) {
        end--;
        continue;
      }

      if (a != b) {
        return false;
      }
      start++;
      end--;
    }
    return true;
}

Pertanyaan kita selanjutnya adalah:

Dua dan II — larik input diurutkan

menggambarkan

diberikan a 1-indeks susunan bilangan bulat numbers itu sudah urutan tidak menuruntemukan dua angka sedemikian rupa sehingga mereka menambahkan hingga tertentu target nomor.Biarkan dua angka ini numbers[index1] Dan numbers[index2] Di mana 1 <= index1 < index2 <= numbers.length.

kembali dua indeks numerik, index1 Dan index2, tambah satu sebagai array bilangan bulat [index1, index2] Panjangnya 2.

Hasilkan tes sedemikian rupa sehingga ada tepat satu solusi. Anda tidak harus Gunakan elemen yang sama dua kali.

Solusi Anda harus menggunakan ruang ekstra konstan saja.

Contoh 1:

Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore, index1 = 1, index2 = 2. We return [1, 2].

Contoh 2:

Input: numbers = [2,3,4], target = 6
Output: [1,3]
Explanation: The sum of 2 and 4 is 6. Therefore index1 = 1, index2 = 3. We return [1, 3].

Contoh 3:

Input: numbers = [-1,0], target = -1
Output: [1,2]
Explanation: The sum of -1 and 0 is -1. Therefore index1 = 1, index2 = 2. We return [1, 2].

larutan

Kami tahu susunan angka kami diurutkan. Tapi apa artinya itu?mewakili numbers[0] < numbers[1] dll. Bisakah kita menggunakannya? Tentu saja, kita bisa menyiapkan dua petunjuk, awal dan akhir. Kami kemudian dapat memeriksa jumlah elemen pada pointer ini.menyukai numbers[start] + numbers[end].Setelah itu, kita harus menganalisis jumlahnya. Jika jumlah kita lebih besar dari target, kita harus meningkatkannya. Jika jumlah kita lebih besar dari target, kita harus menguranginya. Sudah jelas, kan? Untuk menambah jumlah, kita harus memindahkan penunjuk awal ke depan dan menurunkan penunjuk akhir untuk mengurangi jumlah.

Kode

public int[] twoSum(int[] numbers, int target) {
  int[] rez = new int[2];

  int start = 0;
  int end = numbers.length - 1;

  while (start < end) {
    int a = numbers[start];
    int b = numbers[end];
    if (a + b == target) {
      rez[0] = start + 1;
      rez[1] = end + 1;
      return rez;
    } else if (a + b > target) {
      end--;
    } else {
      start++;
    }
  }
  return rez;
}

Selamat. Sekarang Anda tahu cara menjumlahkan dalam array yang diurutkan.

Pertanyaan terakhir kita hari ini adalah:

3 jumlah

menggambarkan

Diberi bilangan array bilangan bulat, kembalikan semua kembar tiga [nums[i], nums[j], nums[k]] Jadi i != j, i != kDan j != kDan nums[i] + nums[j] + nums[k] == 0.

Perhatikan bahwa kumpulan solusi tidak boleh berisi rangkap tiga kali lipat.

Contoh 1:

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Explanation: 
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.
The distinct triplets are [-1,0,1] and [-1,-1,2].
Notice that the order of the output and the order of the triplets does not matter.

Contoh 2:

Input: nums = [0,1,1]
Output: []
Explanation: The only possible triplet does not sum up to 0.

Contoh 3:

Input: nums = [0,0,0]
Output: [[0,0,0]]
Explanation: The only possible triplet sums up to 0.

larutan

Ini adalah pertanyaan wawancara yang populer. Saya akan menunjukkan solusi dengan dua petunjuk.

Gagasan utama dari algoritme ini adalah untuk memeriksa semua tiga kali lipat yang tersedia dan menambah atau mengurangi jumlahnya tergantung pada hasilnya.

Pertama, kita perlu mengurutkan array. Lalu saya ingin mengulang array dan mendapatkan elemen satu di indeks i.

Kemudian kita bisa menyiapkan dua elemen.Jadi, elemen kedua (penunjuk awal) akan berada pada posisinya saya +1, Yang ketiga (penunjuk ujung) akan berada di posisi Panjang – 1. Kemudian berdasarkan jumlah tersebut, kita dapat memindahkan penunjuk awal/akhir.

Kode

public List<List<Integer>> threeSum(int[] nums) {
  if (nums.length < 3) {
    return new ArrayList<>();
  }

  Arrays.sort(nums);

  List<List<Integer>> rez = new ArrayList<>();

  for (int i = 0; i < nums.length; i++) {
    if (i > 0 && nums[i] == nums[i - 1]) {
      continue;
    }
    int start = i + 1;
    int end = nums.length - 1;

    while (start < end) {
      int threeSum = nums[i] + nums[start] + nums[end];

      if (threeSum == 0) {
        List<Integer> tmp = List.of(nums[i], nums[start], nums[end]);
        rez.add(tmp);
        // todo add while iteration
        while (start < end && nums[start] == nums[start + 1]) {
          start++;
        }
        while (end > start && nums[end - 1] == nums[end]) {
          end--;
        }
        start++;
        end--;

      } else if (threeSum > 0) {
        end--;
      } else {
        start++;
      }
    }
  }
  return rez;
}

Alternatifnya, kita dapat mencoba menyelesaikan masalah ini dengan hashing. Tapi itu topik untuk artikel lain.